RE: [stack] continuations in a tiny concatenative language
Tanksley, William D. Jr. — 2003-08-19 16:58:03
From: stevan apter [mailto:
sa@...]
>i've implemented a tiny concatenative language which contains first-
>class continuations.
Are you sure they're first-class, since you can't manipulate them? All you
can do is overwrite your saved continuation with the current continuation or
call the saved continuation (BTW, "current continuation" is a misnomer for
this; your 'cc' word actually saves the current continuation, but once saved
it's no longer current).
>as in the unlambda interpreter, russ's approach to O(1) joy gave me
>the key (pass the result stack and the input stack to all programs,
>modify one or both as needed.)
A facinating approach. Before I examine it, may I ask: is the name "result
stack" already too well established to fight? I find it atrocious when used
for a stack that contains input and output to functions, doubly so when
juxtaposed with a data structure called the "input stack". My preference
would be to call it the "data stack".
In fact, I would effectively have three stacks: a data stack (your result
stack), a program stack (your input stack), and a continuation stack (your
continuation variable, in the most recent version of your language actually
a stack variable stored on K's hidden call stack). 'cc' would copy the
entire program stack onto the continuation stack; 'c' would overwrite the
program stack with the popped head of the continuation stack; and 'getc'
would pop the continuation stack onto the data stack (where the normal swap,
etc. operators could act on it); naturally, 'putc' would be needed to store
and use the result.
My implementation, as usual, won't do exactly this. Let me provide a little
background. I apologise in advance for destroying your sanity, but:
http://citeseer.nj.nec.com/hieb93subcontinuations.html
http://citeseer.nj.nec.com/queinnec91dynamic.html
Rather than having three stacks, I'll only have two: a data stack and a
return marker stack. The 'program stack' will be replaced by the normal
execution mechanism of typical CPUs; the "return marker stack" will be used
to hold return addresses for the CPU AND "continuation markers". My
equivalent to 'cc' will place a continuation marker on the return marker
stack; my equivalent to 'c' will pop the marker stack until it finds a
marker, and then it'll return to the indicated address.
Finally, I'll have a wordset that allocates memory and stores an entire
continuation in it, popping it from the return stack; that'll require a
variable amount of memory depending on the number of return addresses in the
return stack. That'll allow me to treat partial continuations as first-class
data.
-Billy
sa@dfa.com — 2003-08-19 19:00:24
From: stevan apter [mailto:
sa@...]
>i've implemented a tiny concatenative language which contains first-
>class continuations.
Are you sure they're first-class, since you can't manipulate them? All you
can do is overwrite your saved continuation with the current continuation
or
call the saved continuation (BTW, "current continuation" is a misnomer for
this; your 'cc' word actually saves the current continuation, but once
saved
it's no longer current).
my writing got ahead of my code (the paper's not done, and
neither is the coding.) of course you're absolutely right.
in fact, you'll notice 'cc' is now "cache continuation"
and 'c' is "continue". but i've had it in mind from the
outset that i would make the underlying object first-class
only when i wanted to do something for which 'cc' and 'c'
wouldn't suffice, at which point i would implement 'gc'
and 'sc',
nice to see that you're anticipating me here!
>as in the unlambda interpreter, russ's approach to O(1) joy gave me
>the key (pass the result stack and the input stack to all programs,
>modify one or both as needed.)
A facinating approach. Before I examine it, may I ask: is the name "result
stack" already too well established to fight? I find it atrocious when used
for a stack that contains input and output to functions, doubly so when
juxtaposed with a data structure called the "input stack". My preference
would be to call it the "data stack".
yes, i see why you prefer the latter, but i find it a bit too
abstract, and besides, what i'm calling the input stack also
contains data. i'm halfway persuaded ..
In fact, I would effectively have three stacks: a data stack (your result
stack), a program stack (your input stack), and a continuation stack (your
continuation variable, in the most recent version of your language actually
a stack variable stored on K's hidden call stack). 'cc' would copy the
entire program stack onto the continuation stack; 'c' would overwrite the
program stack with the popped head of the continuation stack; and 'getc'
would pop the continuation stack onto the data stack (where the normal
swap,
etc. operators could act on it); naturally, 'putc' would be needed to store
and use the result.
as near as i can tell, this is the suite of four functions i've
been thinking about. (nb: in the current version on my website,
i've eliminated global C - everything got much simpler as a result.)
My implementation, as usual, won't do exactly this. Let me provide a little
background. I apologise in advance for destroying your sanity, but:
http://citeseer.nj.nec.com/hieb93subcontinuations.html
http://citeseer.nj.nec.com/queinnec91dynamic.html
Rather than having three stacks, I'll only have two: a data stack and a
return marker stack. The 'program stack' will be replaced by the normal
execution mechanism of typical CPUs; the "return marker stack" will be used
to hold return addresses for the CPU AND "continuation markers". My
equivalent to 'cc' will place a continuation marker on the return marker
stack; my equivalent to 'c' will pop the marker stack until it finds a
marker, and then it'll return to the indicated address.
Finally, I'll have a wordset that allocates memory and stores an entire
continuation in it, popping it from the return stack; that'll require a
variable amount of memory depending on the number of return addresses in
the
return stack. That'll allow me to treat partial continuations as
first-class
data.
-Billy
To unsubscribe from this group, send an email to:
concatenative-unsubscribe@egroups.com
Your use of Yahoo! Groups is subject to
http://docs.yahoo.com/info/terms/
Tanksley, William D. Jr. — 2003-08-19 21:25:33
From:
sa@... [mailto:
sa@...]
>From: stevan apter [mailto:sa@...]
> and 'c' is "continue". but i've had it in mind from the
> outset that i would make the underlying object first-class
> only when i wanted to do something for which 'cc' and 'c'
> wouldn't suffice, at which point i would implement 'gc'
> and 'sc',
> nice to see that you're anticipating me here!
Hey, you're way further ahead of me -- you've actually implemented this.
I've only done mockups under Forth. And like you, I only plan to make these
first-class when I actually have to :-).
>A facinating approach. Before I examine it, may I ask: is the
>name "result stack" already too well established to fight? I
>find it atrocious when used
>for a stack that contains input and output to functions, doubly so when
>juxtaposed with a data structure called the "input stack". My
>preference would be to call it the "data stack".
> yes, i see why you prefer the latter, but i find it a bit too
> abstract, and besides, what i'm calling the input stack also
> contains data. i'm halfway persuaded ..
The "input stack" is only input from a narrow point of view: that of the
compiler. From any other POV, it's the instruction stack (or something like
that). The "result stack" doesn't contain only results, and in fact its main
purpose is to contain intermediates, not results. I wouldn't mind too much
if you named it accordingly...
But Forth tradition is still to call it the Data Stack.
>In fact, I would effectively have three stacks: a data stack
>(your result
>stack), a program stack (your input stack), and a continuation
>stack (your
>continuation variable, in the most recent version of your
>language actually
>a stack variable stored on K's hidden call stack). 'cc' would copy the
>entire program stack onto the continuation stack; 'c' would
>overwrite the
>program stack with the popped head of the continuation stack;
>and 'getc'
>would pop the continuation stack onto the data stack (where the normal
>swap,
>etc. operators could act on it); naturally, 'putc' would be
>needed to store and use the result.
> as near as i can tell, this is the suite of four functions i've
> been thinking about. (nb: in the current version on my website,
> i've eliminated global C - everything got much simpler as
> a result.)
Yes, I noticed -- as I wrote, you're now storing the saved continuations on
K's call stack, disguised as a parameter to a function. Clever and logical,
and will result in fast speeds than otherwise, since K is written to make
that kind of thing fast.
My system is actually faster, but that's only because I'm dropping to
assembler for tricky things like that.
-Billy
stevan apter — 2003-08-19 22:29:48
----- Original Message -----
From: "Tanksley, William D. Jr." <william.d.tanksley.jr@...>
To: <concatenative@yahoogroups.com>
Sent: Tuesday, August 19, 2003 5:25 PM
Subject: RE: [stack] continuations in a tiny concatenative language
> From: sa@... [mailto:sa@...]
> >From: stevan apter [mailto:sa@...]
> > and 'c' is "continue". but i've had it in mind from the
> > outset that i would make the underlying object first-class
> > only when i wanted to do something for which 'cc' and 'c'
> > wouldn't suffice, at which point i would implement 'gc'
> > and 'sc',
> > nice to see that you're anticipating me here!
>
> Hey, you're way further ahead of me -- you've actually implemented this.
> I've only done mockups under Forth. And like you, I only plan to make these
> first-class when I actually have to :-).
the thing is, i can't see what to do with them once they are
first class (i am so example driven).
anyway, if you look at what i've put in tck in the last few
minutes, you'll see two versions of cc/c/gc/sc. both versions
use the triple
(atrocious-stack;instruction-stack;continuations)
but in one version, cc builds z = continuations recursively:
()
(x1;y1;z1)
(x2;y2;(x1;y1;z1))
:
and in the other, cc prepends the current continuation to
a stack z:
()
,(x1;y1;z1)
((x2;y2;z2);(x1;y1;z1))
(of course there's a c, gc, and sc for each structure).
both approaches "work" within the narrow range of my examples,
but i can't decide which is the "right" one, although i think
i marginally prefer the former, but purely on aesthetic
grounds. it would be nice to have an argument.
>
> >A facinating approach. Before I examine it, may I ask: is the
> >name "result stack" already too well established to fight? I
> >find it atrocious when used
> >for a stack that contains input and output to functions, doubly so when
> >juxtaposed with a data structure called the "input stack". My
> >preference would be to call it the "data stack".
>
> > yes, i see why you prefer the latter, but i find it a bit too
> > abstract, and besides, what i'm calling the input stack also
> > contains data. i'm halfway persuaded ..
>
> The "input stack" is only input from a narrow point of view: that of the
> compiler. From any other POV, it's the instruction stack (or something like
> that). The "result stack" doesn't contain only results, and in fact its main
> purpose is to contain intermediates, not results. I wouldn't mind too much
> if you named it accordingly...
>
> But Forth tradition is still to call it the Data Stack.
i'm still hunting for the mot juste here (that exhausts my french).
>
> >In fact, I would effectively have three stacks: a data stack
> >(your result
> >stack), a program stack (your input stack), and a continuation
> >stack (your
> >continuation variable, in the most recent version of your
> >language actually
> >a stack variable stored on K's hidden call stack). 'cc' would copy the
> >entire program stack onto the continuation stack; 'c' would
> >overwrite the
> >program stack with the popped head of the continuation stack;
> >and 'getc'
> >would pop the continuation stack onto the data stack (where the normal
> >swap,
> >etc. operators could act on it); naturally, 'putc' would be
> >needed to store and use the result.
>
> > as near as i can tell, this is the suite of four functions i've
> > been thinking about. (nb: in the current version on my website,
> > i've eliminated global C - everything got much simpler as
> > a result.)
>
> Yes, I noticed -- as I wrote, you're now storing the saved continuations on
> K's call stack, disguised as a parameter to a function. Clever and logical,
> and will result in fast speeds than otherwise, since K is written to make
> that kind of thing fast.
>
> My system is actually faster, but that's only because I'm dropping to
> assembler for tricky things like that.
i'm really looking forward to studying the prototype. i hope you
have time to work on it once the diapers start flying .. :)
>
> -Billy
>
>
> To unsubscribe from this group, send an email to:
> concatenative-unsubscribe@egroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
Ivan Tomac — 2003-08-19 23:31:36
--- In
concatenative@yahoogroups.com, "Tanksley, William D. Jr."
<william.d.tanksley.jr@s...> wrote:
>
> My implementation, as usual, won't do exactly this. Let me provide
a little
> background. I apologise in advance for destroying your sanity, but:
> http://citeseer.nj.nec.com/hieb93subcontinuations.html
> http://citeseer.nj.nec.com/queinnec91dynamic.html
>
Interesting. I'll have to read those papers sometime.
> Rather than having three stacks, I'll only have two: a data stack
and a
> return marker stack. The 'program stack' will be replaced by the
normal
> execution mechanism of typical CPUs; the "return marker stack"
will be used
> to hold return addresses for the CPU AND "continuation markers". My
> equivalent to 'cc' will place a continuation marker on the return
marker
> stack; my equivalent to 'c' will pop the marker stack until it
finds a
> marker, and then it'll return to the indicated address.
>
An old version of Meta/4 does something like that. I don't know if
you had a look at it yet but cont and xcc words in prim3.inc pretty
much work in the way you described.
I've given up on that for now though. For interpretation I believe
using 3 stacks has a few advantages (simplicity and clarity are
probably the main ones). And for compiled programs I'm thinking
about trying to optimize the code to eliminate continuations
possibly at the expense of code size. I haven't really thought about
it that much yet though. I'll probably go for some hybrid approach
in the end as some continuations would probably be too difficult to
replace with conventional structures depending on how the code is
written.
> -Billy
Ivan
Tanksley, William D. Jr. — 2004-01-20 19:51:22