The fundamental concept of continuations

?

.

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

I said "I think." Matthias corrected me. They're all on readscheme.org
( http://library.readscheme.org/page1.html ) though, and well worth
reading.

I note that I'm being mocked for not using my real name by someone not
using his/her real name. Thank you, no-name gnuist006, you make me laugh.
 
E

Erik Jones

I said "I think." Matthias corrected me. They're all on
readscheme.org
( http://library.readscheme.org/page1.html ) though, and well worth
reading.

I note that I'm being mocked for not using my real name by someone not
using his/her real name. Thank you, no-name gnuist006, you make me
laugh.

Relax, ., I hardly think he was mocking you. He probably assumed
that using a . in a sentence as a form of address would be as
unintelligible as it has been in these two sentences.

Erik Jones

Software Developer | Emma®
(e-mail address removed)
800.595.4401 or 615.292.5888
615.292.0777 (fax)

Emma helps organizations everywhere communicate & market in style.
Visit us online at http://www.myemma.com
 
M

Matthias Blume

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.

Given that you seem to be hanging out at the internets, I expect you
do know how to use the google...
 
M

Marlene Miller

Can anyone explain:
(1) its origin

From the Bibliographic Notes of Chapter 12 Continuations in a Functional
Language, Theories of Programming Languages by John C. Reynolds, page 370:

"A history of the repeated discoveries of continuations (occurring largely
in the context of functional languages) is given in Reynolds [1993];
relevant original papers include those by van Wijngaarden [1996], F. L.
Morris [1993], Strachey and Wadsworth [1974], J. H. Morris [1972], Fischer
[1972; 1993], and Abdali [1976]. The operations callcc and throw first
appeared in Scheme, but are descendents of Landin's [1965b] "J-operator".
Both the continuation-passing transformation from direct to continuation
semantics and defunctionalization were described, in the setting of programs
for interpreting eager-evaluation functional languages, by Reynolds
[1972a]."

"Beginning with the implementation of Scheme [Sussman and Steele Jr., 1975]
continuations and the continuation-passing transformation have played a
major role in the design of compilers. More recently, this topic has been
explored at book length by Appel [1992]."

Reynolds [1993] The Discoveries of Continuations.
van Wijngaarden [1996] Recursive Definition of Syntax and Semantics
F. L. Morris [1993] The Next 700 Formal Language Descriptions
Strachey and Wadsworth [1974] Continuations, A Mathematical Semantics for
Handling Full Jumps.
J. H. Morris [1972] A Bonus from van Wijngarden's Device
Fischer [1972, 1993] Lambda Calculus Schemata
Abdali [1976] A Lambda Calculus Model of Programming Languages - I. Simple
Constructs, II. Jumps and Procedures
Sussman and Steele Jr. [1975] SCHEME: An Interpreter for Extended Lambda
Calculus
Compiling With Continuations, Andrew W. Appel, 2007

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

The Scheme Programming Language, R. Kent Dybvig
3.3 Continuations
5.5 Continuations
http://www.scheme.com/tspl3/

Scheme and the Art of Programming, Springer and Friedman
Chapter 16 Introduction to Continuations
Chapter 17 Using Continuations

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

1. Programming Languages: Application and Interpretation, Shriram
Krishnamurthi
Part VII Continuations
http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/plai-2007-04-26.pdf

2. Essentials of Programming Languages, Friedman, Wand and Haynes
Chapter 7 Continuation-Passing Interpreters
Chapter 8 Continuation-Passing Style
http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/plai-2007-04-26.pdf

3. Theories of Programming Languages, John C. Reynolds
5.7 Continuation Semantics [of imperative languages]
Chapter 12 Continuations in a Functional Language
http://www.cs.indiana.edu/eopl/

From the Bibliographic Notes of Chapter 5 Failure, Input-Output and
Continuations, Theories of Programming Languages, John C. Reynolds

"Most of the literature on continuations discusses the concept in the
setting of functional languages (where we will return to continuations in
Section 12.1). However, the properties of continuation semantics for
imperative languages are described, perhaps to excess, by Reynolds [1977]."

Reynolds [1977] Semantics of the Domain of Flow Diagrams
 
M

Marlene Miller

Corrected the links...

1. Programming Languages: Application and Interpretation
Shriram Krishnamurthi
Part VII Continuations
http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/plai-2007-04-26.pdf

2. Essentials of Programming Languages (2nd edition)
Friedman, Wand and Haynes
Chapter 7 Continuation-Passing Interpreters
Chapter 8 Continuation-Passing Style
http://www.cs.indiana.edu/eopl/

3. Theories of Programming Languages, John C. Reynolds
5.7 Continuation Semantics [of imperative languages]
Chapter 12 Continuations in a Functional Language
http://www.cs.cmu.edu/~jcr/tpl.html
 
D

David Kastrup

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.

Basically, there is no difference to function/subroutine call. The
difference is just that there is no "call stack": the dynamic context
for a call is created on the heap and is garbage-collected when it is
no longer accessible. A continuation is just a reference to the state
of the current dynamic context. As long as a continuation remains
accessible, you can return to it as often as you like.
 
G

George Neuner

Basically, there is no difference to function/subroutine call. The
difference is just that there is no "call stack": the dynamic context
for a call is created on the heap and is garbage-collected when it is
no longer accessible. A continuation is just a reference to the state
of the current dynamic context. As long as a continuation remains
accessible, you can return to it as often as you like.

Yes and no. General continuations, as you describe, are not the only
form continuations take. Nor are they the most common form used. The
most common continuations are function calls and returns. Upward
one-shot continuations (exceptions or non-local returns) are the next
most common form used, even in Scheme.

Upward continuations can be stack implemented. On many CPU's, using
the hardware stack (where possible) is faster than using heap
allocated structures. For performance, some Scheme compilers go to
great lengths to identify upward continuations and nested functions
that can be stack implemented.

George
 
D

David Kastrup

George Neuner said:
Yes and no. General continuations, as you describe, are not the
only form continuations take. Nor are they the most common form
used. The most common continuations are function calls and returns.
Upward one-shot continuations (exceptions or non-local returns) are
the next most common form used, even in Scheme.

Upward continuations can be stack implemented. On many CPU's, using
the hardware stack (where possible) is faster than using heap
allocated structures. For performance, some Scheme compilers go to
great lengths to identify upward continuations and nested functions
that can be stack implemented.

There is a Scheme implementation (I keep forgetting the name) which
actually does both: it actually uses the call stack but never returns,
and the garbage collection includes the stack.
 
R

Rob Warnock

+---------------
| > Upward continuations can be stack implemented. On many CPU's, using
| > the hardware stack (where possible) is faster than using heap
| > allocated structures. For performance, some Scheme compilers go to
| > great lengths to identify upward continuations and nested functions
| > that can be stack implemented.
|
| There is a Scheme implementation (I keep forgetting the name) which
| actually does both: it actually uses the call stack but never returns,
| and the garbage collection includes the stack.
+---------------

You're thinking of "Chicken Scheme":

http://www.call-with-current-continuation.org/

Chicken Scheme is actually using the C call stack *as* the heap[1],
and thus all its continuations are *heap*-allocated, and thus
not actually "stack-allocated" at all.

But that's not what George Neuner is talking about, as I read it,
but rather probably about such things as Kent Dybvig's PhD thesis:

http://www.cs.indiana.edu/~dyb/papers/3imp.pdf
"Three Implementation Models for Scheme"
R. Kent Dybvig, UNC Chapel Hill, 1987 (thesis) (190pp)
...
Chapter 4: The Stack-Based Model
...
Early Scheme implementors believed that because of the need to
support first class functions, the standard techniques used for
block-structured languages were not suitable for Scheme. The
need to optimize tail calls and support continuations further
convinced early implementors that the standard stack techniques
were unsuitable. However, as this chapter will show, these
techniques can be made to work for Scheme with a few modications.
The resulting implementation model allows most function calls to
be performed with little or no allocation, and allows variable
references to be performed in one or two memory references.
Heap allocation remains necessary to support closures, assigned
variables, and continuations. Since function calls and variable
references are faster and heap allocation is limited, the running
time for most programs is greatly decreased.
...


-Rob

[1] As suggested in:

http://home.pipeline.com/~hbaker1/CheneyMTA.html
"CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A"
Henry G. Baker (1994)
 
A

Alex Martelli

Matthias Benkard said:
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/

Alive and well, but it has removed continuations (which were indeed in
early versions, as per the paper at
<http://www.stackless.com/spcpaper.htm>).


Alex
 
L

Lawrence D'Oliveiro

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

That's just a callback. I've been doing that in C code (and other
similar-level languages) for years.
 
G

George Neuner

That's just a callback. I've been doing that in C code (and other
similar-level languages) for years.

Callbacks are a form of continuation. However, general continuations
such as those in Scheme, carry with them their execution context.
This allows them to used directly for things like user-space
threading.

George
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
474,444
Messages
2,571,709
Members
48,796
Latest member
Greg L.
Top