Technical Report (TR96-04) Cover Page

Title:

Partial Evaluation of Call-by-value lambda-calculus with Side-effects

Authors:

Kenichi Asai, Hidehiko Masuhara, and Akinori Yonezawa

Key words and phrases:

partial evaluation, side-effects, pointer equality, preaction, online specialization

Abstract:

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 using preactions. 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:

English

Total number of pages:

30

Number of references:

24

Any other identifying information of this report:

Distribution statement:

First issue 35 copies.

Supplementary notes: