Subject: Re: Java discovers map
From: rpw3@rpw3.org (Rob Warnock)
Date: Tue, 07 Aug 2007 06:07:52 -0500
Newsgroups: comp.lang.lisp
Message-ID: <5v2dnUF0MbUVzyXbnZ2dnUVZ_rmjnZ2d@speakeasy.net>
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