[stack] Fwd: [Factor-talk] cleave, 2cleave, and spread

The Factor developers have been discovering that their new
combinators, inspired by Dr. von Thun's 'cleave' combinator documented
at http://www.latrobe.edu.au/philosophy/phimvt/joy/j01tut.html, have
been dramatically reducing stack noise in their fairly substantial
library.

Slava, the author/primary author of the Factor language, writes:

---------- Forwarded message ----------
From: Slava Pestov <[email protected]>
Date: Tue, Apr 1, 2008 at 8:18 PM
Subject: [Factor-talk] cleave, 2cleave, and spread
To: [email protected]

Hi all,

 Yesterday I discovered that using these three words together with
 'call', any stack shuffle can be expressed.

 Let's recap:

 - cleave takes one value, and an array of quotations. It applies each
 quotation to the value; the value is removed from the stack afterwards.
 - 2cleave takes two values, and an array of quotations. it applies
 each quotation to the two values; the two values are removed from the
 stack afterwards.
 - spread takes n values and an array of n quotations; it applies the
 nth quotation to the nth value in turn.

 Now, we can define

 : drop { } cleave ;

 This works because cleave always consumes one input value, and the
 number of outputs is the sum of the number of outputs of each
 quotation in the array. The array is empty, so it has one input and no
 outputs.

 We need a way to duplicate values. This does the trick:

 : dup { [ ] [ ] } cleave ;

 We need to be able to swap values:

 : swap { [ nip ] [ drop ] } 2cleave ;

 But what about nip?

 : nip { [ drop ] [ ] } spread ;

 Now we only need one more combinator, dip:

 : dip swap { [ call ] [ ] } spread ;

 Once you have drop, dup, swap and dip, you can express any stack
 permutation.

 While this doesn't have much practical value, it does show that there
 is something fundamental about these combinators. The reason they can
 replace stack shufflers in so many cases is because they're equivalent
 in a sense. However they capture something that stack shufflers don't,
 and that is explicit one-to-many, one-to-one and many-to-one dataflow.

 Slava

_______________________________________________
 Factor-talk mailing list
 [email protected]
 https://lists.sourceforge.net/lists/listinfo/factor-talk