THE CONCATENATIVE LANGUAGE XY * Introduction XY is a direct descendant of the vector language K and the concatenative language Joy. 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. The principles of XY are: - The totality of the computational state is available at every step. - A step may produce an arbitrary transformation of computational state. * K The datatypes of XY are those of K: integer, float, character, symbol, null, function, 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 A verb is atomic if it pervades its argument to iterate over atoms. For example, [1 2 3][4 5 6] + -> [5 7 9] The atomic dyads: ! % ^ & * - = + | The atomic monads: $: %: -: _: 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 primitives (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 where 'x^y' denotes the concatenation of x and y. 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 s which is not a primitive has the effect of pushing v, the value of s, onto the queue, whereupon v is immediately evaluated. 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, where each line represents the state at a step, the stack appearing to the left of the colon, and the queue to the right: 10 :trace 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 seven "core" primitives: -> queue [X^z Y] -> [X z] [z Y] => cache [X^z Y] -> [X Y^z] [X^z Y] / use [X^z Y] -> [X z,Y] \ mention [X z^Y] -> [X^z Y] ` enclose [X^z Y] -> [X^{z} Y] disclose [X^{z} Y] -> [X^z Y] 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. => appends to the queue whatever is on the top of the stack. For example 1 2 3 => 4 5 1 2 4 5 3 => can be used to simulate Factor's >r. . / 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 ` is self-dual: if it finds a list on top of the stack, it turns it into a function-atom; if it finds a function-atom on top of the stack, it turns it into a list; otherwise it has no effect. For example, [1 2 3] ` @: 1 [1 2 3] ` ` [1 2 3] ~ 1 10 ` 10 ~ 1 * Patterns An XY program is a lazily-evaluated list, or "quotation." For example, [+ *] when evaluated on a stack whose top three elements are numbers a b c, adds b and c and multiplies the result by a. 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. Since the mapped code is prepended to the queue, it will evaluate as soon as control is returned to the interpreter. For example, 10 20 [+ 0] { [[a b]] a b } 30 0 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. Note that the first of the list is returned "escaped": 10 20 [+ 0] { [[a A]] \a A } 10 20 + [0] 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 * Shuffle A symbol of the form A--B, i.e. one containing exactly one occurrence of the substring --, is translated into a pattern. For example abc--bca is translated into the pattern { [a b c] b c a } Substrings to the left and right of -- may contain lower- and upper- case letters, as well as , which stand in for the quotation- formation words [ and ]. For example, 10 [20 30 40] 50 ac--cBa 50 [30 40] 10 * 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 * Flatness A language is flat if for any sequence S of tokens, all partitionings of S are semantically equivalent. XY is not flat, since not all partitionings of [1 2 3] are equivalent, or even valid. XY 2.0 implements flatness as follows: [ ( { `[ `( `{ are defined as literals, with the semantic rule [X z^Y] -> [X^z Y]. ; is defined: [X ;^Y] -> [X^; Y] if ; is not in X. ] ) } are defined as follows: take everything on the stack back to the last left mate (e.g. [ and `[ are left mates of ]), enlist it, append the appropriate post-processing operations, and place the result on the queue. If one of the left mates is on the stack, every symbol except the right mates, \ and / are treated as literals. In XY 2, the following is valid: ; f [1 ; g 2 3] f g / [1 2 3] f is evaluated, [ is placed on the stack, then 1, then g. / moves the value of g to the queue. 2 is placed on the stack, then 3, then ] evaluates, taking [ 1 2 3, enlisting it, and placing the result [1 2 3] on the queue, which is then evaluated and placed on the stack. * Revisions XY 0 revisits and revises certain features of XY. XY 0 has quotations but not lists. Shuffle-symbols are enhanced and patterns are removed from the language. ( and ) are added to the core on a provisional basis. ( quotes the stack and ) quotes the queue: ( stack* [X Y] -> [X^[X] Y] ) queue* [X Y] -> [X^[Y] Y] * 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' list list manipulation words, e.g. 'cons' general general operators, e.g. 'pred' predicates predicates, e.g. 'false?' queue queue manipulation words, e.g. 'clear' monads keywords for K monads, e.g. 'where' for '&:' dot K amend and dmend adverbs XY definitions for K adverbs, e.g. 'each/' joy XY definitions for Joy combinators, e.g. 'linrec' 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 Define the core words => and { [] _y -cons -> } ; ; } ; Joy's 'dip' and 'step' combinators: ; dip swap => i } ; Infix K notation to postfix: ; infix enlist [infix.] infra ; ; infix. [[[count 2