Implementation of Functional Languages

Literature references and annotations by Dick Grune, dick@dickgrune.com. Last update: Tue Sep 15 09:33:30 2009.
These references and annotations were originally intended for personal use and are presented here only in the hope that they may be useful to others. There is no claim to completeness or even correctness. Each annotation represents my understanding of the text at the moment I wrote the annotation.
No guarantees given; comments and content criticism welcome.

* Nadia Nedjah, Luiza de Macedo Mourelle, "Efficient concise deterministic pattern-matching automata for ambiguous patterns", ACM SIGPLAN Notices, 37, #2, Feb. 2002, pp. 57-67.
Actually pattern matching on trees, in the context of functional languages. Ambiguous patterns are disambiguated using some rules. These rules are applied when a match with multiple patterns is detected (during automaton construction), and results in the rejection of all but one of the reduce items in the recognizing state. This makes some of the items in previous states irrelevant since they can only lead to a reduce item that will be rejected. Removing these irrelevant items can simplify the automaton. Actually they are not removed; they are not generated in the first place, using a modified inference rule in the closure algorithm.

* Rémi Douence, Pascal Fradet, "A systematic study of functional language implementations", TOPLAS, 20, #2, March 1998, pp. 344-387.

* Urban Boquist, Thomas Johnsson, "The GRIN project -- A highly optimizing back end for lazy functional languages", in Implementation of Functional Languages, Lecture Notes in Computer Science #1268, ed. by Werner Kluge, Berlin, Springer-Verlag, 1996, pp. 58-84.
Exactly what the title says.

* Marcel Beemster, "Fine-grained Parallelism in a Lazy Functional Language", PhD Thesis, University of Amsterdam, Amsterdam, March 1996, pp. 195.

* Adam Webber, "Optimization of functional programs by grammar thinning", ACM TOPLAS, 17, #2, March 1995, pp. 293-330.
[ lots of interesting formal language theory and speculation ]

* Michael Hanus, "Towards the global optimization of functional logic programs", in Compiler construction: 5th International Conference, CC'94, ed. by Peter A. Fritzson, Lecture Notes in Computer Science #786, Springer-Verlag, New York, pp. 68-82. 1994,

* Andrei Mantsivoda, Vyacheslav Petukhin, "Compiling Flang", in Compiler Construction, 4th International Conference, CC'92, ed. by U. Kastens and P. Pfahler, Lecture Notes in Computer Science #641, Springer-Verlag, Oct. 1992, pp. 297-311.
[ compilation of a functional-logic language ]

