A combinator-based compiler for a functional language

Authors:

Paul Hudak and David Kranz

Abstract:

The goal of our research has been to demonstrate that a functional language with the full semantic power of lazy evaluation can be implemented efficiently with an appropriate optimizing compiler.  Furthermore, we wish to show that combinators offer a convenient intermediate language with which to perform program transformations and optimizations.  Through the use of combinators, traditional optimizations such as constant-folding and global common-subexpresssion elimination become trivial, and we are able to eliminate other sources of inefficiency that conventional compilers do not typically deal with.  In particular, all procedure boundaries are eliminated from a program, leaving a single combinator expression that can be manipulated at will.  One implication of this is that there is almost no penalty to the programmer for building modular, hierarchical programs that agree with "good design practice".  Data may be "packaged" into lists for passing between procedures, with no run-time overhead.  Once the single combinator expression is created, our compiler creates its own "optimized" procedures that do not necessarily correspond to those defined in the source program.

Bibtex:

 @InProceedings{huda84a
    ,key={hudak}
    ,author={Hudak, P. and Kranz, D.}
    ,title={A combinator-based compiler for a functional language}
    ,booktitle={11th ACM Symposium on Principles of Programming Languages}
    ,organization={ACM}
    ,year=1984
    ,month=Jan
    ,pages={121-132}
    } 

Links:

CombComp-POPL84.pdf