# Parallel computing is concatenative

## r_v_dalen — 2006-11-11 14:06:27

    In this post I argue that parallel programs are most naturally expressed in a concatenative

    language.

    We start our discussion by outlining a typical parallel computational strategy:

    1  Big units of work are split into smaller units of work.

    2  Smaller units are scattered across different threads/nodes.

    3  Each thread/node computes a (partial) result in parallel.

    4  Partial results are gathered from the threads/nodes.

    5  Finally, all partial results are merged into one end result.

    To summarise: most parallel and distributed computations are based on a divide and

    conquer strategy (via explicit scatter/gather steps).

    In array oriented languages (such as APL or K) it is rather easy to harness this kind of

    parallelism. For example, one can split an array (operation) into smaller array (operations)

    like this:

    [1 2 3 4] add [5 6 7 8] ==

    ([1 2] add [5 6]) join ([3 4] add [7 8])

    ..

    [1 2] add [5 6]  =>  [6 8]

    [3 4] add [7 8]  =>  [10 12]

    ..

    [6 8] join [10 12] => [6 8 10 12]

    However, a concatenative language such as Joy adds another opportunity for

    parallelization: concatenative programs can be can split into smaller ones (at any position)

    while their computational results can be concatenated just as easily (to any other

    program).

    1 2 + 3 4 + + ==

    ..

    1 2 + => 3

    3 4 + => 7

    ..

    3 7 + => 10

    One may wonder why this is so. One explanation is that concatenative programs and their

    (intermediate) results are absolutely indistinguishable. For example, every reduction-step

    is also a valid program:

    1 2 + 3 4 + +

    3 3 4 + +

    3 7 +

    10

    Concatenative programs carry no global state, no bindings and no variables. Also, their

    operands and operators are always in very close proximity. This means that computational

    semantics can be kept extremely simple and very localised, which is demonstrated by the

    following rules:

    1) scan for an operator.

    2) is the operator monadic?

     2.1) is the single element left to the monadic operator, an operand?

     2.2) reduce.

    3) the operator is dyadic.

     3.1 are the two elements left to the dyadic operator, operands?

     3.2 reduce.

    Of course, these rules would only apply if we restrict the operators to be either monadic

    and dyadic. Nevertheless, these rules are more or less shared by all other concatenative

    languages.

    It can be argued that exactly this 'principle of locality' allows the opportunity for parallel

    computation in the first place. For example, in languages where global state previals, it is

    usually much harder to find opportunities for parallelization.

    A striking observation is that every concatenative program with more than 1 possible

    reduction (redex) is a parallel program. In that sense, concatenative languages can be

    regarded as the most explicit parallel languages of them all.

    I'll wrap up with an example of an Enchilada program. This program will demonstrate how

    one can reformulate an implicit parallel array operation into an explicit parallel

    concatenative program:

    dac == cut max [mul] mul max

    ...

    [1 2 3 4 5 6 7 8] dac ==

    [1 2 3 4 5 6 7 8] cut max [mul] mul max

    [1 2 3 4] [5 6 7 8] max [mul] mul max

    [1 5;2 6; 3 7;4 8] [mul] mul max

    [1 5;2 6;3 7;4 8] [mul; mul; mul] max

    [1 5 mul;2 6 mul;3 7mul;4 8 mul]

    ...

    [1 2 3 4 5 6 7 8] dac dac dac dac lift ==>

    [1 2 mul 3 4 mul mul 5 6 mul 7 8 mul mul mul] lift ==>

    1 2 mul 3 4 mul mul 5 6 mul 7 8 mul mul mul

    One of the goals of the Enchilada language is to provide a simple, efficient core for doing

    parallel and distributed computations. For more info: see  http://my.opera.com/rapido/

    blog/ and http://enchilada.javaforge.com/

## Robbert van Dalen — 2006-11-11 14:30:49

    [REPOST: YAHOO MAIL DISTROYED MY PREVIOUS POST)

    In this post I argue that parallel programs are most

    naturally expressed in a concatenative language.

    We start our discussion by outlining a typical

    parallel computational strategy:

    1  Big units of work are split into smaller units of

    work.

    2  Smaller units are scattered across different

    threads/nodes.

    3  Each thread/node computes a (partial) result in

    parallel.

    4  Partial results are gathered from the

    threads/nodes.

    5  Finally, all partial results are merged into one

    end result.

    To summarise: most parallel and distributed

    computations are based on a divide and conquer

    strategy (via explicit scatter/gather steps).

    In array oriented languages (such as APL or K) it is

    rather easy to harness this kind of parallelism. For

    example, one can split an array (operation) into

    smaller array (operations) like this:

    [1 2 3 4] add [5 6 7 8] ==

    ([1 2] add [5 6]) join ([3 4] add [7 8])

    ..

    [1 2] add [5 6]  =>  [6 8]

    [3 4] add [7 8]  =>  [10 12]

    ..

    [6 8] join [10 12] => [6 8 10 12]

    However, a concatenative language such as Joy adds

    another opportunity for parallelization: concatenative

    programs can be can split into smaller ones (at any

    position) while their computational results can be

    concatenated just as easily (to any other program).

    1 2 + 3 4 + + ==

    ..

    1 2 + => 3

    3 4 + => 7

    ..

    3 7 + => 10

    One may wonder why this is so. One explanation is that

    concatenative programs and their (intermediate)

    results are absolutely indistinguishable. For example,

    every reduction-step is also a valid program:

    1 2 + 3 4 + +

    3 3 4 + +

    3 7 +

    10

    Concatenative programs carry no global state, no

    bindings and no variables. Also, their operands and

    operators are always in very close proximity. This

    means that computational semantics can be kept

    extremely simple and very localised, which is

    demonstrated by the following rules:

    1) scan for an operator.

    2) is the operator monadic?

     2.1) is the single element left to the monadic

    operator, an operand?

     2.2) reduce.

    3) the operator is dyadic.

     3.1 are the two elements left to the dyadic operator,

    operands?

     3.2 reduce.

    Of course, these rules would only apply if we restrict

    the operators to be either monadic and dyadic.

    Nevertheless, these rules are more or less shared by

    all other concatenative languages.

    It can be argued that exactly this 'principle of

    locality' allows the opportunity for parallel

    computation in the first place. For example, in

    languages where global state previals, it is usually

    much harder to find opportunities for parallelization.

    A striking observation is that every concatenative

    program with more than 1 possible reduction (redex) is

    a parallel program. In that sense, concatenative

    languages can be regarded as the most explicit

    parallel languages of them all.

    I'll wrap up with an example of an Enchilada program.

    This program will demonstrate how one can reformulate

    an implicit parallel array operation into an explicit

    parallel concatenative program:

    dac == cut max [mul] mul max

    ...

    [1 2 3 4 5 6 7 8] dac ==

    [1 2 3 4 5 6 7 8] cut max [mul] mul max

    [1 2 3 4] [5 6 7 8] max [mul] mul max

    [1 5;2 6; 3 7;4 8] [mul] mul max

    [1 5;2 6;3 7;4 8] [mul; mul; mul] max

    [1 5 mul;2 6 mul;3 7mul;4 8 mul]

    ...

    [1 2 3 4 5 6 7 8] dac dac dac dac lift ==>

    [1 2 mul 3 4 mul mul 5 6 mul 7 8 mul mul mul] lift ==>

    1 2 mul 3 4 mul mul 5 6 mul 7 8 mul mul mul

    One of the goals of the Enchilada language is to

    provide a simple, efficient core for doing parallel

    and distributed computations. For more info: see

    http://my.opera.com/rapido/blog/ and

    http://enchilada.javaforge.com/

    ____________________________________________________________________________________

    Yahoo! Music Unlimited

    Access over 1 million songs.

    http://music.yahoo.com/unlimited

## Magnus Jonsson — 2006-11-11 18:36:00

    I would argue the opposite, that the stack model is lousy for

    expressing parallel programs because it forces everything to be sequenced

    by the programmer. Simple relationships between inputs and outputs are

    obscured by stack shuffling.

    compare:

    length x y z = sqrt (square x + square y + square z)

    : length ( x y z -- length )

       square rot square rot square rot sqrt ;

    How can you parallelize length without essentially abandoning the stack

    shuffling representation of your program?

    / Magnus

## Magnus Jonsson — 2006-11-11 18:43:23

    On Sat, 11 Nov 2006, Magnus Jonsson wrote:

     > : length ( x y z -- length )

    >   square rot square rot square rot sqrt ;

     That should of course have been:

    : length ( x y z -- length )

       square rot square rot square rot + + sqrt ;

    or

       square swap square + swap square + sqrt

## Robbert van Dalen — 2006-11-11 19:35:21

    > I would argue the opposite, that the stack model is

    > lousy for

    > expressing parallel programs because it forces

    > everything to be sequenced

    > by the programmer. Simple relationships between

    > inputs and outputs are

    > obscured by stack shuffling.

     I think you bring up a fair counter argument. Stack

    shuffling is indeed synonymous to explicit sequencing.

    Perhaps one could argue that algorithms that need

    stack shuffling are inherently sequential. So yes,

    such algorithms are more naturally expressed in

    applicative form.

    My feeling is that most operations don't need more

    then two arguments at most.

    But when certain operations do need more then two, my

    intuitions say that such operations can be split into

    smaller operations - and that such operations can be

    performed in parallel.

     > compare:

    >

    > length x y z = sqrt (square x + square y + square z)

    >

    > : length ( x y z -- length )

    >    square rot square rot square rot sqrt ;

    >

    > How can you parallelize length without essentially

    > abandoning the stack

    > shuffling representation of your program?

     I would say that the shuffling of three arguments

    doesn't give much opportunity for parallelism. But to

    take the length of a million operands is another

    matter I would say.

    In Enchilada parallel squaring can be done as follows

    (similar to map)

    [a;b;c; ....] [square] mul max =>

    [a square; b square; c square; ...]

    Then if we define dac as follows:

    dac == cut max [add] mul max

    and apply dac multiple times we get:

    [a square b square add c square d square add add ...]

    which obviously can be reduced parallel.

     > / Magnus

     - Robbert.

    ____________________________________________________________________________________

    Do you Yahoo!?

    Everyone is raving about the all-new Yahoo! Mail beta.

    http://new.mail.yahoo.com

## Christopher Diggins — 2006-11-11 20:52:48

    Some forms of concatenative programs are trivially parallelized, while

    others aren't. Consider the following definition for length in Cat:

    define length { square rot square rot square rot + + sqrt }

    While this is hard to parallelize, the following equivalent program:

    define length { triple [square] map [+] reduce sqrt }

    is trivial to parallelize (map and reduces can be implemented as

    concurrent primitives).

    The challenge is to automatically transform arbitrary Cat programs

    into an easily parallelized form. I am working on the specification

    for a sequel to Cat (tentatively called Mutt) which would allow the

    definition of macros. Mutt would enable the definition of

    transformation rules, so that we can automatically convert Cat

    programs into more easily parallelized programs:

    The following is a how the neccessary transform might look in in Mutt:

    transform {

      x:(A:any)->(B:any) rot x rot x rot

      y:(B:any B)->(B:any) y

    }

    -> {

      cons cons

      [x] map

      [y] reduce

    }

    This form indicates that x is a function from a single type A to

    another type B (like sqr which has type (int)->(int)) and y is a

    function which consumes two values of type B and produces a single

    value of type B (like + which has type (int int)->(int)).

    So what I am proposing with Mutt is a language for rewriting typed

    concatenative programs.

     On 11/11/06, Magnus Jonsson <magnus@...> wrote:

    >

    >

    > I would argue the opposite, that the stack model is lousy for

    > expressing parallel programs because it forces everything to be sequenced

    > by the programmer. Simple relationships between inputs and outputs are

    > obscured by stack shuffling.

    >

    > compare:

    >

    > length x y z = sqrt (square x + square y + square z)

    >

    > : length ( x y z -- length )

    > square rot square rot square rot sqrt ;

    >

    > How can you parallelize length without essentially abandoning the stack

    > shuffling representation of your program?

    >

    > / Magnus

## Magnus Jonsson — 2006-11-11 21:12:52

    Hi Robert,

     On Sat, 11 Nov 2006, Robbert van Dalen wrote:

    > But when certain operations do need more then two, my

    > intuitions say that such operations can be split into

    > smaller operations - and that such operations can be

    > performed in parallel.

    I doubt that you are lucky enough to get programs like

    1 2 + 3 4 + +

    in reality, because most functions take some input and probably have to do

    a little bit of shuffling to get them into the right place of the

    expression.

    >> : length ( x y z -- length )

    >>    square rot square rot square rot sqrt ;

    >>

    >> How can you parallelize length without essentially

    >> abandoning the stack

    >> shuffling representation of your program?

    >

    > I would say that the shuffling of three arguments

    > doesn't give much opportunity for parallelism. But to

    > take the length of a million operands is another

    > matter I would say.

    What about:

    length x y = sqrt (square x + square y)

    : length square swap square + sqrt ;

    Even here the parallelism is somewhat obscured but I can see how a clever

    compiler could notice this pattern.

    I think if the stack model was extended with some a naming mechanism we

    could write it more naturally and make the parallelism explicit as well:

    : length >y >x x square y square + sqrt ;

    or using a pattern matching syntax for function definitions:

    : x y length = x square y square + sqrt ;

    > In Enchilada parallel squaring can be done as follows

    > (similar to map)

    >

    > [a;b;c; ....] [square] mul max =>

    > [a square; b square; c square; ...]

    >

    > Then if we define dac as follows:

    >

    > dac == cut max [add] mul max

    >

    > and apply dac multiple times we get:

    >

    > [a square b square add c square d square add add ...]

    >

    > which obviously can be reduced parallel.

    Yes, if you can do this most of the time then I think you have a valid

    approach. I admit I didn't fully understand the above but the gist seems

    to be vector computing.

    Best,

    Magnus Jonsson

