Issue 77 - PROPOSAL: fully generalize iteration - haxe

[issuesbot]

[Google Issue #77 : https://code.google.com/p/haxe/issues/detail?id=77] by she...@coolpage.com, at 13/02/2010, 01:17:42 Fully generalizes iteration to the functional programming model:

http://copute.com/dev/docs/Copute/ref/iteration.html

Solves problems mentioned on the mailing list:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033874.html http://code.google.com/p/haxe/issues/detail?id=71

In short, deprecate "for( in )". Here is the logic:

http://www.defmacro.org/ramblings/lisp-in-haskell.html

"...We also use higher order functions (functions that take other functions in arguments) in order to evaluate the function's arguments. Take a look at how we use map - Haskell's function to iterate over a list. We pass it a function and a list, and map iterates the list and calls our function on each member. We could do this with a for statement (or if we're lucky with a foreach), but we don't have to - Haskell lets us build abstractions over boilerplate code we write over and over again without waiting for the compiler developers to write them for us (of course map is a standard part of Haskell but if it weren't we could easily implement it ourselves)..."

[issuesbot]

[comment from she...@coolpage.com, published at 13/02/2010, 01:23:47] Note, the following proposed addition of reset() to the suggested standard interface for iteration, would still apply to my proposal above:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033874.html

[issuesbot]

[comment from jason.on...@gmail.com, published at 13/02/2010, 01:36:05] Hi she...@ coolpage.com

I've noticed you've been posting alot of proposals lately, some of which are fairly major additions to the language. You seem fairly knowledgeable about how programming languages and compilers work, so have you considered forking the project, implementing the features yourself, and then seeing which of them ought to be merged back into the main code base?

I suppose I'm very aware that Nicolas in particular has a business to run, and as such would have to responsibly limit his time spent on features he doesn't consider important to the project. And while you may have some good ideas, you can't dictate how Nicolas (and the other core developers) use the time they give to the community.

In short, why not implement some of these yourself, and see who likes them? That's the grand thing about open source, which us programmers can take full advantage of.

Just a thought Jason

[issuesbot]

[comment from hubd...@gmail.com, published at 13/02/2010, 01:45:00] I agree with Jason, Shelby. You've made some very lucid and detailed suggestions for improvements, such as your reams of information regarding caching of curried functions. I absolutely commend your detailed posts and admire your intimate knowledge of functional programming concepts. However, you yourself said:

"Any way, I am happy if you do not fix this. Makes it easier to compete with HaXe, if you mark bugs as fixed that are not fixed."

..so why don't you try to 'compete' and submit some fixes yourself? In the time taken to write some of your comments, I'm sure you could have explored the haXe source code and trialed fixes directly. You are clearly a proficient programmer, it would be a pleasure to see you contributing code directly.

Warmly,

Dave

[issuesbot]

[comment from she...@coolpage.com, published at 13/02/2010, 01:59:03] Thank you. I am hoping to do exactly that. I am documenting the proposals here, because:

1. the proposals could help HaXe
2. for now best place for any community pros/cons
3. open source is about sharing (not duplicating effort)
4. have a clear delineation of features between HaXe & Copute
5. to track which of those features HaXe implements
6. for now the proposals have more context here because Copute is vaporware etc...

It is all well intentioned. By no means, am I expecting Nicolas to act or even read all these in any given time-frame. That is the beauty of a database, it saves things in structured way, so we can re-visit and sort. This is not intended to be some pressure tactic on HaXe nor Nicolas. Nor is it intended to "steal" market share for new product which does not exist. It is sharing. You know a friendly (sometime competitive) thing. I believe in "community design", which means I believe I can learn important things early in the design process by interfacing with the community often and iteratively in that process. Iterative design.

For someone to say, "go implement first", do not share here, I think would be counter-productive. You didn't say that. I take your feedback constructively. Again thank you, and thank you to Nicolas for a great product to build on.

I think the proposals I have made are fundamental enough that is important to share them asap, so that they can enter into the overall design flow/process of where we are going from here. They may or may not fit into HaXe. But it is important to consider how they impact existing and new things being contemplated by the HaXe community and developers. Etc....

[issuesbot]

[comment from she...@coolpage.com, published at 13/02/2010, 02:22:47]

..so why don't you try to 'compete' and submit some fixes yourself? In the time taken to write some of your comments, I'm sure you could have explored the haXe source code and trialed fixes directly.

I agree, but let me explain how that works on my side. I think writing the comments is part of the process of perfecting a design early and not late. Eistein said I think that we don't really know something well until we can explain it to a layman.

I have actually coded a parser engine already that implements this grammar, which contains the new proposals I have made:

http://copute.com/dev/docs/Copute/ref/grammar.txt

But there is a long way still from that to an AST, and then on to a compiled target. So yes, I have been deep thinking about what is the most efficient way to achieve the new things. Do I modify the HaXe sources, or do I build a new compiler, potentially with HaXe as an output target. Deep issues such as how to implement type inference:

http://lucacardelli.name/Papers/BasicTypechecking.pdf

So as I am going through the process of how I would code the AST, and analyzing why HaXe chose O'Caml, I am realizing more new ideas for HaXe/Copute itself. I do not want to lose these ideas in haste to implement. Then I get back to one of my original points that it would be best if HaXe/Copute was written in "well HaXe or Copute":

http://lists.motion-twin.com/pipermail/haxe/2010-February/033416.html

Meaning maybe I need the proposals to design the compiler. Or at least how it affects the road-map.

So I need some place to write the things down. The community process places a model of structure on my thought process that seems to help me. It forces me to check and re-check many aspects, because it is public expose. It seems to be working from my side, so why break it. Apologies if my public style of design causes any waste of people's time in reading things they would rather not read about until implemented. Not everyone is interested in the design of the language and compiler. You didn't say that, I just want to apologize in advance for who I am. I do have a personality, Charlie Brown or Fred Flintstone too. "A noisy American, even native indian at that". Please kindly laugh at me, if anyone feels I am being too verbose or philosophical. I will laugh at myself with you. All the best.

The beauty of this internet, is that is all about free speech and freedom to not read. Joke.

[issuesbot]

[comment from hubd...@gmail.com, published at 13/02/2010, 02:39:07] Never apologise for who you are :) Since we're quoting Einstein:

