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