## Magnus Jonsson — 2006-11-11 21:29:55

    On Sat, 11 Nov 2006, Christopher Diggins wrote:

     > While this is hard to parallelize, the following equivalent program:

    >

    > define length { triple [square] map [+] reduce sqrt }

    >

    > is trivial to parallelize (map and reduces can be implemented as

    > concurrent primitives).

     Good point.

     > transform {

    >  x:(A:any)->(B:any) rot x rot x rot

    >  y:(B:any B)->(B:any) y

    > }

    > -> {

    >  cons cons

    >  [x] map

    >  [y] reduce

    > }

    >

    > So what I am proposing with Mutt is a language for rewriting typed

    > concatenative programs.

     You are probably aware of this already, but I'll mention it anyway: This

    approach has been used with great success in the haskell community to

    express library specific optimizations. The brightest example is

    the ByteString library.

    http://web.mit.edu/ghc/www/users_guide/rewrite-rules.html

    / Magnus

     > On 11/11/06, Magnus Jonsson <magnus@...> wrote:

    >>

    >>

    >> I would argue the opposite, that the stack model is lousy for

    >> expressing parallel programs because it forces everything to be sequenced

    >> by the programmer. Simple relationships between inputs and outputs are

    >> obscured by stack shuffling.

    >>

    >> compare:

    >>

    >> length x y z = sqrt (square x + square y + square z)

    >>

    >> : length ( x y z -- length )

    >> square rot square rot square rot sqrt ;

    >>

    >> How can you parallelize length without essentially abandoning the stack

    >> shuffling representation of your program?

    >>

    >> / Magnus

    >

## Christopher Diggins — 2006-11-11 21:49:11

    On 11/11/06, Magnus Jonsson <magnus@...> wrote:

     > On Sat, 11 Nov 2006, Christopher Diggins wrote:

    >

    > You are probably aware of this already, but I'll mention it anyway: This

    > approach has been used with great success in the haskell community to

    > express library specific optimizations. The brightest example is

    > the ByteString library.

    >

    > http://web.mit.edu/ghc/www/users_guide/rewrite-rules.html

    >

    > / Magnus

     I wasn't aware that this was implemented as a language extension in

    the GHC compiler. I had only heard second hand discussion, and read a

    couple papers about deforestation. This is great news for me since it

    lends some academic credibility to the idea of a stand-alone

    transformation language. Thanks for sharing the link with me.

    I believe a rewriting language like Mutt could also be useful for

    writing the actual implementation of a compiler of a concatenative

    language by rewriting the program as an arbitrary assembly language. I

    also think that concatenative languages are probably significantly

    easier to rewrite than languages like Haskell, due to their algebraic

    simplicity.

    Cheers,

    Christopher

## Robbert van Dalen — 2006-11-12 20:34:38

    Hi Magnus,

     > I doubt that you are lucky enough to get programs

    > like

    >

    > 1 2 + 3 4 + +

     I would say we wouldn't be so lucky - programmers

    should push their programs to such forms, ie. make

    parallism more explicit.

     > in reality, because most functions take some input

    > and probably have to do

    > a little bit of shuffling to get them into the right

    > place of the

    > expression.

     Yes, that's true. But just because there can be little

    bit of shuffling from time to time I wouldn't cast all

    concatenative languages as being opposite of parallel

    languages?

     > What about:

    >

    > length x y = sqrt (square x + square y)

    >

    > : length square swap square + sqrt ;

    >

    > Even here the parallelism is somewhat obscured but I

    > can see how a clever

    > compiler could notice this pattern.

     Sure, the postfix form:

    1 2 + 3 4 + +

    can be as easily rewritten to infix:

    (1 + 2) + (3 + 4)

    which is just as 'parallel' as the postfix version.

    I think what give concatenative languages the

    advantage is that you can cut any (postfix) expression

    anywhere you want without ending up with illegal

    expressions.

    It's a matter of keeping things simple, i.e. KISS.

     >

    > I think if the stack model was extended with some a

    > naming mechanism we

    > could write it more naturally and make the

    > parallelism explicit as well:

    >

    > : length >y >x x square y square + sqrt ;

    >

    > or using a pattern matching syntax for function

    > definitions:

    >

    > : x y length = x square y square + sqrt ;

    >

     Although that would be nice, such construct also

    forces the introduction of scope, which could destroy

    some of the  'principles of locality' that is so

    important for parallel computation to work.

     > > In Enchilada parallel squaring can be done as

    > follows

    > > (similar to map)

    > >

    > > [a;b;c; ....] [square] mul max =>

    > > [a square; b square; c square; ...]

    > >

    > > Then if we define dac as follows:

    > >

    > > dac == cut max [add] mul max

    > >

    > > and apply dac multiple times we get:

    > >

    > > [a square b square add c square d square add add

    > ...]

    > >

    > > which obviously can be reduced parallel.

    >

    > Yes, if you can do this most of the time then I

    > think you have a valid

    > approach. I admit I didn't fully understand the

    > above but the gist seems

    > to be vector computing.

     You can safely ignore the Enchilada speak. What I

    wanted to say is that the parallization of vector

    operations is pretty much straightforward.

    What I'm after is *explicit* parallism in the most

    dense form. So one of the example programs I've have

    given rewrote the following *implicit* parallel vector

    program:

    [1;2;3;4] [7;8;9;10] add

    into the following *explicit* parallel concatenative

    program:

    1 7 + 2 8 + + 3 9 +4 10 + + +

    - Robbert.

    ____________________________________________________________________________________

    Cheap talk?

    Check out Yahoo! Messenger's low PC-to-Phone call rates.

    http://voice.yahoo.com

## Magnus Jonsson — 2006-11-12 21:23:28

    On Sun, 12 Nov 2006, Robbert van Dalen wrote:

     > given rewrote the following *implicit* parallel vector

    > program:

    >

    > [1;2;3;4] [7;8;9;10] add

    >

    > into the following *explicit* parallel concatenative

    > program:

    >

    > 1 7 + 2 8 + + 3 9 +4 10 + + +

     I see. I'm going to defer my judgement about this :)

    / Magnus Jonsson

## William Tanksley, Jr — 2006-11-13 14:58:21

    Robbert van Dalen <r_v_dalen@...> wrote:

     > Hi Magnus,

    > > I doubt that you are lucky enough to get programs

    > > like

    > > 1 2 + 3 4 + +

    > I would say we wouldn't be so lucky - programmers

    > should push their programs to such forms, ie. make

    > parallism more explicit.

     Before I start, let me emphasise that I'm a concatenative language

    fanatic. I have every reason and desire to have a positive opinion

    about concatenative languages in every way.

    But I just don't see this as an actual feature of concatenative

    languages in general. (Enchilada is an exception.)

    The fact is that although you _can_ write programs that are capable of

    parallelization, the language format itself does not offer you any

    help or visual assistance -- good parallel programs do NOT look better

    than good serial programs when in concatenative form.

    I've always been of the opinion that concatenative languages are good

    for optimization, because a well-formatted and tidy concatenative

    program contains as few stack shuffles as possible in order to be

    readable -- which concidentally means it moves data around as little

    as possible, so it's fast and highly cache-local. There's a direct

    feedback between a good-looking concatenative program and a

    fast-running concatenative program.

    But that handy link between looks and behavior doesn't seem to me to

    hold for parallelism. I just don't see it.

    Now, I could imagine a simple dataflow graph generator for a

    concatenative language; such a thing would produce a graph in linear

    time (it takes longer to generate a dataflow for an applicative

    language), and then could parallelize the execution of the graph. But

    again, there's nothing about the language that makes this uniquely

    possible or interesting, and especially there's nothing about the

    language that makes the programmer able to help with what's going on.

     > > in reality, because most functions take some input

    > > and probably have to do

    > > a little bit of shuffling to get them into the right

    > > place of the

    > > expression.

    > Yes, that's true. But just because there can be little

    > bit of shuffling from time to time I wouldn't cast all

    > concatenative languages as being opposite of parallel

    > languages?

     No, but that doesn't mean concatenativity is a natural boon to

    parallelism either.

     > I think what give concatenative languages the

    > advantage is that you can cut any (postfix) expression

    > anywhere you want without ending up with illegal

    > expressions.

     By the way, the ability to cut "anywhere" isn't really a property of

    concatenative languages (although I keep thinking it _should_ be,

    because it very nearly is); it's a property of "flat" languages.

    Concatenativity only promises that you can _join_ any two valid

    programs to produce a third valid program.

    Anyhow, the problem with cutting and rejoining is that they are serial

    operations -- in general, you must know the final result of the first

    section in order to begin computation on the second section. There are

    specific exceptions, and there's plenty of stack algebra you can do to

    find them, but that's not something that "concatenativity" buys you.

     > > I think if the stack model was extended with some a

    > > naming mechanism we

    > > could write it more naturally and make the

    > > parallelism explicit as well:

    > > : length >y >x x square y square + sqrt ;

    > > or using a pattern matching syntax for function

    > > definitions:

    > > : x y length = x square y square + sqrt ;

    > Although that would be nice, such construct also

    > forces the introduction of scope, which could destroy

    > some of the  'principles of locality' that is so

    > important for parallel computation to work.

     Yup. It would also destroy concatenativity.

     > You can safely ignore the Enchilada speak. What I

    > wanted to say is that the parallization of vector

    > operations is pretty much straightforward.

     Enchilada, and array languages in general, are nice and natural for

    parallelism. I'd like to see much more work on array concatenative

    languages like X, XY, cK, Enchilada, and so on. By people who

    understand array languages well, of course (which rules me out -- I

    like 'em, I think I can read 'em, but I'm no expert).

     > What I'm after is *explicit* parallism in the most

    > dense form. So one of the example programs I've have

    > given rewrote the following *implicit* parallel vector

    > program:

    > [1;2;3;4] [7;8;9;10] add

     That looks to me like an explicitly parallel vector program.

     > into the following *explicit* parallel concatenative

    > program:

    > 1 7 + 2 8 + + 3 9 +4 10 + + +

     And that looks like a serially written program; the parallelism is at

    best implicit, and at that it's implicit because of a property of the

    "+" function that not all functions have.

     > - Robbert.

     -Billy

## Robbert van Dalen — 2006-11-13 21:13:09

    Hi Billy,

    Many, many thanks for putting so much effort in

    proving me wrong! I *really* do appreciate it.

     > Before I start, let me emphasise that I'm a

    > concatenative language

    > fanatic. I have every reason and desire to have a

    > positive opinion

    > about concatenative languages in every way.

     Before I start, let me emphasise that I'm *not* a

    concatenative language fanatic ;)

    But I do like the simplicity and the unusual

    properties.

     > But I just don't see this as an actual feature of

    > concatenative

    > languages in general. (Enchilada is an exception.)

     I don't feel that Enchilada is an exception - except

    that Enchilada's implementation of a concatenative

    language is very different.

     > The fact is that although you _can_ write programs

    > that are capable of

    > parallelization, the language format itself does not

    > offer you any

    > help or visual assistance -- good parallel programs

    > do NOT look better

    > than good serial programs when in concatenative

    > form.

     I think I agree - partially. But may be it is just me,

    but I can see the inherent parallism when I'm

    eyeballing the following expression:

    1 2 + 3 4 + +

    here is how I go about it:

    .... scanning for an operator.....

    ..found one

    1 2 + 3 4 + +

        ^

    is it reducable? yes!

    .... scanning for another operator....

    ....found another

    1 2 + 3 4 + +

        ^     ^

    Now we've got two possible reductions. Moreover, it

    doesn't matter which of the two we are going to reduce

    first.

    I think that the former is also the most simple and

    explicit form of a parallel program. (but of course,

    you and I could have eye-balled that expression

    completely different!)

     >

    > I've always been of the opinion that concatenative

    > languages are good

    > for optimization, because a well-formatted and tidy

    > concatenative

    > program contains as few stack shuffles as possible

    > in order to be

    > readable -- which concidentally means it moves data

    > around as little

    > as possible, so it's fast and highly cache-local.

    > There's a direct

    > feedback between a good-looking concatenative

    > program and a

    > fast-running concatenative program.

     I think you are absolutely right: the cache-local

    argument is  synonymous to the 'principle of locality'

    argument.

     > But that handy link between looks and behavior

    > doesn't seem to me to

    > hold for parallelism. I just don't see it.

     May be you'll see it when you free your mind from

    stacks ;)

    But seriously, as Manfred has pointed out before me,

    Joy or any concatenative language doesn't need to be

    implemented on top of a stack.

     > Now, I could imagine a simple dataflow graph

    > generator for a

    > concatenative language; such a thing would produce a

    > graph in linear

    > time (it takes longer to generate a dataflow for an

    > applicative

    > language), and then could parallelize the execution

    > of the graph.

     Thanks for bringing up the dataflow argument! In fact,

    the ability to compile Enchilada into a dataflow

    runtime is/was one of the main design goals.

    (shameless plug: http://syrup.sourceforge.net/)

    Anyway, concatenative programs can be thought of

    serialized dataflow graphs (not quite but close).

    Another nice example of the relationship between

    dataflow and concatenative languages is Slava's

    dataflow visualiser:

    http://factorcode.org/dataflow-ui.png

     > But

    > again, there's nothing about the language that makes

    > this uniquely

    > possible or interesting, and especially there's

    > nothing about the

    > language that makes the programmer able to help with

    > what's going on.

     Programmers would be helped a lot of they just scan

    for reducable operators ;)

    But yes, it is not a concatenative feature perse. The

    following infix expression would do just as well:

    (1 + 2) + (3 + 4)

     > By the way, the ability to cut "anywhere" isn't

    > really a property of

    > concatenative languages (although I keep thinking it

    > _should_ be,

    > because it very nearly is); it's a property of

    > "flat" languages.

    > Concatenativity only promises that you can _join_

    > any two valid

    > programs to produce a third valid program.

     I tend to disagree. I'm not sure, but I think you run

    into a serious contradiction when a language allows

    you to concatenate any valid program but not cut them.

    But may be my idea of "flatness" is different from

    what has been discussed on the concatenative list

    previously. For instance, I think Joy is perfectly

    flat. For instance, this is a valid Joy program:

    1 2 + [3 4 +] i

    .. and when we cut it at a random point:

    1 2 +

    [3 4 +] i

    .. and cut further into:

    1

    2 +

    [3 4 +]

    i

    .. we get 4 perfectly valid programs.

    now one would say that the cutting of [3 4 +] cannot

    be done and hence Joy is not flat. Syntactically that

    is a true statement, but semantically one could split

    a quotation without any problem:

    [3] [4 +]

     > Anyhow, the problem with cutting and rejoining is

    > that they are serial

    > operations -- in general, you must know the final

    > result of the first

    > section in order to begin computation on the second

    > section.

     No, the cutting and joining of expressions isn't

    serial - that's an implementation detail. In Enchilada

    you can cut an expression of a million operands and

    operators non-serially in O(log(million)).

     > There are

    > specific exceptions, and there's plenty of stack

    > algebra you can do to

    > find them, but that's not something that

    > "concatenativity" buys you.

     In Enchilada it is not an exception - but that's an

    implementation detail.

     > Enchilada, and array languages in general, are nice

    > and natural for

    > parallelism. I'd like to see much more work on array

    > concatenative

    > languages like X, XY, cK, Enchilada, and so on. By

    > people who

    > understand array languages well, of course (which

    > rules me out -- I

    > like 'em, I think I can read 'em, but I'm no

    > expert).

     I'm no expert either. Such important stuff should be

    left to the popcorn lovers ;)

     > > What I'm after is *explicit* parallism in the most

    > > dense form. So one of the example programs I've

    > have

    > > given rewrote the following *implicit* parallel

    > vector

    > > program:

    > > [1;2;3;4] [7;8;9;10] add

    >

    > That looks to me like an explicitly parallel vector

    > program.

     Under a certain interpretation, yes.

     >

    > > into the following *explicit* parallel

    > concatenative

    > > program:

    > > 1 7 + 2 8 + + 3 9 +4 10 + + +

    > And that looks like a serially written program; the

    > parallelism is at

    > best implicit, and at that it's implicit because of

    > a property of the

    > "+" function that not all functions have.

     I hope that my arguments can change that 'serial' view

    somewhat.

     > -Billy

     - Robbert.

    ____________________________________________________________________________________

    Cheap talk?

    Check out Yahoo! Messenger's low PC-to-Phone call rates.

    http://voice.yahoo.com

