# Re: [stack] X: an update

## stevan apter — 2004-11-22 22:29:31

    my mail program at work has the irritating (and apparently

    incurable) habit of wrapping lines.  of course, it knows

    better than i do about where the text should be broken.

    let me try once more.

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

    THE CONCATENATIVE LANGUAGE X (Draft)

    * Introduction

    X is a new installment in concatenative vector language project.

    X borrows code and ideas from the language XY, but departs in certain respects

    from that earlier language.

    Whereas in XY, the programmer has access to the entirety of the result stack

    and the input queue, in X, explicit access to the queue is blocked, and stack

    manipulation is limited to what can be expressed by the use of finite patterns.

    Otherwise, the most striking difference between the two languages is that all

    combinators in X are treated as adverbs.  An adverb is a function which takes

    one or two quotations off the stack and derives from them a function which is

    then prepended to the queue.  X functions are not first-class. That is, in X

    there is no way to construct an arbitrary function, nor is there any way to

    leave a function on the stack.

    * Notation

            "abc"    a string

            'a       a character

            10       integer

            10.2     float

            10:      negative integer

            10.2:    negative float

            [a 10]   lazy list (quotation)

    A name begins with a-zA-Z, followed by characters drawn from a-zA-Z, dot, and

    colon.  For example, the following are valid names:

            a

            a:

            a.b.c:

            a..foo:bar..

    Note that

            a12b

    is parsed as

            a 12 b

    That is, a name, followed by an integer, followed by a name.

    * Datatypes

    The elementary datatypes of X are integer, float, character, symbol, and list.

    Note that "abc" is a list of characters, that is

            ['a 'b 'c]

    is identical to

            "abc"

    * Verbs

    A verb is a function from elementary datatypes to elementary datatypes.  18

    of the 20 K verbs are verbs of X:

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

    Each verb has three forms:

            @       dyad

            @:      monad

            @.      commuted dyad

    All but one of the X verbs retain their K meanings.  The exception is that

    dyadic '@' has been mapped to dyadic '.'.  That is, x y @ has the K meaning:

            x . y

    X doesn't require the following K verbs:

            .:      execute, make/unmake dictionary, &c.

            @       at

            :       x:y -> y

            ::      ::x -> x

    * Definition

    Inline definition in X is the same as it is in XY:

            ;x A;   define x as A

            ;x;     undefine x

    * Trains

    One of the principal motivations for X is to explore the consequences of

    introducing into K the concept of a verb-train, or "train" for short.

    In K, it is possible to construct a limited subset of compositions.  A valid

    K composition has one of the following two forms:

            m..mm

            m..md

    where 'm' is a monad and 'd' is a dyad.  For example, the following are

    valid K compositions:

            *|:     first (of the) reverse (of)

            *|      first (of the) minimum (of)

    Only the final verb of the composition requires the monadic qualifier ":".

    All verbs preceding the final verb are assumed to be monads.

    In X, any quotation consisting entirely of verbs is a valid train:

            [^:+*]

    * Adverbs

    X has six adverbs.  These have been mapped to the "mated" characters as

    follows:

            X       K       name

            -       -       ----

            (       ':      prior

            )       '       each

            {       \:      each-left

            }       /:      each-right

            \       \       scan

            /       /       over

    For example, polyadic 'each':

            [1 2 3][4 5 6][+])

    ) takes the quotation at the top of the stack, derives a function which adds

    corresponding elements of [1 2 3] and [4 5 6], and returns [5 7 9].

    In X, the valence of the derived function determines how many arguments it

    will consume from the stack.  For example, [+] has valence 2, so [+]) will

    consume two lists.  Since [+*] has valence 3, it expects three arguments on

    the stack:

            [1 2 3][4 5 6][7 8 9][+*])

    The monadic form of an adverb derives a function which expects to find its

    arguments packaged in a single list:

            [[1 2 3][4 5 6][7 8 9]][+*]):

    * Evaluation

    X has integers, floats, characters, symbols, and lists, but it does not have

    derived functions as a first-class datatype.  This implies that at every

    point in the course of evaluation, every object on the stack is one of the

    primitive datatypes enumerated above.

    Although the X programmer has no access to the queue (the list of elements

    yet to be evaluated), the X interpreter does.  Think of the state of X at any

    point in time as consisting of

            X z^Y

    where X is the stack, z^Y is the queue, and z is the next element on the

    queue to evaluate.  The evaluator A examines z:

    If z is defined symbol, A applies it to X and Y, which yields a new stack X'

    and a new queue Y'.  There are two cases:

      - If z is a verb, for example +, then Y' = Y and X' = the

        result of applying + to X.

      - If z is an adverb, for example ), then X' = X minus the

        quotation Q on top and Y' = the result of prepending the

        derived function Q) onto the queue.

    If z is not a defined symbol, there are two cases:

      - If z is not a derived function, then X' = X^z.

      - If z is a derived function, then A applies it to the top

        element of the stack.  There are two cases:

        - The result r is a derived function, in which case

          Y' = r^Y.

        - The result r is not a derived function, in which

          case X' = X^r.

    In the course of repeated passes of the evaluator, a derived function on the

    queue keeps consuming arguments from the stack until its valence is reached.

    For example, [+*]) has valence 3, so it will take three passes before it

    finally returns something which is not a function, at which point that result

    is pushed onto the stack.

    * Combinators

    The valence of a function is the number of arguments it takes.  The charge

    of a function is the number of results it returns.

    K verbs have valence 1 or 2, and charge 1.  K adverbs derive functions which

    have valence v > 0 and charge 1.  but stack-based languages require operations

    which, implicitly or explicitly, permute elements of the stack.  For example,

    'dup' has valence 1 and charge 2, 'swap' has valence 2 and charge 2, and the

    valence and charge of 'i' vary, depending on the quotation 'i' finds at the

    top of the stack.

    X has two combinators:

            `       pattern

            `:      i

    `: is the familiar Joy disquotation combinator:

              10 20 30[+*]`:

            500

    'pattern' is similar to the { combinator found in XY:

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

            [30 10]

    It expects a pair of quotations on the stack.  The first quotation is a list,

    possibly nested, of undotted names.  The second quotation is a list, possibly

    nested, containing some or all of the names in the first quotation, possibly

    repeated, intermixed with other elements.  ` takes the two quotations and

    derives a function.

    The derived function has the following behavior:  Values are drawn in order

    from the stack and mapped to names in the first quotation.  Those values are

    then mapped to corresponding names in the second quotation.

    When the first first quotation is non-empty, the result is a list:

              10 20 30[a b][b a]

            10 30 20

    When the first quotation is empty, the function returned by ` is the 'dip'

    combinator:

              10 20 30 100[][+*]`

            500 100

    In combination with `:, ` is powerful enough to derive the standard swap- and

    list-manipulation words.  For example,

            ;dup[a][a a]`i;

            ;swap[a b][b a]`i;

            ;zap[a][]`i;

            ;uncons[[a A]][a A]`i;

    * Examples

## sa@dfa.com — 2004-11-23 15:46:03

    i was concerned that i hadn't left myself enough "syntactic space"

    to permit comments and end-of-file, but i discovered last night

    that the two syncategorematic particles . and : work just fine for

    these purposes:

          2 3 + . abort evaluation up to the next newline

    and in a script:

          2 3 +

          4 5 *

          :

          abort evaluation within this script

          none of these lines are interpreted

    there's no ambiguity.

    . and : serve other purposes:

    1) negative numbers have a trailing :

    2) monadic verbs and adverbs have a trailing :

    3) the commute of a dyadic verb or adverb has a trailing .

    4) . and : can be used in names as just another character

    1) is a bit "non-standard", but i'm growing to like it.

    it's a pain to have remember to use a space to distinguish

          2 3 - 4

    and

          2 3 -4

    i'm also finding that having the commuted form available is extra-

    handy.  of course, you can always replace

          2 3 -.

    with

          2 3 swap -

    but for adverbs, it allows something closer to infix form:

          [1 2 3] [4 5 6] [+] )

    is equivalent to:

          [1 2 3] [+] [4 5 6] ).

    i've rewritten most of the X summary, and that can be found here:

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

    sections on performance and examples are in the works.  i'm

    starting to think that X is perhaps a little less toy-like than

    i first imagined.

    comments, criticisms, questions, or suggestions welcome.

## William Tanksley, Jr — 2004-11-23 16:50:15

    On Tue, 23 Nov 2004 10:46:03 -0500, sa@... <sa@...> wrote:

     > sections on performance and examples are in the works.  i'm

    > starting to think that X is perhaps a little less toy-like than

    > i first imagined.

     It looks Forthlike. (From me, there's no higher praise. ;-)

    Seriously, though, it looks like a nice design. I especially like how

    you've designed it to precisely fit the environment in which it

    executes, and yet provide more features and a totally different feel

    than that environment.

    -Billy

## stevan apter — 2004-11-23 20:45:47

    >

    > . and : serve other purposes:

    >

    > 1) negative numbers have a trailing :

    > 2) monadic verbs and adverbs have a trailing :

    > 3) the commute of a dyadic verb or adverb has a trailing .

    > 4) . and : can be used in names as just another character

     and i forgot to add:

      5) in trace, derived functions on the queue are represented

         with a . and : is used to separate stack and queue:

            2 3 : . 4 5

    who would ever have thought that two meaningless symbols

    could have so many uses?