Generating a compiler for a lazy language by partial evaluation

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.

REFERENCES

• BD91: 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]
• Bon90: A. Bondorf, Automatic autoprojection of higher order recursive equations, Proceedings of the third European symposium on programming on ESOP '90, p.70-87, May 1990, Copenhagen, Denmark
• Bon91a: Anders Bondorf. Compiling laziness by partial evaluation. In {JHH91}, pages 9-22, 1991.
• Bon91b: Anders Bondorf. Similix manual, system version 4.0. Included in Similix distribution, September 1991.
• Bon92: Anders Bondorf. Improving binding times without explicit cps-conversion. 1992. Forthcoming.
• BW88: Richard Bird , Philip Wadler, An introduction to functional programming, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1988
• CD89: 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]
• Con88: 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
• Dan91: 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]
• 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.
• HG91: Carsten Kehler Holst , Darsten Krogh Gomard, Partial evaluation is fuller laziness, ACM SIGPLAN Notices, v.26 n.9, p.223-233, Sept. 1991
• HH91: Carsten Kehler Hoist and John Hughes. Towards binding-time improvement for free. In {JHH91}, pages 83-100, 1991.
• HW90: Paul Hudak and Philip Wadler. Report on the programming language Haskell. Technical Report, Yale University and Glasgow University, April 1990.
• JHH91: Simon L. Peyton Jones, Graham Hutton, and Carsten Kehler Holst, editors. Functional Programming, Glasgow 1990. Workshops in Computing, Springer-Verlag, August 1991.
• Joh75: S.C. Johnson. YACC: Yet another compiler compiler. Technical Report 32, Bell laboratories, Murray Hill, New Jersey, 1975.
• Jor91a: Jesper Jergensen. Compiler Generation by Partial Evaluation. Master's thesis, DIKU, University of Copenhagen, Denmark, student report, October 1991. Forthcoming.
• Jor91b: Jesper Jergensen. Generating a pattern matching compiler by partial evaluation. In {JHH91}, pages 177-195, 1991.
• JSS85: 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
• 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.
• MTH90: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• RC86: J Rees , W Clinger, Revised report on the algorithmic language scheme, ACM SIGPLAN Notices, v.21 n.12, p.37-79, Dec. 1986 [doi>10.1145/15042.15043]
• 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.
• Sch86: David A. Schmidt, Denotational semantics: a methodology for language development, William C. Brown Publishers, Dubuque, IA, 1986
• Ses85: Peter. Sestoft, The structure of a self-applicable partial evaluator, on Programs as data objects, p.257-281, April 1986, Copenhagen, Denmark
• 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.
• Tur86: D Turner, An overview of Miranda, ACM SIGPLAN Notices, v.21 n.12, p.158-166, Dec. 1986 [doi>10.1145/15042.15053]
• Wad85: Philip Wadler. Introduction to Orwell. Technical Report, Programming Research Group, University of Oxford, 1985.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics; Syntax
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

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

General Terms:
Algorithms, Languages

Keywords:
binding time improvements, compiler generation, lazy functional languages, partial evaluation