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?