SOLUTIONS TO EXERCISES 1. ------------------------- Exercise 1. Using the RPAL string-to-tree-transduction grammar construct the abstract syntax tree (if possible) for each of the following programs: (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 (a) -> (b) (_____->_____) (c) tau / | \ / | \ / | \ or x -> infix -> x aug z 3 / \ / | \ / | \ / | \ / \ x y z x y x eq y z x y x y (d) tau (e) (__let___) (f) same as (e) / | \ / \ x y aug fcn_form where / \ / | \ / \ z 3 f x + G = / \ / \ / \ * 1 f z z 6 / \ x 2 (g) (__let__) (h) No AST possible; / \ a definition following 'where' and ** cannot contain 'and' unless / \ / \ the definition is parenthesized. = = x ** / \ / \ / \ x z y where y y / \ * = / \ / \ 2 z z 3 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. (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,f) let f(x) = X*2+1 in f(z) where z=6 (g) let x = z and y = 2 * z where z = 3 in x** y**y (h) Not possible. 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. 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 ) ) 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). let Rev T = Prev (T,1) where rec Prev (T,N) = N gr (Order T) -> nil | (Prev (T,N+1) aug (T N)) in Print (Rev(1,'2',(3,2),true,(fn x.3),nil)) Exercise 5. Complete the implementation of the Vector_Sum program on page 47 of the class notes, by adding all the suggested error checks. let Vector_sum(A,B)= not(Istuple A) or not(Istuple B) -> 'Error' | (Order A ne Order B) -> 'Error' | Partial_sum (A,B, Order A) where rec Partial_sum(A,B,N)= N eq 0 -> nil |(Partial_sum(A,B,N-1) aug Sum where Sum= ((Isinteger(A N) & (Isinteger(B N))) -> A N + B N | 'Error') ) in Print(Vector_sum((1,2,3),(4,5,6))) 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: Innedrproduct ( (1,2,3), (4,5,6) ) = 1*4 + 2*5 + 3*6 = 32 Innerproduct ( nil, nil ) = 0 Be sure to check for bad data. // This solution uses curried functions, i.e., is meant // to be called as follows: Innerproduct (1,2,3) (4,5,6). let Innerproduct T1 T2 = not (Istuple T1 & Istuple T2) -> 'arguments must both be tuples' | Order T1 ne Order T2 -> 'arguments must have same length' | P 0 1 where rec P Sum N = // We assume components are integers. N gr Order T1 -> Sum | P (Sum + (T1 N) * (T2 N)) (N+1) in Print (Innerproduct (1,2,3) (4,5,6), Innerproduct 'abc' 123, Innerproduct nil nil, Innerproduct (nil aug 5) (nil aug 2), Innerproduct (5,6) (1,2,3) ) 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. let Pairs S1 S2 = not (Isstring S1 & Isstring S2) -> 'arguments must both be strings' | P nil S1 S2 where rec P Result S1 S2 = S1 eq '' & S2 eq '' -> Result | S1 eq '' or S2 eq '' -> 'strings must be of same length' | P (Result aug (Stem S1) @Conc (Stem S2)) (Stern S1) (Stern S2) in Print (Pairs '1357' '2468', Pairs '1357' '246', Pairs '135' '2468', '\n', Pairs '' '' , Pairs 'a' 'b' , Pairs 'abc' 13 ) 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. Function Sum takes an arbitrary number of arguments (one at a time) and adds them. The addition stops when the current argument is zero. 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 (a) (fn x.x) 1 (b) (fn x.x+1) 1 (c) (fn z.z 3) (fn x.x+1) (d) (fn z.z+1) ((fn w.w+1) w) (e) (fn x. fn z. x+z) 1 (f) (fn x. fn w. fn z. w*z+x) 3 2 1 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. (a) fn x. x y (already reduced) (b) (fn y. fn x. x+y) x 1 ( fn x'. x'+x) 1 1+x (c) (fn x. fn y. x y) x fn y. x y (d) (fn x. ((fn y. fn x. x+x) (x+1) (y+1)) +1) 1 (fn x. (( fn x. x+x) (y+1)) +1) 1 (fn x. (y+1+y+1) +1) 1 y+1+y+1+1 Exercise 11. Reduce the following AE's: 4. (a) (fn x.x+1) 3 3+1 (b) (fn x.1+(fn y.y+1) 3) 2 1+(fn y.y+1) 3 1+ 3+1 (c) (fn x.1+(fn x.x+1) 3) 2 1+(fn x.x+1) 3 1+ 3+1 (d) (fn x. fn y. x+y) 3 4 ( fn y. 3+y) 4 3+4 (e) (fn x. fn y. x+y) 3 fn y. 3+y (f) (fn x.x) 3 3 (g) (fn x. fn y. y x) 1 fn y. y 1 (h) (fn x. fn y. x y) (fn z. z+2) 1 ( fn y. (fn z.z+2) y ) 1 (fn z.z+2) 1 1+2 (i) (fn x. fn y. x y) (fn y. y+2) 1 ( fn y. (fn y.y+2) y ) 1 (fn y.y+2) 1 1+2 (j) (fn x. fn y. x y) (fn x. fn y. x y) (fn z. z+1) 1 ( fn y. (fn x. fn y. x y) y) (fn z. z+1) 1 ( (fn x. fn y. x y) (fn z. z+1)) 1 ( fn y. (fn z.z+1) y) 1 (fn z.z+1) 1 1+1 (k) (fn x. fn y. x) 1 3 ( fn y. 1) 3 1 (l) (fn x. fn y. y) 1 3 ( fn y. y) 3 3 (m) (fn x. x+2) ((fn y. y+1) 3) ((fn y.y+1) 3) + 2 3+1 + 2 (n) (fn x. x+2) (fn y. y+1) 3 ( (fn y.y+1) + 2 ) 3 (o) (fn x. x x) 1 1 1 (p) (fn x. x x) (fn y. y 1) (fn y. y 1) (fn y. y 1) (fn y. y 1) 1 1 1 (q) (fn x. x x) (fn y. fn z. y z) (fn z. z+1) 1 ( (fn y.fn z.y z) (fn y.fn z.y z) ) (fn z. z+1) 1 ( fn z. (fn y.fn z.y z) z ) (fn z. z+1) 1 ( (fn y.fn z.y z) (fn z.z+1) ) 1 ( fn z. (fn z.z+1) z ) 1 (fn z.z+1) 1 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. 5. In the following, even the most trivial steps are shown. (fn x. fn y. -xy) y x { [y/x] (fn y.-xy) } x by axiom beta. { fn y`. [y/x] ([y`/y] (-xy)) } x by case 3.2.3. { fn y`. [y/x] ([y`/y](-x) [y`/y]y) } x by case 2. { fn y`. [y/x] (([y`/y](-) [y`/y]x) [y`/y]y) } x by case 2. { fn y`. [y/x] (( (-) [y`/y]x) [y`/y]y) } x by case 1.2. { fn y`. [y/x] (( (-) x) [y`/y]y) } x by case 1.2. { fn y`. [y/x] (( (-) x) y`) } x by case 1.1. { fn y`. [y/x] (-x) ([y/x] y`) } x by case 2. { fn y`. ([y/x] (-) [y/x] x) ([y/x] y`) } x by case 2. { fn y`. ( - [y/x] x) ([y/x] y`) } x by case 1.2. { fn y`. ( - y) ([y/x] y`) } x by case 1.1. { fn y`. ( - y) y` } x by case 1.2. [x/y`] ((-y)y`) by axiom beta. ([x/y`] (-y)) ([x/y`]y`) by case 2. ([x/y`] (-) ([x/y`]y)) ([x/y`]y`) by case 2. - ([x/y`]y)) ([x/y`]y`) by case 1.2. - y ([x/y`]y`) by case 1.2. - y x by case 1.1. 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. let ____/ \____________________ / \ and G _______/ \_______ / \___ / \ G \ fcn_form within / \ G / | | \ / \________ f nil / \ f x v aug = \ p tau / \ / \___ fcn_form / \ x v , \ / | \_____ 1 2 / \ tau p , \ x y / \ / \ -> 1 1 r s ___/|\___ / | \ eq + + / \ / \ r x r y b) Transform the AST to the standardized tree. G _________/ \_________ / \ L tau / \ ________/ \_______ T G / \ __/ \ L G / G / \ / \___________ L / \ x L L \ / \ T 1 / \ / \ tau f G v G T G / \ __/ \ / \ / \_______ 1 1 / G G v L \ L / \ / \ / \ G / \ T 2 aug x x G / \ p G / \____ T 1 / \___ L G G \ / \ / \ / \ G y L T 2 f nil / \ / \ p tau T G / \ / \_______ 1 2 L \ / \ G r G / \ / \____ T 1 L \ / \ G s G / \ / \ T 2 G nil / \__________ G \ / \___ L G \ / \ / \ L () G Cond G / \ / \ / \ () G G y G 1 / \ / \ / \ G x + r eq s / \ + r c) Evaluate the AE via a reduction sequence. Applicative expression: (fn T. (fn f. (fn p. (f nil) (p (1,2)) ) (T 2) ) (T 1) ) ( (fn x. fn y. x aug y) , (fn T. (fn x. (fn y. (fn T. ( fn r. ( fn s. Cond (s eq 1) (fn ().r+x) (fn ().r+y) nil) (T 2) ) (T 1) ) ) (T 2) ) (T 1) ) (1,1) ) => (fn T. (fn f. (fn p. (f nil) (p (1,2)) ) (T 2) ) (T 1) ) ( (fn x. fn y. x aug y) , (fn x. (fn y. (fn T. ( fn r. ( fn s. Cond (s eq 1) (fn ().r+x) (fn ().r+y) nil) (T 2) ) (T 1) ) ) ((1,1) 2) ) ((1,1) 1) ) => (fn T. (fn f. (fn p. (f nil) (p (1,2)) ) (T 2) ) (T 1) ) ( (fn x. fn y. x aug y) , (fn x. (fn y. (fn T. ( fn r. ( fn s. Cond (s eq 1) (fn ().r+x) (fn ().r+y) nil) (T 2) ) (T 1) ) ) (1) ) (1) ) => (fn T. (fn f. (fn p. (f nil) (p (1,2)) ) (T 2) ) (T 1) ) ( (fn x. fn y. x aug y) , (fn y. (fn T. ( fn r. ( fn s. Cond (s eq 1) (fn ().r+1) (fn ().r+y) nil) (T 2) ) (T 1) ) ) (1) ) => (fn T. (fn f. (fn p. (f nil) (p (1,2)) ) (T 2) ) (T 1) ) ( (fn x. fn y. x aug y) , (fn T. ( fn r. ( fn s. Cond (s eq 1) (fn ().r+1) (fn ().r+1) nil) (T 2) ) (T 1) ) ) => (fn f. (fn p. (f nil) (p (1,2)) ) (( (fn x. fn y. x aug y) , (fn T. ( fn r. ( fn s. Cond (s eq 1) (fn ().r+1) (fn ().r+1) nil) (T 2) ) (T 1) ) ) (2)) ) (( (fn x. fn y. x aug y) , (fn T. ( fn r. ( fn s. Cond (s eq 1) (fn ().r+1) (fn ().r+1) nil) (T 2) ) (T 1) ) ) (1)) => (fn f. (fn p. (f nil) (p (1,2)) ) (fn T. ( fn r. ( fn s. Cond (s eq 1) (fn ().r+1) (fn ().r+1) nil) (T 2) ) (T 1) ) ) (fn x. fn y. x aug y) => (fn p. ((fn x. fn y. x aug y) nil) (p (1,2)) ) (fn T. ( fn r. ( fn s. Cond (s eq 1) (fn ().r+1) (fn ().r+1) nil) (T 2) ) (T 1) ) => (fn p. (fn y. nil aug y) (p (1,2)) ) (fn T. ( fn r. ( fn s. Cond (s eq 1) (fn ().r+1) (fn ().r+1) nil) (T 2) ) (T 1) ) => (fn y. nil aug y) ( (fn T. ( fn r. ( fn s. Cond (s eq 1) (fn ().r+1) (fn ().r+1) nil) (T 2) ) (T 1) ) (1,2) ) => (fn y. nil aug y) ( ( fn r. ( fn s. Cond (s eq 1) (fn ().r+1) (fn ().r+1) nil) ((1,2) 2) ) ((1,2) 1) ) => (fn y. nil aug y) ( ( fn r. ( fn s. Cond (s eq 1) (fn ().r+1) (fn ().r+1) nil) ((1,2) 2) ) (1) ) => (fn y. nil aug y) ( ( fn r. ( fn s. Cond (s eq 1) (fn ().r+1) (fn ().r+1) nil) (2) ) (1) ) => (fn y. nil aug y) ( ( fn s. Cond (s eq 1) (fn ().1+1) (fn ().1+1) nil) (2) ) => (fn y. nil aug y) ( Cond (2 eq 1) (fn ().1+1) (fn ().1+1) nil) => (fn y. nil aug y) ( Cond false (fn ().1+1) (fn ().1+1) nil) => (fn y. nil aug y) ( (fn x. fn y. y) (fn ().1+1) (fn ().1+1) nil) => (fn y. nil aug y) ( (fn x. fn y. y) (fn ().1+1) (fn ().1+1) nil) => (fn y. nil aug y) ( fn y. y) (fn ().1+1) nil) => (fn y. nil aug y) (fn ().1+1) nil) => (fn y. nil aug y) (1+1) => (fn y. nil aug y) (2) => nil aug 2 WHEW !!!!! Exercise 14. Reduce the following AE's to normal form: (a) (fn x. x+1) 2 2+1 (b) (fn x. x+3) [(fn y. 2*y) 7] (fn x. x+3) [ 2*7 ] 2*7+3 (c) {fn y. (fn x. y) [(fn x. x x) (fn y. y y)]} 1 (fn x. 1) [(fn x. x x) (fn y. y y)] 1 (d) (fn z. (fn x. x+1) [(fn x. x+z) 1]) fn z. (fn x. x+1) [ 1+z ] fn z. 1+z+1 (e) (fn x. (fn x. (fn x. x+1) (x+2)) (x+3)) x (fn x. (fn x. x+2+1 ) (x+3)) x (fn x. x+3+2+1 ) x x+3+2+1 (f) (fn y. [fn x. (fn y. y+x+a) (y+2)] [(fn t. fn s. t) y x]) 5 (fn y. [fn x. y+2+x+a ] [ (fn s. y) x]) 5 (fn y. [fn x. y+2+x+a ] [ y ]) 5 [fn x. 5+2+x+a ] 5 5+2+5+a (g) [fn f. fn x. f(f x)] [(fn g. fn y. g y) (fn x. x*2)] 3 [fn f. fn x. f(f x)] [ fn y. (fn x.x*2) y ] 3 [fn f. fn x. f(f x)] [ fn y. y*2 ] 3 [ fn x. (fn y.y*2) ((fn y.y*2) x) ] 3 (fn y.y*2) ((fn y.y*2) 3) (fn y.y*2) ( 3*2 ) 3*2*2 (h) (fn x. (fn y. y x 4) (fn x. fn y. x+y)) ((fn x. x*2) 3) (fn x. (fn x. fn y. x+y) x 4 ) ( 3*2 ) (fn x. fn y. x+y) 3*2 4 (fn y. 3*2+y) 4 3*2+4 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]}] => (fn x.x+x) [(fn y.y+y) {(fn z.z+z) [ 2+2 ]}] => (fn x.x+x) [(fn y.y+y) { 2+2+2+2 }] => (fn x.x+x) [2+2+2+2 +2+2+2+2 ] => 2+2+2+2 +2+2+2+2 +2+2+2+2 +2+2+2+2 (==delta==> 32) In programming language order, 4 beta reductions are necessary. In normal order, # beta reductions[(fn x.x+x) E] = 1+2*(# beta reductions[E]) (fn x.x+x) [(fn y.y+y) {(fn z.z+z) [(fn v.v+v) 2]}] Thus: 1+2* ( 1+2* ( 1+2* ( 1+2* 0))) = 15 beta-reductions in normal order. 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". 9. (a) (fn x.x+1) 3 <= let x = 3 in x+1 (b) (fn x. fn f. fn z. x + f z) 3 (fn x. x+1) 1 <= (let x = 3 in fn f. fn z. x + f z) (fn x. x+1) 1 <= (let x = 3 in (let h = fn f. fn z. x+f z in h)) (let h = fn x. x+1 in h) 1 <= (let x = 3 in let h f z = x + f z in h) (let h x = x+1 in h) 1 ALTERNATE SOLUTION: <= (let h = fn x. fn f. fn z. x + f z in h) 3 (fn x. x+1) 1 <= (let h x f z = x + f z) 3 (let h = fn x. x+1 in h) 1 <= (let h x f z = x + f z) 3 (let h x = x+1 in h) 1 (c) (fn x. fn y. x y x) [(fn x. fn y. x y x) (fn x. fn y. x y x)] <= let x = (fn x. fn y. x y x) (fn x. fn y. x y x) in fn y. x y x <= let x = (let x = fn x. fn y. x y x in fn y. x y x) in (let h = fn y. x y x in h) <= let x = (let x x y = x y x in (let h = fn y. x y x in h)) in (let h y = x y x in h) <= let x = (let x x y = x y x in let h y = x y x in h) in (let h y = x y x in h) (d) (fn x. x*3) <= let h = fn x. x*3 in h <= let h x = x*3 in h