Re: Compiling with Continuations/Andrew Appel

In article 92-01-091 nick@dcs.edinburgh.ac.uk writes:
> Compiling with Continuations
> Andrew Appel
> Cambridge University Press 1992
> ISBN 0-521-41695-7


This is indeed a good book, but perhaps not for the reasons you
suggest. It provides an invaluable explaination of the compilation method
currently being used for a non-imperative language, ML, in the Standard
ML/New Jersey compiler (available via ftp from "research.att.com" and
"princeton.edu".) In particular, it demonstrates the (somewhat) surprising
fact: the notion of a "continuation", originally introduced to give a
denotational semantics to imperative-style languages, can be used as a
foundation of a compiler. Thus, there actually _is_ some practical use of
denotational semantics! (Cynics in the programming languages community, like
myself, have often wondered if there were a practical use of anything we did.
Now we know!)


However:


>The book is written with reference to Standard ML, and is in that culture
>(strong typing, garbage collection, higher-order functions) but I see no
>reason why the technology shouldn't have much wider applicability, as the
>sleeve notes (above) suggest.


There are good reasons why the methods described may not be a good
model of compilation for all languages. The continuation-style method
basically converts the source language into executable code for a machine
model _with_a_heap_. While this is OK if the language you are compiling will
need a heap anyways (such as Lisp or ML, or any other language where
functions are first-class objects), it may not be appropriate for simpler
languages, like C or Algol, for which a simple run-time stack is sufficient.
Indeed, higher-order functions come almost for free using a continuation-
passing-style of compilation, along with such interesting control notions as
"callcc".


In addition, the run-time system used in Appel's book relies heavily
on a (fairly) unique feature of ML; namely, the immutability of (almost all)
heap-allocated records. A more general garbage-collector would be necessary
for a more assignment-oriented language.


>It doesn't cover parsing, and only mentions typechecking where it's relevant
>to code generation. I don't consider the former any great loss; we've known
>how to write parsers for decades, and I'm getting sick of compiler books
>which spend six chapters going over it all again.


Well, parsing _is_ an important part of compilation. And, as anyone
who has ever tried to write a parser for a non-trivial language knows, it is
certainly not the plug-and-chug task one first suspects, as witnessed by the
lack of a PD COBOL parser, despite the number of requests for one here.
However, I would agree that, in general, parsing is a well-understood
problem and theoretically uninteresting when compared to other aspects of
compilation. But hey, one can only write a book about solved problems!


>This book looks very interesting. Apart from anything else, it's a very
>welcome change from things like the dreadful Dragon book and its
>contemporaries which are steeped in 1970's UNIX culture and grub around with
>lexical analysers, regular expressions, YACC, LEX, C, and so on. There are
>very few *modern* compiler texts around, but this is certainly one of them.


Well, I would partially agree with your claim that Appel's book is
indeed a change from the Dragon book, but I would hesitate to claim that it
is a "modern compiler text." Rather, I would say it is more like an extended
tech. note on the SML/NJ compiler, and a good view of how continuations might
be useful in your current compilation project.


  - Jack Eifrig (eifrig@cs.jhu.edu) - The Johns Hopkins University
--

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