[Factor-talk] Curry, cleaning up combinators

[Slava P. <sl...@fa...>]

Hi Eduardo and Daniel,

I know you're both concerned with complexity and stack shuffling in  
recursive combinators.

Pretend for a minute you're living in la la land, where 'curry' is  
compiled efficiently, and is also fast in interpretation (by consing  
a virtual sequence instead of copying). Also pretend we have a  
'compose' word which is like 'append', but again it is only for  
quotations, and it compiles in-line.

Now, pretend the core has the following utility combinators (which  
are still ugly) -- note that in this e-mail, 'times' is different  
from the 'times' you know and love -- it passes the index to the  
quotation:

: 2nth-unsafe ( n s s -- x x )
     >r over >r nth-unsafe r> r> nth-unsafe ; inline

: 2curry curry curry ; inline

: 3curry curry curry curry ; inline

: (times) ( i quot n -- )
     pick over >= [
         3drop
     ] [
         >r 2dup 2slip >r 1+ r> r> (times)
     ] if ; inline

: times ( n quot -- )
     swap 0 -rot (times) ; inline

: (find-integer) ( i quot n -- j )
     pick over >= [
         3drop f
     ] [
         >r 2dup 2slip rot [
             r> 2drop
         ] [
             >r 1+ r> r> (find-integer)
         ] if
     ] if ; inline

: find-integer ( n quot -- ? )
     swap 0 -rot (find-integer) ; inline

: all-integers? ( n quot -- ? )
     [ not ] compose find-integer not ; inline

: (find-last-integer) ( i quot -- j )
     over 0 <= [
         2drop f
     ] [
         2dup 2slip rot [
             drop
         ] [
             >r 1- r> (find-last-integer)
         ] if
     ] if ; inline

: find-last-integer ( n quot -- ? )
     >r 1- r> (find-last-integer) ; inline

Now, take a look at the following and compare with today's sequence- 
combinators.factor:

: collect ( n quot dst -- newseq )
     [ >r keep r> set-nth-unsafe ] 2curry times ; inline

: compose ( quot1 quot2 -- seq ) append ;

: (each) ( seq quot -- n newquot )
     >r dup length swap [ nth-unsafe ] curry r> compose ; inline

: each ( seq quot -- )
     (each) times ; inline

: (map) ( seq quot -- n newquot seq )
     over >r (each) r> ; inline

: collect-new ( n quot dst -- dst )
     dup length swap new [ collect ] keep ; inline

: map ( seq quot -- newseq )
     (map) collect-new ; inline

: change-each ( seq quot -- )
     (map) collect ; inline

: (2each) ( seq1 seq2 quot -- n newquot )
     >r [ max-length ] 2keep [ 2nth-unsafe ] 2curry
     r> compose ; inline

: 2each ( seq1 seq2 quot -- )
     (2each) times ; inline

: (2map) ( seq1 seq2 quot -- n quot seq1 )
     pick >r (2each) r> ; inline

: 2map ( seq1 seq2 quot -- newseq )
     (2map) collect-new ; inline

: subset ( seq quot -- newseq )
     over >r
     over length pick new-resizable
     [ [ push-if ] 2curry each ] keep
     r> like ; inline

: all? ( seq quot -- ? )
     (each) all-integers? ; inline

: finish-find ( n seq -- n elt )
     over [ dupd nth ] [ drop f ] if ; inline

: (find) ( seq quot iterator -- n elt )
     pick >r >r (each) r> call r> finish-find ; inline

: find ( seq quot -- n elt )
     [ find-integer ] (find) ; inline

: find-last ( seq quot -- n elt )
     [ find-last-integer ] (find) ; inline

Note the absence of the following:

- 3keep
- roll
- rot (except in the integer combinators)
- tuck
- nip
- swapd
- 2swap
- only 1 dupd :)

Even more interesting is the following fact. If you single-step  
through, say,

   { 1 2 3 } [ sq ] map

you eventually end up with

   3 [ { 1 2 3 } nth-unsafe sq ] collect-new

and then

   3 [ { 1 2 3 } nth-unsafe sq ] { f f f } [ collect ] keep

and then

   [
       [ { 1 2 3 } nth-unsafe sq ] { f f f }
       >r keep r>
       set-nth-unsafe
   ] times

The quotation is built up piecemeal, then passed to 'times'. It is  
very interesting how the values end up _inside_ the quotation, which  
then operates on them.

Now, if we look at the current implementation of 'map', and inline  
some factors, we end up with the following, not nearly as pretty as  
the previous:

   { 1 2 3 } [ sq ]
   over dup length
   [ [ rot nth-unsafe swap call ] 3keep drop rot ]
   -rot tuck >r new r>
   [ [ -rot >r over slip r> set-nth-unsafe ] 3keep ] repeat
   nip 2nip

Yuck! So much unnecessary stack shuffling. Sure, the compiler  
optimizes everything away, but interpreter speed, single stepper  
usability, and code understandability suffers.

I actually did some benchmarks. Interpreted, the curry-using  
combinators are twice as fast as the current ones! There is far less  
stack shuffling going on. However they don't compile.

Finally, I think an efficient 'curry' also makes it easy to implement  
efficient lexically scoped variables, and in turn make Factor a  
better platform for hosting languages with names, such as Scheme.  
libs/locals and libs/rewrite-closures will be able to merge.

Open problem: the integer combinators at the top of the e-mail are  
still ugly.

Open problem #2: actually implement non-copying and compiling curry/ 
compose! I'm going to do that for 0.90.

Slava