"Great spirits have always found violent opposition from mediocrities. The latter cannot understand it when a man does not thoughtlessly submit to hereditary prejudices but honestly and courageously uses his intelligence."

Assuming substitution of 'person' for 'man', I heartily concur.

I won't continue this conversation here, for fear of unwantedly filling subscribers' inboxes. Suffice to say, keep doing what you're doing; the world is a forum and intelligent people always endeavour to learn more.

Warmly,

Dave

[issuesbot]

[comment from she...@coolpage.com, published at 13/02/2010, 03:02:21] One last point on the "submitting patches". It could be very frustrating if one investments weeks of effort to learn deeply the HaXe compiler source code, submits patches, then they are rejected. This was recently lamented by the self-professed creator of "open source" Eric Raymond in his blog.

One first tries to surmise what kind of working relationship they might have with the key developers. So first I have to analyze if the current HaXe code is the way I would go if I was forced to fork. If yes, then I can try submitting patches. If no, then I have to decide what is more risky (invest to make patches they might be rejected, or invest to make my own compiler). There is just a lot of things/options that have to be considered, and I can't hold it all in my head. I have to write it down. Thanks again for the encouragement, and I do hear the feedback that in essence says implementation is more valuable than comments. I agree-- to try my best to balance the process. Also I do understand that many of you are running businesses, and thus have limited time for reading.

I wish there was some way that all emails from the list could be tagged by the person who initiated the thread, so that one could set a simple rule in their email client to dump all my posts and derivative discussion to a folder, then one could wait and read my stuff when they have "nothing better to do" (hehehe).

Warmest, Shelby

[issuesbot]

[comment from hubd...@gmail.com, published at 13/02/2010, 03:40:52] Hehe, that would be handy - if only so I could find all your posts! You convey your thoughts with incredible definition; it makes for quite the engrossing read :)

As for your considerations, perhaps you could probe to save time.. Why not email Nicolas directly with an outline of a patch you're considering implementing (caching currys seems a logical choice, given your familiarity with the solution), and asking whether he's likely to accept it, assuming it is implemented capably? At least you can make a more informed decision, that way.

Then again, you may decide that the promise of Copute in its completed form is too enticing to forego, in which case my suggestion is irrelevant!

Warmly,

Dave

[issuesbot]

