SB CSE 675
Fall 2000
Program Transformation and Program Analysis
Annie Liu
Exercises 4
Handout E4
Oct. 6, 2000
Due Oct. 11

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?