- 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

This topic: Main > CS255Assign2

Topic revision: r1 - 2008-04-14 - XiaomingGu

Copyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding URCS? Send feedback

Ideas, requests, problems regarding URCS? Send feedback