A partial evaluator, and its use for compiling iterative statements in LISP

ABSTRACT

A partial evaluation program for LISP is described, and an application where it has been used. The partial evaluator performs a number of other, related operations such as opening of functions and certain optimizations on programs. The application is based on the fact that we can generate from an interpreter and a partial evaluator the same object code as a corresponding compiler should do. The paper will first formally describe the relationship between an interpreter and a compiler through partial evaluation. The partial evaluator system is then briefly described and finally an experiment is shown where an interpreter for the iterative statement in INTERLISP is partially evaluated.

REFERENCES

• 1: Teitelman, W. INTERLISP Reference Manual, Xerox, Palo Alto Research Center, Calif (1975).
• 2: Futamura, Y. Partial evalution of computer programs: An approach to a compiler-compiler. J. Inst. Electronics and Communication Engineers (1971).
• 3: Deutch, P. The interactive program verifier. Ph.D. Thesis, Xerox Research Center, Palo Alto, CA (1973).
• 4: Ben Wegbreit, Goal-directed program transformation, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.153-170, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811549]
• 5: Ershov, A. P. On the essence of compilation, Computing Center, Siberian Division, USSR Academy of Sciences, Novosibirsk 630090, USSR, (1977).
• 6: Beckman L., Haraldson, A., Oskarson, O., Sandewall, E. A Partial Evaluator and its Use as a Programming Tool, Artificial Intelligence Journal 7, (1976) 319-357.
• 7: Haraldsson, A. A Program Manipulation System Based On Partial Evaluation, Ph.D. Thesis, Informatics Laboratory , Linkoeping University, Sweden (1977).