FALL '98 FINAL EXAM SOLUTION 1. (a) Ambiguous. x+y+z and x*y+z * and - are left associative; + does not have a forced associativity. - has higher precedence than *. (b) Unambiguous, left associativities, * lower than +,- 2. (a) a := a+1 (b) No writes to a formal parameter in a procedure if the corresponding actual parameter can be read after returning from the procedure. No writes to non-local variables which can be aliases of formal parameters. More precise definitions are possible, but these catch the significant cases. 3. (a) ('a -> 'b) * ('c -> 'a) -> 'c -> 'b (b) 'a * 'b -> ('a -> 'c) * ('b -> 'd) -> 'c * 'd (c) ('a * 'b * 'c -> 'd) -> 'a -> 'b -> 'c -> 'd (d) ('a -> 'b -> 'c -> 'd) -> 'a * 'b * 'c -> 'd 4. (a) a(n) = Sum of the first n squares (1 + 2^2 + 3^2 + ... + n^2) (b) b(n) = 2^n (c) c(n,k) = tailfact(n,k) (i.e., fact(n) = c(n,1)) 5. (a) leaf(S), for any string S, is an IS-tree; if t1 and t2 are IS-trees and N is an integer then Node(t1,N,t2) is an IS-tree. (b) datatype IStree = leaf of string | node of IStree * int * IStree; (c). if P(leaf(S)) holds for all strings S and (forall t1,t2, P(t1) and P(t2) implies P(node(t1,N,t2)) for all N) then P(t) holds for all t 6. Under dynamic scoping, we look up non-local variables by following the dynamic links - this way we are sure to find the most recently allocated declaration of each variable. Lexical scoping is not relevant, so static links are not needed. An activation record needs everything except the static link. 7. (a) Fast access (no need to dereference a variable's address) (b) No copying of large data structures 8. (a) |typeof(Select(e0,x,e1,y,e2), Cxt) = let val t0 = typeof(e0,Cxt) in if not(t0=bad) then let val t1 = typeof(e1, (x,t0)::Cxt) val t2 = typeof(e2, (y,t0)::Cxt) in if t1=t2 then t1 else bad end end (b) infer(G, select(E0,X,E1,Y,E2), T) :- infer(G, E0, T0), not(T0=bad), infer([(X,T0)|G], E1, T), infer([(Y,T0)|G], E2, T). ( Note: there was a typo on this problem. The predicate infer was missing its third argument T.) 9. (a) p(xs,ys) if xs is a prefix of ys. (b) p(xs,ys) if length(xs) <= length(ys). (c) p(xs,ys) if xs = ys. (d) p(xs,ys) for any xs and ys. 10. (a) yes (b) yes (c) no response (or "Out of Stack" error) - infinite proof search (d) no (e) no response (or "Out of Stack" error) - infinite proof search