Questions: Partial Evaluation and Program Specialization

Question 1

A partial evaluator is given an interpreter for a small language and a specific program written in that language. The program text is treated as a static (known) input. What does the output of the partial evaluator represent?

• A. An optimized version of the interpreter with dead code eliminated
• B. A compiled version of the specific program — the interpreter's dispatch logic has been specialized away
• C. A new interpreter that runs the same program faster by caching results
• D. A proof that the interpreter correctly implements the language semantics

Answer: (B)

This is the first Futamura projection: partially evaluating an interpreter with respect to a specific program produces a compiled version of that program. The interpreter's parsing overhead, dispatch tables, and runtime branching — all of which are driven by the program text, a static input — are eliminated during specialization. What remains is only the sequence of operations the specific program actually performs, with no interpreter overhead. This shows that partial evaluation is powerful enough to derive compilers from interpreters automatically, without writing a compiler by hand.

Question 2

A partial evaluator is applied to a generic image-processing function with a static kernel size of 3×3. Instead of a compact specialized function, the output is thousands of lines of unrolled code. What phenomenon explains this?

• A. The partial evaluator made a logic error and must be rerun
• B. Code explosion — aggressive unfolding of a small static input produced an oversized residual program
• C. The function contained dynamic inputs that were incorrectly treated as static
• D. Binding-time analysis failed to classify any variables, so all code was duplicated

Answer: (B)

Code explosion occurs when partial evaluation aggressively unfolds loops and function calls driven by static inputs, producing a residual program much larger than the original. Even a small kernel size can cause substantial unrolling if the specialization recursively inlines multiple levels of function calls. This is why binding-time analysis is essential: it identifies which computations are static and limits specialization to avoid producing unmanageably large code. Without this analysis, partial evaluation can make programs larger and slower.

Question 3

Partial evaluation generalizes constant folding and dead code elimination by propagating known values through the entire program structure, including across function call boundaries.

• T. True
• F. False

Answer: True

Constant folding replaces expressions like '3 + 4' with '7' locally. Partial evaluation extends this by following known values into function bodies, unrolling loops whose bounds are statically known, resolving conditionals whose conditions are static, and inlining calls where the arguments are known. This is a global, whole-program transformation, not a local peephole optimization. The result — the residual program — contains only computations that genuinely depend on the unknown inputs.

Question 4

Partial evaluation typically produces a smaller, faster program than the original, making it a universally applicable optimization.

• T. True
• F. False

Answer: False

Partial evaluation can cause code explosion — producing residual programs much larger than the original. If a generic function is specialized for multiple different static inputs, the result is many large specialized copies, potentially worse in code size and instruction-cache performance than the generic original. This is why practical partial evaluators use binding-time analysis to limit specialization, and why partial evaluation is most valuable in specific scenarios (interpreter specialization, tight inner loops with known parameters) rather than as a blanket optimization.

Question 5

Explain what binding-time analysis does in partial evaluation and why it is necessary.

Model answer: Binding-time analysis is a preprocessing phase that classifies every variable and expression in the program as either static (its value is known at specialization time) or dynamic (its value is only known at runtime). The partial evaluator then specializes only the static portions, leaving dynamic computations in the residual program. Without this analysis, the evaluator might attempt to specialize dynamic computations, causing infinite loops or code explosion.

Without binding-time analysis, partial evaluation lacks a stopping criterion. It might try to evaluate a dynamic expression by unfolding it indefinitely, looping forever, or might aggressively inline every function call, producing enormous residual code. The static/dynamic classification is a conservative approximation: anything that might be dynamic is marked dynamic. The analysis ensures specialization terminates and produces a residual program of manageable size. It also guides the programmer in annotating which inputs should be considered static, enabling targeted specialization.