# Re: [stack] Re: continuations in Meta/4

## wtanksleyjr@cox.net — 2002-07-10 16:27:38

    From: "e1_t" <e1_t@...>

     > > I just finished adding continuations to Meta/4 and I

    > > was wondering what other people think of them.

     Continuations are worderful, but what you've implemented is only part of what people can use. See mlg's work on continuations, backtracking, and coroutines in Forth to see the power of an open return stack.

    mlg suggests some handy abstractions you can provide if you don't want to give your users full access to an open return stack (or if you simply want to provide a more friendly library, although I also recommend providing direct access to the return stack as well).

     > Correction - due to tail call optimization this should be

    > 1 cont (which is the same as exit really).

    > Although cont could be defined as a macro that compiles

    > cont nop

    > (where nop is a dummy word that does nothing) which

    > would force cont to not be tail call optimized.

     Tail call folding isn't the problem. There are several problems I can see here.

    First, you're trying to count things that really can't be counted. The user can't count by eye how many continuations to discard, because the continuation stack can be rearranged dynamically. Tail call elimination isn't the only way to do that; cont itself also does wacky things, and other continuation manipulation words can be arbitrarily worse. 'cont' therefore shouldn't take an integer, and if you do need a word which calls a much deeper continuation, you need to have a way to save continuations with labels.

    Second, it looks like your 'x' primitive is executing quotations improperly -- it's assuming that at the end of the quotation, the correct place to resume execution is right after the 'x' (in the word which called the 'x'). That may usually be right, but with continuation manipulation it often won't be. The correct behavior for 'x' is to _call_ the quotation (not simply interpret it), and this means that when the quotation ends it has to return to whatever's on the top of the continuation stack, even if it's not the same thing that was there when we started.

     > Tail call optimization seems to only complicate things

    > and maybe it

    > would be better if it was explicit rather than implicit

    > in which case

    > it would be replaced by a word that transfers control to

    > another word rather than calling it.

     This would only solve half of your problem, and really, it would only treat the symptom. The real problem is the false assumption that you can staticly know the contents of the (dynamic) continuation stack.

    It's also a bad idea because it removes a VERY commonly useful optimization because a very rare operation is affected by it. Even if tail-call were at fault, it would still be better to put the workaround in cont.

     > Ivan

     -Billy

## e1_t — 2002-07-11 00:06:39

    --- In concatenative@y..., <wtanksleyjr@c...> wrote:

     > From: "e1_t" <e1_t@y...>

    > > > I just finished adding continuations to Meta/4 and I

    > > > was wondering what other people think of them.

    >

    > Continuations are worderful, but what you've implemented is only

     part of what people can use. See mlg's work on continuations,

    backtracking, and coroutines in Forth to see the power of an open

    return stack.

     >

    > mlg suggests some handy abstractions you can provide if you don't

     want to give your users full access to an open return stack (or if

    you simply want to provide a more friendly library, although I also

    recommend providing direct access to the return stack as well).

     >

    > > Correction - due to tail call optimization this should be

    > > 1 cont (which is the same as exit really).

    > > Although cont could be defined as a macro that compiles

    > > cont nop

    > > (where nop is a dummy word that does nothing) which

    > > would force cont to not be tail call optimized.

    >

    > Tail call folding isn't the problem. There are several problems I

     can see here.

     >

    > First, you're trying to count things that really can't be counted.

     The user can't count by eye how many continuations to discard,

    because the continuation stack can be rearranged dynamically. Tail

    call elimination isn't the only way to do that; cont itself also does

    wacky things, and other continuation manipulation words can be

    arbitrarily worse. 'cont' therefore shouldn't take an integer, and if

    you do need a word which calls a much deeper continuation, you need

    to have a way to save continuations with labels.

     >

     Meta/4 has no continuation stack. I've already seen M. L.

    Gassanenko's work. From what I recall he only implemented a

    continuation stack because the return stack isn't sufficient if the

    programmer also uses it to store temporary data - in Meta/4 that is

    not a problem anymore - Meta/4 has multiple stacks and the return

    stack, while it can be accessed, shouldn't be unless the programmer

    knows what they're doing.

    cont does nothing wacky - all it does is it simply discards top n

    items from the return stack (well sort of - because in my current

    implementation x' also uses the return stack to save values. cont

    takes that into account and makes sure such values are put back onto

    the data stack even if the return stack has been rearranged).

    cont doesn't take an integer as such - it takes a continuation that

    is associated with that number - for every nesting level the numbers

    get incremented. Similarly #dup does not take an integer - it takes a

    stack associated with that number and duplicates it. Because Meta/4

    is typeless integers are used as ids for everything - that is almost

    completely transparent to the programmer unless they're doing

    something wrong like using dup to duplicate a stack.

    As for saving continuations with labels - I already thought of that -

    in a concatenative language it would look ugly.

    I'm however considering implementing a goto-like word as an addition

    to the current system which would utilize such labels (note that this

    is not the same as the jump word I mentioned earlier). It probably

    wouldn't be a part of Meta/4 but of some library.

     > Second, it looks like your 'x' primitive is executing quotations

     improperly -- it's assuming that at the end of the quotation, the

    correct place to resume execution is right after the 'x' (in the word

    which called the 'x'). That may usually be right, but with

    continuation manipulation it often won't be. The correct behavior

    for 'x' is to _call_ the quotation (not simply interpret it), and

    this means that when the quotation ends it has to return to

    whatever's on the top of the continuation stack, even if it's not the

    same thing that was there when we started.

    There is nothing wrong with how x works - I never said that the

    return stack couldn't be rearranged in which case execution wouldn't

    resume after x - in other words x does call the code-stack/quotation.

     >

    > > Tail call optimization seems to only complicate things

    > > and maybe it

    > > would be better if it was explicit rather than implicit

    > > in which case

    > > it would be replaced by a word that transfers control to

    > > another word rather than calling it.

    >

    > This would only solve half of your problem, and really, it would

     only treat the symptom. The real problem is the false assumption that

    you can staticly know the contents of the (dynamic) continuation

    stack.

     >

    > It's also a bad idea because it removes a VERY commonly useful

     optimization because a very rare operation is affected by it. Even if

    tail-call were at fault, it would still be better to put the

    workaround in cont.

     >

     Tail calls/jumps would still be possible - just explicit - I don't

    have a problem with that. And recursion would still work the same way

    it does now (using recurse - similar to Forth but different in that

    it performs a jump rather than a call).

    True, implicit tail call optimization is still nicer so I'd still

    prefer to keep it.

    Ivan

