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

[Adam-230]

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]

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]

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]

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