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
-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
Factor-talk mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/factor-talk
