my mail program at work has the irritating (and apparently
incurable) habit of wrapping lines. of course, it knows
better than i do about where the text should be broken.

let me try once more.

-------------

THE CONCATENATIVE LANGUAGE X (Draft)

* Introduction

X is a new installment in concatenative vector language project.

X borrows code and ideas from the language XY, but departs in certain respects
from that earlier language.

Whereas in XY, the programmer has access to the entirety of the result stack
and the input queue, in X, explicit access to the queue is blocked, and stack
manipulation is limited to what can be expressed by the use of finite patterns.

Otherwise, the most striking difference between the two languages is that all
combinators in X are treated as adverbs. An adverb is a function which takes
one or two quotations off the stack and derives from them a function which is
then prepended to the queue. X functions are not first-class. That is, in X
there is no way to construct an arbitrary function, nor is there any way to
leave a function on the stack.

* Notation

"abc" a string
'a a character

10 integer
10.2 float
10: negative integer
10.2: negative float

[a 10] lazy list (quotation)

A name begins with a-zA-Z, followed by characters drawn from a-zA-Z, dot, and
colon. For example, the following are valid names:

a
a:
a.b.c:
a..foo:bar..

Note that

a12b

is parsed as

a 12 b

That is, a name, followed by an integer, followed by a name.

* Datatypes

The elementary datatypes of X are integer, float, character, symbol, and list.

Note that "abc" is a list of characters, that is

['a 'b 'c]

is identical to

"abc"

* Verbs

A verb is a function from elementary datatypes to elementary datatypes. 18
of the 20 K verbs are verbs of X:

~ | @ # $ % ^ & * - _ = + | < , > ?

Each verb has three forms:

@ dyad
@: monad
@. commuted dyad

All but one of the X verbs retain their K meanings. The exception is that
dyadic '@' has been mapped to dyadic '.'. That is, x y @ has the K meaning:

x . y

X doesn't require the following K verbs:

.: execute, make/unmake dictionary, &c.
@ at
: x:y -> y
:: ::x -> x

* Definition

Inline definition in X is the same as it is in XY:

;x A; define x as A
;x; undefine x

* Trains

One of the principal motivations for X is to explore the consequences of
introducing into K the concept of a verb-train, or "train" for short.

In K, it is possible to construct a limited subset of compositions. A valid
K composition has one of the following two forms:

m..mm
m..md

where 'm' is a monad and 'd' is a dyad. For example, the following are
valid K compositions:

*|: first (of the) reverse (of)
*| first (of the) minimum (of)

Only the final verb of the composition requires the monadic qualifier ":".
All verbs preceding the final verb are assumed to be monads.

In X, any quotation consisting entirely of verbs is a valid train:

[^:+*]

* Adverbs

X has six adverbs. These have been mapped to the "mated" characters as
follows:

X K name
- - ----
( ': prior
) ' each
{ \: each-left
} /: each-right
\ \ scan
/ / over

For example, polyadic 'each':

[1 2 3][4 5 6][+])

) takes the quotation at the top of the stack, derives a function which adds
corresponding elements of [1 2 3] and [4 5 6], and returns [5 7 9].

In X, the valence of the derived function determines how many arguments it
will consume from the stack. For example, [+] has valence 2, so [+]) will
consume two lists. Since [+*] has valence 3, it expects three arguments on
the stack:

[1 2 3][4 5 6][7 8 9][+*])

The monadic form of an adverb derives a function which expects to find its
arguments packaged in a single list:

[[1 2 3][4 5 6][7 8 9]][+*]):

* Evaluation

X has integers, floats, characters, symbols, and lists, but it does not have
derived functions as a first-class datatype. This implies that at every
point in the course of evaluation, every object on the stack is one of the
primitive datatypes enumerated above.

Although the X programmer has no access to the queue (the list of elements
yet to be evaluated), the X interpreter does. Think of the state of X at any
point in time as consisting of

X z^Y

where X is the stack, z^Y is the queue, and z is the next element on the
queue to evaluate. The evaluator A examines z:

If z is defined symbol, A applies it to X and Y, which yields a new stack X'
and a new queue Y'. There are two cases:

- If z is a verb, for example +, then Y' = Y and X' = the
result of applying + to X.

- If z is an adverb, for example ), then X' = X minus the
quotation Q on top and Y' = the result of prepending the
derived function Q) onto the queue.

If z is not a defined symbol, there are two cases:

- If z is not a derived function, then X' = X^z.

- If z is a derived function, then A applies it to the top
element of the stack. There are two cases:

- The result r is a derived function, in which case
Y' = r^Y.

- The result r is not a derived function, in which
case X' = X^r.

In the course of repeated passes of the evaluator, a derived function on the
queue keeps consuming arguments from the stack until its valence is reached.
For example, [+*]) has valence 3, so it will take three passes before it
finally returns something which is not a function, at which point that result
is pushed onto the stack.

* Combinators

The valence of a function is the number of arguments it takes. The charge
of a function is the number of results it returns.

K verbs have valence 1 or 2, and charge 1. K adverbs derive functions which
have valence v > 0 and charge 1. but stack-based languages require operations
which, implicitly or explicitly, permute elements of the stack. For example,
'dup' has valence 1 and charge 2, 'swap' has valence 2 and charge 2, and the
valence and charge of 'i' vary, depending on the quotation 'i' finds at the
top of the stack.

X has two combinators:

` pattern
`: i

`: is the familiar Joy disquotation combinator:

10 20 30[+*]`:
500

'pattern' is similar to the { combinator found in XY:

10 20 30[a b c][c a]`
[30 10]

It expects a pair of quotations on the stack. The first quotation is a list,
possibly nested, of undotted names. The second quotation is a list, possibly
nested, containing some or all of the names in the first quotation, possibly
repeated, intermixed with other elements. ` takes the two quotations and
derives a function.

The derived function has the following behavior: Values are drawn in order
from the stack and mapped to names in the first quotation. Those values are
then mapped to corresponding names in the second quotation.

When the first first quotation is non-empty, the result is a list:

10 20 30[a b][b a]
10 30 20

When the first quotation is empty, the function returned by ` is the 'dip'
combinator:

10 20 30 100[][+*]`
500 100

In combination with `:, ` is powerful enough to derive the standard swap- and
list-manipulation words. For example,

;dup[a][a a]`i;
;swap[a b][b a]`i;
;zap[a][]`i;
;uncons[[a A]][a A]`i;

* Examples

Re: [stack] X: an update

stevan apter — 2004-11-22 22:29:31

sa@dfa.com — 2004-11-23 15:46:03

William Tanksley, Jr — 2004-11-23 16:50:15

stevan apter — 2004-11-23 20:45:47