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 ?
·········@gmail.com wrote:
> 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
On Oct 8, 11:07 pm, Bakul Shah <······@bitblocks.com> wrote:
> ·········@gmail.com wrote:
>
> > 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.
·········@gmail.com wrote:
> On Oct 8, 11:07 pm, Bakul Shah <······@bitblocks.com> wrote:
...
>> 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.
You will have to get it yourself or explain why this is an
impossibility for you.
Hi all.
What a shock! After reading few wikipedia pages about this argument
here around, I realized that early Forth implementations widely used
these concepts without naming them:
- The vocabulary is a real "spaghetti stack"
- Function-pointers (and closures) are customary
- The <build-does> creation words produce a continuation.
Isn't it?
Bye.
> 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 ?
On Oct 9, 4:04 am, Rod MacBan <·········@yahoo.co.uk> wrote:
> Hi all.
> What a shock! After reading few wikipedia pages about this argument
> here around, I realized that early Forth implementations widely used
> these concepts without naming them:
> - The vocabulary is a real "spaghetti stack"
> - Function-pointers (and closures) are customary
> - The <build-does> creation words produce a continuation.
>
> Isn't it?
>
> Bye.
>
> > 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 ?
plz give the link to the wiki page you are talking about so we can
follow you.
On Oct 9, 1:21 pm, ·········@gmail.com wrote:
> On Oct 9, 4:04 am, Rod MacBan <·········@yahoo.co.uk> wrote:
> > Hi all.
> > What a shock! After reading few wikipedia pages about this argument
> > here around, I realized that early Forth implementations widely used
> > these concepts without naming them:
> > - The vocabulary is a real "spaghetti stack"
> > - Function-pointers (and closures) are customary
> > - The <build-does> creation words produce a continuation.
>
> plz give the link to the wiki page you are talking about so we can
> follow you.
This conversation is from comp.lang.scheme, a discussion on
continuations. "Continuation", "Spaghetti stack", and "Closure" are
all Wikipedia articles. But I don't remember the FIG-FORTH vocabulary
as being a spaghetti stack, rather a simple linked list. I could be
wrong. And after all the alcohol I've ingested today, I can't follow
any of the articles anyway. Cheers!
From: Aleksej Saushev
Subject: Re: The fundamental concept of continuations
Date:
Message-ID: <87y7ebphfa.fsf@inbox.ru>
jcomeau_ictx <···········@gmail.com> writes:
> On Oct 9, 1:21 pm, ·········@gmail.com wrote:
>> On Oct 9, 4:04 am, Rod MacBan <·········@yahoo.co.uk> wrote:
>> > Hi all.
>> > What a shock! After reading few wikipedia pages about this argument
>> > here around, I realized that early Forth implementations widely used
>> > these concepts without naming them:
>> > - The vocabulary is a real "spaghetti stack"
>> > - Function-pointers (and closures) are customary
>> > - The <build-does> creation words produce a continuation.
>>
>> plz give the link to the wiki page you are talking about so we can
>> follow you.
>
> This conversation is from comp.lang.scheme, a discussion on
> continuations. "Continuation", "Spaghetti stack", and "Closure" are
> all Wikipedia articles.
Don't trust Wikipedia so much.
> But I don't remember the FIG-FORTH vocabulary
> as being a spaghetti stack, rather a simple linked list.
It is not.
Each vocabulary (except FORTH) contains loop: it starts with special word
called " " (blank), so you could not enter it with keyboard, and ends
with top word of vocabulary, which is pointed from within special one.
Words in dictionary are stacked, you can FORGET them, but they are threaded
with links in vocabularies, the latter gives you tree-structured logical
dictionary and hidden loops, so you could get to top words, while search is
performed down to the root.
As for Scheme, Chuck Moore attended McCarthy's class, IIRC,
he knew LISP anyway.
You confuse vocabulary and dictionary, they differ a lot.
Dictionary is a set of all words, vocabulary is not.
Vocabulary is known as WORDLIST nowadays.
<BUILDS DOES> doesn't produce continuation, though you can do it, if you wish.
You should take a look at FORTH multitasking, it can be done almost portably.
(Actually, you may need to rewrite part of system to achive that.)
Yes Aleksej, I mix up two ideas and was wrong about the rest
(*blush*).
Sorry for the concern: yesterday I posted a bit too fast straight off.
The Wikipedia article is: http://en.wikipedia.org/wiki/Continuation
and its bottom links.
Don't need to continue this thread. Thanks.
Rod.
> jcomeau_ictx <···········@gmail.com> writes:
>
> > On Oct 9, 1:21 pm, ·········@gmail.com wrote:
> >> On Oct 9, 4:04 am, Rod MacBan <·········@yahoo.co.uk> wrote:
> >> > Hi all.
> >> > What a shock! After reading few wikipedia pages about this argument
> >> > here around, I realized that early Forth implementations widely used
> >> > these concepts without naming them:
> >> > - The vocabulary is a real "spaghetti stack"
> >> > - Function-pointers (and closures) are customary
> >> > - The <build-does> creation words produce a continuation.
> >>
> >> plz give the link to the wiki page you are talking about so we can
> >> follow you.
> >
> > This conversation is from comp.lang.scheme, a discussion on
> > continuations. "Continuation", "Spaghetti stack", and "Closure" are
> > all Wikipedia articles.
>
> Don't trust Wikipedia so much.
>
> > But I don't remember the FIG-FORTH vocabulary
> > as being a spaghetti stack, rather a simple linked list.
>
> It is not.
>
> Each vocabulary (except FORTH) contains loop: it starts with special word
> called " " (blank), so you could not enter it with keyboard, and ends
> with top word of vocabulary, which is pointed from within special one.
> Words in dictionary are stacked, you can FORGET them, but they are threaded
> with links in vocabularies, the latter gives you tree-structured logical
> dictionary and hidden loops, so you could get to top words, while search is
> performed down to the root.
>
> As for Scheme, Chuck Moore attended McCarthy's class, IIRC,
> he knew LISP anyway.
>
> You confuse vocabulary and dictionary, they differ a lot.
> Dictionary is a set of all words, vocabulary is not.
> Vocabulary is known as WORDLIST nowadays.
>
> <BUILDS DOES> doesn't produce continuation, though you can do it, if you wish.
> You should take a look at FORTH multitasking, it can be done almost portably.
> (Actually, you may need to rewrite part of system to achive that.)
On Oct 10, 8:17 am, Aleksej Saushev <····@inbox.ru> wrote:
> jcomeau_ictx <···········@gmail.com> writes:
> > On Oct 9, 1:21 pm, ·········@gmail.com wrote:
> >> On Oct 9, 4:04 am, Rod MacBan <·········@yahoo.co.uk> wrote:
> >> > Hi all.
> >> > What a shock! After reading few wikipedia pages about this argument
> >> > here around, I realized that early Forth implementations widely used
> >> > these concepts without naming them:
> >> > - The vocabulary is a real "spaghetti stack"
> >> > - Function-pointers (and closures) are customary
> >> > - The <build-does> creation words produce a continuation.
>
> >> plz give the link to the wiki page you are talking about so we can
> >> follow you.
>
> > This conversation is from comp.lang.scheme, a discussion on
> > continuations. "Continuation", "Spaghetti stack", and "Closure" are
> > all Wikipedia articles.
>
> Don't trust Wikipedia so much.
>
> > But I don't remember the FIG-FORTH vocabulary
> > as being a spaghetti stack, rather a simple linked list.
>
> It is not.
>
> Each vocabulary (except FORTH) contains loop: it starts with special word
> called " " (blank), so you could not enter it with keyboard, and ends
> with top word of vocabulary, which is pointed from within special one.
Forth doesn't define how the wordlist (or vocabulary, or dictionary)
is implemented. Some are implemented as lists, others as hashes; there
are many technqiues. No Forth that I know of contains a special word "
". Perhaps you are confusing it with BL, and it may or may not be the
top word in the vocabulary. The parser uses blanks to delimit words.
> Words in dictionary are stacked, you can FORGET them, but they are threaded
> with links in vocabularies, the latter gives you tree-structured logical
> dictionary and hidden loops, so you could get to top words, while search is
> performed down to the root.
Hidden loops?
>
> As for Scheme, Chuck Moore attended McCarthy's class, IIRC,
> he knew LISP anyway.
>
> You confuse vocabulary and dictionary, they differ a lot.
> Dictionary is a set of all words, vocabulary is not.
> Vocabulary is known as WORDLIST nowadays.
Vocabularies are named WORDLISTs, and they are not the same.
>
> <BUILDS DOES> doesn't produce continuation, though you can do it, if you wish.
> You should take a look at FORTH multitasking, it can be done almost portably.
> (Actually, you may need to rewrite part of system to achive that.)
--
Regards
Alex McDonald
From: Aleksej Saushev
Subject: Re: The fundamental concept of continuations
Date:
Message-ID: <87sl4jp5xi.fsf@inbox.ru>
Alex McDonald <····@rivadpm.com> writes:
> On Oct 10, 8:17 am, Aleksej Saushev <····@inbox.ru> wrote:
>> jcomeau_ictx <···········@gmail.com> writes:
>> > On Oct 9, 1:21 pm, ·········@gmail.com wrote:
>> >> On Oct 9, 4:04 am, Rod MacBan <·········@yahoo.co.uk> wrote:
>> >> > Hi all.
>> >> > What a shock! After reading few wikipedia pages about this argument
>> >> > here around, I realized that early Forth implementations widely used
>> >> > these concepts without naming them:
>> >> > - The vocabulary is a real "spaghetti stack"
>> >> > - Function-pointers (and closures) are customary
>> >> > - The <build-does> creation words produce a continuation.
>>
>> >> plz give the link to the wiki page you are talking about so we can
>> >> follow you.
>>
>> > This conversation is from comp.lang.scheme, a discussion on
>> > continuations. "Continuation", "Spaghetti stack", and "Closure" are
>> > all Wikipedia articles.
>>
>> Don't trust Wikipedia so much.
>>
>> > But I don't remember the FIG-FORTH vocabulary
>> > as being a spaghetti stack, rather a simple linked list.
>>
>> It is not.
>>
>> Each vocabulary (except FORTH) contains loop: it starts with special word
>> called " " (blank), so you could not enter it with keyboard, and ends
>> with top word of vocabulary, which is pointed from within special one.
>
> Forth doesn't define how the wordlist (or vocabulary, or dictionary)
> is implemented.
We speak about FIG model here, see above.
> Some are implemented as lists, others as hashes; there
> are many technqiues.
Right, modern Forth does not specify whether WORDLIST is actually list.
> No Forth that I know of contains a special word " ".
> Perhaps you are confusing it with BL, and it may or may not be the
> top word in the vocabulary. The parser uses blanks to delimit words.
I speak about classic FIG-Forth, as in rev. 1.0, it does vocabularies
this way. BL is just a name for blank, right, the name is single BL.
>> Words in dictionary are stacked, you can FORGET them, but they are threaded
>> with links in vocabularies, the latter gives you tree-structured logical
>> dictionary and hidden loops, so you could get to top words, while search is
>> performed down to the root.
>
> Hidden loops?
I can't find more appropriate words to describe pointer from within, say,
FORTH, to TASK, which is initial top word in dictionary.
>> As for Scheme, Chuck Moore attended McCarthy's class, IIRC,
>> he knew LISP anyway.
>>
>> You confuse vocabulary and dictionary, they differ a lot.
>> Dictionary is a set of all words, vocabulary is not.
>> Vocabulary is known as WORDLIST nowadays.
>
> Vocabularies are named WORDLISTs, and they are not the same.
You speak about ANS Forth again.
If it were from the very beginning, everything would be different.
In standard Forth:
a) vocabulary is not a stack, you have to explicitly show nesting
with MARKER, if supported;
b) dictionary is just a set of independent WORDLISTs, which may be
linked in any arbitrary way;
c) <BUILDS is replaced with CREATE, but it still doesn't give you
continuations;
d) you can't create continuations unless you have implementation-defined
support.
Well, I mean "easy" ways, obviously nothing stops you from replacing
all you have with your new world.
>> <BUILDS DOES> doesn't produce continuation, though you can do it, if you wish.
>> You should take a look at FORTH multitasking, it can be done almost portably.
>> (Actually, you may need to rewrite part of system to achive that.)
Rod MacBan <·········@yahoo.co.uk> writes:
>Hi all.
>What a shock! After reading few wikipedia pages about this argument
>here around, I realized that early Forth implementations widely used
>these concepts without naming them:
>- The vocabulary is a real "spaghetti stack"
In fig-Forth the dictionary is a cactus stack (aka spaghetti stack):
each vocabulary was an extension of its parent dictionary (at the time
that the child vocabulary was created). That partially alleviates the
absence of a search order in fig-Forth.
In modern Forth systems the wordlists (a concept simular to a
vocabulary) are separate, and the search order allows searching them
in any order (not just the CONTEXT vocabulary, its ancestors, and the
CURRENT vocabulary and its ancestors).
>- Function-pointers (and closures) are customary
Not sure what you mean by that, but execution tokens (XTs) are (a
generalised form of) function pointers (you have XTs for all words,
not just for colon definitions (which correspond to functions in C and
Lisp)).
Forth does not have closures in the usual sense, because Forth does
not normally have nested definitions; moreover, pure Forth does not
have local variables. And even if a Forth system has both locals and
nested definitions, it does not allow referencing locales that are not
from the innermost definition.
You can get something like a closure with CREATE...DOES> (in
fig-Forth, <BUILDS...DOES>), or by defining a colon definition with
the contents of the free variables compiled in as literals (the latter
can even be anonymous in ANS Forth). However, in Forth the resulting
word will stay around until the system is terminated, whereas you
usually expect closures to be garbage collected.
>- The <build-does> creation words produce a continuation.
Not in the least. The only kind of continuation you have in Forth is
the contents of the return stack (and for a proper continuation, you
need to combine this with the contents of the other stacks (data, FP,
and possibly locals). And that's a second-class citizen in any Forth
implementation, and even more restricted in standard Forth (i.e., no
standard Forth way to save and restore a continuation).
Followus set to comp.lang.forth
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2007: http://www.complang.tuwien.ac.at/anton/euroforth2007/
> (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 Benkard <··········@gmail.com> wrote:
> 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
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.
On Oct 8, 11:09 pm, "." <····@bar.biz> wrote:
> 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.
which lambda paper ?
Tim Bradshaw wrote:
> On Oct 9, 7:34 am, ·········@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
On Oct 9, 2:09 am, "." <····@bar.biz> wrote:
> On Tue, 09 Oct 2007 05:15:49 +0000, gnuist006 wrote:
> > (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.
>
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.
> > (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.
>
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.
"." <···@bar.biz> writes:
> 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.
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.)
>> (6) any good readable references that explain it lucidly ?
>
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
On Oct 9, 5:50 am, Matthias Blume <····@my.address.elsewhere> wrote:
> "." <····@bar.biz> writes:
> > 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.
>
> 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.)
>
> >> (6) any good readable references that explain it lucidly ?
>
> 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.
·········@gmail.com wrote in article <························@22g2000hsm.googlegroups.com> in comp.lang.functional:
> > 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, 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.
If nothing else, please use Google. Many will thank you.
http://www.google.com/search?hl=en&q=Definitional+Interpreters+for+Higher-Order+Functions&btnG=Search
--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
If monads encapsulate effects and lists form a monad, do lists correspond to
some effect? Indeed they do, and the effect they correspond to is choice.
Wadler 1995, Monads for fn'l programming
> If nothing else, please use Google. Many will thank you.
>
http://www.google.com/search?hl=en&q=Definitional+Interpreters+for+Higher-Order+Functions&btnG=Search
http://www.brics.dk/~hosc/vol11/contents.html
Definitional Interpreters for Higher-Order Programming Languages
Definitional Interpreters Revisited
·········@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...
On Oct 8, 11:09 pm, "." <····@bar.biz> wrote:
> 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
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.
On Tue, 09 Oct 2007 19:20:06 +0000, gnuist006 wrote:
> On Oct 8, 11:09 pm, "." <····@bar.biz> wrote:
>> 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.
On Tue, 09 Oct 2007 05:15:49 -0000, ·········@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
Special thanks to many of you for your very decent replies.
On Oct 9, 11:18 am, George Neuner <·········@/comcast.net> wrote:
> On Tue, 09 Oct 2007 05:15:49 -0000, ·········@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 fromhttp://rapidshare.com/files/24382311/155860698X.Morgan_20Kaufmann.Eng...
>
> 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
In article <························@57g2000hsv.googlegroups.com>,
·········@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 |
-----------------------------
On Oct 8, 10:59 pm, Barb Knox <····@sig.below> wrote:
>
> 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
·········@gmail.com writes:
> On Oct 8, 10:59 pm, Barb Knox <····@sig.below> wrote:
>
>>
>> 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
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
From: Lawrence D'Oliveiro
Subject: Re: The fundamental concept of continuations
Date:
Message-ID: <feu6r7$ccu$1@lust.ihug.co.nz>
In message <·························@lust.ihug.co.nz>, 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.
On Mon, 15 Oct 2007 11:56:39 +1300, Lawrence D'Oliveiro
<···@geek-central.gen.new_zealand> wrote:
>In message <·························@lust.ihug.co.nz>, 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.
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
George Neuner wrote:
> On Mon, 15 Oct 2007 11:56:39 +1300, Lawrence D'Oliveiro
> <···@geek-central.gen.new_zealand> wrote:
>
>
>>In message <·························@lust.ihug.co.nz>, 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.
>
>
> Callbacks are a form of continuation.
Yes, in the same sense that a shoe is a form of aircraft carrier.
kenny
--
http://www.theoryyalgebra.com/
"Career highlights? I had two. I got an intentional walk
from Sandy Koufax and I got out of a rundown against the Mets."."
- Bob Uecker
On Mon, 15 Oct 2007 00:49:13 -0400, Ken Tilton
<···········@optonline.net> wrote:
>
>
>George Neuner wrote:
>> On Mon, 15 Oct 2007 11:56:39 +1300, Lawrence D'Oliveiro
>> <···@geek-central.gen.new_zealand> wrote:
>>
>>
>>>In message <·························@lust.ihug.co.nz>, 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.
>>
>>
>> Callbacks are a form of continuation.
>
>Yes, in the same sense that a shoe is a form of aircraft carrier.
I was pointing out a simple technical fact. I'm not at all sure what
you are pointing out. shoe <=> aircraft carrier?
Beside which, CL doesn't have "real" continuations ... a fact that
amuses Schemers no end. You are a Lisper so I don't know where you
get off acting so smug.
George
--
for email reply remove "/" from address
George Neuner wrote:
> On Mon, 15 Oct 2007 00:49:13 -0400, Ken Tilton
> <···········@optonline.net> wrote:
>
>
>>
>>George Neuner wrote:
>>
>>>On Mon, 15 Oct 2007 11:56:39 +1300, Lawrence D'Oliveiro
>>><···@geek-central.gen.new_zealand> wrote:
>>>
>>>
>>>
>>>>In message <·························@lust.ihug.co.nz>, 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.
>>>
>>>
>>>Callbacks are a form of continuation.
>>
>>Yes, in the same sense that a shoe is a form of aircraft carrier.
>
>
> I was pointing out a simple technical fact.
Well, I am just a simple application programmer so I am having trouble
understanding how a callback is a continuation, emphasis on "continue".
Please elucidate. My fear is that your answer is that it is a
continuation that happens to continue nothing, like an object at rest is
moving but at a zero velocity. Just as ...
> I'm not at all sure what
> you are pointing out. shoe <=> aircraft carrier?
... a shoe is an aircraft carrier without all the planes. Inter alia.
>
> Beside which, CL doesn't have "real" continuations ... a fact that
> amuses Schemers no end.
No, you are thinking of the fact that your spec is shorter than the
index to our spec. I hear it's growing fast, tho, and every serious
Schemer is locked into just as big a ball of mud as Lisp, except it is
one they built and the consequence that you have this tower of bable
thing going which CL solved twenty years ago with the standard whose
index size amuses you amuses us. No end.
Continuations would be great if I needed anything like them more than
once every twelve months and could not Greenspun them myself with state
which is probably the right way to go anyway since it makes the state
required to continue a calculation explicit -- ok, sorry, continuations
are a stupid pet trick, obscurantist and superflewous and they probably
hasten hair loss. You should lose them, make your spec even smaller.
> You are a Lisper so I don't know where you
> get off acting so smug.
Nonsense. Smug is what Lisp weenies do best.
hth, kenny
--
http://www.theoryyalgebra.com/
"Career highlights? I had two. I got an intentional walk
from Sandy Koufax and I got out of a rundown against the Mets."."
- Bob Uecker
On Mon, 15 Oct 2007 11:22:28 -0400, Ken Tilton
<···········@optonline.net> wrote:
>
>Well, I am just a simple application programmer so I am having trouble
>understanding how a callback is a continuation, emphasis on "continue".
And here I was laboring under the impression that you were a god 8-)
>Please elucidate.
Technically, a continuation is just "whatever happens next". It
manifests at all levels:
- as the next CPU instruction in a sequence. Sequences are not
necessarily contiguous, e.g., FPU instructions may take many cycles so
the FPU instruction that continues the computation may follow several
unrelated instructions destined for other units.
- as the next basic block in a compiler trace. The outputs of a basic
block are the inputs of the one that follows.
- at the programming language level in virtually all languages as
gotos, function/procedure calls and returns, non-local returns, etc.
In this context, closures are just fancy functions, not a separate
category.
- and ultimately as in Scheme where they might represent the context
of a paused execution path. Reified execution context is the basis of
OS process and thread abstractions. What is unique about Scheme's
continuation is not the idea, rather the way the idea is integrated
into the language.
High level programming books, particularly those based on Scheme, like
to profess that continuations are something magical, but in practice
their use tends to be rather mundane.
>My fear is that your answer is a continuation that happens to continue
>nothing, like an object at rest is moving but at a zero velocity.
>Just as ...
Depends on your point of view. I'm not knocking continuations - far
from it - continuations are everywhere and nothing could be done
without them. I'm just pointing out that they are not magic.
George
--
for email reply remove "/" from address
From: Ken Tilton
Subject: Re: The fundamental concept of continuations
Date:
Message-ID: <uRoRi.21$V76.1@newsfe12.lga>
George Neuner wrote:
> On Mon, 15 Oct 2007 11:22:28 -0400, Ken Tilton
> <···········@optonline.net> wrote:
>
>
>>Well, I am just a simple application programmer so I am having trouble
>>understanding how a callback is a continuation, emphasis on "continue".
>
>
> And here I was laboring under the impression that you were a god 8-)
I see. You people won't listen to me on GUI programming but you are hard
at work on my Bible? Time for the yellow bulldozers, this experiement is
done.
>
>
>
>>Please elucidate.
>
>
> Technically, a continuation is just "whatever happens next".
See, this is why need not just dumb trench-digging application
programmers like me, we also need supertheoretical functional geniuses
to come up the Deep Insights. Until now I thought I was about to make a
coffee run, but now I see that even though it will be a new coffee run
it is still what happens next and if I get pulled over and the cop wants
to know what's the hurry I'll just tell him he is interrupting a Scheme
continuation.
technically, kt
--
http://www.theoryyalgebra.com/
"Career highlights? I had two. I got an intentional walk
from Sandy Koufax and I got out of a rundown against the Mets."."
- Bob Uecker
Ken Tilton <·········@gmail.com> wrote:
+---------------
| George Neuner wrote:
| > Technically, a continuation is just "whatever happens next".
|
| See, this is why need not just dumb trench-digging application
| programmers like me, we also need supertheoretical functional geniuses
| to come up the Deep Insights. Until now I thought I was about to make a
| coffee run, but now I see that even though it will be a new coffee run
| it is still what happens next and if I get pulled over and the cop wants
| to know what's the hurry I'll just tell him he is interrupting a Scheme
| continuation.
+---------------
Ahhh, Kenny, Kenny, you're missing the whole point of "real"
(Schemish) continuations. Here's how your story *should* go,
which may help explain (or not):
0. You're slaving away on Cello version 72531.22.91 when you
realize you've *got* to have some coffee, but you know you're
going to be working all night and you only have enough cash
left after buying that 42nd mongo flatpanel [needed to show
off the full feature set of Cello version 72531.22.90] to
buy one cup. Thankfully, you've been reading this thread,
so you...
1. Put a sticky note on your monitor to remind you what it is
you want to do next after your coffee break [note (and this
is very important): you SETF the note, not LET-bind it!!] and
then you make your coffee run (but *DON'T* drink it yet!!)
and bring it back to the CelloCAVE, and while it's nice and
hot, just before you take the first sip, you do a CALL/CC
and stick the resulting continuation you got into a special
box on a shelf near the door. Then you...
2. Enjoy your coffee, get your caffeine rush, and head back to
your coding CAVE and start doing whatever it says on the little
yellow sticky you put on your monitor in step #1.
Now here's where the real fun starts...
3. Several hours [minutes?!?] later, having used up your caffeine
rush [but Cello 72531.22.91 still being unfinished], it's time
for another coffee run, but as noted in #0 you now have no money
left. No problemo! Make a note to yourself on a little yellow
sticky saying what you want to do after your coffee and stick
it on your monitor [SETF, not LET-bind!], then go over next to
the door and FUNCALL the continuation in the box on the shelf
by the door, and you...
4. Wake up, just back from the coffee run you made in #1, with a
hot steaming cut of fresh coffee in your hand, which you enjoy,
get your rush, and head back to your coding CAVE and start doing
whatever it says on the little yellow sticky you put on your
monitor in step #1.
3a. Several hours [minutes?!?] later, having used up your caffeine
rush [but Cello 72531.22.91 still being unfinished], it's time
for another coffee run, but as noted in #0 you now have no money
left. No problemo! Make a note to yourself on a little yellow
sticky saying what you want to do after your coffee and stick
it on your monitor [SETF, not LET-bind!], then go over next to
the door and FUNCALL the continuation in the box on the shelf
by the door, and you...
4a. Wake up, just back from the coffee run you made in #1, with a
hot steaming cut of fresh coffee in your hand, which you enjoy,
get your rush, and head back to your coding CAVE and start doing
whatever it says on the little yellow sticky you put on your
monitor in step #1.
And you continue in this way, never having to pay for another cup of
coffee, until Cello 72531.22.91 *is* finally finished, then you...
5. Crash all weekend, and get up on Sunday night just long enough
to post the announcement of Cello 72531.22.91 [no documentation,
of course, but it all *WORKS*!!] to "comp.lang.lisp", and then
crash back in your bed again. [Only to wake up Monday morning
to discover that the ungrateful yobbos of "c.l.lisp" are all
bitching about the (lack of) documentation instead of singing
hosannas about all the new features... But that's another story.]
In a nutshell: The thing that's different about full/real/Schemish
continuations is that you can call them more than once. But note
that only the *control* path is repeated; any globals that you
SETF'd [such as the yello sticky] *aren't* reset when you call the
continuation a 2nd, 3rd, 4th, etc., time, so you can use them to
tell the difference between successive FUNCALLs of the continuation.
-Rob
p.s. Smart Schemers will realize I've cheated in the above story.
Well, unless somebody knows how to instantiate a cup of coffee
entirely in the control path and not in a stateful "coffee-mug object"
whose mutations (and eventual emptiness) *will* be noticed across
reinvocations of the continuation.
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
> In a nutshell: The thing that's different about full/real/Schemish
> continuations is that you can call them more than once. But note
> that only the *control* path is repeated; any globals that you
> SETF'd [such as the yello sticky] *aren't* reset when you call the
> continuation a 2nd, 3rd, 4th, etc., time, so you can use them to
> tell the difference between successive FUNCALLs of the continuation.
Local bindings that have been SETF'd are also not reset, though of
course they're subject to scope as usual. For example, this:
(let ((coffee-emptyp nil))
(call/cc (lambda (k) (setf *k* k)))
(if coffee-emptyp
"ZZZZ"
(progn (setf coffee-emptyp t) "!!!!")))
would return "!!!!" the first time, but subsequent returns (caused by
invoking the continuation saved in *k*) would yield only "ZZZZ".
--
(let ((C call-with-current-continuation)) (apply (lambda (x y) (x y)) (map
((lambda (r) ((C C) (lambda (s) (r (lambda l (apply (s s) l)))))) (lambda
(f) (lambda (l) (if (null? l) C (lambda (k) (display (car l)) ((f (cdr l))
(C k))))))) '((#\J #\d #\D #\v #\s) (#\e #\space #\a #\i #\newline)))))
Jed Davis <····@panix.com> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > In a nutshell: The thing that's different about full/real/Schemish
| > continuations is that you can call them more than once. But note
| > that only the *control* path is repeated; any globals that you
| > SETF'd [such as the yello sticky] *aren't* reset when you call the
| > continuation a 2nd, 3rd, 4th, etc., time...
|
| Local bindings that have been SETF'd are also not reset, though of
| course they're subject to scope as usual.
+---------------
Yes, of course. You caught me oversimplifying for tutorial purposes...
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
>
> In a nutshell: The thing that's different about full/real/Schemish
> continuations is that you can call them more than once. But note
> that only the *control* path is repeated; any globals that you
> SETF'd [such as the yello sticky] *aren't* reset when you call the
> continuation a 2nd, 3rd, 4th, etc., time, so you can use them to
> tell the difference between successive FUNCALLs of the continuation.
>
Thank you for that. I've read about continuations, but the
accounts missed off the crucial detail that the globals
aren't reset, so I was left going "Huh? That's not gonna work!"
Alan
> (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.
> 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
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
·········@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
On Wed, 10 Oct 2007 12:49:58 +0200, David Kastrup <···@gnu.org> wrote:
>·········@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.
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
George Neuner <·········@/comcast.net> writes:
> 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.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
David Kastrup <···@gnu.org> writes:
> 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.
That would be Chicken Scheme.
http://en.wikipedia.org/wiki/Chicken_(Scheme_implementation)
David Kastrup <···@gnu.org> wrote:
+---------------
| George Neuner <·········@/comcast.net> writes:
| > 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)
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607