A standard ML compiler

Authors: Andrew W Appel David B MacQueen

Publish Date: 1987/9/14

Volume: , Issue: , Pages: 301-324

PDF Link

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 MLGreat attention was paid to modularity in the construction of the compiler leading to a successful largescale 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 structuresThe 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 lambdacalculusbased 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 collectionWe 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

Keywords: