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.

Abstractions and Applications

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.

Exercise

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

Answers to the quiz