Programming Language Principles

Homework for Week 04.


1.

Identify the free variable occurrences in the following AE's:

      (a) fn x. x y
      (b) (fn y. fn x. x+y) x 1
      (c) (fn x. fn y. x y) x
      (d) (fn x. ((fn y. fn x. x+x) (x+1) (y+1)) +1) 1

  Reduce the above AE's.


2.

Reduce the following AE's:

      (a) (fn x.x+1) 3
      (b) (fn x.1+(fn y.y+1) 3) 2
      (c) (fn x.1+(fn x.x+1) 3) 2
      (d) (fn x. fn y. x+y) 3 4
      (e) (fn x. fn y. x+y) 3
      (f) (fn x.x) 3
      (g) (fn x. fn y. y x) 1
      (h) (fn x. fn y. x y) (fn z. z+2) 1
      (i) (fn x. fn y. x y) (fn y. y+2) 1
      (j) (fn x. fn y. x y) (fn x. fn y. x y) (fn z. z+1) 1
      (k) (fn x. fn y. x) 1 3
      (l) (fn x. fn y. y) 1 3
      (m) (fn x. x+2) ((fn y. y+1) 3)
      (n) (fn x. x+2) (fn y. y+1) 3
      (o) (fn x. x x) 1
      (p) (fn x. x x) (fn y. y 1)
      (q) (fn x. x x) (fn y. fn z. y z)       (fn z. z+1) 1


3.

Demonstrate your thorough understanding of function "subst" by
reducing the AE (fn x. fn y. x - y) y x  showing all but the most
trivial steps in detail.  Relate each step to the relevant axiom or 
part of "subst", i.e. 1), 1.1) 1.2), 2), 3) 3.1), 3.2), 3.2.1),
3.2.2) or 3.2.3) in the class notes.


4.

For the following RPAL program:

       let f x v = x aug v 
       and(        x, y = 1, 1 
                 within 
           p (r,s) = s eq 1 -> r+x | r+y 
          ) 
       in 
           f nil (p (1,2)) 

  a) Draw the AST.
  b) Transform the AST to the standardized tree.
  c) Transform the standardized tree to a lambda expression.  

5.

Reduce the following AE's to normal form:

      (a) (fn x. x+1) 2
      (b) (fn x. x+3) [(fn y. 2*y) 7]
      (c) {fn y. (fn x. y) [(fn x. x x) (fn y. y y)]} 1
      (d) (fn z. (fn x. x+1) [(fn x. x+z) 1])
      (e) (fn x. (fn x. (fn x. x+1) (x+2)) (x+3)) x
      (f) (fn y. [fn x. (fn y. y+x+a) (y+2)] [(fn t. fn s. t) y x]) 5
      (g) [fn f. fn x. f(f x)] [(fn g. fn y. g y) (fn x. x*2)] 3
      (h) (fn x. (fn y. y x 4) (fn x. fn y. x+y)) ((fn x. x*2) 3)


6.

Evaluate the following AE in programming language order.
Then estimate the number of beta-reductions necessary to evaluate 
the same AE in normal order.

          (fn x.x+x) [(fn y.y+y) {(fn z.z+z) [(fn v.v+v) 2]}]