Assignment 2
- Deadline: April 28. Please put your answer into Xiaoming's mailbox (tagged by X.GU) in CS department mailroom.
1. Draw the syntax tree for the following lambda expression.
For call-by-value and call-by-name semantics, give the complete
content of the environment at the time when sub-expressions
(x a) and
(+ a a) are evaluated. If an environment has
more than one binding, indicate the order in which they are
searched for a particular name. Give the result of the evaluation.
((lambda (a)
((lambda(x)
((lambda (a)
(x a))
(+ 2 1)))
(lambda(y) (+ a a))))
(+ 1 1))
2. Recursion construction using lambda calculus (455 only)
By recursion we mean a function is defined in terms of itself.
Unfortunately lambda calculus does not allow this. However, a function
can call some special function and then regenerate itself. By
this means, we can achieve recursion using lambda calculus.
An instance of this powerful function is defined as
Y := (lambda (y)
((lambda (x) (y x x))
(lambda (x) (y x x))))
It's easy to verify that for any function
F,
YF = F(YF).
Now Suppose we want to define a recursive function, something like
F(n) = 1, if n == 0; else n*F(n-1)
Since we can't use
F in defining
F, we use
f instead as
a place-holder argument for the function to be passed to itself.
Therefore the lambda calculus representation of the function is
F := (lambda (f n)
(if (zero n)
1
(* n (f (- n 1)))))
Apply
Y to
F, then we get
(YF)n = F(YF)n = F(F(YF))n = ...
By expanding
YF to
F(YF) level by level, the function gets evaluated
in a recursive way.
Now you need to define a recursive function that counts the number
of elements from a list. You may use
if conditional test as following
syntax
(if <test-expr> <true-expr> <false-expr>)
which means if TEST-EXPR is evaluated true then evaluate TRUE-EXPR,
o/w evaluate FALSE-EXPR. You may also use
empty as a predicate
testing whether a list is empty or not, and
rest returning the list
with the first element popped off.
To answer this question, you need to put down your
F function,
then show how
(YF)(list) expands.
--
XiaomingGu - 14 Apr 2008