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]
<- stack [X^z Y] -> [z Y]
=> cache [X^z Y] -> [X Y^z]
<= uncache [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]
<- is Joy's 'unstack' word. The new stack is set to the top value of
the old 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.
=> 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.
<= pushes onto the stack whatever is last on the queue. For example,
1 2 3 <= 4 5
1 2 3 5 4
<= 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 < and >, 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 partitions 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 -> } ;
; <= { [] _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