SYNTAX

The syntax of the lambda calculus is incredibly simple, because there are only three types of expressions:

	TYPE		syntax
	
	variable	string (e.g. "x", "y")
	
	application	(E E')  (where E and E' are both
				 lambda expressions)

	abstraction     \x.E    (where x is a variable
				 and E a lambda expression)

or using BNF:


	LAMBEXPR :: = VARIABLE 
                       | (LAMBEXPR LAMBEXPR)
		       | ("\" VARIABLE "." LAMBEXPR)

Note that the two pieces of concrete syntax (the period and lambda
symbols) have been explicitly quoted (in the BNF).

Which of the following are legal lambda expressions:

1. x

Yes No

2. \x.

Yes No

3. \x.yx

Yes No

4. \x.\y.xyxx

Yes No

BACK
NEXT