# partial continuations

## stevan apter — 2004-09-25 18:59:30

    here's a stab at implementing my best understanding of the idea.

    in XY, the total current continuation is the whole stack X and the

    whole queue Y.  suppose we are able to mark how far back in the

    stack we want to go, and how far forward in the queue we want to

    go:

        X'^m^X Y^m^Y'

    then [X Y] is a partial continuation.

    pc expects two objects on the stack:  a mark object, and a

    quotation.  it constructs a triple

        [X Y cont/pc]

    where X is the stack back to the mark object (or the whole stack,

    if the mark object isn't found), and Y is the queue ahead to the

    mark object (or the whole queue if the mark object isn't found.)

    cont/pc is the same as cont/rc in the my previous message.

    ; pc {{ [m q] [_x m -take _y m take cont/pc] q i }} ;

    ; cont/pc {{ [x y] x i y i }} ;

    ; test-pc

      ["inside" print$ "tpc" .s] pc

      "resuming" print$ ;

    ; call-pc

      tpc

      "exiting call-pc" print$ ;

    i'll use 99 as the mark object:

      10 20 99 1 2 3 99 test-pc * + 99 30 40 50

               ^^^^^^^^         ^^^

    inside

    resuming

    10 20 99 7 99 30 40 50

      clear

      tpc

    resuming

    7

      clear

      10 20 30 tpc 40 50 60

    resuming

    10 20 30 7 40 50 60

     ----- Original Message -----

    From: "stevan apter" <sa@...>

    To: <concatenative@yahoogroups.com>

    Sent: Saturday, September 25, 2004 12:03 PM

    Subject: Re: [stack] XY: final draft

    >

    > ----- Original Message -----

    > From: "William Tanksley, Jr" <wtanksleyjr@...>

    > To: <concatenative@yahoogroups.com>

    > Sent: Thursday, September 23, 2004 3:15 PM

    > Subject: Re: [stack] XY: final draft

    >

    >

    > > On Wed, 22 Sep 2004 18:55:23 -0400, stevan apter <sa@...> wrote:

    > > > i've posted the "final" draft on my website:

    > > >     www.nsl.com/k/xy/xy.htm

    > >

    > > I think you've really got something there, stevan. Your notation and

    > > explanations make sense, and have clarified some of the things I was

    > > having a hard time explaining for Forth.

    > >

    > > Now that you've mastered continuations, are you ready to take on

    > > partial continuations? A normal continuation allows you to use "the

    > > rest of the current computation"; partial continuations, on the other

    > > hand, allow you to define exactly what you mean by the "current

    > > computation". See http://citeseer.ist.psu.edu/queinnec91dynamic.html

    > > for a detailed, formal look at this.

    > >

    > > I know how to implement partial continuations in Forth -- you just

    > > copy items off of the return stack and into an array, and stop copying

    > > when you reach the start of the partial continuation (marking the

    > > start is a different issue, of course). How would you handle them in

    > > XY?

    >

    > perhaps you can tell me, since i don't understand the scheme treatment,

    > even after reading chris's excellent presentation.

    >

    > consider a simplified version of call/cc:

    >

    > ; cc {{ [q] [_x _y cont/cc] q i }} ;

    >

    > cc takes a quotation q and executes it on the triple consisting of the

    > current stack _x, the current queue _y, and the program cont/cc.

    >

    > cont/cc is:

    >

    > ; cont/cc {{ [x y] x <- y -> }} ;

    >

    > cont/cc makes x the current stack and y the current queue.

    >

    > consider the following test devised by chris for factor:

    >

    > ; test-cc

    >   ["inside" print$ "tcc" .s] cc

    >   "resuming" print$ ;

    >

    > ; call-cc

    >   tcc

    >   "exiting call-cc" print$ ;

    >

    >   test-cc

    > inside

    > resuming

    >

    >   tcc

    > resuming

    >

    >   call-cc

    > resuming

    >

    > if, instead of replacing the current stack and queue with x and y,

    > we append x to the current stack and prepend y to the current queue:

    >

    > ; rc {{ [q] [_x _y cont/rc] q i }} ;

    > ; cont/rc {{ [x y] x i y i }} ;

    >

    > ; test-rc

    >   ["inside" print$ "trc" .s] rc

    >   "resuming" print$ ;

    >

    > ; call-rc

    >   trc

    >   "exiting call-rc" print$ ;

    >

    >   test-rc

    > inside

    > resuming

    >

    >   trc

    > resuming

    >

    >   call-rc

    > resuming

    > exiting call-rc  <---- nb, copare with call-cc

    >

    > cont/rc embeds the old stack and queue x and y in the current

    > stack and queue X and Y:

    >

    >     XXXXXXXXXxxxxxxxx yyyyyyyyyYYYYYYYYYY

    >

    > as chris points out, the main reason for partial continuations

    > is efficiency:  partial continuations are smaller than (in my

    > framework) the whole stack and the whole queue.  but i don't

    > understand the principle behind 'splitter' well enough to design

    > something analogous for XY.

    >

    > >

    > > -Billy

    > >

    > >

    > >

    > >

    > > Yahoo! Groups Links

    > >

    > >

    > >

    > >

    > >

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

## William Tanksley, Jr — 2004-09-26 06:17:07

    On Sat, 25 Sep 2004 14:59:30 -0400, stevan apter <sa@...> wrote:

     > in XY, the total current continuation is the whole stack X and the

    > whole queue Y.  suppose we are able to mark how far back in the

    > stack we want to go, and how far forward in the queue we want to

    > go:

    >     X'^m^X Y^m^Y'

    > then [X Y] is a partial continuation.

     Yes, that's essentially correct.

    One minor uncertainty from me, though: I'm not certain that you need

    to save the state of the stack. It may often be handy; it's not

    neccesary, and if I were coding a primitive I wouldn't make it part of

    the primitive, because it isn't always needed, and when it IS needed

    it can be handled as a seperate operation without loss of generality.

    Otherwise, I think you've got it; and even if you disagree with me,

    well, you're still right and it'll still work :-).

    -Billy

## sa@dfa.com — 2004-09-26 14:03:21

    "William Tanksley, Jr" <wtanksleyjr@...> wrote on 09/26/2004 02:17:07

    AM:

     > On Sat, 25 Sep 2004 14:59:30 -0400, stevan apter <sa@...> wrote:

    > > in XY, the total current continuation is the whole stack X and the

    > > whole queue Y.  suppose we are able to mark how far back in the

    > > stack we want to go, and how far forward in the queue we want to

    > > go:

    > >     X'^m^X Y^m^Y'

    > > then [X Y] is a partial continuation.

    >

    > Yes, that's essentially correct.

    >

    > One minor uncertainty from me, though: I'm not certain that you need

    > to save the state of the stack. It may often be handy; it's not

    > neccesary, and if I were coding a primitive I wouldn't make it part of

    > the primitive, because it isn't always needed, and when it IS needed

    > it can be handled as a seperate operation without loss of generality.

    >

    > Otherwise, I think you've got it; and even if you disagree with me,

    > well, you're still right and it'll still work :-).

     the implementation is not quite right, but it wasn't obvious at first.

    pc should be:

          ; pc {{ [m q] _x m -take_ _y m take_ pair \cont/pc , q i }} ;

    that is, take back to m on the stack (_x), take forward to m on the queue

    (_y), make a pair [x y], append the cont/pc function (note the use of \

    to block evaluation), then evaluate the quotation q.

    take_ and -take_ drop the mark object from the chunk taken.

    so:

      10 20 99 1 2 3 99 test-pc * + 99 30 40 50

    inside

    resuming

    10 20 7 30 40 50

      clear

      "tpc" .g

    [[1 2 3] ["resuming" print$ * +] cont/pc]

      clear

      tpc

    resuming

    7

      clear

      17 18 call-pc 19 20

    resuming

    exiting call-pc

    17 18 7 19 20

     >

    > -Billy

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

