Java discovers map
Michael Bohn
http://gafter.blogspot.com/2007/07/internal-versus-external-iterators.html
He even mentions Lisp in his entry!
I'm not mocking about Java, maybe if they find out that Lisp supports
this stuff since a long time (dunno maybe ever?) they will look at us in
this strange way a little less ;)
Michael
Rainer Joswig
Michael Bohn <spaceo...@gmx.de> wrote:
They'd just need to read SICP once or twice.
Pascal Costanza
Back in the days when Sun introduced its collection framework into the
JDK, there was already a moderately successful library for collections
available called JGL which already favored internal over external
iterators. It was much better than the crap that Sun came up with, and a
considerable number of JGL users tried to build up pressure to make Sun
adopt JGL instead of reinventing the wheel in a bad way. Unfortunately,
it was already apparent that Sun's decisions for or against inclusion of
features into Java are mainly driven by political factors, and not
technical ones.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Tayssir John Gabbour
> Back in the days when Sun introduced its collection framework into the
> JDK, there was already a moderately successful library for collections
> available called JGL which already favored internal over external
> iterators. It was much better than the crap that Sun came up with, and a
> considerable number of JGL users tried to build up pressure to make Sun
> adopt JGL instead of reinventing the wheel in a bad way. Unfortunately,
> it was already apparent that Sun's decisions for or against inclusion of
> features into Java are mainly driven by political factors, and not
> technical ones.
Do you recall what the reasoning was? Did they want it smaller?
Tayssir
Pascal Costanza
I think the main issue was licensing costs, but I may be wrong.
Alan Crowe
I see three possible designs.
1)Internal Iterator
The object has a method that applies a function to each
object in the collection.
2)External iterator
There is a setup function that creates an object with
exactly two methods, one that tests it for empty, and one
that pops the next item.
3)endp, car, cdr interface The interface to the collection
object includes a method to test whether it is empty, a
method that reports the first item in the collection, and
a method that generates a new instance of the collection class
and which differs in omitting the first member.
External iterator strikes me as the least useful, though an
endp, car, cdr interface might to hard to implement for some
kinds of collections.
An I misunderstanding Java-speak? Is the articles external
iterator actually what I'm calling the endp,car,cdr
interface?
Alan Crowe
Edinburgh
Scotland
Rainer Joswig
Alan Crowe <al...@cawtech.freeserve.co.uk> wrote:
> Michael Bohn <spaceo...@gmx.de> writes:
>
> > Look here:
> > http://gafter.blogspot.com/2007/07/internal-versus-external-iterators.html
> >
> > He even mentions Lisp in his entry!
> >
> > I'm not mocking about Java, maybe if they find out that Lisp supports
> > this stuff since a long time (dunno maybe ever?) they will look at us in
> > this strange way a little less ;)
> >
>
> I see three possible designs.
>
> 1)Internal Iterator
> The object has a method that applies a function to each
> object in the collection.
>
> 2)External iterator
> There is a setup function that creates an object with
> exactly two methods, one that tests it for empty, and one
> that pops the next item.
See the alternative interface to 'Series':
http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node363.html#SECTION003510000000000000000
"
Generators are generalized input streams in the sense of Smalltalk [20].
A generator can produce a potentially unbounded number of elements of
any type. Individual elements are not computed until requested by next-in.
When an element is taken from a generator, it is removed by side effect.
Subsequent uses of next-in obtain later elements.
There is a close relationship between a generator and a series
of the elements it produces. In particular, any series can be
converted into a generator. As a result, all the scanner functions
used for creating series (see appendix A) can be used to create
generators as well. There is no need to have a separate set of
functions for creating generators.
Gatherers are generalized output streams. Elements of any type
can be entered into a gatherer using next-out. The gatherer
combines the elements together in time-sequence order into a
net result. This result can be retrieved using result-of.
There is a close relationship between a gatherer
and a collector function that combines elements in the same way.
In particular, any one-input one-output collector can be converted
into a gatherer. As a result, all the collectors used for computing
summary results from series can be used to create gatherers.
There is no need to have a separate set of functions for creating
gatherers.
"
>
> 3)endp, car, cdr interface The interface to the collection
> object includes a method to test whether it is empty, a
> method that reports the first item in the collection, and
> a method that generates a new instance of the collection class
> and which differs in omitting the first member.
>
> External iterator strikes me as the least useful, though an
> endp, car, cdr interface might to hard to implement for some
> kinds of collections.
>
> An I misunderstanding Java-speak? Is the articles external
> iterator actually what I'm calling the endp,car,cdr
> interface?
>
> Alan Crowe
> Edinburgh
> Scotland
Steven E. Harris
> 2)External iterator
> There is a setup function that creates an object with
> exactly two methods, one that tests it for empty, and one
> that pops the next item.
The Standard C++ Library's external iterators form a larger family than
the "Forward Traversal Iterator" you describe above. Actually, per the
descriptions hereน, your description maps to a "Readable Single Pass"
iterator, but note that many other combinations are possible.
Different algorithms demand different characteristics of iterators upon
which they operate.
Footnotes:
น http://www.boost.org/libs/iterator/doc/new-iter-concepts.html#design
--
Steven E. Harris
Rob Warnock
+---------------
| Alan Crowe <al...@cawtech.freeserve.co.uk> writes:
| > 2)External iterator
| > There is a setup function that creates an object with
| > exactly two methods, one that tests it for empty, and one
| > that pops the next item.
|
| The Standard C++ Library's external iterators form a larger family than
| the "Forward Traversal Iterator" you describe above. Actually, per the
| iterator, but note that many other combinations are possible.
|
| Different algorithms demand different characteristics of iterators upon
| which they operate.
Indeed. See below.
+---------------
| Footnotes:
| http://www.boost.org/libs/iterator/doc/new-iter-concepts.html#design
+---------------
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:
- An initial setup function [in CLOS terms, an :AFTER method
on INITIALIZE-INSTANCE].
- An empty test [as with Alan Crowe's list].
- A get-next function [as with Alan Crowe's list, except...].
- 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 useful for a style of tree-oriented generators which,
in addition to providing traditional depth-first walks of the
(abstract) leaves [I say "abstract leaves", since the node just
above a collection of "leaves" might really be a generator/iterator
of the leaves which produce them on demand -- and indeed *any*
interior node of the tree may be such a generator], also provides
the ability to walk some subtrees "in parallel", deterministically,
with error detection if the parallel walks don't generate the
same number of leaves.
REAL-LIFE EXAMPLE: "WIRLEX"
I've been carrying around a program -- or perhaps I should say
a "pattern" or a "meme", since I tend to re-write it from scratch
every time I learns a new language [or go to work for a new
employer!] -- which illustrates the need for both "resettable"
iterators and also the "walk some subtrees in parallel" requirement.
I call it "wirlex", which originally meant "a WIRe-wrapping netlist
LEXical pre-processor", which made it easier to create input
netlists of signal/pin pairs for a separate wire-listing program
[which sorted by signal name then generated a quasi-optimal route
and sequence to wrap the wires onto a backplane].
I wrote the original version was written in 1971 in "FASTBOL",
a compiled SNOBOL-4 from The Stevens Institute. This version
used the "expand it all in memory first, then print" approach,
and was used to generate wirelists for the DCA Smart/MUX product
line as well as several hardware design projects at Emory University.
John C. Alderman (DCA) re-wrote it in the "8BAL" macro preprocessor
for the DEC PDP-8 in 1972; that version (and all subsequent ones
that I know of) output the expansion lines as they were calculated,
due to the small memory of the PDP-8. It also ran more than an
order of magnitude faster than the FASTBOL version. Since then,
Bakul Shah wrote a version in C in 1981 at Fortune Systems, which
added the extremely-useful "cross-product" syntax [see below],
and I've since coded versions with that syntax in C [1985],
Scheme [~2000], and CL/CLOS [August 2007 -- actually, currently
in progress as direct a result of this very thread!! ;-} ].
I've also found that discussing the ideas needed for for this
application makes a great interview question for software engineers,
especially when you forbid the "all in memory" approach!! ;-}
The basic meme is just a *tiny* extension of something almost
all of us use every day: the "{string1,string2,string3}"-expander
syntax in most Unix/Linux shells that "generate" multiple
argument strings from a single typed argument, e.g.:
$ echo foo{1,2,3}bar
foo1bar foo2bar foo3bar
$
[Note: This is distinctly different from file-matching pattern
operations such as "[...]", "*", and "?", which don't generate any
expansion unless there is a matching filename in the filesystem.]
Shells, however, perform the expansion "word" at a time, so that
instances of "{...}" on the same line are unrelated, e.g.:
$ echo foo{1,2,3}bar baz{5,6,7,8}gorp
foo1bar foo2bar foo3bar baz5gorp baz6gorp baz7gorp baz8gorp
$
The "wirlex" syntax [approximate grammar attached below], however,
expands such expressions *in parallel*, and also insists that the
parallel expansions produce the same number of items, e.g.:
$ echo 'foo{1,2,3}bar baz{5,6,7}gorp' | ./wirlex -
foo1bar baz5gorp
foo2bar baz6gorp
foo3bar baz7gorp
$ echo 'foo{1,2,3}bar baz{5,6,7,8}gorp' | ./wirlex -
foo1bar baz5gorp
foo2bar baz6gorp
foo3bar baz7gorp
wirlex: Line 1, items in {} {} don't match
$
Moreover, "wirlex" permits iterator element lists to contain
either ascending or descending colon-delimited "ranges" of
either integers or letters, e.g.:
$ echo '{a:i}-{1:9}-{Omega,Z:X,others...,C:A,Alpha}' | ./wirlex -
a-1-Omega
b-2-Z
c-3-Y
d-4-X
e-5-others...
f-6-C
g-7-B
h-8-A
i-9-Alpha
$
It also allows iterators to be specified with angle brackets,
so the input "<a:i>-<1:9>-<Omega,Z:X,others...,C:A,Alpha>"
would generate exactly the same output as the above.
But the really fun part is that if you *mix* "<>" & "{}" on the
same input line, you get the Cartesian cross-product of the "<>"
expansions with the "{}" expansions, with the "{}" expansions
iterating "fastest", e.g.:
$ echo '<1:3>.{1:4} {foo,bar,baz,gorp} said <hello,there,world>' \
| ./wirlex -
1.1 foo said hello
1.2 bar said hello
1.3 baz said hello
1.4 gorp said hello
2.1 foo said there
2.2 bar said there
2.3 baz said there
2.4 gorp said there
3.1 foo said world
3.2 bar said world
3.3 baz said world
3.4 gorp said world
$
Note that all the "{}" iterate together, and all the "<>" iterate
together, no matter where on the line they are.
And of course any list element can contain sub-elements which can
be ranges or lists, including more cross-products, e.g.:
$ echo '<1:9> <{green,red,yellow} <apples,houses,socks>>' | ./wirlex -
1 green apples
2 red apples
3 yellow apples
4 green houses
5 red houses
6 yellow houses
7 green socks
8 red socks
9 yellow socks
$
A more complex example, more typical of what "wirlex" was actually
used for, is in a postscript [below].
Sorry to have nattered on for so long, but this hopefully illustrates
the need for "resettable" iterators, specifically, when one or more
"<>" and one or more "{}" are generating a cross-product, when the
"{}"s come to an end but the "<>"s still have more to generate, the
entire set of "{}" AT THE SAME LEVEL (but not elsewhere above) must
be reset to their initial states, *recursively* all the way down
[which also requires resetting any embedded "<>" that are in
cross-products].
Is there any language whose standard library provides
such resettable iterators?
[And is there a more commonly-known name for them than
"resettable iterators"?]
-Rob
p.s. Here's an approximate grammar for "wirlex" input (primitive
tokens in caps), which doesn't show the constraint on parallel
expansion lengths matching:
goal = cat
cat = cat_elem [ cat ]
cat_elem = angle | curly | kstring | EMPTY
kstring = <a sequence of characters not containing "{}<>,:" >
angle = "<" list ">"
curly = "{" list "}"
list = list_elem [ "," list ]
list_elem = cat | rep
rep = LETTER ":" LETTER | NUMBER ":" NUMBER
p.p.s. Here's a somewhat longer example, typical of its actual use
in generating wire-wrapping netlists. It may be helpful to know that
in circuit design individual chips are often designated "U<number>"
or (archaic) "E<number>", with an individual pin on the chip being
the chip designator, a dash, and a ping number, e.g., "U31-17".
In the following example, there are four chips with nine outputs each
[as might have been the case with a 22-pin MSI package circa 1980,
say, a 9-bit "D" flip-flop register with 9 inputs, 9 outputs, power,
ground, a clock, and a tri-state output enable], driving a 32-bit
data bus with byte-parity [so there are four parity bits, P<3:0>].
Notice that the last chip is used for both five data bits and all
four parity bits [probably not such a good idea, actually -- one
would want the parity bits in different chips than the data bits
they protect]:
$ echo 'BUS DATA <<31:0>,P<3:0>> = U<<23,17,09,12>-{18,3:7,13:11}>' \
| ./wirlex -
BUS DATA 31 = U23-18
BUS DATA 30 = U23-3
BUS DATA 29 = U23-4
BUS DATA 28 = U23-5
BUS DATA 27 = U23-6
BUS DATA 26 = U23-7
BUS DATA 25 = U23-13
BUS DATA 24 = U23-12
BUS DATA 23 = U23-11
BUS DATA 22 = U17-18
BUS DATA 21 = U17-3
BUS DATA 20 = U17-4
BUS DATA 19 = U17-5
BUS DATA 18 = U17-6
BUS DATA 17 = U17-7
BUS DATA 16 = U17-13
BUS DATA 15 = U17-12
BUS DATA 14 = U17-11
BUS DATA 13 = U09-18
BUS DATA 12 = U09-3
BUS DATA 11 = U09-4
BUS DATA 10 = U09-5
BUS DATA 9 = U09-6
BUS DATA 8 = U09-7
BUS DATA 7 = U09-13
BUS DATA 6 = U09-12
BUS DATA 5 = U09-11
BUS DATA 4 = U12-18
BUS DATA 3 = U12-3
BUS DATA 2 = U12-4
BUS DATA 1 = U12-5
BUS DATA 0 = U12-6
BUS DATA P3 = U12-7
BUS DATA P2 = U12-13
BUS DATA P1 = U12-12
BUS DATA P0 = U12-11
$
p.p.s. If one wrote a parser for "wirlex" syntax in CL (which I'm
in the middle of doing), one reasonable intermediate form of the
above "BUS DATA" pattern might be this s-expr:
;;; BUS DATA <<31:0>,P<3:0>> = U<<23,17,09,12>-{18,3:7,13:11}>
(concat (konst "BUS DATA ")
(angle (concat (range 31 0))
(concat (konst "P")
(angle (range 3 0))))
(konst " = U")
(angle (concat (angle (concat (konst "23")
(konst "17")
(konst "09")
(konst "12")))
(konst "-")cat (konst "23")
(curly (concat (konst "18"))
(range 3 7)
(range 13 11)))))
Ob. disclosure: I confess that I didn't bother to figure out the
above s-expr manually; I just transliterated it from the debug output
of my C version when run with "wirlex -t", which prints the parse tree
for each input line! ;-}
$ echo 'BUS DATA <<31:0>,P<3:0>> = U<<23,17,09,12>-{18,3:7,13:11}>' \
| ./wirlex -t -
C -+- K: 'BUS DATA '
|
+- < -+- C --- < --- R: 31,0
| |
| +- C -+- K: 'P'
| |
| +- < --- R: 3,0
|
+- K: ' = U'
|
+- < --- C -+- < -+- C --- K: '23'
| |
| +- C --- K: '17'
| |
| +- C --- K: '09'
| |
| +- C --- K: '12'
|
+- K: '-'
|
+- { -+- C --- K: '18'
|
+- R: 3,7
|
+- R: 13,11
$
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock
+---------------
| rp...@rpw3.org (Rob Warnock) writes:
| >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:
| > - An initial setup function [in CLOS terms, an :AFTER method
| > on INITIALIZE-INSTANCE].
| > - An empty test [as with Alan Crowe's list].
| > - A get-next function [as with Alan Crowe's list, except...].
| > - 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.
|
|
| http://download.java.net/jdk7/docs/api/java/util/Iterator.html
|
| with its »hasNext()« and »next()« methods. The »next()«
| method will return a value and advance to the next value.
+---------------
But this still lacks the "reset()" method, which is IMHO crucial
to implementing cross-products [and was what *most* of my "wirlex"
exposition was really about]!!
+---------------
| However, I have found that when implementing more
| complicated iterators, like »get the next combination
| or permutation«, it is more easy for me to implement
| in terms of the following operations:
| - valid()
| Return wether a call to value() will deliever a valid value.
| - value()
| Return the current value, do not advance.
| - advance()
| Advance to the next value, if any.
+---------------
Yes, I've also done it that way as well. As you observed,
"get_next()" can be expressed in terms of "value()/advance()",
and in fact the latter API gives the user a choice between
pre- & post-incrementing, which a single "get_next()" doesn't.
But again, like Java's, your API is still missing "reset()"!
-Rob
Steven E. Harris
> 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.
> - An initial setup function [in CLOS terms, an :AFTER method
> on INITIALIZE-INSTANCE].
This is usually mapped to a sequence's begin() and end() functions, or
possibly to an iterator's constructor.
> - An empty test [as with Alan Crowe's list].
As C++ iterators are meant to be used in pairs, with one designating
one-past-the-end of a half-open range, "empty" can be tested with the
condition
first == last // The range is empty
or
first != last // The range is not empty
This comparison is supported on all Single Pass Iterators and their
refinements.
> - A get-next function [as with Alan Crowe's list, except...].
This is ++iter to advance the iterator, and *iter (or perhaps
iter->field) to read the value, as defined by the Readable Iterator
concept.
> - 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. Note that the Incrementable Iterator
concept mentions the Assignable and Copy Constructible
concepts. However, not until we go two levels down, past Single Pass
Iterator to Forward Traversal Iterator, do we see the first semantic
guarantee that makes assignment or copy construction valid: The
expression "++r" has the following assertion:
,----
| r == s and r is dereferenceable implies ++r == ++s.
`----
This means that if iterators r and s compared equal before, incrementing
r and then incrementing s will result in both r and s comparing equal
again; they are iterating over the same sequence separately and without
interference, as opposed to a Single Pass Iterator with which r's
incrementing and s's incrementing would have been separate mutations to
the underlying sequence, such as drawing elements from the same
generator.
One "resets" a C++ iterator by saving a copy of the "original" or "base"
value for the iterator. For example:
template <class FTIter, typename T>
FTIter one_before(FTIter first, FTIter last, T const& val)
{
if ( first == last )
return last;
for ( FTIter prev = first++; first != last;
++first, ++prev )
if ( val == *first )
return prev;
return last;
}
Here we're trying to locate the element in the sequence positioned right
before the first element that matches the supplied value
"val". Obviously we can solve this in a single pass, but we need a
"lagging" iterator one behind the iterator we're using to find the
target value. (Of course, a single Bidirectional Traversal Iterator
could work as well, analogous to a singly- v. doubly-linked list
traversal).
Note the expression "FTIter prev = first++". That's making a copy of
"first" as "prev", then advancing "first". Once this expression
completes, "prev" points one element behind "first", and they can be
advanced separately. They can also be assigned, so the one could back up
"first" by one position by writing "first = prev". That's equivalent to
the "reset" operation you desire.
[...]
The WIRLEX problem deserves more time to ponder.
--
Steven E. Harris
Thomas A. Russ
> However, I have found that when implementing more
> complicated iterators, like "get the next combination
> or permutation", it is more easy for me to implement
> in terms of the following operations:
>
> - valid()
> Return wether a call to value() will deliever
> a valid value.
>
> - value()
> Return the current value, do not advance.
>
> - advance()
> Advance to the next value, if any.
>
> So, now I write a "core implementation" in terms of
> value()/advance() and then two adaptors giving two
> interfaces to that core: One for "internal" and one
> for "external" iteration.
This set also has the nice property that it is easily extensible to
iterators that have a structure that is more than just a value. For
example, if one wanted to map over a Map or Dictionary or Hashtable,
then one could also implement
- key()
Return the current key, do not advance
--
Thomas A. Russ, USC/Information Sciences Institute
Steven E. Harris
> This set also has the nice property that it is easily extensible to
> iterators that have a structure that is more than just a value.
This idea is satisfied by Property Mapsš that separate iteration from
value access. A single iterator can then point into any number of
property maps, much like a CLOS class is a key into any number of
generic functions.
Property Maps are central to the Boost Graph Library. The separation of
iteration and access contributes to the refinement of the iterator
categories in the Standard C++ Library, though Property Maps use
iterators only for traversal (calling them "cursors").
As a trivial example, parallel arrays work as property maps for a
decomposed structure:
template <typename PMKey, typename PMVal, typename Iter>
std::ostream& print(std::ostream& os, Iter it,
PMKey pmkey, PMVal pmval)
{
return os << pmkey( *it ) << "->" << pmval( *it );
}
std::string const keys[] = { "foo", "bar" };
int const values[] = { 42, 242 };
size_t iter = 0;
print( std::cout, iter, wrap( keys ), wrap( values ) );
This should print "foo->42".
Here I'm using some hypothetical "wrap()" function that prepares an
array for use as a Property Map. In the Boost Property Map library,
these adapters need not be used explicitly. The Boost library's version
also differs in syntax from the N1873 proposal, including operator[] for
lvalue property maps, but the ideas are basically the same.
To bring this all around, some of my first experiments with specializing
generic functions in CL were motivated by trying to imitate some
property map code I had written in C++.
Footnotes:
š http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1873.html
--
Steven E. Harris
Rob Warnock
| > 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
...
| 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)))))
-----
Matthew Swank
> - 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 sounds like reset takes a saved continuation.
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." - Albert Einstein.
Rob Warnock
Matthew Swank <akopa_is_very_mu...@c.net> wrote:
+---------------
| Rob Warnock wrote:
| > - 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 sounds like reset takes a saved continuation.
*Almost*, except that in most non-lazy[1] languages [e.g., Scheme]
saved continuations *don't* restore the slots of mutable objects
or values of lexical variables bound before the continuation was
captured, only the flow of control. But you're correct in the very
loose sense that an iterator reset function should act somewhat
analogous to a saved continuation, except with respect to the
iterator object's state rather than the flow of control.
-Rob
[1] This is just a CYA caveat, since I don't know enough about
lazy languages in general to say what continuations do there.