Jesper Jørgensen
ABSTRACT
Compiler generation is often emphasized as being the most important application of partial evaluation. But most of the larger practical applications have, to the best of our knowledge, been outside this field. Expecially, no one has generated compilers for languages other than small languages. This paper describes a large application of partial evaluation where a realistic compiler was generated for a strongly typed lazy functional language. The language, that was called BAWL, was modeled after the language in Bird and Wadler [BW88] and is a combinator language with pattern matching, guarded alternatives, local definitions and list comprehensions. The paper describes the most important techniques used, especially the binding time improvements needed in order to get small and efficient target programs. Finally, the performance of the compiler is compared with two compilers for similar languages: Miranda and LML.
- BD91.Anders Bondorf and Olivier Danvy. Automatic autoprojection of recursive equations with global variables and abstract data types. Science of Computer Programming, 16, 1991. To appear. Google Scholar
Digital Library
- Bon90.Anders Bondorf. Automatic autoprojection of higher order recursive equations. In Nell D. Jones, editor, ESOP'90, Copenhagen, Denmark. Lecture Notes in Computer Science ~32, pages 70-87, Springer-Verlag, May 1990. Google ScholarDigital Library
- Bon91a.Anders Bondorf. Compiling laziness by partial evaluation. In {JHH91}, pages 9-22, 1991.Google Scholar
- Bon91b.Anders Bondorf. Similix manual, system version 4.0. Included in Similix distribution, September 1991.Google Scholar
- Bon92.Anders Bondorf. Improving binding times without explicit cps-conversion. 1992. Forthcoming.Google Scholar
- BW88.Richard Bird and Philip Wadler. Introduction to Functional Programming. Computer Science, Prentice-Hall, 1988. Google ScholarDigital Library
- CD89.Charles Consel and Olivier Danvy. Partial evaluation of pattern matching in strings. Information Processing Letters, 30(2):79-86, 1989. Google ScholarDigital Library
- Con88.Charles Consel. New insights into partial evaluation: the schism experiment. In Harald Ganzinger, editor, ESOP'88, Nancy, France. Lecture Notes in Computer Science 300, pages 236-247, Springer-Verlag, March 1988. Google ScholarDigital Library
- Dan91.Olivier Danvy. Semantics-directed compilation of nonlinear patterns. Information Processing Letters, 37(6):315-322, 1991. Google ScholarDigital Library
- GJ89.Carsten K. Gomard and Nell D. Jones. Compiler generation by partial evaluation: a case study. In Proceedings of the Twelfth IFIP World Computer Congress, 1989.Google Scholar
- HG91.Carsten Kehler Holst and Carsten K. Gomard. Partial evaluation is fuller laziness. In Symposium on Partial Evaluation and Semantics- Based Program Manipulation, Yale University, New Haven, Connecticut. SIGPLAN Notices, volume P6, 9, pages 223-233, ACM Press, June 1991. Google ScholarDigital Library
- HH91.Carsten Kehler Hoist and John Hughes. Towards binding-time improvement for free. In {JHH91}, pages 83-100, 1991.Google Scholar
- HW90.Paul Hudak and Philip Wadler. Report on the programming language Haskell. Technical Report, Yale University and Glasgow University, April 1990.Google Scholar
- JHH91.Simon L. Peyton Jones, Graham Hutton, and Carsten Kehler Holst, editors. Functional Programming, Glasgow 1990. Workshops in Computing, Springer-Verlag, August 1991.Google Scholar
- Joh75.S.C. Johnson. YACC: Yet another compiler compiler. Technical Report 32, Bell laboratories, Murray Hill, New Jersey, 1975.Google Scholar
- Jor91a.Jesper Jergensen. Compiler Generation by Partial Evaluation. Master's thesis, DIKU, University of Copenhagen, Denmark, student report, October 1991. Forthcoming.Google Scholar
- Jor91b.Jesper Jergensen. Generating a pattern matching compiler by partial evaluation. In {JHH91}, pages 177-195, 1991.Google Scholar
- JSS85.Nell D. Jones, Peter Sestoft, and Harald Sendergaard. An experiment in partial evaluation: the generation of a compiler generator. In J.- P. Jouannaud, editor, Rewriting Techniques and Applications, Dijon, France. Lecture Notes in Computer Science 202, pages 124-140, Springer- Verlag, 1985. Google Scholar
- JSS89.Nell D. Jones, Peter Sestoft, and Harald Sendergaard. Mix: a self-applicable partial evaluator for experiments in compiler generation. LISP and Symbolic Computation, 2(1):9-50, 1989.Google ScholarCross Ref
- MTH90.Robin Milner, Mads Tofte, and Robert Harper. The definition o.f Standard ML. MIT Press, 1990. Google ScholarDigital Library
- RC86.Jonathan Rees and William Clinger. Revised report3 on the algorithmic language scheme. Sig. plan Notices, 21(12):37-79, December 1986. Google ScholarDigital Library
- Rom88.Sergei A. Romanenko. A compiler generator produced by a self-applicable specialiser can have a surprisingly natural and understandable structure. In Dines Bjerner, Andrei P. Ershov, and Nell D. Jones, editors, Partial Evaluation and Mixed Computation, pages 445-463, North- Holland, 1988.Google Scholar
- Sch86.David A. Schmidt. Denotational Semantics, a Methodology for Language Development. Allyn and Bacon, Boston, 1986. Google ScholarDigital Library
- Ses85.Peter Sestoft. The structure of a self-applicable partial evaluator. In Harald Ganzinger and D. Jones, editors, Programs as Data Objects, Copenhagen, Denmark. Lecture Notes in Computer Science 217, pages 236-256, Springer- Verlag, October 1985. Google ScholarDigital Library
- Tur82.David Turner. Recursion equations as a programming language. In Darlington et al., editor, Functional Programming and Its Applications., pages 1-28, Cambridge University Press, 1982.Google Scholar
- Tur86.David Turner. An overview of Miranda. Sigplan Notices, 21(12):158-166, December 1986. Google ScholarDigital Library
- Wad85.Philip Wadler. Introduction to Orwell. Technical Report, Programming Research Group, University of Oxford, 1985.Google Scholar
Index Terms
- Generating a compiler for a lazy language by partial evaluation
Recommendations
Partial Evaluation of Computation Process—AnApproach to a Compiler-Compiler
This paper reports the relationship between formal description of semantics (i.e., interpreter) of a programming language and an actual compiler. The paper also describes a method to automatically generate an actual compiler from a formal description which ...
Practical partial evaluation for high-performance dynamic language runtimes
PLDI 2017: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and ImplementationMost high-performance dynamic language virtual machines duplicate language semantics in the interpreter, compiler, and runtime system. This violates the principle to not repeat yourself. In contrast, we define languages solely by writing an ...
Realistic compilation by partial evaluation
Two key steps in the compilation of strict functional languages are the conversion of higher-order functions to data structures (closures) and the transformation to tail-recursive style. We show how to perform both steps at once by applying first-order ...
Comments