Lecture overview -- Keyboard shortcut: 'u'  Previous page: Rewrite rules -- Keyboard shortcut: 'p'  Next page: The beta rewrite rule -- Keyboard shortcut: 'n'  Lecture notes - all slides and notes together  slide -- Keyboard shortcut: 't'  Help page about these notes  Alphabetic index  Course home  Lecture 4 - Page 10 : 27
Programming Paradigms
Evaluation Order and Infinite Lists
The alpha rewrite rule

An alpha conversion changes the names of formal parameters in lambda expression

Formal parameters of a lambda expression can be substituted by other names, which are not used as free names in the body

Legal conversion:

Expression

Converted Expression

(lambda (x y) (f x y))
(lambda (a b) (f a b))

An example of an alpha rewriting. The name a replaces x and the name y replaces y.

Illegal conversion:

Expression

Converted Expression

(lambda (x y) (f x y))
(lambda (a f) (f a f))

Examples of an illegal alpha conversion. f is a free name in the lambda expression. A free name is used, but not defined (bound) in the lambda expression. In case we rename one of the parameters to f, the free name will be bound, hereby causing an erroneous name binding.