# eager lists in XY

## stevan apter — 2004-09-19 14:13:22

    my description of eager lists in XY was incorrect.

        (X)

    is recursively transformed at parse-time to

        [[X]] [i] infra

    so that

        (1 2 +)

    yields

        [3]

## sa@dfa.com — 2004-09-20 13:16:44

    Barring unpleasant discoveries, i imagine this is close to a final draft.

    i've filled out the "programming in XY" section with an implementation of

    Factor's >r and r>.

                    THE CONCATENATIVE PROGRAMMING LANGUAGE XY

                                        *

                                  (SECOND DRAFT)

    * Introduction

    XY is a concatenative programming language with roots in Joy and K.

    The elements of XY are unary functions, each of which takes and returns

    a pair of the form:

            [stack queue]

    The stack is a list which represents the past of the computation.

    The queue is a list which represents the future of the computation.

    XY is written in K in continuation-passing style.

    The datatypes of XY are the atoms and lists of K:  integers, floats,

    characters, symbols, dictionary, null, and lists.

    The 20 K verbs are the primitive functions of XY:

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

    * Notation

    Words are separated by blanks:

            12 4 + *

    Blanks are not necessary when using punctuation symbols:  {, ], (, and ).

            [1 2 3[4 5]]

    Characters:

            'a

    Strings:

            "abc\"def"

    A string is a list of characters:

              'a'b'c

            "abc"

              *:

            'a

    If v is a verb, then v denotes the associated dyadic function, v: denotes

    the the associated monad, and v. denotes the commute of the dyad.  For

    example,

            x y -           // x minus y

            x -:            // negate x

            x y -.          // y minus x

    * Constants

            _n              // null

            `               // empty symbol

            0V              // empty integer vector

            0v              // empty float vector

            0`              // empty symbol vector

            0I              // max int

            0i              // infinity

            -0I             // 1+min int

            -0i             // negative infinity

            0N              // min int

            0n              // NaN

    * Lists and Quotations

    XY supports both lazy lists ("quotations") and eager lists.

    Quotations are written using square brackets:

              [2 3 +]

            [2 3 +]

    Eager lists are written using parentheses:

              (2 3 +)

            [5]

    An eager list such as (2 3 +) is recursively transformed at parse-time

    into the expression

              [[2 3 +]] [i] infra

    * Evaluation

    In the course of execution, XY has two objects:  a list of values X and

    a list of tokens z^Y, where z is the next token to be processed and Y

    is a list of the remaining tokens.  X is the result stack and Y is the

    input queue.  Evaluation of z consists of applying z to the list [X Y].

    The result of the application is a new stack X' and a new queue Y'.

    z is either an atom or a list.  An atom is either an integer, a float,

    a character, a dictionary, null, or a symbol.  A symbol is either

    defined or undefined.

    If z is anything other than a defined symbol, its evaluation rule is:

            [X z^Y] -> [X^z Y]

    That is, z is removed from the queue and appended to the stack.

    XY maintains a dictionary W which maps symbols to evaluation rules. For

    each defined symbol, there is an evaluation rule in W.  For example, the

    evaluation rule for the primitive + is:

            [X^x1^x2 Y] -> [X^x1+x2 Y]

    That is, + takes X^x1^x2 and Y, pops x1 and x2, adds them, appends the

    result to X, and returns the new stack and the unaltered queue Y.

    * Projection

    Primitives like + and patterns like { [a b c] b a c } have valence:

    + has valence 2:  it expects at least two values on the stack.  If

    the stack contains fewer than the expected number of values, the

    function is projected onto the available values to produce a closure:

              c\ +

            [+]

              c\ 2 3 { [a b c] b a c }

            [2 3 { [a b c] b a c }]

    * Core

    <-    stack                     [X^z Y] -> [z Y]

            <- replaces the stack with the item found at the top

            of the stack:

              10 20 [2 3 +] <-

            2 3 +

            <- is Joy's "unstack" operator.

    ->    queue                     [X^z Y] -> [X z]

            -> replaces the queue with the item found at the top

            of the stack:

              10 20 [2 3 +] -> 30 40 50

            10 20 5

            -> has no analogue in Joy.

    /     use                       [X^z Y] -> [X z^Y]

            / prepends to the queue the item found at the top of the stack.

              10 20 [2 3 +] / 30 40 50

            10 20 5 30 40 50

            / is Joy's "i" combinator.

    \     mention                   [X z^Y] -> [X^z Y]

            \ appends to the stack the item found at the top of the queue.

              10 20 \ + 30 40

            10 20 + 30 40

            \ has no analogue in Joy.

    ;     define                    [X name^..code..^;^Y] -> [X Y]

              ; add-mul + * ;

              2 3 4 add-mul

            14

            All definitions in XY are inline.

    {     stack pattern             [X template^..code..^}^Y] -> [X^Z Y]

            { matches names in the template to elements on the stack, and

            then substitutes those values for matching names in the code.

            _x denotes the stack and _y the queue as they are at run-time.

            The result of the subtitution Z is appended to the stack:

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

            10 20 30 30 20

    {{    queue pattern             [X template^..code..^}}^Y] -> [X Z^Y]

            {{ matches and substitutes like {, but instead of appending

            the result to the stack, it prepends it to the queue:

              10 20 30 {{ [a b] a b + a * }}

            10 1000

    * Periphery

    The following words are included in the current implementation, but are not

    used.

    .a    amend                     shallow amend with assignment: @[x;y;:;z]

    .d    dmend                     deep amend with assignment: .[x;y;:;z]

    .g    get                       "name" .g -> value of name

    .s    set                       value "name" .s -> associate name with

    value

    .p    parse                     invoke the XY parser

    .r    represent                 invoke the XY representation function

    .i    input                     accept input to the stack

    .o    output                    produce output from the stack

    .e    execute alternate         evaluate P, if that fails evaluate Q

    .xy   XY                        evaluate X and z^Y.

    * Scripts

    XY supports scripts.  An XY script is a text file which contains XY code.

    Typically, the filename ends in ".xy", although this is not necessary.

    On initialization, XY loads the system script xy.xy, which contains core

    definitions, including stack manipulation words like dup and swap, K

    adverbs

    like over, each, and prior, and Joy combinators like linrec and dip.

    Comments are written using //:

            // this is a comment

    A comment ends at the next newline.

    * Programming in XY

    In Factor, the words >r and r> are used to store and retrieve items from

    the

    stack.  The analogous words in XY are => and <=, which use the tail of the

    queue instead of a separate stack:

    =>    cache                     [X^z Y] -> [X Y^z]

            => appends to the queue the item found at the top of the stack.

              10 20 => 30 40

            10 30 40 20

    <=    uncache                   [X Y^z] -> [X^z Y]

            <= appends to the stack the item found at the end of the queue.

              10 <= 30 40 20

            10 20 30 40

    These words are defined in XY as follows:

            ; =>            {{ [] _y |: cons |: -> }} ;

            ; <=            {{ [] _y |: uncons |: -> }} ;

    Here's a trace, which shows how they operate:

      1 2 3 => 4 5 <= 6 7 8

                                             : 1 2 3 => 4 5 <= 6 7 8

                                           1 : 2 3 => 4 5 <= 6 7 8

                                         1 2 : 3 => 4 5 <= 6 7 8

                                       1 2 3 : => 4 5 <= 6 7 8

                                       1 2 3 : {{ [a] a _y |: cons |: -> }} 4 5

    <= 6 7

                                         1 2 : 3 [4 5 <= 6 7 8] |: cons |: -> 4

    5 <= 6

                                       1 2 3 : [4 5 <= 6 7 8] |: cons |: -> 4 5

    <= 6 7

                        1 2 3 [4 5 <= 6 7 8] : |: cons |: -> 4 5 <= 6 7 8

                        1 2 3 [8 7 6 <= 5 4] : cons |: -> 4 5 <= 6 7 8

                        1 2 3 [8 7 6 <= 5 4] : {{ [a b] [a] b , }} |: -> 4 5 <=

    6 7 8

                                         1 2 : [3] [8 7 6 <= 5 4] , |: -> 4 5

    <= 6 7 8

                                     1 2 [3] : [8 7 6 <= 5 4] , |: -> 4 5 <= 6

    7 8

                      1 2 [3] [8 7 6 <= 5 4] : , |: -> 4 5 <= 6 7 8

                        1 2 [3 8 7 6 <= 5 4] : |: -> 4 5 <= 6 7 8

                        1 2 [4 5 <= 6 7 8 3] : -> 4 5 <= 6 7 8

                                         1 2 : 4 5 <= 6 7 8 3

                                       1 2 4 : 5 <= 6 7 8 3

                                     1 2 4 5 : <= 6 7 8 3

                                     1 2 4 5 : {{ [a] a _y |: uncons |: -> }} 6

    7 8 3

                                       1 2 4 : 5 [6 7 8 3] |: uncons |: -> 6 7

    8 3

                                     1 2 4 5 : [6 7 8 3] |: uncons |: -> 6 7 8

    3

                           1 2 4 5 [6 7 8 3] : |: uncons |: -> 6 7 8 3

                           1 2 4 5 [3 8 7 6] : uncons |: -> 6 7 8 3

                           1 2 4 5 [3 8 7 6] : { [[a A]] a A } |: -> 6 7 8 3

                           1 2 4 5 3 [8 7 6] : |: -> 6 7 8 3

                           1 2 4 5 3 [6 7 8] : -> 6 7 8 3

                                   1 2 4 5 3 : 6 7 8

                                 1 2 4 5 3 6 : 7 8

                               1 2 4 5 3 6 7 : 8

                             1 2 4 5 3 6 7 8 :

    1 2 4 5 3 6 7 8

    * Implementation

    At the present time, the implementation consists of a single script

    containing 185 lines, including whitespace and comments.

    The K process contains 27 named objects:

      h W w g s l k j v u c d m q n o P p L r T t a e S i f

    K functions (there are 22 of them) are uniformly lower-case, thus allowing

    room for future enhancements.  (That's a K joke.)

    Interpretation in XY consists of the standard read-eval-print loop.  The

    three steps correspond to three functions:  the parser p, the evaluator e,

    and the function r, which takes a list (either the stack or the queue) and

    represents it as a string, suitable for printing.

    The evaluator takes a stack x and a queue to be evaluated y:

      e:{({if[T>0;t[x;y]];a[*y,();x,()](1_ y),()}.)/(x;y)}

    e repeatedly evaluates x and y until either of the following conditions

    occurs:  either the result of the evaluation matches the previous result,

    or the result of the evaluation matches the initial values of x and y.

    At each step, e checks to see whether the trace variable T is positive.

    If it is, it displays the current states of x and y:

      t:{if[(#x)|#y;`0:(40$r x)," : ",-40$r y;:[#y;if[#0:`;T::0];`0:,""]]}

    It then applies the following algorithm:  if the queue is empty or the

    stack is null, it returns the current stack and queue; else if the next

    element to be evaluated is not a defined symbol, it appends it to the stack

    and returns that and the queue; else it applies the evaluation rule for

    that symbol:

    a:{:[(~#z)&_n~x;(y;z);~4=4:x;(y,,x;z);(#**W)=i:W[0;0]?x;(y,x;z);W[1;i][y;z]]}

    * To do

      - Can { and {{ be defined in terms of the remaining primitives?

    * Links

    XY: http://www.nsl.com/papers/xy.htm.

    K: http://www.kx.com

## sa@dfa.com — 2004-09-20 13:27:10

    i guess a few lines wrapped in what i sent.

    see http://www.nsl.com/k/xy/xy.txt for a good text version.

## Slava Pestov — 2004-09-20 22:09:12

    sa@... wrote:

     > * Projection

    >

    > Primitives like + and patterns like { [a b c] b a c } have valence:

    > + has valence 2:  it expects at least two values on the stack.  If

    > the stack contains fewer than the expected number of values, the

    > function is projected onto the available values to produce a closure:

     I'm curius as to what this can be used for.

    Slava

## stevan apter — 2004-09-20 23:35:34

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Monday, September 20, 2004 6:09 PM

    Subject: Re: [stack] XY: second draft

    > sa@... wrote:

    > > * Projection

    > >

    > > Primitives like + and patterns like { [a b c] b a c } have valence:

    > > + has valence 2:  it expects at least two values on the stack.  If

    > > the stack contains fewer than the expected number of values, the

    > > function is projected onto the available values to produce a closure:

    >

    > I'm curius as to what this can be used for.

    me too.  :)

    >

    > Slava

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

## stevan apter — 2004-09-21 12:27:31

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Monday, September 20, 2004 6:09 PM

    Subject: Re: [stack] XY: second draft

    > sa@... wrote:

    > > * Projection

    > >

    > > Primitives like + and patterns like { [a b c] b a c } have valence:

    > > + has valence 2:  it expects at least two values on the stack.  If

    > > the stack contains fewer than the expected number of values, the

    > > function is projected onto the available values to produce a closure:

    >

    > I'm curius as to what this can be used for.

    in my first implementation, projection built nested quotations which

    are "inside-out" with respect to execution:

      2 + *

    [[2 +] *]

    this is less useful than just appending the unsatisfied operator to

    the last item on the stack:

      2 + *

    [2 + *]

      3 swap i

    [5 *]

      4 swap i

    20

      2 {{ [a b c] b c + a * }}

    [2 {{ [a b c] b c + a * }}]

      3 swap i

    [3 2 {{ [a b c] b c + a * }}]

      4 swap i

    20

      2 {{ [a b] a b + }} {{ [a b] a b * }}

    [2 {{ [a b] a b + }} {{ [a b] a b * }}]

      3 swap i

    [5 {{ [a b] a b * }}]

      4 swap i

    20

    my initial thought was projection provides greater "regularity" than

    a stack underflow error, that it might offer the possibility of useful

    programming techniques.  but i haven't found the time to explore the

    idea.

    >

    > Slava

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >