Programming Language Principles

Homework for Week 03.


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

     (a) m ge n -> m | p -> m | n
     (b) m or n -> p -> m | n | n
     (c) m aug n , p , 5
     (d) m , n , p aug 5
     (e) let n (m) = m / 2 + 1 in n (m) where p = 6
     (f) item (e) above, with all the parentheses removed
     (g) let t = m and n = 2 * m where m = 1 in t ls (n ls 1)
     (h) let t = c in a + b ** c / 2 where (z = 4 and y = 3 * c)
     (i) item (h) above with the parentheses removed.

2. It is possible to write programs in a purely functional subset of an imperative language
such as C or Java, but certain limitations of the language quickly become apparent.
What features would need to be added to your favorite imperative language to
make it genuinely useful as a functional language? (Hint: what does RPAL/Scheme have
that C/Java lacks?)

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-d))) in ((e & f) -> (g -> x * (x**2)|y)

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

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

4. Some authors characterize functional programming as one form of declarative
programming. Others characterize functional programming as a separate
computational model, co-equal with imperative and declarative programming.
Which characterization do you prefer? Why?

5. Explain the algorithm and behavior of the following RPAL program:


let T(list1,list2)= S(list1, 1, list2, 1, nil)
where
(rec S(list1, index1, list2, index2, list) =
  (index1 le (Order list1)) & (index2 le (Order list2)) -> 
  		((list1 index1) le (list2 index2) -> 
      					(S(list1, index1+1, list2, index2, list aug (list1 index1)))
    						|(S(list1, index1, list2, index2+1, list aug (list2 index2)))   
  		 ) 
  		 | (index1 le (Order list1)) -> ( S(list1, index1+1, list2, index2, list aug (list1 index1))) 
  				  |(index2 le (Order list2)) -> ( S(list1, index1, list2, index2+1, list aug (list2 index2))) 
 								| list
)
in
let list1 = (1,3,4,7)
in
let list2 = (2,4,6,7,8)
in Print(T(list1, list2)) 

Make an honest attempt at figuring it out THEN ask the RPAL interpreter.