New Generation Computing, 20(2002)75-99
Ohmsha, Ltd. and Springer-Verlag

Program Transformation System Based on Generalized Partial Computation

Yoshihiko FUTAMURA and Zenjiro KONISHI
Waseda University
3-4-1 Okubo, Shinjuku, Tokyo 169-8555 Japan
{futamura,konishi}@futamura.info.waseda.ac.jp

Robert GLÜCK
Waseda University
3-4-1 Okubo, Shinjuku, Tokyo 169-8555 Japan
PRESTO, JST
glueck@acm.org

Received 1 June 2001
Revised manuscript received 30 August 2001

Abstract

Generalized partial Computation (GPC) is a program transformation method utilizing partial information about input data, abstract data types of auxiliary functions and the logical structure of a source program. GPC uses both an inference engine such as a theorem prover and a classical partial evaluator to optimize programs. Therefore, GPC is more powerful than classical particle evaluators but harder to implement and control. We have implemented an experimental GPC system called WSDFU (Waseda Simplify-Distribute-Fold-Unfold). This paper demonstrates the power of the program transformation system as well as its theorem prover and discusses some future works.

Keywords: Partial Evaluation, Program Transformation, Theorem Proving, Program Optimization, Recursion Removal, Algebraic Manipulation.

[Back]