Re: Compiling with Continuations/Andrew Appel

In article 92-01-101, eifrig@blaze.cs.jhu.edu (Jonathan Eifrig) writes:
> In article 92-01-091 nick@dcs.edinburgh.ac.uk writes:


>>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".


This doesn't mean that CPS doesn't do a perfectly good job for languages
without, say, higher-order functions. Appel believes in sticking
everything on the heap and not using the stack at all; but other people
using CPS don't agree with him on that, and manage to do a quite good job
of figuring out when it isn't necessary to move functions' activation
records onto the heap. In particular, they manage to detect all of the
cases that would show up when compiling, say, C or Pascal. In his
dissertation _Compilation by Program Transformation_, Richard Kelsey
describes part of a CPS compiler for a Scheme variant called T that he
worked on. Front ends were written not only for T but for Pascal and for
that most noble of languages, BASIC, and at the end he compares benchmarks
for their Pascal compiler vs. the Apollo Pascal compiler; theirs is faster
on some, Apollo's is faster on some, but the differences are all within a
ration of 3:2.


> 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.


I won't argue with you here. The book has a lot of neat stuff, I'm glad
to see it, and I'm glad to see CPS finally get an airing in a book after
15 years of being hidden away in tech reports and such, known about to the
Scheme community but not to the compiler community at large. But from the
admittedly cursory at times look that I had at it it's too specific to be
called a "modern compiler text." A book about a modern compiler, rather.


david carlton
carlton@husc.harvard.edu
--

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