# pattern-matching in XY

## stevan apter — 2004-10-27 00:06:41

    i've implemented a slightly simplified version of {{ in XY.

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

    first, matching a template to a list:

      [10 20 30] [a$ b$ c$] from

    [[a$ b$ c$] [10 20 30]]

    the result is a pair of equal-length lists [symbols values].

      [10 [20 30] [40 50 60 70] 80] [a$ b$ [c$ D$] e$] from

    [[a$ b$ c$ D$ e$] [10 [20 30] 40 [50 60 70] 80]]

    the code:

    ; from          {{ [s t] [[] s] [t] [from.] over first reverse flip }} ;

    ; from.         {{ [[r s] t] t atom? [r s t from-atom] [r s t from-list] if }} ;

    ; from-list     {{ [r s t] r s first pair t [from.] over first 1 s _ pair }} ;

    ; from-atom     {{ [r s t] t upper? [r s t from-A] [r s t from-a] if }} ;

    ; from-a        {{ [r s t] s uncons [t swap pair r cons] dip pair }} ;

    ; from-A        {{ [r s t] [t s] r cons [] pair }} ;

    mapping a symbol-value pair into code:

      [10 20 30] [a$ b$ c$] [a$ b$ + c$ *] pattern

    [10 20 + 30 *]

    the rest of the code:

    ; pattern       {{ [s t c] s t from c into }} ;

    ; into          {{ [[s v] c] S/ [s v] c into. S\ first }} ;

    ; into.         {{ [[s v] c] \c atom? [v \c , s \c ? @] [[s v] \c [_z] each/] if }} ;

    using << and >> to simulate {{ and }}:

      10 20 30 40 50 << [a$ b$ c$] a$ b$ + c$ * >> 60 70 80

    10 20 3500 60 70 80

    the code for that:

    ; <<            {{ [] c\ _x _y >> take-drop <<. -> }} ;

    ; <<.           {{ [x [t C] y] x t <<.. t C pattern 1 y _ , }} ;

    ; <<..          {{ [x t] 0 x count t count - pair x _ i [i] dip }} ;

    ; >>            ;

## sa@dfa.com — 2004-10-27 17:00:21

    in the latest release of XY, i've swapped the meanings of { and {{.

    for example,

          {{ [a] a a }}

    is 'dup', and

          { [a b] a b + }

    is 'plus'.

    i've swapped the meanings for two reasons:

    1. as slava pointed out when he removed his version of stack notation

    from Factor, {{ has limited utility:  it picks off some number of

    items from the stack, and then pushes some new arrangement of some or

    all of them back onto the stack.  in XY, as in Factor, i use {{ only

    to define a dozen or so elementary stack-shuffling words, and, very

    rarely, to do something unusual on-the-fly.  {, on the other hand,

    is used very frequently:  it picks some number of items from the stack,

    intermixes them with code, and pushes the result *onto the queue*,

    where they will be evaluated.  hence the redefinition reduces typing

    overall.

    2. one may always replace a { definition with a {{ definition by

    escaping every token.  e.g.

          {{ [a] a a }}

    is semantically equivalent to

          { [a] \a \a }

    so '{{' conveys the idea of quotation, or "escape", as in '"'.

    the revised documentation is

          http://www.nsl.com/xy/xy.txt

    i'll send the text to the list tonight (my mail program at work

    will probably wrap the text.)

    so now i'm thinking that perhaps i should swap the meanings of

    + and - .. (just kidding)

## Narcoleptic Electron — 2004-10-27 18:16:17

    --- sa@... wrote:

     > http://www.nsl.com/xy/xy.txt

     Not found...

    ______________________________________________________________________

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

## sa@dfa.com — 2004-10-27 18:47:02

    sorry:

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

    Narcoleptic Electron <narcoleptic_electron@...> wrote on 10/27/2004

    02:16:17 PM:

     >

    > --- sa@... wrote:

    > > http://www.nsl.com/xy/xy.txt

    >

    > Not found...

    >

    > ______________________________________________________________________

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

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >

## sa@dfa.com — 2004-10-28 15:00:37

    after thinking about it a bit more, i've come to the conclusion

    that supporting two forms of pattern notation when one will do

    is wasteful.  accordingly, i've dumped the {{ form.

    this also allowed me to shrink the implementation code.  for

    those who might be interested, XY now consists of exactly 26

    functions, a through z, all but two of which consist of a single

    line.  sadly, the parser requires 13 lines and the representer 10.

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

    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,

    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 20

    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, the quotation

            [+ *]

    adds b and c and multiplies the result by c.

    XY supports "pattern notation".  A pattern consists of a list, possibly

    nested, of names, followed by a sequence of XY tokens, the whole enclosed

    in curlies:

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

    The initial list is called the "template" and the sequence following that

    up to the closing curly is called the "code".

    '{' is a primitive word, and is defined as follows.  Map elements from the

    top of the stack into names occurring in the template.  Map those values

    into corresponding names occurring in the code.  '{' returns a new stack

    and a new queue.  The new stack is the old stack minus the mapped elements,

    and the new queue is the mapped code prepended to the old queue minus the

    pattern.

    A simple naming convention allows a list on the stack 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.

    Within a pattern, the following names are reserved:

            _x      the stack minus the elements mapped to the template

            _y      the queue minus the current pattern

            _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:

              2 3 + undefined 6 7

            5 undefined 6 7

    * 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 two positions 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 -> } ;

    Infix K notation to postfix:

            ; infix         enlist [infix.] infra ;

            ; infix.        [[[count 2 <] first] [[first sym?] monad] [dyad]]

    cond ;

            ; dyad          { [[x f Y]] x infix. Y infix. \f } ;

            ; monad         { [[f X]] X infix. \f string ': , .g } ;

    * Implementation

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

    comments.

    * Links

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