The fundamental concept of continuations

[gnuist006]

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
(2) its syntax and semantics in emacs lisp, common lisp, scheme
(3) Is it present in python and java ?
(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.
(5) how does it compare to and superior to a function or subroutine
call. how does it differ.

Thanks a lot.

(6) any good readable references that explain it lucidly ?

 

[Barb Knox]

Again I am depressed to encounter a fundamentally new concept that I
was all along unheard of.

Don't be depressed about that. There are countless concepts out there
they you haven't yet heard 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. Instead of function A returning to its caller, the
caller provides an additional argument (the "continuation") which is a
function B to be called by A with A's result(s). In pure "continuation
style" coding, nothing ever "returns" a result.

It is easy to mechanically transform normal function-style lambda
calculus into continuation-style, but the reverse is not so.

(2) its syntax and semantics in emacs lisp, common lisp, scheme
(3) Is it present in python and java ?

Java, sort of. For example, the Run interface.
Python, I don't know.

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

You can have a "spaghetti stack", or keep continuation data-structures
in the heap.

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

This sounds like homework. What do you have so far?

Thanks a lot.

(6) any good readable references that explain it lucidly ?

Google?

--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum viditur.
| BBB aa a r bbb |
-----------------------------

 

[Bakul Shah]

> Again I am depressed to encounter a fundamentally new concept that I
> was all along unheard of.

The concept is 37 years old. Wadsworth in his "Continuation
Revisited" paper says he & Strachey were struggling with
extending the technique of denotational semantics to describe
jumps and not finding a satisfactory answer. Then, in his
words:

in October 1970 Strachey showed me a paper "Proving
algorithms by tail functions" by Mazurkiewicz [2] which he
had obtained from an IFIP WG2.2 meeting. Just the phrase
"tail functions" in the title was enough -- given the
experience of our earlier struggles -- for the ideas to
click into place! The (meaning of the) "rest of the program"
was needed as an argument to the semantic functions -- just
so those constructs that did not use it, like jumps, could
throw it anyway. The term "continuation" was coined as
capturing the essence of this extra argument (though I
often wished to have a shorter word!) and the rest, as they
say, is history.

> 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
> (2) its syntax and semantics in emacs lisp, common lisp, scheme
> (3) Is it present in python and java ?
> (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.
> (5) how does it compare to and superior to a function or subroutine
> call. how does it differ.
>
> Thanks a lot.
>
> (6) any good readable references that explain it lucidly ?

You might like this one:

http://www.intertwingly.net/blog/2005/04/13/Continuations-for-Curmudgeons

 

[.]

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

One of the lambda papers, I think. I don't remember which.

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

elisp and Common Lisp don't have them (although sbcl and maybe others user
continuations internally). In scheme CALL-WITH-CURRENT-CONTINUATION takes
a function of one argument, which is bound to the current continuation.
Calling the continuation on some value behaves like
CALL-WITH-CURRENT-CONTINUATION returning that value. So
(call/cc (lambda (k) (k 42))) => 42
You can think of it as turning the whatever would happen after call/cc
was called into a function. The most practical use for continuations in
implementing control structures, though there are some other neat tricks
you can play with them.

(3) Is it present in python and java ?

Certainly not Java, I dunno about Python. I've never seen someone use
them in Python, but the pythonistas seem to want to add everything but a
decent lambda to their language so I wouldn't be surprised if someone had
added a call/cc. Ruby has it.

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

You have Lisp in Small Pieces. Read Lisp in Small Pieces.

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

You use them like a function call. You can also use them like
setjmp/longjmp in C. You can implement coroutines with them, or
events, or simulate non-determinism or write things like ((call/cc call/cc)
(call/cc call/cc)) and make your head explode, use it like goto's inbred
second cousin or in general whatever perverse things you might like to do
with the flow of control in your program.

Thanks a lot.

(6) any good readable references that explain it lucidly ?

Lisp in Small Pieces for implementation details, the Scheme Programming
Language for examples.

 

[gnuist006]

Lambda calculus. Instead of function A returning to its caller, the
caller provides an additional argument (the "continuation") which is a
function B to be called by A with A's result(s). In pure "continuation
style" coding, nothing ever "returns" a result.

It is easy to mechanically transform normal function-style lambda
calculus into continuation-style, but the reverse is not so.

Explanation and reference please

You can have a "spaghetti stack", or keep continuation data-structures
in the heap.

A picture, diagram? a picture is worth a thousand words

 

[gnuist006]

Again I am depressed to encounter a fundamentally new concept that I
was all along unheard of.

The concept is 37 years old. Wadsworth in his "Continuation
Revisited" paper says he & Strachey were struggling with
extending the technique of denotational semantics to describe
jumps and not finding a satisfactory answer. Then, in his
words:

in October 1970 Strachey showed me a paper "Proving
algorithms by tail functions" by Mazurkiewicz [2] which he
had obtained from an IFIP WG2.2 meeting. Just the phrase
"tail functions" in the title was enough -- given the
experience of our earlier struggles -- for the ideas to
click into place! The (meaning of the) "rest of the program"
was needed as an argument to the semantic functions -- just
so those constructs that did not use it, like jumps, could
throw it anyway. The term "continuation" was coined as
capturing the essence of this extra argument (though I
often wished to have a shorter word!) and the rest, as they
say, is history.

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
(2) its syntax and semantics in emacs lisp, common lisp, scheme
(3) Is it present in python and java ?
(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.
(5) how does it compare to and superior to a function or subroutine
call. how does it differ.

Thanks a lot.

(6) any good readable references that explain it lucidly ?

You might like this one:

http://www.intertwingly.net/blog/2005/04/13/Continuations-for-Curmudg...

thanks for the link but can you plz upload the paper so we can also
get it.

 

[gnuist006]

One of the lambda papers, I think. I don't remember which.


elisp and Common Lisp don't have them (although sbcl and maybe others user
continuations internally). In scheme CALL-WITH-CURRENT-CONTINUATION takes
a function of one argument, which is bound to the current continuation.
Calling the continuation on some value behaves like
CALL-WITH-CURRENT-CONTINUATION returning that value. So
(call/cc (lambda (k) (k 42))) => 42
You can think of it as turning the whatever would happen after call/cc
was called into a function. The most practical use for continuations in
implementing control structures, though there are some other neat tricks
you can play with them.


Certainly not Java, I dunno about Python. I've never seen someone use
them in Python, but the pythonistas seem to want to add everything but a
decent lambda to their language so I wouldn't be surprised if someone had
added a call/cc. Ruby has it.


You have Lisp in Small Pieces. Read Lisp in Small Pieces.


You use them like a function call. You can also use them like
setjmp/longjmp in C. You can implement coroutines with them, or
events, or simulate non-determinism or write things like ((call/cc call/cc)
(call/cc call/cc)) and make your head explode, use it like goto's inbred
second cousin or in general whatever perverse things you might like to do
with the flow of control in your program.





Lisp in Small Pieces for implementation details, the Scheme Programming
Language for examples.

which lambda paper ?

 

[Bakul Shah]

thanks for the link but can you plz upload the paper so we can also
get it.

You will have to get it yourself or explain why this is an
impossibility for you.

 

[Tim Bradshaw]

which lambda paper ?

Are you Ilias? I think you probably are.

 

[Diez B. Roggisch]

Are you Ilias? I think you probably are.

He certainly isn't, but you are right that he smells like he's been living
under a bridge for quite a time...

Diez

 

[Matthias Benkard]

(3) Is it present in python ...?

I don't keep up to date with the recent developments in Python land,
but the last time I used Python, it certainly didn't have first-class
continuations. There used to be a project called Stackless Python
that tried to add continuations to Python, but as far as I know, it
has always been separate from the official Python interpreter. I
don't know whether it's still alive. You may want to check http://stackless.com/
for details.

(6) any good readable references that explain it lucidly ?

If you are familiar with Python syntax, there's
http://www.ps.uni-sb.de/~duchier/python/continuations.html -- and even
if you aren't, you may want to have a look at it, as simple Python
code is ridiculously easy to read.

~ Matthias

 

[Matthias Blume]

One of the lambda papers, I think. I don't remember which.

This is a common misconception. There is very little that
originated from the "lambda" papers. But they did a marvelous job at
promoting some of the ideas that existed in the PL community for
years.

As for the concept of continuations, there is Scott and Strachey's
work on denotational semantics, and there is Landin's J operator.
(There's probably more that I am forgetting right now.)

One of the most lucid explanations of definitional interpreters --
including those that are based on continuation-passing -- are
explained in J. Reynolds' famous 1971 "Definitional Interpreters for
Higher-Order Functions" paper. (It has been re-published in 1998 in
HOSC.) The paper also explains how to perform defunctionalization,
which can be seen as a way to compile (and even hand-compile)
higher-order programs.

Matthias

 

[Joel J. Adamson]

Explanation and reference please

Read R5RS or R6RS, the passage on call-with-current-continuation is similar in both
texts ( http://www.r6rs.org/final/html/r6rs/r6rs.html ).

For lambda calculus, look it up on Wikipedia. Alonzo Church is the
name you're looking for.

Joel

--
Joel J. Adamson
Biostatistician
Pediatric Psychopharmacology Research Unit
Massachusetts General Hospital
Boston, MA 02114
(617) 643-1432
(303) 880-3109

 

[josephoswald+gg]

Certainly not Java, I dunno about Python. I've never seen someone use
them in Python, but the pythonistas seem to want to add everything but a
decent lambda to their language so I wouldn't be surprised if someone had
added a call/cc. Ruby has it.

Continuations exist in all computer languages---actually, in anything
that executes code. The continuation is simply "what will happen for
the rest of the program execution." What might or might not exist is
an explicit linguistic mechanism to examine it, refer to the
continuation as a function, or to save it for later use.

The continuation is typically present in the stack, which contains all
the control-flow information needed to continue program execution from
this point. (I.e., the function call mechanism includes a step saving
the location of the instruction to execute when the function call is
complete, and any registers that it will restore after the function
returns because the function call might destroy them.)

How you save that continuation for later, possibly repeated, use from
a different location in the program is a different question.

 

[Terry Reedy]

| 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
| (2) its syntax and semantics in emacs lisp, common lisp, scheme
| (3) Is it present in python and java ?
| (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.
| (5) how does it compare to and superior to a function or subroutine
| call. how does it differ.
|
| Thanks a lot.
|
| (6) any good readable references that explain it lucidly ?

I am starting with the Wikipedia article 'Continuation' which has
references both to other W. articles and several other books and papers.

 

[George Neuner]

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

 

[gnuist006]

One of the lambda papers, I think. I don't remember which.

Hey no-name "dot" you are the only one who says its origin is in
one of the old lambda papers. Give me a reference or someone
give me a reference. I dont have access to any ACM journals or
other conferences. So

step 1
reference and the idea in it

step 2
if you can upload it

This is for historical and conceptual development at the same
time as learning the ideas to use them.

Thanks a lot.

 

[gnuist006]

Special thanks to many of you for your very decent replies.

 

[Jeff M.]

(6) any good readable references that explain it lucidly ?

This was something that has been very interesting to me for a while
now, and I'm actually still having a difficult time wrapping my head
around it completely.

The best written explanation that I've come across was in "The Scheme
Programming Language" (http://mitpress.mit.edu/catalog/item/
default.asp?ttype=2&tid=9946). But perhaps others have better
references.

I'll attempt my own little explanation of call/cc. I'll butcher some
of it, I'm sure, but hopefully those more knowledgeable will politely
correct me. I will start with a loose analogy and point out a couple
examples I came across that did make a lot of sense.

First, the bad analogy I have (if you are coming from C programming
like me) is setjmp and longjmp. This is a bad analogy in that you're
talking about hardware and stack states as opposed to functions, but a
good analogy in that it saves the current state of execution, and
returns to that same state at a later time with a piece of data
attached to it.

My first example of using this would be to create a return function in
Scheme. I hope I don't get this wrong, but the example would be
something like this:

(define (my-test x)
(call/cc (lambda (return)
(return x))))

Now, here's my understanding of what is happening under-the-hood:

1. call/cc stores the current execution state and creates a function
to restore to that state.

2. call/cc then calls its own argument with the function it created.

The key here is that "return" is a function (created by call/cc)
taking 1 argument, and it restores execution at the same state it was
when the call/cc began (or immediately after it?). This line:

(return x)

is really just calling the function created by call/cc, which will
restore the execution state to what it was just prior to the call/cc,
along with a parameter (in this case, the value of x).

My next example I don't follow 100%, and I won't attempt to reproduce
it here, but it generates a continuation that modifies itself (bad?)
to define a list iterator.

http://blog.plt-scheme.org/2007/07/callcc-and-self-modifying-code.html

I recommend putting that code into a Scheme interpreter and running
it. You'll get it.

Hope this helps, and I look forward to better explanations than mine
that will help me along as well.

Jeff M.

 

[gnuist006]

This is a common misconception. There is very little that
originated from the "lambda" papers. But they did a marvelous job at
promoting some of the ideas that existed in the PL community for
years.

As for the concept of continuations, there is Scott and Strachey's
work on denotational semantics, and there is Landin's J operator.
(There's probably more that I am forgetting right now.)


One of the most lucid explanations of definitional interpreters --
including those that are based on continuation-passing -- are
explained in J. Reynolds' famous 1971 "Definitional Interpreters for
Higher-Order Functions" paper. (It has been re-published in 1998 in
HOSC.) The paper also explains how to perform defunctionalization,
which can be seen as a way to compile (and even hand-compile)
higher-order programs.

Matthias

Matthias, thanks for the reference, but I dont have access to an
engineering library. I would appreciate, if you have access to paper/
scanner or electronic copy to help many of us out, you are
not just helping me but many will thank you.