# 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

    http://www.ps.uni-sb.de/~duchier/python/continuations.html

    ...if you're still working with continuations...

    Hey, I just "sold" someone on K and J. He's an ardent Forther, so perhaps

    he'll be able to do what I haven't yet had time to look at (explore

    concatenative vector languages).

    -Billy