By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
 446,383 Members | 2,063 Online
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,383 IT Pros & Developers. It's quick & easy.

# The fundamental concept of continuations

 P: n/a 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 ? Oct 9 '07 #1
Share this Question
26 Replies

 P: n/a In article <11**********************@57g2000hsv.googlegroups. com>, gn*******@gmail.com wrote: 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 | ----------------------------- Oct 9 '07 #2

 P: n/a On Tue, 09 Oct 2007 05:15:49 +0000, gnuist006 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 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. Oct 9 '07 #3

 P: n/a On Oct 8, 10:59 pm, Barb Knox 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 Oct 9 '07 #4

 P: n/a On Oct 8, 11:09 pm, "."

 P: n/a gn*******@gmail.com wrote: On Oct 8, 11:07 pm, Bakul Shah You might like this one:http://www.intertwingly.net/blog/200...ns-for-Curmudg... 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. Oct 9 '07 #6

 P: n/a On Oct 9, 7:34 am, gnuist...@gmail.com wrote: which lambda paper ? Are you Ilias? I think you probably are. Oct 9 '07 #7

 P: n/a Tim Bradshaw wrote: On Oct 9, 7:34 am, gnuist...@gmail.com wrote: >which lambda paper ? 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 Oct 9 '07 #8

 P: n/a (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/pyt...inuations.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 Oct 9 '07 #9

 P: n/a gn*******@gmail.com writes: On Oct 8, 10:59 pm, Barb Knox >Lambda calculus. Instead of function A returning to its caller, thecaller provides an additional argument (the "continuation") which is afunction B to be called by A with A's result(s). In pure "continuationstyle" coding, nothing ever "returns" a result.It is easy to mechanically transform normal function-style lambdacalculus into continuation-style, but the reverse is not so. 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 Oct 9 '07 #10

 P: n/a On Oct 9, 2:09 am, "."

 P: n/a

 P: n/a On Oct 8, 11:09 pm, "." Can anyone explain: (1) its origin 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. Oct 9 '07 #13

 P: n/a (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/c...ying-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. Oct 9 '07 #14

 P: n/a On Tue, 09 Oct 2007 19:20:06 +0000, gnuist006 wrote: On Oct 8, 11:09 pm, "." On Tue, 09 Oct 2007 05:15:49 +0000, gnuist006 wrote: >> Can anyone explain: (1) its origin 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 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. Oct 9 '07 #15

 P: n/a On Oct 9, 2007, at 3:32 PM, . wrote: On Tue, 09 Oct 2007 19:20:06 +0000, gnuist006 wrote: >On Oct 8, 11:09 pm, "." >On Tue, 09 Oct 2007 05:15:49 +0000, gnuist006 wrote: >>>Can anyone explain:(1) its originOne 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 inone of the old lambda papers. Give me a reference or someonegive me a reference. I dont have access to any ACM journals orother 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. 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ź er**@myemma.com 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 Oct 9 '07 #16

 P: n/a gn*******@gmail.com writes: 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... Oct 10 '07 #17

 P: n/a 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/Publicat...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/Publicat...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 Oct 10 '07 #18

 P: n/a Corrected the links... 1. Programming Languages: Application and Interpretation Shriram Krishnamurthi Part VII Continuations http://www.cs.brown.edu/~sk/Publicat...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 Oct 10 '07 #19

 P: n/a gn*******@gmail.com writes: 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. -- David Kastrup, Kriemhildstr. 15, 44793 Bochum Oct 10 '07 #20

 P: n/a On Wed, 10 Oct 2007 12:49:58 +0200, David Kastrup gn*******@gmail.com writes: >Again I am depressed to encounter a fundamentally new concept that Iwas all along unheard of. Its not even in paul graham's book where ilearnt 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 thatpointer 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 subroutinecall. how does it differ. Basically, there is no difference to function/subroutine call. Thedifference is just that there is no "call stack": the dynamic contextfor a call is created on the heap and is garbage-collected when it isno longer accessible. A continuation is just a reference to the stateof the current dynamic context. As long as a continuation remainsaccessible, 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 -- for email reply remove "/" from address Oct 11 '07 #21

 P: n/a George Neuner

 P: n/a David Kastrup 627 26th Avenue San Mateo, CA 94403 (650)572-2607 Oct 13 '07 #23

 P: n/a David Kastrup

 P: n/a Matthias Benkard ). Alex Oct 13 '07 #25

 P: n/a In message , Barb Knox wrote: 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. Oct 14 '07 #26

 P: n/a On Mon, 15 Oct 2007 11:56:39 +1300, Lawrence D'Oliveiro In message , Barb Knox wrote: >Instead of function A returning to its caller, thecaller provides an additional argument (the "continuation") which is afunction 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 othersimilar-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 -- for email reply remove "/" from address Oct 15 '07 #27

### This discussion thread is closed

Replies have been disabled for this discussion.