SB CSE 675
Fall 2000
Program Transformation and Program Analysis
Annie Liu
Solution 4
Handout S4
Oct. 18, 2000

a. every subcomputation in what is overlined is static, and every subcomputation in the rest, assumed underlined, is dynamic.

  eval(e,vars,vals) = 
    case e of
      Constant(c): c
      Variable(v): lookup(v,vars,vals)
                               ____                 ____
      Sumation(e1,e2): eval(e1,vars,vals) + eval(e2,vars,vals)

  lookup(v,vars,vals) = 
    __ ___________ ____ _
    if empty(vars) then 0
    ____    __________
    else if head(vars)=v then head(vals)
         else lookup(v,tail(vars),tail(vals))


     case e of
       Constant(c): c
       Variable(v): lookup(v,vals)
       Summation(e1,e2): eval(e1,vals)+eval(e2,vals)
     if a=v then head(vals)
     else if b=v then head(tail(vals))
     else if c=v then head(tail(tail(vals)))
     else 0
or better, as some of you got:
     case e of
       Constant(c): c
       Variable(a): head(vals)
       Variable(b): head(tail(vals))
       Variable(c): head(tail(tail(vals)))
       Summation(e1,e2): eval(e1,vals)+eval(e2,vals)

c. head(vals) + 3 + head(tail(vals)


     case e of
       Constant(c): c
       Variable(v): lookup(v,env)
       Summation(e1,e2): eval(e1,env)+eval(e2,env)
     if empty(env) then 0
     else if fst(head(env))=v then snd(head(env))
     else lookup(v,tail(env))

e. none is static