Compilers in functional languages (summary)

Firstly, thanks to all those who replied to my request for information
about compilers written in functional languages. Appended is a slightly
editted summary of the replies I received - I'm now busily tracking all
the references down!


I'm not sure that I can draw a consensus from it all yet. The available
work seems to cover all the usual compiler topics (with the possible
exception of optimisation?). I suppose I'll just spend the next month or
so reading :-)


For background, my interest comes from a need to prototype compilers for
new, experimental languages. I decided to write an Occam compiler for
several reasons: we use it for teaching and needed a very portable
compiler; the language is so simple that it illustrates the concepts
involved in functional compilers without getting stuck in details; and it
was handy to simulate a parallel language on sequential kit, as parallel
languages are what I do for a living. The system I've come up with is a
combined compiler/interpreter for Occam. It generates an AST and then
either interprets it directly or compiles it down to ML: running this
through the ML compiler then generates a stand-alone binary. (Yeah, I
know that's a bit of a cheat, but it saves time hacking a code generator
and improves portability no end when you're using a highly portable ML -
Caml Light in my case. I'd eventually like to look at (partial)
continuation-passing style in code generation, but it depends how much
time I can devote to it.)


Several people expressed an interest in this work, and I'll let them (and
anyone else who's interested) know when it's finished.


Thanks again,




-- Si


Dr Simon A. Dobson


Informatics Department
SERC Rutherford Appleton Laboratory
Chilton, Didcot, Oxon OX11 0QX, UK.


(+44 235) 445478 sd@inf.rl.ac.uk


===== replies start here =====


>From wand@edu.northeastern.ccs Thu May 27 22:14:37 1993


@Article{Wand82c,
    author = "Wand, Mitchell",
    title = "Deriving Target Code as a Representation of
Continuation Semantics",
    journal = "ACM Transactions on Programming Languages and Systems",
    year = "1982",
    volume = "4",
    number = "3",
    pages = "496--517",
    month = jul,
}


@Article{Wand83b,
    author = "Wand, Mitchell",
    title = "Loops in Combinator-Based Compilers",
    journal = "Information ~and Control",
    year = "1983",
    volume = "57",
    number = "2--3",
    pages = "148--164",
    month = "May/June",
}


@InProceedings{WandOliva92,
    author = "Mitchell Wand and Dino P. Oliva",
    title = "Proving the Correctness of Storage Representations",
    booktitle = "Proc. ACM Conf. on Lisp and Functional Programming"
    year = "1992",
    pages = "151--160",
}


Also you should look at the VLisp papers in the Scheme archive at
nexus.yorku.ca , and at


@Book{FriedmanEtAl92,
    author = "Friedman, Daniel P. and Wand, Mitchell and Haynes,
    Christopher T.",
    title = "Essentials of Programming Languages",
    publisher = "MIT Press",
    address = "Cambridge, MA",
    year = "1992",
    note = "Also McGraw-Hill, Chicago, 1992",
}


--Mitch


Mitchell Wand
College of Computer Science, Northeastern University
360 Huntington Avenue #161CN, Boston, MA 02115 Phone: (617) 437 2072
Internet: wand@ccs.neu.edu Fax: (617) 437 5121


=========================


>From edward@uk.ac.york.minster Thu May 27 23:30:17 1993


Dear Dr Simon A. Dobson,


Why stick to just functional languages. Write it in Prolog. It's
more suited.


- edward
-------------------------------------------------------
Postgraduate Student Edward Walker
Advanced Computer Architecture Group
University of York
York, Heslington
YO1 5DD
U.K.


Internet: edward@minster.york.ac.uk


==========================


>From joe@se.ericsson.erix Fri May 28 11:09:33 1993


Hi,
We have used Erlang (a new functional language)
for writing a number of compilers (mostly for Erlang itself :-)).
Some of the more interesting compilers were:


1) A cross compiler from ASN.1 to Erlang and
2) A cross compiler from SDL to Erlang
3) A compiler from Erlang to C