## sa@dfa.com — 2004-10-01 15:42:45

    http://www.nsl.com/k/xy/life.xy

    --

    ; pad           2 [0 swap [,] each/ 0 [,] each\ +:] do ;

    ; l             1 !. ;

    ; r             -1 !. ;

    ; adj           [[[r] map! r]

                     [[r] map! l]

                     [[l] map! r]

                     [[l] map! l]

                     [[l] map!  ]

                     [[r] map!  ]

                     [r         ]

                     [l         ]] [i] each/ ;

    ; next          adj uncons ,: [+] over dup 3 = [2 = &] dip | ;

    ; life          [.i "" ~] [next dup " *" @. .o] while ;

    ; rpent0        [[1 0 0][1 1 1][0 1 0]] ;

    rpent0 5 [pad] do life

    --

    'pad' takes a matrix and wraps it in 0's:

          [[1 2 3][4 5 6]] pad

        [[0 0 0 0 0][0 1 2 3 0][0 4 5 6 0][0 0 0 0 0]

    'l' shifts a list one position left, 'r' one position right:

          [1 2 3] l

        [2 3 1]

    'adj' takes a matrix x and produces eight matrices, each of which

    shifts one of the 8 neighbors of x i j into position i j.

    'next' computes the next generation of a life universe:  x next i j

    is 1 if x i j is 1 and has exactly 2 neighbors or x i j has exactly

    3 neighbors.

    'life' waits for input at the console.  if the user types any character,

    it exits.  else it computes and prints the next generation.

    'rpent0' is an initial life pattern.

    'rpent0 5 [pad] do life' wraps rpent0 in a 5 0's and runs the game.

    --

         *

         * *

         ***

          *

        ** *

         * *

          *

         **

        ** *

        ** *

          *

        ***

           *

        *  *

         **

         *

         **

        *  *

         * *

         **

         **

        ***

        *  *

        ** *

         **

        * *

        *  *

       *   *

        *  *

        ***

         *

       *****

       ** ***

       **  *

        ***

         *

         *

       *    *

      *     *

            *

       *  *

        ***

           ***

           *

        * **

        ***

         *

            *

           **

        *  *

        *  *

        ***

## phimvt@lurac.latrobe.edu.au — 2004-10-12 06:52:21

    I found a paper again which I think is compulsory reading

    for anyone interested in conntinuations - at least the

    first paragraph is worth thinking about:

        Peter Landin        (the "inventor" of the SECD machine)

          "Histories of Discoveries of Continuations"

    (Google will find it from the three nouns in the title

     - there is a pdf file if you like that sort of thing,

    but also Google's text version)

      - Manfred