* Koen Langendoen, Pieter H. Hartel, "FCG: A code generator for lazy functional languages", in Compiler Construction, 4th International Conference, CC'92, ed. by U. Kastens and P. Pfahler, Lecture Notes in Computer Science #641, Springer-Verlag, Oct. 1992, pp. 278-296.
The original FAST (Functional ArrayS on Transputers) compilation pipeline of the Univ. of Southampton comprised the following steps: a high-level functional language (f.e. Haskell) \(→ "intermediate" (a bare-bones functional language) \(→ Functional C (a simple subset of C augmented by a library for lazy evaluation etc.) \(→ machine code (courtesy of gcc). The problem with this is that all pointers turn into C data, in registers, on the stack and who knows where; they are irretrievable and no compacting garbage collector can be written.
To remedy this, the authors want to obtain a C version in which all data manipulation is explicit; more in particular, the stack should be explicit. At the same time they wish to keep as much as possible of the original pipe line in tact. This is achieved by inserting the code generator FCG between Functional and machine code.
FCG translates Functional C to KOALA, a simple graph reduction machine code similar to Johnsson's G machine. The resulting code is then translated into a single C routine, in which the "global variables" of the KOALA machine are register variables and all data manipulation is explicit. Various optimizations are applied, which are argued and discussed in detail in the paper.
The resulting code is often faster than the FAST code and always faster than the code produced by the LML native compiler.

* Mikael Pettersson, "A term pattern-match compiler inspired by finite automata theory", ed. by U. Kastens and P. Pfahler, in Compiler Construction, 4th International Conference, CC'92, Lecture Notes in Computer Science #641, Springer-Verlag, Oct. 1992, pp. 258-270.
The patterns in function definitions in functional languages are considered as very simple regular expressions (very simple in that they do not contain repetition and the only disjunction is on the top level), the tokens of which are variable, wildcard (_), and constructor. A non-deterministic automaton is constructed which matches the patterns in parallel, using the proper disambiguation rules. The automaton is then made deterministic.
Advantages over the usual case-within-case tests are: avoidance of duplicate code, easy detection of incompleteness and redundancy (unreachability). The author reports that the result was meager; this may be due to "difficult" patterns being unnecessary or to programmers avoiding them.

* David R. Tarditi, Peter Lee, Anurag Acharya, "No assembly required: compiling Standard ML to C", ACM Letters on Programming Languages and Systems, 1, #2, pp. 161-177. June 1992,
The authors took the publicly available SML/NJ and replaced the code generator by one that produces C, in order to investigste the translation of first-class functions and tail recursion elimination. In addition, SML has dynamically scoped exceptions, garbage collection and higher-order functions. One man-summer was avaialble for the work.
Basically, SML is converted to continuation-passing form, which is then flattened into C routines, but several optimizations were found necessary.
C compilers are not good enough at tail recursion elimination, so the convertor has to do the work: rather than calling its last routine L, the routine returns with the address of L as the result. It returns to a driver, which then calls the requested routine, etc. This avoids the use of the C stack, which is good for the garbage collector, since now we do not need to do a machine-dependent scan of the C stack; in fact, the depth of the C stack never exceeds two activation records: the driver and the running routine.
All SML values are kept on the heap, but for efficiency reasons some may be cached in local variables of C functions, hoping that the C compiler will place them in registers.
The translation process breaks up the program into numerous small C routines. To avoid much of the overhead involved in routine calling, routines that are dominated by other routines (all of whose calls pass through the other routines) are incorporated into those routines.
Since SML requires integer overflow checking, attempts are made to simplify the check in the cases where the value of one operand is known at compile time. Considerable simplifications turn out to be possible.
These optimizations reduced the run times by 30 to 40%, leaving a 60% gap with native SML/NJ code.

* Simon L. Peyton Jones, "Implementing lazy functional languages on stock hardware: the spineless tagless G-machine", Journal of Functional Programming, 2, #2, pp. 127-202. April 1992,

* Raymond Turner, "Constructive Foundations for Functional Languages", McGraw-Hill, London, 1991, pp. 269.
Implicitly assumes the reader to be familiar with functional programming and its terminology, and to have considerable mathematical sophistication. Yet it is never really obscure, which is quite an achievement. Heavy on the formalism, but the line of reasoning never gets buried in it. Constructivism extended to type theory. Excellent text book.

* P. Fradet, D. Le Métayer, "Compilation of functional languages by program transformation", ACM TOPLAS, 13, #1, 1991, pp. 21-51.

* L. Puel, A. Suárez, "Compiling pattern matching by term decomposition", in 1990 ACM Conference Lisp and Functional Programming, ACM, New York, 1990, pp. ??-??.

* M. Petterson, "Generating efficient code from continuation semantics", in Compiler Compilers, Third International Workshop CC '90, ed. by D. Hammer, Lecture Notes in Computer Science #477, Schwerin, Springer-Verlag, Oct. 1990, pp. 165-178.

* Katsuro Inoue, Hiroyuki Seki, Hikaru Yagi, "Analysis of functional programs to detect run-time garbage cells", ACM TOPLAS, 10, #4, Oct. 1988, pp. 555-578.

* Simon L. Peyton Jones, "The Implementation of Functional Languages", Prentice-Hall, New York, 1987, pp. 445.

* P. Wadler, "Efficient compilation of pattern matching", in The Implementation of Functional Languages, ed. by Simon L. Peyton Jones, Prentice-Hall, New York, 1987, pp. ???-???.

* D. Lester, "The G-machine as a representation of stack semantics", in Functional Programming Languages and Computer Architecture, ed. by G. Kahn, Lecture Notes in Compter Science #274, Springer-Verlag, Berlin, pp. 46-59. 1987,

* J. Fairbairn, S.C. Wray, "TIM. A simple, lazy abstract machine to execute supercombinators", in Functional Programming Languages and Computer Architecture, ed. by G. Kahn, Lecture Notes in Compter Science #274, Springer-Verlag, Berlin, pp. 34-45. 1987,

* Marc Feeley, Guy Lapalme, "Using closures for code generation", Computer Languages, 12, #1, 1987, pp. 47-66.
Closures as intermediate code in functional languages. Lambda lifting is done by introducing environment pointers. Sample translations for some syntactic structures are given. Code is compiled that does interpretation on these closures. As a result, many interpretation facilities are still available.

* J. Fairbairn, S.C. Wray, "Code generation techniques for functional languages", in 1986 ACM Conference on LISP and Functional Programming, ACM Press, pp. 94-104. 1986,

* J. Hughes, "Lazy memo-functions", ed. by J.P. Jouannand, in Functional programming languages and computer architectures, Lect. Notes Comput. Sci., #201, Berlin, Springer, pp. ???-???. 1985,

* W. Dosch, B. Moeller, "Busy and lazy FP with infinite objects", in 1984 ACM Symposium on LISP and Functional Programming, 1984, pp. 282-292.

* Luca Cardelli, "Compiling a functional language", in 1984 ACM Symposium on Lisp and Functional Programming, ACM, New York, 1984, pp. 208-217(226?).
[[ preliminary abstract ]] Very readable and clear account of the entire trajectory of writing a compiler for ML for the VAX.

* P.A. Subrahmanyam, J.-H. You, "Pattern driven lazy reduction -- A unifying evaluation mechanism for functional and logical programs", in Eleventh ACM Symposium Principles of Programming Languages, 1984, pp. 228-234.

* P. Hudak, D. Kranz, "A combinator-based compiler for a functional language", in Eleventh ACM Symposium on Principles of Programming Languages, ACM, New York, 1984, pp. 122-132.

* F.W. Burton, "Annotations to control parallelism and reduction order in the distributed evaluation of functional programs", ACM Trans. Program. Lang. Syst., ??, #1, pp. 159-174. Jan. 1984,

* R. Cartwright, J. Donahue, "The semantics of lazy (and industrious) evaluation", in 1982 ACM Symposium LISP and Functional Programming, 1982, pp. 253-264.

* J. Hughes, "Super combinators -- A new implementation method for applicative languages", in 1982 ACM Conference Lisp and Functional Programming, ACM, New York, 1982, pp. ???.

* D.A. Turner, "A new implementation technique for applicative languages", Software -- Practice and Experience, 9, #1, pp. 31-49. Jan. 1979,

* P.J. Landin, "The mechanical evaluation of expressions", Computer J., 6, #4, pp. 308-320. April 1964,
Invents functional programming and its implementation, including closures.