[comment from she...@coolpage.com, published at 13/02/2010, 05:31:00] I improved the proposed code to be more OOP orthogonal:

http://copute.com/dev/docs/Copute/ref/iteration.html (Ctrl+F for "class Iterator" as starting point)

That now supports reset(), head(), tail() and all dat. Anyone could implement those classes now in a HaXe library, no compiler changes need for those classes.

(Humor: "all dat" is sort of like my hometown "Who dat" French/Cajun)

Also it made me realize that I had to make the class interface namespace distinct to avoid naming collisions on inheritance:

http://copute.com/dev/docs/Copute/ref/class.html#Inheritance

(btw, I hope readers understand that class Name( Super ) is like class Name : extends|implements Super in HaXe)

I was originally thinking that member names from different interfaces would be considered duplicates, but I realized perhaps we can improve upon (afaics) Python mixins.

Clarification: I meant Eric Raymond was commenting about political inertia problems at source forge open source projects, not HaXe specifically.

[issuesbot]

[comment from hubd...@gmail.com, published at 13/02/2010, 06:15:47] 'all dat' looks good, Shelby, but if I'd wanted to create my own Iterator, I would have done so. I was asking the community what they thought of a standards change - reset() seems like a performance-critical component that's missing.

What's with the type parameterisation on 'fold'? The iterative manipulators you've outlined that aren't already in Lambda could be added there. I think, if you strive hard enough, we'll eventually have 'haXell' ;)

Not convinced by your tabular formatting.. Would be nice to use doxygen (javadoc-style) syntax for comments, since it involves negligible additional effort for documentation that can be readily generated as HTML - but hey, it's your document. I'm less keen on underscore as an argument denominator too. Aren't I fussy?

/** @ return   true if the called function
              returned true for every element. */
function every(function( e : E ) : bool) : bool

I really wish we could have fold, or indeed foo. Even MyClass.foo(v:V) would be a welcome improvement to the languge. Would open up so many possibilities..

Warmly,

Dave

[issuesbot]

[comment from she...@coolpage.com, published at 13/02/2010, 07:22:04] Agreed will need a better documentation system.

I am asking the HaXe community what they think of deprecating "for( in )" and replacing it with at least my proposed Iterable as standard. Deprecation would mean can still use it but are discouraged from using it in new code.

My class Iteration could be optional in an HaXell API. Clever :) Any way Iteration can be used on an Iterable. One only needs to inherit their collection from Iteration for optimization.

fold has to be separately parameterized from the Iterable collection, because it operates on a value which may not be the same type as the type E of elements of the collection.

I think you are implying that HaXe doesn't currently allow methods to be type parameterized beyond the class type parameters? I am proposing to allow this in Copute:

http://copute.com/dev/docs/Copute/ref/class.html (see Parameterized Types section)

[issuesbot]

[comment from hubd...@gmail.com, published at 13/02/2010, 07:57:56] I don't think we should deprecate for( in ). There is elegance in its simplicity. By suggesting 'reset()', I was adhering to the philosophy 'everything should be made as simple as possible, but not simpler'. To my mind, as mentioned previously, reset() is more or less required. I consider there to be no other missing functionality which is critical, personally.

Your implementation is comprehensive, and if provided in an external library might be commonly used. However, I do not see it as beneficial to be a new standard. It is very functional (as in 'functional programming') in its design; that may suit your tastes, but others may desire more syntactic sugar. You could, indeed, create a HaXell library that afforded such an implementation.

Furthermore, we already have nearly all of the functionality you describe, using the existing simple iterator pattern and Lambda. All functions you describe in your outline which aren't currently in Lambda could be added with little effort, including 'fold'. In fact, Lambda is more suitable for 'fold' specifically, given can be paramaterised on 'fold' if it is static (..and all the functions in Lambda are static).

I would like to hear other peoples' opinions.

P.S. I was saying there's no type parameterisation on functions, yes :) Ignore the 'MyClass:foo(v:V)' portion, that was a fatigue-induced error. I have been coding various things all night, it's now 8am and I'm just now about to get some sleep!

[issuesbot]

[comment from ncanna...@gmail.com, published at 13/02/2010, 08:49:19] The issue tracker is not meant to post your own ideas about how haXe should be. You've already been banned from the mailing list, don't force me to ban your here as well.