## Robbert van Dalen — 2006-11-14 09:37:10

    Billy,

    I've just posted on my blog, which hopefully gives

    some more food for thought.

    http://my.opera.com/rapido/blog/

    ____________________________________________________________________________________

    Yahoo! Music Unlimited

    Access over 1 million songs.

    http://music.yahoo.com/unlimited

## William Tanksley, Jr — 2006-11-15 20:54:42

    Robbert van Dalen <r_v_dalen@...> wrote:

     > Many, many thanks for putting so much effort in

    > proving me wrong! I *really* do appreciate it.

     You're very welcome -- but I don't expect to prove you wrong; I just

    want to see elaboration of what you mean. Thank you for exploring your

    ideas; you've definitely mixed some interesting new things into my

    head.

    I wouldn't have EVER thought that a tally-based number system would be

    interesting; it would "OBVIOUSLY" be too slow. Well, a guy can be

    wrong, and it looks like I was wrong.

     > > But I just don't see this as an actual feature of

    > > concatenative

    > > languages in general. (Enchilada is an exception.)

    > I don't feel that Enchilada is an exception - except

    > that Enchilada's implementation of a concatenative

    > language is very different.

     Different? It looks like you have the basic features pretty much the

    same... Yes, you implement quotations differently, but Forth doesn't

    implement quotations _at all_, and it's still concatenative.

    Enchilada is still very different from any other concatenative

    language, of course. I didn't mean to imply that it was boring :-).

     > > The fact is that although you _can_ write programs

    > > that are capable of

    > > parallelization, the language format itself does not

    > > offer you any

    > > help or visual assistance -- good parallel programs

    > > do NOT look better

    > > than good serial programs when in concatenative

    > > form.

    > I think I agree - partially. But may be it is just me,

    > but I can see the inherent parallism when I'm

    > eyeballing the following expression:

    > 1 2 + 3 4 + +

     Hmm... But when basic concatenative properties are applied to it (such

    as factoring), the "visible" parallelism goes away. I'm not even sure

    it's all that visible -- you can see it because you know very well

    certain properties of "+" and numeric literals.

    I'm not sure you're wrong, either... I just don't see how to apply

    your algorithm in general, nor do I see how the algorithm would make a

    non-parallel mistake "feel" wrong, even to an experienced programmer.

    (A slow dataflow "feels" wrong because the resulting code gets ugly

    with "stack noise".)

     > here is how I go about it:

    > .... scanning for an operator.....

    > ..found one

    > 1 2 + 3 4 + +

    >     ^

    > is it reducable? yes!

    > .... scanning for another operator....

    > ....found another

    > 1 2 + 3 4 + +

    >     ^     ^

     Hmm. "Operator" isn't a term the concatenative community uses. Perhaps

    we should. How would you define it? I also don't really know what

    "reducible" means, although I think it means that a JIT optimizer

    could choose whether or not to execute the code right then and there

    without any dependancies on stuff that might be out of its sight.

     > Now we've got two possible reductions. Moreover, it

    > doesn't matter which of the two we are going to reduce

    > first.

     Makes sense.

     > I think that the former is also the most simple and

    > explicit form of a parallel program. (but of course,

    > you and I could have eye-balled that expression

    > completely different!)

     It's not explicit, though; it's implicit. An explicitly parallel

    program would *explicitly* mark the parallel lines of computation,

    showing where the diverge and where they come back together. I seem to

    recall that there's a version of the K language that works this way,

    and it looks similar to Enchilada.

     > > I've always been of the opinion that concatenative

    > > languages are good

    > > for optimization, because a well-formatted and tidy

    > > concatenative

    > > program contains as few stack shuffles as possible

    > > in order to be

    > > readable -- which concidentally means it moves data

    > > around as little

    > > as possible, so it's fast and highly cache-local.

    > > There's a direct

    > > feedback between a good-looking concatenative

    > > program and a

    > > fast-running concatenative program.

    > I think you are absolutely right: the cache-local

    > argument is  synonymous to the 'principle of locality'

    > argument.

     Right. Interestingly, a stack-based language encourages the programmer

    to arrange ALL the data roughly in order of need, so that an optimizer

    can distribute the data across multiple levels of cache in what I

    imagine would be a pretty simple and effective way.

     > > But that handy link between looks and behavior

    > > doesn't seem to me to

    > > hold for parallelism. I just don't see it.

    > May be you'll see it when you free your mind from

    > stacks ;)

    > But seriously, as Manfred has pointed out before me,

    > Joy or any concatenative language doesn't need to be

    > implemented on top of a stack.

     That's a possible claim. I've seen it made, and I've agreed with the

    basic principle. The problem is that I've never seen any

    counterexample for its denial. If I told you that "every concatenative

    language is a stack language", how would you argue with me?

    Actually, take a look at the short name of this group, which appears

    at the start of every message title.

    So although I very well understand the mathematical properties which

    gave rise to our understanding of compositional concatenative

    languages, I simply have no idea how they can be done without LIFO

    semantics -- i.e. a stack.

    Oh, and even the fundamental mathematical property of function

    composition is inherently serial.

     > > Now, I could imagine a simple dataflow graph

    > > generator for a

    > > concatenative language; such a thing would produce a

    > > graph in linear

    > > time (it takes longer to generate a dataflow for an

    > > applicative

    > > language), and then could parallelize the execution

    > > of the graph.

    > Thanks for bringing up the dataflow argument! In fact,

    > the ability to compile Enchilada into a dataflow

    > runtime is/was one of the main design goals.

     That's very cool. I definitely do agree that automatic dataflow

    annotations would make parallelism easy to see... But I don't see how

    or why to make that part of the language.

     > (shameless plug: http://syrup.sourceforge.net/)

     That's COOL! Thanks!

     > Anyway, concatenative programs can be thought of

    > serialized dataflow graphs (not quite but close).

     I don't see the "not quite" part -- that seems to me to be exactly

    what they are.

     > Another nice example of the relationship between

    > dataflow and concatenative languages is Slava's

    > dataflow visualiser:

    > http://factorcode.org/dataflow-ui.png

     That's something I'd like to see in an editor. I've often thought of

    it, but I lack the GUI skill.

     > > But

    > > again, there's nothing about the language that makes

    > > this uniquely

    > > possible or interesting, and especially there's

    > > nothing about the

    > > language that makes the programmer able to help with

    > > what's going on.

    > Programmers would be helped a lot of they just scan

    > for reducable operators ;)

     That's a great example of programmers helping themselves, yes. I would

    call that a code review.

     > But yes, it is not a concatenative feature perse. The

    > following infix expression would do just as well:

    > (1 + 2) + (3 + 4)

     That makes sense to me.

     > > By the way, the ability to cut "anywhere" isn't

    > > really a property of

    > > concatenative languages (although I keep thinking it

    > > _should_ be,

    > > because it very nearly is); it's a property of

    > > "flat" languages.

    > > Concatenativity only promises that you can _join_

    > > any two valid

    > > programs to produce a third valid program.

    > I tend to disagree. I'm not sure, but I think you run

    > into a serious contradiction when a language allows

    > you to concatenate any valid program but not cut them.

     It's not a contadiction -- of course you must be able to cut where you

    joined. The question is, can you cut ANYWHERE, and if not, what are

    the restrictions on where you can cut? If you can't state the

    restrictions, or if they're so strong that most places in most

    programs can't be cut, the claim of being able to cut programs seems a

    lot weaker than it should be.

     > But may be my idea of "flatness" is different from

    > what has been discussed on the concatenative list

    > previously. For instance, I think Joy is perfectly

    > flat. For instance, this is a valid Joy program:

     Manfred created a dialect of Joy called "floy", a flat Joy, so he

    doesn't think Joy is perfectly flat.

     > 1 2 + [3 4 +] i

    > .. and when we cut it at a random point:

    > 1 2 +

    > [3 4 +] i

     That's not random enough :-). More accurately, there are 8 plausible

    cut points in the sequence, and only 4 of them can be cut (assuming

    you only try to cut between tokens, which seems right to me). If you

    cut inside the quotation, the resulting two programs are not valid --

    for example, "1 2 + [" is not a valid program in Joy.

    In Joy, that program is 50% flat.

     > now one would say that the cutting of [3 4 +] cannot

    > be done and hence Joy is not flat. Syntactically that

    > is a true statement, but semantically one could split

    > a quotation without any problem:

    > [3] [4 +]

     But that's not semanticly the same, either -- that's not a split

    quotation, but rather is two quotations. Even there, you've added two

    syntactic things to the function that weren't there before.

    Flatness is a syntactic property. If it were semantic, EVERY

    (Turing-complete) language would be flat, and it would be boring.

     > > Anyhow, the problem with cutting and rejoining is

    > > that they are serial

    > > operations -- in general, you must know the final

    > > result of the first

    > > section in order to begin computation on the second

    > > section.

    > No, the cutting and joining of expressions isn't

    > serial - that's an implementation detail. In Enchilada

    > you can cut an expression of a million operands and

    > operators non-serially in O(log(million)).

     The source code is serial; the cutting is serial. You may represent

    the source code non-serially (perhaps as a dataflow graph), but that

    doesn't change how the programmer sees it until you make that graph

    the main language, at which point we're not really talking about a

    concatenative language anymore.

     > > There are

    > > specific exceptions, and there's plenty of stack

    > > algebra you can do to

    > > find them, but that's not something that

    > > "concatenativity" buys you.

    > In Enchilada it is not an exception - but that's an

    > implementation detail.

     I've seen Enchilada, and it definitely isn't flat. (I don't think it

    should be; perfect flatness is a painful thing.)

     > > Enchilada, and array languages in general, are nice

    > > and natural for

    > > parallelism. I'd like to see much more work on array

    > > concatenative

    > > languages like X, XY, cK, Enchilada, and so on. By

    > > people who

    > > understand array languages well, of course (which

    > > rules me out -- I

    > > like 'em, I think I can read 'em, but I'm no

    > > expert).

    > I'm no expert either. Such important stuff should be

    > left to the popcorn lovers ;)

     I've mentioned K now... Perhaps we'll learn something about how array

    languages do it...

     > > > What I'm after is *explicit* parallism in the most

    > > > dense form. So one of the example programs I've

    > > have

    > > > given rewrote the following *implicit* parallel

    > > vector

    > > > program:

    > > > [1;2;3;4] [7;8;9;10] add

    > > That looks to me like an explicitly parallel vector

    > > program.

    > Under a certain interpretation, yes.

     Explicitness doesn't lend itself to interpretation.

     > > > into the following *explicit* parallel

    > > concatenative

    > > > program:

    > > > 1 7 + 2 8 + + 3 9 +4 10 + + +

    > > And that looks like a serially written program; the

    > > parallelism is at

    > > best implicit, and at that it's implicit because of

    > > a property of the

    > > "+" function that not all functions have.

    > I hope that my arguments can change that 'serial' view

    > somewhat.

     The key word isn't "serial"; it's "explicit" versus "implicit". That

    code may have implicit parallelism that a smart compiler or programmer

    (or a dumb one) can find; but it doesn't make the parallelism

    explicit. The code is still written in a serial manner; there's one

    symbol, than the next, then the next, in a series of symbols. Compare

    your vector code above -- there's no defined way to read that

    serially. Even the dumbest compiler has to impose SOME order on it,

    and has to admit that the order is arbitrary.

     > - Robbert.

     -Billy

