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


Part 2: Syntax of the Lambda Calculus

Goals

Abstractions and Applications

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:

	<func> <arg>

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

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.

Exercise

Which of the following are valid function abstractions?

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

Quiz

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


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