Steven E. Harris <seh@panix.com> wrote:
+---------------
| rpw3@rpw3.org (Rob Warnock) writes:
| > Interesting, in that they failed to mention one of the types of
| > iterators that I've found most useful, which one might call
| > "Resettable/Multi-Traversal" [though perhaps there is a more
| > traditional or standard name for it?], which provides:
|
| It's in there, but it's not obvious.
...
| > - A reset function that restores the state of the object *AND ALL
| > OF ITS ITERATOR CHILDREN* to the state which existed immediately
| > after the execution of the "initial setup" function.
|
| This is just copy construction, permitted operationally but not
| semantically by all iterators. ...
...
| One "resets" a C++ iterator by saving a copy of the "original" or "base"
| value for the iterator. For example:
+---------------
Aha! O.k., I can see that, thanks. But that still means that to
provide the "reset()" method -- something a holder of a single
iterator object can invoke on the object and still have the same
one in hand! -- we need a wrapper iterator *around* some underlying
copyable iterator, such that the wrapper's initialization function
automatically makes a copy of the underlying iterator so that it
can make more *future* copies in case the "reset()" function is
ever called.
One copy is never enough, since if "reset()" is ever called it will
likely be called *many* times! E.g., consider this WIRLEX pattern:
<1:1000>-{<1:1000>-{<1:1000>-{1:1000}}}
This input generates a trillion output lines, and the innermost
"range" iterator [the "{1:1000}"] will have its "reset()" method
called a billion times! (Well, a billion minus one...)
+---------------
| The WIRLEX problem deserves more time to ponder.
+---------------
It does appear to be deceptively simple, if I do say so myself!! ;-}
But I find that people without experience in iterators or generators
or co-routines or fully-general continuations [or at least *some*
kind of backtracking] often have surprising difficulty figuring out
how to get different parts of the parse tree to generate results
at different "rates" [or different iteration "shapes" might be a
better phrase] yet still match up with the results from other parts
of the tree. The last example I gave contained an example of this:
BUS DATA <<31:0>,P<3:0>> = U<<23,17,09,12>-{18,3:7,13:11}>
The part to the left of the "=" generates 36 things, 32 one way
and then 4 more a slightly different way. The part to the right
of the "=" also generates 36 things, but as a cross-product of
4 things by 9 things. A naive stack-discipline walk of the parse
tree isn't going to "do the right thing".
-Rob
p.s. Oops! I just noticed a bug in the s-expr version of the
parse tree of the above input which I posted previously. It was
hand-translated from the diagram that the C version of "wirlex"
prints out, and I failed to preserve some of the interior nodes
["administrative redexes", one might almost say] of the original,
which resulted in some contants being concatenated once rather than
iterated over. [There was also a completely nonsensical "paste-o"
in the 4th-from-last line.] Here is a corrected version:
BUS DATA <<31:0>,P<3:0>> = U<<23,17,09,12>-{18,3:7,13:11}>
parses as:
(concat (konst "BUS DATA ")
(angle (concat (angle (range 31 0)))
(concat (konst "P")
(angle (range 3 0))))
(konst " = U")
(angle (concat (angle (concat (konst "23"))
(concat (konst "17"))
(concat (konst "09"))
(concat (konst "12")))
(konst "-")
(curly (concat (konst "18"))
(range 3 7)
(range 13 11)))))
-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607