## John Cowan — 2006-11-15 21:06:42

    William Tanksley, Jr scripsit:

     > Hmm. "Operator" isn't a term the concatenative community uses. Perhaps

    > we should. How would you define it?

     I'd define it as "a word which does something other than pushing itself

    (or its corresponding value, depending on your ontology) on the stack",

    with the usual translation from talk of "the stack" to talk of

    tuple-valued functions, if you like.

    --

    Andrew Watt on Microsoft:                       John Cowan

    Never in the field of human computing           cowan@...

    has so much been paid by so many                http://www.ccil.org/~cowan

    to so few! (pace Winston Churchill)

## William Tanksley, Jr — 2006-11-16 01:20:14

    Robbert van Dalen <r_v_dalen@...> wrote:

     > I've just posted on my blog, which hopefully gives

    > some more food for thought.

    > http://my.opera.com/rapido/blog/

     It does indeed. I'm not sure what to think, though; this is very challenging.

    The idea he's presenting is called "sticky operators". Read his blog

    to see how he presents them.

    Although I think they look cool, there's a problem: they're hard to use.

    Suppose we have the two sticky functions " '1 '+ "; from what I can

    see, that sequence would increment all incoming data. Well, what does

    "incoming data" mean in a concatenative language? It can only mean the

    entire stack, right? This means that for normal programs, a function

    written using sticky functions can never be reused in a different

    context -- the sticky function will gum up everything on the stack.

    -Billy

## stevan apter — 2006-11-16 12:48:26

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Wednesday, November 15, 2006 3:54 PM

    Subject: Re: [stack] Parallel computing is concatenative

    > Robbert van Dalen <r_v_dalen@...> wrote:

    :

    > > May be you'll see it when you free your mind from

    > > stacks ;)

    > > But seriously, as Manfred has pointed out before me,

    > > Joy or any concatenative language doesn't need to be

    > > implemented on top of a stack.

    >

    > That's a possible claim. I've seen it made, and I've agreed with the

    > basic principle. The problem is that I've never seen any

    > counterexample for its denial. If I told you that "every concatenative

    > language is a stack language", how would you argue with me?

    by offering an algorithm (or general directions for constructing

    an algorithm) which translates concatenative programs into applicative

    functions.

    for example, consider P

        dup + swap pop *

    we can prove that P requires at least three items on the stack:

        .. x y z dup + swap pop *

        .. x y z a + swap pop *

        .. x y b swap pop *

        .. x b y pop *

        .. x b *

        .. c

    so we know that fP, the applicative function, takes three arguments:

        fP:{[x;y;z] .. }

    and returns c.

    the algorithm should produce a series of functions corresponding to

    tokens in P:

        f1:{[x;y;z]    f2[x;y;z;z]}

        f2:{[x;y;z;a]  f3[x;y;z+a]}

        f3:{[x;y;b]    f4[x;b;y]}

        f4:{[x;b;y]    f5[x;b]}

        f5:{[x;b]      x*b}

    so:

        fP:{[x;y;z]f1[x;y;z]}

    or:

        fP:f5 . f4 . f3 . f2 . f1 .

    where 'f .' maps the elements of an incoming sequence to the arguments

    of f.

    > Actually, take a look at the short name of this group, which appears

    > at the start of every message title.

    >

    > So although I very well understand the mathematical properties which

    > gave rise to our understanding of compositional concatenative

    > languages, I simply have no idea how they can be done without LIFO

    > semantics -- i.e. a stack.

    >

    > Oh, and even the fundamental mathematical property of function

    > composition is inherently serial.

    >

    > > > Now, I could imagine a simple dataflow graph

    > > > generator for a

    > > > concatenative language; such a thing would produce a

    > > > graph in linear

    > > > time (it takes longer to generate a dataflow for an

    > > > applicative

    > > > language), and then could parallelize the execution

    > > > of the graph.

    >

    > > Thanks for bringing up the dataflow argument! In fact,

    > > the ability to compile Enchilada into a dataflow

    > > runtime is/was one of the main design goals.

    >

    > That's very cool. I definitely do agree that automatic dataflow

    > annotations would make parallelism easy to see... But I don't see how

    > or why to make that part of the language.

    >

    > > (shameless plug: http://syrup.sourceforge.net/)

    >

    > That's COOL! Thanks!

    >

    > > Anyway, concatenative programs can be thought of

    > > serialized dataflow graphs (not quite but close).

    >

    > I don't see the "not quite" part -- that seems to me to be exactly

    > what they are.

    >

    > > Another nice example of the relationship between

    > > dataflow and concatenative languages is Slava's

    > > dataflow visualiser:

    > > http://factorcode.org/dataflow-ui.png

    >

    > That's something I'd like to see in an editor. I've often thought of

    > it, but I lack the GUI skill.

    >

    > > > But

    > > > again, there's nothing about the language that makes

    > > > this uniquely

    > > > possible or interesting, and especially there's

    > > > nothing about the

    > > > language that makes the programmer able to help with

    > > > what's going on.

    >

    > > Programmers would be helped a lot of they just scan

    > > for reducable operators ;)

    >

    > That's a great example of programmers helping themselves, yes. I would

    > call that a code review.

    >

    > > But yes, it is not a concatenative feature perse. The

    > > following infix expression would do just as well:

    > > (1 + 2) + (3 + 4)

    >

    > That makes sense to me.

    >

    > > > By the way, the ability to cut "anywhere" isn't

    > > > really a property of

    > > > concatenative languages (although I keep thinking it

    > > > _should_ be,

    > > > because it very nearly is); it's a property of

    > > > "flat" languages.

    > > > Concatenativity only promises that you can _join_

    > > > any two valid

    > > > programs to produce a third valid program.

    >

    > > I tend to disagree. I'm not sure, but I think you run

    > > into a serious contradiction when a language allows

    > > you to concatenate any valid program but not cut them.

    >

    > It's not a contadiction -- of course you must be able to cut where you

    > joined. The question is, can you cut ANYWHERE, and if not, what are

    > the restrictions on where you can cut? If you can't state the

    > restrictions, or if they're so strong that most places in most

    > programs can't be cut, the claim of being able to cut programs seems a

    > lot weaker than it should be.

    >

    > > But may be my idea of "flatness" is different from

    > > what has been discussed on the concatenative list

    > > previously. For instance, I think Joy is perfectly

    > > flat. For instance, this is a valid Joy program:

    >

    > Manfred created a dialect of Joy called "floy", a flat Joy, so he

    > doesn't think Joy is perfectly flat.

    >

    > > 1 2 + [3 4 +] i

    > > .. and when we cut it at a random point:

    > > 1 2 +

    > > [3 4 +] i

    >

    > That's not random enough :-). More accurately, there are 8 plausible

    > cut points in the sequence, and only 4 of them can be cut (assuming

    > you only try to cut between tokens, which seems right to me). If you

    > cut inside the quotation, the resulting two programs are not valid --

    > for example, "1 2 + [" is not a valid program in Joy.

    >

    > In Joy, that program is 50% flat.

    >

    > > now one would say that the cutting of [3 4 +] cannot

    > > be done and hence Joy is not flat. Syntactically that

    > > is a true statement, but semantically one could split

    > > a quotation without any problem:

    >

    > > [3] [4 +]

    >

    > But that's not semanticly the same, either -- that's not a split

    > quotation, but rather is two quotations. Even there, you've added two

    > syntactic things to the function that weren't there before.

    >

    > Flatness is a syntactic property. If it were semantic, EVERY

    > (Turing-complete) language would be flat, and it would be boring.

    >

    > > > Anyhow, the problem with cutting and rejoining is

    > > > that they are serial

    > > > operations -- in general, you must know the final

    > > > result of the first

    > > > section in order to begin computation on the second

    > > > section.

    >

    > > No, the cutting and joining of expressions isn't

    > > serial - that's an implementation detail. In Enchilada

    > > you can cut an expression of a million operands and

    > > operators non-serially in O(log(million)).

    >

    > The source code is serial; the cutting is serial. You may represent

    > the source code non-serially (perhaps as a dataflow graph), but that

    > doesn't change how the programmer sees it until you make that graph

    > the main language, at which point we're not really talking about a

    > concatenative language anymore.

    >

    > > > There are

    > > > specific exceptions, and there's plenty of stack

    > > > algebra you can do to

    > > > find them, but that's not something that

    > > > "concatenativity" buys you.

    >

    > > In Enchilada it is not an exception - but that's an

    > > implementation detail.

    >

    > I've seen Enchilada, and it definitely isn't flat. (I don't think it

    > should be; perfect flatness is a painful thing.)

    >

    > > > Enchilada, and array languages in general, are nice

    > > > and natural for

    > > > parallelism. I'd like to see much more work on array

    > > > concatenative

    > > > languages like X, XY, cK, Enchilada, and so on. By

    > > > people who

    > > > understand array languages well, of course (which

    > > > rules me out -- I

    > > > like 'em, I think I can read 'em, but I'm no

    > > > expert).

    >

    > > I'm no expert either. Such important stuff should be

    > > left to the popcorn lovers ;)

    >

    > I've mentioned K now... Perhaps we'll learn something about how array

    > languages do it...

    >

    > > > > What I'm after is *explicit* parallism in the most

    > > > > dense form. So one of the example programs I've

    > > > have

    > > > > given rewrote the following *implicit* parallel

    > > > vector

    > > > > program:

    > > > > [1;2;3;4] [7;8;9;10] add

    >

    > > > That looks to me like an explicitly parallel vector

    > > > program.

    >

    > > Under a certain interpretation, yes.

    >

    > Explicitness doesn't lend itself to interpretation.

    >

    > > > > into the following *explicit* parallel

    > > > concatenative

    > > > > program:

    > > > > 1 7 + 2 8 + + 3 9 +4 10 + + +

    > > > And that looks like a serially written program; the

    > > > parallelism is at

    > > > best implicit, and at that it's implicit because of

    > > > a property of the

    > > > "+" function that not all functions have.

    >

    > > I hope that my arguments can change that 'serial' view

    > > somewhat.

    >

    > The key word isn't "serial"; it's "explicit" versus "implicit". That

    > code may have implicit parallelism that a smart compiler or programmer

    > (or a dumb one) can find; but it doesn't make the parallelism

    > explicit. The code is still written in a serial manner; there's one

    > symbol, than the next, then the next, in a series of symbols. Compare

    > your vector code above -- there's no defined way to read that

    > serially. Even the dumbest compiler has to impose SOME order on it,

    > and has to admit that the order is arbitrary.

    >

    > > - Robbert.

    >

    > -Billy

    >

