Re: [Factor-talk] iterator protocol

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

Phil Dawes wrote:
> Hi Slava, Hi Factor list,
>
> I'm sure this must have been discussed before, but I was wondering if 
> the sequence combinators would be better served by an underlying 
> iterator protocol in addition to the current random access one.

This has been discussed before. I think Eduardo is a proponent of the 
idea. Dan has been experimenting with something different but along the 
same lines; a generic iteration combinator (to unify each, assoc-each, etc.)

>  I can 
> see a couple of advantages of this:
>
> - sequence combinators could be used with streams
> - sequence combinators could be used with lazy lists
>   
Yup. Here are a few more to think about:

- assocs
- database query results (see query-each, query-map in extra/db; they're 
already sitting on top of a db-specific iterator protocol)
- file system path iterators -- look at extra/io/files/paths, its 
unfinished but it would be more useful with a generic protocol

However right now lazy list operations don't compile with the optimizing 
compiler so if you used the same generic words for sequences and lazy 
lists any code using them wouldn't compile either.
> - outsources iteration to sequence classes, affording opportunites for 
> optimization
>
> (By the latter I mean that e.g. a fixnum-length container could optimize 
> to fixnum+fast)
>   
Right now if you have a fixnum-length sequence and you apply a 
combinator to it, the compiler optimizes + down to fixnum+fast, etc. Eg,

( scratchpad ) [ { 1 2 3 } [ . ] each ] f optimized-quot.
[
    { 1 2 3 } dup 1 slot swap 0 -rot \ G:184278 [
        pick pick fixnum< [
            swap
            >r 2dup
            >r
            >r
            >r r>
            swap 2 fixnum+fast slot . r>
            r>
            r>
            swap
            >r
            >r 1 fixnum+fast r>
            r>
            G:184278
        ] [ 3drop ] if
    ] call
]

Iterators would be slower than combinators because of the overhead of 
creating the iterator object (which is slight, but might bite if you're 
iterating over very short sequences repeatedly), and accessing the 
iterator state slots. The compiler could perform escape analysis though, 
and stack-allocate the iterator. That would eliminate the overhead, but 
would require some work.
> I had a quick go at an iterator protocol by way of proof-of-concept. 
> (old tuple notation I'm afraid). This protocol is more like python's 
> than STL or java. The 'each' combinator was pretty easy:
>
> GENERIC: next ( iterator -- end? )
> GENERIC: elem ( iterator -- element )
> GENERIC: iter ( seq -- iterator )
>
> USING: math.private ;
>
> TUPLE: fixnum-iterator num end ;
> C: <fixnum-iterator> fixnum-iterator
>
> M: fixnum iter ( seq -- iterator ) 0 swap <fixnum-iterator> ;
>   
Here you have an opportunity to re-order the tuple slots 'end num'. Then 
you can omit the 'swap' here.

> M: fixnum-iterator elem ( iterator -- element ) fixnum-iterator-num ;
>
> M: fixnum-iterator next ( iterator -- end? )
>     dup fixnum-iterator-num 1 fixnum+fast
>     dup pick fixnum-iterator-end fixnum<
>     [ swap set-fixnum-iterator-num t ] [ 2drop f ] if ;
>
>
> : each-iter-loop ( iter quot -- )
>    2dup [ elem ] dip call
>    over next [ each-iter-loop ] [ 2drop ] if ; inline
>
> : each-iter ( seq quot -- )
>    [ iter ] dip each-iter-loop ; inline
>   
This won't work with empty sequences. You need to have an 'end?' word 
which just does a test, and a 'next' which bumps the counter.
>
> ( scratchpad ) 3 [ . ] each-iter
> 0
> 1
> 2
>
> What do you think?

If you want to experiment further, I encourage you to whip up a library 
and submit it to extra/.

Also let me know how your specialized C arrays are going -- those could 
be added too.

Slava