Previous: Part 1: Introduction,
Next: Part 3: Evaluation Strategies,
Part 2: Syntax of the Lambda Calculus
The essential features of the lambda calculus include two operations:
But the syntax of a lambda expression can be either a variable, a constant, an application or an abstraction. The following is the context free grammar for the lambda calculus:
<expr> ::= <var> | <func> <arg> # This is an application. | lambda <var> . <expr> # This is an abstraction. <func> ::= <var> | (lambda <var> . <expr>) | <func> <arg> <arg> ::= <var> | (lambda <var> . <expr>) | (<func> <arg>) <var> ::= a| b| .... | Z
A variable or constant would simply be a letter such as x or y. Take a look at the form of a function application:
You can see that it consists of a function name and its arguments.
Which of the following are valid function applications?
f(x) x x x.y (f (x)
As you probably guessed, the first two are function applications. The second two however, are not. x.y, in fact, is a function abstraction, which we will go into more detail next. (f (x) is wrong because it is syntactically incorrect; the parentheses do not match up.
Now take a look at the form of a function abstraction:
lambda <var> . <expr>
It consists of a lambda followed by a variable, a period, and then an expression. Note that we usually use a backslash "\" to mean lambda.
Which of the following are valid function abstractions?
y x lambda g(x) lambda x.y lambda x.(y x)
State whether the following terms are applications or abstractions or if they are syntactically incorrect.
f x lambda (x.x) (g(y)) (lambda (x. y) lambda x.(x y) (lambda x. x) y
Answers to the quiz