While the target languages were C and Erlang they could equally
well have been any other langauge -- most of the work is done in parsing
and manipulation of abstract data types representing the various phases of
the compilation.


These compilers made heavy use of yecc (Which is an Erlang version of
Yacc) -- this takes a Yaccish grammar and produces an Erlang parser which
parses the source producing an Erlang representation of the program.


Transforming (compiling) this is relativly simple. No nasty
pointers, memory allocation etc. to worry about. The compiler itself being
an easy to read set of patterns which match various intermediate structures.
Doing the same thing in C would be a real mess. The ASN.1 compiler was
probably 10-20 times shorter than a C version of the same thing (this is
just an educated guess, but probably not unrealistic).


Aside: The ASN.1 compiler is used in *real* applications and has
saved many man-years of work!


Joe


=========================


>From Ignacio.Trejos-Zelaya@uk.ac.oxford.prg Fri May 28 12:19:41 1993


Hello,


I understand that Standard ML of New Jersey is written in a mostly-
functional style (using SML/NJ). The Glasgow Haskell compiler is
written in Haskell. The Chalmers Haskell compiler and the LML compiler
are written in Lazy ML. I understand the sources of all of these are
available.




Bernard Sufrin, of the PRG, has developed a nice set of lecture
notes in which he illustrates compiling/interpreting for a variety
of languages (including abstract machines): simple imperative
languages (algolesque), lazy and eager functional languages, and I
think he has an occam compiler/interpreter somewhere. His code is
written mostly in Standard ML (of NJ), and he has several examples in
a Miranda-like language.


Andrew Appel has written a book, "Compiling with continuations" (Cambridge
U. Press) in which he shows the approach taken in the SML/NJ compiler.


I hope this helps,


Ignacio


=========================


>From sspande@edu.ncsu.eos Fri May 28 22:17:13 1993


Hi,


Your idea is very interesting. In fact, since
the functional language implementation has reached a good level of efficiency
in terms of execution speed etc., its use for compiler writing may be a quick
way to generate a robust, bug free code that is efficient too.


Have you considered Sisal? Sisal has also been implemented on a variety of
parallel architectures (Cray, Convex, Sequent etc.) that might make the
compiler implementation using
Sisal quite interesting. For more information on Sisal project, please
contact John Feo at : feo@diego.llnl.gov


Santosh


=========================


>From johnr@ee.uts.edu.au Mon May 31 06:25:13 1993


Hi


I'm writing parts of an optimizing compiler for a simple (strict)
FL in Haskell. The compiler will generate assembler for a
special-purpose number-crunching chip.


I haven't been doing this for long, but
so far, I've found that i) attribute grammars are an
excellent way of describing complicated optimizations, which
can be translated directly into a lazy FL like Haskell. These
work best for things like expression simplification
optimizations, beta-expansion, stuff like that.


ii) The back end (once I get down to the machine instruction level)
is easier to do with a graph representation of the program.
Things like instruction parallelisation (supported by this
particular family of chips) are much easier than with
attribute grammars. Graphs are not difficult in Haskell,
but less efficient (I assume) than with say SML. [Which
reminds me, I'm supposed to post a summary of graph-related
papers to the net....]


See "Attribute Grammars as a Functional Programming Paradigm"
by Johnsson in FPCA 85 (or was it 87?). "The Art of Compiler
Design" by Pittman (author not publisher)
has a lot of basic attribute grammars for standard optimisations.


Hope this helps


John Reekie


=========================


>From ad@cs.st-andrews.ac.uk Mon May 31 16:35:34 1993


I don't know if you know of the 'Glorious Glasgow Haskell Compiler' which
is written in Haskell and makes extensive use of a programming abstraction
called monads. They know a great deal about compilers written in functional
languages there.


In addition here's a bibliography:


A.W. Appel, Compile-Time Evaluation and Code Generation for semantics
Directed Compilers, Carnegie Mellon University Technical Report
CMU--CS--85--147


