Programming Language Principles

Homework 03. 
Assigned: Feb 08
Due: Feb 15, 11:59 pm


1.

Using the RPAL string-to-tree-transduction grammar, construct the
abstract syntax tree (if possible) for each of the following pro-
grams:

     (a) x or y -> x | z -> x | y
     (b) x eq y -> z -> x | y | x
     (c) nil aug x , Print , 5
     (d) x , y , z aug 3
     (e) let f (x) = x * 2 + 1 in f (z) where z = 6
     (f) item (e) above, with all the parentheses removed
     (g) let x = z and y = 2 * z where z = 3 in x ** y ** y
     (h) let i = x in (A i) * j where (x = 2 and j = 2**2)
     (i) item (h) above with the parenthesis removed.

2.

In problem 1, the structure  of  each  program  is  not  apparent
because  the  program  is  written  on  a single line as a linear
string.   Re-write  each  program  on  several  lines,  indenting
appropriately to reflect the structure.

3.

The following RPAL program is overly  parenthesized;  remove  all
superfluous  parentheses,  i.e.  minimize the parentheses without
changing the meaning of the program.

      (let (x =((a * b)/c)) in ((e or f) -> (g -> x ** (x**2)|y)

      | (f(x) where (( f(y) = (y*2)) and (x=(3 + (x * 2)))))))

Also, "beautify" the program by re-writing it  on  several  lines
with the appropriate indentation.

4.

Write, test, and debug an RPAL program that computes  the  "tuple
reverse"  function,  i.e.  Rev(3,'hello',(2,3),(fn x.x+1),true) =
(true,(fn x.x+1),(2,3),'hello',3).

5.

Explain the behavior of the following RPAL program:

let Sum N = S 0 N where rec S Cum N = N eq 0 -> Cum | S (N+Cum)
in Print (Sum 1 2 3 4 5 0)

Make an honest attempt at figuring it out BEFORE asking the  RPAL
interpreter.