Chapter 2 λ Calculus The λ (lambda) calculus [7] created by Church and Kleene in the 1930’s is at the heart of functional programming languages. We will use it as a foundation for sequential computation. The λ calculus is Turing-complete, that is, any computable function can be expressed and evaluated using the calculus. The λ calculus is useful to study programming language concepts because of its high level of abstraction. In the following sections, we will motivate the λ calculus and introduce its syntax and semantics (Section ,) present the notion of scope of variables (Section ,) the importance of the order.