## Billy and Melissa — 2002-07-11 04:42:09

    Was my formatting that terrible? Ouch. Sorry. I posted from egroups, and

    they usually do better. Anyhow:

    From: "e1_t" <e1_t@...>

     > --- In concatenative@y..., <wtanksleyjr@c...> wrote:

    > > From: "e1_t" <e1_t@y...>

    > > > > I just finished adding continuations to Meta/4 and I

    > > > > was wondering what other people think of them.

    > > Continuations are worderful, but what you've implemented is only

    > > part of what people can use. See mlg's work on continuations,

    > > Tail call folding isn't the problem. There are several problems I

    > > can see here.

    > > First, you're trying to count things that really can't be counted.

    > > The user can't count by eye how many continuations to discard,

    > > because the continuation stack can be rearranged dynamically. Tail

    > > call elimination isn't the only way to do that; cont itself also does

    > > wacky things, and other continuation manipulation words can be

    > > arbitrarily worse. 'cont' therefore shouldn't take an integer, and if

    > > you do need a word which calls a much deeper continuation, you need

    > > to have a way to save continuations with labels.

    > Meta/4 has no continuation stack.

     When I say "continuation stack" I mean "stack upon which continuations are

    stored", not "stack upon which ONLY continuations are stored." So Meta/4

    certainly does have a continuation stack; it's the return stack.

     > I've already seen M. L.

    > Gassanenko's work. From what I recall he only implemented a

    > continuation stack because the return stack isn't sufficient if the

    > programmer also uses it to store temporary data - in Meta/4 that is

    > not a problem anymore - Meta/4 has multiple stacks and the return

    > stack, while it can be accessed, shouldn't be unless the programmer

    > knows what they're doing.

     His continuation stack is irrelevant -- the abstractions which use it are

    the interesting things.

     > cont does nothing wacky - all it does is it simply discards top n

    > items from the return stack

     Ouch. So it's not a continuation operator at all -- it's a forced multiple

    return operator. I assumed that it was actually doing continuation work: if

    so, it would have copied the /n/th item to the top of the rstack, not

    dropped /n/ items. A better name for it would be 'unwind', since it unwinds

    the call chain and forces an exit.

     > (well sort of - because in my current

    > implementation x' also uses the return stack to save values. cont

    > takes that into account and makes sure such values are put back onto

    > the data stack even if the return stack has been rearranged).

     Good deal, makes sense.

     > cont doesn't take an integer as such - it takes a continuation that

    > is associated with that number - for every nesting level the numbers

    > get incremented. Similarly #dup does not take an integer - it takes a

    > stack associated with that number and duplicates it. Because Meta/4

    > is typeless integers are used as ids for everything - that is almost

    > completely transparent to the programmer unless they're doing

    > something wrong like using dup to duplicate a stack.

     Obviously, this integer is NOT transparently associated with a specific

    continuation: you're having problems with it. The reason for this is that

    the continuation is not associated with the number; the number is actually a

    relative index from the current continuation. I repeat: this won't work the

    way you intend it to, except in one special case.

     > As for saving continuations with labels - I already thought of that -

    > in a concatenative language it would look ugly.

     Labels need not be textual. They could be anything from an integer to a hash

    code (with a way to input a literal hash code, perhaps like Smalltalk's

    #syntax).

    Thus, if you have your code:

    [ something 45 cont dead-code ] x

    called by a function which looks like this:

    [ other 45 cont-label other-again yadda ] x

    ...that '45 cont' will return to the function which most recently executed

    the '45 cont-label'.

    A better name for this pair of functions might be "unwind-until" and

    "unwind-marker", by the way. The obvious implementation would be to have

    unwind-marker drop its marker on the return stack, and have unwind-until

    drop continuations off the rstack until it hits the marker. When any word

    returns it will have to clear any markers from its data stack, of course.

    (Alternately, each continuation on the rstack could have space for a single

    marker.)

     > There is nothing wrong with how x works - I never said that the

    > return stack couldn't be rearranged in which case execution wouldn't

    > resume after x - in other words x does call the code-stack/quotation.

     My mistake, I think, was in assuming that 'cont' was performing a

    continuation operation. You're right.

     > > > Tail call optimization seems to only complicate things

    > > > and maybe it

    > > > would be better if it was explicit rather than implicit

    > > > in which case

    > > > it would be replaced by a word that transfers control to

    > > > another word rather than calling it.

    > > This would only solve half of your problem, and really, it would

    > > only treat the symptom. The real problem is the false assumption that

    > > you can staticly know the contents of the (dynamic) continuation

    > > stack.

    > > It's also a bad idea because it removes a VERY commonly useful

    > > optimization because a very rare operation is affected by it. Even if

    > > tail-call were at fault, it would still be better to put the

    > > workaround in cont.

    > Tail calls/jumps would still be possible - just explicit - I don't

    > have a problem with that.

     I do; tail-call elimination is a safe optimization, and if it's not working

    there's something wrong with your code or design.

     > And recursion would still work the same way

    > it does now (using recurse - similar to Forth but different in that

    > it performs a jump rather than a call).

     You mean tail recursion? Yes, that's fine. Many Forth compilers do that as

    well. If you meant that recursion _always_ performs a jump, that won't work;

    recursion needs to have a correct return address.

     > True, implicit tail call optimization is still nicer so I'd still

    > prefer to keep it.

     You can keep it if you implement continuations; you just have to implement

    them a little differently than you're thinking now.

     > Ivan

     -Billy

## e1_t — 2002-07-11 06:19:13

    --- In concatenative@y..., "Billy and Melissa" <wtanksleyjr@c...>

     > > cont does nothing wacky - all it does is it simply discards top n

    > > items from the return stack

    >

    > Ouch. So it's not a continuation operator at all -- it's a forced

     multiple

     > return operator. I assumed that it was actually doing continuation

     work: if

     > so, it would have copied the /n/th item to the top of the rstack,

     not

     > dropped /n/ items. A better name for it would be 'unwind', since it

     unwinds

     > the call chain and forces an exit.

    >

     Seems I messed that up.

     > > (well sort of - because in my current

    > > implementation x' also uses the return stack to save values. cont

    > > takes that into account and makes sure such values are put back

     onto

     > > the data stack even if the return stack has been rearranged).

    >

    > Good deal, makes sense.

    >

    > > cont doesn't take an integer as such - it takes a continuation

     that

     > > is associated with that number - for every nesting level the

     numbers

     > > get incremented. Similarly #dup does not take an integer - it

     takes a

     > > stack associated with that number and duplicates it. Because

     Meta/4

     > > is typeless integers are used as ids for everything - that is

     almost

     > > completely transparent to the programmer unless they're doing

    > > something wrong like using dup to duplicate a stack.

    >

    > Obviously, this integer is NOT transparently associated with a

     specific

     > continuation: you're having problems with it. The reason for this

     is that

     > the continuation is not associated with the number; the number is

     actually a

     > relative index from the current continuation. I repeat: this won't

     work the

     > way you intend it to, except in one special case.

    >

     That's not what I was referring to. I was referring to the fact that

    Meta/4 has no types and that's why it's using integers as ids for

    various things. But I know what you're getting at.

     > > As for saving continuations with labels - I already thought of

     that -

     > > in a concatenative language it would look ugly.

    >

    > Labels need not be textual. They could be anything from an integer

     to a hash

     > code (with a way to input a literal hash code, perhaps like

     Smalltalk's

     > #syntax).

    >

    > Thus, if you have your code:

    >

    > [ something 45 cont dead-code ] x

    >

    > called by a function which looks like this:

    >

    > [ other 45 cont-label other-again yadda ] x

    >

    > ...that '45 cont' will return to the function which most recently

     executed

     > the '45 cont-label'.

    >

     I thought of something similar to that but I decided not to do it

    because it looks ugly (the goto system I was planning to implement is

    also similar to this but it doesn't unwind the return stack).

    What about allowing the use of the word creation word ; (by defining

    it as a macro as well as a word) within the code-stacks/quotations

    themselves? That way execution tokens of words could be used as

    labels. Any thoughts on that?

     > > > It's also a bad idea because it removes a VERY commonly useful

    > > > optimization because a very rare operation is affected by it.

     Even if

     > > > tail-call were at fault, it would still be better to put the

    > > > workaround in cont.

    >

    > > Tail calls/jumps would still be possible - just explicit - I don't

    > > have a problem with that.

    >

    > I do; tail-call elimination is a safe optimization, and if it's not

     working

     > there's something wrong with your code or design.

    >

     Tail call elimination does work in Meta/4. It's just that it can get

    confusing when cont (err.. unwind) is used together with it (because

    tail call elimination would not be transparent to the programmer).

    For that matter even if I didn't include it it could still be done

    through an optimizer that could even be a part of some implementation

    of Meta/4 - the point is that tail call elimination wouldn't be

    guaranteed by Meta/4 itself and the programmer wouldn't be able to

    rely on that.

     > > And recursion would still work the same way

    > > it does now (using recurse - similar to Forth but different in

     that

     > > it performs a jump rather than a call).

    >

    > You mean tail recursion? Yes, that's fine. Many Forth compilers do

     that as

     > well. If you meant that recursion _always_ performs a jump, that

     won't work;

     > recursion needs to have a correct return address.

    >

     Sorry, yes, I was referring to tail recursion. And yes, many Forths

    do implement tail recursion and even tail call elimination (tail

    recursion is just a variation of tail call elimination for that

    matter) but Forth itself doesn't guarantee proper tail recursion

    unlike Scheme for example. A Forth programmer cannot assume Forth is

    going to eliminate tail calls.

    Ivan

## wtanksleyjr@cox.net — 2002-07-11 15:46:39

    From: "e1_t" <e1_t@...>

     > --- In concatenative@y..., "Billy and Melissa"

    > > > As for saving continuations with labels - I already

    > > > thought of that -

    > > > in a concatenative language it would look ugly.

    > > Labels need not be textual. They could be anything from

    > > an integer to a hash

    > > code (with a way to input a literal hash code, perhaps

    > > like Smalltalk's #syntax).

    > What about allowing the use of the word creation word ;

    > (by defining

    > it as a macro as well as a word) within the code-

    > stacks/quotations

    > themselves? That way execution tokens of words could be

    > used as labels. Any thoughts on that?

     I wish I'd thought of that -- great idea. So you're saying that ";" would be like Forth's "[']"?

    This wouldn't be as powerful as allowing arbitrary labels, but it would be generally less riskier.

    (Allowing arbitrary labels would allow you to return to different words, depending on which one called you; it would be kind of like exception handling, so any word could serve as the handler. Using a word's XT as the label requires that only that specific word can handle the 'exception', so it's more like an interrupt handler than an exception.)

     > > > > It's also a bad idea because it removes a VERY

    > > > > commonly useful

    > > > > optimization because a very rare operation is

    > > > > affected by it.

    > > > > Even if

    > > > > tail-call were at fault, it would still be better

    > > > > to put the workaround in cont.

    > > > Tail calls/jumps would still be possible - just

    > > > explicit - I don't have a problem with that.

    > > I do; tail-call elimination is a safe optimization, and

    > > if it's not working

    > > there's something wrong with your code or design.

    > Tail call elimination does work in Meta/4. It's just that

    > it can get

    > confusing when cont (err.. unwind) is used together with

    > it (because

    > tail call elimination would not be transparent to the

    > programmer).

     Again, this is a symptom of a problem in cont. You shouldn't design things so that they can break this easily. Tail-call elimination is safe! Anything that breaks it is itself broken, and has to be rethought.

    Your labelling idea (using a function's own XT as an unwind label) is perfect, and will work around all the problems we were looking at here. It'll also work to make true continuation calls operate better. (A continuation call, as I've mentioned before, returns to a deep return-stack address, but first pushes the current continuation, and doesn't destroy any return stack context.)

    Gosh, I wish I'd thought of that. :-)

    BTW, the effect of a rewind which doesn't find anything would be to clear the return stack and exit; the effect of a continuation call which doesn't find anything would be to simply continue execution.

    I'm thinking now of how to use this... The obvious use is to implement coroutines. The problem is that both words have to know each others' XTs; that's not good. Fortunately, the words can pass each other their XTs, so it's not as bad as it might be.

     > Ivan

     -Billy

## e1_t — 2002-07-12 00:22:28

    --- In concatenative@y..., <wtanksleyjr@c...> wrote:

     > From: "e1_t" <e1_t@y...>

    >

    > > What about allowing the use of the word creation word ;

    > > (by defining

    > > it as a macro as well as a word) within the code-

    > > stacks/quotations

    > > themselves? That way execution tokens of words could be

    > > used as labels. Any thoughts on that?

    >

    > I wish I'd thought of that -- great idea. So you're saying that ";"

     would be like Forth's "[']"?

     >

     Well sort of. Only when it's used from within other code stacks.

    Normally a word is defined as

    [ code ] " word" ;

    If ; is used from within a code stack then it would look something

    like this

    [ code1 [ code2 ] " word1" ; code3 ] " word2" ;

    In this case ; would act as normal ; which creates a word but it

    would also compile word1 in the current code stack as well as compile

    the code to push the xt of word1 onto the return stack.

    Then the xt of word1 could be used as a label:

    [ code4 [ word1 ] unwind-until code5 ] " word3" ;

     > This wouldn't be as powerful as allowing arbitrary labels, but it

     would be generally less riskier.

     >

    > (Allowing arbitrary labels would allow you to return to different

     words, depending on which one called you; it would be kind of like

    exception handling, so any word could serve as the handler. Using a

    word's XT as the label requires that only that specific word can

    handle the 'exception', so it's more like an interrupt handler than

    an exception.)

     >

     I didn't think of that. That's a considerable limitation. A possible

    solution is to make a new word (instead of using ; ) that creates

    temporary words that appear on the heap as opposed to code space -

    during the creation of such words the original stack the token is

    associated with gets saved on the return stack and the new code stack

    that belongs to the newly created word gets associated with the

    token. Using the example above:

    [ code1 [ code2 ] " word1" mark code3 ] " word2" ;

    mark is probably a bad name for the word but it's a bit more

    appropriate then something like label in this case... I'll try to

    think of a better name though.

    Anyway mark is again both a macro and a word - the macro is needed to

    reserve the token and compile the word mark into the current code

    stack (the string " word1" gets replaced with the reserved execution

    token).

    The word mark on the other hand takes a code stack and a token as

    parameters and associates the previously reserved token with the code

    stack while saving the code stack the token previously pointed to.

    mark then executes code2.

    Then word3 could be rewritten as

    [ code4 [ word1 ] unwind-until code5 ] " word3" ;

     >

    > > Tail call elimination does work in Meta/4. It's just that

    > > it can get

    > > confusing when cont (err.. unwind) is used together with

    > > it (because

    > > tail call elimination would not be transparent to the

    > > programmer).

    >

    > Again, this is a symptom of a problem in cont. You shouldn't design

     things so that they can break this easily. Tail-call elimination is

    safe! Anything that breaks it is itself broken, and has to be

    rethought.

     >

     So I should completely drop unwind from Meta/4?

     > Your labelling idea (using a function's own XT as an unwind label)

     is perfect, and will work around all the problems we were looking at

    here. It'll also work to make true continuation calls operate better.

    (A continuation call, as I've mentioned before, returns to a deep

    return-stack address, but first pushes the current continuation, and

    doesn't destroy any return stack context.)

     >

    > Gosh, I wish I'd thought of that. :-)

    >

    > BTW, the effect of a rewind which doesn't find anything would be to

     clear the return stack and exit; the effect of a continuation call

    which doesn't find anything would be to simply continue execution.

     >

    > I'm thinking now of how to use this... The obvious use is to

     implement coroutines. The problem is that both words have to know

    each others' XTs; that's not good. Fortunately, the words can pass

    each other their XTs, so it's not as bad as it might be.

     >

     I already thought of a way to make coroutines and mutually recursive

    words.

    It again involves reserving a token in advance. For example

    " word1" reserve

    [ code word1 code ] " word2" ;

    [ code word2 code ] " word1" ;

    reserve acts a bit like prototypes in C.

    Ivan

## e1_t — 2002-07-13 05:48:49

    Ignore my last post. I wasn't thinking when I wrote that heh - it

    would work but there are heaps of problems with that approach. I

    might in the end have to implement something similar to Scheme's

    call/cc.

    call/cc would be called xcc and would put current continuation on the

    stack which could then be executed with cont.

    I was considering this a while ago but I can't remember what was my

    reason for choosing not to implement it.

    Ivan

## Manfred von Thun — 2002-07-17 05:37:13

    I have been reading this discussion with considerable interest,

    although I could not follow the details properly.

    Do you have any particular kinds of problems/programs in mind?

    It would be interesting to see what you wand to be able to do

    with continuations.

    I have used continuations ony for one kind of problem: backtracking.

    On the Joy page there are now two libraries -

       plglib.joy             propositional logic semantic tableaux

       grmlib.joy             grammar (& regular expression) parsing

    Both use a quotation on top of the stack as continuation, but they

    just use Joy (i.e. Joy1) as is. (But I am also considering

    implementing a new structure, "the continuation stack" which is

    under user control. It would be quite different from the unsuccessful

    "conts" operator which pushed the implicit continuations.)

    Back in the distant past I have used procedures as parameters

    as continuations to implement backtracking in Pascal:

       http://www.latrobe.edu.au/philosophy/phimvt/s00bok.html

    Chapters 8 9 10 11 12 15 16 19 20  and Appendix parts 2..6

    Maybe these could be of interest to you.

      - Manfred

## wtanksleyjr@cox.net — 2002-07-17 15:03:10

    From: Manfred von Thun <phimvt@...>

     > It would be interesting to see what you wand to

    > be able to do with continuations.

     I plan to brag: "Joy, unlike your favorite language,

    supports continuations!" ;-)

     > I have used continuations ony for one kind of problem:

    > backtracking.

     They're also useful for coroutines: functions which work

    together and give the appearance of running simultaneously.

    As a matter of fact, of course, they can do a HUGE amount

    of other things, and it's impossible to say that none of

    the others are useful; coroutines, backtracking, and

    exceptions are just the best known structured ways of

    using them.

     > just use Joy (i.e. Joy1) as is. (But I am also considering

    > implementing a new structure, "the continuation stack"

    > which is under user control.

     Ah, that would be VERY powerful and useful. I highly

    recommend that you read mlg's work on the same topic in

    Forth; he winds up implementing a continuation stack in

    Forth in order to keep continuations separate from >R

    values (roughly equivalent to values saved using

    Joy's "dip"). He's also posted a lot of articles to

    comp.lang.forth, and perhaps he might have some

    interesting insights if we talk to him.

    In fact, why don't I just invite him onto the group?

    Keep in mind that the continuation stack won't add any

    extra space, and may increase speed; you can and should

    use it to store return addresses.

     >   - Manfred

     -Billy

## Billy and Melissa — 2002-07-28 18:54:55

    From: "e1_t" <e1_t@...>

     > --- In concatenative@y..., <wtanksleyjr@c...> wrote:

    > > From: "e1_t" <e1_t@y...>

    > > (Allowing arbitrary labels would allow you to return to different

    > > words, depending on which one called you; it would be kind of like

    > > exception handling, so any word could serve as the handler. Using a

    > > word's XT as the label requires that only that specific word can

    > > handle the 'exception', so it's more like an interrupt handler than

    > > an exception.)

    > I didn't think of that. That's a considerable limitation. A possible

    > solution is to make a new word (instead of using ; ) that creates

    > temporary words that appear on the heap as opposed to code space -

    > during the creation of such words the original stack the token is

    > associated with gets saved on the return stack and the new code stack

    > that belongs to the newly created word gets associated with the

    > token. Using the example above:

    > [ code1 [ code2 ] " word1" mark code3 ] " word2" ;

     This is very limiting as well; the main problem is that it's enormously

    complex. Why not just define a word which returns the hash of a string as an

    integer, and allow arbitrary integers to serve as your labels? If people use

    it enough, or if you need hashes often enough, you can even add some syntax

    to the language to make finding the hash of a static word easier, as in

    Rebol and Smalltalk.

     > Then word3 could be rewritten as

    > [ code4 [ word1 ] unwind-until code5 ] " word3" ;

     The solution I propose would look exactly the same, but it wouldn't require

    a macro+word approach, merely a simple function.

     > > > Tail call elimination does work in Meta/4. It's just that

    > > > it can get

    > > > confusing when cont (err.. unwind) is used together with

    > > > it (because

    > > > tail call elimination would not be transparent to the

    > > > programmer).

    > > Again, this is a symptom of a problem in cont. You shouldn't design

    > > things so that they can break this easily. Tail-call elimination is

    > > safe! Anything that breaks it is itself broken, and has to be

    > > rethought.

    > So I should completely drop unwind from Meta/4?

     Only if you want. Unwind is safe too, as long as it doesn't involve static

    counting of things which can't be generally staticly counted. Using markers

    instead will work perfectly.

     > Ivan

     -Billy

## e1_t — 2002-07-29 00:08:08

    --- In concatenative@y..., "Billy and Melissa" <wtanksleyjr@c...>

    wrote:

     > From: "e1_t" <e1_t@y...>

    > > I didn't think of that. That's a considerable limitation. A

     possible

     > > solution is to make a new word (instead of using ; ) that creates

    > > temporary words that appear on the heap as opposed to code space -

    > > during the creation of such words the original stack the token is

    > > associated with gets saved on the return stack and the new code

     stack

     > > that belongs to the newly created word gets associated with the

    > > token. Using the example above:

    >

    > > [ code1 [ code2 ] " word1" mark code3 ] " word2" ;

    >

    > This is very limiting as well; the main problem is that it's

     enormously

     > complex. Why not just define a word which returns the hash of a

     string as an

    I don't think it's limiting but like I said in my last post - there

    are heaps of problems with this approach.

    That's why I decided to fall back to an implementation of

    continuations that's similar to that found in Scheme. Speaking of

    Scheme I remembered what was my initial reason for abandoning that

    approach (it was the very first I considered..) - the stack could

    very easily get too messy. Thats starting to look like the best

    approach though.

    On another related note, as much as I dislike Forth's locals word set

    I was actually considering implementing something like that in order

    to minimize the pressure on stack - the only difference would be that

    the local variables in Meta/4 would actually be constants as opposed

    to variables (in other words they'd resemble variables found in

    functional languages).

    Through that it would be possible to simulate something similar to

    the system you described. Local variable could for example be bound

    to a continuation so continuation wouldn't have to be kept on stack

    anymore.

    I'm not really happy with this but I can't think of anything better

    right now.

     > integer, and allow arbitrary integers to serve as your labels? If

     people use

     > it enough, or if you need hashes often enough, you can even add

     some syntax

     > to the language to make finding the hash of a static word easier,

     as in

     > Rebol and Smalltalk.

    >

    > > Then word3 could be rewritten as

    > > [ code4 [ word1 ] unwind-until code5 ] " word3" ;

    >

    > The solution I propose would look exactly the same, but it wouldn't

     require

     > a macro+word approach, merely a simple function.

    >

    > > > > Tail call elimination does work in Meta/4. It's just that

    > > > > it can get

    > > > > confusing when cont (err.. unwind) is used together with

    > > > > it (because

    > > > > tail call elimination would not be transparent to the

    > > > > programmer).

    >

    > > > Again, this is a symptom of a problem in cont. You shouldn't

     design

     > > > things so that they can break this easily. Tail-call

     elimination is

     > > > safe! Anything that breaks it is itself broken, and has to be

    > > > rethought.

    >

    > > So I should completely drop unwind from Meta/4?

    >

    > Only if you want. Unwind is safe too, as long as it doesn't involve

     static

     > counting of things which can't be generally staticly counted. Using

     markers

     > instead will work perfectly.

    >

    > > Ivan

    >

    > -Billy

     Ivan

## Manfred von Thun — 2002-08-16 06:28:57

    On Wed, 17 Jul 2002 wtanksleyjr@... wrote:

     > From: Manfred von Thun <phimvt@...>

    >

     [Q&A about continuations]

     > > I have used continuations ony for one kind of problem:

    > > backtracking.

    >

    > They're also useful for coroutines: functions which work

    > together and give the appearance of running simultaneously.

     Yes. I know that this is useful in imperative languages,

    and (I imagine) behind-the-scenes implementation of functional

    languages. But in functional languages there is no notion

    of "running" or of "running simultaneously". [Here I do

    acknowledge having talked with a forked tongue: "Joy is

    purely functional" and "You can think about Joy imperatively"]

    On the web I have also found coroutines used in not-so-pure

    functional languages such as Scheme, Lisp and ML. But it

    is not so easy to determine whether the coroutines there

    use the impure features essentially.

     > As a matter of fact, of course, they can do a HUGE amount

    > of other things, and it's impossible to say that none of

    > the others are useful; coroutines, backtracking, and

    > exceptions are just the best known structured ways of

    > using them.

     Yes. One other I have seen mentioned are generators (in the

    CLU language, for example). They are also implicit in lazy

    data structure, and of course in lazy languages such as Haskell.

    And I saw a quote from McIlroy (the inventor of Unix pipes)

    about pipes and coroutines (but lost the URL).

     > > just use Joy (i.e. Joy1) as is. (But I am also considering

    > > implementing a new structure, "the continuation stack"

    > > which is under user control.

    >

    > Ah, that would be VERY powerful and useful.

     I am still hesitant about that. One reason is that it might

    be better to have a number of general purpose stacks, perhaps

    ten: $0 $1 $2 .. or perhaps 26: $A $B .., which can be given

    application dependent names, e.g.  foo-stack == $7 . But that

    does seem ugly too.

    On the other hand I was very impressed by a paper by P. Landin

    (inventor of the SECD machine):

        "Histories of Discoveries of Continuations", at

         http://dcs.qmul.ac.uk/~peterl/danvy/danvy.html

    Compulsory reading _before_ one even thinks about an implementation!

    Finally, instead of continuation there are always monads, used

    a great deal in Haskell. They do not depend on lazy evaluation,

    and I have seen some implementations in Scheme.

    A good introduction is in an early paper by P.Wadler

         "The essence of Functional Languages",

            search google:  "Wadler Essence Functional" for

            references in print and for the web page (in postscript)

     > I highly

    > recommend that you read mlg's work on the same topic in

    > Forth;

     I did, but as always with Forth, I find it very difficult

     > he winds up implementing a continuation stack in

    > Forth in order to keep continuations separate from >R

    > values (roughly equivalent to values saved using

    > Joy's "dip").

     There will be at least one big difference which might make

    it difficult to transfer ideas from Forth to Joy:

    stacks in the two languages are implemented so differently:

      consecutive memory locations (i.e. "arrays") in Forth

      linked lists (GC'ed) in Joy

     > He's also posted a lot of articles to

    > comp.lang.forth, and perhaps he might have some

    > interesting insights if we talk to him.

    >

    > In fact, why don't I just invite him onto the group?

     Yes, please do.

     > Keep in mind that the continuation stack won't add any

    > extra space, and may increase speed; you can and should

    > use it to store return addresses.

     That would be an implemention that is very different from

    the current one which of course implicitly uses the C-stack for

    return addresses. But I shall try to think about what you

    said in more detail for any future implementation ("threaded

    bytecode" ?)

     > -Billy

     Thanks for this.

      - Manfred

## m_l_g3 — 2002-08-18 18:48:11

    --- In concatenative@y..., "e1_t" <e1_t@y...> wrote:

     > Meta/4 has no continuation stack. I've already seen M. L.

    > Gassanenko's work. From what I recall he only implemented a

    > continuation stack because the return stack isn't sufficient if the

    > programmer also uses it to store temporary data - in Meta/4 that is

    > not a problem anymore - Meta/4 has multiple stacks and the return

    > stack, while it can be accessed, shouldn't be unless the programmer

    > knows what they're doing.

     The reason to introduce the L stack was:

    1. words can call continuation, that is, transfer control forward

    leaving the address-to-backtrack on the return stack

    2. in the general case, you cannot count the items left on the return

    stack: you need to know how such words are defined to know how many

    items are left on the return stack (but in some cases even this

    would not help, different branches of the same definitions may

    use different amounts of r-stack space)

    You cannot count the return stack items even if the programmer

    does not use the return stack to keep data. For example

      ( x y )  {| || BSWAP |}   ( x y | y x )

    \ Use:

    \ : foo {| || BSWAP |} 2DUP SWAP . . SPACE ;

    \ 1 2 foo

    \ prints first 1 2 and then 2 1

    \ (NB: foo does not remove (1,2) from the data stack)

    leaves more return stack items for ( y x ) than for ( x y ),

    because BSWAP (Backtrackable SWAP) leaves one (one?) item on the

    return stack.

    : bar PRO {| || BSWAP |} CONT ;

    works with no problems:

    PRO moves the continuation address onto the L-stack,

    and CONT calls the continuation using the address on the L-stack.

    But this is my CONT, not yours.

     > As for saving continuations with labels - I already thought of that -

    > in a concatenative language it would look ugly.

     Very ugly. Do not do that (universal advice).

     > > > Tail call optimization seems to only complicate things

    > > > and maybe it

    > > > would be better if it was explicit rather than implicit

    > > > in which case

    > > > it would be replaced by a word that transfers control to

    > > > another word rather than calling it.

    > >

    > > This would only solve half of your problem, and really, it would

    > only treat the symptom. The real problem is the false assumption that

    > you can staticly know the contents of the (dynamic) continuation

    > stack.

     With the tail call elimination optimisation, you cannot know

    if the return address is there. This is a problem.

    Words that access return addresses must be marked as non-TCE words.

    You will need a flag in the header (do not forget about ALIASes!

    maybe, this flag must be in some other kind of datastructure)

    and an algorithm that would detect using the return addresses

    while compiling a definition.

    If you build a serious optimizing compiler, this will not

    significanly complicate it; if your compiler is traditionally

    simple (search the dictionary, if found, compile procedures and

    execute control structure words), it is easier to make this

    optimization explicit.

## m_l_g3 — 2002-08-18 19:03:25

    --- In concatenative@y..., <wtanksleyjr@c...> wrote:

     >

    > Again, this is a symptom of a problem in cont. You shouldn't design things so that they can break this easily. Tail-call elimination is safe! Anything that breaks it is itself broken, and has to be rethought.

    >

     Forth is NOT concatenative:

    : foo bar ;

    foo =/= bar

    foo == [r bar EXIT ']

    where [r ... '] stand for return stack nesting.

    Ok, we can have a language with the notation borrowed from mlg's

    theoretical work.

    2DUP == [ OVER OVER ]

    LIT == [r R@ @ R> CELL+ >R EXIT ']

    With this notation,

    foo == [ blah blah foo ]

    would mean that tail call elimination (TCE) is possible,

    while it's evident that for

    myexit == [r RDROP EXIT ']

    TCE would be wrong.

     > Your labelling idea (using a function's own XT as an unwind label) is perfect, and will work around all the problems we were looking at here. It'll also work to make true continuation calls operate better. (A continuation call, as I've mentioned before, returns to a deep return-stack address, but first pushes the current continuation, and doesn't destroy any return stack context.)

    >

    > Gosh, I wish I'd thought of that. :-)

     And if the word does not have an xt because it's inlined?

    Well, the code still has an address, but I dislike the idea.

    You still have an auxiliary value.

    GOTO labels are bad because their names are auxiliary entities.

## e1_t — 2002-08-19 00:16:52

    --- In concatenative@y..., "m_l_g3" <mlg@f...> wrote:

     > --- In concatenative@y..., "e1_t" <e1_t@y...> wrote:

    > > Meta/4 has no continuation stack. I've already seen M. L.

    > > Gassanenko's work. From what I recall he only implemented a

    > > continuation stack because the return stack isn't sufficient if

     the

     > > programmer also uses it to store temporary data - in Meta/4 that

     is

     > > not a problem anymore - Meta/4 has multiple stacks and the return

    > > stack, while it can be accessed, shouldn't be unless the

     programmer

     > > knows what they're doing.

    >

    > The reason to introduce the L stack was:

    >

    > 1. words can call continuation, that is, transfer control forward

    > leaving the address-to-backtrack on the return stack

    >

    > 2. in the general case, you cannot count the items left on the

     return

     > stack: you need to know how such words are defined to know how many

    > items are left on the return stack (but in some cases even this

    > would not help, different branches of the same definitions may

    > use different amounts of r-stack space)

    >

    >

    > You cannot count the return stack items even if the programmer

    > does not use the return stack to keep data. For example

    >

    >   ( x y )  {| || BSWAP |}   ( x y | y x )

    >

    > \ Use:

    > \ : foo {| || BSWAP |} 2DUP SWAP . . SPACE ;

    > \ 1 2 foo

    > \ prints first 1 2 and then 2 1

    > \ (NB: foo does not remove (1,2) from the data stack)

    >

    > leaves more return stack items for ( y x ) than for ( x y ),

    > because BSWAP (Backtrackable SWAP) leaves one (one?) item on the

    > return stack.

    >

    > : bar PRO {| || BSWAP |} CONT ;

    >

    > works with no problems:

    >

    > PRO moves the continuation address onto the L-stack,

    > and CONT calls the continuation using the address on the L-stack.

    >

    > But this is my CONT, not yours.

    >

    > > As for saving continuations with labels - I already thought of

     that -

     > > in a concatenative language it would look ugly.

    >

    > Very ugly. Do not do that (universal advice).

    >

     I don't have your papers or the time right now to remind myself of

    how it all works and what || does but it seems to me this is all

    specific to your implementation of continuations in Forth. Meta/4 is

    not Forth even though it can easily be extended into a fully ANS-

    Forth compliant implementation of it. Doing so however would break

    many of Meta/4's own words. For example while >r does exist in Meta/4

    it's not meant to be used in general programming. While in Forth

    anyone can use >r if they follow a small set of rules, in Meta/4 only

    those familiar with the internals of the specific system they're

    using should use >r (return stack is generally not meant to be

    accessed in Meta/4).

     >r is in fact mostly used by words such as x'.

     Right now I decided to implement something similar to Scheme's

    continuations (slightly less powerfull though).

    Once I get Meta/4 into a fully functional state (functional as in

    working) I'll experiment with other more powerfull methods such as

    yours.

     >

    > > > > Tail call optimization seems to only complicate things

    > > > > and maybe it

    > > > > would be better if it was explicit rather than implicit

    > > > > in which case

    > > > > it would be replaced by a word that transfers control to

    > > > > another word rather than calling it.

    > > >

    > > > This would only solve half of your problem, and really, it

     would

     > > only treat the symptom. The real problem is the false assumption

     that

     > > you can staticly know the contents of the (dynamic) continuation

    > > stack.

    >

    > With the tail call elimination optimisation, you cannot know

    > if the return address is there. This is a problem.

    > Words that access return addresses must be marked as non-TCE words.

    >

     Yes. That's why I came up with all those wacky solutions to the

    problem but as Billy pointed out tail call elimination should be safe

    and transparent (unless it's done explicitly in which case it's more

    like a goto than an optimization).

     > You will need a flag in the header (do not forget about ALIASes!

    > maybe, this flag must be in some other kind of datastructure)

    > and an algorithm that would detect using the return addresses

    > while compiling a definition.

    >

     That would make the system more complicated. I want Meta/4 to be

    small, fast, simple, flexible and reasonably elegant (elegance seems

    to be the biggest problem).

     > If you build a serious optimizing compiler, this will not

    > significanly complicate it; if your compiler is traditionally

    > simple (search the dictionary, if found, compile procedures and

    > execute control structure words), it is easier to make this

    > optimization explicit.

     Eventually I'm planning to write a good multi-pass optimizing

    compiler but not as a part of Meta/4 itself but as an extension (for

    example given a string containing the name of a word it would create

    a new optimized word of the same name - that way proper register

    allocation can be done as well as many inter-procedural

    optimizations - after that the optimized word could be exported into

    a library to be used from within other languages or saved as an

    executable file).

    Finally a few words about the current status of Meta/4. It's now

    almost usable. The two main things that are missing are higher order

    functions and floating point support. I was planning to add the

    latter after Meta/4 is finished. As for higher order functions I just

    have to write a macro version of [ so that it compiles the new

    quotation within the current one (kinda tricky).

    I know I said I'd have it finished soon but since Warcraft 3 came out

    recently and I got a new guitar amp too I haven't really worked on

    Meta/4 as much as I wanted to (yeah, yeah I know... I don't really

    have an excuse..).

    In it's current state programming in Meta/4 should be similar to

    programming in a very primitive Forth. I don't have a web page where

    I could put Meta/4 yet but I'd be glad to send it to anyone who is

    interested in what it looks like (just give me a day or two to write

    up a readme file).

    I still haven't decided on what licence I'm going to release it under

    but it'll probably be a modified BSD licence. Any suggestions?

    Ivan