## Robbert van Dalen — 2006-11-16 13:05:44

    I think *now* I understand why my arguments have not

    made any sense:

    Enchilada does *not* use a stack model for the

    evaluation of expressions, but instead performs

    rewritings of expressions (similar to how a functional

    VM rewrites graphs). That's why I call evaluations ->

    reductions.

    So in Joy the following expression:

    + 2 3 + 4 5 +

    wouldn't reduce, as where in Enchilada it would:

    + 2 3 + 4 5 +

    + 2 3 + 9

    + 5 9

    Also, the re-writing '4 5 +' and '2 3 +' could be done

    in parallel.

    I'll define a toy concatenative (integer arithmetics)

    language to demonstrate how this can be done:

    syntax:

    Expression := Term*

    Term := Operand | Operator

    Operand := Number

    Operator := "+" | "*" | "/" | "-"

    Number := ["1"-"9"] ["0"-"9"]*

    auxilary functions/procedures:

    - boolean reducable(Expression e)

    - Expression reduce(Expression e)

    - Expression cat(Expression e1, Expression e2)

    - Pair cut(Expression e) (cuts the expression in two)

    - Expression left(Pair p)

    - Expression right(Pair p)

    examples:

    reducable(1 2 +) => true

    reduce(1 2 +) => 3

    split(1 2 + 3 4 +) => [1 2 +;3 4 +]

    left([1 2 +;3 4 +]) => 1 2 +

    right([1 2 +;3 4 +]) => 3 4 +

    now we can formulate the parallel reduction algorithm:

    reduce_p(Expression e)

    {

     if (reducable(e))

     {

     Pair s = e.cut();

     left_r = reduce_p(left(s));

     right_r = reduce_p(right(s));

     result = cat(left_r, right_r);

     return reduce(result);

     }

    }

    where the computation of left_r and right_r can be run

    in parallel.

    Now in Enchilada, reducable()is O(1) and cat() and

    split() are O(log(N). Next to that, no information is

    destroyed: everything expression is immutable and all

    operations are purely functional.

    So if we were to reduce the following enormous

    expression with one redex in the middle:

    1 2 3 ....... 4999999 5000000 + ..... 9999999

    that would cost us O(log(n)*log(n)) time (if my

    calculations are correct)

    Also, the following 'dataflow' expression can be

    processed in parallel like this:

    1 2 3 4 5 6 7 8 '+ '+ '+

    1 2 3 4 5 6 '+ 15 '+ '+

    1 2 3 4 '+ 11 15 '+ '+

    1 2 '+ 7 '+ 26 '+

    '+ 3 7 '+ 26 '+

    '+ '+ 10 26 '+

    '+ '+ '+ 36

    Now a final question to you: would you call this toy

    language flat?

    I would call it flat, because I consider every pure

    arithmetical postfix expression (without variables) to

    be flat. But with your definition of flatness we

    should also be allowed to cut numbers, right?

    But cutting numbers makes no sense to me, ie.

    reduce(12 + -) => 12 + -

    ie. doesn't reduce, but:

    cut(12 + -) => [1 2; + -] ?

    left(cut) => 1 2

    right(cut) => + -

    reduce(cat(left,right)) => 1 2 + - => 3 => _3

    reduces.

    - Robbert

    --- "William Tanksley, Jr" <wtanksleyjr@...>

    wrote:

     > Robbert van Dalen <r_v_dalen@...> wrote:

    > > I've just posted on my blog, which hopefully gives

    > > some more food for thought.

    > > http://my.opera.com/rapido/blog/

    >

    > It does indeed. I'm not sure what to think, though;

    > this is very challenging.

    >

    > The idea he's presenting is called "sticky

    > operators". Read his blog

    > to see how he presents them.

    >

    > Although I think they look cool, there's a problem:

    > they're hard to use.

    >

    > Suppose we have the two sticky functions " '1 '+ ";

    > from what I can

    > see, that sequence would increment all incoming

    > data. Well, what does

    > "incoming data" mean in a concatenative language? It

    > can only mean the

    > entire stack, right? This means that for normal

    > programs, a function

    > written using sticky functions can never be reused

    > in a different

    > context -- the sticky function will gum up

    > everything on the stack.

    >

    > -Billy

    >

## Robbert van Dalen — 2006-11-16 13:26:58

    My last post contained some typos:

    syntax:

    Expression := Term*

    Term := Operand | Operator

    Operand := Number

    Operator := "+" | "*" | "/" | "-"

    Number := ["1"-"9"] ["0"-"9"]*

    auxilary functions/procedures:

    - boolean reducable(Expression e)

    - Expression reduce(Expression e)

    - Expression cat(Expression e1, Expression e2)

    - Pair cut(Expression e) (cuts the expression in two)

    - Expression left(Pair p)

    - Expression right(Pair p)

    examples:

    reducable(1 2 +) => true

    reduce(1 2 +) => 3

    cut(1 2 + 3 4 +) => [1 2 +;3 4 +]

    left([1 2 +;3 4 +]) => 1 2 +

    right([1 2 +;3 4 +]) => 3 4 +

    the parallel reduction algorithm:

    reduce_p(Expression e)

    {

     if (reducable(e))

     {

      Pair s = cut(e);

      left_r = reduce_p(left(s));

      right_r = reduce_p(right(s));

      result = cat(left_r, right_r);

      return reduce(result);

     }

    }

## William Tanksley, Jr — 2006-11-16 14:29:14

    stevan apter <sa@...> wrote:

     > > > But seriously, as Manfred has pointed out before me,

    > > > Joy or any concatenative language doesn't need to be

    > > > implemented on top of a stack.

    > > That's a possible claim. I've seen it made, and I've agreed with the

    > > basic principle. The problem is that I've never seen any

    > > counterexample for its denial. If I told you that "every concatenative

    > > language is a stack language", how would you argue with me?

    > by offering an algorithm (or general directions for constructing

    > an algorithm) which translates concatenative programs into applicative

    > functions.

     Okay, I see what he meant. I misunderstood, and he's right. Yes, you

    can easily translate into applicative continuation-passing style,

    removing thereby *all* need for a stack in the underlying

    implementation.

    I was thinking (incorrectly) that he meant that some other semantics

    is possible aside from LIFO when executing concatenated functions.

    We've speculated that there might be some type of data object aside

    from a LIFO stack that could form the basis of a concatenative

    language, but nobody's been able to come up with one. (Yes, we know

    there are auxillary structures aside from the data stack, but the

    stack is still there.)

    -Billy

## William Tanksley, Jr — 2006-11-16 15:11:08

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

     > Enchilada does *not* use a stack model for the

    > evaluation of expressions, but instead performs

    > rewritings of expressions (similar to how a functional

    > VM rewrites graphs). That's why I call evaluations ->

    > reductions.

     No, I can see that's what you're doing... But you still have a model.

    I'm interested to hear if your model isn't a stack model, though.

    Intriguing.

     > So in Joy the following expression:

    > + 2 3 + 4 5 +

    > wouldn't reduce, as where in Enchilada it would:

    > + 2 3 + 4 5 +

    > + 2 3 + 9

    > + 5 9

     Well, in Joy no expression "reduces" as part of the language; they

    either execute or they don't. That expression would execute with no

    problem in Joy, and the result would be equivalent to executing the

    expression you got after reduction.

     > I'll define a toy concatenative (integer arithmetics)

    > language to demonstrate how this can be done:

    > Now in Enchilada, reducable()is O(1)

     How do you determine reducible() without looking at least at every

    token, i.e. O(n)? My gut feeling is that it's an O(n*log(n)) problem,

    since I'd expect to have to keep a lookup table.

     > and cat() and split() are O(log(N).

     Obviously you're preloading the source into a tree of some kind.

     > Next to that, no information is

    > destroyed: everything expression is immutable and all

    > operations are purely functional.

     Right.

     > So if we were to reduce the following enormous

    > expression with one redex in the middle:

    > 1 2 3 ....... 4999999 5000000 + ..... 9999999

    > that would cost us O(log(n)*log(n)) time (if my

    > calculations are correct)

     *I see* now why you said that (a long time) before.

     > Also, the following 'dataflow' expression can be

    > processed in parallel like this:

    > 1 2 3 4 5 6 7 8 '+ '+ '+

    > 1 2 3 4 5 6 '+ 15 '+ '+

    > 1 2 3 4 '+ 11 15 '+ '+

    > 1 2 '+ 7 '+ 26 '+

    > '+ 3 7 '+ 26 '+

    > '+ '+ 10 26 '+

    > '+ '+ '+ 36

     That's no problem; it certainly makes sense to do textual

    transformations when possible. And of course, with your engine, it's

    natural to do so. But when do the sticky operators *stop* sticking?

    It's easy to show with a "toy" problem like that one, but in a real

    program with functions calling other functions, do the sticky

    operators act on all the results of a called function?

      1 2 3 somefunction '+

    You can't just commute somefunction and '+. What do you do?

    Also, what if someotherfunction has a '+ inside of it (suppose that's

    ALL it is). What is the result of

      1 2 3 someotherfunction

    ?

     > Now a final question to you: would you call this toy

    > language flat?

     It's not complex enough to be flat -- there's no syntax for function

    definition. If all you can do is write a single expression, there's no

    way to split that expression into two (the language can't handle the

    concept of "two expressions").

    Aside from that, it's flat.

     > I would call it flat, because I consider every pure

    > arithmetical postfix expression (without variables) to

    > be flat.

     You also have to be without quotations or other groupings. But yes.

     > But with your definition of flatness we

    > should also be allowed to cut numbers, right?

    > But cutting numbers makes no sense to me, ie.

     It makes no sense to me either -- I specifically stated that you

    should cut only on the boundaries between tokens (lexemes). A number

    is a single token and can't be interpreted otherwise.

    It's imaginable to make a language which has only two possible tokens,

    and which therefore could be expressed as a fully cuttable bitstream.

    I don't know what that language would look like. The corresponding

    applicative language is Jot and Iota, and neither one is flat. I tried

    to make a similar concatenative language and failed, but I'm working

    out a new approach.

     > - Robbert

     -Billy

## stevan apter — 2006-11-16 21:06:34

    but now, having read robbert's post in which he describes

    his rewriting algorithm, i think i was wrong, or at least

    over-hasty.

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Thursday, November 16, 2006 9:29 AM

    Subject: Re: [stack] Parallel computing is concatenative

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

    > > > > But seriously, as Manfred has pointed out before me,

    > > > > Joy or any concatenative language doesn't need to be

    > > > > implemented on top of a stack.

    > > > That's a possible claim. I've seen it made, and I've agreed with the

    > > > basic principle. The problem is that I've never seen any

    > > > counterexample for its denial. If I told you that "every concatenative

    > > > language is a stack language", how would you argue with me?

    >

    > > by offering an algorithm (or general directions for constructing

    > > an algorithm) which translates concatenative programs into applicative

    > > functions.

    >

    > Okay, I see what he meant. I misunderstood, and he's right. Yes, you

    > can easily translate into applicative continuation-passing style,

    > removing thereby *all* need for a stack in the underlying

    > implementation.

    >

    > I was thinking (incorrectly) that he meant that some other semantics

    > is possible aside from LIFO when executing concatenated functions.

    > We've speculated that there might be some type of data object aside

    > from a LIFO stack that could form the basis of a concatenative

    > language, but nobody's been able to come up with one. (Yes, we know

    > there are auxillary structures aside from the data stack, but the

    > stack is still there.)

    >

    > -Billy

    >

## Manfred Von Thun — 2006-11-17 07:19:39

    It occurred to me that mathematicians have been using another

    concatenative notation that deserves to be looked at.

    Let x y z be numbers (or variables standing for numbers)

    Let f g h be unary functions on numbers

       (such as successor, square, negative ..)

    Consider the expression "xyz", normally taken to

    be the product of the three numbers, with the binary

    multiplication symbol suppressed. This is done quite

    often, and only addition is written with an explicit

    symbol. So this is x * y * z

    Consider "fxy", the result of applying f to the

    product of two numbers. So this is f(x * y).

    Or "fgx" , the result of applying f to the result

    of applying g to x. This is f(g(x)), or the

    result of applying the composition f.g to x.

    Or "xfy", the result of multiplying x by the

    result of applying f to y. This is x * f(y).

    But what about "xyf" ? this looks like a function

    that is still in need of an argument. Similarly

    "xfg" and "fgh" are functions in need of an argument.

    But if the last three still need an argument, why

    don't the earlier ones?

    Answer: they all need an argument, and it is always

    implicit, and that argument is just the number one

    (1), the identity element for multiplication. Each

    of the expressions "x", "y", "xy" "xyz" denote

    unary functions which take one argument and return

    one value. "x" is denotes the unary function which

    multiplies its argument by the number x. The

    concatenation "xy" denotes a unary function which

    is the composition of the functions denoted by

    its parts, this unary function multiplies its

    argument by the product x*y. Other concatenations

    like "fg" also denote the compositions of the

    functions denoted by their parts.

    The upshot of all this: each of "x" "y" "z"

    "f" "g" "h" denotes a unary function from

    numbers to numbers, and the concatenation of any

    two or more denotes the function which is the

    composition of the functions denoted by the parts.

    Sound familiar? Of course. Its like concatenative

    languages operating on a stack, possibly of several

    variables. Here numerals "42" do no mean a number

    but the operation "push 42", a unary function from

    stacks to stacks, and the stack is initially empty.

    In the multiplicative language we operate on a single

    number. Here numerals "42" do not mean a number

    but the operation of "multiply by 42", a unary

    function from numbers to numbers, and the initial

    number is the number one, (1).

    Of course this is not restricted to plain old

    integers, reals or complex numbers. You could have

    matrices instead, or the weirdest gizmos mathematicians

    could invent. You just need a notion of multiplication

    (not necessarily commutative), but I think it has

    to be a multiplication with an identity element -

    in other words a monoid. The functions of a

    concatenative language do not have to operate on a

    stack.

    But, you say, a stack that is always just of size one

    is still a stack, isn't it? Well, yes, OK. But the

    difference lies in what a single numeral "42" denotes:

    a number, as in ordinary notation? Or a push operation

    as in concatenative stack languages? Or a multiplication

    by that number, as in the concatenative product language?

    I think the last two are both concatenative, but in a

    different way: one has its unary functions operate on stacks,

    the other has is unary functions operate on numbers or

    other creatures.

      - Manfred