A.W. Appel, D.B. MacQueen, A Standard ML Compiler, LNCS 274 p301-324. Proc
1987 FPCA, The authors describe the first compiler written for Standard ML
in
Standard ML


C. Hall, K. Hammond, W. Partain, S.l. Peyton Jones, P. Wadler, The Glasgow
Haskell Compiler: A Retrospective, In J. Launchbury, P.M. Sansom, eds.,
Functional Programming Glasgow 1992, Springer Verlag, Workshop, Ayr


G. Hutton, Higher-Order Functions for Parsing, JFP 2,3, pp323-343 - also
published as a Chalmers technical report.


G. Hutton, Parsing Using Combinators, In K. Davis, J. Hughes, Eds,
Functional Programming, Glasgow 1989, Springer Verlag 0-387-19609-9, 1989,
pp353-370


R. Leermakers, L. Augusteijn, F. Aretz, A functional LR-parser, Theoretical
Computer Science 104, pp313-323


M. Mauny, D. de Rauglaudre, Parsers in ML, In Proc.1992 ACM Conference on
LISP and Functional Programming, ISBN 0-89791-481-3, ACM Order No. 552920,
pp76-85


I.W. Moor, An Applicative Compiler for a Parallel Machine, SIGPLAN 17,6 1982


S.L. Peyton Jones, C. Hall, K. Hammond, W. Partain, The Glasgow Haskell
Compiler: A Technical Overview, Proc. UK Joint Framework for Information
Technology (JFIT) Technical Conference, Keele, 1993, also available from
ftp.dcs.glasgow.ac.uk


D.A. Turner, Some Notes on the SASL Compiler in SASL, Report for Burroughs
Corp., Austin, 1980


G.O. Uddeborg, A Functional Parser Generator, Report 43, Programming
Methodology Group Department of Computer Science, Chalmers University of
Technology and University of Goteborg


P.L. Wadler, How to Replace Failure by a List of Successes, A Method for
Exception Handling, Backtracking and Pattern matching in Lazy Functional
Languages - FPCA'85, Nancy, LNCS 201, pp113-128. This paper presents a
method whereby some programs, that use features such as exception handling,
backtracking and pattern matching, can be rewritten in a functional
language with lazy evaluation, without the use of any special features.


M. Wand, Essentials of Programming Languages, ? Date ?, Ch 11 is said to
have a functional parser


Hope these help




Tony Davie Department of Mathematical and Computational Sciences
Tel: +44 334 63257 St.Andrews University
Fax: +44 334 63278 North Haugh
ad@dcs.st-andrews.ac.uk St.Andrews
                                                  Scotland
                                                  KY16 9SS


=========================


>From rwatson@au.edu.une.alsvid Tue Jun 1 04:43:50 1993


You might look at


@article{Hutton92,
keywords={FP,parsing,combinator parsing},
author={Graham Hutton},
title={Higher-order functions for parsing},
journal=jfp,
volume=2,
number=3,
pages={323-343},
month=jul,
year=1992
}


Another paper I have seen referenced but not read myself is:


Leermaker et at, A functional LR parser, Theoretical Computer Science
v104, pp313-323


=========================


>From keithc@uk.ac.qmw.dcs Tue Jun 1 17:29:13 1993


I've implemented some compiler-compiler tools using SML - scanner, parser,
AST implementation, pretty-printer generators. The idea is to "compile"
the grammar into SML modules, rather than to build table-driven
interpreters for it. The parsers are modified recursive descent, extended
to handle operator precedence, & I'm working on hooks so nasty kludges can
be inserted as glue between modules, rather than by editing automatically
generated SML. The scanners and parsers are imperative ML, though, so
they may not be up your street... The ASTs are ML datatypes, & the pretty
printer is declarative. I have tools for generating (declarative, simple)
code generators from pattern-matching specifications; there's an example
of the sort of spec I can translate in a paper of mine in Software
Practice & Experience, 1989.


I could send a preliminary report (a Word document) on the tools. I'm
also writing an undergraduate text that deals with C, Pascal etc
compilation using ML as the meta-language.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.