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

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

    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).

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

    In my last post, where I 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.

    "conses the item following 1" should be "conses 1"

    It got garbled in editing from a different formulation.

    --Chirs

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

    "Chris Cogan" <ccogan@...> wrote on 10/03/2004 07:40:24 PM:

    :

     > 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.

    >

     XY is a superset of K:  the twenty K operators ~!@#$%^&*-_=+|:<,>.? and

    seven

    of the eight K datatypes (int, float, char, symbol, dictionary, null, and

    list -- but not lambdas).  to these i've added seven XY operators:  -> <- /

    \

    { {{ and ;.  <- is Joy's 'unstack', and / is the 'i' combinator.  from this

    basis, the Joy combinators, the continuation operators, and the K adverbs

    (which are themselves combinators) are derived.  it is possible to write {

    and {{ in XY (i.e. move them to the derived set), but i've left that as an

    exercise for the future.

    i take your point that the choice of primitives shouldn't be too closely

    tied

    to, or excessively dependent upon, the implementation details; in this

    case,

    decisions about the underlying data-structures.  but i don't think i've

    actually

    committed this error.  the concepts of "stack" and "queue" as they occur in

    XY are purely virtual.  given a different implementation language, it might

    make sense to realize these as one, two, or 17 different data-structures.

    in fact, in my implementation, i use random-access lists for both concepts,

    since this provides for the shortest, simplest, best-performing *K* code.

    but i want the programmer to imagine that he has a stack of results

    computed

    so far, and a queue of inputs waiting for evaluation, no matter how these

    ideas are physically realized.

    of course, you may be right that there's a better choice of primitives.

    i've

    changed my mind on this matter too often to feel certain that the current

    set

    is the best.  but, given the underlying assumptions, it is, i would say,

    very

    likely that -> <- / and \ are optimal, since they allow the programmer to

    subject data anywhere on either the stack or queue to K operations, and to

    take the results of such operations and place them answer on either the

    stack

    or the queue, and to do this in such a way that concatenativity is

    respected.

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

    i'm really grateful to billy for drawing my attention back to this paper.

    i was far too preoccupied when it first appeared to appreciate its originality,

    despite chris's overly-modest disclaimer on that score.  in retrospect, i

    think chris understands XY better than i do!  (and by the way, i too find

    it difficult to read and write in this language.  fortunately, i don't

    plan to do much of either!)

    the section i've snipped out below is had a nearly psychedelic effect on

    me when i re-read it.  i hope you'll elaborate on the ideas, when you

    have some time.  fractal loops ... what an idea.

    (and i love the term "richly-brachiated" for complex items on the queue.)

    an unhappy note:  the APL community was saddened to learn that ken

    iverson, inventor of APL and the J language passed away this week.

    ken was a powerful intellectual influence on many people, as well as

    a kind and generous individual.  now THOSE were shoulders to stand on!

    his turing award lecture, _notation as a tool of thought_, is a true

    classic of computer science literature, and i recommend it to members

    of this mail group.

     ----- Original Message -----

    From: "Chris Cogan" <ccogan@...>

    To: <concatenative@yahoogroups.com>

    Sent: Sunday, October 03, 2004 7:40 PM

    Subject: [stack] Standing on Stevan's Shoulders: QP and Tree-P

    [:]

    >

    > 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.

    >

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

    On Sat, 23 Oct 2004 16:56:37 -0400, stevan apter <sa@...> wrote:

     > i'm really grateful to billy for drawing my attention back to this paper.

     You're quite welcome. I haven't had a chance to reply to it, but in my

    opinion it's one of the major works on concatenativity so far, since

    it clearly and elegantly explains what previous concatenative theory

    was completely unable to explain.

     > i was far too preoccupied when it first appeared to appreciate its originality,

    > despite chris's overly-modest disclaimer on that score.  in retrospect, i

    > think chris understands XY better than i do!  (and by the way, i too find

     Yes, and Forth as well.

     > the section i've snipped out below is had a nearly psychedelic effect on

    > me when i re-read it.  i hope you'll elaborate on the ideas, when you

    > have some time.  fractal loops ... what an idea.

     I think that was my favorite part -- I hope not merely because I was

    just studying string theory and loop theory (the successors to quantum

    and relativity theory in physics). Seriously, though, I think his loop

    metaphor fits Forth better than anything else I've seen.

     > an unhappy note:  the APL community was saddened to learn that ken

    > iverson, inventor of APL and the J language passed away this week.

    > ken was a powerful intellectual influence on many people, as well as

    > a kind and generous individual.  now THOSE were shoulders to stand on!

     Yes, I'm saddened to hear that! Iverson was truly a great man. I've

    enjoyed reading some of his work, posted at www.jsoftware.com. The

    textbook "Calculus" posted there is highly inventive -- it's a chance

    to learn or review Calculus in a truly new way (have you ever read

    about fractional integrals anywhere else?).

    Can "Notation as a tool of thought" be downloaded?

    -Billy