Foundations of software
CS-452
Lecture 3: Programming in the untyped lambda calculus and recursion
This page is part of the content downloaded from Lecture 3: Programming in the untyped lambda calculus and recursion on Monday, 30 June 2025, 16:54. Note that some content and any files larger than 50 MB are not downloaded.
Description
Finishing week 3 slides (Programming with lambda calculus).
Slides are augmented with new material on recursion.
Takeaway: one can represent data and "program" in lambda calculus.
- Encoding datatypes (sum and product) through Scott encoding. Boolean, Product, Sum.
- Another encoding: Church encoding. Predecessors
- Discussion of differences between the two encodings: https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encoding#Comparison_to_the_Church_encoding
Slides are augmented with new material on recursion.
Takeaway: one can represent data and "program" in lambda calculus.
- Encoding datatypes (sum and product) through Scott encoding. Boolean, Product, Sum.
- Another encoding: Church encoding. Predecessors
- Discussion of differences between the two encodings: https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encoding#Comparison_to_the_Church_encoding