Hello,
Let's take a look at the 'find' word:
: find ( seq quot -- i elt )
0 -rot (find) ; inline
Hmm... OK. Let's look at (find) :
: (find) ( n seq quot -- i elt )
[
find-step [
drop dupd nth-unsafe
] [
rot 1+ -rot (find)
] if
] if-bounds+ ; inline
OK. To understand that, we need to look at find-step and if-bounds+ :
: find-step [ >r nth-unsafe r> call ] 3keep roll ; inline
: if-bounds+ ( n seq quot quot -- )
>r pick pick length < r> find-fails ; inline
Aha, there's one more, find-fails :
: find-fails ( ? quot -- ) [ 3drop f f ] if ; inline
Are you following me? Yeah... I'm not either. :-) There are some
complicated things going on in there. I think every nook an cranny of
the Factor implementation should be approachable to a new
explorer. Especially things like combinators.
WWLBD? That is, what would Leo Brodie do? Some time ago, I read
through his funny book "Thinking Forth". I would imagine that if Leo
were in the Factor community, he'd break down the problem into
subproblems, and at the heart of the solution would be this word:
: find/run ( seq index value quot -- ? obj )
{ { [ find/out-of-bounds? ]
[ find/not-found ] }
{ [ find/test ]
[ find/found ] }
{ [ t ]
[ find/next find/run ] } } cond ; inline
That one word expresses the whole algorithm. Go ahead and count the
shuffle words in it. Yeah, zero.
The key to this design is to have a "static layout" for the
stack. Use the stack as a set of registers. For this problem, I chose
to use four "registers":
seq index value quot
When using a static-layout stack, you keep the layout of the stack
consistent across the helper words. This makes things easier for the
programmer and it works well for the 'find' word.
seq The sequence to look through
index The index of the element we're looking at in this iteration
value The value at the index
quot The "predicate"
The helper words are:
find/out-of-bounds? t if index is out of bounds for the sequence
find/not-found Exit find, return f f
find/test Call the predicate on the value
find/found Exit find, return index elt
find/next Increment the index, get the new value
find/setup Setup the static stack
This version of find has good performance:
( scratchpad ) : foo-a [ 90000 = ] find ;
----------
( scratchpad ) \ foo-a compile
Compiling foo-a
----------
( scratchpad ) : foo-b [ 90000 = ] alt-find ;
----------
( scratchpad ) \ foo-b compile
Compiling foo-b
----------
( scratchpad ) 100000 >array [ foo-a ] time 2drop
10 ms run / 0 ms GC time
----------
( scratchpad ) 100000 >array [ foo-b ] time 2drop
11 ms run / 0 ms GC time
----------
The implementation is at:
http://dharmatech.onigirihouse.com/find-stack-b.factor
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
