Slide 12.2: Concepts and examples
Slide 12.4: Syntax of the lambda calculus (cont.)
Home

Syntax of the Lambda Calculus

The lambda calculus can be thought of as an idealized, minimalistic programming language. It is capable of expressing any algorithm, and it is this fact that makes the model of functional programming an important one. The lambda calculus derives its usefulness from having a sparse syntax and a simple semantics, and yet it retains sufficient power to represent all computable functions. Lambda expressions come in four varieties:
  1. Variables, which are usually taken to be any lowercase letters.

  2. Predefined constants, which act as values and operations are allowed in an impure or applied lambda calculus. For example, the constant nil represents the empty list.

  3. Function applications (combinations). For example, 
          ( lambda n . n * 2 + 3 ) 7
   ⇒ ( n * 2 + 3 ) [7/n]
   ⇒ 7 * 2 + 3
   ⇒ 14 + 3
   ⇒ 17
  4. Lambda abstractions (function definitions).
The simplicity of lambda calculus syntax is apparent from a BNF specification of its concrete syntax: 
  <expr> ::= <var>                       ; lowercase identifiers
           | <constant>                  ; predefined objects
           | ( <expr> <expr> )           ; combinations
           | ( &lambda <var> . <expr> )        ; abstractions
A function abstraction is an expression for a function. The identifier is the name of the parameter; it is said to be bound. An unbound identifier is free. The function itself has no name. Application is left associative, f x y = (f x) y. The constants include true, false, integers, some functions such as plus, minus, and a conditional function (if).

Demonstration