Programming Languages (CS 329) Homework 2 Computer Science and Engineering Out: 2000-09-09 Indian Institute of Technology Bombay Due: 2000-09-25

1. Implement a λ-macro called DEC which decrements positive Church numerals without using recursion, Y, pairs, or any obvious syntactic equivalents.

2. In class we described a variant of the Y -combinator which works for normal order reduction. Design an alternative form which will work with applicative order evaluation. Demonstrate its use to compute

(a) factorial

(b) length of a list.

3. Consider the code

    (let rx   = (new 0)
         swap = (lambda (r1 r2)
                    (let t = (read r1)
                        (r1 := (read r2))
                        (r2 := t) ) )
        (letarray a[2]
            (a[0] := 1)
            (a[1] := 0)
            (call swap rx a[(read rx)])
            a ) )

where the final expression a prints out all the elements of array a in order.

Illustrate how the code is executed and what result is produced by a FL! interpreter that uses

(a) pass-by-value

(b) pass-by-name.

Note: If a is an array and i evaluates to an array index, then a[i] evaluates to a Location.