Re: Demystifying continuations

[Guy Steele - Sun Microsystems Labs <address@hidden>]

   To: Kevin Kelleher <KevinKelleher@usa.net>
   Cc: ll1-discuss@ai.mit.edu
   Subject: Re: Demystifying continuations
   From: gregs@ai.mit.edu (Gregory T. Sullivan)
   Date: 22 Mar 2002 13:08:18 -0500
   User-Agent: Gnus/5.0803 (Gnus v5.8.3) Emacs/20.7
   
   >>>>> ":Kevin" == :Kevin Kelleher <KevinKelleher@usa.net> writes:
   	
    :Kevin> It's quite readable.  I think that now I have a crude
    :Kevin> idea of what continuations are - a continuation is
    :Kevin> a "goto with parameters":  as opposed to a function
    :Kevin> that returns to its caller, a continuation passes
    :Kevin> control to some other function.  It's possible to
    :Kevin> have a programming language in which every function
    :Kevin> ends in a continuation.
   
   You may be confusing continuations with "tail calls".
   
   A tail call can be described as a "goto with parameters" but I really
   don't think that's a good description of continuations.  There have
   already been some nice descriptions of continuations on this thread,
   so I won't add my version.  

In fact, *every* function call can be described as a "goto with
parameters".  "Returning" is not a property of a function call
per se, but of the context in which it occurs.  (That context,
by the way, is pretty much what we mean by a "continuation".)

  define foo(a) = (a==3) ? 1 : bar(a)

  define quux(a) = (a==3) ? 1 : bar(a)+1

  define bar(a) = (a==4) ? 43 : sqrt(a)
  
Both function foo and function quux call function bar.
These calls may be carried out using *identical*
mechanisms: each performs a "goto" to the code for bar,
handing it two things: the argument "a" and an indication
of what to do after the code for bar has been executed.
This latter indication is the continuation.  We often think
of it an being encoded by a stack that contains, among other
things, what we call a "return address" but would be better
called a "next address" or "continuation address".

It so happens that quux calls bar in a context where quux
requires more work to be done after that call to bar, namely
an addition to the constant 1.  So quux passes bar a continuation
that says, roughly, "add 1 to the value from bar and then give
that to the continuation originally given to quux".  To make this
new continuation in a stack-based implementation, pretty much
all quux has to do is push a new continuation address onto the
stack; this address is the address of a code sequence that performs
the addition by 1 (and then passes control to its continuation,
which will be the continuation originally given to quux).

Many computers have a convenient compound instruction that optimizes the
performance of the two-instruction sequence "build a new continuation
by pushing a new continuation address onto the stack" and "jump to bar";
we call this compound instruction "call" or "pushj" or "jsp" or "gosub".
(The terrible thing is that we regard the call instruction as a
primitive and a tail-call as a hack, when it is much more fruitful to
regard the tail-call (a goto) as primitive and the call instruction as
an optimization.  Why?  Because the latter theory consumes less
stack space.)

Many computers also have a single instruction that takes a compound
continuation A, represented as a stack containing a continuation
address C and a substack B, and in a single operation replaces
A with B and transfers control to C.  We call this instruction
"return" or "popj" or "ret".

On the other hand, foo calls bar in a context where quux requires
no further work.  Therefore the continuation to be passed to bar
is identical; to that which was given to foo.  So no new continuation
needs to be built before calling bar.  So the call to bar consists
merely of setting up the argument "a" and then "jump to bar".
This is what is often called a "tail call"; I call it a normal
call for which no new continuation was constructed.

By the way, the fact that functions "return a value" in any given
language also is not a characteristic of the function call mechanism
as such but of the continuations and the primitive operations that
invoke them.  The function bar is able to return a value only
because it receives a continuation that accepts a value, and because
bar uses a primitive ("43") whose behavior may be defined as passing
a specific constant value to whatever continuation it is given---that is,
a literal constant "produces a value".  But one can define other
programming languages in which most (or all) continuations do not
accept values.  In a statement-oriented language such as C, for
example, continuations for expressions accept values but those
for statements do not.

See, for example,

  Steele, Guy Lewis Jr.  "Debunking the `Expensive Procedure Call'
  Myth; or, Procedure Call Implementations Considered Harmful; or,
  LAMBDA: The Ultimate GOTO."  Proc. ACM National Conference
  (Seattle, October 1977), 153-162.  Revised as MIT AI Memo 443
  (Cambridge, Massachusetts, October 1977).

  Steele, Guy Lewis Jr.  "LAMBDA: The Ultimate Declarative."  AI
  Memo 379.  MIT AI Lab (Cambridge, November 1976).

--Guy Steele