Barring unpleasant discoveries, i imagine this is close to a final draft.
i've filled out the "programming in XY" section with an implementation of
Factor's >r and r>.
THE CONCATENATIVE PROGRAMMING LANGUAGE XY
*
(SECOND DRAFT)
* Introduction
XY is a concatenative programming language with roots in Joy and K.
The elements of XY are unary functions, each of which takes and returns
a pair of the form:
[stack queue]
The stack is a list which represents the past of the computation.
The queue is a list which represents the future of the computation.
XY is written in K in continuation-passing style.
The datatypes of XY are the atoms and lists of K: integers, floats,
characters, symbols, dictionary, null, and lists.
The 20 K verbs are the primitive functions of XY:
~ ! @ # $ % ^ & * - _ = + | : < , > . ?
* Notation
Words are separated by blanks:
12 4 + *
Blanks are not necessary when using punctuation symbols: {, ], (, and ).
[1 2 3[4 5]]
Characters:
'a
Strings:
"abc\"def"
A string is a list of characters:
'a'b'c
"abc"
*:
'a
If v is a verb, then v denotes the associated dyadic function, v: denotes
the the associated monad, and v. denotes the commute of the dyad. For
example,
x y - // x minus y
x -: // negate x
x y -. // y minus x
* Constants
_n // null
` // empty symbol
0V // empty integer vector
0v // empty float vector
0` // empty symbol vector
0I // max int
0i // infinity
-0I // 1+min int
-0i // negative infinity
0N // min int
0n // NaN
* Lists and Quotations
XY supports both lazy lists ("quotations") and eager lists.
Quotations are written using square brackets:
[2 3 +]
[2 3 +]
Eager lists are written using parentheses:
(2 3 +)
[5]
An eager list such as (2 3 +) is recursively transformed at parse-time
into the expression
[[2 3 +]] [i] infra
* Evaluation
In the course of execution, XY has two objects: a list of values X and
a list of tokens z^Y, where z is the next token to be processed and Y
is a list of the remaining tokens. X is the result stack and Y is the
input queue. Evaluation of z consists of applying z to the list [X Y].
The result of the application is a new stack X' and a new queue Y'.
z is either an atom or a list. An atom is either an integer, a float,
a character, a dictionary, null, or a symbol. A symbol is either
defined or undefined.
If z is anything other than a defined symbol, its evaluation rule is:
[X z^Y] -> [X^z Y]
That is, z is removed from the queue and appended to the stack.
XY maintains a dictionary W which maps symbols to evaluation rules. For
each defined symbol, there is an evaluation rule in W. For example, the
evaluation rule for the primitive + is:
[X^x1^x2 Y] -> [X^x1+x2 Y]
That is, + takes X^x1^x2 and Y, pops x1 and x2, adds them, appends the
result to X, and returns the new stack and the unaltered queue Y.
* Projection
Primitives like + and patterns like { [a b c] b a c } have valence:
+ has valence 2: it expects at least two values on the stack. If
the stack contains fewer than the expected number of values, the
function is projected onto the available values to produce a closure:
c\ +
[+]
c\ 2 3 { [a b c] b a c }
[2 3 { [a b c] b a c }]
* Core
<- stack [X^z Y] -> [z Y]
<- replaces the stack with the item found at the top
of the stack:
10 20 [2 3 +] <-
2 3 +
<- is Joy's "unstack" operator.
-> queue [X^z Y] -> [X z]
-> replaces the queue with the item found at the top
of the stack:
10 20 [2 3 +] -> 30 40 50
10 20 5
-> has no analogue in Joy.
/ use [X^z Y] -> [X z^Y]
/ prepends to the queue the item found at the top of the stack.
10 20 [2 3 +] / 30 40 50
10 20 5 30 40 50
/ is Joy's "i" combinator.
\ mention [X z^Y] -> [X^z Y]
\ appends to the stack the item found at the top of the queue.
10 20 \ + 30 40
10 20 + 30 40
\ has no analogue in Joy.
; define [X name^..code..^;^Y] -> [X Y]
; add-mul + * ;
2 3 4 add-mul
14
All definitions in XY are inline.
{ stack pattern [X template^..code..^}^Y] -> [X^Z Y]
{ matches names in the template to elements on the stack, and
then substitutes those values for matching names in the code.
_x denotes the stack and _y the queue as they are at run-time.
The result of the subtitution Z is appended to the stack:
10 20 30 { [a b] a b b a }
10 20 30 30 20
{{ queue pattern [X template^..code..^}}^Y] -> [X Z^Y]
{{ matches and substitutes like {, but instead of appending
the result to the stack, it prepends it to the queue:
10 20 30 {{ [a b] a b + a * }}
10 1000
* Periphery
The following words are included in the current implementation, but are not
used.
.a amend shallow amend with assignment: @[x;y;:;z]
.d dmend deep amend with assignment: .[x;y;:;z]
.g get "name" .g -> value of name
.s set value "name" .s -> associate name with
value
.p parse invoke the XY parser
.r represent invoke the XY representation function
.i input accept input to the stack
.o output produce output from the stack
.e execute alternate evaluate P, if that fails evaluate Q
.xy XY evaluate X and z^Y.
* Scripts
XY supports scripts. An XY script is a text file which contains XY code.
Typically, the filename ends in ".xy", although this is not necessary.
On initialization, XY loads the system script xy.xy, which contains core
definitions, including stack manipulation words like dup and swap, K
adverbs
like over, each, and prior, and Joy combinators like linrec and dip.
Comments are written using //:
// this is a comment
A comment ends at the next newline.
* Programming in XY
In Factor, the words >r and r> are used to store and retrieve items from
the
stack. The analogous words in XY are => and <=, which use the tail of the
queue instead of a separate stack:
=> cache [X^z Y] -> [X Y^z]
=> appends to the queue the item found at the top of the stack.
10 20 => 30 40
10 30 40 20
<= uncache [X Y^z] -> [X^z Y]
<= appends to the stack the item found at the end of the queue.
10 <= 30 40 20
10 20 30 40
These words are defined in XY as follows:
; => {{ [] _y |: cons |: -> }} ;
; <= {{ [] _y |: uncons |: -> }} ;
Here's a trace, which shows how they operate:
1 2 3 => 4 5 <= 6 7 8
: 1 2 3 => 4 5 <= 6 7 8
1 : 2 3 => 4 5 <= 6 7 8
1 2 : 3 => 4 5 <= 6 7 8
1 2 3 : => 4 5 <= 6 7 8
1 2 3 : {{ [a] a _y |: cons |: -> }} 4 5
<= 6 7
1 2 : 3 [4 5 <= 6 7 8] |: cons |: -> 4
5 <= 6
1 2 3 : [4 5 <= 6 7 8] |: cons |: -> 4 5
<= 6 7
1 2 3 [4 5 <= 6 7 8] : |: cons |: -> 4 5 <= 6 7 8
1 2 3 [8 7 6 <= 5 4] : cons |: -> 4 5 <= 6 7 8
1 2 3 [8 7 6 <= 5 4] : {{ [a b] [a] b , }} |: -> 4 5 <=
6 7 8
1 2 : [3] [8 7 6 <= 5 4] , |: -> 4 5
<= 6 7 8
1 2 [3] : [8 7 6 <= 5 4] , |: -> 4 5 <= 6
7 8
1 2 [3] [8 7 6 <= 5 4] : , |: -> 4 5 <= 6 7 8
1 2 [3 8 7 6 <= 5 4] : |: -> 4 5 <= 6 7 8
1 2 [4 5 <= 6 7 8 3] : -> 4 5 <= 6 7 8
1 2 : 4 5 <= 6 7 8 3
1 2 4 : 5 <= 6 7 8 3
1 2 4 5 : <= 6 7 8 3
1 2 4 5 : {{ [a] a _y |: uncons |: -> }} 6
7 8 3
1 2 4 : 5 [6 7 8 3] |: uncons |: -> 6 7
8 3
1 2 4 5 : [6 7 8 3] |: uncons |: -> 6 7 8
3
1 2 4 5 [6 7 8 3] : |: uncons |: -> 6 7 8 3
1 2 4 5 [3 8 7 6] : uncons |: -> 6 7 8 3
1 2 4 5 [3 8 7 6] : { [[a A]] a A } |: -> 6 7 8 3
1 2 4 5 3 [8 7 6] : |: -> 6 7 8 3
1 2 4 5 3 [6 7 8] : -> 6 7 8 3
1 2 4 5 3 : 6 7 8
1 2 4 5 3 6 : 7 8
1 2 4 5 3 6 7 : 8
1 2 4 5 3 6 7 8 :
1 2 4 5 3 6 7 8
* Implementation
At the present time, the implementation consists of a single script
containing 185 lines, including whitespace and comments.
The K process contains 27 named objects:
h W w g s l k j v u c d m q n o P p L r T t a e S i f
K functions (there are 22 of them) are uniformly lower-case, thus allowing
room for future enhancements. (That's a K joke.)
Interpretation in XY consists of the standard read-eval-print loop. The
three steps correspond to three functions: the parser p, the evaluator e,
and the function r, which takes a list (either the stack or the queue) and
represents it as a string, suitable for printing.
The evaluator takes a stack x and a queue to be evaluated y:
e:{({if[T>0;t[x;y]];a[*y,();x,()](1_ y),()}.)/(x;y)}
e repeatedly evaluates x and y until either of the following conditions
occurs: either the result of the evaluation matches the previous result,
or the result of the evaluation matches the initial values of x and y.
At each step, e checks to see whether the trace variable T is positive.
If it is, it displays the current states of x and y:
t:{if[(#x)|#y;`0:(40$r x)," : ",-40$r y;:[#y;if[#0:`;T::0];`0:,""]]}
It then applies the following algorithm: if the queue is empty or the
stack is null, it returns the current stack and queue; else if the next
element to be evaluated is not a defined symbol, it appends it to the stack
and returns that and the queue; else it applies the evaluation rule for
that symbol:
a:{:[(~#z)&_n~x;(y;z);~4=4:x;(y,,x;z);(#**W)=i:W[0;0]?x;(y,x;z);W[1;i][y;z]]}
* To do
- Can { and {{ be defined in terms of the remaining primitives?
* Links
XY:
http://www.nsl.com/papers/xy.htm.
K:
http://www.kx.com