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