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.

SOLUTION 1:


     (a)  ->          
        /  | \        
       ge  m  ->      
      /  \   / | \    
      m   n p  m  n


     (b)      (_____->_____)  
              /      |     \    
            or       ->      n   
           /  \    / | \        
          m    n  p  m  n     


     (c)     tau
            / | \
         aug  p  5
         / \
        m   n


     (d) tau        
        / | \       
       m  n aug     
            / \     

           p   5

     (e)        (__let___)      
                /          \
         fcn_form        where
         /  |  \         /   \
        n   m   +     gamma   =
               / \     / \   / \
             "/"  1   n   m p   6
             / \  
            m   2  

     (f) same as (e)

     (g)        (__let__)            
                /        \          
            and           ls         
          /     \        /  \       
         =       =      t   ls
        / \    /   \       /  \
       t   m  n  where    n    1
                 /   \
                *     =
               / \   / \
              2   m m   1

     (h)        (__let__)           
               /          \
              =           where
             / \        /       \   
            t   c      +         \       
                      / \         and   
                     a  "/"      /   \
                        /  \    =     =
                       **   2  / \   / \
                      / \     z   4 y   *
                     b  c              / \
                                      3   c
     (i) No AST possible; A definition following 'where'cannot contain 'and' unless the definition is parenthesized.


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 have
that C/Java lacks?)

SOLUTION 2:
Here are some possibilities:
(a) Functions as first-class objects: functional constants, function types, functions as return
values, syntax to call a function returned from another function
(b) The ability to use statements as expressions, for example to embed an if statement (expression)
in a parameter list
(c) Polymorphic functions
(d) On-the-fly creation of functions: something similar to lambda
(e) Literal (“manifest”) constants of arbitrary types—constant trees
(f) Garbage collection

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.

SOLUTION 3:

     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
                           )
                    )

4. Functional programming is sometimes characterized 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?

SOLUTION 4:
The argument for categorizing functional programming as declarative centers on
the lack of side effects and the relatively unconstrained order of evaluation (normal v. applicative).
The argument for a separate category emphasizes the algorithmic character of functional
programs, despite their lack of side effects, and the contrast between the functional and logic
programming “mindsets.”

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.

SOLUTION 5:
Function "merge" takes two lists of numbers in increasing order and merges
them into one list of numbers in incresasing order. For example,
 merge((1,3,4,7),(2,4,6,7,8)) = (1,2,3,4,4,6,7,7,8).