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 <[email protected]> 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 2...@. 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 [email protected] https://lists.sourceforge.net/lists/listinfo/factor-talk
