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

Topic revision: r2 - 2008-04-16 - XiaomingGu    Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback