# Concatenative macros?

## Robbert van Dalen — 2006-12-21 19:53:54

    The newest version (0.5) of the Enchilada language has macros onboard.

    This is mainly thanks to Stevan. He pushed me to include Billy's

    shuffle operator!

    Exactly because of macros, I could drop the typical stack operators

    such as duplicate, swap (and drop!).

    Enchilada macros come in two flavours: eager and lazy.

    Here is an example of a lazy macro that swaps two lists:

    {a b=b a}

    [1;2] [3;4] {a b=b a}

    [1;2] {a=[3;4] a}

    [3;4] [1;2]

    Here is an example of a eager macro that compiles into an interesting

    (but otherwise useless) other macro:

    {a b c==[c] b * [a;1;] * & [c] + +}

    8 5 {a b c==[c] b * [a;1;] * & [c] + +}

    8 {a b==[5] b * [a;1;] * & [5] + +}

    {a==[5;5;5;5;5;5;5;5;a;1;;a;1;;a;1;;a;1;;a;1;;a;1;;a;1;;a;1;;5]}

    Lazy macros are denoted with one equals(=) symbol while eager macros

    have two equals(=) symbols.

    Here are some other examples:

    {a=[a]}  (enlist)

    {a} (drop)

    (a=a a} (duplicate)

    Although macros are very powerful I consider them to be more Lispy

    then Joyish.

    I wonder what the concatenative list think of macros?

    If you are interested, my blog (http://my.opera.com/rapido/blog/) has

    the links to the lastest Enchilada documentation and implementation.

    - Robbert

## William Tanksley, Jr — 2006-12-21 22:34:02

    Robbert van Dalen <robbert.van.dalen@...> wrote:

     > The newest version (0.5) of the Enchilada language has macros onboard.

    > This is mainly thanks to Stevan. He pushed me to include Billy's

    > shuffle operator!

    > Exactly because of macros, I could drop the typical stack operators

    > such as duplicate, swap (and drop!).

     That's something I like. Remembering the names of some of those is

    frankly a pain.

     > Enchilada macros come in two flavours: eager and lazy.

     I don't know if I understand what that means.

     > Although macros are very powerful I consider them to be more Lispy

    > then Joyish.

     Shuffle notation is entirely concatenative. It looks like your macros

    are more like Lisp lambdas, not shuffle notation.

     > I wonder what the concatenative list think of macros?

     Nothing wrong with using a lambda when it helps. Just remember that

    while you're doing it, you're not concatenative anymore.

    I kind of like the idea of making lambdas (macros with functions

    inside them) look different from shuffle notation. Shuffles can be

    considered nothing more than a different way to name stack operators;

    lambdas are not so simple.

    But I understand the argument against this too: that macros are a

    single simple concept, and users won't want to split that into two

    parts, one that's "concatenatively pure" and one that's actually

    useful ;-).

    Your language; your call.

     > - Robbert

     -Billy

## Robbert van Dalen — 2006-12-22 09:52:49

    > > Enchilada macros come in two flavours: eager and lazy.

    >

    > I don't know if I understand what that means.

     Here is another example:

    1 2 3 {a b c=[a] [b] [c] + +} (lazy expansion)

    1 2 {a b=[a] [b] [3] + +}

    1 {a=[a] [2] [3] + +}

    [1] [2] [3] + +

    [1] [2;3] +

    [1;2;3]

    1 2 3 {a b c==[a] [b] [c] + +} (eager expansion)

    1 2 3 {a b c==[a;b;c]}

    1 2 {a b==[a;b;3]}

    1 {a==[a;2;3]}

    [1;2;3]

     > > Although macros are very powerful I consider them to be more Lispy

    > > then Joyish.

    >

    > Shuffle notation is entirely concatenative. It looks like your macros

    > are more like Lisp lambdas, not shuffle notation.

     Is that because shuffle notation is considered to be a word?, so:

    xyz-zyx

    is considered to be uncuttable? Then with the same reasoning I claim a

    macro also to be an uncuttable word :)

     > > I wonder what the concatenative list think of macros?

    >

    > Nothing wrong with using a lambda when it helps. Just remember that

    > while you're doing it, you're not concatenative anymore.

     OK. I guess I have to let it go then - macros are just to good to be left out!

     >

    > I kind of like the idea of making lambdas (macros with functions

    > inside them) look different from shuffle notation. Shuffles can be

    > considered nothing more than a different way to name stack operators;

    > lambdas are not so simple.

    >

    > But I understand the argument against this too: that macros are a

    > single simple concept, and users won't want to split that into two

    > parts, one that's "concatenatively pure" and one that's actually

    > useful ;-).

    >

    > Your language; your call.

     I guess with macros, Enchilada will eventually end up to be some kind

    of postfix lisp :)

     > -Billy

     [Robbert]

## William Tanksley, Jr — 2006-12-26 06:41:06

    Robbert van Dalen <robbert.van.dalen@...> wrote:

     > > > Enchilada macros come in two flavours: eager and lazy.

    > > I don't know if I understand what that means.

    > Here is another example:

    > 1 2 3 {a b c=[a] [b] [c] + +} (lazy expansion)

    > 1 2 3 {a b c==[a] [b] [c] + +} (eager expansion)

     In other words, lazy expansion is a normal inline lambda; eager

    expansion is like a Lisp macro. Right?

     > > > Although macros are very powerful I consider them to be more Lispy

    > > > then Joyish.

    > > Shuffle notation is entirely concatenative. It looks like your macros

    > > are more like Lisp lambdas, not shuffle notation.

    > Is that because shuffle notation is considered to be a word?, so:

    > xyz-zyx

    > is considered to be uncuttable? Then with the same reasoning I claim a

    > macro also to be an uncuttable word :)

     No, not because it's "considered" to be uncuttable (although it must

    be considered uncuttable in order to be considered a word, of course),

    but because it's form is easily lexable and its semantics are atomic.

    Neither criterion applies to macro notation.

    Macros come close to being lexable -- anything between { and } is

    obviously a macro, assuming macros are not nestable. This still makes

    knowing when you're splitting a lexeme difficult; in a flat grammar

    the only thing you need to know is that if you find a space, you can

    always split the word. If there are macros, you have to know about

    spaces AND about {}.

    Macros are definitely not atomic in semantics -- they can contain

    calls to any word, so they can do anything.

     > > > I wonder what the concatenative list think of macros?

    > > Nothing wrong with using a lambda when it helps. Just remember that

    > > while you're doing it, you're not concatenative anymore.

    > OK. I guess I have to let it go then - macros are just to good to be left out!

     I disagree; I think they're a positive danger. But that's because my

    goals are different from yours. I don't think that they're "good" as

    such; I think they're convenient, but there's a risk that people

    learning the language will use them instead of learning the language

    on its own terms.

    For that reason, I would split them into two parts: one non-optional

    part that does shuffling and nothing else (and is extremely easy to

    language-analyze), and another part that handles full variable

    substitution. Full variable substitution is undeniably useful, of

    course.

    But your language is not even close in purpose to mine. I accept your

    design decisions :-).

     > I guess with macros, Enchilada will eventually end up to be some kind

    > of postfix lisp :)

     You know, there have been a lot of reimplementations of Lisp. I hope

    it sounds like a positive statement when I say that Enchilada doesn't

    seem at all like a mere reimplementation of Lisp.

     > [Robbert]

     -Billy

## Robbert van Dalen — 2006-12-27 11:47:19

    > > Here is another example:

    >

    > > 1 2 3 {a b c=[a] [b] [c] + +} (lazy expansion)

    > > 1 2 3 {a b c==[a] [b] [c] + +} (eager expansion)

    >

    > In other words, lazy expansion is a normal inline lambda; eager

    > expansion is like a Lisp macro. Right?

     Yes, more or less. But alas, the problem with eager expansion is that

    we get all the hairy lambda stuff, such as alpha-conversion, etc. In

    the lazy case everything is much, much easier.

     > Macros come close to being lexable -- anything between { and } is

    > obviously a macro, assuming macros are not nestable. This still makes

    > knowing when you're splitting a lexeme difficult; in a flat grammar

    > the only thing you need to know is that if you find a space, you can

    > always split the word. If there are macros, you have to know about

    > spaces AND about {}.

     Macros may nest in Enchilada, just like lists.

     > Macros are definitely not atomic in semantics -- they can contain

    > calls to any word, so they can do anything.

     Yes you are right. Shuffle words are atomic as opposed to macros.

     > > OK. I guess I have to let it go then - macros are just to good to be left

    > out!

    >

    > I disagree; I think they're a positive danger. But that's because my

    > goals are different from yours. I don't think that they're "good" as

    > such; I think they're convenient, but there's a risk that people

    > learning the language will use them instead of learning the language

    > on its own terms.

     I guess I know what your goal is: to build a flat concatenative

    language that's cuttable anywhere..... A fine goal indeed!.....

    But I'm not so much concerned with Enchilada not being fully

    concatenative but rather with Enchilada being immutable and useable

    (while still being scalable).

    Anyway, the shuffle notation you helped invent has led me to introduce

    the macro construct. So you are partly to blame :-)

     > > I guess with macros, Enchilada will eventually end up to be some kind

    > > of postfix lisp :)

    >

    > You know, there have been a lot of reimplementations of Lisp. I hope

    > it sounds like a positive statement when I say that Enchilada doesn't

    > seem at all like a mere reimplementation of Lisp.

     Enchilada is a little bit different from Lisp, yes ;). But the dark

    (applicative) side is calling me.... :-)

     > -Billy

     Robbert

## William Tanksley, Jr — 2006-12-27 17:03:36

    Robbert van Dalen <robbert.van.dalen@...> wrote:

     > > In other words, lazy expansion is a normal inline lambda; eager

    > > expansion is like a Lisp macro. Right?

    > Yes, more or less. But alas, the problem with eager expansion is that

    > we get all the hairy lambda stuff, such as alpha-conversion, etc. In

    > the lazy case everything is much, much easier.

     I had to look alpha-conversion up :-). Now I remember. I would have

    expected alpha conversion to appear even in the lazy case... Certainly

    if you allow nested macros.

     > > Macros come close to being lexable -- anything between { and } is

    > > obviously a macro, assuming macros are not nestable. This still makes

    > > knowing when you're splitting a lexeme difficult; in a flat grammar

    > > the only thing you need to know is that if you find a space, you can

    > > always split the word. If there are macros, you have to know about

    > > spaces AND about {}.

    > Macros may nest in Enchilada, just like lists.

     Makes sense.

     > > Macros are definitely not atomic in semantics -- they can contain

    > > calls to any word, so they can do anything.

    > Yes you are right. Shuffle words are atomic as opposed to macros.

    > > > OK. I guess I have to let it go then - macros are just to good to be left

    > > > out!

    > > I disagree; I think they're a positive danger. But that's because my

    > > goals are different from yours. I don't think that they're "good" as

    > > such; I think they're convenient, but there's a risk that people

    > > learning the language will use them instead of learning the language

    > > on its own terms.

    > I guess I know what your goal is: to build a flat concatenative

    > language that's cuttable anywhere..... A fine goal indeed!.....

     Grin.. That's not so much my primary goal as it is a curiosity of

    mine. I'd love see such a thing, but it would surprise me if it were

    useful, and I'm pretty big on usefulness (in spite of appearances!).

    I'm really focussed on exploring concatenativity. Flatness appears to

    be an interesting and useful adjunct; we haven't explained precisely

    how it fits in, but it's definitely convenient and practical to have

    some amount of flatness.

     > But I'm not so much concerned with Enchilada not being fully

    > concatenative but rather with Enchilada being immutable and useable

    > (while still being scalable).

     Yes, indeed. Fine goals; not at cross-purposes with mine at all, but

    clearly we have different priorities. I definitely like what you're

    doing, though. Fun.

     > Anyway, the shuffle notation you helped invent has led me to introduce

    > the macro construct. So you are partly to blame :-)

     The story of my shame will outlive me. :-)

     > > > I guess with macros, Enchilada will eventually end up to be some kind

    > > > of postfix lisp :)

    > > You know, there have been a lot of reimplementations of Lisp. I hope

    > > it sounds like a positive statement when I say that Enchilada doesn't

    > > seem at all like a mere reimplementation of Lisp.

    > Enchilada is a little bit different from Lisp, yes ;). But the dark

    > (applicative) side is calling me.... :-)

     If once you start down the dark path, forever will it dominate your

    destiny, consume you it will, as it did PL/1.

    It's tempting to assume that the familiar (applicative notation with

    named parameters) is easier and (in your word) "usable". We all know

    it's not always true, but it's quick and convenient to assume that in

    this case it might be.

    Your job isn't to find out whether or not this is one of the cases

    where the familiar solution is the best one. That's my job :-).

     > Robbert

     -Billy

## Manfred Von Thun — 2007-01-02 09:08:04

    I liked the original ideas and the discussions on this topic. Just  a few

    brief comments:

    What you called ³eager² and ³lazy² macros seems to correspond pretty well to

    ³#define² macros in the C preprocessor and ordinary function definitions in

    C. Am I right here? Clearly most languages could use a macro processor, and

    in many it would be very useful. You might also call them ³compile-time² and

    ³run-time² operators (or something like that). I believe some languages even

    have ³link-time² and ³load-time² macros, but these distinctions only make

    sense in more complex systems. So, I would advise you to continue with the

    two, but you do need some really convincingly useful examples of the eager

    macros.

    About the pattern matching operators, written in the ³before-and-after²

    style, where (a b  b a)  implements swap, for example. I seem to remember a

    few years back some discussion on how to extend this to handle list

    manipulation. The pattern (a [b c D]  --  b a [c a D] b [D]) would match a

    stack whose top element is a list of at least two items, b and c, and which

    also has a second element a. This operator would remove these two items from

    the stack and then push the five items on the right of the ³--², which are:

    b, the first element of the list, then a, the original second element,

    then a list whose first two elements are c and a then the rest D of the

    list, then b again, and finally, on top, the list which is just the rest D

    of the list. Not a very useful example (contrary to my own advice), but

    you get the idea. It would help if someone could remember when this

    discussion occurred.

    It looks a bit like Prolog, doesn¹t it? In fact all the stack-shufflers and

    all list operators can be implemented in a Joy-in-Prolog using this style.

    Sticking to the ³before/after² style, here are some familiar ones:

        cons == (a [B] -- [a B])

        uncons == ([a B] -- a [B])

        first == ([a B] -- a)

        rest == ([a B] -- [B])

    Note that in the two examples all variables occurring to the right of

    the ²--² were already bound on the left of the ³--². That need not be

    so, but then we need some extra machinery. I will only give one

    example. Suppose I have a list of at least 3 items on top of the stack,

    and that third item is a number, and I wish to square it. In Joy I

    would write

        squarethird == uncons uncons unswons   dup *  swons cons cons

    In a pattern matching Prolog-like Joy I would write

        squarethird([x y z R] -- [x y w R])

            w = z dup *

    So the extra ³machinery² is precisely what in Prolog is the body of

    a relation.

    I cannot remember how far we went in our discussion some years back.

    I have resisted the pattern matching mechanism for Joy mainly for

    reasons  of purity. But I am also aware how some of the pattern matching

    languages allow very succinct code.

    I hope what I wrote is of some use to the language smiths on this group.

      - Manfred

    [Non-text portions of this message have been removed]

## Chris Double — 2007-01-02 13:02:08

    On 1/2/07, Manfred Von Thun <m.vonthun@...> wrote:

     >  The pattern (a [b c D]  --  b a [c a D] b [D]) would match a

    >  stack whose top element is a list of at least two items, b and c, and which

    >  also has a second element a.

     That's pretty nifty. I wrote some pattern matching routines for Factor

    a while back and for fun implented a 'shuffle' word that used it to do

    stack manipulation. I wrote about it here:

    http://www.bluishcoder.co.nz/2006/12/factor-pattern-matching-additions.html

    or if the URL wraps and doesn't work: http://wee-url.com/NBE12

    As an example, 2dup looks like: { ?a ?b } { ?a ?b ?a ?b } shuffle

    Where ?a and ?b are pattern matching variables. I didn't think about

    it at the time but implementing cons,etc works fine too:

    : mycons { ?a { ?b } } { { ?a ?b } } shuffle ;

    1 { 2 } mycons

     => { 1 2 }

    I like the idea of being able to do calculations to insert in the

    result - 'shuffle' unfortunately doesn't allow that.

    Since writing the pattern matching stuff I use it a lot. Not for stack

    shuffling though - it was just me playing around with the idea.

    Although it could get addictive!

    By the way, wee-url.com I linked above is implemented in Factor,

    written by Doug Coleman, one of the keen Factor users.

    Chris.

    --

    http://www.bluishcoder.co.nz

## Christopher Diggins — 2007-01-04 17:07:36

    It is perhaps interesting to mention the equivalence of stack shuffling

    notation and lambda expressions (other languages) which was identified by

    Brent Kerby http://tunes.org/~iepos/joy.html

    In other words a pattern such as:

    [c] [b] [a] -> [[c] b] [c] a

    Would be expressed in the lambda calculus as:

    \abc.ac(bc)

    Which rewritten with () around the arguments to a function looks like:

    \abc.a(c)(b(c))

    Notice this is simply the stack pattern written backwards. .

    I am planning on creating a separate language for expressing stack

    operations as shuffle operations. It is intended to operate on concatenative

    languages without itself being concatenative. This would be basically an

    implementation of the concatenative algebra. The tool would be useful for

    optimizing and manipulating concatenative code. A similar approach is used

    in the GHC haskell compiler.

    I am also interested in a Joy program for automatically generating Joy

    programs from lambda expressions. Does anyone have such a beast? The

    algorithm is provided on Brent Kerby's page (

    http://tunes.org/~iepos/joy.html ) I simply haven't yet had time to

    implement it yet. Chris double's Factor program does it, but apparently

    relies on a bit of Factor specific items to achieve the result.

    Christopher Diggins

    [Non-text portions of this message have been removed]