## Robbert van Dalen — 2006-11-17 14:11:24

    >

    >> So in Joy the following expression:

    >> + 2 3 + 4 5 +

    >> wouldn't reduce, as where in Enchilada it would:

    >> + 2 3 + 4 5 +

    >> + 2 3 + 9

    >> + 5 9

    >

    > Well, in Joy no expression "reduces" as part of the language; they

    > either execute or they don't. That expression would execute with no

    > problem in Joy, and the result would be equivalent to executing the

    > expression you got after reduction.

     When I execute '+ 2 3 + 4 5 +' in Joy I get the following error:

    'run time error: two parameters needed for +'

     >

    >> I'll define a toy concatenative (integer arithmetics)

    >> language to demonstrate how this can be done:

    >

    >> Now in Enchilada, reducable()is O(1)

    >

    > How do you determine reducible() without looking at least at every

    > token, i.e. O(n)? My gut feeling is that it's an O(n*log(n)) problem,

    > since I'd expect to have to keep a lookup table.

    >

     I use a balanced binary tree that has a flag 'reducible' at each node.

    So I just have to query the top parent node.

     >> and cat() and split() are O(log(N).

    >

    > Obviously you're preloading the source into a tree of some kind.

    >

     Yes. But 'the source' could also be generated at runtime, for

    instance by manipulating Joy quotations:

    [1 2 +] dup dup cat cat cat i =>

    [1 2 +] [1 2 +] [1 2 +] cat cat cat i =>

    [1 2 + 1 2 + 1 2 +] i

    3 3 3

     >

    >> Next to that, no information is

    >> destroyed: everything expression is immutable and all

    >> operations are purely functional.

    >

    > Right.

    >

    >> So if we were to reduce the following enormous

    >> expression with one redex in the middle:

    >> 1 2 3 ....... 4999999 5000000 + ..... 9999999

    >> that would cost us O(log(n)*log(n)) time (if my

    >> calculations are correct)

    >

    > *I see* now why you said that (a long time) before.

    >

    >> Also, the following 'dataflow' expression can be

    >> processed in parallel like this:

    >

    >> 1 2 3 4 5 6 7 8 '+ '+ '+

    >> 1 2 3 4 5 6 '+ 15 '+ '+

    >> 1 2 3 4 '+ 11 15 '+ '+

    >> 1 2 '+ 7 '+ 26 '+

    >> '+ 3 7 '+ 26 '+

    >> '+ '+ 10 26 '+

    >> '+ '+ '+ 36

    >

    > That's no problem; it certainly makes sense to do textual

    > transformations when possible. And of course, with your engine, it's

    > natural to do so. But when do the sticky operators *stop* sticking?

    > It's easy to show with a "toy" problem like that one, but in a real

    > program with functions calling other functions, do the sticky

    > operators act on all the results of a called function?

    >

    >   1 2 3 somefunction '+

    >

    > You can't just commute somefunction and '+. What do you do?

     Enchilada has no functions, only monadic or dyadic operators. So

    let's say somefunction is an monadic operator (neg), then we get:

    1 2 3 somefunction '+

    1 2 3 neg '+

    1 2 _3 '+

    1 '+ _1

     >

    > Also, what if someotherfunction has a '+ inside of it (suppose that's

    > ALL it is). What is the result of

    >

    >   1 2 3 someotherfunction

     rephased in Enchilada terms:

    1 2 3 ['+] lft

    1 2 3 '+

    1 '+ 5

     >

    >> But with your definition of flatness we

    >> should also be allowed to cut numbers, right?

    >> But cutting numbers makes no sense to me, ie.

    >

    > It makes no sense to me either -- I specifically stated that you

    > should cut only on the boundaries between tokens (lexemes). A number

    > is a single token and can't be interpreted otherwise.

    >

     OK, I forgot about the lexical rule: my wrong.

     > It's imaginable to make a language which has only two possible tokens,

    > and which therefore could be expressed as a fully cuttable bitstream.

    > I don't know what that language would look like. The corresponding

    > applicative language is Jot and Iota, and neither one is flat. I tried

    > to make a similar concatenative language and failed, but I'm working

    > out a new approach.

     That would be a very interesting and fundamental result.

    Could you tell us something more about your new approach?

     >

    >> - Robbert

    >

    > -Billy

## William Tanksley, Jr — 2006-11-17 16:06:21

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

     > >> So in Joy the following expression:

    > >> + 2 3 + 4 5 +

    > >> wouldn't reduce, as where in Enchilada it would:

    > >> + 2 3 + 4 5 +

    > >> + 2 3 + 9

    > >> + 5 9

    > > Well, in Joy no expression "reduces" as part of the language; they

    > > either execute or they don't. That expression would execute with no

    > > problem in Joy, and the result would be equivalent to executing the

    > > expression you got after reduction.

    > When I execute '+ 2 3 + 4 5 +' in Joy I get the following error:

    > 'run time error: two parameters needed for +'

     Execution isn't the same thing as reduction. Joy can define and use a

    function whose body is '+ 2 3 + 4 5 +', but its execution will be

    stack-dependant. Enchilada's made for reduction, which is one of the

    reasons it's so interesting.

     > >> I'll define a toy concatenative (integer arithmetics)

    > >> language to demonstrate how this can be done:

    > >> Now in Enchilada, reducable()is O(1)

    > > How do you determine reducible() without looking at least at every

    > > token, i.e. O(n)? My gut feeling is that it's an O(n*log(n)) problem,

    > > since I'd expect to have to keep a lookup table.

    > I use a balanced binary tree that has a flag 'reducible' at each node.

    > So I just have to query the top parent node.

     Yup, and a balanced tree is n*log n, so I was right :-). But yes,

    caching the results is a great idea. Very nice.

     > >> and cat() and split() are O(log(N).

    > > Obviously you're preloading the source into a tree of some kind.

    > Yes. But 'the source' could also be generated at runtime, for

    > instance by manipulating Joy quotations:

    > [1 2 +] dup dup cat cat cat i =>

    > [1 2 +] [1 2 +] [1 2 +] cat cat cat i =>

    > [1 2 + 1 2 + 1 2 +] i

    > 3 3 3

     Oh, sure -- and you can generate the tree at runtime too. No problem.

    Many languages parse into a tree; your tree is semantic rather than

    syntactic. Great idea.

    I have a question. In Enchilada turing-complete? I know you can do

    arbitrary loops; can you also do recursions?

     > >> Also, the following 'dataflow' expression can be

    > >> processed in parallel like this:

    > >> 1 2 3 4 5 6 7 8 '+ '+ '+

    > >> 1 2 3 4 5 6 '+ 15 '+ '+

    > >> 1 2 3 4 '+ 11 15 '+ '+

    > >> 1 2 '+ 7 '+ 26 '+

    > >> '+ 3 7 '+ 26 '+

    > >> '+ '+ 10 26 '+

    > >> '+ '+ '+ 36

    > > That's no problem; it certainly makes sense to do textual

    > > transformations when possible. And of course, with your engine, it's

    > > natural to do so. But when do the sticky operators *stop* sticking?

    > > It's easy to show with a "toy" problem like that one, but in a real

    > > program with functions calling other functions, do the sticky

    > > operators act on all the results of a called function?

    > >   1 2 3 somefunction '+

    > > You can't just commute somefunction and '+. What do you do?

    > Enchilada has no functions, only monadic or dyadic operators.

     Oh! But Enchilada does have quotations, which serve as functions.

     > So

    > let's say somefunction is an monadic operator (neg), then we get:

    > 1 2 3 somefunction '+

    > 1 2 3 neg '+

    > 1 2 _3 '+

    > 1 '+ _1

     Let me put it another way -- what happens when '+ runs up against a

    non-reducible operand?

     > > Also, what if someotherfunction has a '+ inside of it (suppose that's

    > > ALL it is). What is the result of

    > >   1 2 3 someotherfunction

    > rephased in Enchilada terms:

    > 1 2 3 ['+] lft

    > 1 2 3 '+

    > 1 '+ 5

     Okay -- it seems clear to me that the textual transformation is

    equivalent to the operational behavior of:

    1. Executing up to the actual location of '+.

    2. Breaking the stack up into adjacent pairs.

    3. Replacing each pair with its sum.

    4. If the number of items on the stack was odd, place the '+ token on

    the stack above the odd remaining item.

    So a possible whole-stack effect picture would be:

    '* ( a b c d e -- a '* bc de )

    In a general, software engineering sense, it doesn't seem very useful.

    In a computer science/language theory sense, it's kind of nice because

    it gives you a smooth and predictable way to commute certain

    operators. Understanding that can only possibly increase our

    understanding of concatenative languages, which will help all of us.

     > > It's imaginable to make a language which has only two possible tokens,

    > > and which therefore could be expressed as a fully cuttable bitstream.

    > > I don't know what that language would look like. The corresponding

    > > applicative language is Jot and Iota, and neither one is flat. I tried

    > > to make a similar concatenative language and failed, but I'm working

    > > out a new approach.

    > That would be a very interesting and fundamental result.

    > Could you tell us something more about your new approach?

     Yes: it failed too. :-)

    My problem is that I'm too uneducated.

    I'm trying to use Kerby's http://tunes.org/~iepos/joy.html brief

    exploration of concatenative combinators to design a combinator set

    which does not _also_ require the reams of quotations that his

    combinators require. Such a language would be purely concatenative and

    purely flat, both by the strictest definitions I could give -- after

    all, in a sense the quotation syntax [] is an applicative function

    q(x), which returns x quoted into a list.

    I started with his {cake,k} base, and tried to express some things in

    it -- but I found that even the simple result [] was unattainable. I

    realized that I'd need quoted forms of cake and k, so I tried the base

    {cake,k,[cake],[k]}. Again, [] wasn't evidently attainable, and it's

    needed for many fundamental expressions. I could try

    {cake,k,[cake],[k],[]}, but now it's getting clear that something's

    missing... The applicative quotation operator q() is secretly very

    important to the so-called concatenative combinator theory.

    My ingenuity and knowledge is hitting its limits... I don't know

    enough about combinator theory to work anything out here.

    I'm getting some ideas about combinators that, in addition to having a

    pattern effect as we're used to, also return a constant value which

    happens to be some other quoted combinator. In that way all the

    combinators can be generated onto the stack, where they can be

    captured into a pattern by a later combinator. But I don't know how to

    determine whether such a combinator "base" is actually complete, so

    I'm not eager to go to the work to construct one that merely looks

    complete to me.

    Does anyone have any ideas?

    My ultimate goal is to build a flat bitstring encoding for a friend of

    mine who's researching genetic algorithms. Flatness, as you can

    imagine, would be a huge benefit to a genetic algorithm encoding -- it

    really would be nice to be able to cut a gene at any site.

    -Billy

## William Tanksley, Jr — 2006-11-17 18:24:13

    Manfred Von Thun <m.vonthun@...> wrote:

     > It occurred to me that mathematicians have been using another

    > concatenative notation that deserves to be looked at.

     I haven't seen any uses of that notation, except in Herstein, in which

    case it's written the other way around (i.e. f(x) is written xf). One

    problem with the notation is that the operations of multiplication and

    function applications are very different in their algebraic

    properties. (Herstein gets away with it because he only uses it for

    functions, so multiplication is not a concern.)

     > could invent. You just need a notion of multiplication

    > (not necessarily commutative), but I think it has

    > to be a multiplication with an identity element -

    > in other words a monoid. The functions of a

    > concatenative language do not have to operate on a

    > stack.

     I think you may be right here -- you've shown, I believe, that the

    words of a concatenative language must form a monoid under

    concatenation, so implicit multiplication is therefore concatenative.

    That means that functions defined in terms of the same operations can

    freely be substituted for the operations themselves.

    Okay, then; we know that numeric multiplication, matrix

    multiplication, and function composition where the functions take a

    stack to return a stack are all concatenative. Numbers aren't very

    powerful; matrices are reasonably powerful; function composition is

    Turing-complete. What else is there? Is there some monoid more

    computationally powerful than matrices but more amenible to textual

    analysis than function composition?

    Hmm. Another statement of the same question: we know that regular

    expressions are concatenative (they're usually defined that way). We

    also know that recursively enumerable languages are concatenative

    (since f(stack)->stack composition can compute anything a Turing

    machine can). Are there any concatenatively computable languages in

    between those two? Might it be possible to build a concatenative

    language that can accept only context-free languages?

    This, by the way, is the first time I realized that the usual way to

    express regular expressions is an impurely concatenative language

    (impure because it has a grouping operator).

    More and more example of concatenative languages that do NOT require

    the functions on stacks! Wonderful! Sometimes it's pleasant to be

    proven wrong, and I'm enjoying this one.

     >   - Manfred

     -Billy

## Robbert van Dalen — 2006-11-17 19:12:14

    >

    >> I use a balanced binary tree that has a flag 'reducible' at each

    >> node.

    >> So I just have to query the top parent node.

    >

    > Yup, and a balanced tree is n*log n, so I was right :-). But yes,

    > caching the results is a great idea. Very nice.

     The only difficult thing is to keep the tree balanced. Now the whole

    Enchilada thing started with having a very efficient balanced tree

    data structure in the first place.

    That's why unary numbers didn't scare me - they can be implemented

    rather efficiently on top of balanced binary trees.

     >

    > Oh, sure -- and you can generate the tree at runtime too. No problem.

    > Many languages parse into a tree; your tree is semantic rather than

    > syntactic. Great idea.

    >

    > I have a question. In Enchilada turing-complete? I know you can do

    > arbitrary loops; can you also do recursions?

     Yes, I'm sure it's Turing complete. And Enchilada doesn't need the do/

    while operator to be Turing complete.

    See: http://my.opera.com/rapido/blog/2006-10-11-dowhilesolution

     >

    >> Enchilada has no functions, only monadic or dyadic operators.

    >

    > Oh! But Enchilada does have quotations, which serve as functions.

    >

     Right.

     >

    > Let me put it another way -- what happens when '+ runs up against a

    > non-reducible operand?

    >

     Let me rephrase the reduction rules to answer your question:

    1) scan for an operator

    2) is it monadic?

      2.1) is the element left to the monadic operator, not an operator?

      2.2) reduce.

    3) it's dyadic

      3.1) are the two elements left to the dyadic operator, not operators?

      3.2) reduce.

    '+ is an operator (albeith sticky)

    so:

    * '+

    doesn't reduce because of 3.1

    1 '+

    doesn't reduce, again because of 3.1

    2 1 '+

    '+ 3

    reduces, but doesn't destroy '+. Alternatively:

    2 1 +

    3

    reduces, but destroys +

     >

    > Okay -- it seems clear to me that the textual transformation is

    > equivalent to the operational behavior of:

    >

    > 1. Executing up to the actual location of '+.

    > 2. Breaking the stack up into adjacent pairs.

    > 3. Replacing each pair with its sum.

    > 4. If the number of items on the stack was odd, place the '+ token on

    > the stack above the odd remaining item.

     Replace 1. with 1) and I think everything turns out to have much

    simpler semantics.

     >

    > So a possible whole-stack effect picture would be:

    >

    > '* ( a b c d e -- a '* bc de )

    >

    > In a general, software engineering sense, it doesn't seem very useful.

    > In a computer science/language theory sense, it's kind of nice because

    > it gives you a smooth and predictable way to commute certain

    > operators. Understanding that can only possibly increase our

    > understanding of concatenative languages, which will help all of us.

     Can you elaborate on your notation?  It's rather alien to me.

     >

    >>> It's imaginable to make a language which has only two possible

    >>> tokens,

    >>> and which therefore could be expressed as a fully cuttable

    >>> bitstream.

    >>> I don't know what that language would look like. The corresponding

    >>> applicative language is Jot and Iota, and neither one is flat. I

    >>> tried

    >>> to make a similar concatenative language and failed, but I'm working

    >>> out a new approach.

    >

    >> That would be a very interesting and fundamental result.

    >> Could you tell us something more about your new approach?

    >

    > Yes: it failed too. :-)

    >

    > My problem is that I'm too uneducated.

     Never mind that. Education never taught me to appreciate fresh and

    new ideas (mostly boring and obvious ones).

     >

    > I'm trying to use Kerby's http://tunes.org/~iepos/joy.html brief

    > exploration of concatenative combinators to design a combinator set

    > which does not _also_ require the reams of quotations that his

    > combinators require. Such a language would be purely concatenative and

    > purely flat, both by the strictest definitions I could give -- after

    > all, in a sense the quotation syntax [] is an applicative function

    > q(x), which returns x quoted into a list.

     You are very strict, indeed!

    And your observation that quotations are essentially applicative is

    very interesting. I tend to agree but I'm not sure why.

     >

    > I started with his {cake,k} base, and tried to express some things in

    > it -- but I found that even the simple result [] was unattainable. I

    > realized that I'd need quoted forms of cake and k, so I tried the base

    > {cake,k,[cake],[k]}. Again, [] wasn't evidently attainable, and it's

    > needed for many fundamental expressions. I could try

    > {cake,k,[cake],[k],[]}, but now it's getting clear that something's

    > missing... The applicative quotation operator q() is secretly very

    > important to the so-called concatenative combinator theory.

     It's a very hidden secret not know to many ;)

    So 'how to get rid of q() without losing Turing completeness?' is the

    challenge that you meet?

     >

    > My ingenuity and knowledge is hitting its limits... I don't know

    > enough about combinator theory to work anything out here.

     I would say, don't restrict yourself - let your thoughts and

    ingenuity not be hampered by any theories.

     >

    > I'm getting some ideas about combinators that, in addition to having a

    > pattern effect as we're used to, also return a constant value which

    > happens to be some other quoted combinator. In that way all the

    > combinators can be generated onto the stack, where they can be

    > captured into a pattern by a later combinator. But I don't know how to

    > determine whether such a combinator "base" is actually complete, so

    > I'm not eager to go to the work to construct one that merely looks

    > complete to me.

     Please show us the work. Then may be someone on the list can

    determine if your base is complete.

     >

    > Does anyone have any ideas?

     Your ideas surely deserve another post, different from this 'parallel

    computing is concatenative' post.

     >

    > My ultimate goal is to build a flat bitstring encoding for a friend of

    > mine who's researching genetic algorithms. Flatness, as you can

    > imagine, would be a huge benefit to a genetic algorithm encoding -- it

    > really would be nice to be able to cut a gene at any site.

     Yes. But  there is a difference between genotype (the program) and

    phenotype (the result). Moreover, DNA is not encoded in a binary form

    so we shouldn't restrict ourselves to that.

    But I do think that pure flatness would blend the concepts of

    genotype and phenotype in very interesting ways.

     >

    > -Billy

     - Robbert

## janvanlent — 2006-11-19 12:50:50

    --- In concatenative@yahoogroups.com, "William Tanksley, Jr"

    <wtanksleyjr@...> wrote:

     > > > It's imaginable to make a language which has only two possible

     tokens,

     > > > and which therefore could be expressed as a fully cuttable

     bitstream.

     > > > I don't know what that language would look like. The corresponding

    > > > applicative language is Jot and Iota, and neither one is flat. I

     tried

     > > > to make a similar concatenative language and failed, but I'm working

    > > > out a new approach.

    >

    > > That would be a very interesting and fundamental result.

    > > Could you tell us something more about your new approach?

    >

    > Yes: it failed too. :-)

    >

    > My problem is that I'm too uneducated.

    >

    > I'm trying to use Kerby's http://tunes.org/~iepos/joy.html brief

    > exploration of concatenative combinators to design a combinator set

    > which does not _also_ require the reams of quotations that his

    > combinators require. Such a language would be purely concatenative and

    > purely flat, both by the strictest definitions I could give -- after

    > all, in a sense the quotation syntax [] is an applicative function

    > q(x), which returns x quoted into a list.

    >

    > I started with his {cake,k} base, and tried to express some things in

    > it -- but I found that even the simple result [] was unattainable. I

    > realized that I'd need quoted forms of cake and k, so I tried the base

    > {cake,k,[cake],[k]}. Again, [] wasn't evidently attainable, and it's

    > needed for many fundamental expressions. I could try

    > {cake,k,[cake],[k],[]}, but now it's getting clear that something's

    > missing... The applicative quotation operator q() is secretly very

    > important to the so-called concatenative combinator theory.

    >

    > My ingenuity and knowledge is hitting its limits... I don't know

    > enough about combinator theory to work anything out here.

    >

    > I'm getting some ideas about combinators that, in addition to having a

    > pattern effect as we're used to, also return a constant value which

    > happens to be some other quoted combinator. In that way all the

    > combinators can be generated onto the stack, where they can be

    > captured into a pattern by a later combinator. But I don't know how to

    > determine whether such a combinator "base" is actually complete, so

    > I'm not eager to go to the work to construct one that merely looks

    > complete to me.

    >

    > Does anyone have any ideas?

     You could have a look at the following papers by Chris Okasaki. His

    book has been mentioned on this list before, I'm surprised these haven't.

    Flattening Combinators: Surviving Without Parentheses by Chris

    Okasaki. Journal of Functional Programming, 13(4):815-822, July 2003.

    http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp03

    Techniques for Embedding Postfix Languages in Haskell by Chris

    Okasaki. Haskell Workshop, October 2002, pages 105-113.

    http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#hw02

    The embedding of a postfix language in Haskell could also be of

    interest to people studying type inference of postfix languages.

     > My ultimate goal is to build a flat bitstring encoding for a friend of

    > mine who's researching genetic algorithms. Flatness, as you can

    > imagine, would be a huge benefit to a genetic algorithm encoding -- it

    > really would be nice to be able to cut a gene at any site.

     You might be interested in the work of Lee Spector.

    http://hampshire.edu/lspector/push.html

    From

    http://hampshire.edu/lspector/push3-description.html

    "Push achieves its combination of syntactic simplicity and semantic

    power through the use of a stack-based execution architecture that

    includes a stack for each data type. A CODE data type, with its own

    stack and an associated set of code-manipulation instructions,

    provides many of the more interesting features of the language. Push

    instructions, like instructions in all stack-based languages, take any

    arguments that they require and leave any results that they produce on

    data stacks. To provide for "stack safe" execution of arbitrary code

    Push adopts the convention, used widely in stack-based genetic

    programming, that instructions requiring arguments that are not

    available (because the relevant stacks are empty) become NOOPs; that

    is, they do nothing. Because Push's stacks are typed, instructions

    will always receive arguments and produce results of the appropriate

    types (if they do anything at all), regardless of the contexts in

    which they occur."

    There has been other work on genetic programming using stack based

    languages or other "linear" program representations, but I don't have

    any references at hand.

     > -Billy

     jan

## stevan apter — 2006-11-19 19:47:46

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

    From: "janvanlent" <jan.vanlent+concatenative@...>

        You could have a look at the following papers by Chris Okasaki. His

        book has been mentioned on this list before, I'm surprised these haven't.

        Flattening Combinators: Surviving Without Parentheses by Chris

        Okasaki. Journal of Functional Programming, 13(4):815-822, July 2003.

        http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp03

    this is a wonderful paper - thanks!

## William Tanksley, Jr — 2006-11-21 19:21:40

    janvanlent <jan.vanlent+concatenative@...> wrote:

     > You could have a look at the following papers by Chris Okasaki. His

    > book has been mentioned on this list before, I'm surprised these haven't.

    > Flattening Combinators: Surviving Without Parentheses by Chris

    > Okasaki. Journal of Functional Programming, 13(4):815-822, July 2003.

    > http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp03

     Wow. That answers all my questions. Well, I don't understand what the

    X combinator does, but why after all should I expect to :-).

    A complete, TWO word, concatenative language. Perfect. And a

    reasonably clear explanation, too! Thank you.

     > You might be interested in the work of Lee Spector.

    > http://hampshire.edu/lspector/push.html

     I'd seen it a long time ago, but I'm glad you found it -- my friend

    should find it more immediately useful. I've seen some other work in

    Forthlike program evolution -- the advantages have seemed obvious to

    others as well.

     > jan

     -Billy

