> 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