# david madore's yin/yang mind-boggler

## stevan apter — 2004-07-25 19:11:53

    http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&threadm=u04sjxypbh.fsf%40hana.kurims.kyoto-u.ac.jp&rnum=1&prev=/groups%3Fq%3Dyin-yang%2Bcps%26hl%3Den%26lr%3D%26ie%3DUTF-8%26selm%3Du04sjxypbh.fsf%2540hana.kurims.kyoto-u.ac.jp%26rnum%3D1

    for continuation enthusiasts ..

## sa@dfa.com — 2004-07-28 18:08:41

    basic documentation for XY is done (http://www.nsl.com/papers/xy.htm), and

    most of the bugs have been knocked out of the code (accessible from the

    paper.)

    i've implemented several of the k adverbs (each, apply, converge) and a

    few of the many joy combinators (linrec, infra, cond, ifte).

    there are 19 XY primitives.  here they are (X is the result stack, Y is the

    input queue, -> separates before and after state, ^ is concatenation):

                 {           set pattern                   ( X : {^a^b^}^Y -> X

    : Z^Y ), Z = b/X[a]

                 {{          get pattern                   ( X : {{^a^}}^Y -> X

    : Z^Y ), Z = X[a]

                 \s          set left                      ( X^z : Y -> z : Y )

                 /s          set right               ( X^z : Y -> X : z )

                 /           cache                         ( X^z : Y -> X :

    Y^z) )

                 \           uncache                       ( X : Y^z -> X^z : Y

    )

                 //          queue                         ( X^z : Y -> X : z^Y

    )

                 \\          stack                         ( X : z^Y -> X^z : Y

    )

                 ;           define                        ( X^;^w^d^; : Y -> X

    : Y ), w = d

                 .g          get                           ( X^".." : Y ->

    X^[V("..")] : Y )

                 .s          set                           ( X^v^".." : Y -> X

    : Y => V("..") = v )

                 .p          parse                         ( X^".." : Y ->

    X^[..] : Y )

                 .r          represent               ( X^[..] : Y -> X^".." : Y

    )

                 .i          input                         ( X : Y -> X^s : Y,

    s accepted )

                 .o          output                        ( X^s : Y -> X : Y,

    s printed )

                 .e          evaluate (alternate)    ( X^[p q] : Y -> p(X,Y) or

    if p fails then q(X,Y) )

                                                           ( X^[p] : Y ->

    p(X,Y) or if p fails then X : Y )

                 .a          apply                         ( X^X0^Y0 : Y ->

    X^X1^Y1 : Y )

                 @0          amend                         ( X^a^b^c : Y -> X^d

    : Y), d = @[a;b;:;c]

                 .0          dmend                         ( X^a^b^c : Y -> X^d

    : Y), d = .[a;b;:;c]

## sa@dfa.com — 2004-07-28 18:40:49

    i hate my mail program.

    hate hate hate.

    find the un-pretzeled version on my website.

## phimvt@lurac.latrobe.edu.au — 2004-08-03 06:12:06

    It would be useful for readers if there was some kind of compact

    comparison of the various concatenative languages that we have

    been discussing here. I am proposing that this could be a joint

    effort, with sections preferably pretty much the same length.

    Something like 500 words, to be discussed. I would propose

    sections (and authors) as follows:

        1. Concatenative languages in general (MvT)

        2. Forth (BT)

        3. Joy (MvT)

        4. cK (SA)

        5. Factor (SP)

        6. XY (SA)

    This list is in what I remember as the chronological order.

    I cannot tell whether 4. and 6. should be treated as one

    or two. I also know that there are (were ?) one or two other

    designs in the making, this would be a good spot to revive

    them. Of course the sections can only give a superficial

    view of the languages, but such is the nature of comparisons.

    But we could also make the sections longer.

    I there is interest in such a collaborative effort, I should

    write a draft of section 1. rather quickly so that all authors

    can comment on it and then write their own specialised section

    with possible reference to it.

    Any thoughts?

      - Manfred

## William Tanksley, Jr — 2004-08-04 01:43:12

    I'd be glad to write about Forth. When you ask for a comparison,

    though, do you mean something more like a precis, or a summary? I

    couldn't compare Forth to any of the others except Joy or maybe cK; I

    don't know enough about them to do them justice. But I'd be glad to

    talk about Forth :-).

    -Billy

## Slava Pestov — 2004-08-04 01:55:21

    Hi,

    I think this is a great idea! Do you want each section to be 'free

    standing', or discuss differences with other concatenative languages?

    phimvt@... wrote:

     > It would be useful for readers if there was some kind of compact

    > comparison of the various concatenative languages that we have

    > been discussing here. I am proposing that this could be a joint

    > effort, with sections preferably pretty much the same length.

    > Something like 500 words, to be discussed. I would propose

    > sections (and authors) as follows:

    >

    >     1. Concatenative languages in general (MvT)

    >     2. Forth (BT)

    >     3. Joy (MvT)

    >     4. cK (SA)

    >     5. Factor (SP)

    >     6. XY (SA)

    >

    > This list is in what I remember as the chronological order.

    > I cannot tell whether 4. and 6. should be treated as one

    > or two. I also know that there are (were ?) one or two other

    > designs in the making, this would be a good spot to revive

    > them. Of course the sections can only give a superficial

    > view of the languages, but such is the nature of comparisons.

    > But we could also make the sections longer.

    >

    > I there is interest in such a collaborative effort, I should

    > write a draft of section 1. rather quickly so that all authors

    > can comment on it and then write their own specialised section

    > with possible reference to it.

    >

    > Any thoughts?

    >

    >   - Manfred

## sa — 2004-08-04 07:51:03

    i'm not sure when i'll be able to get to this - perhaps in a few weeks.

    meanwhile, i've encountered some serious difficulties with the xy

    design, which i'm not sure how to handle - perhaps someone else

    has some ideas.

    here's the issue:

    in xy, you can define uncons1 as the pattern:

      ; uncons1 { [[a A]] a A } ;

    uncons1 expects a list with car a and cdr A, and it pushes *onto the queue*

    the elements a and A.  if [a A] is e.g. [1 2 3], then 1 and [2 3] are pushed

    onto the queue and then evaluated, leaving 1 and [2 3] on the stack.  but

    if [a A] is [+ 2 3], then + and [2 3] are pushed, with the consequence that

    + is evaluated, and then [2 3].  this is not what we want for uncons.  so we

    can (should) define uncons as:

     ; uncons { [[a A]] `a A } ;

    in which case `+ and [2 3] are pushed, and so + and [2 3] wind up on the

    stack.

    this seems to work fine:  use ` to block evaluation - ` is shorthand for

      \\ a

    where \\ is the primitive quotation word:  it takes the next thing on the

    queue (a) and pushes it, unevaluated, onto the result stack.

    i haven't yet convinced myself that this blocks unwanted evaluation in

    all circumstances, but i've not yet succeeded in defining, in terms of the

    XY primitives, all the combinators on my list (i.e. Joy + K), which i think

    of as a kind of "proof of concept" of the basic idea that XY provides

    methods for manipulating unevaluated tokens in the queue.

    i'm tied up with work for the next several weeks, so i don't expect to have

    any time to pursue this.

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

    From: "William Tanksley, Jr" <wtanksleyjr@...>

    Sent: Aug 4, 2004 3:43 AM

    To: concatenative@yahoogroups.com

    Subject: Re: [stack] Five (?) concatenative languages

    I'd be glad to write about Forth. When you ask for a comparison,

    though, do you mean something more like a precis, or a summary? I

    couldn't compare Forth to any of the others except Joy or maybe cK; I

    don't know enough about them to do them justice. But I'd be glad to

    talk about Forth :-).

    -Billy

    Yahoo! Groups Links

## William Tanksley, Jr — 2004-08-04 15:15:16

    On Wed, 4 Aug 2004 09:51:03 +0200 (GMT+02:00), sa <sa@...> wrote:

     > in xy, you can define uncons1 as the pattern:

    >   ; uncons1 { [[a A]] a A } ;

     This makes sense.

     > uncons1 expects a list with car a and cdr A, and it pushes *onto the queue*

    > the elements a and A.  if [a A] is e.g. [1 2 3], then 1 and [2 3] are pushed

    > onto the queue and then evaluated, leaving 1 and [2 3] on the stack.  but

    > if [a A] is [+ 2 3], then + and [2 3] are pushed, with the consequence that

    > + is evaluated, and then [2 3].  this is not what we want for uncons.  so we

    > can (should) define uncons as:

     This doesn't make sense to me. Oh, yes, I suspect you can make it work

    this way, but allowing things to execute inside your stack manipulator

    word exposes your internal order of evaluation, which doesn't seem

    very clean.

    I also have to ask -- how did the execution of + get inside your list?

    I can see how + itself got in there, so I'd expect + to be left on the

    stack; but I don't see how or why any purely list operation could

    "accidentally" execute anything.

    -Billy

## sa@dfa.com — 2004-08-04 15:39:45

    suppose the queue consists of

          [+ 2 3] { [[a A]] a A }

    so [+ 2 3] is pushed on the stack, then { is evaluated, which looks

    ahead to the closing } and takes the list [[[a A]] a A ], matches [+ 2 3]

    to [a A], and populates a with + and A with [2 3].  + and [2 3] are then

    pushed onto the *queue*, *not* the stack.  the evaluator continues to

    process the queue.  it finds +, and then *evaluates* it.  which is not

    what we want.

    on the other hand,

          [+ 2 3] { [[a A]] `a A }

    leaves

          \\ + [2 3]

    on the queue, which *is* what we want:  \\ is evaluated, which

    finds + on the queue, moves it to the stack, &c.

    or perhaps i'm not doing a good job explaining how the evaluator

    works:  at every step it takes both the result stack and the input

    queue, and returns both a new result stack and a new input queue.

    "William Tanksley, Jr" <wtanksleyjr@...> wrote on 08/04/2004 05:15:16

    PM:

     > On Wed, 4 Aug 2004 09:51:03 +0200 (GMT+02:00), sa <sa@...> wrote:

    > > in xy, you can define uncons1 as the pattern:

    > >   ; uncons1 { [[a A]] a A } ;

    >

    > This makes sense.

    >

    > > uncons1 expects a list with car a and cdr A, and it pushes *onto the

     queue*

     > > the elements a and A.  if [a A] is e.g. [1 2 3], then 1 and [2 3] are

     pushed

     > > onto the queue and then evaluated, leaving 1 and [2 3] on the stack.

     but

     > > if [a A] is [+ 2 3], then + and [2 3] are pushed, with the consequence

     that

     > > + is evaluated, and then [2 3].  this is not what we want for uncons.

     so we

     > > can (should) define uncons as:

    >

    > This doesn't make sense to me. Oh, yes, I suspect you can make it work

    > this way, but allowing things to execute inside your stack manipulator

    > word exposes your internal order of evaluation, which doesn't seem

    > very clean.

    >

    > I also have to ask -- how did the execution of + get inside your list?

    > I can see how + itself got in there, so I'd expect + to be left on the

    > stack; but I don't see how or why any purely list operation could

    > "accidentally" execute anything.

    >

    > -Billy

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

## phimvt@lurac.latrobe.edu.au — 2004-08-06 06:08:37

    Thanks to everybody for the quick responses. To answer several

    questions, here is some clarification.

    It would require some detailed knowledge of all the languages

    to write a comparison of any one with the rest. Maybe we can

    leave such a project for much later. What I had in mind is

    much simpler:

    The introduction would look roughly like this: Various notations,

    various evaluations of expressions, postfix on stack, the

    useful stack operations dup swap pop and so on. Then the

    important result that these with these operations we are forced

    to say that such programs do not operate on numbers but on stacks.

    Hence concatenations of various programs compute the composition of

    the unary stack functions that are computed by the various parts.

    This is concatenative notation. No more, except to say that

    the various concatenative languages have this as a common part.

    I have started on this intro, and found my first version far too

    technical. The current one attempts to assume as little as

    possible. But I am finding it hard to stick to 500 words as

    I had suggested at first. Maybe 600 or 700.

    The  sections on specific concatenative languages can assume

    the introduction but probably not much else. The sections should

    contain essentially the principal additions to the bare concatenative

    notation. Word limits "negotiable", as they say.

    I'll hurry up to get the intro done - but the above summary

    should give you some clues to start thinking. And Stevan, yes

    we are happy to wait.

    Thanks all

      - Manfred

## Chris Cogan — 2004-08-08 04:01:26

    > I'd be glad to write about Forth. When you ask for a comparison,

    > though, do you mean something more like a precis, or a summary? I

    > couldn't compare Forth to any of the others except Joy or maybe cK; I

    > don't know enough about them to do them justice. But I'd be glad to

    > talk about Forth :-).

    >

    > -Billy

     Your remarks give me what seems to be a good idea: A list of attributes that

    concatenative languages (and sometimes other languages) can have that would

    enable them to be both compared to each other and also classified.

    1. Concatenation is at least one common trait. But, then, all programming

    languages are concatenative in a very broad sense (they concatenate

    statements, etc.), so we would want to restrict the term to languages that

    basically map the sequence of functions in the language to sequences of

    steps in execution, without introducing complexities like

    parameter-substitution and complex statements. Joy is more strictly

    concatenative than Forth, for example (no control constructs to get in the

    way).

    2. Another of the features about Joy that distinguish it from conventional

    functional languages is the lack of application (or, rather, the completely

    automatic nature of application, in that every function is automatically

    "applied" to the stack). I assume that all of the language in the list are

    like this, so this might not be a good basis for comparison, except with

    languages of completely different types.

    3. The use of a stack is itself a feature of languages, at least in terms of

    how they are typically implemented, and even two languages that use a stack

    can be differentiated somewhat on how they use it. Forth has a return stack,

    for example, and Joy does not, so those knowledgeable about the other

    languages (XY, etc.) might want to discuss the specifics of how the stack is

    used, whether they require a return stack, etc.

    4. Variables: We can compare languages on both whether they have variables

    or not, and, if they do, how they are used. Forth has variables, but it uses

    them sparingly, and Joy doesn't even have them.

    5. Whether a language has a fairly simple, straightforward structure is

    another area of comparison and classification. Joy is even simpler in

    structure than Forth, for example.

    6. Usefulness for general programming might be another classificatory

    dimension, in that, while some languages are theoretically universal, in

    practice, they are not very useful. Of course, we might want to qualify this

    by saying that a language is useful for such things as studying computation

    theory, even if it is not useful for writing games, business applications,

    word processors, or various other things.

    7. Control constructs. No really useful language gets away with being

    completely free of them, if only in the form of conditional branching. But

    most modern languages have explicit loops and some variant of if-then-else.

    Even Forth has them. Joy does not have them in the usual sense, of course,

    but it still has (much nicer) equivalents (ifte, etc). Thus, in describing a

    language, we might want to describe how it handles the need to be able to

    repeatedly, conditionally, or otherwise control the execution of code.

    8. Verbosity might be another dimension. Cobol and (I think) PL/1 are

    probably at least among the most verbose languages. APL and Forth and Joy

    all tend to require less long-windedness to "say" something in them than is

    required in other languages at the same general level of programming.

    9. What might be called programmer-efficient programming might be another

    "dimension." One of the things I like about Joy, Forth, Factor, etc., is the

    ease with which fragments of code can be given names and thereby made into

    single words/atoms. Many languages typically don't allow fairly short

    stretches of code to be turned into named entities. The only way you can get

    significant compression is by finding longer stretches of code that you use

    often enough to make it worthwhile to turn them into functions or

    subroutines. You won't find swons very tersely defined in Basic. In Basic,

    even if you have both swap and cons already written, there is still a lot of

    overhead in using them to write swons:

    Sub swons()

    swap()

    cons()

    End Sub

    Compare this with:

    swons == swap cons ;

    This latter is programmer-efficient coding. Don't get me started on Cobol or

    Pl/1 (yes, I'm afraid I've been around long enough to have worked with PL/1

    code, converting PL/1 to Fortran in the 1970's).

    10. Does code = data? Can we manipulate code easily with other code? It has

    been a primary design constraint of mine in making my own variant of Joy

    that this facility be retained even though it is to be a "compiled" language

    (in the form of what might be called "object-threaded code"(so far, this is

    actually working, though I'm still in mid-implementation).

    11. How far from the hardware is the language? One of the things that I

    don't much like about Forth is that actual data goes on the stack, so you

    can't put a long string on the stack without eating up stack space. In Joy,

    it doesn't matter how big a thing is. It takes exactly one unit of stack

    space regardless of its actual size, and we don't even have to know how wide

    a unit of stack space is. This is not so much a criticism of Forth as it is

    a recognition of their different origins and typical uses. For some

    purposes, this relative closeness to the hardware is a significant

    advantage, but for the kinds of programming that I'm mostly interested in, I

    don't want to be concerned with actual stack-width, actual memory, etc.

    12. Performance. This is so strongly dependent on how a language is

    implemented that it's mostly only meaningful if we are actually considering

    implementing something in the language where performance might be an issue.

    However, some languages seem more inclined to inefficiency than others,

    almost inherently. This is probably partly due to the difficulty that a

    compiler (okay, a compiler-writer) has in determining how to determine the

    "lowest common denominator" of code that will work for anything that it

    might have to handle.

    13. Closeness of fit between code and problem. Lower-level languages tend to

    allow the programmers to quite precisely fit the program to the problem.

    Higher-level languages tend to be more likely to require either doing more

    than one really wants to in order to get done what one wants, or to have

    extraneous processing that's not really part of doing what one really wants

    the program to do. This is related to, but not identical to, the issue of

    verbosity. Some languages tend to have sledgehammers and bulldozers, but no

    pliers or tweezers (metaphorically speaking). Cobol has a selection of

    clunky tools that are okay for their general uses (like batch processing in

    business), but not so good for doing such things as writing a game like Duke

    Nukem (I'd use a more recent game as an example, but I'm not a gamer so I

    don't keep up). You might be able to write such a game in such a language,

    but you'd end up using up a lot of CPU doing things that you don't really

    want to do merely because Cobol doesn't offer any more

    sharply-discriminating way to do it (consider trying to process lots

    bit-masks in Cobol). One way I think of this aspect of a programming

    language is: How closely does the outline of the program follow the outline

    of the problem? For a metaphor from geometry: An octagon more closely fits

    around a circle than a triangle does. The circumference is more nearly equal

    to that of the circle, and the area between the circle and the octagon is

    smaller than the area between a circle and an enclosing triangle, so there

    is, in a sense, less "waste" if one can use an octagon to approximate the

    circle rather than a triangle.

    What else? I'm sure I've left some things out, if only because I'm getting

    sleepy, so this is my official request to others to expand/modify the list

    of attributes/dimensions that we might want to use in comparing the

    languages MVT listed.

    I don't know anything about the other languages other than Forth and a

    little about XY and Factor (I skimmed over (some of) the documentation

    quickly to get the general idea, but need to go back to it), so it's quite

    likely that people can come up with additional language-aspects (or

    reformulations of ones listed) for the list.

    When we get through, we might be able to make a fairly reasonable

    comparison-table (or at least have a list of things to talk about in the

    500-word descriptions).

    Comments, additions, suggested modifications?

    --Chris Cogan

## phimvt@lurac.latrobe.edu.au — 2004-08-11 05:56:40

    Here is my first draft for the general introduction,

    warts and all. But I think the contents will stand.

    I send it out straight away so that the authors of

    the specific sections can see what they can presuppose

    (i.e., very little).

      - Manfred

    SOME TITLE TO BE DECIDED

    Introduction

    The following are examples for three possible notations for arithmetic

    expressions:

        prefix notation :    - 12 + 2 3

        infix notation  :    12 - (2 + 3)

        postix notation :    12 2 3 + -

    Parentheses are necessary for most larger expressions in infix notation.

    They are never necessary in prefix or postfix notation, but they are made

    compulsory for two common variants of prefix notation.

    Expressions in whatever notation can be evaluated in many ways. One is the

    school method of stepwise rewriting of the actual expressions.  Another is

    translation into one of various computer methods of shuffling results of

    operations across several named registers. The only restriction is that

    subexpressions have to be evaluated before the enclosing expression.

    Apart from this, subexpressions can be evaluated in any order, even

    concurrently.

    Postfix expressions can also be evaluated on a stack of anonymous

    registers. A stack is a linear structure that is best conceived

    vertically. There are instructions to "push" value on top, and to replace

    one or several on top by the single result of a computation In the example

    it works like this: "Push 12, push 2, push 3, replace top two by their

    sum, replace top two by their difference.  Note that the instructions are

    executed in the same order as the postfix expression.

    To square a number it has to be multiplied by itself.  To compute the

    square of the sum of two and three it should not be necessary to compute

    the sum twice. On a stack it coult be computed by

        2 3 + dup *

    which is executed as "Push 2, push 3, replace top two by their sum, push a

    duplicate or copy of the top value. Apart from the "dup" instruction, a

    stack can also have a "swap" instruction to interchange the top two

    values, and a "pop" instruction to discard the top value. These and

    similar others that perform more complex changes are not only useful but

    often essential.

    The previous expression is not an arithmetical expression in postfix

    notation, simply because "dup" is not an arithmetical operator.  Therefore

    the expression and allits parts have to be interpreted differently: the

    whole and any consecutive parts compute unary functions taking a stack as

    argument an yielding a stack as result.  All but the first part take as

    argument the result of the previous part.  The whole computes the

    composition of the functions computed by its parts.

    The whole expression is of course just the linear concatenation of its

    parts. Concatenation is an associative operation. The composition of

    functions is also associative. So meaning, what is computed, maps the

    syntactic operation of concatenation onto the semantic operation of

    function composition. This is only possible because both operations are

    associative binary operations.  Languages with such a connection between

    syntax and semantics are what Billy Tanksley has called concatenative

    languages.

    Apart from the intimate connection between syntax and semantics,

    concatenative languages have an interesting property of definitions.  In

    conventional languegs "square(x)" might be defined as "x * x", or some

    variant. Whatever the details, the head of the definition, "square(x)"

    introduces a formal parameter "x" which is then used in the body, "x * x".

    When the newly defined squaring function is later called with an actual

    parameter, the formal parameter has to become associated with this actual

    parameter, the value of an expressions. Concatenative languages do not

    need such an association, since "square" is simple defined as "dup *".

    Arithmetic expressions in prefix notation can also be evaluated on a

    stack, and a concatenative language in prefix order can do the same. But

    in either case the order of execution has to be backward and hence is less

    natural. All existing concatenative languages use a stack, but this is not

    required by the definition - structures other than a stack might fit the

    bill. A concatenative language can use a larger structure of which the

    stack is only a part. Other parts might be additional stacks or a file

    system for explicit input and output.  An implementation of a

    concatenative language need not evaluate expressions in the order in which

    they are written, but can use a different order and even evaluate

    concurrently - as long as the final result is the same.

    This introduction has described concatenative languages in terms of a core

    that is common to all existing implementations.  The remainder of this

    paper gives a broad summary description of what they add to the common

    core.  All have numbers, some have other simple data types or structure

    such as lists or vectors.  Any concatenative language needs a way of

    accessing the stack arbitrarily deep below the top, and this is done in

    different ways in the examples.  Any computer language needs a conditional

    construct if-the-else, and there are several concatenative solutions.

    Some have second order functions such as "map", "fold" and "filter",

    possibly with different names, for processing list or vectors, and some

    have many others, including user defined ones.  In some "programs = data",

    programs can be manipulated on the stack and later executed.  Finally,

    although all use a stack, some implement the stack as an array (of

    consecutive memory locations), and some as a linked list (which

    necessitates garbage collection).  To some extent the implementations have

    affected the design of the languages.

    END OF INTRODUCTION

## phimvt@lurac.latrobe.edu.au — 2004-08-11 06:32:21

    Since there are different ways of doing the conditional in concatenative

    languages, it might be good if we all had them for comparison.  This is

    more or less what I propose to put somewhere in the Joy section:

      - Manfred

    ...

    The conditional construct for branching is another combinator, written

    "ifte" (short for if-then-else).  It needs three parameters, an if-part, a

    then-part and an else-part. Like all other combinators in Joy, these

    parameters are expected on top of the stack:  third from top the if-part,

    second from top the then-part, and right on top the elSe-part. The

    combinator does not care how and when the parameters got there, but in

    most cases they will have been pushed just before "ifte"  is executed.

    Hence typical usage will take the form

        [if-part]  [then-part]  [else-part]  ifte

    In execution "ifte" stores away the parameters and then executes the

    if-part. Then it restores the stack to what it was before the test.

    Finally, if the test yielded true, it executes the if-part, otherwise it

    executes the then-part.

    ...

## phimvt@lurac.latrobe.edu.au — 2004-08-11 06:44:32

    Billy, you will have seen the previous posting about conditionals in Joy.

    The corresponding one for Forth would be something like this (pardon my

    Forth, you will have to Forthify it properly, but the intent should be

    clear):

    ...

    Forth also provides a conditional construct, which needs three parts: an

    if-part, a then-part and an else-part.  The if-part has to be a truth

    value on top of the stack.  The other two parts are always explicitly part

    of the program, and they take the form

        IF  then-part  ELSE  else-part  END

    The three capitalised words are the standard syntax.

    In execution the top value on the stack is examined,

    and if it is true, the then-part is executed, otherwise

    the else-part is executed.

    ...

    But feel free to change the style to whatever you are using

    in the rest of the Forth section.

      - Manfred

## phimvt@lurac.latrobe.edu.au — 2004-08-11 06:51:38

    On Sat, 7 Aug 2004, Chris Cogan wrote:

    [..]

    > Your remarks give me what seems to be a good idea: A list of attributes that

    > concatenative languages (and sometimes other languages) can have that would

    > enable them to be both compared to each other and also classified.

    [.. A very long and careful contribution to the discussion ..]

    Thank you very much for this, much appreciated. But I will need

    more time to stew over the many details. But one thing I would

    like to say right now: would you be interested to write a sort

    of conclusion/comparison/evaluation to the joint paper? You

    seem to be in a better position to write such a thing than anybody

    else.

    Thanks again

      - Manfred

## ccogan@cox.net — 2004-08-11 14:57:33

    > Thank you very much for this, much appreciated. But I will need

    > more time to stew over the many details. But one thing I would

    > like to say right now: would you be interested to write a sort

    > of conclusion/comparison/evaluation to the joint paper? You

    > seem to be in a better position to write such a thing than anybody

    > else.

    >

    > Thanks again

    >

    >   - Manfred

     Yes, I would. Of course it would be subject to correction by the rest of the gang. All of the languages and dialects seem to have interesting features or interesting variants of features. I'm not sure of my final opinion on the XY language's queue, but I think it's a clever idea that might smooth out the flow in a language. Salvatore Sanfilippo's "local variables" (in his tcl version of Joy, which he calls Apathy) seems even nicer to me. Perhaps a section on the more or less novel or special features of the languages would be in order.

    This might be a good time to bring up the subject of a book on Joy. I've been considering offering to help you do one. You've already got all or nearly all of the basic materials that would go into it. I've been hesitating because I'm not sure I'm in a position to afford the time it would take (though I could do whatever I do in such a way that others could pick up from wherever I left off if I did).

    The obvious title would be, _The Joy of Programming_, but that would probably be a little too cutesy (and it suggests a much more general coverage of programming).

    --Chris

## John Cowan — 2004-08-11 16:14:58

    ccogan@... scripsit:

     > The obvious title would be, _The Joy of Programming_, but that would probably be a little too cutesy (and it suggests a much more general coverage of programming).

     No, no!  The title should be _The Programming of Joy_!

    --

    John Cowan  jcowan@...  www.reutershealth.com  www.ccil.org/~cowan

    No man is an island, entire of itself; every man is a piece of the

    continent, a part of the main.  If a clod be washed away by the sea,

    Europe is the less, as well as if a promontory were, as well as if a

    manor of thy friends or of thine own were: any man's death diminishes me,

    because I am involved in mankind, and therefore never send to know for

    whom the bell tolls; it tolls for thee.  --John Donne

## Slava Pestov — 2004-08-15 19:41:06

    Chris Cogan wrote:

     > 2. Another of the features about Joy that distinguish it from conventional

    > functional languages is the lack of application (or, rather, the completely

    > automatic nature of application, in that every function is automatically

    > "applied" to the stack). I assume that all of the language in the list are

    > like this, so this might not be a good basis for comparison, except with

    > languages of completely different types.

     I think the stack is the key concept, not the "concatenative" nature.

    The latter is just implied by the former. I'm not aware of any language

    with implicit operands and postfix notation that does not use a stack.

     > 3. The use of a stack is itself a feature of languages, at least in terms of

    > how they are typically implemented, and even two languages that use a stack

    > can be differentiated somewhat on how they use it. Forth has a return stack,

    > for example, and Joy does not, so those knowledgeable about the other

    > languages (XY, etc.) might want to discuss the specifics of how the stack is

    > used, whether they require a return stack, etc.

     It might also be worth mentioning if the stacks are reflective -- if it

    is possible to write a function to print out the stack, etc.

     > 5. Whether a language has a fairly simple, straightforward structure is

    > another area of comparison and classification. Joy is even simpler in

    > structure than Forth, for example.

     Forth is simpler than all the others, I think, simply because it can fit

    inside, say, 8Kb of assembly, plus some hundreds of lines of supporting

    Forth code. The fact that the compiler is written in the language itself

    allows one to, for exmple, create a set of words for defining classes

    and methods and instantiating objects and so on, going far beyond the

    builtin VARIABLE scheme. Factor borrows the Forth metaprogramming model,

    but in this case the parser is not as close to the metal as a Forth

    compiler -- it simply builds nested linked lists from text. However, the

    style of programming is permitted in both, where one can define parsing

    words for a domain-specific language.

      > 7. Control constructs. No really useful language gets away with being

    > completely free of them, if only in the form of conditional branching. But

    > most modern languages have explicit loops and some variant of if-then-else.

    > Even Forth has them. Joy does not have them in the usual sense, of course,

    > but it still has (much nicer) equivalents (ifte, etc). Thus, in describing a

    > language, we might want to describe how it handles the need to be able to

    > repeatedly, conditionally, or otherwise control the execution of code.

     One thing I've noticed is that recursive algorithms in concatenative

    languages are almost always as easy to code as iterative ones, and

    sometimes easier. It might be worth mentioning if each language promotes

    a recursive or iterative style, or both.

     > 9. What might be called programmer-efficient programming might be another

    > "dimension." One of the things I like about Joy, Forth, Factor, etc., is the

    > ease with which fragments of code can be given names and thereby made into

    > single words/atoms.

     I believe the interactive style of programming, where short expressions

    can be tested at the prompt and then built up into complete definitions

    in a source file, is another closely related benefit. It is very easy to

    try out different approaches interactively, due to the reduced amount of

    typing compared to, say, BeanShell (an interactive Java interpreter).

     > Many languages typically don't allow fairly short

    > stretches of code to be turned into named entities. The only way you can get

    > significant compression is by finding longer stretches of code that you use

    > often enough to make it worthwhile to turn them into functions or

    > subroutines.

     Furthermore, in many languages these longer subroutines usually can't

    return more than one value. So you are forced to either:

    - Side-effect a parameter

    - Return a composite type of some kind -- a sequence, or an object with

    slots.

    - Write your code in such a way that each computation results in one

    value only.

     > You won't find swons very tersely defined in Basic. In Basic,

    > even if you have both swap and cons already written, there is still a lot of

    > overhead in using them to write swons:

     One thing I've noticed is that a lot of things that are done as macros

    of some kind in other languages can be defined as ordinary words in

    concatenative languages. For example, a constant can be defined as a

    word that just pushes it on the stack.

     > 11. How far from the hardware is the language? One of the things that I

    > don't much like about Forth is that actual data goes on the stack, so you

    > can't put a long string on the stack without eating up stack space.

     Many Forths include a memory manager in the style of malloc/free, or you

    can write one. And every Forth allows memory to be allocated in the

    dictionary with allot/forget.

     > 12. Performance. This is so strongly dependent on how a language is

    > implemented that it's mostly only meaningful if we are actually considering

    > implementing something in the language where performance might be an issue.

    > However, some languages seem more inclined to inefficiency than others,

    > almost inherently. This is probably partly due to the difficulty that a

    > compiler (okay, a compiler-writer) has in determining how to determine the

    > "lowest common denominator" of code that will work for anything that it

    > might have to handle.

     It might be worth mentioning the execution models typical for the

    language. For example, Forth is usually implemented as indirect, direct

    or subroutine threaded code. Factor and Joy interpreters iterate linked

    lists recursively.

    Slava

## phimvt@lurac.latrobe.edu.au — 2004-08-17 06:14:19

    Here is my draft for the Joy section.

    I humbly submit it to your savage criticism.

      - Manfred

    THE CONCATENATIVE LANGUAGE JOY

    The datatypes of Joy are integers, reals, truth values, strings (of

    characters), small sets of numbers (0..31), dates and times, possibly

    heterogeneous lists of any datatypes including lists, and files for

    explicit input and output. For all datatypes the usual operators are

    provided, and where possible these are polymorphic. In addition to these

    there are the operators for shuffling the elements of the untyped stack.

    Joy has a large number of combinators, higher order functions which take

    other functions as arguments. These arguments are in the form of programs

    to compute other functions. Like all other arguments of functions, these

    arguments are expected on the stack, but they have to be in an unevaluated

    form called quotations, written inside square brackets. Lists are just a

    special case of quotations, for example [3 12 7], or [peter paul mary],

    or [3 [4 5] "two"].

    Three well known higher order functions are for manipulating lists. For

    example, given a list of numbers on top of the stack, the following simple

    programs can be used: the first to produce a list of their squares, the

    second to retain numbers less than 10 and discard others, the third to

    compute their sum.

        [dup *] map

        [10 <] filter

        0 [+] fold

    In all three examples the quotations are being pushed onto the stack just

    before the combinators execute.

    One important combinator is the "dip" combinator which is used to access

    the stack below the top. In the following, the first program adds the

    fourth, third and second element on the stack but leaves the first element

    on top. The second one interchanges the third and second element and

    leaves the first on top.

        [+ +] dip

        [swap] dip

    To access the stack further down than the top element, the "dip"

    combinator can be nested.

    Many combinators take several quotations as arguments. One example is the

    "ifte"  (if-then-else) combinator for branching. It expects three

    quotations on the stack, an if-part, a then-part, and topmost an

    else-part. For example a program which increments numbers less than 10 and

    decrements others is this:

        [1 <]  [1 +]  [1 +]  ifte

    Note that in this example the if-part [10 <] consumes the number argument,

    but it is automatically restored before the appropriate other part is

    executed.

    The three list manipulating combinators at the beginning abstract from

    common recursion patterns use with lists. Joy also has combinators that

    abstract from more general recursion patterns that are not restricted to

    lists. There are combinators for linear recursion, tail recursion, binary

    recursion, more general n-ary recursion, and even the rare nested

    recursion (best known from the Ackermann function. Most resemble the

    "ifte"

    combinator, except that the else-part is split into two, and the recursion

    occurs between the two parts. For example the quicksort algorithm might be

    paraphrased like this: If the list is small, being empty or having only

    one member, then it is sorted already. Otherwise, use its first element as

    a pivot to split the rest into two lists, those smaller and those larger

    than the first. Recursively, sort the two lists, and then combine the two

    results with the pivot. The following one-liner implements this in Joy:

        [small]  []  [uncons [>] split]  [swapd cons concat]  binrec

                                       ^^

                                       two recursions occur here

    Note that the recursion occurs without a recursive definition. Of course

    Joy allows definitions, including recursive ones, in this style:

        square  ==  dup *

    The various general and specialised libraries contain many useful

    definitions which extend the base language. There is also a simple module

    system which so far has not been used much.

    The current implementation of Joy is written in C. Programs, quotations,

    lists, and the stack itself are implemented as singly linked lists. I

    thank members of the "concatenative" mailing group for numerous

    suggestions and corrections, especially John Cowan who wrote a major

    portion of the implementation.

    END OF CONCAT-JOY

## phimvt@lurac.latrobe.edu.au — 2004-08-17 06:25:51

    On Wed, 11 Aug 2004 ccogan@... wrote:

    [..]

    > This might be a good time to bring up the subject of a book on Joy.

    > I've been considering offering to help you do one. You've already got

    > all or nearly all of the basic materials that would go into it. I've

    > been hesitating because I'm not sure I'm in a position to afford the

    > time it would take (though I could do whatever I do in such a way that

    > others could pick up from wherever I left off if I did).

    >

    > The obvious title would be, _The Joy of Programming_, but that would

    > probably be a little too cutesy (and it suggests a much more general

    > coverage of programming).

    That is certainly something we should discuss in detail.  You may or may

    not know that my original version of the chapters was written in Latex,

    and I still have those files. I tried a publisher, but they did not bite.

    Of course by now they are very much outdated, as are the current HTML

    pages.  We should decide whether to go for Latex or for HTML.

    Views anyone ?

    And thanks for the offer

      - Manfred

## phimvt@lurac.latrobe.edu.au — 2004-08-17 06:45:12

    On Sun, 15 Aug 2004, Slava Pestov wrote:

     > Chris Cogan wrote:

    > > 2. Another of the features about Joy that distinguish it from conventional

    > > functional languages is the lack of application (or, rather, the completely

    > > automatic nature of application, in that every function is automatically

    > > "applied" to the stack). I assume that all of the language in the list are

    > > like this, so this might not be a good basis for comparison, except with

    > > languages of completely different types.

    >

    > I think the stack is the key concept, not the "concatenative" nature.

    > The latter is just implied by the former. I'm not aware of any language

    > with implicit operands and postfix notation that does not use a stack.

     The stack is not essential, except that:

       1.  it is an obvious and convenient may of implementing postfix

       2.  it is psychologically useful for explaining the language

    See the chapter on rewriting systems for Joy (which I have not looked at

    myself for a long time, I admit). Like any functional language, Joy and

    can be implemented by a (non-deterministic) rewriting system. A stack is

    just a convenient way to order the steps efficiently.

    You are right in saying that Joy does not have an application operation

    not even implicitly. If the stack were essential, then application

    would be an implicit operation taking the stack as operand. I know

    I talk like that (and everybody else does, too), when I explain Joy.

    But strictly speaking it is not true. It is a useful myth, but maybe

    we should make clearer that it is. So, some better way of talking

    and explaining is perhaps called for.

      - Manfred

## Sergei Zubkov — 2004-08-18 07:35:08

    Hello

    I believe I haven't posted here yet, but I want to ask something

    regarding this thread:

    Slava and Manfred wrote:

     > > I think the stack is the key concept, not the "concatenative"

    > > nature. The latter is just implied by the former. I'm not aware

    > > of any language with implicit operands and postfix notation that

    > > does not use a stack.

    > The stack is not essential, except that:

    >    1.  it is an obvious and convenient may of implementing postfix

    >    2.  it is psychologically useful for explaining the language

     Here's my question - can J be considered a partially concatenative

    language? It has extensive facilities for eliminating explicit

    arguments from expressions and creating "trains of verbs" which are

    the same (in my opinion) as fragments of a forth-like language

    program. Those trains are actually encouraged throughout J manuals.

    There is no data stack, but functions and higher-order operators are

    contatenated to form an expression that needs only a single

    application of its argument, if at all (they have functions that yield

    constants, too).

    --Sergey Zubkov

## sa@dfa.com — 2004-08-18 12:39:43

    phimvt@... wrote on 08/17/2004 08:14:19 AM:

     >

    >

    > Here is my draft for the Joy section.

    > I humbly submit it to your savage criticism.

    >

    >   - Manfred

    >

    >

    > Many combinators take several quotations as arguments. One example is the

    > "ifte"  (if-then-else) combinator for branching. It expects three

    > quotations on the stack, an if-part, a then-part, and topmost an

    > else-part. For example a program which increments numbers less than 10

     and

     > decrements others is this:

    >

    >     [1 <]  [1 +]  [1 +]  ifte

           [10 <] [1 +]  [-1 +] ifte

    in XY, ifte is defined:

          { [d c t e] d [e t] d c i true? at i }

    or non-patternishly as:

          pair [[dup] dip i false?] dip swap at i

## sa@dfa.com — 2004-08-18 16:25:19

    XY implementations of map (still looking for a simpler implementation),

    filter, fold:

    ; map    { [a p] `a [a @: [a p i] [[] a p map.] else] [a] if } ;

    ; map.   { [r a p] `a [r a uncons [,: p infra ,] dip p map.] [r] if } ;

    ; filter { [l p] l l p i &: @ } ;

    ; fold   { [a s p] `a [1 a _ s a *: p i p fold] [s] if } ;

    a non-patternish filter:

    ; filter [dup] dip i &: @ ;

## William Tanksley, Jr — 2004-08-21 17:21:29

    On Wed, 18 Aug 2004 07:35:08 -0000, Sergei Zubkov <cubbi@...> wrote:

     > Here's my question - can J be considered a partially concatenative

    > language? It has extensive facilities for eliminating explicit

    > arguments from expressions and creating "trains of verbs" which are

    > the same (in my opinion) as fragments of a forth-like language

    > program. Those trains are actually encouraged throughout J manuals.

    > There is no data stack, but functions and higher-order operators are

    > contatenated to form an expression that needs only a single

    > application of its argument, if at all (they have functions that yield

    > constants, too).

     No; this means that J is a dataflow-using language. The ability to

    write "tacit" functions in J does give you some of the advantages that

    concatenative languages share; however, in J that ability is largely

    accidental, and in fact all of the manuals I've read say that nobody

    knows whether it's possible to write every program tacitly. In

    concatenative languages, it's fundamental.

    BTW, the last thing I read about J was that the newest interpreter

    removed the ability to use trains. The only ones remaining are the

    hook and the fork. The problem is that nobody actually used the other

    ones, and they were rather arbitrary.

     > --Sergey Zubkov

     -Billy

## phimvt@lurac.latrobe.edu.au — 2004-08-24 06:01:07

    Would Sergei or Billy be interested to write a short exposition

    of this for the "5 concat L's" (maybe 5.5 or 6)? Back in the

    early days of the concatenative mailing group there was some

    discussion of J already.

      - Manfred

     On Sat, 21 Aug 2004, William Tanksley, Jr wrote:

    > On Wed, 18 Aug 2004 07:35:08 -0000, Sergei Zubkov <cubbi@...> wrote:

    > > Here's my question - can J be considered a partially concatenative

    > > language? It has extensive facilities for eliminating explicit

    > > arguments from expressions and creating "trains of verbs" which are

    > > the same (in my opinion) as fragments of a forth-like language

    > > program. Those trains are actually encouraged throughout J manuals.

    > > There is no data stack, but functions and higher-order operators are

    > > contatenated to form an expression that needs only a single

    > > application of its argument, if at all (they have functions that yield

    > > constants, too).

    >

    > No; this means that J is a dataflow-using language. The ability to

    > write "tacit" functions in J does give you some of the advantages that

    > concatenative languages share; however, in J that ability is largely

    > accidental, and in fact all of the manuals I've read say that nobody

    > knows whether it's possible to write every program tacitly. In

    > concatenative languages, it's fundamental.

    >

    > BTW, the last thing I read about J was that the newest interpreter

    > removed the ability to use trains. The only ones remaining are the

    > hook and the fork. The problem is that nobody actually used the other

    > ones, and they were rather arbitrary.

    >

    > > --Sergey Zubkov

    >

    > -Billy

## phimvt@lurac.latrobe.edu.au — 2004-08-24 06:23:34

    On Wed, 18 Aug 2004 sa@... wrote:

     > phimvt@... wrote on 08/17/2004 08:14:19 AM:

    > > Many combinators take several quotations as arguments. One example is the

    > > "ifte"  (if-then-else) combinator for branching. It expects three

    > > quotations on the stack, an if-part, a then-part, and topmost an

    > > else-part. For example a program which increments numbers less than 10

    > and

    > > decrements others is this:

    > >

    > >     [1 <]  [1 +]  [1 +]  ifte

    >

    >       [10 <] [1 +]  [-1 +] ifte       (* OOPS, yes, 10 of course, MvT *)

    > in XY, ifte is defined:

    >

    >       { [d c t e] d [e t] d c i true? at i }

    >

    > or non-patternishly as:

          ^^^^^^^^^^^^^^^^ I admire your creative use of the English language

     >

    >       pair [[dup] dip i false?] dip swap at i

     In Joy, a program that increments the number on top of the stack

    if the five numbers on top of the stack add up to less than 100

    and otherwise decrements it is this:

        [+ + + + 100 <]  [1 +]  [1 -]  ifte

    This is possible because after the test the stack is restored

    to what it was before the test, and then either the then-part

    of the else-part is executed. One way to define ifte in Joy

    might be a (somewhat clumsy) way that uses the stack operator

    to save the stack somehow, and then uses the (Forth-like)

    branch operator. But actually ifte is inbuilt, of course.

    I point this out, because I am not really sure whether

    you definition of ifte in XY could handle if-part tests

    which destroy an arbitrary amount of stack.

    Or, to give another example, here is a program which

    increments/decrements the top number according as

    the fifth number from the top is less than 10:

        [pop pop pop pop 10 <]  [1 +]  [1 -]  ifte

      - Manfred

## sa@dfa.com — 2004-08-24 07:22:54

    phimvt@... wrote on 08/24/2004 08:23:34 AM:

    [:]

     > In Joy, a program that increments the number on top of the stack

    > if the five numbers on top of the stack add up to less than 100

    > and otherwise decrements it is this:

    >     [+ + + + 100 <]  [1 +]  [1 -]  ifte

    > This is possible because after the test the stack is restored

    > to what it was before the test, and then either the then-part

    > of the else-part is executed. One way to define ifte in Joy

    > might be a (somewhat clumsy) way that uses the stack operator

    > to save the stack somehow, and then uses the (Forth-like)

    > branch operator. But actually ifte is inbuilt, of course.

    >

    > I point this out, because I am not really sure whether

    > you definition of ifte in XY could handle if-part tests

    > which destroy an arbitrary amount of stack.

     of course you are right.  here is a version which conforms

    to the joy spec:

          { [c t e] [e t] _x c infra *: true? @ i }

    thanks

     >

    > Or, to give another example, here is a program which

    > increments/decrements the top number according as

    > the fifth number from the top is less than 10:

    >     [pop pop pop pop 10 <]  [1 +]  [1 -]  ifte

    >

    >   - Manfred

    >

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >