# XY

## stevan apter — 2004-07-18 16:51:21

    hi all

    this is an interim report on some work i've been doing on a new

    (toy) language, which i'm calling 'xy'.  the code is here:

    www.nsl.com/k/xy/xy.k

    xy is written in k (naturally), and has the atoms, lists, and

    verbs of k.  the look and feel of the notation is joy-like.

    all the stack-riented words are defined in terms of extended

    stack notation.  semicolons enclose associations of a name and

    a definition.  e.g.

    ; swap          { [a b] b a } ;

    ; pick          { [a b c] a b c a } ;

    ; car           { [[a A]] a } ;

    ; cdr           { [[a A]] A } ;

    ; cons          { [a b] [a] b , } ;

    ; uncons        { [[a A]] a A } ;

    i've adopted several definitions of slava's, which you can see

    at:

    www.nsl.com/k/xy/xy.xy

    the car of one of these definitions is a pattern, and the cdr

    is code containing elements of the pattern.

    the underlying xy machinery consists of a result stack x and an

    input queue y, hence the name 'xy'.

    within one of these definitions, the symbol _x denotes the

    result, and _y denotes the input queue.

    all xy primitives access both x and y, although some, like +,

    make no use of y.  among the primitives are:

    \s        like joy's "unstack"

    "clear the result stack" is defined:

    ; \c            [] \s ;

    the equivalent of joy's "stack" word is:

    ; \g            { [] \c _x } ;

    a parameterized callcc is:

    ; callcc        { [q n] [_x _y n continue] q i } ;

    ; continue      { [x_ y_ n] \c x_ i n -: _x  # i y_ /s } ;

    ; callcc0       0 callcc ;

    ; callcc1       1 callcc ;

    a working xy version of chris's parlor-trick factor-exercise can

    be found here:

    www.nsl.com/k/xy/stuff/choose.xy

    www.nsl.com/k/xy/stuff/parlortrick.xy

    'i' and 'ifte' are the only primitive combinators.  xy definitions

    for linrec, infra, and cond:

    ; linrec        { [c t e f] c i c t e f _x linrec_ } ;

    ; linrec_       { [b c t e f x] x \s b t [e i c t e f linrec f i] ifte } ;

    ; infra         pair \g |: uncons |: / |: \s |: \g |: uncons , i i \g unit \ swap , \s ;

    ; cond          { [a] a #: 1 = [a *:] [a [0 0] . i a [0 1] . 1 a _ _x cond_] ifte } ;

    ; cond_         { [b t e x] x \s b t [e cond] ifte } ;

    xy doesn't have anything like a "return stack", but it's pretty

    convenient to have something like factor's >r and r>.  that is,

    an operator to take a value from the stack and stash it somewhere

    out of the way, and then later recall it to the stack.

    my solution is to have / and \ (the equivalents of >r and <r)

    use *the other end* of the input queue y, as though it was a stack.

    for that reason, y has the characteristics of both a queue AND a

    stack.  a colleague suggested that i call it a "quack".

    here's an example:

      "2dip" def

    -rot / / i \ \

      clear

      1 trace 2 3 111 222 [+] 2dip

                                             : 1 trace 2 3 111 222 [+] 2dip

                                           1 : trace 2 3 111 222 [+] 2dip

                                             : 2 3 111 222 [+] 2dip

                                           2 : 3 111 222 [+] 2dip

                                         2 3 : 111 222 [+] 2dip

                                     2 3 111 : 222 [+] 2dip

                                 2 3 111 222 : [+] 2dip

                             2 3 111 222 [+] : 2dip

                             2 3 111 222 [+] : -rot / / i \ \

                             2 3 111 222 [+] : { [a b c] c a b } / / i \ \

                                         2 3 : [+] 111 222 / / i \ \

                                     2 3 [+] : 111 222 / / i \ \

                                 2 3 [+] 111 : 222 / / i \ \

                             2 3 [+] 111 222 : / / i \ \

                                 2 3 [+] 111 : / i \ \ 222

                                     2 3 [+] : i \ \ 222 111

                                     2 3 [+] : // \ \ 222 111

                                         2 3 : + \ \ 222 111

                                           5 : \ \ 222 111

                                       5 111 : \ 222

    5 111 222

    / and \ cache to and from the end of the input queue.

    // takes the top of the result stack, quotes it, and pushes it back

    onto the front of the input queue, so that it will be the next item

    processed.

    \\ takes the next item on the input queue (the one about to be

    processed) and pushes it onto the result stack.  for example,

      2 3 \\ + //

                                             : 2 3 \\ + //

                                           2 : 3 \\ + //

                                         2 3 : \\ + //

                                       2 3 + : //

                                         2 3 : +

    5

    // is actually a generalization of the 'i' combinator:

      2 3 [+] //

                                             : 2 3 [+] //

                                           2 : 3 [+] //

                                         2 3 : [+] //

                                     2 3 [+] : //

                                         2 3 : +

    5

## Slava Pestov — 2004-07-19 02:32:11

    Hi Steve,

    Good to hear about your experiments with concatenative languages again!

     > ; cons          { [a b] [a] b , } ;

     I don't understand this.

     > the car of one of these definitions is a pattern, and the cdr

    > is code containing elements of the pattern.

     Does this mean code can be inspected and constructed at runtime?

     > a parameterized callcc is:

    >

    > ; callcc        { [q n] [_x _y n continue] q i } ;

    > ; continue      { [x_ y_ n] \c x_ i n -: _x  # i y_ /s } ;

    >

    > ; callcc0       0 callcc ;

    > ; callcc1       1 callcc ;

     Nice!

     > // takes the top of the result stack, quotes it, and pushes it back

    > onto the front of the input queue, so that it will be the next item

    > processed.

    >

    > \\ takes the next item on the input queue (the one about to be

    > processed) and pushes it onto the result stack.  for example,

     Interesting.

    I notice your language has side effects (variable assignment). What made

    you choose this approach, compared to your earlier cK (which if I recall

    was purely functional)?

    Slava

## stevan apter — 2004-07-19 10:08:39

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

    From: "Slava Pestov" <slava@...>

    To: <concatenative@yahoogroups.com>

    Sent: Sunday, July 18, 2004 10:32 PM

    Subject: Re: [stack] XY

    > Hi Steve,

    >

    > Good to hear about your experiments with concatenative languages again!

    >

    >

    > > ; cons          { [a b] [a] b , } ;

    >

    > I don't understand this.

    cons expects two items on the stack, a and b:

        [a b]

    what it will leave on the stack is

        [a] b ,

    the join of the enlist of a with b.  alternatively:

        [unit] dip ,

    (but don't be misled into thinking that these are factor's "cons

    cells".  they're not.  e.g.

        10 20 cons

    [10 20]

        10 [20] cons

    [10 20]

    i debated about whether to error trap the first case, the way

    joy does:

        { [a b] b list? [[a] b ,] ["not a list" error] ifte }

    then decided it wasn't necessary at this stage.)

    >

    > > the car of one of these definitions is a pattern, and the cdr

    > > is code containing elements of the pattern.

    >

    > Does this mean code can be inspected and constructed at runtime?

    you mean, can {}-expressions be constructed?  yes, for example,

      1 trace

      10 20 [ { ] i [a b] b a }

                                             : 10 20 [{] i [a b] b a }

                                          10 : 20 [{] i [a b] b a }

                                       10 20 : [{] i [a b] b a }

                                   10 20 [{] : i [a b] b a }

                                   10 20 [{] : // [a b] b a }

                                       10 20 : { [a b] b a }

                                             : 20 10

                                          20 : 10

    20 10

    as in joy and factor, programs-as-lists can also be constructed

    and manipulated at run-time, then executed with 'i'.

    >

    > > a parameterized callcc is:

    > >

    > > ; callcc        { [q n] [_x _y n continue] q i } ;

    > > ; continue      { [x_ y_ n] \c x_ i n -: _x  # i y_ /s } ;

    > >

    > > ; callcc0       0 callcc ;

    > > ; callcc1       1 callcc ;

    >

    > Nice!

    >

    > > // takes the top of the result stack, quotes it, and pushes it back

    > > onto the front of the input queue, so that it will be the next item

    > > processed.

    > >

    > > \\ takes the next item on the input queue (the one about to be

    > > processed) and pushes it onto the result stack.  for example,

    >

    > Interesting.

    >

    > I notice your language has side effects (variable assignment). What made

    > you choose this approach, compared to your earlier cK (which if I recall

    > was purely functional)?

    i added .s and .g (your 'set' and 'get') in order to make chris's

    continuation exercises work.  i don't regard either one as essential

    vocabulary.

    >

    > Slava

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

## stevan apter — 2004-07-20 22:27:40

    i've fixed a few bugs, and further trimmed the set of primitives.

    here they are:

    k: ~!@#$%^&*_-+=|<,>?.:

       f  dyad

       f: monad

       f. commute dyad

    k system functions, n:, &c.

    ( )     comment      2 3 ( not executed ) + -> 5

    { }     pattern-set  { [a b] a b + a * }

    {{  }}  pattern-get  {{ a [b] [c d] }}

    /s      stack        1 2 3 /s 4 5 6 -> 1 2 3 [4 5 6]

    \s      queue        1 2 3 \s 4 5 6 -> 1 2 3 [1 2 3] 4 5 6

    \\      quote        1 2 3 \\ + -> 1 2 3 +

    //      unquote      1 2 3 [+] // -> 1 5

    /       cache        1 2 3 / 4 5 6 -> 1 2 4 5 6 3

    \       uncache      1 2 3 / 4 \ 5 6 -> 1 2 4 3 5 6

    ;       define       ; inc 1 + ;

    :       amend        [1 2 3] 1 99 @ -> [1 99 3]

    .s      set          [-1 +] "dec" .s

    .g      get          "dip" .g -> [swap / i \]

    .p      parse        "[1 2 3]" .p -> [[1 2 3]]

    .r      represent    [[1 2 3]] .r -> "[1 2 3]"

    .i      read         10 .i -> 10 "what you type"

    .o      write        "print this" write

    words   word-list    words -> [@4 .4 @3 .3 exit ..

    error   error        "signal this message" error

    stop    stop         2 3 stop + -> stops before + in console

    trace   trace        1 trace -> print step and wait for <enter>

    trap    trap         0 trap -> on error, go idle

    exit    exit

    k       exit to k

    i believe that this is sufficient to define all the joy combinators.

    for example:

    ; infra         { [a p] \g / a p , i \g \ \g |: uncons , i } ;

## stevan apter — 2004-07-20 23:45:54

    oops - a few mistakes in the earlier draft.

    ---------

    xy primitives:

    k: ~!@#$%^&*_-+=|<,>?.:

       f  dyad

       f: monad

       f. commute dyad

    system functions, n:, &c.

    ( )     comment      2 3 ( not executed ) + -> 5

    { }     pattern-set  { [a b] a b + a * }

    {{  }}  pattern-get  {{ a [b] [c d] }}

    \s      stack        1 2 [4 5 6] \s -> 4 5 6

    /s      queue        1 2 3 /s 4 5 6 -> 1 2 3

    \\      quote        1 2 3 \\ + -> 1 2 3 +

    //      unquote      1 2 3 [+] // -> 1 5

    /       cache        1 2 3 / 4 5 6 -> 1 2 4 5 6 3

    \       uncache      1 2 3 / 4 \ 5 6 -> 1 2 4 3 5 6

    ;       define       ; inc 1 + ;

    :       amend        [1 2 3] 1 99 : -> [1 99 3]

    .s      set          [-1 +] "dec" .s

    .g      get          "dip" .g -> [swap / i \]

    .p      parse        "[1 2 3]" .p -> [[1 2 3]]

    .r      represent    [[1 2 3]] .r -> "[1 2 3]"

    .i      read         10 .i -> 10 "what you type"

    .o      write        "print this" write

    words   word-list    words -> [@4 .4 @3 .3 exit ..

    error   error        "signal this message" error

    stop    stop         2 3 stop + -> stops before + in console

    trace   trace        1 trace -> print step and wait for <enter>

    trap    trap         0 trap -> on error, go idle

    exit    exit

    k       exit to k