Hello,
Once upon a time, I wrote about an implementation of subset based on
an object I called a "pusher".
A pusher has a "predicate" quotation and some local storage called the
"accumulator". You can "apply" a pusher to an object. If the object
you apply the pusher to satisfies the predicate, it's added to the
accumulator.
Here's a pusher which accumulates even numbers:
[ dup [ even? ] call [ V{ } push ] [ drop ] if ]
Let's see it in action:
( scratchpad ) [ dup [ even? ] call [ V{ } push ] [ drop ] if ]
----------
[ dup [ even? ] call [ V{ } push ] [ drop ] if ]
( scratchpad ) 2 over call
----------
[ dup [ even? ] call [ V{ 2 } push ] [ drop ] if ]
( scratchpad ) 4 over call
----------
[ dup [ even? ] call [ V{ 2 4 } push ] [ drop ] if ]
( scratchpad ) 6 over call
----------
[ dup [ even? ] call [ V{ 2 4 6 } push ] [ drop ] if ]
( scratchpad ) 7 over call
----------
[ dup [ even? ] call [ V{ 2 4 6 } push ] [ drop ] if ]
( scratchpad )
The subset word can be implemented in terms of a pusher.
Let's say we have a word called 'make-pusher' ( predicate -- pusher ).
Then subset looks like this:
: alt-subset ( seq quot -- subseq )
make-pusher 2dup >r >r each r> r> pusher-accum swap like ;
Or:
: alt-subset ( seq quot -- subseq )
make-pusher [ each ] 2keep pusher-accum swap like ;
So what about the implementation of make-pusher? It's conceptually
very simple. Consider the example again:
[ dup [ even? ] call [ V{ } push ] [ drop ] if ]
The template of a pusher is:
[ dup PREDICATE call [ ACCUMULATOR push ] [ drop ] if ]
All make-pusher has to do is start with the template and fill in the
two slots, PREDICATE and ACCUMULATOR. Conceptually it does this:
: make-pusher ( predicate -- pusher )
[ dup PREDICATE call [ ACCUMULATOR push ] [ drop ] if ]
clone
set-pusher-predicate
reset-accumulator ;
This kind of pusher can be made fast with define-transform. A subset
defined in terms of this pusher performs well:
( scratchpad ) : foo-a [ even? ] subset ;
----------
( scratchpad ) \ foo-a compile
Compiling foo-a
----------
( scratchpad ) : foo-b [ even? ] alt-subset ;
----------
( scratchpad ) \ foo-b compile
Compiling foo-b
Compiling reset-pusher
Compiling pusher-accum
----------
( scratchpad ) 100000 >array [ foo-a ] time drop
23 ms run / 0 ms GC time
----------
( scratchpad ) 100000 >array [ foo-b ] time drop
21 ms run / 0 ms GC time
----------
( scratchpad )
Ed
-------------------------------------------------------------------------
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
