Compiling a functional language

ABSTRACT

This paper summarizes my experience in implementing a compiler for a functional language. The language is ML(1) [Milner 84] and the compiler was first implemented in 1980 as a personal project when I was a postgraduate student at the University of Edinburgh(2). At the time, I was familiar with programming language semantics but knew very little about compiler technology; interpreters had been my main programming concern. Major influences in the design of this compiler have been [Steele 77] [Steele 78] and the implementation folklore for statically and dynamically scoped dialects of Lisp [Allen 78]. As a result, the internal structure of the compiler is fairly unorthodox, if compared for example with [Aho 78]. Anyway, a compiler for a language like ML has to be different. ML is interactive, statically scoped, strongly typed, polymorphic, and has first class higher-order functions, type inference and dynamic allocation. These features preclude many well-known implementation styles, particularly the ones used for Lisp (because of static scoping), the Algol family (because of functional values) and C (because of nested scoping and strong typing). The interaction of these features is what gives ML its “character”, and makes compilation challenging. The compiler has been recently partially converted to the new ML standard. The major points of interest which are discussed in this paper are: (a) the interactive interpreter-like usage; (b) the polymorphic type inference algorithm; (c) the compilation of pattern matching; (d) the optimization of the representation of user defined data types; (e) the compilation of functional closures, function application and variable access; (f) the intermediate abstract machine and its formal operational semantics; (g) modules and type-safe separate compilation.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: John Allen, Anatomy of LISP, McGraw-Hill, Inc., New York, NY, 1978
• 3: R. M. Burstall , D. B. MacQueen , D. T. Sannella, HOPE: An experimental applicative language, Proceedings of the 1980 ACM conference on LISP and functional programming, p.136-143, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802799]
• 4: L.Cardelli. "The Functional Abstract Machine", Bell Labs Technical Report TR-107, 1983.
• 5: M.Gordon, R.Milner, C.Wadsworth, "Edinburgh LCF", Lecture Notes in Computer Science, No. 78, Springer-Verlag, 1979.
• 6: Peter Henderson, Functional Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1980
• 7: Robert Kowalski, Logic for problem-solving, North-Holland Publishing Co., Amsterdam, The Netherlands, 1986
• 8: P.J.Landin: "The Mechanical Evaluation of Expressions", Computer J., Vol. 6, No. 4, 1964, pp. 308-320.
• 9: D.B.MacQueen: "Modules for Standard ML", this conference.
• 10: R.Milner: "A theory of type polymorphism in programming", Journal of Computer and System Science 17, pp. 348-375, 1978.
• 11: R.Milner: "A proposal for Standard ML" Internal Report CSR-157-83, Dept of Computer Science, University of Edinburgh.
• 12: G.D.Plotkin: "A Structural Approach to Operational Semantics", Internal Report DAIMI FN-19, Computer Science Dept, Aarhus University, 1981.
• 13: J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
• 14: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 15: Guy Lewis Steele, Jr., Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO, Proceedings of the 1977 annual conference, p.153-162, January 1977 [doi>10.1145/800179.810196]
• 16: Niklaus Wirth, Programming in MODULA-2 (3rd corrected ed.), Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: ML

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

General Terms:
Languages