# RE: [stack] Generalising shuffle strings [Was: Pattern matching, stack comments]

## Tanksley, William D. Jr. — 2004-05-03 17:27:55

    From: phimvt@... [mailto:phimvt@...]

     >But consider the following generalisation of shuffle strings.

     Shuffle strings are interesting because they provide a clear, simple way to

    write stack manipulations; essentially, they replace the arbitrary names

    such as "dup" and "pop" or "drop" with pictographs that follow a simple

    rule. Stevan's generalization to also handle arrays meets with the spirit of

    shuffle strings.

     >In other words, the right hand side can be any Joy program.

     This extends shuffle strings so far that they cease entirely to be useful as

    shuffle strings. Before they were just new names for atomic stack reordering

    operations; now they are turing-complete.

    I disagree entirely with the common desire to add lambda notation to

    concatenative languages. Shuffle strings relieve some of the pressure to do

    that, by making stack notation a little more approachable, so I like shuffle

    strings (although I prefer them embedded in the language syntax and

    optimized by the compiler).

     >  - Manfred

     -Billy

## sa@dfa.com — 2004-05-03 17:45:12

    manfred's 'let' extension corresponds to my 'lambda' combinator.

    i've adopted his notational suggestion and replaced '--' with ':'.

    i don't entirely agree with billy about lambdas (read: variables).

    that is, i agree that lambdas are a blot on the purity of concatenative

    languages, but i have found that starting with lambdas, and then

    either eliminating themaltogether, or replacing them with shuffle-

    strings and more code, is an efficient implementation strategy.

    analogously, although it is possible to code directly in unlambda,

    it makes more sense to compose in the lambda calculus, then replace

    lambdas with combinators.

    "Tanksley, William D. Jr." <TanksleyJrW@...> wrote on 05/03/2004

    01:27:55 PM:

     > From: phimvt@... [mailto:phimvt@...]

    > >But consider the following generalisation of shuffle strings.

    >

    > Shuffle strings are interesting because they provide a clear, simple way

     to

     > write stack manipulations; essentially, they replace the arbitrary names

    > such as "dup" and "pop" or "drop" with pictographs that follow a simple

    > rule. Stevan's generalization to also handle arrays meets with the spirit

     of

     > shuffle strings.

    >

    > >In other words, the right hand side can be any Joy program.

    >

    > This extends shuffle strings so far that they cease entirely to be useful

     as

     > shuffle strings. Before they were just new names for atomic stack

     reordering

     > operations; now they are turing-complete.

    >

    > I disagree entirely with the common desire to add lambda notation to

    > concatenative languages. Shuffle strings relieve some of the pressure to

     do

     > that, by making stack notation a little more approachable, so I like

     shuffle

     > strings (although I prefer them embedded in the language syntax and

    > optimized by the compiler).

    >

    > >  - Manfred

    >

    > -Billy

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

## Don Groves — 2004-05-03 18:26:52

    Hello all,

    I'm new to Joy (I do know Forth).  To me, Joy combinators

    and lambda expressions seem to be semantically the same thing.

    In [1 2 3] [dup *] map for example, [dup *] is an anonymous

    function, fulfilling exactly the same purpose in Joy as

    does (lambda (x) x*x) in Lisp.  The difference is merely one

    of syntax.  Is this a reasonable view or am I mixed up?

    --

    Don

     On Mon, 3 May 2004 13:45:12 -0400, <sa@...> wrote:

    > manfred's 'let' extension corresponds to my 'lambda' combinator.

    >

    > i've adopted his notational suggestion and replaced '--' with ':'.

    >

    > i don't entirely agree with billy about lambdas (read: variables).

    > that is, i agree that lambdas are a blot on the purity of concatenative

    > languages, but i have found that starting with lambdas, and then

    > either eliminating themaltogether, or replacing them with shuffle-

    > strings and more code, is an efficient implementation strategy.

    >

    > analogously, although it is possible to code directly in unlambda,

    > it makes more sense to compose in the lambda calculus, then replace

    > lambdas with combinators.

    >

    >

    > "Tanksley, William D. Jr." <TanksleyJrW@...> wrote on 05/03/2004

    > 01:27:55 PM:

    >

    >> From: phimvt@... [mailto:phimvt@...]

    >> >But consider the following generalisation of shuffle strings.

    >>

    >> Shuffle strings are interesting because they provide a clear, simple way

    > to

    >> write stack manipulations; essentially, they replace the arbitrary names

    >> such as "dup" and "pop" or "drop" with pictographs that follow a simple

    >> rule. Stevan's generalization to also handle arrays meets with the spirit

    > of

    >> shuffle strings.

    >>

    >> >In other words, the right hand side can be any Joy program.

    >>

    >> This extends shuffle strings so far that they cease entirely to be useful

    > as

    >> shuffle strings. Before they were just new names for atomic stack

    > reordering

    >> operations; now they are turing-complete.

    >>

    >> I disagree entirely with the common desire to add lambda notation to

    >> concatenative languages. Shuffle strings relieve some of the pressure to

    > do

    >> that, by making stack notation a little more approachable, so I like

    > shuffle

    >> strings (although I prefer them embedded in the language syntax and

    >> optimized by the compiler).

    >>

    >> >  - Manfred

    >>

    >> -Billy

    >>

    >>

    >>

    >> Yahoo! Groups Links

    >>

    >>

    >>

    >>

    >>

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

