Technical Report (TR96-04) Cover Page
Department of Information Science,
Faculty of Science, University of Tokyo
Partial Evaluation of Call-by-value lambda-calculus with Side-effects
Kenichi Asai, Hidehiko Masuhara, and Akinori Yonezawa
- Key words and phrases:
partial evaluation, side-effects, pointer equality, preaction,
We present a framework of an online partial evaluator for a call-by-value
lambda-calculus with destructive updates of data structures.
To our knowledge, this is the first partial evaluator that can deal
with full side-effects as well as pointer equality in higher-order languages.
Our partial evaluator uses a side-effect analysis for handling
assignment operations and then performs an online specialization
By separating mutable data structures
from immutable ones using the side-effect
analysis, the most accesses to structured data (e.g., cons cells)
are statically reduced at partial evaluation time.
For the correct residualization of side-effecting operations,
preactions are used to solve various issues, such as code elimination,
code duplication, and the order of execution.
The resulting partial evaluator is simple enough to prove its correctness.
Based on the framework, we extend it to
a partial evaluator for almost full Scheme
and demonstrate that it is powerful enough to specialize an
interpreter written using side-effects.
- Report date:
November 6, 1996
- Written language:
- Total number of pages:
- Number of references:
- Any other identifying information of this report:
- Distribution statement:
First issue 35 copies.
- Supplementary notes: