# Fwd: [Factor-talk] Currying cleave/spread combinators

## Adam — 2009-02-03 03:28:42

    Cross-posting Slava's email to the concatenative crowd.

    ---------- Forwarded message ----------

    From: Slava Pestov <slava@...>

    Date: Mon, Feb 2, 2009 at 10:12 AM

    Subject: Re: [Factor-talk] Currying cleave/spread combinators

    To: factor-talk@...

    Hi all,

    First, I should put it out there that these days, I'm waging holy war

    on certain shuffle words in the core. For the words listen below, my

    goal is to eliminate all usages from core, and most usages in basis,

    and move them to basis/shuffle, where the 'ugly' shufflers live. The

    shuffle words that I'm targeting for marginalization are the

    following:

    roll

    -roll

    rot

    -rot

    spin

    tuck

    2over

    Now that we have cleave/spread/apply combinators, there is really no

    reason to manipulate the stack 3 or 4-elements deep. You'll only be

    hurting yourself and people that maintain your code in the future if

    you do so. And of course they will always live on in basis/shuffle so

    they'll be around if people need them, but I'll merilessly refactor

    contributed code that uses them where I can. And of course there's

    always the locals "escape hatch": Factor's locals are full-featured

    and efficient.

    Now, you may remember about a year ago Joe sent this e-mail to the list:

     On Sun, Jul 27, 2008 at 12:54 PM, Joe Groff <arcata@...> wrote:

    > I've run into the situation a few times now where I've had "a b c" on

    > the stack, and wanted to perform "a c foo" followed by "b c bar"--

    > effectively a cleave followed by a spread. I had been doing this to

    > get that effect:

    >

    > [ [ foo ] curry ]

    > [ [ bar ] curry ] bi bi*

    >

    > This could also work:

    >

    > [ dup swapd ] 2dip 2bi*

    >

    > but that double nesting and repeated curry is an eyesore, and swapd is

    > evil, especially as part of a three-punch shuffling combo. So I threw

    > the following words into combinators.lib:

    >

    > : bi, ( obj quot quot -- quot' quot' )

    >     [ [ curry ] curry ] bi@ bi ; inline

    > : tri, ( obj quot quot quot -- quot' quot' quot' )

    >     [ [ curry ] curry ] tri@ tri ; inline

    I've decided to add Joe's combinators to the core, with the names

    bi-curry and tri-curry. I also added bi-curry*, tri-curry*, bi-curry@

    and tri-curry@ (if you're concerned about the explosion of

    combinators, see near the end of this post).

    I won't be pushing this change for a little while, maybe two weeks or

    so, because it relies on some other experimental stuff I'm working on.

    Here are the rewrite rules for these combinators; these help reason

    about them intuitively:

    A [ F ] [ G ] bi-curry == [ A F ] [ A G ]

    A B [ F ] [ G ] bi-curry* == [ A F ] [ B G ]

    A B [ F ] bi-curry@ == [ A F ] [ B F ]

    Note that they can be chained if you wish,

    A B [ F ] [ G ] bi-curry bi-curry == [ A B F ] [ A B G ]

    Using these combinators, a few tricks, and good old-fashioned code

    cleanup, I was able to eliminate all usages of 'tuck' from the core:

    tuck [ F ] 2bi@ => [ F ] curry bi@

    tuck [ F ] [ G ] 2bi* => [ F ] [ G ] bi-curry bi*

    tuck F => [ nip ] [ F ] 2bi

    The last one only makes sense if F has two inputs, but it so happens

    that every case that didn't fall under #1 and #2 was an instance of

    #3.

    To convince yourself the LHS in the second line is equivalent to the

    RHS, you can do a proof by term rewriting:

    A B C tuck [ F ] [ G ] 2bi*

    == A C B C [ F ] [ G ] 2bi*

    == A C F B C F

    A B C [ F ] [ G ] bi-curry bi*

    == A B [ C F ] [ C G ] bi*

    == A C F B C G

    Now, the new curried cleave and spread combinators have some

    interesting properties.

    Notice the following identities:

    bi == bi-curry [ call ] bi@

    2bi == bi-curry bi

    bi* == bi-curry* [ call ] bi@

    2bi* == bi-curry* bi*

    Above we saw that the combination bi-curry bi* can express a pattern

    that 2bi and 2bi* alone cannot. What if you do bi-curry* bi? Well it

    turns out that's equivalent to another common stack shuffle pattern:

    [ over ] dip [ F ] [ G ] 2bi*

    Indeed,

    A B C [ over ] dip [ F ] [ G ] 2bi*

    == A B over C [ F ] [ G ] 2bi*

    == A B A C [ F ] [ G ] 2bi*

    == A B F A C G

    And also,

    A B C [ F ] [ G ] bi-curry* bi

    == A [ B F ] [ C G ] bi

    == A B F A C G

    Now recall this,

    tuck [ F ] 2bi@ == [ F ] curry bi@

    Well how can we write this without a shuffle?

    [ over ] dip [ F ] 2bi@

    This is just

    [ F ] bi-curry@ bi

    Because

    A B C [ over ] dip [ F ] 2bi@

    == A B over C [ F ] 2bi@

    == A B A C [ F ] 2bi@

    == A B F A C F

    And

    A B C [ F ] bi-curry@ bi

    == A [ B F ] [ C F ] bi

    == A B F A C F

    Using this I got rid of all but one usages of [ over ] dip.

    tri-curry* tri, tri-curry tri*, and tri-curry@ tri all encapsulate

    much more complex stack shuffle patterns which were hard to do with

    just 2tri* and 2tri@.

    Now, you may ask, what's the point of eliminating shuffle word usages

    if doing so requires introducing a whopping six new combinators. Well,

    first of all, these new combinators are natural factors of the

    existing ones; as I've mentioned above, we could define

    : 2bi bi-curry bi ;

    : 2bi* bi-curry* bi* ;

    : 3bi bi-curry bi-curry bi ;

    : 3bi* bi-curry* bi-curry* bi* ;

    : 2bi@ curry bi@ ;

    : 3bi@ curry curry bi@ ;

    Another reason is more philosophical, and explains why lately I prefer

    using combinators rather than shufflers. Shuffle words are just

    arbitrary stack permutations, whereas dataflow combinators have a

    certain inherent symmetry to them. The shuffle words which are

    'natural' to me, are the following:

    ! Removing top n stack elements

    drop

    2drop

    3drop

    ...

    ! Duplicating top n stack elements

    dup

    2dup

    3dup

    ...

    ! Swapping two elements

    swap

    Code that uses the above shufflers together with combinators is very

    easy for me to read; easier than applicative code, and I since I do

    all my programming in Factor these days, I sometimes struggle to

    understand other people's code written in Lisp, Java, or Haskell.

    On the other hand, I don't like the other shuffle words -- rot, tuck,

    over, and so on -- they don't really follow any consistent naming

    scheme, and are mostly historical artifacts from Forth. They all

    represent a subset of the possible permutations of the top 3 stack

    elements, and it is these shufflers -- not the combinators, and not

    the 'natural' shufflers listed above -- that force you to 'picture the

    stack in your head'.

    One last point I'd like to touch upon is that the 'idiomatic' Factor

    coding style has changed a lot over the years. One thing that has

    enabled the move away from lower-level stack manipulation to

    higher-level code with combinators is that over time, Factor's

    performance has improved drastically. Nowadays, higher-order functions

    -- including construction using curry and compose -- are very cheap.

    The optimizing compiler's inlining, escape analysis and dead code

    elimination cut through layers of abstraction like a knife through

    butter. This wasn't the case a couple of years ago, when something

    like "dup FOO swap BAR" would run faster than "[ FOO ] [ BAR ] bi",

    and calling "curry" was unacceptable anywhere other than

    rarely-executed, peripheral code.

    Slava

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

    This SF.net email is sponsored by:

    SourcForge Community

    SourceForge wants to tell your story.

    http://p.sf.net/sfu/sf-spreadtheword

    _______________________________________________

    Factor-talk mailing list

    Factor-talk@...

    https://lists.sourceforge.net/lists/listinfo/factor-talk

    ---------- Forwarded message ----------

    From: Slava Pestov <slava@...>

    Date: Mon, Feb 2, 2009 at 1:55 PM

    Subject: [Factor-talk] Correction to previous e-mail

    To: factor-talk@...

    Hi,

    These identities do not hold:

    : 2bi* bi-curry* bi* ;

    : 3bi* bi-curry* bi-curry* bi* ;

    : 2bi@ curry bi@ ;

    : 3bi@ curry curry bi@ ;

    Instead,

    [ A ] [ B ] bi-curry* bi* == swapd [ A ] [ B ] 2bi*

    and

    tuck [ A ] 2bi@ == [ A ] curry bi@

    So the new combinators can eliminate swapd usages (I've changed two so far).

    Slava

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

    Create and Deploy Rich Internet Apps outside the browser with Adobe(R)AIR(TM)

    software. With Adobe AIR, Ajax developers can use existing skills and code to

    build responsive, highly engaging applications that combine the power of local

    resources and data with the reach of the web. Download the Adobe AIR SDK and

    Ajax docs to start building applications today-http://p.sf.net/sfu/adobe-com

    _______________________________________________

    Factor-talk mailing list

    Factor-talk@...

    https://lists.sourceforge.net/lists/listinfo/factor-talk

## John Nowak — 2009-02-03 17:17:01

    On Feb 2, 2009, at 10:28 PM, Adam wrote:

     > Cross-posting Slava's email to the concatenative crowd.

    >

    > ...

     I'm not sure how much of a step forward this is.

    How many words/combinators are we up to now that do nothing else but

    shove values around? We have the basics like dup, drop, swap, dip,

    keep, and slip. We also have 2dup, 3dup, 2drop, 3drop, 2dip, 3dip,

    2keep, 3keep, 2slip, and 3slip. We have derived functions like nip,

    2nip, swapd, dupd, pick, tuck, over, 2over, spin, etc. Then we get

    into the more symmetrical things like bi, 2bi, 3bi, bi@, 2bi@, 3bi@,

    bi*, 2bi*, tri, tri@ 2tri, and tri*. Now we're adding to that bi-curry

    and tri-curry, bi-curry*, tri-curry*, bi-curry@, and tri-curry@.

    I'm sorry, but this just sucks. We shouldn't need dozens of words that

    do nothing else but shove data around. This isn't nearly as big of an

    issue in Forth where you don't have quotations: Eight or so functions

    is enough for moving data into the right place. Factor's higher order

    nature, however, has enabled (required?) several dozen words that all

    do really boring things. I'm sure after some period of time I'll be

    able to think in terms of 'bi-curry@' and 'tri-curry*' and so on, but

    this all seems pretty unfortunate.

    At the very least, it's going to be hard to convince new programmers

    to buy into this. Slava has already stated that getting new

    programmers to use the existing combinators instead of the basic

    shuffles is hard enough. Adding more combinators probably isn't going

    to help things. Making the traditional shufflers like 'rot' harder to

    get at in an attempt to lightly force people into the more symmetrical

    combinators is likely only going to frustrate new programmers.

    It seems to me that there has to be a better way of doing this stuff.

    At this point, I'd be willing to just go for some sort of shuffle

    syntax.

    Here's an idea for such a syntax: The input is on the left side of a

    '/' and the output is on the right side. Capitals are used only on the

    right side and indicate that a particular value is "called". For

    example:

        dip  = xf/Fx

        swap = xy/yx

        drop = x/

        dup  = x/xx

        slip = fx/Fx

        bi   = xfg/xFxG

        2bi@ = wxyzf/wxFyzF

        keep = xf/xFx

        ...

    You get the idea. I think it is possible that, with just a bit of

    practice, these will be no harder to read than the mnemonics currently

    used. Yes, they're longer, but we'd often be able to get away with

    using less of them since they're more powerful.

    We can actually make these shorter if we assume all values on the left

    side are named starting with 'z' and the top and 'y', 'x', etc going

    down the stack. I use '~' instead of '/' here to indicate the shorter

    variant is used:

        dip  = ~Zy

        swap = ~zy

        drop = ~y

        dup  = ~zz

        slip = ~Yz

        bi   = ~xYxZ

        2bi@ = ~wvZxyZ

        keep = ~yZy

        ...

    These have the upside of letting us do away with all of the current

    "boring" words if we so desired. They'd also make it easier for new

    programmers to get involved with concatenative languages because there

    wouldn't be an initial wall of useless words to learn in order to be

    able to read existing code. The downside, obviously, is that they're

    completely unpronounceable.

    - John

## John Nowak — 2009-02-03 17:29:59

    On Feb 3, 2009, at 12:17 PM, John Nowak wrote:

     > Factor's higher order nature, however, has enabled (required?)

    > several dozen words that all do really boring things.

     Perhaps I should clarify this. If Factor did not have quotations, it

    would be sensible to offer an n-ary "cleave" syntax, "spread" syntax,

    etc. For example, we might write this:

        [ + ] [ - ] 2bi

    As this:

        (| + , - |)

    I've already proposed a few such combinators lately so I won't repeat

    myself here.

    The problem with doing this in Factor is that they can only be used

    with constant functions; you can't use them with functions passed in

    as quotations. Accordingly, you'd still need the usual pile of

    combinators.

    - John

## William Tanksley, Jr — 2009-02-03 19:39:16

    I'm tempted to cross-post.

    John Nowak <john@...> wrote:

     > I'm not sure how much of a step forward this is.

    > I'm sorry, but this just sucks. We shouldn't need dozens of words that

    > do nothing else but shove data around. This isn't nearly as big of an

    > issue in Forth where you don't have quotations: Eight or so functions

    > is enough for moving data into the right place. Factor's higher order

    > nature, however, has enabled (required?) several dozen words that all

    > do really boring things. I'm sure after some period of time I'll be

    > able to think in terms of 'bi-curry@' and 'tri-curry*' and so on, but

    > this all seems pretty unfortunate.

     I agree with you; and most of those words seem hard to parse. The *

    and @ and 2 and 3 are easy to skim over, but are actually crucial to

    understanding the words' behaviors, and worse yet, crucial to

    understanding the purpose and behavior of the quotations PRECEDING

    those words. You wind up having to look back too often to figure out

    what's going on.

    I think cleave and spread are one of the biggest advances in practical

    concatenativity in a long time; I'm very impressed with Eduardo's

    inventiveness, and I'm glad Slava took the plunge and converted the

    entire Factor library to use them. There's no doubt in my mind that

    they entirely CRUSH the usual run-of-the-mill stack shuffles for many,

    perhaps most, purposes. They document intention much better than stack

    shuffles for most cases. But there's something missing, as outlined

    above.

     > It seems to me that there has to be a better way of doing this stuff.

    > At this point, I'd be willing to just go for some sort of shuffle

    > syntax.

     This has been suggested before; I've been a strong proponent. The

    problem with it -- if I may be so free as to complain (ha) -- is that

    it's merely a better naming convention for shuffles, with all the

    resulting problems with documenting intent. When you add in the

    ability to execute within the shuffle you get a LOT more power, but

    the naming burden becomes too much for the syntax to bear; every

    shuffle becomes a "stop and think about it" moment, at least long

    enough to see whether there are upper case letters.

    From what I can see, adding the ability to run functions eliminates

    the readability of shuffle notation, thereby removing the one thing

    they originally did best: providing clear names for complex data

    rearrangements. And they're certainly not clear names for documenting

    dataflow intent.

    Factor has, I think, proven that dataflow intent is more expressive

    than general stack shuffling. Therefore, I think we ought to be

    looking more along the lines of clarifying dataflow intent... And on

    this point I clearly agree with you that cleave/spread aren't the

    final solution.

    [...later, John added:]

     > Perhaps I should clarify this. If Factor did not have quotations, it

    > would be sensible to offer an n-ary "cleave" syntax, "spread" syntax,

    > etc. For example, we might write this:

    >   [ + ] [ - ] 2bi

    > As this:

    >   (| + , - |)

    > The problem with doing this in Factor is that they can only be used

    > with constant functions; you can't use them with functions passed in

    > as quotations. Accordingly, you'd still need the usual pile of

    > combinators.

     Actually, they might be enough to handle the vast majority of use

    cases (just as cleave/spread were enough to handle the vast majority

    of stack shuffles). For times when passed functions are required, a

    combinator will also be needed -- that's a common shortcoming with

    syntax.

    I wonder if Factor's impressive code-querying tools are powerful

    enough to answer the following question: "How common is it to pass

    literal quotations to 'cleave' and 'spread'?" If it happens a

    reasonable amount (and if Factor can automatically tell us where!), it

    might be worth our time to start converting those examples to see if

    there's a decent readability increase.

     > - John

     -Wm