## Tanksley, William D. Jr. — 2004-05-03 18:37:53

    From: sa@... [mailto:sa@...]

     >manfred's 'let' extension corresponds to my 'lambda' combinator.

     Correct; I don't disagree with the presence of a feature, such as a lambda

    combinator. I will tend to focus on teaching people how to work without

    using it, though; it may seem handy, but it's fundamentally NOT part of the

    language, and will block learning of the language itself.

    This is especially bad within a language like Joy, which is intended to show

    off concatenative notions.

     >i've adopted his notational suggestion and replaced '--' with ':'.

     No problem :-). I prefer the double dashes, largely because they're

    traditional notation; but that's no reason to keep them.

     >i don't entirely agree with billy about lambdas (read:

    >variables).

     I, of course, can't accept this. :-) ;-)

     >that is, i agree that lambdas are a blot on the

    >purity of concatenative languages, but i have found that

    >starting with lambdas, and then either eliminating

    >themaltogether, or replacing them with shuffle- strings and

    >more code, is an efficient implementation strategy.

     Yes, it is, for someone who isn't familiar with concatenative notation but

    how is familiar with computation theory. There's nothing wrong with that,

    and you can learn a lot by doing it. Unfortunately, one of the lessons

    you'll learn is that compilers have to do a LOT of work to translate lambda

    code into dataflow, and when you write programs this way, YOU are doing that

    work by hand. Think about it -- is that the lesson you want to teach

    potential new cK programmers? That in order to code in cK, you have to not

    only understand stack notation, but also lambda notation, dataflow

    optimization, and stack rewriting, and be willing to do all the work that

    the compiler does for all the other languages?

    And then there are people who /don't/ know lambda theory. It's likely that

    most Forth programmers are engineers who don't do any real programming (it's

    common belief, although I haven't seen any surveys or anything); the

    language is certainly highly accessible to them. Such people would have a

    doubly hard time learning a language presented in this way; they'd have to

    learn not only the math and theory, but also TWO notations, lambda and

    concatenative.

    My experience and belief is that writing concatenative programs is easier

    than writing lambda programs, and yields insight about the process and data

    in your algorithm that's otherwise hidden. I think the work to learn

    concatenativity natively is worthwhile.

    It's analogous to learning a foreign language; to become fluent you have to

    stop thinking in your native language and start thinking in the foreign one.

    You can't think in Greek if the word "naus" means "boat" to you; the word

    "naus" must mean a boat, not an English word surrounded by double quotes.

    You can't think concatenatively if the phrase "2 +" means "(lambda x (+ 2

    x))" to you.

     >analogously, although it is possible to code directly in

    >unlambda, it makes more sense to compose in the lambda

    >calculus, then replace lambdas with combinators.

     Unlambda is a toy language, though; there are better languages built around

    the same basic concept. For example, J. Although I know you prefer K (as do

    I), you have to admit that J proves that it's possible and rather elegant to

    code applicatively without variables. And J wasn't even REALLY designed to

    be used without variables; its dataflow features are halfhearted.

    -Billy

## sa@dfa.com — 2004-05-03 19:21:54

    "Tanksley, William D. Jr." <TanksleyJrW@...> wrote on 05/03/2004

    02:37:53 PM:

    [:]

     >

    > My experience and belief is that writing concatenative programs is easier

    > than writing lambda programs, and yields insight about the process and

     data

     > in your algorithm that's otherwise hidden. I think the work to learn

    > concatenativity natively is worthwhile.

     i would very much like to know whether this is true in general.  based on

    my experience, which is substantially less than yours, i'd have to say that

    the jury is still out.  while manfred's many examples are useful, the

    problem is that he's such a good joy programmer that it's hard to tell

    whether an extra cerebral lobe is required to function at that level.

## Tanksley, William D. Jr. — 2004-05-03 19:42:30

    From: sa@... [mailto:sa@...]

     >"Tanksley, William D. Jr." <TanksleyJrW@...> wrote:

    >>My experience and belief is that writing concatenative programs is

    >>easier than writing lambda programs, and yields insight about the

    >>process and data

    >>in your algorithm that's otherwise hidden. I think the work to learn

    >>concatenativity natively is worthwhile.

    >i would very much like to know whether this is true in

    >general.

     I made at least 3 unsupported claims in that paragraph -- which one would

    you like to have substantiated?

     1. writing concatenative programs is easier than writing lambda programs

     2. writing concatenative programs yields insight about the process and data

    in your algorithm that's otherwise hidden

     3. the work required to learn concatenativity natively is worthwhile

    Sorry, I should be more careful at backing up what I say, but I'm lazy and

    would rather wait until someone calls me out. And even then, I'll hide

    behind ambiguity to delay answering a reasonable question.

    :-)

    Seriously, though, #1 is perhaps the least justifiable; writing

    concatenative programs is clearly /sometimes/ easier and sometimes harder,

    but it's not clear whether either notation has any specific or general

    advantage. Even when used as a mathematical notation both have their

    advantages. I could weaken #1 to say "writing concatenative programs is

    about as easy as writing applicative programs", and I think I could defend

    that in a general sense.

    #2 I can justify easily, since concatenative notation explicitly reveals the

    priority of the data to the algorithm; at every point in the algorithm you

    can determine the order of the data on the stack, and the stuff near the top

    is more important than the stuff nearer the bottom. Lambda notation hides

    the data in variables, which "magically" teleport the data to where it's

    needed and then disappear until the next time they're needed.

    #3 I gave the most support for in my original post, but it certainly needs

    more discussion before I could expect anyone to believe it.

    -Billy

