**Previous:** Part 1: Introduction,
**Next:** Part 3: Evaluation Strategies,
**Up:** Contents

- Gain a good understanding of the syntax and the semantics of the lambda calculus.
- Recognize the distinction between a function application and a function abstraction.

The essential features of the lambda calculus include two operations:

- Function definition or lambda abstraction.
- Function application or lambda application.

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:

<func> <arg>

You can see that it consists of a function name and its arguments.

- A simple example of a function application would be: f(x)
- The parentheses are not necessary.
- Spaces are also ignored; f(x) is equivalent to f x which is equivalent to f x and so on.

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.

- A function abstraction is an expression for a function.
- A simple example of a function abstraction would be: lambda x.y

Which of the following are valid function abstractions?

y x lambda g(x) lambda x.y lambda x.(y x)

- The first one is not a function abstraction. In fact, it is a function application. It does not have a lambda term and no period.
- The second one is also not valid; it is syntactically incorrect.
- The last two are function abstractions because they follow the form correctly.
- (Note: Take a look at the fourth one. It contains both an application and an abstraction)

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