Slide 12.4: Syntax of the lambda calculus (cont.)

Syntax of the Lambda Calculus (Cont.)

Some examples of lambda expressions are

The lambda expression λx.x denotes the identity function in the sense that ((λx.x) E) = E for any lambda expression E.

The expression λn.(add n 1) denotes the successor function on the integers so that ((λn.(add n 1)) 5) = 6.

The abstraction (λf.(λx.(f (f x)))) describes a function with two arguments, a function and a value, that applies the function to the value twice. If sqr is the (predefined) integer function that squares its argument, then
```
     ( ( ( λf . ( λx . ( f ( f x ) ) ) ) sqr ) 3 )
   = ( ( λx . ( sqr ( sqr x ) ) ) 3 )
   = ( sqr ( sqr 3 ) )
   = ( sqr 9 )
   = 81
```
Here f is replaced by sqr and then x by 3.

These examples show that the number of parentheses in lambda expressions can become quite large. The following notational conventions allow abbreviations that reduce the number of parentheses:

Uppercase letters and identifiers beginning with capital letters will be used as metavariables ranging over lambda expressions.

Function application associates to the left.
```
     E₁ E₂ E₃  means  ( ( E₁ E₂ ) E₃ )
```
The scope of “λ<variable>“ in an abstraction extends as far to the right as possible.
```
   λx.E₁ E₂ E₃ means (λx.(E₁ E₂ E₃)) and not ((λx.E₁ E₂) E₃)
```