## sa@dfa.com — 2004-05-03 20:05:51

    "Tanksley, William D. Jr." <TanksleyJrW@...> wrote on 05/03/2004

    03:42:30 PM:

     > From: sa@... [mailto:sa@...]

    > >"Tanksley, William D. Jr." <TanksleyJrW@...> wrote:

    > >>My experience and belief is that writing concatenative programs is

    > >>easier than writing lambda programs, and yields insight about the

    > >>process and data

    > >>in your algorithm that's otherwise hidden. I think the work to learn

    > >>concatenativity natively is worthwhile.

    >

    > >i would very much like to know whether this is true in

    > >general.

    >

    > I made at least 3 unsupported claims in that paragraph -- which one would

    > you like to have substantiated?

    >

    >  1. writing concatenative programs is easier than writing lambda programs

    >  2. writing concatenative programs yields insight about the process and

     data

     > in your algorithm that's otherwise hidden

    >  3. the work required to learn concatenativity natively is worthwhile

     2 imples 3.  and i suppose one could argue that over the course of time,

    the accumulation of insights into computation makes writing programs

    easier.

    so perhaps 2 imples 1 as well.

     >

    > Sorry, I should be more careful at backing up what I say, but I'm lazy

     and

     > would rather wait until someone calls me out. And even then, I'll hide

    > behind ambiguity to delay answering a reasonable question.

     have you considered politics as a profession?  :)

     >

    > :-)

    >

    > Seriously, though, #1 is perhaps the least justifiable; writing

    > concatenative programs is clearly /sometimes/ easier and sometimes

     harder,

     > but it's not clear whether either notation has any specific or general

    > advantage. Even when used as a mathematical notation both have their

    > advantages. I could weaken #1 to say "writing concatenative programs is

    > about as easy as writing applicative programs", and I think I could

     defend

     > that in a general sense.

     easy/hard is misleading - the question is whether, or to what extent,

    the language gets in the way of seeing solutions to some problems, and

    assists with others.

     >

    > #2 I can justify easily, since concatenative notation explicitly reveals

     the

     > priority of the data to the algorithm; at every point in the algorithm

     you

     > can determine the order of the data on the stack, and the stuff near the

     top

     > is more important than the stuff nearer the bottom. Lambda notation hides

    > the data in variables, which "magically" teleport the data to where it's

    > needed and then disappear until the next time they're needed.

     perhaps that's a good thing?  but really, that's the heart of the matter.

    is it true that "the stuff near the top is more important than the stuff

    nearer the bottom"?  is it trivially true, in that if the program has been

    designed well, and written correctly, then the data it wants is

    (?magically?)

    near the top of the stack?

     >

    > #3 I gave the most support for in my original post, but it certainly

     needs

     > more discussion before I could expect anyone to believe it.

    >

    > -Billy

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

## Nick Forde — 2004-05-05 14:17:45

    I've read with interest the recent discussions on shuffle strings and

    pattern matching as I've been toying with a Joy extension which allows

    a mix of applicative and concatenative styles. I have found that often

    when writing Joy functions with > 1 argument a significant percentage

    of my code ends up being stack manipulation, even with careful

    design. This is probably largely because I'm not a good Joy programmer

    but I find this is particularly true when using the more complex

    recursive combinators. In other cases I find very little stack

    manipulation is required and the concatenative notation provides the

    most elegant solution.

    To tackle this I've been experimenting with the addition of immutable

    stack references in function definitions. For example, in Manfred's

    "Nested Recursion" paper the Ackermann function example is defined in

    pseudo code as:

    ack(m, n) =

        IF m = 0  THEN n + 1

        ELSEIF n = 0  THEN ack(m - 1, 1)

        ELSE ack(m - 1, ack(m, n - 1))

    In Joy this can be written:

    r-ack ==

        [ [ [pop null] popd succ ]

          [ [null] pop pred 1 r-ack ]

          [ [dup pred swap] dip pred r-ack r-ack ]

        ] cond.

    By adding lexically scoped stack references and automatically popping

    the arguments off the evaluation stack this could be written:

    r2-ack(m n) ==

        [ [ [m null] n succ ]

          [ [n null] m pred 1 r-ack ]

          [ m pred m n pred r2-ack r2-ack ]

        ] cond.

    Although both implementations are very similar I find the intention of

    the latter clearer. In a similar way the condnestrec implementation

    of the same function could also be rewritten:

    cnr-ack ==

        [ [ [pop null] [popd succ] ]

          [ [null]  [pop pred 1]  [] ]

          [ [[dup pred swap] dip pred] [] [] ]

        ] condnestrec.

    arg-ack(m n) ==

        [ [ [m null] [n succ] ]

          [ [n null] [m pred 1] [] ]

    	  [ [m pred m n pred] [] [] ]

        ] condnestrec.

    Although more compelling examples could be constructed to illustrate the

    benefits of the applicative vs. concatenative styles I like the idea

    of being able to combine the two.

    As Billy has already observed use of stack references like the above

    make compilation much harder but I believe that in an interpreter the

    performance could be comparable, at the cost of some additional memory

    overhead.

    Regards,

    Nick.

## Tanksley, William D. Jr. — 2004-05-05 15:24:50

    From: Nick Forde [mailto:nickf@...]

     >As Billy has already observed use of stack references like the

    >above make compilation much harder but I believe that in an

    >interpreter the performance could be comparable, at the cost

    >of some additional memory overhead.

     Is there some particular reason to use stack references (which are very hard

    to manage and make stack use impossible) rather than local variables (which

    are well-understood and easy to manage, although they do add a specific

    overhead to calls)?

    I'm not saying I like either one :-), just that I don't understand your

    choice.

     >Nick.

     -Billy

## Nick Forde — 2004-05-05 15:35:33

    Tanksley, William D. Jr. writes:

      > From: Nick Forde [mailto:nickf@...]

     > >As Billy has already observed use of stack references like the

     > >above make compilation much harder but I believe that in an

     > >interpreter the performance could be comparable, at the cost

     > >of some additional memory overhead.

     >

     > Is there some particular reason to use stack references (which are very hard

     > to manage and make stack use impossible) rather than local variables (which

     > are well-understood and easy to manage, although they do add a specific

     > overhead to calls)?

     Sorry, my choice of terminology was confusing. I'm really talking

    about immutable local variables since each function begins by popping

    its arguments off the evaluation stack they are no longer acessible

    except through the local variable references.

    Nick.

## Tanksley, William D. Jr. — 2004-05-05 16:08:10

    From: Nick Forde [mailto:nickf@...]

     >Sorry, my choice of terminology was confusing. I'm really

    >talking about immutable local variables since each function

    >begins by popping its arguments off the evaluation stack they

    >are no longer acessible except through the local variable references.

     Sorry for being a bit obtuse :-). I thought you really were talking about

    stack references.

    I don't think they're hard to compile; all you need to do is create a stack

    frame and load the locals into it, and pop the stack frame at the end of the

    function. If you do this, mutable locals are just as easy to justify as

    immutable ones.

    Having locals available is a good thing when your problem includes some

    functions for which concatenative notation really isn't the best solution.

    So I can't argue against languages including it. And if programmers will

    have to judge when locals are needed and when they're not, I can't argue

    against this group discussing them in order to build a groundwork for making

    that decision.

    I'm just uncomfortable with what I see a lot, where the decision is made by

    and for people who simply don't know concatenative notation, and the

    language used implies that concatenative notation is difficult and inferior.

    Of course, the error can go two ways. I've seen otherwise skilled Forth

    programmers hate locals so much that they wind up using globals.

    I'd like to develop some guidelines for determining when locals/lambdas

    really are objectively "better" for implementing a design. I'd also like to

    think about when it's worthwhile to change your design in order to avoid

    locals. Answering those two questions would allow a complete answer to

    Stevan Apter's recent post, since lambdas are really the fundamental

    difference between concatenative languages and applicative ones.

    (Of course, extra points for concatenative languages, since they easily

    allow both! :-)

     >Nick.

     -Billy

## Tanksley, William D. Jr. — 2004-05-07 15:25:02

    From: phimvt@... [mailto:phimvt@...]

     >Some of the recent discussion prompts me to clarify the

    >difference between the (LET-like) generalisation and lambda

    >abstractions.

     There need be no distinction; the only difference is that lambdas are quoted

    and lets are not. Both would be the same (or at most, lambdas would be

    syntactic sugar for the quotation of a let) in a language that offered

    quotation independantly from enlistment.

    Since this (the separation of quotation from enlistment) has been my number

    two fixation throughout the history of this list, I thought I'd bring that

    up. :-)

    For any who might be new here, I'm referring to the fact that building a

    list and quoting things are two distinct operations, but Joy offers no way

    to quote things aside from making a list containing them. What Joy calls a

    "quotation" other languages might call a "quoted list".

     >This does not quite mix well with definitions, where one might

    >have expected

    >    DEFINE  foo(a b)  ==  foo-body.

    >to be equivalent to

    >    DEFINE  foo  ==  LAMBDA a b IN foo-body ENDLAMBDA.

    >when in fact it would be equivalent to

    >    DEFINE  foo  ==  LET a b IN foo-body ENDLET.

     That's because DEFINE quotes its body, so the lambda itself winds up being

    quoted (leaving the contents of the lambda double-quoted). If define were to

    execute its body, the lambda (or a quoted list) would be the appropriate way

    to define things.

    uqDEFINE foo == LAMBDA a b IN a b + ENDLAMBDA.

    uqDEFINE foo == [+].

     >  - Manfred

     -Billy

## Tanksley, William D. Jr. — 2004-05-07 17:10:33

    From: Don Groves [mailto:dgroves@...]

     >Hello all,

    >I'm new to Joy (I do know Forth).  To me, Joy combinators

    >and lambda expressions seem to be semantically the same thing.

     You're thinking of Joy quotations, not combinators. Close; combinators are

    functions that take quotations as arguments.

     >In [1 2 3] [dup *] map for example, [dup *] is an anonymous

    >function, fulfilling exactly the same purpose in Joy as does

    >(lambda (x) x*x) in Lisp.  The difference is merely one of

    >syntax.  Is this a reasonable view or am I mixed up?

     That's reasonable -- in concatenative notation, quotations replace lambdas.

    However, to call them equivalent is to miss the crucial point that although

    they're the same in purpose, they're very different in execution.

    In a lambda, the syntax of the language is different from what it is outside

    of the lambda: it's modified by the change in meaning of several symbols (in

    your above example, "x*x" does something different than it would do outside

    of the lambda). In a quotation, the syntax of the language is the same as it

    was outside of the quotation; there are no new or redefined symbols.

    In a lambda, values get transmitted from one location to another invisibly,

    and destroyed just as invisibly. In a quotation, values must explicitly flow

    under operations that don't use them or into operations that do; there's no

    point at which the exact location of a value is unknown.

    In order to call a lambda, the language must secretly arrange its parameters

    into the order and location expected by the lambda's compiler. This almost

    always involves copying, and is always hidden from the programmer. Very good

    compilers attempt to minimise this copying, but because all of them do it

    differently no programmer can code with those optimizations in mind, and no

    compiler can rely on another compiler's optimizations. In order to call a

    quotation, the programmer must arrange the data in order in which the

    quotation uses it, so there's an incentive to arrange operations in a way so

    that the data falls naturally in the right position without copying or

    swapping.

    I could go on, but now I'm getting into the realm of the discussion I'm

    having with Stevan Apter, so I'll continue providing more differences in

    that post.

    Let me comment, though, that I've phrased all the above comparisons in favor

    of quotations and against lambdas. I could just as easily phrase things the

    other way around; lambdas have advantages too. Stevan and I will be

    discussing this more carefully and fairly in a while. For now, please try to

    ignore my bias and accept this message as pointing out differences between

    lambdas and Joy quotations, not as trying to argue that Joy quotations are

    better than lambdas. I do believe that they are; but this message doesn't

    attempt to properly justify that belief.

     >Don

     -Billy

## Don Groves — 2004-05-08 04:15:44

    Billy,

    Thanks for the explanation. I realized soon after sending

    that I'd confused the terms 'combinator' and 'quotation'.

    In my brief experience with Joy (which I hope someday will

    be much greater), I too feel that quotations are 'better'

    than lambdas, they seem so much more direct and simpler.

    I guess my remaining question at this point is: when would

    one want to use a lambda given that quotations are available.

    I'll continue to follow this thread with interest.

    --

    Don

    ------------------------------------------------------------

     On Fri, 7 May 2004 10:10:33 -0700, Tanksley, William D. Jr. <wtanksleyjr@...> wrote:

    > From: Don Groves [mailto:dgroves@...]

    >> Hello all,

    >> I'm new to Joy (I do know Forth).  To me, Joy combinators

    >> and lambda expressions seem to be semantically the same thing.

    >

    > You're thinking of Joy quotations, not combinators. Close; combinators are

    > functions that take quotations as arguments.

    >

    >> In [1 2 3] [dup *] map for example, [dup *] is an anonymous

    >> function, fulfilling exactly the same purpose in Joy as does

    >> (lambda (x) x*x) in Lisp.  The difference is merely one of

    >> syntax.  Is this a reasonable view or am I mixed up?

    >

    > That's reasonable -- in concatenative notation, quotations replace lambdas.

    >

    > However, to call them equivalent is to miss the crucial point that although

    > they're the same in purpose, they're very different in execution.

    >

    > In a lambda, the syntax of the language is different from what it is outside

    > of the lambda: it's modified by the change in meaning of several symbols (in

    > your above example, "x*x" does something different than it would do outside

    > of the lambda). In a quotation, the syntax of the language is the same as it

    > was outside of the quotation; there are no new or redefined symbols.

    >

    > In a lambda, values get transmitted from one location to another invisibly,

    > and destroyed just as invisibly. In a quotation, values must explicitly flow

    > under operations that don't use them or into operations that do; there's no

    > point at which the exact location of a value is unknown.

    >

    > In order to call a lambda, the language must secretly arrange its parameters

    > into the order and location expected by the lambda's compiler. This almost

    > always involves copying, and is always hidden from the programmer. Very good

    > compilers attempt to minimise this copying, but because all of them do it

    > differently no programmer can code with those optimizations in mind, and no

    > compiler can rely on another compiler's optimizations. In order to call a

    > quotation, the programmer must arrange the data in order in which the

    > quotation uses it, so there's an incentive to arrange operations in a way so

    > that the data falls naturally in the right position without copying or

    > swapping.

    >

    > I could go on, but now I'm getting into the realm of the discussion I'm

    > having with Stevan Apter, so I'll continue providing more differences in

    > that post.

    >

    > Let me comment, though, that I've phrased all the above comparisons in favor

    > of quotations and against lambdas. I could just as easily phrase things the

    > other way around; lambdas have advantages too. Stevan and I will be

    > discussing this more carefully and fairly in a while. For now, please try to

    > ignore my bias and accept this message as pointing out differences between

    > lambdas and Joy quotations, not as trying to argue that Joy quotations are

    > better than lambdas. I do believe that they are; but this message doesn't

    > attempt to properly justify that belief.

    >

    >> Don

    >

    > -Billy

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