## William Tanksley, Jr — 2007-01-04 18:52:16

    Christopher Diggins <cdiggins@...> wrote:

     > It is perhaps interesting to mention the equivalence of stack shuffling

    > notation and lambda expressions (other languages) which was identified by

    > Brent Kerby http://tunes.org/~iepos/joy.html

     Yes, although there's nothing interesting about the fact that those

    are equivalent to lambdas -- they are, prima facia, lambdas, since

    they create a function that takes arguments which are expressed as

    named parameters and returns a function of those parameters.

    There are some minor things to notice about this notation.

    First, it's not immediately obvious that it's not a mere stack

    shuffle; it can also enlist and execute its parameters.

    Second, it is never used in Kerby's paper to delist, because that

    would require the language to officially know what is inside lists. In

    other words, the pattern on the left-hand-side must NEVER contain

    complex quoted expressions, just lists containing a single variable

    each.

    Third, it's more powerful than Kerby wants it to be. It's (allegedly)

    possible to write expressions in it, called in his paper

    "pseudo-combinators", that cannot be simplified so that their result

    contains only quotations and input variables.

     > In other words a pattern such as:

    > [c] [b] [a] -> [[c] b] [c] a

    > Would be expressed in the lambda calculus as:

    > \abc.ac(bc)

    > Which rewritten with () around the arguments to a function looks like:

    > \abc.a(c)(b(c))

    > Notice this is simply the stack pattern written backwards. .

     It took me AGES to recognize this, and when I finally did, I saw it

    was there in his paper all along.

    It gets much harder with lambda expressions which include combinators.

    I still haven't found an expression for any of the X combinators.

     > I am planning on creating a separate language for expressing stack

    > operations as shuffle operations. It is intended to operate on concatenative

    > languages without itself being concatenative. This would be basically an

    > implementation of the concatenative algebra. The tool would be useful for

    > optimizing and manipulating concatenative code. A similar approach is used

    > in the GHC haskell compiler.

     That's an excellent idea. You might want to think about how much power

    you want to put into that language, and for what purposes. Kerby's

    notation, as I've mentioned, has more power than he wanted to use; my

    notation for stack shuffles has deliberately too little power because

    it can neither execute its parameters nor enlist them.

    I wonder if a stack shuffle language which could execute, but not

    enlist, its parameters would be "just right"? The power to execute

    implies the power to enlist, after all, since you can always pass [[]

    cons] to the shuffle. Such a language might be expressed as something

    like:

    {abc--abCc} =>

    [a][b][c] == [a] [b] c [c]

    I still wouldn't include such a pattern language in my ideal language,

    but I certainly recognize that languages with other purposes would.

    The lack of list operators implies that the notation is not

    _primarily_ designed to manipulate lists, although it's possible to

    make it do so; it's designed to rearrange the stack, execute

    parameters, and allow the preservation of parameters.

    I haven't bothered implementing one of the X combinators in this

    notation (I only just invented the notation :-).

    More later, if I remember. (I've been doing a lot of work on the X

    combinator stuff.)

     > Christopher Diggins

     -Billy

## Robbert van Dalen — 2007-01-05 09:55:50

    >

    > What you called ³eager² and ³lazy² macros seems to correspond

    > pretty well to

    > ³#define² macros in the C preprocessor and ordinary function

    > definitions in

    > C. Am I right here?

     No, I would say they are more dynamic and very close to Lisp macros.

     > So, I would advise you to continue with the

    > two, but you do need some really convincingly useful examples of

    > the eager

    > macros.

     Eager macros are very useful to efficiently generate or compile code.

    Let's say you want to repeat an item with a constant.

    Here is the lazy version:

    3 5 {a b=[a] b * &}

    3 {a=[a] 5 * &}

    [3] 5 * &

    [3;3;3;3;3] 5 &

    [3;3;3;3;3]

    Here is the eager version:

    3 5 {a b==[a] b * |}

    3 {a==[a;a;a;a;a]}

    [3;3;3;3;3]

    Now we could reuse the eager macro to multiply items in a list with a

    constant:

    [1;2;3;4] [3 {a b==[a] b * |}] ! * | !

    [1;2;3;4] [{a==[a;a;a]}] * | !

    [1;2;3;4] [{a==[a;a;a]};{a==[a;a;a]};{a==[a;a;a]};{a==[a;a;a]}] | !

    [1 {a==[a;a;a]};2 {a==[a;a;a]};3 {a==[a;a;a]};4 {a==[a;a;a]}] !

    [[1;1;1];[2;2;2];[3;3;3];[4;4;4]]

    the lazy case would be less efficient:

    [1;2;3;4] [3 {a b=[a] b * |}] ! * | ! ! !

    [1;2;3;4] [{a=[a] 3 * |}] * | ! ! !

    [1;2;3;4] [{a=[a] 3 * |};{a=[a] 3 * |};{a=[a] 3 * |};{a=[a] 3 * |}]

    | ! ! !

    [1 {a=[a] 3 * |};2 {a=[a] 3 * |};3 {a=[a] 3 * |};4 {a=[a] 3 * |}] ! ! !

    [[1] 3 * |;[2] 3 * |;[3] 3 * |;[4] 3 * |] ! !

    [[1;1;1] 3 |;[2;2;2] 3 |;[3;3;3] 3 |;[4;4;4] 3 |] !

    [[1;1;1];[2;2;2];[3;3;3];[4;4;4]]

     >

    > About the pattern matching operators, written in the ³before-and-

    > after²

    > style, where (a b ‹ b a) implements swap, for example. I seem to

    > remember a

    > few years back some discussion on how to extend this to handle list

    > manipulation.

     I remember Stevan Apter has put some similar constructs in his XY

    language.

     >

    > It looks a bit like Prolog, doesn¹t it? In fact all the stack-

    > shufflers and

    > all list operators can be implemented in a Joy-in-Prolog using this

    > style.

    > Sticking to the ³before/after² style, here are some familiar ones:

    >

    > cons == (a [B] -- [a B])

    > uncons == ([a B] -- a [B])

    > first == ([a B] -- a)

    > rest == ([a B] -- [B])

     Wasn't it you that implemented Joy in Prolog in the first place? :)

     > I cannot remember how far we went in our discussion some years back.

    > I have resisted the pattern matching mechanism for Joy mainly for

    > reasons of purity. But I am also aware how some of the pattern

    > matching

    > languages allow very succinct code.

     I think (Prolog) pattern matching has more power than Enchilada macros.

    Enchilada macros are just lambdas (just variable substitution).

     >

    > I hope what I wrote is of some use to the language smiths on this

    > group.

     You certainly made me consider to include pattern matching in

    Enchilada, so yes!

     >

    > - Manfred

     Robbert.

