Continuation-based partial evaluation

ABSTRACT

Binding-time improvements aim at making partial evaluation (a.k.a. program specialization) yield a better result. They have been achieved so far mostly by hand-transforming the source program. We observe that as they are better understood, these hand-transformations are progressively integrated into partial evaluators, thereby alleviating the need for source-level binding-time improvements.Control-based binding-time improvements, for example, follow this pattern: they have evolved from ad-hoc source-level rewrites to a systematic source-level transformation into continuation-passing style (CPS). Recently, Bondorf has explicitly integrated the CPS transformation into the specializer, thus partly alleviating the need for source-level CPS transformation. This CPS integration is remarkably effective but very complex and goes beyond a simple CPS transformation. We show that it can be achieved directly by using the control operators shift and reset, which provide access to the current continuation as a composable procedure.We automate, reproduce, and extend Bondorf's results, and describe how this approach scales up to hand-writing partial-evaluation compilers. The first author has used this method to bootstrap the new release of Consel's partial evaluator Schism. The control operators not only allow the partial evaluator to remain in direct style, but also can speed up partial evaluation significantly.

REFERENCES

• 1: Lennart Beckman, Anders Haraldsson, Osten Oskarsson, and Erik Sandewall. A partial evaluator, and its use a~ a programming tool. Artificial Intelligence, 7(4)-319-s57, 19n.
• 2: Lars Birkedal and Morten Welinder. Partial evaluation of Standard ML. Master's thesis, DIKU, Computer Science Department, University of Copenhagen, August 1993.
• 3: Anders Bondorf, Improving binding times without explicit CPS-conversion, Proceedings of the 1992 ACM conference on LISP and functional programming, p.1-10, June 22-24, 1992, San Francisco, California, United States
• 4: William Clinger, editor. Proceedings of the 1992 A CM Conference on Lisp and Functional Programming, LISP Pointers, Vol. V, No. 1, San Francisco, California, June 1992. ACM Press.
• 5: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams, IV , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand , William Clinger , Jonathan Rees, Revised report on the algorithmic language scheme, ACM SIGPLAN Lisp Pointers, v.IV n.3, p.1-55, July, 1991 [doi>10.1145/382130.382133]
• 6: Will Clinger , Anne Hartheimer , Eric Ost, Implementation strategies for continuations, Proceedings of the 1988 ACM conference on LISP and functional programming, p.124-131, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62692]
• 7: Charles Consel, Polyvariant binding-time analysis for applicative languages, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.66-77, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154638]
• 8: Charles Consel, A tour of Schism: a partial evaluation system for higher-order applicative languages, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.145-154, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154645]
• 9: C. Consel , O. Danvy, From interpreting to compiling binding times, Proceedings of the third European symposium on programming on ESOP '90, p.88-105, May 1990, Copenhagen, Denmark
• 10: Charles Consel , Olivier Danvy, For a better support of static data flow, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.496-519, June 1991, Cambridge, Massachusetts, United States
• 11: Charles Consel , Olivier Danvy, Tutorial notes on partial evaluation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.493-501, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158707]
• 12: Charles Consel , Siau Cheng Khoo, Parameterized partial evaluation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.3, p.463-493, July 1993 [doi>10.1145/169683.174155]
• 13: Olivier Danvy , Andrzej Filinski, Abstracting control, Proceedings of the 1990 ACM conference on LISP and functional programming, p.151-160, June 27-29, 1990, Nice, France [doi>10.1145/91556.91622]
• 14: Olivier Danvy and Andrzej Filinski. Representing control, a study of the CPS transformation. Mathematical Structures in Computer Science, 2(4):361-391, December 1992.
• 15: Olivier Danvy , Julia L. Lawall, Back to direct style II: first-class continuations, Proceedings of the 1992 ACM conference on LISP and functional programming, p.299-310, June 22-24, 1992, San Francisco, California, United States
• 16: M. Felleisen, The theory and practice of first-class prompts, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.180-190, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73576]
• 17: Andrzej Filinski, Representing monads, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.446-457, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.178047]
• 18: Cormac Flanagan , Amr Sabry , Bruce F. Duba , Matthias Felleisen, The essence of compiling with continuations, ACM SIGPLAN Notices, v.28 n.6, p.237-247, June 1993
• 19: Daniel P. Friedman. Personal communication, e-mail [e-mail], September 1993.
• 20: R. Hieb , R. Kent Dybvig , Carl Bruggeman, Representing control in the presence of first-class continuations, ACM SIGPLAN Notices, v.25 n.6, p.66-77, Jun. 1990
• 21: Carsten Kehler Holst , Darsten Krogh Gomard, Partial evaluation is fuller laziness, ACM SIGPLAN Notices, v.26 n.9, p.223-233, Sept. 1991
• 22: Carsten K. Hoist and John Launchbury. Handwriting cogen to avoid problems with static typing. In Draft Proceedings, Fourth Annual Glasgow Workshop on Functional Programmzng, Skye, Scotland, pages 210-218. Glasgow University, 1991.
• 23: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 24: Neil D. Jones, Peter Sestoft, and Itarald S~ndergaard. MiX: A self-applicable partiM evalnator for experiments in compiler generation. LISP and Symbolic Computation, 2(1):9-50, 1989.
• 25: Lionello A. Lombardi and Bertram Raphael. Lisp as the language for an incremental computer. In Edmund C. Berkeley and Daniel G. Bobrow, editors, The Programming Language Lssp: Its Operation and Applications, pages 204-219, Cambridge, Massachusetts, 1964. The MIT Press.
• 26: Karoline Malmkjær, Towards efficient partial evaluation, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.33-43, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154634]
• 27: Karoline Malmkjaer, Nevin Heintze, and Olivier Danvy. ML partial evaluation using set-based analysis. Technical report CMU-CS-94-129, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, February 1994.
• 28: Chethan R. Murthy. Control operators, hierarchies, and pseudo-classicM type systems' A-translation at work. In Olivier Danvy and Carolyn L. Talcott, editors, Proceedings of the ACM SIGPLAN Workshop on Continuations, Technical report STAN-CS-92-1426, Stanford University, pages 49-72, San Francisco, California, June 1992.
• 29: Erik Steven Ruf, Topics in online partial evaluation, Stanford University, Stanford, CA, 1993
• 30: Amr Sabry , Matthias Felleisen, Reasoning about programs in continuation-passing style., ACM SIGPLAN Lisp Pointers, v.V n.1, p.288-298, Jan. 1992
• 31: David A. Schmidt, Detecting global variables in denotational specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.299-310, April 1985 [doi>10.1145/3318.3323]
• 32: Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, August 1993
• 33: Dorai Staram , Matthias Felleisen, Control delimiters and their hierarchies, Lisp and Symbolic Computation, v.3 n.1, p.67-99, Jan. 1990 [doi>10.1007/BF01806126]
• 34: Mitchell Wand , Daniel P. Friedman, The mystery of the tower revealed: a non-reflective description of the reflective tower, Proceedings of the 1986 ACM conference on LISP and functional programming, p.298-307, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319871]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Functional constructs

General Terms:
Algorithms, Experimentation, Measurement