## John Cowan — 2004-05-08 13:08:21

    Don Groves scripsit:

     > I guess my remaining question at this point is: when would

    > one want to use a lambda given that quotations are available.

     When your head has exploded trying to keep track of what all is on

    the stack; i.e. when you need highly non-local behavior.  Then names

    become a tremendous win.

    After all, Forthish languages could dispense with non-primitive words

    and insist that all concatenations be stored on the stack too, to be

    rolled up when needed.  But that would make even Chuck Moore's

    remarkably capacious brain pan go boom, I fear.

    --

    "Well, I'm back."  --Sam        John Cowan <jcowan@...>

## Don Groves — 2004-05-08 20:12:54

    On Sat, 8 May 2004 09:08:21 -0400, John Cowan <cowan@...> wrote:

     > Don Groves scripsit:

    >

    >> I guess my remaining question at this point is: when would

    >> one want to use a lambda given that quotations are available.

    >

    > When your head has exploded trying to keep track of what all is on

    > the stack; i.e. when you need highly non-local behavior.  Then names

    > become a tremendous win.

     But... a lambda defines an anonymous function, they don't

    bind a function to a name, that's their whole point.

    --

    Don

## John Cowan — 2004-05-08 20:40:25

    Don Groves scripsit:

     > > When your head has exploded trying to keep track of what all is on

    > > the stack; i.e. when you need highly non-local behavior.  Then names

    > > become a tremendous win.

    >

    >

    > But... a lambda defines an anonymous function, they don't

    > bind a function to a name, that's their whole point.

     I meant names of arguments.

    --

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

    There are books that are at once excellent and boring.  Those that at

    once leap to the mind are Thoreau's Walden, Emerson's Essays, George

    Eliot's Adam Bede, and Landor's Dialogues.  --Somerset Maugham

## Don Groves — 2004-05-08 21:17:11

    On Sat, 8 May 2004 16:40:25 -0400, John Cowan <cowan@...> wrote:

     > Don Groves scripsit:

    >

    >> > When your head has exploded trying to keep track of what all is on

    >> > the stack; i.e. when you need highly non-local behavior.  Then names

    >> > become a tremendous win.

    >>

    >>

    >> But... a lambda defines an anonymous function, they don't

    >> bind a function to a name, that's their whole point.

    >

    > I meant names of arguments.

    >

     I must have misunderstood somewhere, my question related

    to anonymous functions, when to use lambdas vs. quotations.

    Is there a connection between that distinction and argument

    names that I'm missing?

    --

    Don

## John Cowan — 2004-05-09 03:12:36

    Don Groves scripsit:

     > I must have misunderstood somewhere, my question related

    > to anonymous functions, when to use lambdas vs. quotations.

    > Is there a connection between that distinction and argument

    > names that I'm missing?

     I was saying that a big advantage of lambdas is that they bind

    their arguments to names (independently of whether they themselves

    are named or not).  It's a lot easier for me, given that I have

    ten objects to deal with, to give them ten names rather than

    keep track of the current position of each on a stack.

    --

    Ambassador Trentino: I've said enough. I'm a man of few words.

    Rufus T. Firefly: I'm a man of one word: scram!

            --Duck Soup                     John Cowan <jcowan@...>

## Don Groves — 2004-05-09 17:25:30

    I looked at an example of how lambdas are implemented

    in Joy and now I get it - finally!  Thanks, John.

    --

    Don

     On Sat, 8 May 2004 23:12:36 -0400, John Cowan <cowan@...> wrote:

    > Don Groves scripsit:

    >

    >> I must have misunderstood somewhere, my question related

    >> to anonymous functions, when to use lambdas vs. quotations.

    >> Is there a connection between that distinction and argument

    >> names that I'm missing?

    >

    > I was saying that a big advantage of lambdas is that they bind

    > their arguments to names (independently of whether they themselves

    > are named or not).  It's a lot easier for me, given that I have

    > ten objects to deal with, to give them ten names rather than

    > keep track of the current position of each on a stack.

    >

