# slash and burn

## stevan apter — 2004-10-14 21:37:42

    > when "the dust has settled".

    >

    >   - Manfred

     here's a shorter, clearer, snappier version of my XY paper.

    i'm thinking of setting it to music.

    although it has a few more lines than slava's Factor paper,

    it contains exactly the same number of non-whitespace tokens,

    which would be pretty amazing if it weren't intentional.

    ------------

    THE CONCATENATIVE LANGUAGE XY

    * Introduction

    XY is a direct descendant of the vector language K and the concatenative

    language Joy.  The basic idea is this:

    Computation consists of a sequence of evaluation steps over a pair of

    objects X and Y.  X is the stack, and contains the entirety of what has

    been computed so far.  Y is the queue, and contains the entirety of what

    remains to be computed.  A step consists of taking the next element in

    the queue and applying it to the stack and the remainder of the queue.

    The result is a new stack and a new queue.

    * K

    The datatypes of XY are those of K:  integer, float, character, symbol,

    dictionary, null, list, and dictionary.

    The elementary operators of XY are the twenty K verbs:

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

    Each verb v has three functional forms:

            v       dyad            3 2 - -> 1      subtract

            v:      monad           2 -: -> -2      negate

            v.      commuted dyad   3 2 -. -> -1    commute subtract

    The atomic verbs automatically pervade their list arguments, iterating

    over corresponding atoms:

            $ % ^ & * - = + | < >

            [1 2 3][4 5 6] + -> [5 7 9]

    The six overloaded adverbs of K,

            ' / \ ': /: \:

    are mapped to distinct XY words:

            '       each

            /       over while do converge

            \       over! while! do! converge!

            ':      prior

            /:      each/

            \:      each\

    K system functions (e.g. _in) and input/output operators (e.g. 3:) are

    also supported.

    * XY

    The operators of Joy are unary functions of the form

            stack -> stack'

    For example, + takes the stack, pops two numbers, adds them, pushes the

    result onto the stack, and returns the modified stack:

            X^n^m -> X^n+m

    The operators of XY are unary functions of the form

            [stack queue] -> [stack' queue']

    A description of evaluation in XY will clarify the difference.

    Initially, the stack X is empty, and the queue Y consists of a sequence

    of elements which are to be processed.  If Y is empty, we are done.

    Otherwise, Y has the form z^Y, where z is the next element to process.

    Processing consists of applying z to the pair [X Y], and obtaining

    [X' Y'] as a result.

    The result of applying z to the pair [X Y] is determined as follows:  if

    z is anything other than a defined symbol, then the result is [X^z Y];

    otherwise, the result is whatever is returned by applying the value of z

    to [X Y].

    Since the queue contains the entirety of what remains to be computed,

    a call to a defined symbol which is not a primitive has the effect of

    pushing that symbol onto the queue, where it might (might!) be evaluated

    at some future point.  XY is therefore "stackless", in the sense that

    evaluation proceeds by passing the current continuation at each step.

    For example, consider the non-terminating recursion 'foo', defined as

    follows:

              ; foo 1 + foo ;

    We trace the first few execution steps:

              10 :trace

    <enter> for next step, any character to exit

              0 foo

                       : 0 foo

                     0 : foo

                     0 : 1 + foo

                   0 1 : + foo

                     1 : foo

                     1 : 1 + foo

                   1 1 : + foo

                     2 : foo

                     2 : 1 + foo

                   2 1 : + foo

                     3 : foo

    * Core

    The words of XY can be sorted into two categories:  those which modify

    only the stack, such as +, and those which modify the queue, and possibly

    the stack as well.

    XY contains four "core" primitives.  Two of them modify the stack and two

    modify the queue:

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

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

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

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

    <- is Joy's 'unstack' word.  It sets the stack to whatever is on top of

    the stack.  For example,

              1 2 [3 4] <-

            3 4

    \ appends to the stack whatever is next on the queue.  For example,

              1 2 \ + 3 4

            1 2 + 3 4

    This has the effect of "escaping" execution.  It has no analogue in Joy.

    -> sets the queue to whatever is on top of the stack.  For example,

              1 2 [+ 4 5 *] -> 10 20 30

            3 9

    As this example shows, -> behaves like an unconditional "go to".  It has

    no analogue in Joy.

    / is Joy's 'i' combinator.  It prepends to the queue whatever is on top of

    the stack.  For example,

              1 2 [+] / 10 20

            3 10 20

    * Patterns

    XY programs are quotations.  For example, when evaluated on a stack whose

    top three elements are numbers a b c,

            [+ *]

    adds b and c and multiples the result by c.  In addition, XY provides two

    words which allows the programmer to deconstruct the stack into two parts:

    some number n of named elements from the top, and whatever remains below

    the n-th element.  For example, the 'swap' word can be defined as follows:

            { [a b] b a }

    It expects two elements a and b on top of the stack.  It pushes b and then

    a onto the remainder.  The expression is an example of an XY stack-pattern.

    A stack-pattern has the form

            { template .. code .. }

    The first element is either an atomic name or a list of of elements, each

    of which is in turn a template.

    Elements are drawn from the stack, mapped to names in the template, and

    then remapped to corresponding names in the code.  The result is appended

    to the remainder of the stack.

    A simple naming convention allows a list to be deconstructed into a fixed

    number of initial elements and the remainder, which is a list.  For

    example, the 'uncons' word is defined as follows:

            { [[a A]] a A }

    Upper-case names may occur only in tail-position in a list, in which case

    as much of the list as possible is mapped to the initial elements of the

    template, and what remains is mapped to the sole upper-case name.

    XY also supports queue-patterns.  A queue-pattern draws elements from the

    stack, populates the template, maps those values to corresponding names in

    the code, and then prepends the result to the queue.  For example, the

    'cons' word is defined:

            {{ [a b] [a] b , }}

    Patterns can nest.  Names are scoped to a single level.

    Within a pattern of either kind, the following names are reserved,

    and have special meanings:

            _x      the stack - the elements mapped to the template

            _y      the queue

            _z      the current pattern

    * Definitions

    Any XY object can be given a name by means of the defining word ;.  For

    example,

            ; plus-times + - ;

    To expunge a definition:

            ; plus-times ;

    The value of an undefined symbol s is s.

    * Scripts

    XY code can be stored in a file and loaded either at the beginning of a

    session:

            k xy my.xy

    or in the course of execution:

            "my.xy" :load

    By default, the script xy.xy is loaded at the very beginning of a session.

    Currently, xy.xy establishes the following modules:

            stack           the basic Joy stack words, e.g. 'dup'

            monads          keywords for K monads, e.g. 'where' for '&:'

            dot             K amend and dmend

            adverbs         XY definitions for K adverbs

            joy             XY definitions for Joy combinators

            call            call with current/partial continuation

            io              input-output convenience words

            misc            miscellaneous

    Comments are prefixed by //.

    Script evaluation is aborted by \\ in the first column of a line.

    * Four Programming Examples

    Factor's '>r' and 'r>' words:

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

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

    Joy's 'dip' and 'step' combinators:

            ; dip           swap => i <= ;

            ; step          {{ [a p] a [a uncons p dip p _z] [] if }} ;

    call/cc in XY:

            ; call/cc       {{ [q n] [_x _y n continue/cc] q i }} ;

            ; continue/cc   {{ [x y n] x <- n -: _x # i y -> }} ;

    Conway's "Game of Life":

            ; pad           2 [0 [,.] 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

    * Implementation

    XY is implemented in about 200 lines of K, including whitespace and

    comments.

    * Links

    XY hompage:     http://www.nsl.com/k/xy/xy.htm

## Narcoleptic Electron — 2004-10-14 23:20:14

    This might be my first post to the list.  If so: hi,

    everybody!

    --- stevan apter <sa@...> wrote:

     > The datatypes of XY are those of K:  integer, float,

    > character, symbol,

    > dictionary, null, list, and dictionary.

     You forgot "dictionary".

    --- stevan apter <sa@...> wrote:

     >           1 2 [+ 4 5 *] -> 10 20 30

    >         3 9

     I may have misunderstood:

    1 2 [+ 4 5 *] -> 10 20 30

    => 1 2 + 4 5 *

    => 3 4 5 *

    => 3 20

    I haven't read the rest yet, but the stuff I have read

    so far is fantastic.  Great language, and the wording

    of your document has become much clearer since the

    previous version.

    Cheers,

    N. Electron

    ______________________________________________________________________

    Post your free ad now! http://personals.yahoo.ca

## stevan apter — 2004-10-14 23:27:20

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

    From: "Narcoleptic Electron" <narcoleptic_electron@...>

    To: <concatenative@yahoogroups.com>

    Sent: Thursday, October 14, 2004 7:20 PM

    Subject: Re: [stack] slash and burn

    >

    > This might be my first post to the list.  If so: hi,

    > everybody!

    >

    > --- stevan apter <sa@...> wrote:

    > > The datatypes of XY are those of K:  integer, float,

    > > character, symbol,

    > > dictionary, null, list, and dictionary.

    >

    > You forgot "dictionary".

    >

    > --- stevan apter <sa@...> wrote:

    > >           1 2 [+ 4 5 *] -> 10 20 30

    > >         3 9

    >

    > I may have misunderstood:

    no, you haven't.  thanks.

    >

    > 1 2 [+ 4 5 *] -> 10 20 30

    > => 1 2 + 4 5 *

    > => 3 4 5 *

    > => 3 20

    >

    > I haven't read the rest yet, but the stuff I have read

    > so far is fantastic.  Great language, and the wording

    > of your document has become much clearer since the

    > previous version.

    thanks again.

    >

    > Cheers,

    > N. Electron

    >

    > ______________________________________________________________________

    > Post your free ad now! http://personals.yahoo.ca

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >