# Assignment 1

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