Odd behavior in 0.2.2 under jdk1.6.0_02
Tim
through some experiments and I'm not sure it behaves as I'd expect.
Maybe this is by design and maybe not. I do think the documentation
could provide some more examples with output. The example I've got is
as follows:
public class YieldTest {
private static Iterable<Integer> yieldMax(final int x) {
return new Yielder<Integer>() {
@Override
protected void yieldNextCore() {
for (int i = 0; i < x; i++) {
System.out.println("Computing " + i);
yieldReturn(i);
}
}
};
}
public static void main(String[] argv) {
for (int i: YieldTest.yieldMax(5)) {
System.out.println("Got value " + i);
}
}
}
I would expect to see alternating Computing... / Got value messages
but instead I see the following:
Computing 0
Computing 1
Got value 0
Computing 2
Got value 1
Computing 3
Got value 2
Computing 4
Got value 3
Got value 4
It computes the first two values. I haven't dug into the source code
yet but it doesn't seem necessary at first glance to compute two
values at the start. I get the same results when using the iterator
directly rather than through the for each loop.
This a very interesting project and has got me interested in all sorts
of changes that could be made at the bytecode level!
Avah
Maybe some documentation is lacking on why this behavior might happen,
but here is an informal version of it.
Since iterators have the hasNext() method, they require you to know if
there are further values to be retrieved. For a simple array, this is
a simple test since it just needs to check the size of the array
compared against the current index. For a filtered iteration, however,
it's more complex as you need to compute all of the next values until
reaching a valid value (a value that passes the evaluation check of
the filter).
Since the hasNext needs to be initialised at first (in order to allow
the start of an iteration!), the pseudo-code for iteration is:
When creating the iterator, call internal "yieldNext" which does:
1. Check next values (by calling nextYieldCore) and see that a value
arrived.
1.1. Value returned? Great. Set that value to the "nextValue" and set
"hasNext" to true.
1.2. Value didn't return? Set "hasNext" to false.
When calling "next()"
1. Save "nextValue" to a local variable "x".
2. Call "nextYield" again in order to set "hasNext" and "nextValue"
for the next "next()" or "hasNext()" calls.
3. Return "x".
When calling "hasNext()"
1. Just returned the previously intiialised member "hasNext". This has
been initialised to something, by called yieldReturn or yieldBreak (or
by not calling any, if the yieldNextCore returned normally, set to
"false".)
This is why you get two "Computing": The first is when starting the
Yielder, then there are alternating "Computing/Got value" sets, until
the last one which doesn't have "Computing" because it already knows
that the last value has been reached before returning "3".
A different version of the above explanation: The yielder always
computes one value ahead of the value returned by "next()".
Avah
There are other ideas I have for making these kind of online mini-
compilers, but the main issue is keeping the code compilable under
normal JDK compilers.
Aviad.
On Sep 16, 11:28 pm, Tim <tsnyder...@gmail.com> wrote:
Tim
for fun and it kept me up late... I was having trouble and finally
went to bed but had local variable promotion and goto labels swirling
around my head and just had to try by hand what the Yielder package
does. Without the goto statement, what a nightmare! More on that in
a minute though, first back to yielding twice first.
As I understand the Iterators (and maybe this is just plain wrong
but...) each iteration of a for each loop calls Iterator.hasNext() AND
Iterator.next()... in essence the design used for the Enumerators with
while loops ie: for (int i: new LinkedList<Integer>()) {} is
equivalent to
Iterator it = new LinkedList<Integer>.iterator();
while (it.hasNext()) {
int i = it.next();
}
In this case the couldn't the Yielder call yieldNextCore() for each
call to hasNext() and save the results temporarily, then return those
results on a call to next()?
I still have not ventured into the Yielder source but I have read
through the posts about its design and I think such an approach would
at least work, if not be more desirable.
For my project I wanted to iterate through the many solutions to a
problem where the algorithm yields the answer at the deepest level of
recursion, then continues to the next answer (Knuth's Dancing Links
Algorithm X to place the 12 pentominoes in a 6x10 board.) Anyways in
case the first solution to a problem takes a long time to generate I
wanted to avoid having to generate two solutions just to get to the
first.
In my hand coded approach I had to break the structured code into
smaller method blocks that ended in a yielding return statement. As
suggested by your solution I stored off the location of the next
instruction in the algorithm by saving a reference to the next method
in the form of an object implementing a common interface. These
objects were all unique instances of different inner classes. The
outer class stored all the promoted local variables. An interesting
exercise, but not one I would want to try again.
This brings me back to the problem I'm still having with Yielder...
Everything compiles, but when I run it I get the following exception
when using 0.2.2:
Exception in thread "main" java.lang.VerifyError: (class: tim/fun/
SBMatrix$1, method: yieldNextCore signature: ()V) Incompatible
argument to function -- any ideas?
Avah
in which the yielder first looks up and caches both the fact that it
has an object to offer (the return value of "hasNext") and the object
itself (the return value of "next"). Then, for each call to "next",
the NEXT value is being seeked, "hasNext" and "next" are cached again,
and the original value is returned, which achieves the Iterator's
contract.
For your problem: I have been noticing a problem like that, and I've
added it to the issues list (this is #11 at
http://code.google.com/p/infomancers-collections/issues/detail?id=11).
The problem could occur quite often, and requires either another
"mapping session", much like the one done for variable promotion, or a
change to use a DOM model instead of a SAX model for going through the
code. This is a critical problem and I'm trying to get a fix for it as
fast as I can! :)
Avah
I've reached the conclusion it would be wiser to just switch to a tree-
based model.
It's a pain, since I might need to transform all the previous code
too... I'll take a look at what it takes. If you'd like, take the
trunk version and see what I've done so far, see if you can make the
tests work. :)
Aviad.
On Sep 20, 6:36 am, Avah <aviad.infomanc...@gmail.com> wrote:
> I'll first answer the design question: Yes, what you said is correct,
> in which the yielder first looks up and caches both the fact that it
> has an object to offer (the return value of "hasNext") and the object
> itself (the return value of "next"). Then, for each call to "next",
> the NEXT value is being seeked, "hasNext" and "next" are cached again,
> and the original value is returned, which achieves the Iterator's
> contract.
>
> For your problem: I have been noticing a problem like that, and I've
> added it to the issues list (this is #11 athttp://code.google.com/p/infomancers-collections/issues/detail?id=11).