I wish I could claim great originality for the remarks and suggestions made
and given below, but *the* "Great Insight" (if there is one to be found) has
eluded me. What I'm doing here, instead, is re-formulating XY and using some
basic observations about concatenatively languages (such as that they don't
*have* to work off of a stack), and that they don't even have to work in a
"postfix" ordering of data and functions (see below about the single-element
"stack"). From those observations, I offer some suggestions for extending or
generalizing XY (or almost any concatenative language, for that matter).

==========================
Concatenation and Data

I've been very impressed by the observation that the concatenativity of a
language like Joy imposes no restriction on the data structure that it uses.
Joy uses a stack, XY uses a queue and a stack, but other configurations are
possible. One that I considered was the two-element stack, in which no more
than two-elements at a time could be pushed on the stack. Oddly, while this
makes programming more difficult, it does not break the Turing universality
of the language.

Even the restriction that the language not allow variables leaves a wide
range of options open as to what the language will work with as its basic
data structure.

The Single-Element "Stack"

Oddest of all, we can even imagine variable-free concatenative language that
has nothing but a *single* "register" and an input queue (or even just a
code stream that cannot be modified or have data pushed back onto it), a
language that uses an infix style of notation for binary operators (the
first operand function automatically fills the register with its value and
the operator automatically uses the register value and the value immediately
following it in the queue, and puts the result in the register). This is a
little like XY with a single-element stack.

Another thing that this language could do would be to put a list in the
register. Thus, in an infix style, we could say,

[] cons 1 cons 2 cons 3

(where, because of the infix style, "cons 1" conses the item following 1 to
the list in the "register") to build [ 3 2 1] in the register. What this
does is *make* a stack out of the queue, using cons as a kind of explicit
push operator (since [] 1 2 3 would just put an empty list in the register,
and *overwrite* it with 1, etc., we have to somehow prevent that from
happening, and we do that with the cons operator starting from an empty
list). Having made a stack, we can then proceed, in principle to perform any
computation that would be possible in full-blown XY or Joy (etc.). Of course
this assumes that we have a suitable set of functions that can perform
operations on lists as if they were stacks, but that's easy enough to
manage.

Alternatives to the Simple Stack

The point here is not that this is a good way to go, or that we would
actually want to program extensively in such a cramped language (at least
not without first implementing a stack in it). The point is to break the
psychological hold of the stack on our minds (or at least on *my* mind!) as
being *the* way to implement concatenative languages. Don't get me wrong; I
think Joy's use of the stack is beautiful. But, having been impressed with
the observation that we are not inherently limited to the stack, and then
being further impressed with the potential of XY, I've been searching for a
structure that could be given a clear mathematical definition *and* that
would give us more ease-of-programming than does Joy and XY (of course, part
of the problem for me with XY is not the lack of power of the primitives but
the fact that it is still hard for me to read it).

In getting to the point where I am now, I considered a number of
alternatives, including a "T" structure, in which there would be an input
queue (the right side of the top bar of the T), a stack (the vertical part
of the T) and an output queue (the other side of the top bar of the T) and a
+ structure, which would be like the T language but with an additional stack
sticking upward.

But, for now, I have settled on further consideration of XY with some
generalizations. These generalizations would affect both the primitives and
how we think about the language. Instead of adding additional structures to
the XY pair, I suggest first combining both the queue and the stack into a
single queue and then generalizing that queue to make it possible to do more
with less code (I hope). Here goes:

XY's Queue/Stack Pair to Queue/Pointer Pair

Start with XY and re-conceptualize the queue/stack pair into a single
entity, a queue and a "pointer" to the next item in the queue to be
executed. I regard this as a single entity because the pointer only has
meaning in association with the queue, whereas the XY queue and stack can
each stand alone as data structures.

That is, imagine a language that is identical to XY except that, internally,
it is based not on a stack and a queue but on a single modified queue and an
execution or program pointer which points at the next queue element to be
executed. If the pointer moves one step further along the queue without
executing, this "pushes" the element that is stepped-over in the process
onto the stack-part of the queue, but it does so more efficiently than
actually using a separate stack because all that happens is that a single
"pointer" is incremented (at least logically) to point to the next item in
the queue. In this version of the language, this is how literals would be
"executed": they literally do nothing at all; the QP virtual machine detects
them as literals and simply moves on to the next item in the queue just as
it would if we had a No-Op word. But, the magic is that this non-operation
nevertheless pushes the literal onto the stack (because it is now on the
stack side of the pointer). Whether an element is part of the stack-part of
the queue or part of the input-part of the queue depends solely on which
side of the pointer it is on at the moment. This allows us to "push" large
numbers of items by doing nothing more than making the execution pointer
point much further along the input queue.

