Description
1. Derive the list of free variables in the following λ term. Outline your
derivation according to the rules given in the notes.
(λx.y(xx))(λy.x(yy))(λz.y)
2. Evaluate the following λ expressions using α and $ β reduction rules
to obtain the normal form. Please stop the reduction when you #rst
obtain the normal form.
(a) (λab · ba)ab
(b) (λx · xx)(λa · a) .
(c) (λx · xx)(λx · xx) .
3. Construct a λ term that does not have a normal form – i.e. construct
a term which can always be β reduced further. Explain why this term
has this property in one or two sentences.
4. Based on the Church representation of Boolean values given in the
notes, de#ne the λ term which computes the “or” of Boolean values –
i.e. a term which takes two arguments, and evaluates to the Boolean
representation of True if either of them is True, and to False if both of
them are False.
5. What is the set of #xed points of the λ term (λx · x) ?
16. Consider an enriched λ calculus which has natural numbers available,
has a normal if-then-else construct, and has the operators + , − and
== . Using the Y-combinator, de#ne the following recursive function
to sum the #rst n numbers.
sum = λn· if n==0 then 0 else n+(sum n-1).
2
