Compiling with Continuations

At the risk of being repetitious, let me remind people that
continuation-based compiling does NOT imply heap-based allocation. It is
perfectly fine to do continuation-based compiling and still do analysis to
put whatever you can on a stack.


In particular, in the absence of call/cc and the like, continuations
(activation records) can ALWAYS be stack-allocated. Heap allocation is
only necessary for environments (closures), even if your compiler is
arbitrarily stupid.


With slightly more effort, you can do an escape or closure analysis to
determine when a closure has dynamic extent, so you can allocate it on the
stack. Steele's RABBIT compiler (ca 1977) and Kranz et al's ORBIT
compiler (ca 1986) both do this.


Like most good ideas, continuation-based compiling can be bent in various
directions, depending on the rest of one's agenda. The RABBIT/T thread
represents one such direction; Appel's development represents another
(I'll also plug Kelsey's thesis-- it has some technical similarities to
Appel's approach, but it also uses a stack, I believe). As a theoretician
(relatively speaking), I find continuation-based compiling very attractive
because it allows the best, easiest correctness proofs around.


This has been said before on this list, but some people seem to have
missed the point.


Here's a short(?) reading list:


\ref{Steele 78} Steele, G.L. ``Rabbit: A Compiler for Scheme,'' MIT AI TR
No.~474 (May, 1978).


\ref{Wand 82b} Wand, M. ``Semantics-Directed Machine Architecture''
{\it Conf. Rec. 9th ACM Symp. on Principles of Prog. Lang.} (1982), 234--241.


\ref{Wand 82c} Wand, M. ``Deriving Target Code as a Representation of
Continuation Semantics'' {\it ACM Trans. on Prog. Lang. and Systems 4}, 3
(July, 1982) 496--517.


\ref{Wand 83} Wand, M. ``Loops in Combinator-Based Compilers,'' {\it Conf.
Rec. 10th ACM Symposium on Principles of Programming Languages} (1983),
190--196.


\ref{Wand 83} Wand, M. ``Loops in Combinator-Based Compilers,'' {\it Info.
and Control 57}, 2--3 (May/June, 1983), 148--164.


\ref{Clinger 84} Clinger, W. ``The Scheme 311 Compiler: An Exercise in
Denotational Semantics,'' {\it Conf. Rec. 1984 ACM Symposium on Lisp and
Functional Programming} (August, 1984), 356--364.


\ref{Kranz {\it {et al.}\/} 86} Kranz, D.A., Kelsey, R., Rees, J.A., Hudak,
P., Philbin, J., and Adams, N.I., ``Orbit: An Optimizing Compiler for
Scheme,'' {\it Proc. SIGPLAN '86 Symp. on Compiler Construction}, {\it
{SIGPLAN Notices 21}\/}(7), July, 1986, 219-223.


\ref{Kelsey \&\ Hudak 89} Kelsey, R., and Hudak, P. ``Realistic Compilation
by Program Transformation,'' {\it {Conf. Rec. 16th Ann. ACM Symp. on
Principles of Programming Languages}\/} (1989), 281--292.


\ref{Appel \&\ Jim 89} Appel, A.W., and Jim, T., ``Continuation-Passing,
Closure-Passing Style,'' {\it {Conf. Rec. 16th ACM Symp. on Principles of
Programming Languages}\/} (1989), 293--302.


\bibitem{Wand-MFPS} Wand, M. ``On the Correctness of Procedure Representations
in Higher-Order Assembly Language'' {\it {Proc. MFPS '91}\/} (S. Brookes,
ed.) Springer Lecture Notes in Computer Science, to appear.


--Mitch


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

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