How does this single queue look?

In effect, the queue looks very much like the trace displays of XY. These
tracing displays represent the queue and the colon in the display tells us
where the pointer is. For example, if a trace display in XY looked like
this:

1 2 3 [4 5 <= 6 7 8] : -cons -> 4 5 <= 6 7 8

this would represent, in my re-conceptualization, a single queue with the
pointer at "-cons", meaning that "-cons" would be executed next. Let's call
this "language" QP (for "queue/pointer"). In effect, the XY queue/stack pair
are butted together, with the front of the queue butting against the top of
the stack. It was after I thought of the idea of using a single queue that I
realized that the XY trace displays effectively represented the XY pair as
if it was a single queue.

An Alternative to the XY Trace Display

I don't know if reading the XY documentation gave me the idea, or not, but
the XY trace certainly represents it well. However, I think I would want to
have two lines. The first would be the queue itself, *without* the colon,
and the second line would have a caret symbol pointing at the next item to
be executed, like this

1 2 3 [4 5 <= 6 7 8] -cons -> 4 5 <= 6 7 8
^

(Format the two lines above in Courier New or some other monospace font to
see most clearly what I mean: the caret should point at the hyphen in
"-cons")

Represented this way, it is clear that there is no fundamental distinction
between the input part of the queue and the stack part. They are just on
opposite sides of the execution pointer. To me, it's amazing the difference
I see in just removing the colon and putting a location pointer under the
next word to be executed. Somehow, *seeing* the queue and the stack as a
single line of tokens, with one of them momentarily singled out by a
pointer, gives a significantly different "feel" to it, one that tends
towards a different way of programming.[1]

Again, I emphasize at this point that I am not claiming a genuinely new
language here, but am merely re-formulating XY in a way that seems a little
cleaner and easier to understand to me, and that more naturally suggests
some primitives that might be very useful, such as one or two to *just* move
the pointer along the queue in either direction (thus magically "pushing"
items onto the stack or onto the queue).

It seems conceptually cleaner to me because we only have one data entity to
"pass" to functions (we count the execution pointer as part of the overall
structure) and we only get the one data entity back, and, importantly, we
only have to track one "pointer" because the *same* pointer indicates both
the top of the stack and the first item of the queue, which is why just
incrementing it (or doing the logical equivalent if we are using a
linked-list approach, which would probably be best anyway) "moves" one or
more items from the queue-part to the stack-part. Moving the pointer the
other way also moves things from the stack to the queue. [2]

But, I'm not satisfied yet. We can think of the queue as being a kind of
tree, in which each primitive is a leaf, and each non-primitive is a branch
with (usually) one or more further branches and/or leaves. Thus, in
principle, "compiled" XY/QP code could be a complete tree structure, and
execution would be a matter of traversing (and modifying) this tree
structure. If we retain the "tree-ness" during the execution of
non-primitives, then (I think) we can do some interesting things. We don't
actually have to compile the code to get this effect, however (and, to
retain full flexibility, we wouldn't want to truly compile the language
anyway).

Generalizing XP/QP: Tree-P

We can get the same effect by regarding the queue/stack as a tree in a
logical or virtual sense. To this end, I suggest the following extensions of
XY/QP:

The end of the executing function's code is marked or tracked in such a way
that the code in the function can easily access and manipulate the portion
of the queue *following* the function without having to perform complicated
calculations to determine where that part of the queue is. For example, it
might be able to easily move that queue item to the stack, or insert a stack
item after itself and in front of what was originally the next element.
The queue is really a tree, with the elements in the queue being the
first-level branches, and the branches of the function being executed (if it
is non-primitive). Included in the primitives would be tree-manipulation
functions that have the same status as stack-operators in Joy. We could
perhaps bodily convert some of the Joy tree library to primitives in the new
language.
The ability of functions to manipulate the code/data in the branches that
branch from branches other than itself. Thus, the currently-executing
function might create or re-structure or otherwise modify branches that have
not yet been reached during execution. We might do this in the process of
building a complex data structure to be used later, or in building code on
the fly to be executed later, code custom-built to current requirements, or
even code to be sent off to a PostScript printer (perhaps after a
translation pass after it is constructed).
Currently executing code would also be free (and able) to access itself via
tree-related operators, so it could do combinator-like things in a
more-general way than might easily be done with ordinary XY tools.
XY's pattern-programming would be extended to include tree-related pattern
specifications, so tree-structures could be manipulated by patterns as well
as sequentially-ordered queue/stack items. I envision a set of
tree-functions that would allow fairly radical tree-modifications and
pattern-matching/replacement operations that would obviate the need for
really quite large amounts of the pattern-programming that XY already
provides (which already seems to be a fairly powerful mechanism for reducing
coding).