As discussed here http://lists.motion-twin.com/pipermail/haxe/2010-February/033844.html, your usage of the issue tracker is not accepted by the haXe compiler team. Only use it to post ACTUAL WORKING CODE PATCHES !

Don't bother answering, I will not read it anyway.

[issuesbot]

[comment from she...@coolpage.com, published at 13/02/2010, 09:53:20] I was just preparing to submit the following, when I noticed that Nicolas marked all my proposals as "won't fix". But I will submit this any way, because I already put effort into writing it.

I modified the code of my proposal again:

http://copute.com/dev/docs/Copute/ref/iteration.html (Ctrl+F for "class Iterator" as starting point)

Added Iterator.index, changed Iteration methods to optionally pass the Iterator (not the index) to the called function.

Added Iterable.unreverse

Without Iterator.reset and Iterator.previous then there is no way to back up while inside of a loop, would instead break out of the loop and start over again, which means conflating the logic of the outer loop with the inner loop. So I agree with you on reset(), and add previous() as minimum needed.

Iterator.current and hasPrevious() are not necessary for a loop. I am considering removing them from my proposal. There is Iterable.reverse for making hasNext() into hasPrevious() since you only need that test when iterating the loop. Iterable.index is necessary if for no other reason that otherwise need hasPrevious() to know if at first iteration. Without Iterable.index, then the inner loop has to be conflated with the outer loop to set up a variable to simulate it. So I say add Iterable.index to the minimum needed.

Syntactical sugar is desirable when it makes code less verbose and/or easier-to-understand. Compare:

var a = [0, 1, 2, 3]; for( elem in a )... a.each...

Seems to me that my proposal is superior in every aspect, and this is why I argue to deprecate for( in ). Can you think of any example where my what is less verbose than for( in )? For example, in 3 dimension loop, it is even more compelling:

var a = [[[],[],[]],[[],[],[]],[[],[],[]]] for( i in a ) for( j in i ) for( k in j )... a.each.each.each...

That is very compelling given you get all the generality for free.

