A standard ML compiler

Andrew W. Appel, David B. MacQueen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

43 Scopus citations

Abstract

Standard ML is a major revision of earlier dialects of the functional language ML. We describe the first compiler written for Standard ML in Standard ML. The compiler incorporates a number of novel features and techniques, and is probably the largest system written to date in Standard ML. Great attention was paid to modularity in the construction of the compiler, leading to a successful large-scale test of the modular capabilities of Standard ML. The front end is useful for purposes other than compilation, and the back end is easily retargetable (we have code generators for the VAX and MC68020). The module facilities of Standard ML were taken into account early in the design of the compiler, and they particularly influenced the environment management component of the front end. For example, the symbol table structure is designed for fast access to opened structures. The front end of the compiler is a single phase that integrates parsing, environment management, and type checking. The middle end uses a sophisticated decision tree scheme to produce efficient pattern matching code for functions and case expressions. The abstract syntax produced by the front end is translated into a simple lambda-calculus-based intermediate representation that lends itself to easy case analysis and optimization in the code generator. Special care was taken in designing the runtime data structures for fast allocation and garbage collection. We describe the overall organization of the compiler and present some of the data representations and algorithms used in its various phases. We conclude with some lessons learned about the ML language itself and about compilers for modern functional languages.

Original languageEnglish (US)
Title of host publicationFunctional Programming Languages and Computer Architecture, Proceedings
EditorsGilles Kahn
PublisherSpringer Verlag
Pages301-324
Number of pages24
ISBN (Print)9783540183174
DOIs
StatePublished - Jan 1 1987
Event3rd International Conference on Functional Programming Languages and Computer Architecture, 1987 - Portland, United States
Duration: Sep 14 1987Sep 16 1987

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume274 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd International Conference on Functional Programming Languages and Computer Architecture, 1987
CountryUnited States
CityPortland
Period9/14/879/16/87

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A standard ML compiler'. Together they form a unique fingerprint.

  • Cite this

    Appel, A. W., & MacQueen, D. B. (1987). A standard ML compiler. In G. Kahn (Ed.), Functional Programming Languages and Computer Architecture, Proceedings (pp. 301-324). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 274 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-18317-5_17