Tutorial notes on partial evaluation

ABSTRACT

The last years have witnessed a flurry of new results in the area of partial evaluation. These tutorial notes survey the field and present a critical assessment of the state of the art.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: L. O. Andersen. Self-applicable C program specialization. In Consel {26}, pages 54-61.
• 4: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 5: Wing Yee Au , Daniel Weise , Scott Seligman, Automatic generation of compiled simulations through program specialization, Proceedings of the 28th conference on ACM/IEEE design automation, p.205-210, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127665]
• 6: Denis Bechet. Partial evaluation of interaction nets. In WSA'92 {109}, pages 331-338.
• 7: L. Beckman, A. Haraldsson, O. Oskarsson, and E. Sandewall. A partial evaluator, and its use as a programming tool. Artificial intelligence, 7(4):319-357, 1976.
• 8: Andrew Berlin, Partial evaluation applied to numerical computation, Proceedings of the 1990 ACM conference on LISP and functional programming, p.139-150, June 27-29, 1990, Nice, France [doi>10.1145/91556.91612]
• 9: D. Bj0rner, A. P. Ershov, and N. D. Jones, editors. Partial Evaluation and Mixed Computation. North-Holland, 1988.
• 10: Corrado Böhm, Subduing Self-Application, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.108-122, July 11-15, 1989
• 11: A. Bondorf. Towards a self-applicable partial evaluator for term rewriting systems. In Bj0rner et al. {9}.
• 12: A. Bondorf. Self-Applicable Partial Evaluation. PhD thesis, University of Copenhagen, DIKU, Copenhagen, Denmark, 1990. DIKU Report 90-17.
• 13: Anders Bondorf, Automatic autoprojection of higher order recursive equations, Science of Computer Programming, v.17 n.1-3, p.3-34, Dec. 1991
• 14: A. Bondorf. Similix manual, system version 3.0. Technical Report 91/9, Computer Science Department, University of Copenhagen, 1991.
• 15: 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
• 16: Anders Bondorf , Olivier Danvy, Automatic autoprojection of recursive equations with global variable and abstract data types, Science of Computer Programming, v.16 n.2, p.151-195, Sept. 1991 [doi>10.1016/0167-6423(91)90002-F]
• 17: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 18: M. A. Bulyonkov. Polyvariant mixed computation for analyzer programs. Acta Informatica, 21:473-484, 1984.
• 19: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 20: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, ACM SIGPLAN Notices, v.24 n.7, p.146-160, July 1989
• 21: 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]
• 22: C. Colby and P. Lee. An implementation of parameterized partial evaluation. In WSA'91 {108}, pages 82-89.
• 23: Charles Consel, New Insights into Partial Evaluation: the SCHISM Experiment, Proceedings of the 2nd European Symposium on Programming, p.236-246, March 21-24, 1988
• 24: C. Consel. Analyse de Programmes, Evaluation Partielle et Gdndration de Compilateurs. PhD thesis, Universit~ de Paris VI, Paris, France, June 1989.
• 25: Charles Consel, Binding time analysis for high order untyped functional languages, Proceedings of the 1990 ACM conference on LISP and functional programming, p.264-272, June 27-29, 1990, Nice, France [doi>10.1145/91556.91668]
• 26: C. Consel, editor. A CM Workshop on Partial Evaluation and Semantics-Based Program Manipulation. Research Report 909, Department of Computer Science, Yale University, 1992.
• 27: C. Consel. Report on Schism'92. Research report, Pacific Software Research Center, Oregon Graduate Institute of Science and Technology, Beaverton, Oregon, USA, 1992.
• 28: Charles Consel , Olivier Danvy, Partial evaluation of pattern matching in strings, Information Processing Letters, v.30 n.2, p.79-86, January 1989 [doi>10.1016/0020-0190(89)90113-0]
• 29: 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
• 30: 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
• 31: Charles Consel , Olivier Danvy, Static and dynamic semantics processing, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.14-24, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99588]
• 32: 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]
• 33: Charles Consel , Siau Cheng Khoo, Parameterized partial evaluation, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.92-106, June 24-28, 1991, Toronto, Ontario, Canada
• 34: C. Consel and S. C. Khoo. Semantics-directed generation of a Prolog compiler. In 3rd International Symposium on Programming Language Implementation and Logic Programming, volume 528 of Lecture Notes in Computer Science, pages 135-146. Springer-Verlag, 1991.
• 35: C. Consel and S.C. Khoo. On-line & off-line partial evaluation: Semantic specifications and correctness proofs. Research Report 896, Yale University, New Haven, Connecticut, USA, 1992.
• 36: C. Consel and S. Psi. A programming environment for binding-time based partial evaluators. In Consel {26}, pages 62-66.
• 37: C. Consel, C. Pu, and J. Walpole. Incremental specialization: The key to high performance, modularity and portability in operating systems. Research report, Pacific Software Research Center, Oregon Graduate Institute of Science and Technology, Beaverton, Oregon, USA, 1992.
• 38: K. D. Cooper, M. W. Hall, and K. Kennedy. Procedure cloning, in Fourth IEEE International Conference on Computer Languages, pages 96-105, 1992.
• 39: Pierre Cr~gut. Machines d environnement pour la rgduction symbolique et l ' gvaluation partielle. PhD thesis, Universit6 Paris VII, 1991.
• 40: Olivier Danvy, Semantics-directed compilation of nonlinear patterns, Information Processing Letters, v.37 n.6, p.315-322, March 28, 1991 [doi>10.1016/0020-0190(91)90148-B]
• 41: L. P. Deutsch. An interactive program verifier. Technical Report CSL-73-1, Xerox PARC, May 1973.
• 42: A. P. Ershov, D. Bjorner, Y. Futamura, K. Furukawa, A. Haraldsson, and W. L. Scherlis, editors. Selected Papers from the Workshop on Partial Evaluation and Mixed Computation, volume 6 (2,3) of New Generation Computing. OHMSHA. LTD. and Springer-Verlag, 1988.
• 43: Daniel P. Friedman , Christopher T. Haynes , Mitchell Wand, Essentials of programming languages, MIT Press, Cambridge, MA, 1992
• 44: D. A. Fuller and S. Abramsky. Mixed computation of Prolog. In Bjorner et al. {9}.
• 45: Y. Futamura. Partial evaluation of computation processan approach to a compiler-compiler. Systems, Computers, Controls P, 5, pages 45-50, 1971.
• 46: Y. Futamura and K. Nogi. Generalized partial computation. In Bjorner et al. {9}.
• 47: J. Gallager and M. Codish. Specialisation of Prolog and FCP programs using abstract interpretation. In Bjorner et al. {9}.
• 48: M. Gengler and B. Rytz. A polyvariant binding time analysis handling partially known values. In WSA'92 {109}, pages 322-330.
• 49: R. Glfick. Towards multiple self-application. In I-Iudak and
• 50: D. Golub, R. Dean, A. Forin, and R. Rashid. Unix as an application program. In Proceedings of the USENIX Summer Conference, 1990.
• 51: C. K. Gomard. Higher order partial evaluation - HOPE for the lambda calculus. Master's thesis, DIKU, University of Copenhagen, Copenhagen, Denmark, 1989.
• 52: Carsten K. Gomard, Partial type inference for untyped functional programs, Proceedings of the 1990 ACM conference on LISP and functional programming, p.282-287, June 27-29, 1990, Nice, France [doi>10.1145/91556.91672]
• 53: Carsten K. Gomard, A self-applicable partial evaluator for the lambda calculus: correctness and pragmatics, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.2, p.147-172, April 1992 [doi>10.1145/128861.128864]
• 54: C. K. Gomard and N.D. Jones. Compiler generation by partial evaluation: a case study. Structured Programming, 12:123-144, 1991.
• 55: M. A. Guzowski. Toward developing a reflexive partial evaluator for an interesting subset of Lisp. Master's thesis, Department of Computer Engineering and Science, Case Western Reserve University, Cleveland, Ohio, 1988.
• 56: T. A. Hansen. Transforming a naive pattern matcher into efficient pattern matchers. Technical report, DAIMI, 1991.
• 57: A. Haraldsson. A Program Manipulation System Based on Partial Evaluation. PhD thesis, LinkSping University, Sweden, 1977. LinkSping Studies in Science and Technology Dissertations N~ 14.
• 58: S. Harnett and M. Montenyohl. Towards efficient compilation of a dynamic object-oriented language. In Consel {26}, pages 82-89.
• 59: Fritz Henglein, Efficient type inference for higher-order binding-time analysis, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.448-472, June 1991, Cambridge, Massachusetts, United States
• 60: C. K. Holst. Language triplets: The AMIX approach. In Bjorner et al. {9}, pages 167-185.
• 61: P. Hudak and N. D. Jones, editors. Partial Evaluation and Semantics based Program Manipulation. Vol. 26, No 9. ACM SIGPLAN Notices, 1991.
• 62: J. Hughes. Backward analysis of functional programs.
• 63: Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, June 1991
• 64: Suresh Jagannathan , Jim Philbin, A foundation for an efficient multi-threaded scheme system, Proceedings of the 1992 ACM conference on LISP and functional programming, p.345-357, June 22-24, 1992, San Francisco, California, United States
• 65: Neil D. Jones, Partial evaluation, self-application and types, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.639-659, July 1990, Warwick University, England
• 66: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 67: Neil D. Jones , Peter Sestoft , Harald Sondergaard, An experiment in partial evaluation: the generation of a compiler generator, Proc. of the first international conference on Rewriting techniques and applications, p.124-140, December 1985, Dijon, France
• 68: N. D. Jones, P. Sestoft, and H. Sendergaard. Mix: a selfapplicable partial evaluator for experiments in compiler generation. LISP and Symbolic Computation, 2(1):9-50, 1989.
• 69: J. J0rgensen. Generating a pattern matching compiler by partial evaluation. In Simon L. Peyton Jones, Guy Hutton, and Carsten Kehler Hoist, editors, Functional Programming, Glasgow 1990, pages 177-195. Springer-Verlag, 1991.
• 70: Jesper Jørgensen, Generating a compiler for a lazy language by partial evaluation, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.258-268, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143220]
• 71: M. Katz and D. Weise. Towards a new perspective on partial evaluation. In Consel {26}, pages 29-37.
• 72: Siau Cheng Khoo, Parameterized partial evaluation principle and practice, Yale University, New Haven, CT, 1993
• 73: Siau Cheng Khoo , R. S. Sundaresh, Compiling inheritance using partial evaluation, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.211-222, June 17-19, 1991, New Haven, Connecticut, United States
• 74: S. C. Kleene. Introduction to Metamathematics. Van Nostrand, 1952.
• 75: D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM, 6(2):323-350, 1977.
• 76: H. Jan Komorowski, Partial evaluation as a means for inferencing data structures in an applicative language: a theory and implementation in the case of prolog, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.255-267, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582181]
• 77: Arun Lakhotia , Leon Sterling, ProMiX: a Prolog partial evaluation system, The practice of Prolog, MIT Press, Cambridge, MA, 1990
• 78: J. L&unchbury. Projection Factorisation in Partial Evaluation. PhD thesis, Department of Computing Science, University of Glasgow, Scotland, 1990.
• 79: L. A. Lombardi and B. Raphael. Lisp as the language for an incremental computer. In E. C. Berkeley and D. G. Bobrow, editors, The Programming Language Lisp: Its Operation and Applications, pages 204-219. MIT Press, Cambridge, Massachusetts, 1964.
• 80: K. Malmkjmr. On static properties of specialized programs. in WSA'91 {108}, pages 234-241.
• 81: K. Malmkjaer. Predicting properties of residual programs. In Consel {26}, pages 8-13.
• 82: Uwe Meyer, Techniques for partial evaluation of imperative languages, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.94-105, June 17-19, 1991, New Haven, Connecticut, United States
• 83: T. Mogensen. The application of partial evaluation to raytracing. Master's thesis, University of Copenhagen, DIKU, Copenhagen, Denmark, 1986.
• 84: T. Mogensen. Bindsng Time Aspects o} Partial Evaluation. PhD thesis, University of Copenhagen, DIKU, Copenhagen, Denmark, 1989.
• 85: P. Mosses. SIS- Semantics Implementation System, reference manual and user guide. University of Aarhus, Aarhus, Denmark, 1979. Version 1.0.
• 86: C. Mossin. Similix binding time debugger manual. Technical report, University of Copenhagen, Copenhagen, Denmark, 1991.
• 87: Flemming Nielson , Hanne Riis Nielson, Two-level functional languages, Cambridge University Press, New York, NY, 1992
• 88: F. Nielson , R. H. Nielson, Automatic binding time analysis for a typed &lgr;-calculus, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.98-106, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73569]
• 89: Vivek Nirkhe , William Pugh, Partial evaluation of high-level imperative programming languages with applications in hard real-time systems, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.269-280, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143223]
• 90: J. Palsberg and M. I. Schwartzbach. Binding time analysis: Abstract interpretation versus type inference. Technical report, DAIMI, 1992.
• 91: C. Pu, H. Massalin, and J. Ioamnidis. The Synthesis kernel. ACM Computing Systems, 1(1):11-32, 1988.
• 92: C. Queinnec and J. M. Geffroy. Partial evaluation applied to pattern matching with intelligent backtracking. In WSA'92 {109}, pages 109-117.
• 93: Erik Steven Ruf, Topics in online partial evaluation, Stanford University, Stanford, CA, 1993
• 94: Erik Ruf , Daniel Weise, Using types to avoid redundant specialization, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.321-333, June 17-19, 1991, New Haven, Connecticut, United States
• 95: E. Ruf and D. Weise. Improving the accuracy of higherorder specialization using control flow analysis. In Consel {26}, pages 67-74.
• 96: B. Rytz and M. Gengler. A polyvariant binding time analysis. In Consel {26}, pages 21-28.
• 97: William Louis Scherlis, Expression procedures and program derivation, 1980
• 98: D. A. Schmidt. Static properties of partial evaluation. In Bjcrner et al. {9}, pages 465-483.
• 99: R. Schooler, PARTIAL EVALUATION AS A MEANS OF LANGUAGE EXTENSIBILITY, Massachusetts Institute of Technology, Cambridge, MA, 1984
• 100: P. Sestoft. Automatic call unfolding in a partial evaluator. In Bj0rner et al. {9}.
• 101: David Sherman , Robert Strandh , Irène Durand, Optimization of equational programs using partial evaluation, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.72-82, June 17-19, 1991, New Haven, Connecticut, United States
• 102: Donald A. Smith, Partial evaluation of pattern matching in constraint logic programming languages, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.62-71, June 17-19, 1991, New Haven, Connecticut, United States
• 103: K. L. Solberg, H. It. Nielson, and F. Nielson. Inference systems for binding time analysis. In WSA'92 {109}, pages 247-254.
• 104: 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]
• 105: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
• 106: P. Weiner. Linear pattern matching algorithms. In 14th Annual Symposium on Switching and Automata Theory, pages 1-11, 1973.
• 107: Daniel Weise , Roland Conybeare , Erik Ruf , Scott Seligman, Automatic online partial evaluation, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.165-191, June 1991, Cambridge, Massachusetts, United States
• 108: Workshop on Static Analysis, volume 74 of Bigre Journal. IRISA, Itennes, France, 1991.
• 109: Workshop on Static Analysis, volume 81-82 of Bigre Journal. IItISA, Rennes, France, 1992.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines
      D.3.4 Processors
          Subjects: Compilers; Interpreters; Optimization

General Terms:
Algorithms, Languages, Performance