## stevan apter — 2007-01-05 15:02:54

    i've implemented several versions of this, in XY, and then again in F

    and G (http://www.nsl.com/k/f/f.htm)

    in F/G:

    A pattern is a list whose head is a scheme and whose tail is a template

    A scheme is a name or a list of schemes. The case of the first letter

    in a name is significant. If lower-case, the name matches a single element.

    If upper-case, the name must occur as the final element in a list of schemes,

    and will match zero or more elements, viz. the remainder of the list whose

    initial elements are matched by schemes preceding the terminal name.

    A template is a list. If s is a symbol in the template which also occurs in

    the scheme, the value matched by s is substituted for s in the template.

    in G, ` is the pattern operator.  it takes a pattern, performs substitutions

    from the stack below it, and replaces the pattern and the elements consumed

    from the stack with the result.

    G also supports the more limited case of shuffles.  e.g. swap is the shuffle-

    symbol ab-ba.

    the G prelude defines some common words:

        http://www/k/f/g/prelude.g

    e.g. where ! is eval, dip is:

        [[a b][b!a]]`!

    in XY (http://www.nsl.com/k/xy/xy.htm) the result of pattern-evaluation

    is placed on the queue, so evaluation happens automatically.

    in F, four operators are defined which apply the pattern to either

    the stack or the queue, and place the result on either the stack or

    the queue.  on reflection, i thought this might be overkill, so G

    was defined to contain just the one pattern operator ` : stack->stack.

    i still believe that a single notation which treats stack-shuffling

    and list-construction/deconstruction in the same way is desirable,

    but as billy points out, patterns and macros do much more than that.

    although i haven't worked out the details, i think an extended form of

    shuffle-symbol would be just adequate.  e.g.

        [aB]-ab    uncons

        ab-[aB]    cons

        [aA]-a     car

        [aA]-A     cdr

    this is more powerful than the notation billy described, but less

    powerful than either XY patterns or enchilada macros.

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

    From: "Manfred Von Thun" <m.vonthun@...>

    To: <concatenative@yahoogroups.com>

    Sent: Tuesday, January 02, 2007 4:08 AM

    Subject: Re: [stack] Concatenative macros?

    I liked the original ideas and the discussions on this topic. Just  a few

    brief comments:

    What you called ³eager² and ³lazy² macros seems to correspond pretty well to

    ³#define² macros in the C preprocessor and ordinary function definitions in

    C. Am I right here? Clearly most languages could use a macro processor, and

    in many it would be very useful. You might also call them ³compile-time² and

    ³run-time² operators (or something like that). I believe some languages even

    have ³link-time² and ³load-time² macros, but these distinctions only make

    sense in more complex systems. So, I would advise you to continue with the

    two, but you do need some really convincingly useful examples of the eager

    macros.

    About the pattern matching operators, written in the ³before-and-after²

    style, where (a b < b a)  implements swap, for example. I seem to remember a

    few years back some discussion on how to extend this to handle list

    manipulation. The pattern (a [b c D]  --  b a [c a D] b [D]) would match a

    stack whose top element is a list of at least two items, b and c, and which

    also has a second element a. This operator would remove these two items from

    the stack and then push the five items on the right of the ³--², which are:

    b, the first element of the list, then a, the original second element,

    then a list whose first two elements are c and a then the rest D of the

    list, then b again, and finally, on top, the list which is just the rest D

    of the list. Not a very useful example (contrary to my own advice), but

    you get the idea. It would help if someone could remember when this

    discussion occurred.

    It looks a bit like Prolog, doesn¹t it? In fact all the stack-shufflers and

    all list operators can be implemented in a Joy-in-Prolog using this style.

    Sticking to the ³before/after² style, here are some familiar ones:

        cons == (a [B] -- [a B])

        uncons == ([a B] -- a [B])

        first == ([a B] -- a)

        rest == ([a B] -- [B])

    Note that in the two examples all variables occurring to the right of

    the ²--² were already bound on the left of the ³--². That need not be

    so, but then we need some extra machinery. I will only give one

    example. Suppose I have a list of at least 3 items on top of the stack,

    and that third item is a number, and I wish to square it. In Joy I

    would write

        squarethird == uncons uncons unswons   dup *  swons cons cons

    In a pattern matching Prolog-like Joy I would write

        squarethird([x y z R] -- [x y w R])

            w = z dup *

    So the extra ³machinery² is precisely what in Prolog is the body of

    a relation.

    I cannot remember how far we went in our discussion some years back.

    I have resisted the pattern matching mechanism for Joy mainly for

    reasons  of purity. But I am also aware how some of the pattern matching

    languages allow very succinct code.

    I hope what I wrote is of some use to the language smiths on this group.

      - Manfred

    [Non-text portions of this message have been removed]

## William Tanksley, Jr — 2007-01-05 16:16:14

    stevan apter <sa@...> wrote:

     > i still believe that a single notation which treats stack-shuffling

    > and list-construction/deconstruction in the same way is desirable,

    > but as billy points out, patterns and macros do much more than that.

    > although i haven't worked out the details, i think an extended form of

    > shuffle-symbol would be just adequate.  e.g.

    >     [aB]-ab    uncons

    >     ab-[aB]    cons

    >     [aA]-a     car

    >     [aA]-A     cdr

     I think you're probably right. I just did some work with the shuffle

    notation I proposed in my last post, which provided for stack shuffle

    and execution but not any support for lists. I didn't like the results

    at all.

    If you want a shuffle notation to be able to express all possible

    combinators, you have to support lists, execution, and shuffling. I

    don't see any way around that.

    I would propose a slight modification of your system, though. Your

    system doesn't allow for execution, and it has a little bit of

    redundancy, since the last letter in a list is ALWAYS the tail of the

    list, and therefore always has to be a list itself (unless you're

    going to support Lisp's "improper lists"; I'll assume in my notation

    that this isn't desired).

    Here's an alternate form:

         [ab]-ab   uncons

         ab-[ab]   cons

         [ab]-a     car

         [ab]-b     cdr

    This frees us up to use upper case to mean something else; I choose to

    make it mean execution.

        ab-A   k combinator

        a-A     i

        abc-[cB]cA  s combinator

    I'm not entirely satisfied with this. Consider the last combinator --

    the s combinator might also be written as

        abc-[[C]B][C]A  s combinator

    I'm just not entirely happy with the equivalence between lower case

    and quoted upper case. I suppose the problem is inherent in our choice

    to equate quotation and enlistment. On the other hand, this notation

    does offer a nice shorthand; my first definition of the s combinator

    is pleasantly short.

    It's also worth noting that your notation (and this notation) has both

    the ability to take apart input lists, AND manages to make it obvious

    when lists are being taken apart.

    There's a little problem. I can't figure out how to define Fokker's X

    combinator. (The following work uses Kerby's notation.)

     X = \f fS(\xyz x) =

         \f f(S)(\xyz x) =

         \f [\xyz x] [s] f =

        [\xyz x] [s] rot i

    Okay, now I'll use my shuffle notation...

        [abc-A] [abc-[cB]cA] abc-bcA

    The problem now is that I don't see how I can consolidate this into a

    single shuffle, which cues me that something's wrong.

    A doubt begins to stir in my mind. Is the Fokker X combinator actually

    a pseudo-combinator? If so, is that a problem with the Fokker X

    combinator, or is it a problem with Kerby's ideas about

    pseudo-combinators? If not, have I simply overlooked the solution, or

    is my shuffle notation a bit too weak?

     > this is more powerful than the notation billy described, but less

    > powerful than either XY patterns or enchilada macros.

     Definitely so.

    -Billy

## stevan apter — 2007-01-05 20:20:40

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Friday, January 05, 2007 11:16 AM

    Subject: Re: [stack] Concatenative macros?

    > stevan apter <sa@...> wrote:

    > > i still believe that a single notation which treats stack-shuffling

    > > and list-construction/deconstruction in the same way is desirable,

    > > but as billy points out, patterns and macros do much more than that.

    > > although i haven't worked out the details, i think an extended form of

    > > shuffle-symbol would be just adequate.  e.g.

    >

    > >     [aB]-ab    uncons

    > >     ab-[aB]    cons

    > >     [aA]-a     car

    > >     [aA]-A     cdr

    >

    > I think you're probably right. I just did some work with the shuffle

    > notation I proposed in my last post, which provided for stack shuffle

    > and execution but not any support for lists. I didn't like the results

    > at all.

    >

    > If you want a shuffle notation to be able to express all possible

    > combinators, you have to support lists, execution, and shuffling. I

    > don't see any way around that.

    >

    > I would propose a slight modification of your system, though. Your

    > system doesn't allow for execution, and it has a little bit of

    > redundancy, since the last letter in a list is ALWAYS the tail of the

    > list, and therefore always has to be a list itself (unless you're

    > going to support Lisp's "improper lists"; I'll assume in my notation

    > that this isn't desired).

    well, in my notation, [aB] and [ab] are different.  [aB] matches

    any list which contains at least one element.  then a is the first

    of that list and B is the rest.  but [ab] only matches those lists

    which contain exactly two elements.

    i don't know what an "improper list" is, so i probably wasn't

    intending to support them.  :-)

    >

    > Here's an alternate form:

    >

    >      [ab]-ab   uncons

    then you can't decompose a pair into its parts.

    >      ab-[ab]   cons

    or compose two things into a pair.

    >      [ab]-a     car

    >      [ab]-b     cdr

    etc.

    what am i missing?

    btw, i've lost the reference for the X combinator you've been

    discussing.

    >

    > This frees us up to use upper case to mean something else; I choose to

    > make it mean execution.

    >

    >     ab-A   k combinator

    >     a-A     i

    >     abc-[cB]cA  s combinator

    >

    > I'm not entirely satisfied with this. Consider the last combinator --

    > the s combinator might also be written as

    >

    >     abc-[[C]B][C]A  s combinator

    >

    > I'm just not entirely happy with the equivalence between lower case

    > and quoted upper case. I suppose the problem is inherent in our choice

    > to equate quotation and enlistment. On the other hand, this notation

    > does offer a nice shorthand; my first definition of the s combinator

    > is pleasantly short.

    >

    > It's also worth noting that your notation (and this notation) has both

    > the ability to take apart input lists, AND manages to make it obvious

    > when lists are being taken apart.

    >

    > There's a little problem. I can't figure out how to define Fokker's X

    > combinator. (The following work uses Kerby's notation.)

    >

    >  X = \f fS(\xyz x) =

    >      \f f(S)(\xyz x) =

    >      \f [\xyz x] [s] f =

    >     [\xyz x] [s] rot i

    >

    > Okay, now I'll use my shuffle notation...

    >

    >     [abc-A] [abc-[cB]cA] abc-bcA

    >

    > The problem now is that I don't see how I can consolidate this into a

    > single shuffle, which cues me that something's wrong.

    >

    > A doubt begins to stir in my mind. Is the Fokker X combinator actually

    > a pseudo-combinator? If so, is that a problem with the Fokker X

    > combinator, or is it a problem with Kerby's ideas about

    > pseudo-combinators? If not, have I simply overlooked the solution, or

    > is my shuffle notation a bit too weak?

    >

    > > this is more powerful than the notation billy described, but less

    > > powerful than either XY patterns or enchilada macros.

    >

    > Definitely so.

    >

    > -Billy

    >

## John Cowan — 2007-01-05 20:52:16

    stevan apter scripsit:

     > i don't know what an "improper list" is, so i probably wasn't

    > intending to support them.  :-)

     An improper list is one whose final cons does not have a car of nil.

    --

    He played King Lear as though           John Cowan <cowan@...>

    someone had played the ace.             http://www.ccil.org/~cowan

            --Eugene Field

## stevan apter — 2007-01-05 22:25:12

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

    From: "John Cowan" <cowan@...>

    To: <concatenative@yahoogroups.com>

    Sent: Friday, January 05, 2007 3:52 PM

    Subject: Re: [stack] Concatenative macros?

    > stevan apter scripsit:

    >

    > > i don't know what an "improper list" is, so i probably wasn't

    > > intending to support them.  :-)

    >

    > An improper list is one whose final cons does not have a car of nil.

    you know, i've just never really internalized lisp lists.  for

    me, a list is just a sequence.  everytime i have to understand

    something like this i have to forget what i know.  (never mind

    that i've implemented lisp lists several times -- they're just

    not intuitive (to me).)

    >

    > --

    > He played King Lear as though           John Cowan <cowan@...>

    > someone had played the ace.             http://www.ccil.org/~cowan

    >         --Eugene Field

    >

## William Tanksley, Jr — 2007-01-06 06:58:20

    stevan apter <sa@...> wrote:

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

    > > stevan apter <sa@...> wrote:

    > > > i still believe that a single notation which treats stack-shuffling

    > > > and list-construction/deconstruction in the same way is desirable,

    > > > but as billy points out, patterns and macros do much more than that.

    > > > although i haven't worked out the details, i think an extended form of

    > > > shuffle-symbol would be just adequate.  e.g.

    > > I think you're probably right. I just did some work with the shuffle

    > > notation I proposed in my last post, which provided for stack shuffle

    > > and execution but not any support for lists. I didn't like the results

    > > at all.

    > > If you want a shuffle notation to be able to express all possible

    > > combinators, you have to support lists, execution, and shuffling. I

    > > don't see any way around that.

    > > I would propose a slight modification of your system, though. Your

    > > system doesn't allow for execution, and it has a little bit of

    > > redundancy, since the last letter in a list is ALWAYS the tail of the

    > > list, and therefore always has to be a list itself (unless you're

    > > going to support Lisp's "improper lists"; I'll assume in my notation

    > > that this isn't desired).

    > well, in my notation, [aB] and [ab] are different.  [aB] matches

    > any list which contains at least one element.  then a is the first

    > of that list and B is the rest.  but [ab] only matches those lists

    > which contain exactly two elements.

     My system tries not to specify the shape of lists -- I consider it a

    bad habit. Even being able to take apart lists is mathematically

    problematic within a system that allows execution (notice that Kerby's

    notation never tries). The problem is that if you specify the shape of

    a list, you've got a problem if someone passes to you a list that's

    got the wrong shape, and your code doesn't explain what to do with

    that problem.

     > i don't know what an "improper list" is, so i probably wasn't

    > intending to support them.  :-)

     It's a list whose cdr points to an object rather than another list --

    in other words, a pair, since both the car and cdr are objects. But I

    don't think they're worth supporting for our general purposes.

     > > Here's an alternate form:

    > >      [ab]-ab   uncons

    > then you can't decompose a pair into its parts.

     That's what uncons does, unless you meant a "pair" as in an improper

    list -- but if so, that's only one special case, so there's no reason

    why we couldn't support it, aside from not wanting to. (We still can't

    create improper lists.)

     > >      ab-[ab]   cons

    > or compose two things into a pair.

     Again, how is this not composing two things into a pair?

     > >      [ab]-a     car

    > >      [ab]-b     cdr

    > etc.

    > what am i missing?

     I don't know -- am I missing something?

     > btw, i've lost the reference for the X combinator you've been

    > discussing.

     After reading http://ling.ucsd.edu/~barker/Iota/zot.html, I noticed a

    reference to "Rosser" and "Fokker". Citeseer showed me

    http://citeseer.ist.psu.edu/fokker97systematic.html, which lists quite

    a few others (note that Iota, Jot, and Zot all use a different one).

    I'm really working hard trying to figure out what the X combinator

    DOES to a stack...

    -Billy

## stevan apter — 2007-01-06 12:10:32

    between you and john, i now understand the point about "improper

    lists".

    i think the two notations can be made equivalent by adding a special

    symbol to each.

                      mine       yours

                      ----       -----

    pair-to-parts:    [ab]-ab    [ab.]-ab     for you, . means nil

    parts-to-pair:    ab-[ab]    ab-[ab.]

    k-combinator:     ab-a.      ab-A         for me, . means execute

    for me, . can only occur on the right side of a shuffle.  for you,

    . can only occur on the left side.

    on second thought, maybe you don't need the extra symbol.  isn't

    [ab[]] a pair?  (as i said, the "car/cdr/cons" approach to lists

    isn't the natural way for me think about these things.)  if this

    is the case, then i think i favor your notation.

    on the question of list-deconstruction and "bad input", it seems

    that you and robbert are in agreement.  i'd like to better understand

    the practical implications of this devil's bargain (freedom-from-

    exceptions for reduced expressiveness.)

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Saturday, January 06, 2007 1:58 AM

    Subject: Re: [stack] Concatenative macros?

    > stevan apter <sa@...> wrote:

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

    > > > stevan apter <sa@...> wrote:

    > > > > i still believe that a single notation which treats stack-shuffling

    > > > > and list-construction/deconstruction in the same way is desirable,

    > > > > but as billy points out, patterns and macros do much more than that.

    > > > > although i haven't worked out the details, i think an extended form of

    > > > > shuffle-symbol would be just adequate.  e.g.

    >

    > > > I think you're probably right. I just did some work with the shuffle

    > > > notation I proposed in my last post, which provided for stack shuffle

    > > > and execution but not any support for lists. I didn't like the results

    > > > at all.

    >

    > > > If you want a shuffle notation to be able to express all possible

    > > > combinators, you have to support lists, execution, and shuffling. I

    > > > don't see any way around that.

    >

    > > > I would propose a slight modification of your system, though. Your

    > > > system doesn't allow for execution, and it has a little bit of

    > > > redundancy, since the last letter in a list is ALWAYS the tail of the

    > > > list, and therefore always has to be a list itself (unless you're

    > > > going to support Lisp's "improper lists"; I'll assume in my notation

    > > > that this isn't desired).

    >

    > > well, in my notation, [aB] and [ab] are different.  [aB] matches

    > > any list which contains at least one element.  then a is the first

    > > of that list and B is the rest.  but [ab] only matches those lists

    > > which contain exactly two elements.

    >

    > My system tries not to specify the shape of lists -- I consider it a

    > bad habit. Even being able to take apart lists is mathematically

    > problematic within a system that allows execution (notice that Kerby's

    > notation never tries). The problem is that if you specify the shape of

    > a list, you've got a problem if someone passes to you a list that's

    > got the wrong shape, and your code doesn't explain what to do with

    > that problem.

    >

    > > i don't know what an "improper list" is, so i probably wasn't

    > > intending to support them.  :-)

    >

    > It's a list whose cdr points to an object rather than another list --

    > in other words, a pair, since both the car and cdr are objects. But I

    > don't think they're worth supporting for our general purposes.

    >

    > > > Here's an alternate form:

    > > >      [ab]-ab   uncons

    > > then you can't decompose a pair into its parts.

    >

    > That's what uncons does, unless you meant a "pair" as in an improper

    > list -- but if so, that's only one special case, so there's no reason

    > why we couldn't support it, aside from not wanting to. (We still can't

    > create improper lists.)

    >

    > > >      ab-[ab]   cons

    > > or compose two things into a pair.

    >

    > Again, how is this not composing two things into a pair?

    >

    > > >      [ab]-a     car

    > > >      [ab]-b     cdr

    >

    > > etc.

    > > what am i missing?

    >

    > I don't know -- am I missing something?

    >

    > > btw, i've lost the reference for the X combinator you've been

    > > discussing.

    >

    > After reading http://ling.ucsd.edu/~barker/Iota/zot.html, I noticed a

    > reference to "Rosser" and "Fokker". Citeseer showed me

    > http://citeseer.ist.psu.edu/fokker97systematic.html, which lists quite

    > a few others (note that Iota, Jot, and Zot all use a different one).

    >

    > I'm really working hard trying to figure out what the X combinator

    > DOES to a stack...

    >

    > -Billy

    >

## William Tanksley, Jr — 2007-01-07 01:56:05

    stevan apter <sa@...> wrote:

     > between you and john, i now understand the point about "improper

    > lists".

    > i think the two notations can be made equivalent by adding a special

    > symbol to each.

    >                   mine       yours

    >                   ----       -----

    > pair-to-parts:    [ab]-ab    [ab.]-ab     for you, . means nil

    > parts-to-pair:    ab-[ab]    ab-[ab.]

    > k-combinator:     ab-a.      ab-A         for me, . means execute

     Yes, that would make them equivalent (although "." wouldn't mean 'nil'

    for me; instead, it would be a code that meant that the previous item

    was the end of the list).

     > for me, . can only occur on the right side of a shuffle.  for you,

    > . can only occur on the left side.

    > on second thought, maybe you don't need the extra symbol.  isn't

    > [ab[]] a pair?  (as i said, the "car/cdr/cons" approach to lists

    > isn't the natural way for me think about these things.)  if this

    > is the case, then i think i favor your notation.

     Well, actually, [ab[]] (either of our notations) is the same thing as

    [aB] (in your notation) and [ab] in mine. I don't think [ab.] is a

    "pair" in the sense of an improper list. Personally, if you asked me,

    I don't think our notations need to support creating improper lists --

    they are really a special case of linked list, not really something

    languages should worry about in general.

    I don't see why we should care about a "pair" when it's so easy to

    deal with a "list". It's easy to create a list with two items; why

    bother with a "pair"? The only thing specifying a pair as input can do

    is force your shuffle to throw an error when the input is actually a

    list. And specifying a pair as output is only useful if your language

    includes words to process pairs specially.

    So I still don't see the need for the "." code.

     > on the question of list-deconstruction and "bad input", it seems

    > that you and robbert are in agreement.  i'd like to better understand

    > the practical implications of this devil's bargain (freedom-from-

    > exceptions for reduced expressiveness.)

     It simply depends on your language, I think. A language without list

    deconstruction is as powerful as a language with; but the language

    with might express some things more tersely.

    If the rest of your language doesn't use exceptions or runtime errors

    (like Enchilada), it's a forgone conclusion that your shuffles

    shouldn't support list deconstruction. If your language uses runtime

    errors and/or exceptions regularly, it's probably better to include

    support for list deconstructions. If your language is strongly

    staticly typed with decent type inference, list deconstructions will

    probably fit in nicely.

    IMO.

    -Billy

## stevan apter — 2007-01-08 13:15:37

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Saturday, January 06, 2007 8:56 PM

    Subject: Re: [stack] Concatenative macros?

    > stevan apter <sa@...> wrote:

    > > between you and john, i now understand the point about "improper

    > > lists".

    >

    > > i think the two notations can be made equivalent by adding a special

    > > symbol to each.

    >

    > >                   mine       yours

    > >                   ----       -----

    > > pair-to-parts:    [ab]-ab    [ab.]-ab     for you, . means nil

    > > parts-to-pair:    ab-[ab]    ab-[ab.]

    >

    > > k-combinator:     ab-a.      ab-A         for me, . means execute

    >

    > Yes, that would make them equivalent (although "." wouldn't mean 'nil'

    > for me; instead, it would be a code that meant that the previous item

    > was the end of the list).

    i was relying on the fact that [1 2 3] = 1 . 2 . 3 . nil.

    >

    > > for me, . can only occur on the right side of a shuffle.  for you,

    > > . can only occur on the left side.

    this directly contradicts the parts-to-pair expression above.

    >

    > > on second thought, maybe you don't need the extra symbol.  isn't

    > > [ab[]] a pair?  (as i said, the "car/cdr/cons" approach to lists

    > > isn't the natural way for me think about these things.)  if this

    > > is the case, then i think i favor your notation.

    >

    > Well, actually, [ab[]] (either of our notations) is the same thing as

    > [aB] (in your notation) and [ab] in mine.

    no, that isn't actually true.  in my notation [ab[]] is a list of three

    items:  a, b, and [].  [ab] in your notation is equivalent to [aB] in

    mine.

    > I don't think [ab.] is a

    > "pair" in the sense of an improper list. Personally, if you asked me,

    > I don't think our notations need to support creating improper lists --

    > they are really a special case of linked list, not really something

    > languages should worry about in general.

    >

    > I don't see why we should care about a "pair" when it's so easy to

    > deal with a "list". It's easy to create a list with two items; why

    > bother with a "pair"? The only thing specifying a pair as input can do

    > is force your shuffle to throw an error when the input is actually a

    > list. And specifying a pair as output is only useful if your language

    > includes words to process pairs specially.

    i think our miscommunication on this point is the rseult of terminological

    confusion, which is probably my fault.  for me, a pair is just a list with

    two elements; thus:  [1 2].  in the shuffle notation i've implemented in

    various languages, [ab] matches a to 1 and b to 2, and [aB] matches a

    to 1 and B the cdr of the list, viz. [2].

    if my program expects a two-element list, and wants to operate on

    those elements as named entities, then [ab] will pick them off and

    make them available to the program.  in your case, your program

    will use [ab]-aB.

    >

    > So I still don't see the need for the "." code.

    for you, [ab]-aB = [ab.]-ab, so i think you're right -- you don't need

    it.  for me, since on the left mean "rest of the list", . on the right

    means execute, and unless i want to forego the ability to fold that

    idea into the notation, i need it (or a third case beyond lower and

    upper!)

    >

    > > on the question of list-deconstruction and "bad input", it seems

    > > that you and robbert are in agreement.  i'd like to better understand

    > > the practical implications of this devil's bargain (freedom-from-

    > > exceptions for reduced expressiveness.)

    >

    > It simply depends on your language, I think. A language without list

    > deconstruction is as powerful as a language with; but the language

    > with might express some things more tersely.

    yes, i think i agree with that.  that's really the whole of my point.

    >

    > If the rest of your language doesn't use exceptions or runtime errors

    > (like Enchilada), it's a forgone conclusion that your shuffles

    > shouldn't support list deconstruction. If your language uses runtime

    > errors and/or exceptions regularly, it's probably better to include

    > support for list deconstructions. If your language is strongly

    > staticly typed with decent type inference, list deconstructions will

    > probably fit in nicely.

    >

    > IMO.

    >

    > -Billy

    >

## William Tanksley, Jr — 2007-01-10 16:21:19

    stevan apter <sa@...> wrote:

     > > stevan apter <sa@...> wrote:

    > > > between you and john, i now understand the point about "improper

    > > > lists".

    > > > i think the two notations can be made equivalent by adding a special

    > > > symbol to each.

     From the rest of your message, it's clear that you didn't want support

    for "improper lists"; what you wanted was the ability to get the last

    item out of a list without having to execute anything. A fine

    ambition. My notation (so far) doesn't support that, and I can see why

    you'd want it. Furthermore, it's a natural feature within any notation

    that allows list deconstruction, since such deconstruction naturally

    carries the exact same risk of error (said error being that the list

    doesn't have the desired structure).

     > > > on second thought, maybe you don't need the extra symbol.  isn't

    > > > [ab[]] a pair?  (as i said, the "car/cdr/cons" approach to lists

    > > > isn't the natural way for me think about these things.)  if this

    > > > is the case, then i think i favor your notation.

    > > Well, actually, [ab[]] (either of our notations) is the same thing as

    > > [aB] (in your notation) and [ab] in mine.

    > no, that isn't actually true.  in my notation [ab[]] is a list of three

    > items:  a, b, and [].  [ab] in your notation is equivalent to [aB] in

    > mine.

     No, you're right; my notation doesn't define an input meaning for

    [ab[]], because I didn't consider what happens to nested lists. That's

    because I didn't want to deal with list deconstruction, so I didn't

    put any thought into it. Further instances of not putting thought into

    things will be followed by further instances of putting my foot into

    my mouth.

    But this is worth thinking about.

    I believe that the strengths of our two syntaxes can and should be

    combined into a single semantics which would scale nicely, so that

    languages with differing needs can pick the subset that matches their

    needs and capabilities. Some languages require only shuffling; some

    require execution; some require list construction; some require list

    deconstruction into head and tail; and some require full list

    deconstruction.

    By the way, I admit grudgingly that some language designs do require

    lambda forms. I persist in claiming that our mega-shuffle notation

    need not support that; I would suggest that such languages should

    borrow syntax from an applicative language, since that class of

    languages has thoroughly researched the practice (a concatenative

    language with locals is essentially the same as Haskell interpreting a

    monad). Fitting lambda support into our notation would simply balloon

    the notation.

    Therefore, I choose to limit the features we need to support to

    shuffling, enlistment, delistment, indexing, and execution. (Here I

    choose to define "indexing" as accessing elements deeper in the list

    than the first element, what I earlier called "full list

    deconstruction".)

     > if my program expects a two-element list, and wants to operate on

    > those elements as named entities, then [ab] will pick them off and

    > make them available to the program.  in your case, your program

    > will use [ab]-aB.

     Unfortunately, my notation would make it impossible to execute a

    combinator which happened to be the CDR of a list, since I can only

    uppercase once. Strike one for my notation.

    So let me go a bit closer to your notation on the input side, except

    that 'a' and 'A' are no longer distinct variables. Case is used to

    control how the input is fetched and how the output is generated.

    I'm having some trouble defining (in my own head) the meaning of an

    uppercase letter on the input side. Even in your notation it seems a

    bit limited. The examples you gave are clear enough, but what happens

    if an uppercase letter appears in some other place than the tail of a

    list?

    Anyhow, it would be a start to define a special meaning for uppercase

    in the input: it's defined only as the last character in a list

    pattern, and as in your notation, it means "the rest of the list". On

    the output side, uppercase would indicate execution, as with my stack

    shuffle notation.

    I think that makes all your examples work, although "[aA]-a" doesn't

    work (it has to be changed to "[aB]-a", since variable names have to

    be unique regardless of case). Then the definition of cdr becomes

    "[aB]-b".

    I'm really not very happy with the fact that uppercase letters on the

    input side are undefined except at the tail of a list. I've thought of

    a few meanings, but none of them make me happy and fulfilled :-).

    I'm considering making upper case in the input side mean "gather as

    many values as will fit", which might be handy... What do you think?

    Doing that would change the definition of CDR to "[aB]-[b]", and would

    allow i to be defined as "[A]-A" (that means get the entire contents

    of a list and execute each of the atoms in it, first to last). Of

    course, an uppercase letter outside of a list would still be

    undefined, so I haven't really completely solved the problem, but at

    least I've opened a new door (I don't think either of our notations

    could express the definition of "i" before).

    -Billy

## sa@dfa.com — 2007-01-10 20:29:28

    i think i've formulated a version which captures your requirements.

    since setting down the rules is more difficult than grasping the

    notation by way of examples, let me do that first:

          car         [aB]-a

          cdr         [aB]-B

    B is the rest of the list [a ...].  that is, B is [...].

          cons        aB-[aB]

    B on the left matches a list.  on the right [aB] is the list

    with a as the first element, and B as the remaining elements.

    on either side, a list may contain at most one upper-case letter:

          [aBc]

    a is the first, c is the last, [B] is [aBc] without a, c.

          uncons      [aB]-aB

          i           A-a

    A matches a list, a is A i.

          dip         aB-ba

    so then what do the following shuffles mean?

          a-A

          [aB]-[ab]

    the first could be quotation; i.e. a-[a].

    the second could be disquotation without execution:

          [2 [3 +]] [aB]-[ab] -> [2 3 +]

    i don't see any problem extending the notation to handle nested

    lists on either side.

    but this is just off the top of my head, and i might have

    overlooked some lurking inconsistency.

    concatenative@yahoogroups.com wrote on 01/10/2007 11:21:19 AM:

     > stevan apter <sa@...> wrote:

    > > > stevan apter <sa@...> wrote:

    > > > > between you and john, i now understand the point about "improper

    > > > > lists".

    >

    > > > > i think the two notations can be made equivalent by adding a

     special

     > > > > symbol to each.

    >

    > From the rest of your message, it's clear that you didn't want support

    > for "improper lists"; what you wanted was the ability to get the last

    > item out of a list without having to execute anything. A fine

    > ambition. My notation (so far) doesn't support that, and I can see why

    > you'd want it. Furthermore, it's a natural feature within any notation

    > that allows list deconstruction, since such deconstruction naturally

    > carries the exact same risk of error (said error being that the list

    > doesn't have the desired structure).

    >

    > > > > on second thought, maybe you don't need the extra symbol. isn't

    > > > > [ab[]] a pair? (as i said, the "car/cdr/cons" approach to lists

    > > > > isn't the natural way for me think about these things.) if this

    > > > > is the case, then i think i favor your notation.

    >

    > > > Well, actually, [ab[]] (either of our notations) is the same thing as

    > > > [aB] (in your notation) and [ab] in mine.

    >

    > > no, that isn't actually true. in my notation [ab[]] is a list of three

    > > items: a, b, and []. [ab] in your notation is equivalent to [aB] in

    > > mine.

    >

    > No, you're right; my notation doesn't define an input meaning for

    > [ab[]], because I didn't consider what happens to nested lists. That's

    > because I didn't want to deal with list deconstruction, so I didn't

    > put any thought into it. Further instances of not putting thought into

    > things will be followed by further instances of putting my foot into

    > my mouth.

    >

    > But this is worth thinking about.

    >

    > I believe that the strengths of our two syntaxes can and should be

    > combined into a single semantics which would scale nicely, so that

    > languages with differing needs can pick the subset that matches their

    > needs and capabilities. Some languages require only shuffling; some

    > require execution; some require list construction; some require list

    > deconstruction into head and tail; and some require full list

    > deconstruction.

    >

    > By the way, I admit grudgingly that some language designs do require

    > lambda forms. I persist in claiming that our mega-shuffle notation

    > need not support that; I would suggest that such languages should

    > borrow syntax from an applicative language, since that class of

    > languages has thoroughly researched the practice (a concatenative

    > language with locals is essentially the same as Haskell interpreting a

    > monad). Fitting lambda support into our notation would simply balloon

    > the notation.

    >

    > Therefore, I choose to limit the features we need to support to

    > shuffling, enlistment, delistment, indexing, and execution. (Here I

    > choose to define "indexing" as accessing elements deeper in the list

    > than the first element, what I earlier called "full list

    > deconstruction".)

    >

    > > if my program expects a two-element list, and wants to operate on

    > > those elements as named entities, then [ab] will pick them off and

    > > make them available to the program. in your case, your program

    > > will use [ab]-aB.

    >

    > Unfortunately, my notation would make it impossible to execute a

    > combinator which happened to be the CDR of a list, since I can only

    > uppercase once. Strike one for my notation.

    >

    > So let me go a bit closer to your notation on the input side, except

    > that 'a' and 'A' are no longer distinct variables. Case is used to

    > control how the input is fetched and how the output is generated.

    >

    > I'm having some trouble defining (in my own head) the meaning of an

    > uppercase letter on the input side. Even in your notation it seems a

    > bit limited. The examples you gave are clear enough, but what happens

    > if an uppercase letter appears in some other place than the tail of a

    > list?

    >

    > Anyhow, it would be a start to define a special meaning for uppercase

    > in the input: it's defined only as the last character in a list

    > pattern, and as in your notation, it means "the rest of the list". On

    > the output side, uppercase would indicate execution, as with my stack

    > shuffle notation.

    >

    > I think that makes all your examples work, although "[aA]-a" doesn't

    > work (it has to be changed to "[aB]-a", since variable names have to

    > be unique regardless of case). Then the definition of cdr becomes

    > "[aB]-b".

    >

    > I'm really not very happy with the fact that uppercase letters on the

    > input side are undefined except at the tail of a list. I've thought of

    > a few meanings, but none of them make me happy and fulfilled :-).

    >

    > I'm considering making upper case in the input side mean "gather as

    > many values as will fit", which might be handy... What do you think?

    > Doing that would change the definition of CDR to "[aB]-[b]", and would

    > allow i to be defined as "[A]-A" (that means get the entire contents

    > of a list and execute each of the atoms in it, first to last). Of

    > course, an uppercase letter outside of a list would still be

    > undefined, so I haven't really completely solved the problem, but at

    > least I've opened a new door (I don't think either of our notations

    > could express the definition of "i" before).

    >

    > -Billy

    >

## stevan apter — 2007-01-10 22:19:09

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

    From: <sa@...>

    To: <concatenative@yahoogroups.com>

    Sent: Wednesday, January 10, 2007 3:29 PM

    Subject: Re: [stack] Concatenative macros?

    >

    >

    > i think i've formulated a version which captures your requirements.

    > since setting down the rules is more difficult than grasping the

    > notation by way of examples, let me do that first:

    >

    >       car         [aB]-a

    >       cdr         [aB]-B

    >

    > B is the rest of the list [a ...].  that is, B is [...].

    >

    >       cons        aB-[aB]

    >

    > B on the left matches a list.  on the right [aB] is the list

    > with a as the first element, and B as the remaining elements.

    >

    > on either side, a list may contain at most one upper-case letter:

    >

    >       [aBc]

    correction:  a list may contain any number of non-contiguous upper-

    case letter, e.g.

            [aBcDe]

    is fine, but

            [aBCd]

    is not.

    >

    > a is the first, c is the last, [B] is [aBc] without a, c.

    >

    >       uncons      [aB]-aB

    >

    >       i           A-a

    >

    > A matches a list, a is A i.

    >

    >       dip         aB-ba

    >

    > so then what do the following shuffles mean?

    >

    >       a-A

    >       [aB]-[ab]

    >

    > the first could be quotation; i.e. a-[a].

    >

    > the second could be disquotation without execution:

    >

    >       [2 [3 +]] [aB]-[ab] -> [2 3 +]

    >

    > i don't see any problem extending the notation to handle nested

    > lists on either side.

    >

    > but this is just off the top of my head, and i might have

    > overlooked some lurking inconsistency.

    >

    > concatenative@yahoogroups.com wrote on 01/10/2007 11:21:19 AM:

    >

    > > stevan apter <sa@...> wrote:

    > > > > stevan apter <sa@...> wrote:

    > > > > > between you and john, i now understand the point about "improper

    > > > > > lists".

    > >

    > > > > > i think the two notations can be made equivalent by adding a

    > special

    > > > > > symbol to each.

    > >

    > > From the rest of your message, it's clear that you didn't want support

    > > for "improper lists"; what you wanted was the ability to get the last

    > > item out of a list without having to execute anything. A fine

    > > ambition. My notation (so far) doesn't support that, and I can see why

    > > you'd want it. Furthermore, it's a natural feature within any notation

    > > that allows list deconstruction, since such deconstruction naturally

    > > carries the exact same risk of error (said error being that the list

    > > doesn't have the desired structure).

    > >

    > > > > > on second thought, maybe you don't need the extra symbol. isn't

    > > > > > [ab[]] a pair? (as i said, the "car/cdr/cons" approach to lists

    > > > > > isn't the natural way for me think about these things.) if this

    > > > > > is the case, then i think i favor your notation.

    > >

    > > > > Well, actually, [ab[]] (either of our notations) is the same thing as

    > > > > [aB] (in your notation) and [ab] in mine.

    > >

    > > > no, that isn't actually true. in my notation [ab[]] is a list of three

    > > > items: a, b, and []. [ab] in your notation is equivalent to [aB] in

    > > > mine.

    > >

    > > No, you're right; my notation doesn't define an input meaning for

    > > [ab[]], because I didn't consider what happens to nested lists. That's

    > > because I didn't want to deal with list deconstruction, so I didn't

    > > put any thought into it. Further instances of not putting thought into

    > > things will be followed by further instances of putting my foot into

    > > my mouth.

    > >

    > > But this is worth thinking about.

    > >

    > > I believe that the strengths of our two syntaxes can and should be

    > > combined into a single semantics which would scale nicely, so that

    > > languages with differing needs can pick the subset that matches their

    > > needs and capabilities. Some languages require only shuffling; some

    > > require execution; some require list construction; some require list

    > > deconstruction into head and tail; and some require full list

    > > deconstruction.

    > >

    > > By the way, I admit grudgingly that some language designs do require

    > > lambda forms. I persist in claiming that our mega-shuffle notation

    > > need not support that; I would suggest that such languages should

    > > borrow syntax from an applicative language, since that class of

    > > languages has thoroughly researched the practice (a concatenative

    > > language with locals is essentially the same as Haskell interpreting a

    > > monad). Fitting lambda support into our notation would simply balloon

    > > the notation.

    > >

    > > Therefore, I choose to limit the features we need to support to

    > > shuffling, enlistment, delistment, indexing, and execution. (Here I

    > > choose to define "indexing" as accessing elements deeper in the list

    > > than the first element, what I earlier called "full list

    > > deconstruction".)

    > >

    > > > if my program expects a two-element list, and wants to operate on

    > > > those elements as named entities, then [ab] will pick them off and

    > > > make them available to the program. in your case, your program

    > > > will use [ab]-aB.

    > >

    > > Unfortunately, my notation would make it impossible to execute a

    > > combinator which happened to be the CDR of a list, since I can only

    > > uppercase once. Strike one for my notation.

    > >

    > > So let me go a bit closer to your notation on the input side, except

    > > that 'a' and 'A' are no longer distinct variables. Case is used to

    > > control how the input is fetched and how the output is generated.

    > >

    > > I'm having some trouble defining (in my own head) the meaning of an

    > > uppercase letter on the input side. Even in your notation it seems a

    > > bit limited. The examples you gave are clear enough, but what happens

    > > if an uppercase letter appears in some other place than the tail of a

    > > list?

    > >

    > > Anyhow, it would be a start to define a special meaning for uppercase

    > > in the input: it's defined only as the last character in a list

    > > pattern, and as in your notation, it means "the rest of the list". On

    > > the output side, uppercase would indicate execution, as with my stack

    > > shuffle notation.

    > >

    > > I think that makes all your examples work, although "[aA]-a" doesn't

    > > work (it has to be changed to "[aB]-a", since variable names have to

    > > be unique regardless of case). Then the definition of cdr becomes

    > > "[aB]-b".

    > >

    > > I'm really not very happy with the fact that uppercase letters on the

    > > input side are undefined except at the tail of a list. I've thought of

    > > a few meanings, but none of them make me happy and fulfilled :-).

    > >

    > > I'm considering making upper case in the input side mean "gather as

    > > many values as will fit", which might be handy... What do you think?

    > > Doing that would change the definition of CDR to "[aB]-[b]", and would

    > > allow i to be defined as "[A]-A" (that means get the entire contents

    > > of a list and execute each of the atoms in it, first to last). Of

    > > course, an uppercase letter outside of a list would still be

    > > undefined, so I haven't really completely solved the problem, but at

    > > least I've opened a new door (I don't think either of our notations

    > > could express the definition of "i" before).

    > >

    > > -Billy

    > >

    >

    >

## William Tanksley, Jr — 2007-01-11 18:02:12

    sa@... <sa@...> wrote:

     > i think i've formulated a version which captures your requirements.

     I think I see some ambiguities.

     > since setting down the rules is more difficult than grasping the

    > notation by way of examples, let me do that first:

     Agreed.

     >       car         [aB]-a

    >       cdr         [aB]-B

    > B is the rest of the list [a ...].  that is, B is [...].

     I do like your notation of uppercase meaning "the rest of the list".

     >       cons        aB-[aB]

    > B on the left matches a list.

     But this is a contradiction. B on the left doesn't match a list; it

    matches "the rest of the list". It's true that at the end of the list

    "the rest of the list" happens to be a CDR, which is enclosed in a

    list -- but our notation hides that fact, and we shouldn't expect the

    user to know it.

    Therefore I propose that uppercase on the left not match a list, but

    rather match "the rest of the list" (and not be defined outside of a

    list, nor if used twice inside a list).

     > on the right [aB] is the list

    > with a as the first element, and B as the remaining elements.

     I propose that uppercase on the right side mean execution, always.

    So your example

     >       cons        aB-[aB]

     becomes (I suggest):

         cons        a[B]-[ab]

     > on either side, a list may contain at most one upper-case letter:

    >       [aBc]

     I agree with this, because obviously "the rest of the list" doesn't

    make sense when used more than once per list. Your followup message

    contradicts this because I think you were believing that uppercase

    meant "there is a list here", but that's not accurate. If you want to

    match a list, you can make it explicit, like this:

     [a[B][C]]-[c][b]

     >       uncons      [aB]-aB

     And in my proposed notation,

          uncons      [aB]-a[b]

    It's an implementation detail that B is entirely contained within the

    CDR list of the original list, so no new list needs to be formed.

     >       i           A-a

    > A matches a list, a is A i.

     This isn't accurate, because 'i' must execute each item, not merely

    unquote a list. It's also ambiguous what A means here -- you defined

    it as "rest of the list", but you're using it here as "a list".

    I propose:

          i           [A]-A

    First, we see that the unquoting is explicit, but different from

    execution. Second, we see that execution is expressed by uppercase

    letter on the right side. This means that uppercase means something

    different on the left and right side -- but this seems to me to be

    reasonable, since the left side is a pattern, while the right side is

    not.

     >       dip         aB-ba

     Again, I would express this as:

      dip  a[b]-Ba

     > so then what do the following shuffles mean?

    >       a-A

    > the first could be quotation; i.e. a-[a].

     In my notation, this is the general form of 'i'; it executes anything,

    list or non-list.

     >       [aB]-[ab]

    > the second could be disquotation without execution:

    >       [2 [3 +]] [aB]-[ab] -> [2 3 +]

     In my notation that would be identity.

    If you want disquotation without execution, you'd write:

      [a[B]]-[ab]

     > i don't see any problem extending the notation to handle nested

    > lists on either side.

     Correct, unless we confuse our notation with CDR notation. In our

    notation the tail of a list is not _written as_ a list -- it's a group

    of items. It's an array style notation. If we adopt your style, every

    list would have a CDR of [], so the two left-hand expressions [a[]]

    and [a] would match the same lists. I think it gets worse, because it

    would become difficult (ambiguous) to express lists that contain the

    empty list.

    -Billy

## sa@dfa.com — 2007-01-11 19:16:55

    i think i like this.

    concatenative@yahoogroups.com wrote on 01/11/2007 01:02:12 PM:

     > sa@... <sa@...> wrote:

    > > i think i've formulated a version which captures your requirements.

    >

    > I think I see some ambiguities.

    >

    > > since setting down the rules is more difficult than grasping the

    > > notation by way of examples, let me do that first:

    >

    > Agreed.

    >

    > > car [aB]-a

    > > cdr [aB]-B

    > > B is the rest of the list [a ...]. that is, B is [...].

    >

    > I do like your notation of uppercase meaning "the rest of the list".

    >

    > > cons aB-[aB]

    > > B on the left matches a list.

    >

    > But this is a contradiction. B on the left doesn't match a list; it

    > matches "the rest of the list". It's true that at the end of the list

    > "the rest of the list" happens to be a CDR, which is enclosed in a

    > list -- but our notation hides that fact, and we shouldn't expect the

    > user to know it.

    >

    > Therefore I propose that uppercase on the left not match a list, but

    > rather match "the rest of the list" (and not be defined outside of a

    > list, nor if used twice inside a list).

    >

    > > on the right [aB] is the list

    > > with a as the first element, and B as the remaining elements.

    >

    > I propose that uppercase on the right side mean execution, always.

    >

    > So your example

    > > cons aB-[aB]

    > becomes (I suggest):

    > cons a[B]-[ab]

    >

    > > on either side, a list may contain at most one upper-case letter:

    > > [aBc]

    >

    > I agree with this, because obviously "the rest of the list" doesn't

    > make sense when used more than once per list. Your followup message

    > contradicts this because I think you were believing that uppercase

    > meant "there is a list here", but that's not accurate. If you want to

    > match a list, you can make it explicit, like this:

    >

    > [a[B][C]]-[c][b]

    >

    > > uncons [aB]-aB

    >

    > And in my proposed notation,

    >

    > uncons [aB]-a[b]

    >

    > It's an implementation detail that B is entirely contained within the

    > CDR list of the original list, so no new list needs to be formed.

    >

    > > i A-a

    > > A matches a list, a is A i.

    >

    > This isn't accurate, because 'i' must execute each item, not merely

    > unquote a list. It's also ambiguous what A means here -- you defined

    > it as "rest of the list", but you're using it here as "a list".

    >

    > I propose:

    >

    > i [A]-A

    >

    > First, we see that the unquoting is explicit, but different from

    > execution. Second, we see that execution is expressed by uppercase

    > letter on the right side. This means that uppercase means something

    > different on the left and right side -- but this seems to me to be

    > reasonable, since the left side is a pattern, while the right side is

    > not.

    >

    > > dip aB-ba

    >

    > Again, I would express this as:

    >

    > dip a[b]-Ba

    >

    > > so then what do the following shuffles mean?

    >

    > > a-A

    > > the first could be quotation; i.e. a-[a].

    >

    > In my notation, this is the general form of 'i'; it executes anything,

    > list or non-list.

    >

    > > [aB]-[ab]

    > > the second could be disquotation without execution:

    > > [2 [3 +]] [aB]-[ab] -> [2 3 +]

    >

    > In my notation that would be identity.

    >

    > If you want disquotation without execution, you'd write:

    >

    > [a[B]]-[ab]

    >

    > > i don't see any problem extending the notation to handle nested

    > > lists on either side.

    >

    > Correct, unless we confuse our notation with CDR notation. In our

    > notation the tail of a list is not _written as_ a list -- it's a group

    > of items. It's an array style notation. If we adopt your style, every

    > list would have a CDR of [], so the two left-hand expressions [a[]]

    > and [a] would match the same lists. I think it gets worse, because it

    > would become difficult (ambiguous) to express lists that contain the

    > empty list.

    >

    > -Billy

    >

## William Tanksley, Jr — 2007-01-11 20:18:57

    sa@... <sa@...> wrote:

     > i think i like this.

     I just noticed a problem with my idea. Help me...

     > Billy wrote on 01/11/2007 01:02:12 PM:

    > > I propose:

    > > i1   [A]-A

     [...snip...]

     >    i2   a-A

    > In my notation, this is the general form of 'i'; it executes anything,

    > list or non-list.

     I'm wrong about i2. It won't correctly execute a list, because if i1

    works, the result of executing a list MUST be the list itself. (Try

    passing a list containing a list, such as [[2]], to 'i'.)

    So my notation can't express Joy's 'i', because my notation can only

    execute lists, not atoms.

    Unless, of course, we choose to allow me to define Joy's 'i' as:

     i == [ atom? ] [ a-A ] [ [A]-A ] ifte.

    That may be acceptable, since Joy's i wasn't originally intended to

    work that way (it just happened, from what I recall).

    What do you think?

    -Billy

## sa@dfa.com — 2007-01-11 20:49:27

    i don't quite follow the reasoning here, but it has always

    seemed to me that joy's 'i' (and other combinators as well)

    was unduly restrictive in requiring a *quotation* to

    execute.  and in fact i've never built that restriction

    into any of my languages.

    the way i've always thought of 'i' was that it took its

    operand x and:  if x is a quotation push the contents of

    x onto the queue, else push x onto the queue.  so

          [[2]] i

    pushes [2] onto the queue, and it winds up on the stack.

          3 i

    pushes 3 onto the queue, and it winds up on the stack.

          [+] i

    pushes + onto the queue, and then it's executed.

    so once again, why can't you interpret i1 and i2 in that

    framework?  in other words, what's wrong with your

    redefinition of 'i'?

    concatenative@yahoogroups.com wrote on 01/11/2007 03:18:57 PM:

     > sa@... <sa@...> wrote:

    > > i think i like this.

    >

    > I just noticed a problem with my idea. Help me...

    >

    > > Billy wrote on 01/11/2007 01:02:12 PM:

    > > > I propose:

    >

    > > > i1 [A]-A

    >

    > [...snip...]

    >

    > > i2 a-A

    > > In my notation, this is the general form of 'i'; it executes anything,

    > > list or non-list.

    >

    > I'm wrong about i2. It won't correctly execute a list, because if i1

    > works, the result of executing a list MUST be the list itself. (Try

    > passing a list containing a list, such as [[2]], to 'i'.)

    >

    > So my notation can't express Joy's 'i', because my notation can only

    > execute lists, not atoms.

    >

    > Unless, of course, we choose to allow me to define Joy's 'i' as:

    >

    > i == [ atom? ] [ a-A ] [ [A]-A ] ifte.

    >

    > That may be acceptable, since Joy's i wasn't originally intended to

    > work that way (it just happened, from what I recall).

    >

    > What do you think?

    >

    > -Billy

    >

## William Tanksley, Jr — 2007-01-12 16:59:40

    sa@... <sa@...> wrote:

     > i don't quite follow the reasoning here, but it has always

    > seemed to me that joy's 'i' (and other combinators as well)

    > was unduly restrictive in requiring a *quotation* to

    > execute.  and in fact i've never built that restriction

    > into any of my languages.

     I think that Joy's 'i' will work with a bare function (i.e., 2 2 [+]

    car i == 4). Manfred mentioned that he'd never thought of that while

    he was building it, and it was accidental (but nice) that it worked.

     > the way i've always thought of 'i' was that it took its

    > operand x and:  if x is a quotation push the contents of

    > x onto the queue, else push x onto the queue.  so

    >       [[2]] i

    > pushes [2] onto the queue, and it winds up on the stack.

    >       3 i

    > pushes 3 onto the queue, and it winds up on the stack.

    >       [+] i

    > pushes + onto the queue, and then it's executed.

    > so once again, why can't you interpret i1 and i2 in that

    > framework?  in other words, what's wrong with your

    > redefinition of 'i'?

     You're right. But it's still true that [A]-A and a-A are not *both*

    definitions of 'i'. Using your semantics, the problem is that the

    second one will execute the list (which will unquote it), but won't

    execute any of the things inside the list (functions will be dumped

    onto the stack).

    Compare the results of [+ -] a-A to the results of [+ -] [A]-A.

    So my definition didn't cover the cases well enough, and (at least)

    one of my examples was bad. I think I'm going to claim that the

    definition of i is a-A, and leave it at that; the meaning of [A]-A

    will be to perform 'i' on every item in the list (which is not the

    same as performing 'i' on the list).

    In other words, uppercase on the left *means* that each item in the

    uppercased variable gets 'i' applied to it.

    Okay, I think I'm satisfied... This problem was only in my example,

    not in my notation.

    -Billy

## sa@dfa.com — 2007-01-15 16:32:10

    solve the 99 lisp (haskell/prolog/etc.) problems in enchilada.

    :-)

## Robbert van Dalen — 2007-01-16 19:27:20

    I'd rather solve 99 lisp problems with the Game Of Live - now *thats*

    a challenge!

    but yes, it would be interesting to see how many symbols are needed

    to solve crossword puzzles in Enchilada.

    but seriously, such problems have to wait until Enchilada reaches

    version 1.0.

     On Jan 15, 2007, at 5:32 PM, sa@... wrote:

    >

    >

    > solve the 99 lisp (haskell/prolog/etc.) problems in enchilada.

    >

    > :-)

    >

## iepos — 2007-01-16 22:22:51

    Hi Billy & all,

    It's been a while! Sorry this post is a little belated. I tried

    sending it last week, but something was wrong with my account (my

    concatenative membership had expired, apparently; or maybe the list

    was unmoderated back when I used to use it). In any case, Yahoo ate

    my post up, so I had to rewrite it ...

     > A doubt begins to stir in my mind. Is the Fokker X combinator

     actually

     > a pseudo-combinator? If so, is that a problem with the Fokker X

    > combinator, or is it a problem with Kerby's ideas about

    > pseudo-combinators?

     Yes. The Fokker X combinator would be a "pseudo-combinator". But

    that was a bad choice of terminology on my part. Under the standard

    definition, it is a combinator. The restricted objects I was calling

    combinators are what Curry called "proper combinators". So we ought

    to say that the Fokker X combinator is an improper combinator, but a

    combinator nonetheless. To recap, here are the standard definitions

    which I should have used:

    Proper combinator: Any closed lambda-form in which all lambdas occur

    at the head (i.e., at the far left).

    Combinator: Any closed lambda-form whatsoever (or, equivalently: any

    combination of proper combinators)

    This applies to both applicative and concatenative systems (although

    the interpretation of "lambda" and "combination" of course depends

    on which system we're dealing with). Another way of putting it is

    that proper combinators are ones that can be expressed by a rewrite

    rule; i.e., in an applicative system, Z is a proper combinator if

    you can state a rule

      Zxyz == (some applicative combination of x, y, and z)

    or the like, with as many variables as needed; the standard

    combinators S, K, I, B, C, W, T, etc. are all proper, while the

    Fokker X combinator and, for example, Y, the "paradoxical" or fixed-

    point combinator, are not.

    Likewise, in a concatenative system, Z is a proper combinator if you

    can state a rule

      [z] [y] [x] Z == (some concatenative combination of x, y, and z)

    or the like, with as many variables as needed. The standard

    combinators i, cons, dip, cat, swap, dup, zap, k, and cat are all

    proper.

    Now, since the Fokker X combinator is improper, the question

    naturally arises: Is there a complete basis (in applicative

    combinatory logic) consisting of a single _proper_ combinator? The

    answer is no. The standard proof (due to William Craig) goes roughly

    like this: Every basis of proper combinators must contain a

    selector, i.e., a combinator like I or K, that takes some parameters

    (in a curried fashion, of course) and returns a certain one of them

    untouched, ignoring the rest. This is because selectors cannot be

    constructed out of other proper combinators; this can been seen by

    looking at the rewriting process: An expression Fxyz, for example,

    where F is written as some combination of proper combinators A, B,

    C, ..., none of which is a selector, can never reduce to just the

    the single variable 'x' by applying rewrite rules, because the

    rewrite rules for A, B, C, ... each have a right-hand-side

    consisting of something more than just a single variable. There is a

    combinator F (namely, the selector \xyz.x) for which Fxyz would

    reduce to x; but it is impossible to construct this F, or likewise,

    any selector, from a basis of non-selectors. Therefore, in a basis

    consisting of a single proper combinator, this combinator must be a

    selector. But selectors have no duplicative effect; therefore, it

    would be impossible to construct "W" or "S", for example. So a

    complete basis consisting of a single proper combinator does not

    exist.

    So in a complete basis of proper combinators, we need at least two.

    And of course it turns out that two is enough, since {S, K} is a

    complete basis. But if you allow improper combinators, then one is

    enough, as the Fokker X combinator shows, for instance.

    Now, what about in a concatenative system? Well, using an argument

    similar to the one above, we can show that a basis consisting of a

    single proper combinator is again impossible. This is because any

    basis of proper combinators must contain what I'll call a "total

    dequoter", i.e., a combinator whose right-hand-side contains no

    quotations; total dequoters simply execute some of their parameters

    (possibly multiple times, or none at all) in a certain order;

    examples would be i, k, zap, 'cat i', and

      X\ Y\ Z\ W\ Y X W X

    A total dequoter is needed, because if every combinator in the basis

    had a quotation on the right-hand-side, then it would never be

    possible to get down to an empty stack, once a quotation was on it;

    specifically, the expression [] F, where F is written as some

    combination of proper combinators A, B, C, ..., none of which is a

    total dequoter, could never reduce to the empty program, which shows

    that 'i' could not be constructed, since 'i' would be an F that

    works. Therefore, in a basis consisting of a single proper

    combinator, this combinator must be a total dequoter. But from a

    total dequoter alone, it is clearly impossible to construct cons, or

    even swap, dup, dip, or cat. So a basis consisting of a single

    proper combinator again does not exist.

    So the best we could hope for would be a two-combinator basis of

    proper combinators, or a one-combinator basis consisting of an

    improper combinator. We know that a basis of two proper combinators

    is possible; for example, {cake, k} works.

    So what about a one-combinator basis? This is an interesting

    question. It will not work to simply take the concatenative version

    of the Fokker X combinator (or the Rosser, or any other applicative

    one-combinator complete basis).  This would be equivalent to the

    basis {s, k}, which is _not_ complete in a concatenative system.

    From {s, k}, we can construct all applicative combinators (i, b, c,

    etc.) and even many others (swap, cons, dup, zap), but it would be

    impossible to construct dip (or cat). You can see this by looking at

    the rewrite rules for 's' and 'k':

    [Z] [Y] [X] s  ==  [[Z] Y] [Z] X

        [Y] [X] k  ==  X

    Note that on the right-hand-side of both rules, there is nothing to

    the right of the only dequoted term X. In reducing the

    expression '[B] [A] F', where F is some (concatenative) combination

    of 's' and 'k', every step of the reduction preserves the property

    that no subexpression contains a (dequoted) A followed by anything

    containing B; therefore, it could never reduce to 'A [B]'. So it is

    impossible to construct dip from {s, k}.

    But after some fiddling, I was able to find a one-combinator base

    that does work. The idea is to make a combinator with 'cake' and 'k'

    somehow embedded in it, built in such a way that, with a little

    manipulation, we can extract them back out. Let

    z == X\ zap [cake] [k] X

    or, in other words,

    z == [zap [cake] [k]] dip i

    Then

    [] [] z z

    == [] zap [cake] [k] z

    == [cake] [k] z

    == [cake] zap [cake] [k] k

    == [cake] [k] k

    == k

    So we can construct k. And

    [] [] [zap k] z

    == [] [] zap [cake] [k] zap k

    == [] [cake] [k] zap k

    == [] [cake] k

    == cake

    So we can construct cake. Explicitly, we can write them

    k    == [] [] z z

    cake == [] [] [[] [] [] z z [] [] z z] z

    So this {z} forms a complete basis. Incidentally, this construction

    doesn't depend specifically on 'cake'; you could replace 'cake' with

    any combinator that, along with 'k', forms a complete basis.

    - Brent

## William Tanksley, Jr — 2007-01-17 05:56:16

    iepos <bkerby@...> wrote:

     > Hi Billy & all,

    > It's been a while! Sorry this post is a little belated. I tried

    > sending it last week, but something was wrong with my account (my

    > concatenative membership had expired, apparently; or maybe the list

    > was unmoderated back when I used to use it). In any case, Yahoo ate

    > my post up, so I had to rewrite it ...

     Thank you for putting the effort in. I have one more question.

     > > A doubt begins to stir in my mind. Is the Fokker X combinator

    > > actually

    > > a pseudo-combinator? If so, is that a problem with the Fokker X

    > > combinator, or is it a problem with Kerby's ideas about

    > > pseudo-combinators?

    > Yes. The Fokker X combinator would be a "pseudo-combinator". But

    > that was a bad choice of terminology on my part. Under the standard

    > definition, it is a combinator. The restricted objects I was calling

    > combinators are what Curry called "proper combinators". So we ought

    > to say that the Fokker X combinator is an improper combinator, but a

    > combinator nonetheless. To recap, here are the standard definitions

    > which I should have used:

     Ah! A light dawns. Thank you again. Your definitions make sense.

     > But after some fiddling, I was able to find a one-combinator base

    > that does work. The idea is to make a combinator with 'cake' and 'k'

    > somehow embedded in it, built in such a way that, with a little

    > manipulation, we can extract them back out. Let

    > z == [zap [cake] [k]] dip i

     Nice. Now I'm going to have to try to understand Fokker's paper so I

    can try to construct a simpler version. (I'll have to pick a

    definition of "simpler".)

    Before I fiddle with that, though, I'm going to work on the

    two-combinator flat language... That's seriously interesting. To me.

     > - Brent

     -Billy

## William Tanksley, Jr — 2007-01-19 16:52:13

    Sorry; I said in my last post that I had one more question, and then I

    forgot to ask it.

    My question is: how does Okasaki's and Barker's work apply to this?

    Okay, actually, what I want to know is how to design a flat,

    two-combinator, concatenative language that's implemented using stacks

    and lists (like Joy).

    I've wanted to figure this out for a while, but my friend wants it in

    order to design a genetic algorithm system that allows maximum

    flexibility in cutting genomes.

    iepos <bkerby@...> wrote:

     > So what about a one-combinator basis? This is an interesting

    > question. It will not work to simply take the concatenative version

    > of the Fokker X combinator (or the Rosser, or any other applicative

    > one-combinator complete basis). This would be equivalent to the

    > basis {s, k}, which is _not_ complete in a concatenative system.

     Okasaki, in the postscript file linked to at

    http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp03, builds a

    concatenative system using different rules, under which the classical

    combinators form the classical structures (and so {s,k} is complete,

    hence the classical X combinators are complete). The difference

    between his notation and yours is that his notation uses combinators

    to build a list-structure which is then treated as a grammatical

    structure in itself; your notation has its own grammatical structure.

    His notation has two strengths: first, it harnesses directly the

    classic combinators; and second, it is syntactically completely flat

    (lists and quotation play no part in the grammar). I'm concerned that

    it has weaknesses that I don't understand, however, because I can't

    figure out how it actually works well enough to design an

    implementation.

    I also found Barker's work on Zot at

    http://ling.ucsd.edu/~barker/Iota/zot.html to be compelling -- I

    speculate that Zot (and probably Jot as well) qualify as

    concatenative, although they don't explicitly specify a stack (that

    could be another example of a non-stack-based concatenative language,

    or it could just be that the stack is hidden by the way in which the

    semantics of the language is described). Again, though, the notation

    used is foreign to me, so further examination is hindered. The reason

    I qualify Zot as probably concatenative is that the author describes

    several properties of it in ways that make me think it might meet my

    definitions as well. Interestingly, it's probably also applicative, if

    I read its notation right (although it doesn't provide

    variables/lambdas, so it's pure dataflow -- that certainly reduces the

    differences between the concepts).

     > But after some fiddling, I was able to find a one-combinator base

    > that does work. The idea is to make a combinator with 'cake' and 'k'

    > somehow embedded in it, built in such a way that, with a little

    > manipulation, we can extract them back out. Let

    > z == [zap [cake] [k]] dip i

     Interesting. I came up with a similar combinator (i.e. one which

    contained both cake and k) when I was attempting to build a system

    that didn't use a list structure as part of its grammar back a while

    ago. Unfortunately, my notes are lost, and since I wasn't trying for

    completeness (indeed, I didn't understand it at all) I doubt I

    achieved it.

    Your combinator, unlike Barker's and Okasaki's, makes sense to me :-).

    The problem is that I don't see whether it's possible to transform it

    to a flat system.

    My problem with non-flat systems isn't merely syntactic; my concern is

    that they hide infinite semantic complexity in the ability to create

    layers of quotations. It's hard to unambiguously measure the

    K-complexity of a non-flat syntax; do you count the depth of nesting,

    or do you count opening brackets, or ...? A flat syntax makes the

    K-complexity of things implemented in it obvious.

     > - Brent

     -Billy

## iepos — 2007-02-06 05:39:27

    Billy and all,

    Sorry for taking so long to respond to this. When I first read your

    email, the server hosting Chris Okasaki's paper was apparently down.

    And then for a couple weeks I forgot to come back and try it again. I

    must say -- What he's accomplished is pretty cool.

     > My question is: how does Okasaki's and Barker's work apply to this?

    > Okay, actually, what I want to know is how to design a flat,

    > two-combinator, concatenative language that's implemented using

     stacks

     > and lists (like Joy).

     I want to respond to your second question first; hopefully this will

    in turn shed some light on the relationship between flat

    concatenative systems and Okasaki's and Barker's work.

    When I wrote that flaky old program that searches for optimal Joy

    constructions, I put in an option to search only for flat

    constructions (activated by uncommenting the line "//#define

    NOQUOTES" :-) ) but never really pursued the problem, although I

    agree it is an interesting one.

    Let's try this. We're looking for a finite set of combinators from

    which we can construct any combinator by concatenation alone (no

    quotations). We'll say that such a set of combinators forms complete

    flat basis. To start, we observe that if "z" is any combinator

    forming a complete (non-flat) basis (for example, z == X\ zap [cake]

    [k] X, as we've seen), then {[], [z], unit, cat, i} forms a complete

    flat basis. Any concatenative combination of "z" can be decomposed

    into a flat one in terms of these combinators quite easily; For

    example,

       [z [z z] z]

    == [z] [[z z] z] cat

    == [z] [[z z]] [z] cat cat

    == [z] [z z] unit [z] cat cat

    == [z] [z] [z] cat unit [z] cat cat

    If the expression had contained a dequoted 'z', then we would have

    needed to use '[z] i' (or, if desired, we could have included 'z' in

    the basis instead of i); and if the expression had contained a null

    quotation, we would have had to use []. In this way, we can decompose

    any concatenative combination of "z", and hence any combinator

    whatsoever, into a flat expression in terms of {[], [z], unit, cat,

    i}.

    Now, we can do better than that. You really want a basis in terms of

    just two combinators (not five). So let's think about what would have

    to be true about such a basis:

    1. One of the two combinators must be able to execute on an empty

    stack; therefore it must do nothing but push a sequence of constant

    quotations onto the stack (This will necessarily be an improper

    combinator).

    2. The other combinator must be a total dequoter, such as 'i' or 'k'

    (otherwise, roughly speaking, it's impossible to get down to an empty

    stack again once anything has been pushed onto it).

    It might be possible to relax the first requirement if our system has

    a "bottomless stack", i.e., if we can assume infinitely many stack

    items are always available if needed, so that "[] dip" is considered

    equivalent to the empty program (analagous to the beta-eta-theory of

    classical combinatory logic, as opposed to the beta-theory). In any

    case, this won't be necessary, because it turns out there is a

    solution satisfying both requirements.

    Also, intuitively, the empty quotation [] must be embedded somehow in

    the first combinator. My first attempts at a two-combinator flat

    basis were {[] [z], i}, {[z] [], i}, {[] [cake] [k], i}, {[cake] [k]

    [], i}, and so forth, before realizing that these are all doomed

    because it is impossible to construct "cat" from them. But I'll skip

    over my failed attempts and cut straight to one that works. To do

    this, first define a new combinator "q":

    [B] [A] q == [[B]] [A B]

    This combinator, along with k, forms a complete basis (in the

    ordinary, non-flat sense). This is interesting in itself, since "q"

    is a bit simpler than "cake" ({cake, k} formerly being the simplest

    known basis of two proper combinators). But, as you've mentioned,

    Billy, it's not exactly clear how to count the size of a combinator.

    In my search program, I've counted it as the total number of atoms

    plus the number of quotations (so "q" would be size 6, 3 atoms plus 3

    quotations, while "cake" would be size 8, 4 atoms plus 4 quotations);

    but other schemes may be equally valid.

    Anyhow, here are the essential constructions from {q,k}:

    zap  == [] k

    i    == [] q k

    unit == [] q zap

    swat == q unit k     (where swat == X\ Y\ [X Y] == swap cat)

    dip  == unit [unit] swat i swat i

    dup  == [] q unit swat i

    I'll give the verification of "dip", the most interesting of these:

    [Y] [X] unit [unit] swat i swat i

    == [Y] [[X]] [unit] swat i swat i

    == [Y] [unit [X]] i swat i

    == [Y] unit [X] swat i

    == [[Y]] [X] swat i

    == [X [Y]] i

    == X [Y]

    It's worth noting that

      swat i == X\ Y\ X Y == dip i

    This combinator simply executes the top two programs on the stack. It

    may be constructed simply as "q k". Using this makes the above

    constructions of "dip" and "dup" much more efficient (In fact, a

    computer search shows that they are then minimal, in terms of their

    size as combinations of the original base combinators "q" and "k").

    Also, notice that the constructions of unit and swat (as well as zap,

    i, and dup) are flat in terms of [], q, and k. This will be useful to

    us in a moment. But I want to emphasize that I'm not claiming that

    {q, k} is a complete flat basis, because it certainly isn't. However,

    {q, k} is complete in the ordinary sense, and will be useful in

    building a flat basis:

    All right, so for a two-combinator basis, define:

    o == [] [q] [k]

    Then {o,i} is a complete flat basis. To prove this, we just need to

    show how to construct each combinator in {[], [q], [k], swat, unit},

    because this set, along with "i", clearly forms a complete flat

    basis, applying with minor adjustment the simple algorithm

    illustrated above for {[], [z], cat, unit, i}, noticing that "swat"

    will do just as well as "cat".

    So here we go. First, as an auxiliary step, we find that

    oi == q

    and

    ooooqiiiiii == [][k]

    (We might as well dispense with unnecessary spaces). Here's the

    verification:

    oi

    == [][q][k]i

    == [][q]k

    == q

    ooooqiiiiii

    == ooo[][q][k]qiiiiii

    == ooo[][[q]][kq]iiiiii

    == ooo[][[q]]kqiiiii

    == ooo[q]qiiiii

    == oo[][q][k][q]qiiiii

    == oo[][q][[k]][qk]iiiii

    == oo[][q][[k]]qkiiii

    == oo[][[q]][[k]q]kiiii

    == oo[][k]qiiii

    == oo[[]][k[]]iiii

    == oo[[]]k[]iiii

    == oo[[]]kiii

    == o[][q][k][[]]kiii

    == o[][q][]iii

    == o[][q]ii

    == o[]qi

    == [][q][k][]qi

    == [][q][[k]][k]i

    == [][q][[k]]k

    == [][k]

    From this we can get zap:

    zap == [][k] i

    The verification:

    [A][][k]i

    == [A][]k

    ==

    Now we can construct []:

    [] == [][k] zap

    This was one of the five we wanted. So, one down, four to go.

    Actually, we're done with most of the hard work. Next construct [k]:

    [k] == [][k] [] q i

    The verification:

    [][k][]qi

    == [][[k]][k]i

    == [][[k]]k

    == [k]

    Now take advantage of our original flat constructions of "unit"

    and "swat":

    unit == [] q zap

    swat == q unit k

    Now it remains only to construct [q]. (Note we already

    constructed "q" at the very beginning, but in a flat system, this is

    not enough.):

    [q] == o zap unit k

    The verification:

    o zap unit k

    == [][q][k] zap unit k

    == [] [q] unit k

    == [] [[q]] k

    == [q]

    So there we have it! We can write all this explicitly as

    []   == oooooiiiiiiioooooiiiiiiii

    [k]  == oooooiiiiiiioooooiiiiiiioooooiiiiiiiioii

    unit == oooooiiiiiiioooooiiiiiiiioioooooiiiiiiii

    swat ==

    oioooooiiiiiiioooooiiiiiiiioioooooiiiiiiiioooooiiiiiiioooooiiiiiiioooo

    oiiiiiiiioiii

    [q] ==

    ooooooiiiiiiiioooooiiiiiiioooooiiiiiiiioioooooiiiiiiiioooooiiiiiiioooo

    oiiiiiiioooooiiiiiiiioiii

    Of course, these constructions could probably be improved; my poor

    little Joy searcher (among other restrictions) only works on a basis

    of proper combinators, which does not apply in this case. So I'm not

    able to determine what the minimal constructions might be. Also, it

    is certainly possible that a more clever choice of basis could lead

    to smaller constructions.

    - Brent

## William Tanksley, Jr — 2007-02-06 19:19:27

    iepos <bkerby@...> wrote:

     > Billy and all,

    > Sorry for taking so long to respond to this. When I first read your

    > email, the server hosting Chris Okasaki's paper was apparently down.

    > And then for a couple weeks I forgot to come back and try it again. I

    > must say -- What he's accomplished is pretty cool.

     I agree -- and it was both instructive and reasonably fun to read.

     > I want to respond to your second question first; hopefully this will

    > in turn shed some light on the relationship between flat

    > concatenative systems and Okasaki's and Barker's work.

     Indeed it did! I especially appreciate you including your reasoning.

    Not only do I know how to construct the language I wanted, I also

    understand a bit more about how to think about that type of problem.

    Thank you!

    I'm also amused by your choice of 'o' and 'i' as combinators,

    considering that I mentioned that I was going to use 0 and 1 bits to

    represent them. Way back in my school career I took a typing class in

    which we were taught that upper case 'i' and 'o' could be typed

    instead of 1 and 0. (My community college was always a bit behind the

    technology curve; I'm not actually that old. Yes, my Fortran class

    taught me how to use punchcards, even though I've never set hands on a

    punchcard reader and never will use one.)

    The rest snipped for now... I'm going to try some constructions based

    on your and Fokker's work (not his combinator, just the way in which

    he derived it) to assure myself that I understand this.

    Thank you!

     > - Brent

     -Billy

## sa@dfa.com — 2007-02-06 19:54:22

    concatenative@yahoogroups.com wrote on 02/06/2007 02:19:27 PM:

     > I'm also amused by your choice of 'o' and 'i' as combinators,

    > considering that I mentioned that I was going to use 0 and 1 bits to

    > represent them.

     i thought it might be subliminal tribute to o[kasak]i.

## William Tanksley, Jr — 2007-02-08 00:01:18

    My apologies to the many people (I hope) reading this list and hoping

    for something useful. This stuff is a LONG way from usefulness. I hope

    that it will sharpen our understanding of what it means to be

    concatenative; I hope that after I understand this I'll be better

    equipped to explain the potential benefits.

    For now, just treat this as a puzzle: to be solved if it entertains,

    and skipped otherwise.

    iepos <bkerby@...> wrote:

     > Also, it

    > is certainly possible that a more clever choice of basis could lead

    > to smaller constructions.

     I chose a different basis which results in shorter constructions for

    the primitives we're producing. I think it's universally shorter; my

    reason for suspecting that is that your 'o' and 'i' operations have

    very asymmetric stack effects, so in general you have to execute a LOT

    of 'i's for every 'o'. I also personally found it to be much simpler

    to derive results for.

    Let

       0 = [] [q] [k]

       1 = k

    In this experiment, I didn't change the sequence of the 'o'

    combinator. One interesting (to me) implication is that 'k' is very

    exposed -- it's the last operation in both combinators. The other

    simple choice would be to define 0 as [] [k] [q]; doing that seems to

    result in slightly more complex forms for some primitives, but might

    make others much simpler. (I need to work that out in full.) The other

    permutations should be interesting as well, but now we're talking

    computer work, not human work.

    I originally chose 'k' so that the VM only needs to define 2

    operations, q and k (rather than having to define q, k, and i). I also

    suspect that it'll reduce faster, since there's less asymmetry between

    '0' producing stack items and '1' consuming them.

    Construct 'k':

    1 =

       k

    Construct 'zap':

    01 =

      [] [q] [k] k =

      [] k =

      zap

    (A simple 'zap' is very useful. It allows me to easily get at the

    functions contained in '0'. It also promises a nice peephole

    optimizer, since I have meanings for both "1" and "01"!)

    Construct 'q':

    0011 =

      0 01 1 =

      [] [q] [k] zap k =

      [] [q] k =

      q

    Construct '[]':

    00101 =

       0 01 01 =

       0 zap zap =

      [] [q] [k] zap zap =

      []

    Construct 'i':

    00101 0011 1 =

       [] q k =

       i

    Construct 'unit':

    00101 0011 01 =

       [] q zap =

       unit

    Construct 'nip':

    00101001101 1 =

      unit k =

      nip

    Construct 'swat':

    0011 001010011011 =

      q nip

     > []   == oooooiiiiiiioooooiiiiiiii

     [] = 00101

     > [k]  == oooooiiiiiiioooooiiiiiiioooooiiiiiiiioii

     [k] = 0 nip nip ==

    0 001010011011 001010011011

    (That's 26 bits for the k system, versus 41 when using 'i'. This is

    the closest thing to a tie.)

     > unit == oooooiiiiiiioooooiiiiiiiioioooooiiiiiiii

     unit == 00101001101

     > swat ==

    > oioooooiiiiiiioooooiiiiiiiioioooooiiiiiiiioooooiiiiiiioooooiiiiiiioooo

    > oiiiiiiiioiii

     swat == 0011001010011011

     > [q] ==

    > ooooooiiiiiiiioooooiiiiiiioooooiiiiiiiioioooooiiiiiiiioooooiiiiiiioooo

    > oiiiiiiioooooiiiiiiiioiii

     [q] = 0 zap nip ==

    0 01 001010011011

    Seems like I had a good intuition. Balance them combinators!

    I still need to explore the effect of using cake instead of q. I also

    need to (just as an exercise) express 'dip' and 'swap' in this system.

    So far I haven't (I've tried...).

     > - Brent

     -Billy

## iepos — 2007-02-08 03:34:57

    > I chose a different basis which results in shorter constructions for

    > the primitives we're producing.

     Wow! That's much better. Nice work.

     > I think it's universally shorter;

     Well, what exactly do you mean by that? There's certainly one

    combinator which is shorter in my {o,i}, namely "i". But there

    probably aren't too many more :-) Perhaps only finitely many. That

    would be an interesting question ...

     > I still need to explore the effect of using cake instead of q.

     Well, I can show you that {[] [cake] [k], k} is incomplete (and the

    choice of total dequoter "k" is irrelevant to the following argument,

    as is the order of the 3 quotations in 0). It is impossible to

    construct cat. Why? Well, notice that in the right side of the

    rewrite rule for "cat", there is a quotation containing two non-

    quoted terms:

    [B] [A] cat == [B A]

    But if we start with the stack "[B] [A]" and execute only a sequence

    of 0's and 1's (i.e., [] [cake] [k], or k), at each step the property

    will be preserved that each quotation contains at most one non-quoted

    term. This is because "cake" and "k" both preserve this property, as

    we can see from their rewrite rules:

    [B] [A] cake == [[B] A] [A [B]]

    [B] [A] k    == A

    Assuming "A" and "B" each contain at most one non-quoted term (and

    that, if they contain quotations or subquotations, these also contain

    at most non-quoted term each), the same will hold for the right-hand-

    side of both rewrite rules. So it is impossible to construct "cat".

    Now, to be clear, I'm not claiming that "cat" is inconstructible in

    every basis expressed in terms of "cake" and "k". For example, let

    0 = [] [cake] [k k]

    1 = k

    Then {0,1} is a complete flat basis (albeit a much uglier one than

    the one you've just given). Construct

    zapk: 01  (i.e., zapk == zap k == x\ y\ z\ y )

    == [] [cake] [k k] k

    == [] k k

    == zap k

    cake: 001

    == 0 01

    == 0 zap k

    == [] [cake] [k k] zap k

    == [] [cake] k

    == cake

    zap: 000 cake zapk k zapk

    == 00 [] [cake] [k k] cake zap k k zap k

    == 00 [] [[cake] k k] [k k [cake]] zap k k zap k

    == 00 [] [[cake] k k] k k zap k

    == 00 [cake] k k k zap k

    == 0 [] [cake] [k k] [cake] k k k zap k

    == 0 [] [cake] cake k k zap k

    == 0 [[] cake] k k zap k

    == [] [cake] [k k] [[] cake] k k zap k

    == [] [cake] [] cake k zap k

    == [] [[cake]] [[cake]] k zap k

    == [] [cake] zap k

    == [] k

    == zap

    []: 0 zap zap

    == [] [cake] [k k] zap zap

    == [] [cake] zap

    == []

    unit: [] cake zap

    [A] [] cake zap

    == [[A]] [[A]] zap

    == [[A]]

    nip: unit k (as in your construction)

    [cake]: 0 zap nip

    == [] [cake] [k k] zap nip

    == [] [cake] nip

    == [cake]

    cons: cake zap

    [B] [A] cake zap

    == [[B] A] [A [B]] zap

    == [[B] A]

    dip: cake k

    [B] [A] cake k

    == [[B] A] [A [B]] k

    == A [B]

    swap: unit dip

    [B] [A] unit dip

    == [B] [[A]] dip

    == [A] [B]

    i: [] swap k

    [A] [] swap k

    == [] [A] k

    == A

    take: cake nip

    [B] [A] cake nip

    == [[B] A] [A [B]] nip

    == [A [B]]

    swat: [] swap take take [] swap 0 nip nip cons cons

    [B] [A] [] swap take take [] swap 0 nip nip cons cons

    == [B] [] [A] take take [] swap 0 nip nip cons cons

    == [B] [A []] take [] swap 0 nip nip cons cons

    == [A [] [B]] [] swap 0 nip nip cons cons

    == [] [A [] [B]] 0 nip nip cons cons

    == [] [A [] [B]] [] [cake] [k k] nip nip cons cons

    == [] [A [] [B]] [] [k k] nip cons cons

    == [] [A [] [B]] [k k] cons cons

    == [] [[A [] [B]] k k] cons

    == [[] [A [] [B]] k k]

    == [A [] [B] k]

    == [A B]

    [k]: 0 nip cons [] swap cons

    == [] [cake] [k k] nip cons [] swap cons

    == [] [k k] cons [] swap cons

    == [[] k k] [] swap cons

    == [] [[] k k] cons

    == [[] [] k k]

    == [k]

    We've constructed [], [cake], [k], "swat", "unit", and "i", so that

    implies completeness. (But note that we had to assume transparent

    quotation in the last two constructions). The reason the above

    argument does not apply here is that [k k], in the basis combinator

    0, is a quotation containing more than one non-quoted term; so the

    initial assumption of the argument is not satisfied.

     > I also need to (just as an exercise) express 'dip' and 'swap' in

     this system.

    If you still want the exercise, close this message now. I also wanted

    the exercise, so I'm going to spoil it below :-)

    (lines intentionally left blank)

    (lines intentionally left blank)

    (lines intentionally left blank)

    (lines intentionally left blank)

    So, the (non-flat) construction for dip is

    dip == unit [unit] swat i swat i

    Putting things in terms of {q,k} (recalling that "swat i" == "q k")

    and flattening, we get:

    dip == [] q zap [[] q zap] q k q k

    == [] q zap [[] q [] k] q k q k

    == [] q zap [k] [[] q []] swat q k q k

    == [] q zap [k] [[]] [[] q] swat swat q k q k

    == [] q zap [k] [[]] [q] [[]] swat swat swat q k q k

    == [] q zap [k] [] unit [q] [] unit swat swat swat q k q k

    == 00101 0011 01 0001010011011001010011011 00101 00101001101

    001001010011011 00101 00101001101 0011001010011011 0011001010011011

    0011001010011011 0011 1 0011 1

    ==

    0010100110100010100110110010100110110010100101001101001001010011011001

    0100101001101001100101001101100110010100110110011001010011011001110011

    1 (141 bits)

    Then, the easiest way to get swap is via the construction

    swap == unit dip

    Of course, if you could construct swap first some other way, then you

    could use the construction

    dip == swap unit cat i

        == swap unit swap swat i

        == swap unit swap q k

    to get dip; but I doubt that this is helpful, because "swap" is

    probably more complicated to construct than "dip". At least, in the

    non-flat case, the minimal construction of "swap" in terms of {q,k},

    according to a computer search (at least, according to my memory -- I

    seem to have accidentally overwritten the log file, and this one took

    quite a while to run), is

    [] q [] k [] q [] k [[] q [] k] q k q k

    which is just the minimal construction of "unit" concatenated with

    the minimal construction of "dip", so that "unit dip" really is the

    minimal way to construct swap in this situation. Of course, it's

    certainly possible that this could change when we switch to the flat

    basis {0,1}.

    By the way, I said "the minimal", but there were actually some other

    solutions of equal size; I didn't take the time to look at them all,

    but they mostly seemed to be trivial varients based on the equivalence

    [A] k == [] k A

    (which, in fact, could be useful to help flatten out expressions over

    {q,k} without introducing as many "swat"'s).

     > > - Brent

    >

    > -Billy

    >

     - Brent

## stevan apter — 2007-02-08 23:01:42

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

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

    >

    > Construct 'i':

    > 00101 0011 1 =

    >    [] q k =

    >    i

    >

    i think this should be

    00101 0011 1 1 =

        [] q k k

    i've posted an interpreter for 01 at:

        http://www.nsl.com/k/01.k

## William Tanksley, Jr — 2007-02-09 04:54:14

    stevan apter <sa@...> wrote:

     > > Construct 'i':

    > > 00101 0011 1 =

    > >    [] q k =

    > >    i

    > i think this should be

    > 00101 0011 1 1 =

    >     [] q k k

     [A] [] q k k =

    [[A]] [A] k k =

    A k

    Too many k's.

    What might be messing things up is how you treat the [A B] term in the

    result of 'q'. In this quotation, [A] is [], which means that A must

    be nothing. It's kind of (severely) wierd, but that's how it works.

    Does your interpreter act that way?

     > i've posted an interpreter for 01 at:

    >     http://www.nsl.com/k/01.k

     You are amazing. :-)

    -Billy

## iepos — 2007-02-09 08:28:15

    Billy & all,

    I hacked at my old Joy searcher for a while and was at last able to

    persuade it to deal with improper combinators; so I've been able to

    determine some minimal constructions for the basis we're looking at,

    i.e., {o,k} where

      o == [] [q] [k]

    and

      [B] [A] q == [[B]] [A B]

      [B] [A] k == A

    So, it turns out most of the constructions you gave are minimal. An

    improvement was possible only for [q] (from 15 to 8 bits) and [k]

    (from 25 to 18 bits). Here are all minimal constructions for q, [],

    i, unit, nip, swat, [q], and [k]:

    q   == ookk         ( == o zap k, same as your construction)

    []  == ookok        ( == o zap zap, same as your construction)

    i   == ookokookkk   ( == [] q k, same as your construction)

        == ookoookkkk

    unit== ookokookkok  ( == [] q zap, same as your construction)

        == ookoookkkok

    nip == ookokookkokk ( == unit k, same as your construction)

        == ookoookkkokk

    swat== ookkookokookkokk (== q nip, same as your construction)

        == ookkookoookkkokk

    [q] == oookkokk     ( == o q zap k)

    [k] == oookokookkookkokkk  ( == o [] q q zap k k)

        == oookoookkkookkokkk

    The varients are all due to the equivalence

      okookk == oookkk == zap q

    The improvements on [q] and [k] are actually interesting. The

    original construction for [q] was

    [q] == o zap nip

        == o zap unit k

        == o zap [] q zap k

    Notice that in the construction

      unit == [] q zap

    the empty program is only used as a junk element; any other element

    works just as well:

    [A] [junk] q zap

    == [[A]] [junk A] zap

    == [[A]]

    So, in the construction for [q], we might as well leave [k] alone

    and use it as our junk element, rather than zapping it and pushing

    []. Therefore, we can delete "zap []" from the construction. Compare:

       o zap [] q zap k

    == [] [q] [k] zap [] q zap k

    == [] [q] [] q zap k

    == [] [[q]] [q] zap k

    == [] [[q]] k

    == [q]

       o q zap k

    == [] [q] [k] q zap k

    == [] [[q]] [k q] zap k

    == [] [[q]] k

    == [q]

    Now let's look at [k]. The original construction was

    [k] == o nip nip

        == o unit k unit k

    Notice that "unit unit k k" also works as an implementation of "nip

    nip":

    [C] [B] [A] unit unit k k

    == [C] [B] [[A]] unit k k

    == [C] [B] [[[A]]] k k

    == [C] [[A]] k

    == [A]

    So we have

    [k] == o unit unit k k

        == o [] q zap [] q zap k

    And once again we can delete the unneeded "zap []" (for the same

    reason as with [q]) to get

    [k] == o [] q q zap k

    which is the minimal construction.

    I've tried searching for minimal constructions of "dip" and "swap"

    but without success; I can say that "dip" has size at least 33

    and "swap" has size at least 35. But I would guess that the minimal

    constructions are much larger than this, so it's probably useless to

    continue searching in a brute-force manner (although technically

    it's not quite brute-force; I did implement a sort of backtracking

    algorithm for flat constructions, which helps speed things up a bit).

    I also did some experimenting with different bases. Remarkably, all

    five other bases obtained from {o,k} by changing the order of the

    three quotations in "o" are flat complete. Here are the

    constructions (for the sake of conciseness, I'll just choose one

    representative when there are multiple minimal constructions):

    o := [] [k] [q]

    []  == oookkokkk

    [q] == ookokokkokkkk

    [k] == ookkokokk

    i   == okk

    unit== okoookkokkkk

    swat== ookokkkokookkokokkk

    o := [q] [] [k]

    []  == oookkoookkokkk

    [q] == ooookkookkokkk

    [k] == ooookkokkookkk

    i   == oookkokkk

    unit== ookoookkookkkk

    swat== ookkoookokookkkk

    o := [k] [] [q]

    []  == ooookokookkkkkokk

    [q] == ooookokkkkokk

    [k] == ooookokookkkkkk

        == ooookokkokkokkk

    i   == oookkokkk

    unit== oookokkkk

    swat== oookokkokokkkk

    o := [q] [k] []

    []  == ooookkookkkokkk

    [q] == ok

    [k] == ooookkkoookkkkk

    i   == oookkkoookkkokkkk

    unit== oookkoookokkokkookkkkk

    swat== okokkookkookoookkkkkk

    o := [k] [q] []

    []  == ooookkkookkokkk

    [q] == oookkokk

    [k] == ok

    i   == oookkkoookkookkkkkk

    unit== okooookkkookkkk

    swat== ookkoookkkokk

    Also, it turns out that my original base {o,i} isn't as bad as it

    first appeared; here are the minimal constructions over it:

    []  == oooiiioooiiiiii

    [q] == ooioooiioiioiiii

    [k] == oooiioiii

    unit== ooiioooiiiii

    swat== oiooiioooiioiioiiii

    And the basis {[k] [q] [],i} also turns out to be complete and has

    fairly simple constructions:

    o := [k] [q] []

    []  == ooiiioiii

    [q] == ooioiiiiiiii

    [k] == ooiiii

    unit== oiiooiiioiiioiiii

    swat== oooiioiiioiiooiioiii

    The other four bases obtained from {o, i} by changing the order of

    the quotations in "o" appear to be incomplete, although I'm not

    certain except in the case {[q] [] [k], i}, which is definitely

    incomplete since "oi" is the empty program.

    A couple other interesting bases arise from a new combinator, call

    it "h", defined

    [B] [A] h == [[A B]] [B]

    which forms a complete (non-flat) basis with "k", as evidenced by

    the constructions

    i    == [] h k

    unit == [] h [] k

    swat == h h k

    dup  == [] h unit swat i

    Then {[] [h] [k], k} and {[] [k] [h], k} are complete flat bases:

    o := [] [h] [k]

    []   == ookok

    [h]  == ookookkookkk

    [k]  == ooookkkokoookkkokkk

    i    == oookkkk

    unit == oookkkok

    swat == ookkookkk

    o := [] [k] [h]

    []   == ookkokokkk

    [h]  == ookookokkkokookokkkkk

    [k]  == ookkokkokk

    i    == okk

    unit == okookokkk

    swat == ookookokkkkkookokkkokk

    In the end, from what I can see, none of these alternative bases

    offer significant improvement over your {o,k}, which is one of the

    best in terms of yielding small constructions of the combinators

    we're looking at. It looks like your intuition served you well

    indeed!

    - Brent

## stevan apter — 2007-02-09 12:54:42

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Thursday, February 08, 2007 11:54 PM

    Subject: Re: [stack] Re: Concatenative macros?

    > stevan apter <sa@...> wrote:

    > > > Construct 'i':

    > > > 00101 0011 1 =

    > > >    [] q k =

    > > >    i

    >

    > > i think this should be

    > > 00101 0011 1 1 =

    > >     [] q k k

    >

    > [A] [] q k k =

    > [[A]] [A] k k =

    > A k

    >

    > Too many k's.

    >

    > What might be messing things up is how you treat the [A B] term in the

    > result of 'q'. In this quotation, [A] is [], which means that A must

    > be nothing. It's kind of (severely) wierd, but that's how it works.

    > Does your interpreter act that way?

    it does now.  that wasn't at all clear (to me) from the description of 'q'.

        [B] [A] q == [[B]] [A B]

    shouldn't that be

        [B] [A] q == [[B]] [A B] if A is not []

                     [[B]] B if A is []

    ?

    did i read right past that in brent's original explanation?

      O["";"[1][0]q"]

    [[1]][[0][1]]

      O["";"[1][]q"]

    [[1]][1]

      O["";"[][0]q"]

    [[]][[0][]]

    do i have this right, or should B = [] produce analogous

    behavior?

    in any case, kudos to both you and brent.  this is fascinating.

    >

    > > i've posted an interpreter for 01 at:

    > >     http://www.nsl.com/k/01.k

    >

    > You are amazing. :-)

    >

    > -Billy

    >

## William Tanksley, Jr — 2007-02-09 15:25:56

    stevan apter <sa@...> wrote:

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

    > > What might be messing things up is how you treat the [A B] term in the

    > > result of 'q'. In this quotation, [A] is [], which means that A must

    > > be nothing. It's kind of (severely) wierd, but that's how it works.

    > > Does your interpreter act that way?

    > it does now.  that wasn't at all clear (to me) from the description of 'q'.

    >     [B] [A] q == [[B]] [A B]

    > shouldn't that be

    >     [B] [A] q == [[B]] [A B] if A is not []

    >                  [[B]] B if A is []

    > ?

     This is one of the things that confuses me about this notation -- but

    it's something you have to learn. The reason it's confusing to us is

    that it's a purely functional notation, and we're used to thinking

    procedurally. You're especially in danger of that, since you're using

    a concrete implementation in order to learn about it.

    In this case, we think procedurally when we use the word "dequote" to

    mean "execute now". What it actually means is "insert the semantics

    that are quoted inside this list directly into this context."

    I'm taking a long time to get to the point. Let me take a break to

    give an example.

     >     [B] [A] q == [[B]] [A B] if A is not []

    >                  [[B]] B if A is []

     Well, first, the second part is a typo -- you probably meant to type

    "[[B]] [B]". Second, though, and this is the important part, in this

    notation the term "A" doesn't mean "the top item on the stack". It

    means "the semantics which are quoted inside the top item on the

    stack."

     > did i read right past that in brent's original explanation?

    >   O["";"[1][0]q"]

    > [[1]][[0][1]]

    >   O["";"[1][]q"]

    > [[1]][1]

    >   O["";"[][0]q"]

    > [[]][[0][]]

     I can't read this notation; sorry.

     > do i have this right, or should B = [] produce analogous

    > behavior?

     Precisely so -- "B" means "the semantics quoted inside the second item

    on the stack". If [B] == [], that means there are no semantics quoted

    inside the second item on the stack.

    So these things are not a special case; they're normal behavior.

     > in any case, kudos to both you and brent.  this is fascinating.

     Thank you -- and a HUGE thank you to Brent, who's at last made this

    all make sense to me. This is exciting to me, since I've been puzzled

    by it for so long.

    I've decided (tentatively) that my next goal is to build a basis in

    which swap is easier to express. I don't think that'll be the last

    basis I construct :-), but I'm just not happy with the extreme

    imbalance between how easy it is to nip and how hard it is to swap.

    I know there will always be tradeoffs; but I want to learn how to make

    them wisely. I have a very strong sense that some of these bases are

    FAR easier to work with than others, so I'm confident that there's

    much room for improvement.

     > > > i've posted an interpreter for 01 at:

    > > >     http://www.nsl.com/k/01.k

     I wrote a Python interpreter, although I didn't even try to run it, so

    it's probably severely broken. (My purpose was to explain this to a

    fellow programmer who doesn't know anything about concatenativity or

    flatness or mathematics; I succeeded, since he wrote back with a bunch

    of derivations.) Does anyone want to see it? It's not that many lines

    long.

    -Billy

## sa@dfa.com — 2007-02-09 16:37:57

    concatenative@yahoogroups.com wrote on 02/09/2007 10:25:56 AM:

     > stevan apter <sa@...> wrote:

     [:]

     >

    > > [B] [A] q == [[B]] [A B]

    >

    > > shouldn't that be

    > > [B] [A] q == [[B]] [A B] if A is not []

    > > [[B]] B if A is []

    > > ?

    >

    > This is one of the things that confuses me about this notation -- but

    > it's something you have to learn. The reason it's confusing to us is

    > that it's a purely functional notation, and we're used to thinking

    > procedurally. You're especially in danger of that, since you're using

    > a concrete implementation in order to learn about it.

    >

    > In this case, we think procedurally when we use the word "dequote" to

    > mean "execute now". What it actually means is "insert the semantics

    > that are quoted inside this list directly into this context."

    >

    > I'm taking a long time to get to the point. Let me take a break to

    > give an example.

     [:]

     >

    > Precisely so -- "B" means "the semantics quoted inside the second item

    > on the stack". If [B] == [], that means there are no semantics quoted

    > inside the second item on the stack.

    >

    > So these things are not a special case; they're normal behavior.

     my confusion was purely notational:  i didn't realize that "A B"

    meant (what i would write as) "A^B", although the left-hand-side of

    the rule should have clued me in.

    i notice that robbert also favors a rewrite-rule style for his

    exposition of enchilada.  and he too is always correcting me on

    this matter!

     >

    > > in any case, kudos to both you and brent. this is fascinating.

    >

    > Thank you -- and a HUGE thank you to Brent, who's at last made this

    > all make sense to me. This is exciting to me, since I've been puzzled

    > by it for so long.

     yes, i find his contributions uniquely valuable, indispensable to

    understanding this terrain.  thank you brent.

     >

    > I've decided (tentatively) that my next goal is to build a basis in

    > which swap is easier to express. I don't think that'll be the last

    > basis I construct :-), but I'm just not happy with the extreme

    > imbalance between how easy it is to nip and how hard it is to swap.

    >

    > I know there will always be tradeoffs; but I want to learn how to make

    > them wisely. I have a very strong sense that some of these bases are

    > FAR easier to work with than others, so I'm confident that there's

    > much room for improvement.

     onward.  i'll be with the baggage, in the rear.

     >

    > > > > i've posted an interpreter for 01 at:

    > > > > http://www.nsl.com/k/01.k

    >

    > I wrote a Python interpreter, although I didn't even try to run it, so

    > it's probably severely broken. (My purpose was to explain this to a

    > fellow programmer who doesn't know anything about concatenativity or

    > flatness or mathematics; I succeeded, since he wrote back with a bunch

    > of derivations.) Does anyone want to see it? It's not that many lines

    > long.

     yes, by all means.

    as i mentioned to you privately a few days ago, i wrote the interpreter

    as a preliminary step to experimenting with a genetic algorithm (to find

    programs.)  as you pointed out at the beginning of this discussion,

    programs constructed in a flat, two-element language seem tailor-made

    for recombination operations.

    01.k contains inner and outer interpreters.  the inner interpreter

    evaluates and produces binary sequences.  the outer interpreter takes

    strings using a vocabulary (e.g. zap, i, unit, &c.), deconstructs them

    into binary sequences, invokes the inner interpreter, then constructs

    strings in the vocabulary from the result.

     >

    > -Billy

    >

## William Tanksley, Jr — 2007-02-09 18:47:13

    iepos <bkerby@...> wrote:

     > > I chose a different basis which results in shorter constructions for

    > > the primitives we're producing.

    > Wow! That's much better. Nice work.

     Thanks, but obviously it builds on your work -- you actually know what

    you're doing, and you get all the credit for making it make sense.

    I suspect that this language is more easily explained than any of the

    unlambda-ish competitors. In theory, it might be nice that each

    element of the language stands alone, and any substring of any program

    can be understood in isolation, and it means exactly the same thing in

    context, no matter what the context is.

    (In practice, a real language would have to define a data convention,

    so there would be a difference between data and code.)

    I sent a Python implementation (of your first version of the language)

    to a friend who knows Forth but no math (a pure electronic engineer

    type), and he responded with a series of derivations (although he

    wasn't really interested in the language and in fact some of his

    derivations were incorrect, he definitely proved that he understood

    it).

     > > I think it's universally shorter;

    > Well, what exactly do you mean by that? There's certainly one

    > combinator which is shorter in my {o,i}, namely "i". But there

    > probably aren't too many more :-) Perhaps only finitely many. That

    > would be an interesting question ...

     That's what I meant, yes. I don't know a precise way of asking the

    question; I've seen that type of assertion made in math, but I don't

    remember how it was expressed. It's also possible that in that

    particular case there's no way to express what I meant (but you know

    what I mean).

    Anyhow, I found my {01} basis to be far easier to derive things for

    than your {oi} basis. I suspect there's a reason for that. I also

    found my basis to be very hard to express stack reorderings in, and I

    suspect I know a reason for that. I want to see how *good* of a basis

    I can possibly construct.

     > > I still need to explore the effect of using cake instead of q.

    > Well, I can show you that {[] [cake] [k], k} is incomplete (and the

    > choice of total dequoter "k" is irrelevant to the following argument,

     Very nice. You just saved me a lot of time. And, to boot, gave me a

    good example of reasoning. Well,  more accurately, you caused me to

    spent my time looking at good reasoning instead of trying to create my

    own bad reasoning.

     > > I also need to (just as an exercise) express 'dip' and 'swap' in

    > > this system.

    > If you still want the exercise, close this message now. I also wanted

    > the exercise, so I'm going to spoil it below :-)

     I tried, I failed. Your path to a solution is more prudent than mine.

     > to get dip; but I doubt that this is helpful, because "swap" is

    > probably more complicated to construct than "dip". At least, in the

     That was my conclusion as well.

    I'm still exploring basises (bases? basi?). I know there's no

    perfection, only tradeoffs, but I also suspect that some are much

    worse than others, and I have no theoretical basis for believing that

    I've found the "best".

     > - Brent

     -Billy

## William Tanksley, Jr — 2007-02-09 19:10:00

    sa@... <sa@...> wrote:

     > concatenative@yahoogroups.com wrote on 02/09/2007 10:25:56 AM:

    > > I wrote a Python interpreter, although I didn't even try to run it, so

    > > it's probably severely broken. (My purpose was to explain this to a

    > yes, by all means.

     Included at the end of this post.

     > as i mentioned to you privately a few days ago, i wrote the interpreter

    > as a preliminary step to experimenting with a genetic algorithm (to find

    > programs.)  as you pointed out at the beginning of this discussion,

    > programs constructed in a flat, two-element language seem tailor-made

    > for recombination operations.

     Indeed.

    Although I'm also interested in genetic systems, my main interest is

    in understanding languages for use by humans. I'm not certain

    (although I can sometimes hope) that perfectly flat languages will

    ever be usable by humans (we and the people who write in Unlambda are

    NOT humans, sorry), but I'm certain that I'm increasing my

    understanding of languages :-).

     > 01.k contains inner and outer interpreters.  the inner interpreter

    > evaluates and produces binary sequences.  the outer interpreter takes

    > strings using a vocabulary (e.g. zap, i, unit, &c.), deconstructs them

    > into binary sequences, invokes the inner interpreter, then constructs

    > strings in the vocabulary from the result.

     Of course, the "outer interpreter" could also be implemented as a

    "compiler" and "decompiler". I think this is a useful result of

    flatness: any string always means the same thing, regardless of

    context. (Of course, this also means that decompilations are not

    unique.)

    -Billy

    -------- the "ok" 01 interpreter (untested):

    def q(stack):

      a = stack.pop()

      b = stack.pop()

      stack.push( [[b]] )

      stack.push( [a, b] )

      return stack

    def one(stack): # K combinator

      a = stack.pop()

      b = stack.pop() # throw away

      return Execute(a, stack)

    def zero(stack):

      stack.push( list() )

      stack.push( list(q) )

      stack.push( list(one) )

    # It's impossible to Execute anything that's not a list.

    def Execute(fn, stack):

     for elem in fn:

        if elem instanceof list: stack.push(elem)

        else elem(stack)

    # The heart of the system:

    bits = raw_input("Input a string of 0s and 1s: ")

    stack = []

    for bit in bits:

      if bit == '0': zero(stack)

      else: one(stack)

    print stack

## William Tanksley, Jr — 2007-02-09 19:12:38

    iepos <bkerby@...> wrote:

     > I hacked at my old Joy searcher for a while and was at last able to

    > persuade it to deal with improper combinators; so I've been able to

    > determine some minimal constructions for the basis we're looking at,

    > i.e., {o,k} where

     Okay; and then you posted it where? :-)

    Let me get my credit card.

    -Billy

## stevan apter — 2007-02-09 22:02:30

    i would be extremely interested in reading a description

    of the algorithm.

    (my dog ate my credit card)

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Friday, February 09, 2007 2:12 PM

    Subject: Re: [stack] Re: Flat concatenative basis (was: Concatenative macros?)

    > iepos <bkerby@...> wrote:

    > > I hacked at my old Joy searcher for a while and was at last able to

    > > persuade it to deal with improper combinators; so I've been able to

    > > determine some minimal constructions for the basis we're looking at,

    > > i.e., {o,k} where

    >

    > Okay; and then you posted it where? :-)

    >

    > Let me get my credit card.

    >

    > -Billy

    >

## Brent L Kerby — 2007-02-09 22:56:20

    > Okay; and then you posted it where? :-)

     Oh, yeah, I forgot to mention that. It's at http://www.tunes.org/~iepos/joys.zip (it's linked from the article "Theory of Concatenative Combinators"); I overwrote the old version with the new version. The C source code is included, although it's very unreadable (sorry about that). I meant to include an updated README, but it looks like I've misplaced the file. The basic difference is that if you want to search only for flat constructions, place an underscore ("_") on a line by itself anywhere in the "goal" file. And, to support the use of improper combinators in the basis, you may declare auxiliary combinators (which will not be included in the basis) at the beginning of the "goal" file and separate them from the others by putting a "." on a line by itself. The goal combinator is marked by an asterisk ("*") and may be placed anywhere in the file (whereas the older version always required the goal to be the first line); but it must occur after any combinators it references (so, if you're searching for "[q]", it should come after the definition of "q"); it's fine to always put it at the end.

    For example, to search for constructions of "swat" over the basis {o, k} where o == [] [q] [k], use this for the "goal" file:

    _

    2q [[1]][01]

    .

    2k 0

    0o [][q][k]

    2* [01]

    Oh, by the way, the searcher assumes opaque quotation because this was the easiest to implement; years ago I partially implemented transparent quotation (activated by uncommenting the line "#define LIVEQUOTES") but the code for it is broken, so I don't recommend using it.

    Enjoy!

     > -Billy

     - Brent

## Brent L Kerby — 2007-02-10 03:31:16

    > i would be extremely interested in reading a description

    > of the algorithm.

     It basically works by trying all programs of size 0 (There aren't too many of these :-) ), then all programs of size 1, and so forth, testing each program by executing it to see if it generates the desired effect. There's a limit (the constant "TOOLONG" in my implementation) as to how many steps it spends on any one program; this is necessary to prevent it from freezing when it encounters a non-terminating program (of which, by the way, in {o,k}, there are none of size 34 or less; I have yet to find the smallest one). Of course, in theory, this could cause the searcher to miss possible solutions, since in general there is no way to tell whether an apparently non-terminating program really is non-terminating (the Halting Problem, the canonical problem which a Turing machine cannot solve), or whether it might not eventually yield the desired construction after a very long time. My searcher makes an announcement the first time it first finds an apparently non-terminating program, so that you know that there could be omitted solutions. For practical purposes, we're probably not really interested in constructions that have extremely long run times anyway.

    In the case of flat constructions, I implemented a (partial) backtracking algorithm so that if a program generates an error (i.e., a stack underflow) at a certain point, then that whole branch of the search space will be skipped. So, for example, when we search for a construction of "i" over the basis {o,k}, at some point the program "koooo" will be tested which will generate a stack underflow in the very first instruction (since only 1 stack item is available and "k" needs 2), so that the subsequent programs "koook", "kooko", "kookk", ..., "kkkkk" will be entirely skipped.

    I say that it's only a partial implementation of backtracking because each program still gets tested from scratch. My implementation does not use recursion or dynamic memory allocation; instead, there is both a data stack and a code "stack" (the data stack grows up while the code stack grows down), each implemented as a simple array of fixed maximum size. I'm pretty sure this is not the best way to do it. Each quotation requires a memcpy() (of size equal to the length of the quotation) from the code stack to the data stack, while execution (i.e., dequoting) likewise requires a memcpy() from the data stack to the code stack. If I were doing it again, I would allocate quotations dynamically and reference them by pointers to eliminate the need for this deep copying, especially considering that fully implementing backtracking would otherwise require making a copy of the stack at each level of the recursion. So we should implement stacks/quotations using lists, or better yet, trees, which generally we will never modify, only newly create. Trees are preferable to lists, so that, for example, we can implement q == A\ B\ [[B]] [A B], in constant time; with lists, a copy, albeit a shallow copy, is needed to form the concatenation "A B", and this is potentially problematic, as I'll show below.

    There's no reason why "dup" (or "q") actually needs to duplicate anything more than a pointer. In a real implementation of the system, this would necessitate garbage collection, but in a searcher this is unnecessary, since individual programs do not run long enough to generate a significant amount of garbage (and since we want to be able to backtrack, even the "garbage" isn't garbage to us). In a recursive implementation of the searcher, everything new that is created should be freed on the way out of the recursion, so that special  garbage collection, i.e., reference counting, mark&sweep, etc., is unnecessary.

    Now, there are "busy beaver" programs which can generate an obscenely large amount of data in only a very small amount of code (the maximum amount generated grows so fast as a function of code length that it is incomputable; that means that in the end, it grows faster than any function you can describe, worse than exponential or even Ackermann functions); and of course, non-terminating programs could potentially generate an unbounded amount of data. For instance,

    [] [[dup cons] dip dup i] dup i

    is a non-terminating program that takes up stack space exponential to the amount of time you let it run. In general,

    [[P] dip dup i] dup i

    is an infinite loop that runs "P" over and over again unconditionally:

    [[P] dip dup i] dup i

    == [[P] dip dup i] [[P] dip dup i] i

    == [[P] dip dup i] [P] dip dup i

    == P [[P] dip dup i] dup i

    == P P P P P P ...

    So then

    [] [[dup cons] dip dup i] dup i

    == [] dup cons dup cons dup cons dup cons ...

    == [] [] cons dup cons dup cons dup cons ...

    == [[]] dup cons dup cons dup cons dup cons ...

    == [[]] [[]] cons dup cons dup cons dup cons ...

    == [[[]][]] dup cons dup cons dup cons ...

    == [[[]][]] [[[]][]] cons dup cons dup cons ...

    == [[[[]][]]][[]][]] dup cons dup cons ...

    == [[[[]][]]][[]][]] [[[[]][]]][[]][]] cons dup cons ...

    == [[[[[]][]]][[]][]][[[]][]]][[]][]] dup cons ...

    == ...

    My Joy searcher would likely crash if it encounters such a program. That's not a good thing. But an efficient Joy searcher would implement "dup" by copying references, not by a deep copy, so that then the amount of space a program uses is bounded linearly by the length of time it is allowed it to run, which makes space requirements trivial. Another example that is even worse than the one above is

    == [[]] [[dup cat] dip dup i] dup i

    == [[]] dup cat dup cat dup cat dup cat ...

    == [[]] [[]] cat dup cat dup cat dup cat ...

    == [[] []] dup cat dup cat dup cat ...

    == [[] []] [[] []] cat dup cat dup cat ...

    == [[] [] [] []] dup cat dup cat ...

    == [[] [] [] []] [[] [] [] []] cat dup cat ...

    == [[] [] [] [] [] [] [] []] dup cat ...

    == [[] [] [] [] [] [] [] []] [[] [] [] [] [] [] [] []] cat ...

    This one is worse because it will thwart a system that assumes that shallow copies are cheap; that's why I'd suggest using trees. Using balanced trees might be helpful, but it is probably unnecessary, since the maximum depth of any tree is no larger than the number of steps we allow the program to run (which should be fairly small), times a small constant (normally 1 or 2) which depends on the choice of basis.

    Okay, so thus far this has been more of a description of how I should have written the searcher, and not how I actually did :-) But I'll explain one thing that I think I did right that could be a bit subtle. Prior to testing each program, the stack is arranged with a number of quotations of distinct special objects which I'll call indeterminates. For example, if you're searching for "dip", the goal line will look like

    2* 0[1]

    and two indeterminates (referred to as "0" and "1", "0" the top one) will be pushed prior to each test. When one of these indeterminates is executed, it is stored (in dequoted form) on the "data stack" just like quotations. Thus, you may think of the "data stack" as more of a history than of a stack in the literal sense. In one sense, a dequoted indeterminate is a brick wall in the history, in that attempting to look past one will generate a stack underflow, regardless of whether there are quotations beyond it.

    Anyhow, back to optimization strategies ... Currently, the only condition which causes the searcher to backtrack is a stack underflow. But there are other conditions which should also trigger this:

    1. Whenever a program appears to be non-terminating.

    2. Whenever an indeterminate is executed and the history/"data stack" does not precisely match the first part of the goal combinator.

    3. Whenever last copy of an indeterminate that is still needed is destroyed. (This is potentially more expensive to check; perhaps the set of referenced indeterminates could be built into the data structure for quotations/stack).

    Another optimization would be to build an exhaustive table of small constructions and find out which ones are equivalent. Then from each equivalence class, choose one representative and prohibit all others in the construction (Backtrack if one occurs). For example, in {o,k} we found that

    okookk == oookkk == zap q

    Therefore, to speed things up, we should choose "okookk" and prohibit "oookkk", or vice versa. Under certain bases and sufficiently large table size, it is possible that in building the table we may encounter some (apparently) non-terminating programs; if this happens, we should prohibit them entirely.

    - Brent

## stevan apter — 2007-02-11 00:02:29

    thanks brent

    as usual, work that you consider throw-away contains more insights than can fit in a standard

    published article, much less the margins of one.

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

    From: "Brent L Kerby" <bkerby@...>

    To: <concatenative@yahoogroups.com>

    Sent: Friday, February 09, 2007 10:31 PM

    Subject: Re: Re: [stack] Re: Flat concatenative basis (was: Concatenative macros?)

    > i would be extremely interested in reading a description

    > of the algorithm.

    It basically works by trying all programs of size 0 (There aren't too many of these :-) ), then all programs of size 1, and so

    forth, testing each program by executing it to see if it generates the desired effect. There's a limit (the constant "TOOLONG" in my

    implementation) as to how many steps it spends on any one program; this is necessary to prevent it from freezing when it encounters

    a non-terminating program (of which, by the way, in {o,k}, there are none of size 34 or less; I have yet to find the smallest one).

    Of course, in theory, this could cause the searcher to miss possible solutions, since in general there is no way to tell whether an

    apparently non-terminating program really is non-terminating (the Halting Problem, the canonical problem which a Turing machine

    cannot solve), or whether it might not eventually yield the desired construction after a very long time. My searcher makes an

    announcement the first time it first finds an apparently non-terminating program, so that you know that there could be omitted

    solutions. For practical purposes, we're probably not really interested in constructions that have extremely long run times anyway.

    In the case of flat constructions, I implemented a (partial) backtracking algorithm so that if a program generates an error (i.e., a

    stack underflow) at a certain point, then that whole branch of the search space will be skipped. So, for example, when we search for

    a construction of "i" over the basis {o,k}, at some point the program "koooo" will be tested which will generate a stack underflow

    in the very first instruction (since only 1 stack item is available and "k" needs 2), so that the subsequent programs "koook",

    "kooko", "kookk", ..., "kkkkk" will be entirely skipped.

    I say that it's only a partial implementation of backtracking because each program still gets tested from scratch. My implementation

    does not use recursion or dynamic memory allocation; instead, there is both a data stack and a code "stack" (the data stack grows up

    while the code stack grows down), each implemented as a simple array of fixed maximum size. I'm pretty sure this is not the best way

    to do it. Each quotation requires a memcpy() (of size equal to the length of the quotation) from the code stack to the data stack,

    while execution (i.e., dequoting) likewise requires a memcpy() from the data stack to the code stack. If I were doing it again, I

    would allocate quotations dynamically and reference them by pointers to eliminate the need for this deep copying, especially

    considering that fully implementing backtracking would otherwise require making a copy of the stack at each level of the recursion.

    So we should implement stacks/quotations using lists, or better yet, trees, which generally we will never modify, only newly create.

    Trees are preferable to lists, so that, for example, we can implement q == A\ B\ [[B]] [A B], in constant time; with lists, a copy,

    albeit a shallow copy, is needed to form the concatenation "A B", and this is potentially problematic, as I'll show below.

    There's no reason why "dup" (or "q") actually needs to duplicate anything more than a pointer. In a real implementation of the

    system, this would necessitate garbage collection, but in a searcher this is unnecessary, since individual programs do not run long

    enough to generate a significant amount of garbage (and since we want to be able to backtrack, even the "garbage" isn't garbage to

    us). In a recursive implementation of the searcher, everything new that is created should be freed on the way out of the recursion,

    so that special  garbage collection, i.e., reference counting, mark&sweep, etc., is unnecessary.

    Now, there are "busy beaver" programs which can generate an obscenely large amount of data in only a very small amount of code (the

    maximum amount generated grows so fast as a function of code length that it is incomputable; that means that in the end, it grows

    faster than any function you can describe, worse than exponential or even Ackermann functions); and of course, non-terminating

    programs could potentially generate an unbounded amount of data. For instance,

    [] [[dup cons] dip dup i] dup i

    is a non-terminating program that takes up stack space exponential to the amount of time you let it run. In general,

    [[P] dip dup i] dup i

    is an infinite loop that runs "P" over and over again unconditionally:

    [[P] dip dup i] dup i

    == [[P] dip dup i] [[P] dip dup i] i

    == [[P] dip dup i] [P] dip dup i

    == P [[P] dip dup i] dup i

    == P P P P P P ...

    So then

    [] [[dup cons] dip dup i] dup i

    == [] dup cons dup cons dup cons dup cons ...

    == [] [] cons dup cons dup cons dup cons ...

    == [[]] dup cons dup cons dup cons dup cons ...

    == [[]] [[]] cons dup cons dup cons dup cons ...

    == [[[]][]] dup cons dup cons dup cons ...

    == [[[]][]] [[[]][]] cons dup cons dup cons ...

    == [[[[]][]]][[]][]] dup cons dup cons ...

    == [[[[]][]]][[]][]] [[[[]][]]][[]][]] cons dup cons ...

    == [[[[[]][]]][[]][]][[[]][]]][[]][]] dup cons ...

    == ...

    My Joy searcher would likely crash if it encounters such a program. That's not a good thing. But an efficient Joy searcher would

    implement "dup" by copying references, not by a deep copy, so that then the amount of space a program uses is bounded linearly by

    the length of time it is allowed it to run, which makes space requirements trivial. Another example that is even worse than the one

    above is

    == [[]] [[dup cat] dip dup i] dup i

    == [[]] dup cat dup cat dup cat dup cat ...

    == [[]] [[]] cat dup cat dup cat dup cat ...

    == [[] []] dup cat dup cat dup cat ...

    == [[] []] [[] []] cat dup cat dup cat ...

    == [[] [] [] []] dup cat dup cat ...

    == [[] [] [] []] [[] [] [] []] cat dup cat ...

    == [[] [] [] [] [] [] [] []] dup cat ...

    == [[] [] [] [] [] [] [] []] [[] [] [] [] [] [] [] []] cat ...

    This one is worse because it will thwart a system that assumes that shallow copies are cheap; that's why I'd suggest using trees.

    Using balanced trees might be helpful, but it is probably unnecessary, since the maximum depth of any tree is no larger than the

    number of steps we allow the program to run (which should be fairly small), times a small constant (normally 1 or 2) which depends

    on the choice of basis.

    Okay, so thus far this has been more of a description of how I should have written the searcher, and not how I actually did :-) But

    I'll explain one thing that I think I did right that could be a bit subtle. Prior to testing each program, the stack is arranged

    with a number of quotations of distinct special objects which I'll call indeterminates. For example, if you're searching for "dip",

    the goal line will look like

    2* 0[1]

    and two indeterminates (referred to as "0" and "1", "0" the top one) will be pushed prior to each test. When one of these

    indeterminates is executed, it is stored (in dequoted form) on the "data stack" just like quotations. Thus, you may think of the

    "data stack" as more of a history than of a stack in the literal sense. In one sense, a dequoted indeterminate is a brick wall in

    the history, in that attempting to look past one will generate a stack underflow, regardless of whether there are quotations beyond

    it.

    Anyhow, back to optimization strategies ... Currently, the only condition which causes the searcher to backtrack is a stack

    underflow. But there are other conditions which should also trigger this:

    1. Whenever a program appears to be non-terminating.

    2. Whenever an indeterminate is executed and the history/"data stack" does not precisely match the first part of the goal

    combinator.

    3. Whenever last copy of an indeterminate that is still needed is destroyed. (This is potentially more expensive to check; perhaps

    the set of referenced indeterminates could be built into the data structure for quotations/stack).

    Another optimization would be to build an exhaustive table of small constructions and find out which ones are equivalent. Then from

    each equivalence class, choose one representative and prohibit all others in the construction (Backtrack if one occurs). For

    example, in {o,k} we found that

    okookk == oookkk == zap q

    Therefore, to speed things up, we should choose "okookk" and prohibit "oookkk", or vice versa. Under certain bases and sufficiently

    large table size, it is possible that in building the table we may encounter some (apparently) non-terminating programs; if this

    happens, we should prohibit them entirely.

    - Brent

## William Tanksley, Jr — 2007-02-11 00:27:58

    stevan apter <sa@...> wrote:

     > as usual, work that you consider throw-away contains more insights than can fit in a standard

    > published article, much less the margins of one.

     I'm looking forward to your genetic system -- one would expect that it

    would be useful for the same purpose. Perhaps you should tailor a

    version of it to accept the same input as Kerby's, so we cant directly

    compare them.

    Also, Enchilada's tree data structure might be extremely useful for this.

     > - Brent

     -Billy

## Robbert van Dalen — 2007-02-11 11:27:34

    Great stuff!

    Still, I don't see the need for a flat binary base (except for

    extreme simplicity and fun).

    Why not allow 4 flat primitives that follow the 4 bases (ACGT) of

    DNA? :)

    I'm not sure but that may lead to smaller programs.

    I also wonder how one can do arithmetics on top of {o,k} without

    resorting to Church numerals.

     On Feb 11, 2007, at 1:27 AM, William Tanksley, Jr wrote:

    > stevan apter <sa@...> wrote:

    > > as usual, work that you consider throw-away contains more

    > insights than can fit in a standard

    > > published article, much less the margins of one.

    >

    > I'm looking forward to your genetic system -- one would expect that it

    > would be useful for the same purpose. Perhaps you should tailor a

    > version of it to accept the same input as Kerby's, so we cant directly

    > compare them.

    >

    > Also, Enchilada's tree data structure might be extremely useful for

    > this.

    If the flat base {o,k} settles to a definite version I would be very

    happy to implement it on top of Enchilada's tree structure.

    (or provide you guys with the algorithms).

    >

    > -Billy

    >

    >

    Robbert.

    >

## William Tanksley, Jr — 2007-02-11 18:45:29

    Robbert van Dalen <robbert.van.dalen@...> wrote:

     > Great stuff!

    > Still, I don't see the need for a flat binary base (except for

    > extreme simplicity and fun).

     That's a great reason :-). I'm using it to better understand perfect

    flatness, in hopes that I can see whether flatness has any desirable

    properties. It's also accidentally making it possible for me to

    understand combinators, which I now see that I didn't fully "get".

     > Why not allow 4 flat primitives that follow the 4 bases (ACGT) of

    > DNA? :)

    > I'm not sure but that may lead to smaller programs.

     It certainly would; but it would be just that much less flat (you

    could only 'cut' programs at every other bit address). Long-term, I'm

    likely going to make a 256-base code, and claim that it's flat at the

    8-bit byte level. But before I think about that I have to understand

    this much simpler system -- 256 bases is a lot to have to choose when

    one doesn't know why 2 bases are efficient.

     > I also wonder how one can do arithmetics on top of {o,k} without

    > resorting to Church numerals.

     That's essentially correct, although actually there are other

    conventions that will work as well as Church numbers do. As you know,

    Enchilada uses one of them (although of course E can see into its

    quotations). I haven't bothered choosing one, because I've got so much

    else to do.

     > > Also, Enchilada's tree data structure might be extremely useful for

    > > this.

    > If the flat base {o,k} settles to a definite version I would be very

    > happy to implement it on top of Enchilada's tree structure.

    > (or provide you guys with the algorithms).

     Thank you!

     > Robbert.

     -Billy

## William Tanksley, Jr — 2007-02-26 00:12:40

    Robbert van Dalen <robbert.van.dalen@...> wrote:

     > Why not allow 4 flat primitives that follow the 4 bases (ACGT) of

    > DNA? :)

    > I'm not sure but that may lead to smaller programs.

     I played with this -- it definitely does make things simpler, since

    you don't need to have a "do everything" 'o' combinator; the other

    combinators can help supply the needed operators.

    Of course, I wasn't imitating ACGT, but was just using 4 bases.

     > I also wonder how one can do arithmetics on top of {o,k} without

    > resorting to Church numerals.

     I haven't bothered trying to find out yet. But another possibility

    would be to include a new set of bases especially for handling

    numbers. You could even use a separate stack for numbers.

    -Billy