Iterators at the Summer Games

re: Iterators at the Summer Games

Strilanc — Sat, 27 Jun 2009 00:00:19 GMT

I generally prefer pulling to pushing. The reason I prefer it is because when you are being pushed data, it's sometimes hard to know if you have enough data yet without doing half the work then aborting.

For example, I bet the compression stream Write methods are more complicated than the Read methods, because they have to wait for enough data before they can emit the next byte. The read method just asks for the data it wants, and that's it.

I don't like it when things are needlessly complicated, so I decided to try to turn allow pull methods to accept 'push' data. The major challenge is the lack of continuations or coroutines in .Net, so I used a separate thread instead. When data arrives the push thread passes control to the processing thread, which runs until it requests more data than is available, at which point it passes control back to the push thread. Unfortunately the requirement of that extra thread makes this only useful in limited cases.

re: Iterators at the Summer Games

Dave — Sat, 27 Jun 2009 00:18:54 GMT

I thought a commentator was supposed to make mindless comments! Where were the corny sports metaphors?

"To win this competition, that script will really need to go out and execute. Really, you just need a little bit of I/O to keep the drive alive. That may not be a full line of output...it depends on where they spot the cursor. A new Dictionary object would give him some more room to operate. That runtime error was definitely due to a blown coverage test. Now that was an ill-advised pass through the loop. He'll try and tack on the extra point with an autoincrement."

re: Iterators at the Summer Games

marc.gravell — Sat, 27 Jun 2009 01:29:56 GMT

"Similarly, collection iterators could be implemented on a “push” model." - you hay have already seen it, but if not, take a peek at PushLINQ in MiscUtil; Jon and I had fun making this work as a full LINQ implementation where data is pushed, not pulled.

http://msmvps.com/blogs/jon_skeet/archive/2008/01/04/quot-push-quot-linq-revisited-next-attempt-at-an-explanation.aspx & http://www.yoda.arachsys.com/csharp/miscutil/

re: Iterators at the Summer Games

Bertrand Le Roy — Sat, 27 Jun 2009 01:52:23 GMT

If I'm not mistaken, one example of collection iterators that push is SAX. http://en.wikipedia.org/wiki/Simple_API_for_XML

re: Iterators at the Summer Games

Pavel Minaev [MSFT] — Sat, 27 Jun 2009 02:33:19 GMT

> The next version of the CLR framework is likely to have standard interfaces that represent “observable collections”

Do you mean 4.0, or the next version after that?

re: Iterators at the Summer Games

Pavel Minaev [MSFT] — Sat, 27 Jun 2009 02:35:07 GMT

Oh, and I also can't help but remember F#'s IEvent, which can work in either pull or push. Given the ongoing type unification between languages (e.g. F# and IronPython separate tuples being replaced by a single common System.Tuple), I wonder if that upcoming feature is also going to be used in a similar way - for IEvent by F#, and possibly for something similar in C#?

re: Iterators at the Summer Games

Ben Voigt [C++ MVP] — Sat, 27 Jun 2009 06:33:23 GMT

@Strilanc:

Keeping state and using 'push' is the price you pay for non-blocking operation. But who said C# doesn't have coroutines? Since Eric is talking about iterators, it's the right place to point out that iterator blocks (the "yield return" construct) are nothing other than coroutines.

re: Iterators at the Summer Games

Frank Quednau — Sat, 27 Jun 2009 11:27:04 GMT

> The next version of the CLR framework is likely to have standard interfaces that represent “observable collections”

There is already INotifyCollectionChanged and INotifyPropertyChanged. Or do you mean something like the abstraction of parsing & registering callbacks and filters to have more control over when your code is called?

re: Iterators at the Summer Games

marc.gravell — Sat, 27 Jun 2009 12:52:43 GMT

> There is already INotifyCollectionChanged and INotifyPropertyChanged.

Don't forget IBindingList.ListChanged, which (according to MSDN) goes all the way back to .NET 1.1

re: Iterators at the Summer Games

ShuggyCoUk — Mon, 29 Jun 2009 00:46:11 GMT

"Why exactly is this exciting? Or are we really just that impressed at someone reinventing pthread_cond_wait?"

imagine a fold on an infinite sequence where the accumulator is always available to query at any point.

All your usual tools/functions for dealing with sequences would 'just work', I like the expressibiity implied.

The compiler can transform something like this already

public static IEnumerable<TResult> FoldWithPeek(this IEnumerable<T> s, TResult acc, Func<TResult,T,TResult> op)

{

yield return acc;

foreach (var t in s)

{

acc = op(acc,t);

yield return acc;

}

or you could be more imperative in style

public static TResult FoldWithPeek(this IEnumerable<T> s, ref TResult acc, Func<TResult,T,TResult> op)

{

foreach (var t in s)

{

acc = op(acc,t);

}

return acc;

}

and the compiler inserts the magic to let acc be read (but not written to) elsewhere if you need to refer to it. I prefer the co-routine style (you are letting the compiler/platform deal with the underlying thread management (the ref value wouldn't play nice if the stack moved for example), heck it could use fibers or somesuch if it wanted to.

re: Iterators at the Summer Games

Anthony Tarlano — Mon, 29 Jun 2009 12:21:15 GMT

If you haven't seen this talk by Erik Meijer at Lang.NET 2009 you should give it a viewing..

He pretty much nails "the powerful isomorphism between events and collections" by using combinators with IObserverable reactive LINQ queries instead of IEnumerables..

http://www.langnetsymposium.com/2009/talks/23-ErikMeijer-LiveLabsReactiveFramework.html

re: Iterators at the Summer Games

Greg — Wed, 01 Jul 2009 18:52:57 GMT

The easier way to do this is to use powershell to build a batch file for your to change the process's priority. You would then difference (using FC.exe) this batch file with the last batch file you had to find new lines (i.e., new processes) and output that to a batch file. Run that batch file. Rename your output file to old.txt and use it for the next run's file compare.

I've used this trick of building a batch file via command line tools many times to simplify what would involve lots of vbscript or win32 api coding.

re: Iterators at the Summer Games

Rainer Schuster — Tue, 07 Jul 2009 14:28:44 GMT

Great news! Sound like the ReactiveLinq http://tomasp.net/blog/reactive-ii-csevents.aspx

re: Iterators at the Summer Games

quetzalcoatl — Fri, 21 Aug 2009 16:32:07 GMT

Though a nice article, take no offence: sounds like you've just found a wheel.

This isomorphism is well-known (at least from my point of view) and is also used in VERY many places.

Take for example plain old send/receive pair for berkeley sockets. RECV is blocking data reading mechanisms. Almost wherever you look at OOP send/recv-like communication, you find that recv is loop'ed to wait until whole object is downloaded and then returns the whole object. More bright C++'ers envelop that method in an .. iterator, to use such sequence easily with whole STL/Boost/etc libraries. Mind the whole "stream/collection" approach directly leads to this. Yep, writing your own iterator is not a task for a complete beginner, but after writing two or three templates, its asy enough to consider it a tool rather than esoteric feature.

Or look at Ruby or Lua, where lambdas thrive as the blocks/procs/coroutines, implementing such dynamic sequence iterators is so plain dumb trivial, that there's hard NOT TO write any streaming iterators at all. if you want to read lines from file and parse them, you open the file, call "enumeratormethod" and supply it with your callback procedure, that will be called back on every single line found in the file. Similar for sockets, webrequests, whatever. It's literally everywhere.

Totalling up: whenever you perform blocking read from whatever source, you actually use this isomorphism, and it is well-known that every blocking read can be transformed into- and backfrom- an 'on completion' callback. Existence of AsyncIO proves that well enough.