Good HaXe already has Lambda ( http://haxe.org/api/lambda ), but also need the optional ability to have it in non-static methods, combined with my function folding proposal ( http://code.google.com/p/haxe/issues/detail?id=71 ), so a.each is more terse than for( in ).

Even though not explicitly stated in reference docs ( http://haxe.org/ref/type_params ), implicitly static methods can be separately type parameterized from other methods of the same class in HaXe, but not non-static methods. This is because for a static method, we do not have to create the instance when we specify the class parameters:

http://haxe.org/api/lambda

Lambda<int,int>.fold(... Lambda<int,float>.fold(... Lambda.filter(...

For clarity only, I will repeat that I also propose that non-static methods be type parameterizable separably from the class parameters. And I understand your point that we must work today without it. My plans for Copute (or HaXe patch) would instead optionally allow:

Lambda<int,int>.fold(... Lambda.fold(... Lambda.fold<int,int>(...

P.S. I've also had my share of "trying to code past the drooping eyelids, forehead bouncing off keyboard" moments. Unfortunately it may be getting more common at age 44.7. We push on for time we have remaining. I've read that by 50s, we are pretty much washed up in terms of doing our life's best work. I hope not. I think this is why we push harder in mid-40s.

[issuesbot]

[comment from she...@coolpage.com, published at 13/02/2010, 10:03:07] Nicolas, you are hilarious. You banned me from discussing ideas at the mailing list. Now you want to ban me from sharing ideas on the issues tracker. And do you think I would invest to create a patch for HaXe, when you are standing in the way of it being utilized? I know you won't read it, you also won't entertain my private emails. You are generally obstructive to any sort of positive and friendly working relationship. I have no idea why you do not like me.

Any way, never mind. We've laid enough ground work already. Time to move to the next level. You can ban me now.

[issuesbot]

[comment from she...@coolpage.com, published at 14/02/2010, 03:47:58] There are several comments at the mailing list claiming that construction of a new iterator is semantically equivalent to proposed iterator.reset(). Note, some admit a difference in potential performance, depending on implementation, but that is not a semantic difference:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033910.html http://lists.motion-twin.com/pipermail/haxe/2010-February/033923.html http://lists.motion-twin.com/pipermail/haxe/2010-February/033927.html http://lists.motion-twin.com/pipermail/haxe/2010-February/033928.html

Well these folks are missing the fact that if the iterator is consumed by Lambda, then Lambda calls a function on each iteration, then that function is unable to reset (nor backup) without conflating logic with the outer function that called the Lambda, which of course defects one of the main points of the orthogonal composability of functional programming. It also defeats referential transparency, which will become extremely important for programming on 1000 cores (as I will explain in future on design of Copute).

I see that Dave realized this:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033929.html

And I do understand reset can not implemented for forward-only semantics:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033931.html

The simple solution is to have BiIterator (adds reset and possibly previous) inherit from Iterator, then parameterize Lambda on Iterator type expected by the function Lambda calls. Everything should be able to implement BiIterator because the forward-only Iterator cab save its construction arguments and always support a reset. If something can only be consumed once, then simply cache it in the Iterator. The ability to specify Iterator instead of BiIterator (when reset is not needed) will enable to turn off the internal caching in those cases.

Btw, Lambda currently has a design error, because it doesn't have the optional interface to pass the Iterator to the called function.

The reason bidirectional Iterator needs to be standard is so that we can write code that is composable with unknown future code in the wild. I will get more into this notion of correct OOP and composability with Copute. I think people do not understand well that referential transparency dictates composability.

[issuesbot]

[comment from she...@coolpage.com, published at 14/02/2010, 20:00:45] I think what is confusing people is that the current the HaXe Lambda ( http://haxe.org/api/lambda ) does not offer the option to pass the Iterator (nor the Iterable) to the inner function that Lambda functions call on each iteration. This is a mistake in the design of Lambda, because thus it is impossible for the inner functions to modify (such as reverse, reset, or skip forward) the Iterator being used by the Lambda function to iterate the inner function.

First John:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033945.html

John, there would be no way to call Iterable.iterator() to get a new iterator, even if Iterator will be input to the inner function with an improved Lambda. Even if Lambda functions did pass Iterable (or an Iterator without a reset()) into the Lambda inner function, it would be useless to create a new instance of Iterator using Iterable.iterator(), because the outer Lambda function would still be using the original Iterator. Besides even if you do create a new Iterator for use on child nested inner functions, then there is still no semantics for telling the Iterator of a one-time-only collection (e.g. a stream) to prepare (cache) for reset. Those are two reasons why there is no alternative to a BiIterator.reset() as a standard (which should be optional to implement only for collections that want interoperability on bidirectional consumers).

Also, you can see from above that there is no benefit to inputting the Iterable (the collection itself) into inner function, and this is harmonious with the desire to not conflate the the inner function of a Lambda with any thing more than the Iterator (and even not the Iterator in many cases). The whole point of Lambda, is that you can reuse generalized inner functions, which are not just for Iterables (and often not just for Iterators).

Tangential point is that a generalized inner function will not even be able to reference the Iterable variable in the outer lexical scope directly, because this would mean the function is not reuseable except in that one instance. Here is an example:

function f( v : Int )

{
    i.anything
}

var i = [0, 1, 2] // an Array which is an Iterable Lambda.foreach( i, f ) var j = [4, 5, 9]; Lambda.foreach( j, f ) // Bug

And again John:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033948.html

John, I hope you see above that the issue is not performance twiddling, but algorithmically fundamental to minimum needed functionality and interoperability.

And now Cauê:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033947.html

Creating your sub-class instance of Iterator is useless in terms of full interoperability, because Lambda takes an Iterable, not an Iterator, and the standard Iterables such as Array, return an Iterator, not your sub-classed Iterator. The solution of course is here:

http://copute.com/dev/docs/Copute/ref/iteration.html

Iterable returns a BiIterator or Iterator, then Lambda takes functions which expect an Iterator or BiIterator (or no Iterator). Obviously that solution depends on function overloading, but you can use function naming to achieve the same in HaXe. Also in my examples above, the Lambda functions are methods, but you can easily convert these to HaXe's static Lambda functions.

Also note that Iterator.index() is also needed, as there is no alternative. The name should semantically be index and not count (because of the potential reversible sub-class).

Off Topic: in your example the name ReverseIterator is semantically inferior to BiIterator. Your sub-class is bidirectional.

[issuesbot]

[comment from she...@coolpage.com, published at 14/02/2010, 20:19:53] And again John:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033950.html

1) Read my prior post above, for why creating a new Iterator is not possible in the inner function without conflating the inner function with the outer lexical scope. Besides there is no way for the inner function to stop Lambda functions such as foreach(). They don't return the Iterator to their caller.

2) toList() is useless on an infinite stream

3) the stream Classes that don't want to be cached can refuse to implement BiIterator.

4) I hadn't seen any infinite streams that weren't bugs :D Virtual memory is plentiful.

5) How the heck does an infinite stream ever stop iterating any way?

[issuesbot]

[comment from she...@coolpage.com, published at 14/02/2010, 20:32:50] I had a typo in prior comment, I meant "iter" instead of "foreach".

[issuesbot]

[comment from she...@coolpage.com, published at 14/02/2010, 21:15:57]

I think you conflate two different things: streams and collections. Reset does not make sense for streams.

Then don't implement BiIterator on your streams.

I can implement BiIterator on my streams because after all, it is only going to force caching when I ask for a BiIterator. Then I much rather have the caching in the reuseable BiIterator than duplicated every where I need caching of my stream.

For collections, iterator() may be called to produce any number of iterators, thus negating the need for a "reset" function.

No that is not true. Please read again:

http://code.google.com/p/haxe/issues/detail?id=77#c17

As soon as such a reset function is created, the next natural step is to start passing around iterators rather than iterables.

That is desireable.

This will lead to bugs because code will call "reset" before or after using the iterator, and other code will expect an iterator to be reset or not to be reset, depending on its requirements. It's a headache.

The implementation of BiIterator shouldn't be expecting any such order. I think I can code a BiIterator properly for a stream but if not, then no BiIterators on streams.

Iterators are bad enough because they are stateful.

Agreed, but when you need such state, it is best to encapsulate it. Iterator is the ideal encapsulation for forward iteration. If you don't need or want BiIterator state, then do not implement it. It won't be forced on you.

I think you should avoid iterators at all cost and use higher-order functions such as fold, map, etc.

Agreed. But there may be cases where someone chooses to use a bidirectional procedural algorithm. After all, if state was unnecessary, then we would code in pure Haskell with no Monads.

My objective with Copute, is to isolate the state in more intuitive ways. I am contemplating a "function" and a "procedure" keywords. Only latter will allow to reference the external lexical scope.

A subset of these functions are well-defined for both streams and iterables. Indeed, I'm releasing a haXe library fairly soon that will provide separate implementations for streams and for iterables. No API changes in iterator are necessary or even desired.

Iterator is well defined for a stream. BiIterator is optional.

[issuesbot]

[comment from she...@coolpage.com, published at 14/02/2010, 21:35:50] The counter-point line of logic seems to be that since streams are not a perfect fit to BiIterator, then do not support BiIterator for anything. Because we need for Iterable and Lambda to know about BiIterator, else we can not roll our own into them.

Additionally, in the cases where one does choose to use a BiIterator on a stream, it will be superior to rolling your own caching each time. Remember BiIterator is orthogonal to stream. Your stream code isn't impinged in any way (unless you CHOOSE to optimize for BiIterator with some stream level tricks).

[issuesbot]

[comment from she...@coolpage.com, published at 14/02/2010, 21:45:08] I think a key point keeps getting lost. How is Iterable.iterator() going to work for a stream? It is not going to rewind unless there was caching. But how would it know to cache? It is simply going to create a new forward iteration from the current position in the stream. So constructing a new Iterator is not a solution for a reset on streams. At least with BiIterator it becomes explicit which Iterables do not support BiIterator. Actually I just realized that I need to create a BiIterable to inherit from Iterable. I will correct my example code now here:

http://copute.com/dev/docs/Copute/ref/iteration.html

[issuesbot]

[comment from she...@coolpage.com, published at 15/02/2010, 04:20:49]

I get an iterator and start iterating a collection. But do I call reset first or not?

By "get", I assume you mean Iterable.iterator() or BiIterable.iterator():

http://copute.com/dev/docs/Copute/ref/iteration.html http://code.google.com/p/haxe/issues/detail?id=77#c22

If you are getting an "Iterator", then there is no reset, thus the only thing you know is that it will forward iterate.

If you get a "BiIterator", then it should be in an initially "reset" state. "reset" means at the start of the first iteration ever on the Iterable, except for any modification of the contents of Iterable by operations on Iterable outside of the Iterable interface.

If I do not call reset, the code will have different behavior depending on who calls it;

I do not understand what you see as a problem? Please remember that state of BiIterator.reset is distinct for each copy of BiIterator. A new copy of BiIterator is obtained on each BiIterable.iterator() or BiIterator.copy().

if I must call reset,

The BiIterator is initially in a reset state upon BiIterable.iterator(), but not upon BiIterator.copy().

then I may forget sometimes, leading to obscure bugs.

You do not have to remember to call reset when you BiIterable.iterator().

Moreover, if I pass the same iterator to another piece of code, which you suggest is "desirable", then it may call reset while I am in the midst of iteration, breaking my code.

If you do not want to allow that, then pass BiIterator.copy(). There may be cases where you want to allow the inner function to reset your loop, e.g. the Lambda functions should allow this generality.

The reason that proliferating Iterators (Bi or not) is "desirable" as compared to proliferating references to Iterables, is because each Iterator has distinct state, whereas if all code was interacting on Iterable, then they would be interfering with each other's state.

Iterators do not and should not have reset.

They do not and will not. Only BiIterator is proposed to have reset.

It will lead to numerous bugs, especially if people start passing around iterators in code rather than iterables.

No it will lead to less bugs by passing around BiIterator instead of Iterable. If you pass around Iterable, then Iterable.iterator() is ambiguous with respect to reverse iteration state. If you pass BiIterable, then you conflate the common state. Best is to pass around BiIterator (and copy() as desired).

The whole notion is imperative and wreaks of bad design.

No BiIterator is less imperative than passing around an Iterable, because at least you have a plurality of distinct states. If you want less imperative code than BiIterator, then pass around .copy(), and if you want even less imperative code, then pass around Iterator instead. The BiIterator exists only for those algorithms where it makes it easier and justified. Why should I force the programmer to do it the Haskell way? I give them all gradients in between imperative and pure functional.

It requires super human discipline and diligence for correct code.

I do not see any extra dependence on state that wouldn't also be required if the code operated on Iterable.iterator() and did its own caching some how. In fact, operating on Iterable.iterator() with custom caching is going to conflate state much more.

People should not even be using iterators (in general) since nearly all operations can be done with higher-order functions on collections or streams.

Agreed but with caveats. For example, lets say my incoming stream is in some form of grammar that requires me to have unbounded look-ahead. This can not be done without caching the stream. I would have two choices. I can either custom cache the stream, or I can use BiIterable. The latter is much less imperative, because the caching is encapsulated and supports distinct instances of bi-state.

[issuesbot]

[comment from she...@coolpage.com, published at 15/02/2010, 04:38:58] I think you did not understand the specifics of the proposal. Let me clarify please.

http://lists.motion-twin.com/pipermail/haxe/2010-February/033960.html

Take, for example, the following snippet of innocent looking code:

> for (a in list) {
    >    for (b in list) {
        >    }
    > }

Fails completely under your proposal.

That does not fail.

1) for( in ) uses Iterable, not BiIterable

2) Even if for( in ) used BiIterable, the BiIterator for the outer loop is not passed to the inner loop, because for( in ) will call .iterator() distinctly for each loop, and because each instance of BiIterator has a distinct state and is initially reset.

P.S. I am not participating in the discussion of pooling performance implementation of .iterator() as that is irrelevant to the semantics we are discussing.

[issuesbot]

[comment from she...@coolpage.com, published at 15/02/2010, 05:19:02] Again sorry to go on, but a quick note to say thank you to John, as his feedback caused me to make the following documentary changes:

http://copute.com/dev/docs/Copute/ref/iteration.html

// State of the first ever BiIterable.iterator
// except for content of elements and the appendage
// of additional elements.
// (it is for this reason that methods of Iterable
//  should not modify its instance, e.g. Array.splice
//  should return a new array)
function reset() : void

Also I improved the definition of index, as follows. Note as for a precedent, Javascript supports passing index (and also the Iterable) for its standard Lambda higher-order functions ( https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference/Objects/Array/ForEach ). Note where I am soon headed is to enable Copute to pass any extra object to an inner function via a mechanism similar to Monad, so then I can remove the specific option to pass an Iterator from the Lambda higher-order functions.

class Iterator

{
    // # of next() performed + 1
    function index() : int
}

class BiIterator

{
    // # of previous() to reset - 1
    function index() : int
}