Partial evaluation and separate compilation

ABSTRACT

Hitherto all partial evaluators have processed a complete program to produce a complete residual program. We are interested in treating programs as collections of modules which can be processed independently: 'separate partial evaluation', so to speak. In this paper we still assume that the original program is processed in its entirety, but we show how to specialise it to the static data bit-by-bit, generating a different module for each bit. When the program to be specialised is an interpreter, this corresponds to specialising it to one module of its object language at a time: each module of the object language gives rise to one module of the residual program.

REFERENCES

• AJ89: L. Augustsson , T. Johnsson, The Chalmers lazy ML-compiler, The Computer Journal, v.32 n.2, p.127-141, April 1989 [doi>10.1093/comjnl/32.2.127]
• DHH96: Dirk Dussart, Rogardt Heldal, and John Hughes. Module-Sensitive Program Specialization. submitted for publication, November 1996.
• Fut71: Y. Futamura. Partial evaluation of computation process- an approach to a compiler-compiler. In Systems, Computers, Controls, volume 2, pages 721-728, 1971.
• GJ95: Robert Glück , Jesper Jørgensen, Efficient Multi-level Generating Extensions for Program Specialization, Proceedings of the 7th International Symposium on Programming Languages: Implementations, Logics and Programs, p.259-278, September 20-22, 1995
• Glü91: Robert Glück, Towards multiple self-application, ACM SIGPLAN Notices, v.26 n.9, p.309-320, Sept. 1991
• HL91: C. K. Hoist and J. Launchbury. Handwriting cogen to avoid problems with static typing, in Draft Proceedings, Fourth Annual Glasgow Workshop on Functional Programming, Skye, Scotland, pages 210-218. Glasgow University, 1991.
• Hud92: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• Hug96: John Hughes, Type Specialisation for the lambda-Calculus; or, A New Paradigm for Partial Evaluation Based on Type Inference, Selected Papers from the Internaltional Seminar on Partial Evaluation, p.183-215, February 12-16, 1996
• JGS93: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• JSS89: Neil D. Jones, Peter Sestoft, and Haxald Scndergaard. Mix: A self-applicable partial evaluator for experiments in compiler generation. Lisp and Symbolic Computation, 2(1):9-50, 1989. DIKU Report 91/12.
• Lau91a: John Launchbury, A strongly-typed self-applicable partial evaluator, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.145-164, June 1991, Cambridge, Massachusetts, United States
• Lau91b: J. Launchbury. Projection Factorisations in Partial Evaluation (PhD thesis), volume 1 of Distinguished Dissertations in Computer Science. Cambridge University Press, 1991.
• Mog93: Torben Æ Mogensen, Constructor specialization, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.22-32, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154633]
• Mog96: Torben Æ. Mogensen, Evolution of Partial Evaluators: Removing Inherited Limits, Selected Papers from the Internaltional Seminar on Partial Evaluation, p.303-321, February 12-16, 1996
• Rom90: S. A. Romanenko, Arity raiser and use in program specialization, Proceedings of the third European symposium on programming on ESOP '90, p.341-360, May 1990, Copenhagen, Denmark
• SH91: R. S. Sundaresh , Paul Hudak, A theory of incremental computation and its application, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-13, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99587]
• Tur86: Valentin F. Turchin, The concept of a supercompiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.292-325, July 1986 [doi>10.1145/5956.5957]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Interpreters

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

General Terms:
Design, Languages, Performance, Theory

Keywords:
modules, partial evaluation, separate compilation