Partial Evaluation and Program Specialization. (Due at class time next Wednesday. Solution will be handed out then.)

An evaluator eval for an arithmetic expression e is given below, where vars is a list of variables and vals is a list of their corresponding values. If we know that vars are static, we would like get a specialized evaluator with respect to this fact.

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

a. Do binding-time analysis and show annotations. Specifically, overline each subcomputation that is static, and underline each subcomputation that is dynamic.

b. What is a best specialized version of eval if vars=[a,b,c]?

c. What is a best specialized version of eval if vars=[a,b,c] and e=Summation(Summation(a,3),b)?

d. Rewrite the above evaluator so that it takes, instead of vars and vals, a single list env of pairs of variables and their corresponding values.

e. What are subcomputations in the new program that are static, assuming binding-time analysis does not handle partially static structures?

Bonus. For real-world application of partial evaluation, people do not want to rewrite the program to be specialized, so they hand-code their partial evaluators to treat environment specially. Can we obtain the given program from the new program automatically?