## stevan apter — 2004-05-09 21:53:31

    in cK, 'let' is a combinator which uses a pattern to distribute items

    from the stack into various positions in a quotation.  cK versions of

    your r-ack, r2-ack, cnr-ack, and arg-ack are:

    [[[[pop null] popd succ                          ]

      [[null]     pop pred 1 ack1                    ]

                  [[dup pred swap] dip pred ack1 ack1]] cond]              `ack1 def;

    [[[m n][[[m null] n succ                     ]

            [[n null] m pred 1 ack2              ]

                      [m pred m n pred ack2 ack2]] cond] let]              `ack2 def;

    [[[[pop null]                 [popd succ]    ]

      [[null]                     [pop pred 1] []]

      [[[dup pred swap] dip pred] []           []]] condnestrec]           `ack3 def;

    [[[[[[m n]m null]let]           [[[m n]n succ]let]     ]

      [[[[m n]n null]let]           [[[m n]m pred 1]let] []]

      [[[[m n]m pred m n pred]let]  []                   []]] condnestrec] `ack4 def;

    the last one had me stumped for a while, until i remembered that 'let'

    is a combinator, and that lists are lazily evaluated.

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

    From: "Nick Forde" <nickf@...>

    To: <concatenative@yahoogroups.com>

    Sent: Wednesday, May 05, 2004 10:17 AM

    Subject: RE: [stack] Generalising shuffle strings [Was: Pattern matching, stack comments]

    > I've read with interest the recent discussions on shuffle strings and

    > pattern matching as I've been toying with a Joy extension which allows

    > a mix of applicative and concatenative styles. I have found that often

    > when writing Joy functions with > 1 argument a significant percentage

    > of my code ends up being stack manipulation, even with careful

    > design. This is probably largely because I'm not a good Joy programmer

    > but I find this is particularly true when using the more complex

    > recursive combinators. In other cases I find very little stack

    > manipulation is required and the concatenative notation provides the

    > most elegant solution.

    >

    > To tackle this I've been experimenting with the addition of immutable

    > stack references in function definitions. For example, in Manfred's

    > "Nested Recursion" paper the Ackermann function example is defined in

    > pseudo code as:

    >

    > ack(m, n) =

    >     IF m = 0  THEN n + 1

    >     ELSEIF n = 0  THEN ack(m - 1, 1)

    >     ELSE ack(m - 1, ack(m, n - 1))

    >

    > In Joy this can be written:

    >

    > r-ack ==

    >     [ [ [pop null] popd succ ]

    >       [ [null] pop pred 1 r-ack ]

    >       [ [dup pred swap] dip pred r-ack r-ack ]

    >     ] cond.

    >

    > By adding lexically scoped stack references and automatically popping

    > the arguments off the evaluation stack this could be written:

    >

    > r2-ack(m n) ==

    >     [ [ [m null] n succ ]

    >       [ [n null] m pred 1 r-ack ]

    >       [ m pred m n pred r2-ack r2-ack ]

    >     ] cond.

    >

    > Although both implementations are very similar I find the intention of

    > the latter clearer. In a similar way the condnestrec implementation

    > of the same function could also be rewritten:

    >

    > cnr-ack ==

    >     [ [ [pop null] [popd succ] ]

    >       [ [null]  [pop pred 1]  [] ]

    >       [ [[dup pred swap] dip pred] [] [] ]

    >     ] condnestrec.

    >

    > arg-ack(m n) ==

    >     [ [ [m null] [n succ] ]

    >       [ [n null] [m pred 1] [] ]

    >   [ [m pred m n pred] [] [] ]

    >     ] condnestrec.

    >

    > Although more compelling examples could be constructed to illustrate the

    > benefits of the applicative vs. concatenative styles I like the idea

    > of being able to combine the two.

    >

    > As Billy has already observed use of stack references like the above

    > make compilation much harder but I believe that in an interpreter the

    > performance could be comparable, at the cost of some additional memory

    > overhead.

    >

    > Regards,

    >

    > Nick.

    >

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

## Slava Pestov — 2004-05-09 23:05:31

    On Sat, May 08, 2004 at 11:12:36PM -0400, John Cowan wrote:

     > It's a lot easier for me, given that I have

    > ten objects to deal with, to give them ten names rather than

    > keep track of the current position of each on a stack.

     You don't need to keep track of the position of 10 objects on the stack.

    Factor your words into smaller pieces, such that each word manipulates

    at most 3 or so parameters on the stack.

    --

    Slava Pestov

## phimvt@lurac.latrobe.edu.au — 2004-05-10 06:44:11

    On Sun, 9 May 2004, Slava Pestov wrote:

     > On Sat, May 08, 2004 at 11:12:36PM -0400, John Cowan wrote:

    > > It's a lot easier for me, given that I have

    > > ten objects to deal with, to give them ten names rather than

    > > keep track of the current position of each on a stack.

    >

    > You don't need to keep track of the position of 10 objects on the stack.

    > Factor your words into smaller pieces, such that each word manipulates

    > at most 3 or so parameters on the stack.

     Is there a universal algebraist on board?

    I have a vague recollection reading in a book on universal algebra

    that any algebra with n-ary operators (n > 2) can be reduced (?) to

    one in which there are only binary operators. I did not understand

    the proof then, now I would not even know where to find it. But it

    struck me as something extraordinary then, and still does now. I have

    sometimes thought that it is of relevance to Joy, for precisely the

    reason you were discussing.

    So it might be that all cases of 10 objects on the stack can be

    handled by factoring, as you put it, into 3 or even just 2. There

    may even be an algorithm to do it. Even if there is, several questions

    arise: 1) an algorithm that works in all cases might produce solutions

    that are poor for the situations that actually arise. 2) The algorithm

    might produce some exponential blowout. 3) The algorithm might produce

    solutions that are mathematically correct but psychologically poor,

    yielding unreadable programs. So I would not put too much hope into

    a project that aims to mechanise the process.

    On the other hand, some well-crafted examples of hand-written solutions

    might do a lot of good. We could then learn how to apply such techniques

    in new situations. This would be useful even if the techniques do not

    work in all situations.

    To some extent the problem also arises for languges with named formal

    parameters. If so, then replacing stack references with names will

    only be part of the solution to what is essentially a psychological

    problem.

    Nothing much definite in the above, I know. Too many "might"s and

    "perhaps"es. But maybe food for thought.

      - Manfred

     >

    > --

    > Slava Pestov

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

