Re: The fundamental concept of continuations

[George Neuner <gneuner2/@/comcast.net>]

On Tue, 09 Oct 2007 05:15:49 -0000, gnuist006@gmail.com wrote:

>Again I am depressed to encounter a fundamentally new concept that I
>was all along unheard of. Its not even in paul graham's book where i
>learnt part of Lisp. Its in Marc Feeley's video.
>
>Can anyone explain:
>
>(1) its origin

Lambda calculus.  Continuation is just a formal term for "what the
code does next".  It manifests, literally, as the next instruction(s)
to be executed.


>(2) its syntax and semantics in emacs lisp, common lisp, scheme

Lisp does not have explicit continuations so there is no syntax for
them.  Continuations in Lisp mainly take the form of function calls,
function returns, exceptions, conditions, etc.  Sometimes code is
written in "continuation passing style" (CPS) in which each function
has one or more additional function parameters (the continuations) -
the function terminates by passing its result as an argument to one of
those continuation functions.

Scheme has explicit continuations based on closures.  Closure
continuations are created using CALL-WITH-CURRENT-CONTINUATION
(usually abbreviated as CALL/CC).  Some Schemes also recognize a
LET/CC form used mainly for escape continuations (exceptions).
Scheme's closure continuations can be stored in data structures and
used for complex control forms such as multitasking.  Like Lisp,
Scheme code also is sometimes written using CPS.


>(3) Is it present in python and java ?

It is present in all languages.  It generally takes the form of
procedure or function calls, returns, exceptions, etc.


>(4) Its implementation in assembly. for example in the manner that
>pointer fundamentally arises from indirect addressing and nothing new.
>So how do you juggle PC to do it.

As I stated above, every function call or return _is_ a continuation
... their implementation is obvious.

For the closure form used in Scheme, the implementation is to create a
closure, a data structure containing the function address and some
method of accessing the function's free variables, and to call the
function.  How you do this depends greatly on the instruction set.


>(5) how does it compare to and superior to a function or subroutine
>call. how does it differ.

Calling closure continuations is a little more complicated and a bit
slower than calling a normal function.  Creating the closure in the
first place may be simple or complicated depending on the complexity
of the source code and the processor's instruction set.


>Thanks a lot.
>
>(6) any good readable references that explain it lucidly ?

Get yourself a good textbook on compilers.  Most of the techniques are
applicable to all languages - even for seemingly very different
languages, the differences in their compilers are simply in how the
basic compilation techniques are combined.


My favorite intermediate-level books are 

Aho, Sethi & Ullman. "Compilers: Principles, Techniques and Tools".
2nd Ed. 2006. ISBN 0-321-48681-1.
The first edition from 1986, ISBN 0-201-10088-6, is also worth having
if you can still find it.  The 1st edition is mainly about procedural
languages, the 2nd gives more time to functional languages and modern
runtime issues like GC and virtual machines.

Cooper & Torczon, "Engineering a Compiler", 2004.  
ISBN 1-55860-698-X (hardcover), 1-55860-699-8 (paperback).
Also available as a restricted 90-day ebook from
http://rapidshare.com/files/24382311/155860698X.Morgan_20Kaufmann.Engineering_20a_20Compiler.pdf


There are also some decent intro books available online.  They don't
go into excruciating detail but they do cover the basics of code
shaping which is what you are interested in.

Torben Mogensen. "Basics of Compiler Design"
http://www.diku.dk/~torbenm/Basics/

"Engineering a Compiler".  I don't have this author's name, nor can
Google find it at the moment.  I have a copy though (~2MB) - if you
are interested, contact me by email and I'll send it to you.


Also Google for free CS books.  Many older books (including some
classics) that have gone out of print have been released
electronically for free download.

George
--
for email reply remove "/" from address