I propose calling this modified XY "Tree-P" because, like QP, it maintains a
pointer to where execution is about to occur, but, unlike QP, I propose that
it have some tree-specific primitives (and pattern-programming features)
built in at the start.

Part of the idea here is to make the entire system open, transparent to
executing code (except for any restrictions imposed by the developers of
applications). That is, while we would not generally want to fool with much
of the code following the executing function, I want to leave the system
open, in principle, to whatever the designers of a software package want to
do with it. The hiding of internals and such would be allowed and used but
not required, so, if a developer wanted code to be able to access all of the
"tree" of the queue/stack entity, he could make all of the code he is
writing accessible in this way.

Loops Upon loops: Trees by Another Description

I'd like now to merely introduce yet one more way of thinking code in
programming languages, it's logically equivalent to the tree idea, but, to
me at least, it gives more a sense of the continuity of code during
execution. If we start execution with a single "word" (or function) in the
(QP) queue, we can think of the code for it as being a kind of loop. Think
of a piece of string that starts out straight, but we pinch two points
together to form a loop, and then, on the loop itself, we pinch separated
point together to form smaller loops "budding" off of the larger one, and
then we do the same thing with the smaller loops, all the way to the point
where each of the outer-most loops is a call to a single primitive.

The queue can be regarded as a single loop with many lesser loops attached
to it. Execution of code consists of traversing this loop and of using parts
of it as data. We may do this at any level of branching, so we have
indefinite flexibility. Like the simple queue or the stack, we may modify it
during execution. If we are lucky and clever, we can come up with a small
set of primitives that enable us to work with the entire structure if we
choose to and have laid out our code and data in it in such a way as to make
this a useful thing to do. In general, we would only actually do this mostly
at the level of the currently-executing code, or one level inward (toward
the main loop), but, in principle, it could be valuable to be able to go
outward as well.

Whether we visualize our program as a tree or a set of loops budding off of
each other, what we are doing is structuring out code so as to make it
manageable by human minds. Each branch or loop is (if we have fully
succeeded in our functional decomposition) a conceptually-clean "unit" that
we can work with without too much mental overhead. The advantage of the tree
over the simple queue is that it retains good structure while giving us
greater conceptual flexibility than does the idea of a simple queue.

Of course, this is largely a matter of how we describe things, because a
queue can contain elements that are as richly-brachiated as we could
conceivably wish for. There is no ultimate dichotomy between trees and
queues, just as lists and queues, and stacks, and lists of lists, can all be
brought under the same conceptual scheme (a list can be made into a tree
simply by having it be a list of lists, and a list can be a queue simply by
*treating* it as a queue, and so on). But, in terms of a programming
language, it makes a difference because, if we think of the base structure
as a tree or a system of loops growing off of loops, then we can build
special primitives into the language itself, so it will "naturally" be
suited to tree management and tree-processing. If we do that, then we don't
have to implement them as a library, because they become the base we start
from rather than something we build up to.

There is also a slight efficiency issue as well. If the language is
*designed*, from the ground up, to work with trees, we can put at least the
core tree-handling operations into the most efficient infra-structure code
we can find. If we add this stuff in later as non-primitives, we pay a
price, except, possibly, in truly-compiled code. True machine-language
compilation is hard to do in such a way as to retain the flexibility of an
interpreter, though concatenative languages make this easier than it would
be in other kinds of languages, because we can do incremental and almost
context-free compilation. We definitely want to retain the ability to
construct code on the fly, even if we construct it out of pre-compiled bits
that can be separated and combined in different ways. By eliminating
variables and parameter-passing from compilation, we can have the compiler
simply insert in-line any code we want to be treated that way. As long as we
know where it begins and ends, we can then treat it as a unit of data and
move it around in quoted programs or other structures however we wish.

On Saving Some of the Good Symbols from Less-Important Uses