## Joel Kelso — 2004-05-11 00:52:37

    phimvt@... wrote:

     > On Sun, 9 May 2004, Slava Pestov wrote:

    >

    > Is there a universal algebraist on board?

    >

    > I have a vague recollection reading in a book on universal algebra

    > that any algebra with n-ary operators (n > 2) can be reduced (?) to

    > one in which there are only binary operators. I did not understand

    > the proof then, now I would not even know where to find it. But it

    > struck me as something extraordinary then, and still does now. I have

    > sometimes thought that it is of relevance to Joy, for precisely the

    > reason you were discussing.

     It's not a book on universal algebra per se, but I can

    recommend "Term Rewriting and All That" by Franz Baader

    and Tobias Nipkow (Cambridge University Press, 1998,

    ISBN 0-521-77920-0).  This book (at least the first

    few chapters, I'm still working my way through it)

    helped me a lot in understanding the relationship

    between algebras, equational logic, rewrite systems,

    functional programming languages and so forth.  I'm

    not sure if it has any results pertinent to discussions

    here, but I found the terminology and concepts very

    helpful.

    Joel Kelso

## phimvt@lurac.latrobe.edu.au — 2004-05-12 06:26:59

    On Mon, 10 May 2004 phimvt@... wrote:

    [..]

    > Is there a universal algebraist on board?

    >

    > I have a vague recollection reading in a book on universal algebra

    > that any algebra with n-ary operators (n > 2) can be reduced (?) to

    > one in which there are only binary operators.

    I did find it.

    P.M. Cohn, 1965, Universal Algebra, Harper & Row. p 147:

      "Theorem 7.1

       Let Omega be an operator domain; then there exists an operator

       domain Omega* such that Omega can be embedded in the domain

       of derived operators of Omega*, and such that every Omega algebra

       A may be embedded in an Omega*-algebra A*. Moreover, if A is

       infinite, A* may be taken to have the same carrier as A, whereas

       if A is finite, A* may be taken to be countable"

    Essentially one invents (very many) arbitrary new elements to be values

    of the (few) new binary operators that need to be built. That is my

    understanding of it. But read the real proof if you can stomach it.

    I still find the theorem astounding, but I am less convinced of its

    relevance to practical computing.

    Also on p 147, bottom:

       "Another more practical method of reducing operators to binary

        ones is given in Chapter IV."

    This sounded promising, but I failed to find in that chapter anything

    that sounded like the reduction mentioned. Sorry. Anyone?

    A sobering statistic: p 148 top:

       "We note that for k = 3 [k is the nmber of elements of the domain],

        the number of unary operations is 27, the number of binary operations

        is 19683, and the number of ternary operations is nearly 10^13."

    Just before that is a simple proof that

        "..not every operation on a finite set can be expresssed in terms

         of binary ones.."

    The last two quotations seem to generalise to any kind of reduction

    of n-ary to m-ary (m < n). Bad news for the sort of factoring that

    this discussion started with.

      - Manfred

## Duraid Madina — 2004-05-12 06:55:42

    Hi Manfred,

    phimvt@... wrote:

     > Just before that is a simple proof that

    >     "..not every operation on a finite set can be expresssed in terms

    >      of binary ones.."

     This has me a bit worried; I think I'm missing something here. Can you

    please make precise what is meant by "operation on a finite set" and "in

    terms of"? I assume the simple proof is nevertheless not a constructive

    one..?

    I am quite certain that any n-ary operation (for finite n !) on a finite set

    may be expressed as a composition of binary operations, except perhaps for

    some degenerate corner cases.

        Curious,

        Duraid

## phimvt@lurac.latrobe.edu.au — 2004-05-17 03:58:56

    On Wed, 12 May 2004, Duraid Madina wrote:

     > Hi Manfred,

    >

    > phimvt@... wrote:

    >

    > > Just before that is a simple proof that

    > >     "..not every operation on a finite set can be expresssed in terms

    > >      of binary ones.."

    >

    > This has me a bit worried; I think I'm missing something here. Can you

    > please make precise what is meant by "operation on a finite set" and "in

    > terms of"? I assume the simple proof is nevertheless not a constructive

    > one..?

     "Operation":

    A function which takes arguments and values from the same set S (finite or

    infinite) is said to be an operation on S. (That's pretty standard)

    "In terms of"

    means "we can find an equivalent expression which only uses binary ops".

    Here is the verbatim proof from the book, top of p 148:

    (Note that the autor does really use postfix notation)

      "That not every operation on a finite set can be expressed in terms

       binary ones is already clear by counting. Thus on a set of k elements

       there are  k^(k^n)  n-ary operations, so that the number of ternary

       operations is  k^(k^3) . By combining two binary operations a and b,

       we can form four ternary operations xyazb, xybza, xyzab, and xyzba; so

       the number of these is at most  k^(4*(k^2)), and this is less than

       k^(k^3) for k >= 5.

     > I am quite certain that any n-ary operation (for finite n !) on a finite set

    > may be expressed as a composition of binary operations, except perhaps for

    > some degenerate corner cases.

     It is true that in most cases where we try to think of an n-ary operation

    we come up with one built up from binary ones (e.g. the sum of three

    numbers). But the proof shows that what you call the degenerate cases

    are in fact the overwhelming majority.

      - Manfred