Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Partial evaluation provides a unifying paradigm for a broad spectrum of work in program optimization compiling interpretation and the generation of automatic program generators [Bjørner et al. 1987; Ershov 1992; and Jones et al. 1993]. It is a program optimization technique, perhaps better called program specialization, closely related to but different from Jørring and Scherlis' staging transformations [1986]. It emphasizes, in comparison with Burstall and Darlington [1977] and Jørring and Scherlis [1986] and other program transformation work, full automation and the generation of program generators as well as transforming single programs. Much partial evaluation work to date has concerned automatic compiler generation from an interpretive definition of programming language, but it also has important applications to scientific computing, logic programming, metaprogramming, and expert systems; some pointers are given later.

REFERENCES

• 1: ACM. 1991. Partial Evaluation and Semantics- Based Program Manipulation, New Haven, Connecticut. (Sigplan Notices, 26, 9, Sept.), ACM Press.
• 2: ACM. 1992. Sigplan Workshop on Partial Evaluation and Semantics-Based Program Manipulation, (San Francisco).
• 3: ACM. 1993. Sigplan Workshop on Partial Evaluation and Semantics-Based Program Manipulation (Copenhagen). ACM Press.
• 4: ACM 1994. Sigplan Workshop on Partial Evaluation and Semantics-Based Program Manipulation, (Orlando, Florida) Univ. of Melbourne report 94/9, 1994.
• 5: ACM. 1995. Sigplan Workshop on Partial Evaluation and Semantics-Based Program Manipulation, (San Diego, Calif.) ACM Press.
• 6: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 7: ANDERSEN, L. O. 1994. Program analysis and specialization for the C programming language. DIKU, Dept. of Computer Science, Univ. of Copenhagen. DIKU Rep. No. 94/19.
• 8: ANDERSEN, L. O. 1992. C program specialization. International Workshop on Compiler Construction, (Paderborn, Germany), Springer-Verlag.
• 9: ANDERSEN, P. H. 1994. Partial evaluation applied to ray tracing. Res. Rep. DIKU, Dept. of Computer Science, Univ. of Copenhagen.
• 10: APPEL, A. 1988. Reopening closures. Unpublished report, Princeton Univ.
• 11: BAIER, R., GLUCK, R., AND Z()CHLING, R. 1994. Partial evaluation of numerical programs in Fortran. In Proceedings of ACM SIGPLAN Workshop on Partial Evaluation and Semantics- Based Program Manipulation, Tech. Rep. 94/9, Univ. of Melbourne, Australia, 119-132.
• 12: BECKMAN, L., ET AL. 1976. A partial evaluator, and its use as a programming tool. Artif. Intell. 7, 4, 319-357.
• 13: Andrew Berlin , Daniel Weise, Compiling Scientific Code Using Partial Evaluation, Computer, v.23 n.12, p.25-37, December 1990 [doi>10.1109/2.62091]
• 14: BJORNER, D., ERSHOV, A. P., AND JONES, N. D. EDS. 1987. Partial evaluation and mixed computation. In Proceedings of the IFIP TC2 Workshop (Gammel Avernoes, Denmark, Oct.) North-Holland, 1988.
• 15: Anders Bondorf, A Self-Applicable Partial Evaluator for Term Rewriting Systems, Proceedings of the International Joint Conference on Theory and Practice of Software Development, Volume 2: Advanced Seminar on Foundations of Innovative Software Development II and Colloquium on Current Issues in Programming Languages, p.81-95, March 13-17, 1989
• 16: BONDORF, A. 1990. Self-applicable partial evaluation. PhD thesis, DIKU, Univ. of Copenhagen. Revised version: DIKU Rep. 90/17.
• 17: Anders Bondorf, Automatic autoprojection of higher order recursive equations, Science of Computer Programming, v.17 n.1-3, p.3-34, Dec. 1991
• 18: 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]
• 19: 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]
• 20: Charles Consel , François Noël, A general approach for run-time specialization and its application to C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.145-156, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237767]
• 21: 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]
• 22: 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]
• 23: 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]
• 24: ERSHOV, A.P. 1982. Mixed computation: Potential applications and problems for study. Theor. Comput. Sci., 18, 41-67.
• 25: ERSHOV, A. P., BJORNER, D., FUTAMURA, Y., FU- RUKAWA, K., HARALDSON, A., AND SCHERLIS, W. EDS. 1988. In Special Issue: Selected Papers from the Workshop on Partial Evaluation and Mixed Computation, 1987. New Generation Comput., 6, 2,3. Ohmsha Ltd. and Springer-Verlag.
• 26: Yoshihiko Futamura, Partial Evaluation of Computation Process—AnApproach to a Compiler-Compiler, Higher-Order and Symbolic Computation, v.12 n.4, p.381-391, December 1999 [doi>10.1023/A:1010095604496]
• 27: GOMARD, C. K. AND JONES, N.D. 1991a. Compiler generation by partial evaluation: a case study. Structured Program. 12, 123-144. Also as DIKU-report 88/24 and 90/16.
• 28: GOMARD, C. K. AND JONES, N.D. 1991b. A partial evaluator for the untyped lambda-calculus. J. Funct. Program. 1 1 (Jan.) 21-69.
• 29: John Hannan , Dale Miller, From operational semantics to abstract machines: preliminary results, Proceedings of the 1990 ACM conference on LISP and functional programming, p.323-332, June 27-29, 1990, Nice, France [doi>10.1145/91556.91680]
• 30: HOLST, N. C. K. 1988. Language triplets: The AMIX approach. In Partial Evaluation and Mixed Computation, D. Bj0rner, A. P. Ershov, and N. D. Jones, Eds., North-Holland, 167- 185.
• 31: JACOBSEN, H. F. 1990. Speeding up the backpropagation algorithm by partial evaluation. DIKU Student Project 90-10-13, 32 pages. DIKU, Univ. of Copenhagen. (In Danish).
• 32: JONES, N.D. 1988. Automatic program specialization: A re-examination from basic principles. In Partial Evaluation and Mixed Computation, D. Bj0rner, A. P. Ershov, and N. D. Jones, Eds. North-Holland, 225-282.
• 33: Neil D. Jones, Mix ten years later, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.24-38, June 21-23, 1995, La Jolla, California, United States [doi>10.1145/215465.215468]
• 34: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 35: 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
• 36: JONES, N. D., SESTOFT, P., AND SONDERGAARD, H. 1989. Mix: A self-applicable partial evaluator for experiments in compiler generation. Lisp Symbolic Comput., 2, 1, 9-50.
• 37: 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]
• 38: Ulrik Jørring , William L. Scherlis, Compilers and staging transformations, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.86-96, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512652]
• 39: 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]
• 40: John Launchbury, Projection factorisations in partial evaluation, Cambridge University Press, New York, NY, 1991
• 41: LEONE, M. AND LEE, P. 1994. Lightweight runtime code generation. In Proceedings of PEPM'94, the ACM Sigplan Symposium on Partial Evaluation and Semantics-Based Program Manipulation. ACM Press.
• 42: Michael Leuschel , Danny De Schreye, Towards creating specialised integrity checks through partial evaluation of meta-interpreters, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.253-263, June 21-23, 1995, La Jolla, California, United States [doi>10.1145/215465.215598]
• 43: J. W. Lloyd , J. C. Shepherdson, Partial evaluation in logic programming, Journal of Logic Programming, v.11 n.3-4, p.217-242, Oct./Nov. 1991 [doi>10.1016/0743-1066(91)90027-M]
• 44: LOMBARDI, L. A. AND RAPHAEL, B. 1964. Lisp as the language for an incremental computer. In The Programming Language Lisp: Its Operation and Applications, E. C. Berkeley and D. G. Bobrow, Eds. MIT Press, Cambridge, Massachusetts, 204-219.
• 45: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 46: MOGENSEN, T. 1986. The application of partial evaluation to ray-tracing. Master's thesis, DIKU, Univ. of Copenhagen, Denmark.
• 47: MOSSES, P. 1979. SIS--semantics implementation system, reference manual and user guide. DAIMI Rep. MD-30, DAIMI, Univ. of Aarhus, Denmark.
• 48: 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]
• 49: Frank G. Pagan, Partial computation and the construction of language processors, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 50: Lawrence Paulson, Compiler generation from denotational semantics, Methods and tools for compiler construction, Cambridge University Press, New York, NY, 1984
• 51: PINGALI, K. AND ROGERS, A. 1990. Compiler parallelization for a simple distributed memorymachine. In International Conference on Parallel Programming, (St. Charles, Illinois).
• 52: C. Pu , T. Autrey , A. Black , C. Consel , C. Cowan , J. Inouye , L. Kethana , J. Walpole , K. Zhang, Optimistic incremental specialization: streamlining a commercial operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.314-321, December 03-06, 1995, Copper Mountain, Colorado, United States
• 53: ROMANENKO, S. A. 1988. A compiler generator produced by a self-applicable specializer can have a surprisingly natural and understandable structure. In Partial Evaluation and Mixed Computation, D. Bj~rner, A. P. Ershov, and N. D. Jones, Eds. North-Holland, 445- 463.
• 54: Erik Steven Ruf, Topics in online partial evaluation, Stanford University, Stanford, CA, 1993
• 55: SAFRA, S. AND SHAPIRO, E. 1986. Meta interpreters for real. In Information Processing 86, H.-J. Kugler, Ed. North-Holland, 271-278.
• 56: Dan Sahlin, The Mixtus approach to automatic partial evaluation of full Prolog, Proceedings of the 1990 North American conference on Logic programming, p.377-398, January 1990, Austin, Texas, United States
• 57: SESTOFT, P. AND ZAMULIN, A. V. 1988. Annotated bibliography on partial evaluation and mixed computation. In Special Issue: Selected Papers from the Workshop on Partial Evaluation and Mixed Computation. Ohmsha Ltd. and Springer-Verlag, 309-354.
• 58: Ehud Y. Shapiro, Algorithmic Program DeBugging, MIT Press, Cambridge, MA, 1983
• 59: Morten Heine Sørensen , Robert Glück , Neil D. Jones, Towards Unifying Partial Evaluation, Deforestation, Supercompilation, and GPC, Proceedings of the 5th European Symposium on Programming: Programming Languages and Systems, p.485-500, April 11-13, 1994
• 60: Michael Sperber , Peter Thiemann, Realistic compilation by partial evaluation, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.206-214, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 61: Michael Sperber , Peter Thiemann, The essence of LR parsing, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.146-155, June 21-23, 1995, La Jolla, California, United States [doi>10.1145/215465.215579]
• 62: 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]
• 63: Jesper Vasell, A partial evaluator for data flow graphs, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.206-215, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154651]
• 64: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.m Miscellaneous
          Subjects: Rapid prototyping**

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Experimentation, Performance, Verification

Keywords:
compiler generators, compilers, interpreters, partial evaluation, program specialization