Another reason for suggesting that the language be built from the ground up
on the assumption of a tree-cum-queue-cum-stack-cum-execution pointer is
that it can enable us not to use up all the good primitive symbols on
primitives of less generality. We could get around this, to some extent, by
allowing overloading, but then we might get semantic/conceptual clashes
between the different uses of symbols (or have a very hard time avoiding
them, at least). Imagine that we use the slash and the backslash as XY does,
but then we realize that it would be idea to use these for some different
and very valuable tree operator (just suppose; I'm not saying that this is
true). If we re-define it, we break existing code, but if we overload it, we
end up with a clash of meanings. As much as is feasible, we want to use a
given symbol for conceptually similar operations.

I'm not sure what I think of XY's newest set of primitives, since I haven't
studied them. I'm only making a general remark here about being careful to
design our languages in such a way as to get the best set of primitives, and
that, therefore we need to avoid prematurely settling on a data structure
that may "channel" our decisions about primitives too narrowly. Allowing for
a more-general data structure at the start helps us ensure that we make
better decisions about primitives.

Final Remarks

As I said, there is not much that's really original here, if anything, but I
hope that my particular formulation of things XY and my suggestions for
possible modifications or extensions may lead to further advancements by
others, perhaps even to ones more radical than my re-conceptualization of
the XY queue/stack pair into a single structure. And, I hope that, at best,
we will come up with good reasons for *not* using a tree as our basic
structure (of course, it would be even nicer for me if it turned out to be a
good idea).

Special Acknowledgements

Stevan Apter, for providing another way to have a concatenative language
basic data structure that is not just a stack. Much of what I have said
above is just a different "take" on stuff that's present or implicit in XY.

Manfred van Thun, for going deeper than Forth and Lisp to give us a better
alternative to control constructs[3], and for showing that the
non-von-Neumann dream of Backus is realizable in a practical programming
language, and for giving the rest of us the Concatenative list so we can
stand on each other's shoulders in a recursive way.

Notes:

1. This is related to the differences in thinking that, in general,
different representations of things can lead to. An extreme example is the
difference between Roman numerals and the Arabic system of
number-representation. One tends makes calculation very difficult and
cumbersome, and the other makes calculations follow a few simple rules in a
(comparatively) simple way, regardless of the size of the numbers (well, up
to the point where we simply run out of room or will to write down all the
digits).

This was one of the things I noticed when I started learning APL in the
seventies. APL can be regarded as a different system of notation, but it
suggests and encourages a different way of *thinking* about things. I had
the same experience when learning Forth.

Of course, translating the XY queue/stack pair into a single queue is not
nearly as radical as going from, say, Fortran to APL, but the same principle
applies, just in a much smaller way.

2. One note before going on to other things: In a way, QP is like a
generalized Turing machine, where the tape is represented by the queue, and
where we can insert and delete things from it at the current location of the
execution pointer. Adding XY's cache and uncache functions makes the
generalization even greater. And yet, despite these modifications and
extensions, there is still a very Turing-machine-like quality to this
representation. (When a non-primitive is executed in XY/QP, it is removed
from the queue and its code is inserted in its place (at the front of the
queue), and this, too, goes beyond the basic Turing machine idea). I
considered developing this document from the idea of a Turing machine that I
would gradually modify until it got to be what I now have in mind, but
decided to stick with developing the ideas as they originally arose: As
inspired by XY.

3. Having to set up loops *every* time I need one is almost enough to cause
insanity. It is no wonder that Stevan has a Web page with "no stinking
loops" as the title. The iterators of conventional languages are scant help
in this respect. For one thing, they are non-general. Having a *function*
that does looping, and then being able to just call it whenever one needs
the loop (with no more than quoting the pieces of code it needs) is one of
the greatest benefits of Joy, to my mind. Being able to simply *make* a
combinator that does whatever control-construct-like thing one needs is an
even greater benefit, because it means that, even if the language did not
already have a good supply of looping functions (map, while, times (etc.?)),
we could simply make them and then have them with us always (as long as we
had at least one primitive that would enable us to define them).

Standing on Stevan's Shoulders: QP and Tree-P

Chris Cogan — 2004-10-03 23:40:24

cpcogan — 2004-10-04 17:50:07

sa@dfa.com — 2004-10-05 16:43:36

stevan apter — 2004-10-23 20:56:37

William Tanksley, Jr — 2004-10-24 00:38:27