EXERCISE SET # 1 We STRONGLY recommend you do all these exercises, in preparation for the midterm. Solutions will be posted soon. Exercise 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) x aug y , z , 3 (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 x = z in x ** y ** y where z = 3 and y = 2 * z Exercise 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. Exercise 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. Exercise 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). Exercise 5. Complete the implementation of the Vector_Sum program in he Notes on RPAL, page 6, by adding all the suggested error checks. Exercise 6. Write, test and run a PAL program which implements function Innerproduct. Function Innerproduct multiplies two N-tuples of integers element by element and returns the sum of the products. Examples: Innerproduct ( (1,2,3), (4,5,6) ) = 1*4 + 2*5 + 3*6 = 32 Innerproduct ( nil, nil ) = 0 Be sure to check for bad data. Exercise 7. Write,test and run a PAL program, Pairs, that takes two strings of length N and produces an N-tuple whose i-th component contains a string composed of the i-th characters of the strings. In general, Pairs (s1s2...sN , t1t2...tN) = (s1t1, s2t2, ..., sNtN) Example: Pairs ('1357', '2468') = ('12', '34', '56', '78'). Check for bad data. Exercise 8. 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. Exercise 9. Give the linear lambda-expressions (NOT linear tree notation), with a MINIMUM number of parentheses, for the following trees: a) b) c) d) G G G G____ / \ / \ / \ / \ L 1 L 1 L L / \ / \ / \ / \ | \ L G x x x + z G x + / \ / \ / \ / \ / \ z + L w x 1 z 3 x 1 / \ / \ z 1 w + / \ w 1 e) f) G G / \ / \ L 1 G 1 / \ / \ x L G 2 / \ / \ z + L 3 / \ / \ x z x L / \ w L / \ z + / \ * x / \ w z Exercise 10. 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. Exercise 11. 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 Exercise 12. 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) on page 49 of the class notes. Exercise 13. 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) Evaluate the AE via a reduction sequence. Exercise 14. 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) Exercise 15. 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]}] Exercise 16. Map the following AE's into RPAL programs by using the transformational grammar in reverse. This is called "sugaring", the opposite of "de-sugaring". The intent is to eliminate all "lambdas". When stuck with a lambda expression that cannot be eliminated directly by applying a subtree transformation right-to-left, you may introduce the identity function. Example: Given fn x. x+1 all alone, or in a context where no other rule applies, we introduce the name f, by transforming fn x. x+1 to (fn f.f) (fn x.x+1), which can be transformed via the reverse of either "let" or "where", i.e. (fn f.f) (fn x.x+1) <= let f = fn x.x+1 in f <= let f x = x + 1 in f (fn f.f) (fn x.x+1) <= f where f = fn x.x+1 <= f where f x = x+1 This trick can be called a "beta-expansion". (a) (fn x.x+1) 3 (b) (fn x. fn f. fn z. x + f z) 3 (fn x. x+1) 1 (c) (fn x. fn y. x y x) [(fn x. fn y. x y x) (fn x. fn y. x y x)] (d) (fn x. x*3)