tailieunhanh - Chapter 2λ CalculusThe λ (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 co

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. | Chapter 2 À Calculus The A 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 A calculus is Turing-complete that is any computable function can be expressed and evaluated using the calculus. The A calculus is useful to study programming language concepts because of its high level of abstraction. In the following sections we will motivate the A calculus and introduce its syntax and semantics Section present the notion of scope of variables Section the importance of the order of expression evaluation Section the notion of combinators Section currying Section -conversion eta- conversion Section the sequencing and recursion combinators Sections and and higher-order programming in the A calculus including an encoding of natural numbers and booleans Section . Syntax and Semantics We will briefly motivate the calculus and then introduce its syntax and semantics. The mathematical notation for defining a function is with a statement such as f x x2 f Z Z where Z is the set of all integers. The first Z represents the domain of the function or the set of values x can take. The second Z represents the range of the function or the set containing all possible values of f x . Suppose f x x2 and g x x 1. Traditional function composition is defined as f g f g x . With our functions f and g f g f g x f x 1 x2 2x 1. 19 20 CHAPTER 2. A CALCULUS Similarly g f g f x g x2 x2 1. Therefore function composition is not commutative. In the X calculus we can use a different notation to represent the same concepts. To define a function f x x2 we instead may write1 . Similarly for g x x 1 we write 1. To describe a function application such as f 2 4 we write 2 22 4. The syntax for A calculus expressions is e v - variable I - functional abstraction I e e - function application The semantics of the A calculus or the