Charles Consel
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.
- 1.A. D. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques and Tools. Addison-Wesley, 1986. Google Scholar
Digital Library
- 2.A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. Google ScholarDigital Library
- 3.L. O. Andersen. Self-applicable C program specialization. In Consel {26}, pages 54-61.Google Scholar
- 4.A. W. Appel. Compiling with Continuations. Cambridge University Press, 1992. Google ScholarDigital Library
- 5.W. Au and D. Weise. Automatic generation of compiler simulation through program specialization. In IEEE Conference on Design Automation, pages 205-210, 1991. Google ScholarDigital Library
- 6.Denis Bechet. Partial evaluation of interaction nets. In WSA'92 {109}, pages 331-338.Google Scholar
- 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.Google ScholarCross Ref
- 8.A. Berlin. Partial evaluation appfied to numerical computation. In A CM Conference on Lisp and Functional Programming~ pages 139-150, 1990. Google ScholarDigital Library
- 9.D. Bj0rner, A. P. Ershov, and N. D. Jones, editors. Partial Evaluation and Mixed Computation. North-Holland, 1988.Google Scholar
- 10.C. BShm. Subduing self-application. In 16th International Colloquium on Automata, Languages and Programming, volume 372 of Lecture Notes in Computer Science. Springer- Verlag, 1989. Google ScholarDigital Library
- 11.A. Bondorf. Towards a self-applicable partial evaluator for term rewriting systems. In Bj0rner et al. {9}.Google Scholar
- 12.A. Bondorf. Self-Applicable Partial Evaluation. PhD thesis, University of Copenhagen, DIKU, Copenhagen, Denmark, 1990. DIKU Report 90-17.Google Scholar
- 13.A. Bondorf. Automatic autoprojection of higher-order recursire equations. Science of Computer Programming, 17:3-34, 1991. Google ScholarDigital Library
- 14.A. Bondorf. Similix manual, system version 3.0. Technical Report 91/9, Computer Science Department, University of Copenhagen, 1991.Google Scholar
- 15.A. Bondorf. Improving binding times without explicit CPS- conversion. In A CM Conference on Lisp and Functional Programming, pages 1-10, 1992. Google ScholarDigital Library
- 16.A. Bondorf and O. Danvy. Automatic autoprojection of recursive equations with global variables and abstract data types. Science of Computer Programming, 16:151-195, 1991. Google ScholarDigital Library
- 17.R. S. Boyer and J. S. Moore. A fast string searching algorithm. Communications of the ACM, 20(10):62-72, 1976. Google ScholarDigital Library
- 18.M. A. Bulyonkov. Polyvariant mixed computation for analyzer programs. Acta Informatica, 21:473-484, 1984.Google ScholarDigital Library
- 19.R. M. Burstall and J. Darlington. A transformational system for developing recursive programs. Journal of A CM, 24(1):44-67, 1977. Google ScholarDigital Library
- 20.C. Chambers and D. Ungar. Customization: Optimizing compiler technology for SELF, a dynamically-typed objectoriented programming language. In A CM SIGPLAN Conference on Programming Language Design and Implementation, SIGPLAN Notices, Vol. 24, No 7, pages 146-160, 1989. Google ScholarDigital Library
- 21.W. Clinger and J. Rees (editors). Revised4 report on the algorithmic language Scheme. LISP Pointers, IV(3):1'--55, July-September 1991. Google ScholarDigital Library
- 22.C. Colby and P. Lee. An implementation of parameterized partial evaluation. In WSA'91 {108}, pages 82-89.Google Scholar
- 23.C. Consel. New insights into partial evaluation: the Schism experiment. In ESOP'88, ~nd European Symposium on Programming, volume 300 of Lecture Notes in Computer Science, pages 236-246. Springer-Verlag, 1988. Google Scholar
- 24.C. Consel. Analyse de Programmes, Evaluation Partielle et Gdndration de Compilateurs. PhD thesis, Universit~ de Paris VI, Paris, France, June 1989.Google Scholar
- 25.C. Consel. Binding time analysis for higher order untyped functional languages. In A CM Conference on Lisp and Functional Programming, pages 264-272, 1990. Google ScholarDigital Library
- 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.Google Scholar
- 27.C. Consel. Report on Schism'92. Research report, Pacific Software Research Center, Oregon Graduate Institute of Science and Technology, Beaverton, Oregon, USA, 1992.Google Scholar
- 28.C. Consel and O. Danvy. Partial evaluation of pattern matching in strings. Information Processing Letters, 30(2):79-86, 1989. Google ScholarDigital Library
- 29.C. Consel and O. Danvy. From interpreting to compiling binding times. In ESOP'90, 3rd European Symposium on Programming, volume 432 of Lecture Notes in Computer Science, pages 88-105. Springer-Verlag, 1990. Google Scholar
- 30.C. Consel and O. Danvy. For a better support of static data flow. In Hughes {63}, pages 496-519. Google Scholar
- 31.C. Consel and O. Danvy. Static and dynamic semantics processing. In A CM Symposium on Principles of Programming Languages, pages 14-23, 1991. Google ScholarDigital Library
- 32.C. Consel and S. C. Khoo. Parameterized partial evaluation. Research Report 865, Yale University, New Haven, Connecticut, USA, 1991. To appear in Transactions on Programming Languages and Systems. Extended version of {33}. Google ScholarDigital Library
- 33.C. Consel and S. C. Khoo. Parameterized partial evaluation. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 92-106, 1991. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 36.C. Consel and S. Psi. A programming environment for binding-time based partial evaluators. In Consel {26}, pages 62-66.Google Scholar
- 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.Google Scholar
- 38.K. D. Cooper, M. W. Hall, and K. Kennedy. Procedure cloning, in Fourth IEEE International Conference on Computer Languages, pages 96-105, 1992.Google ScholarCross Ref
- 39.Pierre Cr~gut. Machines d environnement pour la rgduction symbolique et l ' gvaluation partielle. PhD thesis, Universit6 Paris VII, 1991.Google Scholar
- 40.O. Danvy. Semantics-directed compilation of non-hnear patterns. In.formation Processing Letters, 37:315-322, March 1991. Google ScholarDigital Library
- 41.L. P. Deutsch. An interactive program verifier. Technical Report CSL-73-1, Xerox PARC, May 1973.Google Scholar
- 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.Google Scholar
- 43.D. P. Friedman, M. Wand, and C. T. Haynes. Essentials of Programming Languages. MIT Press and McGraw-Hill, 1991. Google ScholarDigital Library
- 44.D. A. Fuller and S. Abramsky. Mixed computation of Prolog. In Bjorner et al. {9}.Google Scholar
- 45.Y. Futamura. Partial evaluation of computation processan approach to a compiler-compiler. Systems, Computers, Controls P, 5, pages 45-50, 1971.Google Scholar
- 46.Y. Futamura and K. Nogi. Generalized partial computation. In Bjorner et al. {9}.Google Scholar
- 47.J. Gallager and M. Codish. Specialisation of Prolog and FCP programs using abstract interpretation. In Bjorner et al. {9}.Google Scholar
- 48.M. Gengler and B. Rytz. A polyvariant binding time analysis handling partially known values. In WSA'92 {109}, pages 322-330.Google Scholar
- 49.R. Glück. Towards multiple self-application.
In Hudak and Jones [61], pages 309-320. Google Scholar
- 50.D. Golub, R. Dean, A. Forin, and R. Rashid. Unix as an application program. In Proceedings of the USENIX Summer Conference, 1990.Google Scholar
- 51.C. K. Gomard. Higher order partial evaluation - HOPE for the lambda calculus. Master's thesis, DIKU, University of Copenhagen, Copenhagen, Denmark, 1989.Google Scholar
- 52.C. K. Gomard. Partial type inference for untyped functional programs. In A CM Conference on Lisp and Functional Programming, 1990. Google ScholarDigital Library
- 53.C. K. Gomard. A self-appficable partial evaluator for the lambda-calculus: Correctness and pragmatics. A CM Transactions on Programming Languages and Systems, 14(2):147- 172, 1992. Google ScholarDigital Library
- 54.C. K. Gomard and N.D. Jones. Compiler generation by partial evaluation: a case study. Structured Programming, 12:123-144, 1991.Google Scholar
- 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.Google Scholar
- 56.T. A. Hansen. Transforming a naive pattern matcher into efficient pattern matchers. Technical report, DAIMI, 1991.Google Scholar
- 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.Google Scholar
- 58.S. Harnett and M. Montenyohl. Towards efficient compilation of a dynamic object-oriented language. In Consel {26}, pages 82-89.Google Scholar
- 59.F. ttenglein. Efficient type inference for higher-order binding-time analysis. In Hughes {63}, pages 448-472. Google Scholar
- 60.C. K. Holst. Language triplets: The AMIX approach. In Bjorner et al. {9}, pages 167-185.Google Scholar
- 61.P. Hudak and N. D. Jones, editors. Partial Evaluation and Semantics based Program Manipulation. Vol. 26, No 9. ACM SIGPLAN Notices, 1991.Google Scholar
- 62.J. Hughes. Backward analysis of functional programs.Google Scholar
- 63.John Hughes, editor. FPCA '91, 5th International Conference on Functional Programming Languages and Computer Architecture, number 523 in Lecture Notes in Computer Science, 1991. Google ScholarDigital Library
- 64.S. Jagannathan and J. Philbin. A foundation for an efficient multi-threaded Scheme system. In A CM Conference on Lisp and Functional Programming, pages 345-357, 1992. Google ScholarDigital Library
- 65.N. D. Jones. Partial evaluation, self-application and types. In 17th International Colloquium on Automata, Languages and Programming, volume 443 of Lecture Notes in Computer Science, pages 639-659. Springer-Verlag, 1990. Google Scholar
- 66.N. D. Jones, C. K. Gomard, and P. Sestoft. Partial Evaluation and A utomatzc Program Generation. Prentice-Hall International, 1993. To appear. Google ScholarDigital Library
- 67.N. D. Jones, P. Sestoft, and H. S0ndergaard. An experiment in partial evaluation: the generation of a compiler generator. In J.-P. Jouannaud, editor, Rewriting Techniques and Applications, Dijon, France, volume 202 of Lecture Notes in Computer Science, pages 124-140. Springer-Verlag, 1985. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 70.J. JOrgensen. Generating a compiler for a lazy language by partial evaluation, in A CM Symposium on Principles o} Programming Languages, pages 258-268, 1992. Google Scholar
- 71.M. Katz and D. Weise. Towards a new perspective on partial evaluation. In Consel {26}, pages 29-37.Google Scholar
- 72.S. C. Khoo. Parameterized Partial Evaluation: Theory and Practice. PhD thesis, Yale University, 1992. Forthcoming. Google ScholarDigital Library
- 73.S. C. Khoo and R. S. Sundaresh. Compiling inheritance using partial evaluation. In Hudak and Jones {61}, pages 211-222. Google Scholar
- 74.S. C. Kleene. Introduction to Metamathematics. Van Nostrand, 1952.Google Scholar
- 75.D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM, 6(2):323-350, 1977.Google ScholarDigital Library
- 76.H. J. Komorowski. Partial evaluation as a means for inferencing data structures in an applicative language: A theory and implementation in the case of Prolog. In ACM Symposium on Principles of Programming Languages, 1982. Google ScholarDigital Library
- 77.A. Lakhotia and L. Sterling. ProMiX: A Prolog partial evalnation system, in L. Sterling, editor, The Practice of Prolog, chapter 5, pages 137-179. MIT Press, 1991. Google Scholar
- 78.J. L&unchbury. Projection Factorisation in Partial Evaluation. PhD thesis, Department of Computing Science, University of Glasgow, Scotland, 1990.Google Scholar
- 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.Google Scholar
- 80.K. Malmkjmr. On static properties of specialized programs. in WSA'91 {108}, pages 234-241.Google Scholar
- 81.K. Malmkjaer. Predicting properties of residual programs. In Consel {26}, pages 8-13.Google Scholar
- 82.U. Meyer. Techniques for partial evaluation of imperative languages. In Hudak and Jones {61}, pages 94-105. Google Scholar
- 83.T. Mogensen. The application of partial evaluation to raytracing. Master's thesis, University of Copenhagen, DIKU, Copenhagen, Denmark, 1986.Google Scholar
- 84.T. Mogensen. Bindsng Time Aspects o} Partial Evaluation. PhD thesis, University of Copenhagen, DIKU, Copenhagen, Denmark, 1989.Google Scholar
- 85.P. Mosses. SIS- Semantics Implementation System, reference manual and user guide. University of Aarhus, Aarhus, Denmark, 1979. Version 1.0.Google Scholar
- 86.C. Mossin. Similix binding time debugger manual. Technical report, University of Copenhagen, Copenhagen, Denmark, 1991.Google Scholar
- 87.F. Nielson and H. R. Nielson. Two-Level Functional Languages. Cambridge University Press, 1992. Google ScholarDigital Library
- 88.H. R. Nielson and F. Nielson. Automatic binding time analysis for a typed ),-calculus. in A CM Symposium on Principles of Programming Languages, pages 98-106, 1988. Google Scholar
- 89.V. Nirkhe and W. Pugh. Partial evaluation of high-level imperative program languages with applications in hard realtime systems. In A CM Symposium on Principles of Programming Languages, pages 269-280, 1992. Google ScholarDigital Library
- 90.J. Palsberg and M. I. Schwartzbach. Binding time analysis: Abstract interpretation versus type inference. Technical report, DAIMI, 1992.Google Scholar
- 91.C. Pu, H. Massalin, and J. Ioamnidis. The Synthesis kernel. ACM Computing Systems, 1(1):11-32, 1988.Google Scholar
- 92.C. Queinnec and J. M. Geffroy. Partial evaluation applied to pattern matching with intelligent backtracking. In WSA'92 {109}, pages 109-117.Google Scholar
- 93.E. Ruf. Topics in Online Partial Evaluation. PhD thesis, Department of Computer Science, Stanford University, 1993. (in preparation). Google ScholarDigital Library
- 94.E. Ruf and D. Weise. Using types to avoid redundant specialization. In Hudak and Jones {61}, pages 321-333. Google Scholar
- 95.E. Ruf and D. Weise. Improving the accuracy of higherorder specialization using control flow analysis. In Consel {26}, pages 67-74.Google Scholar
- 96.B. Rytz and M. Gengler. A polyvariant binding time analysis. In Consel {26}, pages 21-28.Google Scholar
- 97.W. L. Scherlis. Expression Procedures and Program Derivatwn. PhD thesis, Department of Computer Science, Stanford University, 1980. Report No. STAN-CS-80-818. Google ScholarDigital Library
- 98.D. A. Schmidt. Static properties of partial evaluation. In Bjcrner et al. {9}, pages 465-483.Google Scholar
- 99.R. Schooler. Partial evaluation as a means of language extensibility. Master's thesis, M.I.T. (LCS), Massachusetts, U.S.A, 1984. TR-324. Google ScholarDigital Library
- 100.P. Sestoft. Automatic call unfolding in a partial evaluator. In Bj0rner et al. {9}.Google Scholar
- 101.D. Sherman, It. Strandh, and I. Durand. Optimization of equational programs using partial evaluation. In Hudak and Jones {61}, pages 72-82. Google Scholar
- 102.D. A. Smith. Partial evaluation of pattern matching in CLP domains. In Hudak and Jones {61}, pages 62-71. Google Scholar
- 103.K. L. Solberg, H. It. Nielson, and F. Nielson. Inference systems for binding time analysis. In WSA'92 {109}, pages 247-254.Google Scholar
- 104.R. S. Sundaresh and P. Hudak. Incremental computation via partial evaluation, in A CM Symposium on Principles o} Programming Languages, pages 1-13, 1991. Google Scholar
- 105.M. N. Wegman and F. K. Zadeck. Constant propagation with conditional branches. A CM Transactions on Programming Languages and Systems, 3(2):181-210, 1991. Google ScholarDigital Library
- 106.P. Weiner. Linear pattern matching algorithms. In 14th Annual Symposium on Switching and Automata Theory, pages 1-11, 1973.Google ScholarDigital Library
- 107.D. Weise, R. Conybeare, E. Ruf, and S. Seligman. Automatic online partial evaluation. In Hughes {63}, pages 165-191. Google Scholar
- 108.Workshop on Static Analysis, volume 74 of Bigre Journal. IRISA, Itennes, France, 1991.Google Scholar
- 109.Workshop on Static Analysis, volume 81-82 of Bigre Journal. IItISA, Rennes, France, 1992.Google Scholar
Index Terms
- Tutorial notes on partial evaluation
Comments