PARTIAL EVALUATION OF CALL-BY-VALUE LAMBDA-CALCULUS WITH SIDE-EFFECTS

We present a framework of an online partial evaluator for a call-by-va lue lambda-calculus with destructive updates of data structures. It pr operly and correctly specializes expressions that contain side-effects , while preserving pointer equality, which is an important property fo r programs using updates. Our partial evaluator uses a side-effect ana lysis to extract immutable data structures and then performs an online specialization using preactions. Once mutable and immutable data stru ctures are separated, partial evaluation is done in such a way that ac cesses to immutable ones are performed at specialization time, while a ccesses to mutable ones are residualized. For the correct residualizat ion of side-effecting operations, preactions are used to solve various issues, including code elimination, code duplication, and execution o rder preservation. The preaction mechanism also enables us to reduce e xpressions that were residualized when the conventional let-expression approach of Similix was used. The resulting partial evaluator is simp le enough to prove its correctness. Based on the framework, we have co nstructed a partial evaluator for Scheme, which is powerful enough to specialize fairly complicated programs with side-effects, such as an i nterpreter.