## Manfred Von Thun — 2006-11-28 08:01:45

    I have been trying to make a more methodical search for

    possible concatenative languages. Here is what I have

    come up with so far.

    First, define ³concatenative²:

    A functional language is concatenative iff

    the concatenation PQ of two programs P and

    Q denotes the composition of the functions

    denoted by the two programs.

    Let T and U be two types (not necessarily

    distinct), and let t1 t2 t3 .. be literals of type T.

    (We might also need u1 u2 u3 .. literals of type U,

    but probably not.)

    Both T and U might themselves be complex

    unions of simpler types, but this will not be important.

    In what follows, let f,g,h be unary functions

    taking an argument of type U and producing

    a value of type U:

        f ,g,h..   :  U ->  U

    These functions will of course depend very

    much on the nature of the type U.

    I am now looking for a general method for

    constructing further functions like these,

    by using literals of type T and just one

    binary function b which takes a T and a U

    as arguments and produces a U as value:

        b  :  T * U  ->  U

    Here follow several examples where U

    is ³container of type T² for various kinds

    of containers, and where b is an operation

    of putting an element of type T into a

    container U:

    1. U = stack/list-of-T, and b = push/cons

            push  :  T * stack-of-T   ->  stack-of-T

            cons  :  T * list-of-T  ->  list-of-T

      Assume S : stack-of-T, then

            push(t1, S)  =  S with new element t1

      Now turn the literal t1 into a unary operator

      and write  S t1  in postfix order. So t1 is

      now a unary operator on stacks.

      This is just our familiar stack notation. We

      can also have pop dup swap, and other

      unary operators + - * / on stacks which

      depend on the type T.

      Needless to say, we start with an empty stack

      which is the implicit initial operand.

      Instead of stacks we could have queues,

      or double-ended-queues (³deque²), and then

      the postfix operators t1 could operate on

      either end of the deque.

      2.  U = set-of-T, and b = insert

           insert  :  T * set-of-T  ->  set of T

      Assume S : Set-of-T, then

           insert(t1, S) = S augmented with

              new member t1 (if t1 was not a

              member already).

           In set notation,

           insert(t1, S)  = {t1} union S

    Now turn the literal t1 into a unary operator

    and write S t1 in postfix order. So t1 is

    now a unary operator on sets.

    We start with an empty set which is the implicit

    initial operand.

    Since sets are unordered, we cannot have pop dup

    and swap, so there is no way of describing

    which of the elements are to be affected.

    However, if the type T has an ordering

    (as for example numbers have), then we can

    always pick out the smallest or the largest

    and remove that. But that does not remove

    the most recently added element. I cannot

    see how sets could be useful as the basis of

    a concatenative programming language.

      3. The container  type bag-of-T is less

          well known than stack/list-of-T or

          set-of-T. Bags are somewhat in between:

          they are like lists but not ordered,

          and like sets but allow repetitions.

          U = bag-of-T, and b = add-another

          add-another  :  T * bag-of-T  ->  bag-of-T

          Assume B : bag-of-T, then

          add-another(t1, B) = B with one more t1.

          For example:

          add-another(3, {2 2 2 3 5 5}) = {2 2 2 3 3 5 5}

    Now turn literal t1 into a unary operator

    and write B t1 in postfix order. So t1 is now a unary

    operator on bags.

    The implicit initial operand has to be the empty bag.

    Again, since bags are unordered, we cannot have pop

    dup and swap, but if T has an ordering, we could

    have remove operations as for sets. Also, since

    each element in the bag has a ³multiplicity², we

    can operate on those.

    Useful as a basis for a language? Marginally more

    interesting than sets, but not too promising.

    Other container types are possible, in particular

    trees of various sorts, or lists-of-lists-of-T or even

    arbitrarily deep nesting of lists. I¹ll take just one

    example:

        4. U = stack-of-stack-of-T, and b is the

            operation of pushing t1 onto the top

            stack S on the stack of stacks SS

    Now turn t1 into a unary postfix operator as before.

    We can now have pop, dup, swap as usual, and also

    the usual + - * and so on, but now operating on the

    top stack S of the stack-of-stacks SS. In addition we can

    now have operations POP, DUP, SWAP operating on

    the stack-of-stacks SS. Useful? maybe.

    Much of this can already be done in Joy with the

    infra combinator, though in a round-about-way.

    I now turn to cases where U is not a container type.

    My main examples have U and T the same type.

        5.  T = U = numbers (natural, integer, real ..)

             b = multiplication

    As before, assume that we have  unary

    functions f,g,h  but now we use binary multiplication

    to create unary operators on numbers. The implicit

    initial operand has to be the number 1. Then

        2 5 f 8 4

    means: multiply by 2, then by 5, then take the f,

    then multiply by 8 then by 4. If f is the unary squaring

    function, then this evaluates to the function which

    which multiplies by 3200, and using the double-speak

    that we concatenators barely notice, ³it evaluates

    to 3200².

    This is of some interest if the numbers are naturals.

    Then any multiplication by anything greater than 1

    leaves its trace in the factors of the number. For

    example

        6 10  =>  60

    which is (2 * 2 * 3 * 5), and these prime factors

    are preserved by any multiplication by 1 or greater.

    An interestingly, any natural number can be seen

    a bag of its prime factors. There is some relation

    to Goedel numbering that might deserve closer

    examination.

        6. T = U = numbers,

            b = addition/exponentiation/whatnot

    Addition would take 0 as the initial implicit operand,

    but I cannot see any use. Maybe there are other

    binary operators worth exploring as a basis for

    concatenative languages.

        7. T = U = strings/lists/sequences-of-type-X

            (take X to be characters, for example)

            b = concatenation of strings (of characters)

    Take the nullstring ³² to be the initial implicit

    operand, and take t1, t2 to be strings, which

    now denote a unary operation ³append t1²

    Thus ³peter ³  is the unary operation of appending

    that string to an operand string. Then

        ³pe²  ³ter li²  ³kes do²  ³gs²   =>   ³peter likes dogs²

    Unlike a stack language the result string does not

    say how it was constructed, but at least we can

    do  dup swap pop to the result string, operating just

    on the last few characters.

    If T and U are sequences of something more

    interesting than characters, say numbers, then

    essentially we end up with a stack language

    in which pushes are not of single items but of

    sequences of items. Barely anything dramatically new.

        8. T = U = sets of strings = languages.

            e.g. English = { ..., ³He runs², ... }

                   French = { ..., ³Elle mange², ...}

            b = concatenation of languages, all

                  those strings formed by taking a member

                  of one concatenated with a member of

                  another:

            English French = { ..., ³He runsElle mange²,...}

    Sounds crazy, but we use it all the time in regular

    expressions and in grammars.

    Initial implicit operand is the one element language

    consisting of just the nullstring ³². Now a t1 such as

    English is the unary operation of concatenating

    every string in the argument with every string in English.

    A less preposterous example:

    L1 =     a | b | c  = the language {³a², ³b², ³c²}

    L2 =     d | e       = the language {³d², ³e²}

    L1 L2 = their concatennation:

                {³ad² , ³bd², ³cd², ³ae², ³be², ³ce²}

    Since sets do not allow any sensible dup swap pop,

    as mentioned earlier, nothing much doing here.

    BUT: since the elements of the sets are sequences,

    we can do dup swap pop on these sequences:

    L1 L2 dup =

              {³add², ³bdd², ³cdd², ³aee², ³bee², ³cee²}

    Furthermore, if the sequences are not character strings,

    but sequences of numbers, then all sorts of other

    unary operations become possible, i.e. unary

    operations on sets of sequences of numbers -

    or other whatnots.

    I must go.

      - Manfred

    Well, I¹ll leave the discussion to another day or to

    somebody else.

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

## Manfred Von Thun — 2006-12-07 08:45:31

    Ever wondered what factorial(20000) might be?

    [Yes, that was twenty-thousand]

    A big number, and it has over 77000 digits.

    You need a bignum cruncher for that, and the

    unix utility dc (Desk Calculator) is just the right thing for that.

    I had known about it for many years, and also that it is

    probably the oldest concatenative language, but never had any

    need to use it. But recently I did need something for bignums,

    so I looked at it with more care.

    It has numbers that are pushed onto the stack, the usual

    arithmetic operators, a few stack shufflers,

    some fancy stuff to do with input and output bases

    and with precision. Whatever is on the stack

    can also be stored in one of the 256 registers, or loaded

    back from a register to the main stack.

    * Chris Diggins, note: the meaning of store and load in dc

    * is the opposite of what you have on your ³primitives² table.

    * You might search the literature to see which is most common.

    You can also put strings on the stack, store in and load from

    registers, print them, and execute them as programs.

    Strings are written like [hello world], but the usual

    string operations like concatenation, extracting or deleting

    parts, are not available. Strings are really meant as programs.

    The interesting thing is that as programs they can contain

    other strings (which would make no sense in other languages).

    The string [11 22 33] when executed will push the three

    numbers, leaving 33 topmost. The string [11 22 [33 44]]

    when executed will push two numbers, 11 and 22,

    and then push the string [33 44] on top of that. The

    string [33 44] might then be executed in turn.

    There are no lists in dc, but using these program strings

    one can mimic some list operations. Consider the

    string [11 [22 [33 [44 [55]]]]]. Like the previous examples

    these look just like Joy lists or quotations. But as lists

    in Joy the last example is different from [11 22 33 44 55].

    There is also an interesting connection between these

    two forms of Joy lists and the two Lisp notations:

    (11 22 33 44 55) as a Lisp list is just shorthand for

    (11 . (22 . (33 . (44 . (55 . ())))))), where the dot

    is the (infix) operator ³cons², separating the left

    ³car²-part and the right ³cdr²-part. But the two

    notations mean exactly the same in Lisp.

    However, in Joy the two lists [11 22 33 44 55]

    and [11 [22 [33 [44 [55]]]]] do not mean the same

    at all. The first is the usual notation for lists, and the

    second I have never really used. Looking at dc made

    me wonder whether perhaps one should.

    Joy:   [11 [22 [33 [44 [55]]]]] i   ==

             [11 [22 [33 [44 [55]]]]] uncons

    dc:    [11 [22 [33 [44 [55]]]]] x       # x = i in Joy

    The three programs above (two Joy, one dc) all

    do exactly the same to the stack.  We can repeat the

    i or uncons in Joy or the x in dc a further 4 times

    to end up with all the five numbers on the stack. This is the

    closest I can come to an kind of list manipulation in dc.

    There seems to be no way of constructing lists

    by concatenation or cons.

    As an aside, let us ask what

    happens when what we have inside all those brackets

    are not just numbers but other program fragments,

    i.e. of the form [A [B [C [D [E]]]]], where A..E are

    literals or operators (and even combinators, which

    can in fact be defined in dc as well as in Joy).

    For example

           [1 2 [+ [dup [dup * [*]]]]]           # Joy

           [1 2 [+ [d    [d     * [*]]]]]           # dc

    By doing 5 times i in Joy, or 5 times x in dc, we

    should be left with 27 on top of the stack. But

    we can also do it in steps:

           x  ..  x  ..  x  ..  x  ..  x

    where at the four points .. something else is done,

    most likely with dip somewhere below the remaining

    quotation. What uses this has in Joy I do not know.

    The dc utility also allows the 256 registers to be

    used as stacks, with shifts between the main stack

    and the register stacks. I have not explored this

    at all. Obviously this is the way to implement a

    dip combinator, using one of these register stacks

    in the manner of the Forth return stack. But there

    is no way of putting a register stack on top of the

    main stack, or vice versa. So all these stacks cannot

    do duty for lists.

    Since strings can be stored in the registers, they

    are the right sort of place for definitions. I wrote

    my (recursive) factorial function as a 10 or 12

    character dc string, stored of course in register f.

    The Gnu extension of dc also allows the registers

    or the register stacks to hold arrays. I have not

    explored this at all.

    I hope that some of you will look at dc, the

    grandfather of all concatenative languages. Maybe

    you will find something stimulating for your

    own concatenative languages.

      - Manfred

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

## William Tanksley, Jr — 2006-12-09 00:54:25

    Manfred Von Thun <m.vonthun@...> wrote:

     > I hope that some of you will look at dc, the

    > grandfather of all concatenative languages. Maybe

    > you will find something stimulating for your

    > own concatenative languages.

     The first Forth was written in 1958 (by Chuck Moore). dc was written

    in the B language on a PDP-7, so it couldn't have been written before

    the late 1960s. So Forth is still older.

    The two share no common ancestry, of course. (Obviously.) There's no

    common grandfather yet... convergent evolution? :-)

     >   - Manfred

     -Billy

## Christopher Diggins — 2006-12-09 18:44:25

    > * Chris Diggins, note: the meaning of store and load in dc

    > * is the opposite of what you have on your ³primitives² table.

    > * You might search the literature to see which is most common.

     Thanks for pointing that out to me Manfred!

    - Christopher

## Manfred Von Thun — 2006-12-12 05:16:09

    On 7/12/06 7:45 PM, "Manfred Von Thun" <m.vonthun@...> wrote:

    [..]

    OOOPS  -  a little error:

    in the 7-th line below, replace the ³uncons² by ³uncons first².

    > However, in Joy the two lists [11 22 33 44 55]

    > and [11 [22 [33 [44 [55]]]]] do not mean the same

    > at all. The first is the usual notation for lists, and the

    > second I have never really used. Looking at dc made

    > me wonder whether perhaps one should.

    >

    > Joy:   [11 [22 [33 [44 [55]]]]] i   ==

    >  [11 [22 [33 [44 [55]]]]] uncons

    >

    > dc:    [11 [22 [33 [44 [55]]]]] x       # x = i in Joy

    >

    > The three programs above (two Joy, one dc) all

    > do exactly the same to the stack.

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