Last week, Sam Ruby posted a very interesting article on continuations for "people older than dirt" (a category which I, according to his definition, fall into). The topic became even more interesting when Don Box posted how you can use a very similar syntax in the next iteration of C#. Shortly thereafter, Cedric Beust posted that he wasn't convinced on the usefulness of this construct, and that a simple Java class without continuations pretty much does the same thing.
Despite having, like Cedric, mainly a Java background, I do think this construct will be useful, and would welcome it in the next release (that seems to be the established pattern anyway). Consider the example of trying to write a filtered Iterator. Using the C# 2.0, the code almost writes itself:
class Program
{
public static IEnumerable<T> IteratorFilter<T>(IEnumerable<T> iterator,
Predicate<T> predicate)
{
foreach (T value in iterator)
{
if (predicate(value))
{
yield return value;
}
}
}
static void Main()
{
int[] values = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
foreach(int i in IteratorFilter(values,
delegate(int v){ return v%2 == 0; }))
{
Console.WriteLine(i); // even numbers only
}
}
}
The same can definitely not be said for Java. My initial version took quite a bit longer to create than the C# version, and ended up looking like this:
public interface Predicate<T> {
boolean evaluate(T value);
}
public class IteratorFilter<T> implements Iterator<T> {
private Iterator<T> _iterator;
private Predicate<T> _predicate;
private T _currentValue;
private boolean _hasNext = true;
public IteratorFilter(Iterator<T> iterator, Predicate<T> predicate) {
_iterator = iterator;
_predicate = predicate;
skipFiltered();
}
private void skipFiltered() {
while (_iterator.hasNext()) {
_currentValue = _iterator.next();
if (_predicate.evaluate(_currentValue)) {
return;
}
}
_hasNext = false;
}
public boolean hasNext() {
return _hasNext;
}
public T next() {
if (!_hasNext) {
throw new NoSuchElementException();
}
T result = _currentValue;
skipFiltered();
return result;
}
public void remove() {
throw new UnsupportedOperationException();
}
public static void main(String[] args) {
Integer[] values = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
Iterator<Integer> i = new IteratorFilter<Integer>(
Arrays.asList(values).iterator(),
new Predicate<Integer>() {
public boolean evaluate(Integer value) {
return value % 2 == 0;
}
});
while(i.hasNext()) {
System.out.println(i.next());
}
}
}
Ouch! Without continuations, there's no option to just iterate over the elements and filter out the unwanted values, like I did in the C# implementation. Instead, I'm forced to create a class that implements the Iterator interface, store _currentValue and _hasNext as fields, and create a skipFiltered() method to skip unwanted values.
I am aware that C#'s IEnumarable isn't exactly the same as a Java Iterator; in a way it's more like a subset of Java's Collection. However, creating a Java function that creates a new Collection (containing the filtered subset of the original) wouldn't be quite the same as it would create a second Collection and have all filtering done up-front, instead of just an iterator whose elements are fetched from the original in an on-demand fashion.
Disclaimer: I am by no means an expert on the new constructs in C# 2.0 or Java 5.0 (far from it) - if I've overlooked something, please let me know in the comment section below.
See also Don Box's recent blog entries for the sort of functional programming you can do when using generics and continuations: http://www.pluralsite.com/blogs/dbox/default.aspx.
Posted by Richard at April 26, 2005 2:55 AMI totally agree they are very very useful. One of the prime uses I've found is with an XmlReader. You can read through an XML document using XmlTextReader, yielding a new object everytime you hit something useful in the XML document. It's a great way to turn a firehose-style cursor with an unusual API into an OO iterator which can be consumed with foreach(). When we wrote NChant (nchant.sourceforge.net) we used the 'yield return' keyword extensively to filter sets into subsets.
Posted by RichB at April 26, 2005 4:48 AMContiuations look like to be useful. But Java was designed to be C++--: The C++ language without the garbage stuff and syntax. But C# looks like Java++--: The Java language with some new useful additions that turn it into a near-C++ dirty syntax and adds the old C++ garbage to it.
People say that Java went after C# and added the generics stuff to the language. The truth is that, this feature request was on the list at Bug Parade for some years with many votes but that was the garbage that Java was trying to remove from the language. Then, Microsoft added those old garbage (and sometimes useful) stuff to C# and used it as marketing campaign against Java. So Sun couldn't do anything but accept the expectations of its customers and add the generics stuff to the Java language.
Continuations are good. But when someone designs a programming language he has to consider tradeoffs: Say, do I want to design a language with as much syntactical sugar as Perl or do I want to keep the syntax clean and add powerful libraries to its core or both of them? Java was designed with the second principle in mind. C# is going to look like the third one... In marketing terms C# may win, but I prefer a language with a clean syntax... Now for marketing reasons, I guess Java's syntax will turn to something as ugly as C#...
Posted by Behrang Saeedzadeh at April 26, 2005 5:24 AMA minor stylistic suggestion: you chosen to advance the input interator in your constructor. You might consider delaying that until the user actually starts using the iterator so that the price of advancing the input iterator is paid at a more appropriate time.
In the equivalent class in the jga library, I used a Boolean rather than boolean, and cleared the reference when the wrapper iterator had returned a reference (essentially using the null state of the reference to indicate 'I don't know if there's a next() or not').
If you haven't seen jga (http://jga.sf.net/), consider taking a look. It is a reasonably complete adaptation of STL to java idioms.
Sorry Luke, but what you are demonstrating in this article is a generator, not a continuation...
The challenge is still on :-)
--
Cedric
Well strictly speaking, .NET doesn't have continuations, just a continuation-like syntax for generators. Multiple calls to IteratorFilter() will return new IEnumerable objects, not continue from where the previous one left off.
You have to admit though that the "yield return" construct makes the C# code a lot cleaner than the Java version.
I'll leave the discussion on actual continuations to the Ruby experts.
Posted by Luke Hutteman at April 26, 2005 10:12 AM
values = range(10)
for nr in (nr for nr in values if nr%2==0):
print nr
Posted by gheorghe at April 26, 2005 3:16 PM
Yuck, this Python code is really ugly. Five "nr" variables?!?
Python keeps rubbing me the wrong way
In response to Luke Hutteman's post on continuations, someone offered the following Python snippet to illustrate filtering: values = range(10) for nr in (nr for nr in values if nr%2==0):...
Now for marketing reasons, I guess Java's syntax will turn to something as ugly as C#...
Actually, worse - since Sun's reluctance to introduce new keywords will probably result in more ugly constructs like "for (SomeClass x: SomeCollection) { }" (as opposed to the much cleaner C# foreach version).
If this was a key feature, why wasn't an extract of real code used rather cooking up an example?
Nice to see like has been compared with like. Using an anonymous delegate stuffed onto one line (that disappears behind the adverts) for the C# and an outer class with non-standard layout for the Java.
BTW: You probably want to implement Iterator<T> for it to be useful.
Using the jga library in Java the example is:
final List< Integer > list = asList( new Integer[] { 1, 2, 3 } ); // create list
final UnaryPredicate< Integer > even = new UnaryPredicate< Integer >() { // filter function
public Boolean fn( final Integer x ) { return x%2 == 0; }
};
for ( final Integer i : filter( list, even ) )
System.out.println( i ); // print filtered list
I think this code is simpler to understand; the C# code has a double loop, one for the generator and one for the reader. Also the code is likely to be easier to debug; the C# code is transformed into something like the Java code in the compiler, therefore there is no simple mapping between runtime and source.
The example shows how inner classes in Java give you continuations (in iterator sense), iterators, generators, closures, blocks, first class functions, functors etc. in one concept. They have a number of other advantages as well:
1. Easy to understand - they are just a class
2. Easy to refactor as a stand alone class
3. Can inherit from existing classes and interfaces - e.g. UnaryPredicate above
4. Can have fields
5. Can have multiple methods
Tom: I'd use real code if I had any, but I don't use .NET 2.0 in my day-job. The .NET code was written while trying to teach myself this new construct. The subsequent Java code was then written simply to try and get the same functionality using a language I do use on a daily basis (well, Java 1.4 anyway - unfortunately I don't use Java 5 in my day-job yet either).
I added some linebreaks that should help prevent the code from disappearing off the screen - running 1600x1200 myself it looked fine on my screen, but of course most people don't run on that resolution.
Regarding implementing Iterator<T> - you're absolutely right, thank you. Fixed.
Howard: I'm not familiar with jga, but it looks interesting.
As far as debugability goes, using VS.NET you debug the code as-is, so for every iteration in the foreach in Main(), the debugger will jump to the foreach in IteratorFilter to retrieve the next value. It's very intuitive (kind of like how current Java IDEs allow you to debug a JSP as-is, instead of forcing you to deal with the generated Servlet like they used to do).
The way I understand the jga code though, it's not filtering on the fly, but rather creating a new (filtered) Collection based on the original one; or does jga's filter() method return a virtual collection that still uses the original collection as a backing store?
While I'm glad to see that people here have already pointed out that generators are not continuations, and shouldn't be called such, no one has really pointed out what full continuations can do. In theory, the generator usage of continuations could be emulated with some compiler transformations and some anonymous classes. (Which is, in fact, what I think the C# compiler does internally)
However, that won't let you get to a classic continuation example: amb. Here's the standard scheme implementation, and here's a ruby version I made by ripping off the scheme implementation.
However, before you look behind the curtain to see the little man pulling the wires, maybe you should look at a short example of what this lets you do. Yes, that's right: backtracking ala prolog right in the middle of your ruby code. (the example was also ripped out of the scheme page referenced earlier)
yield is neat, but C# doesn't have actual continuations yet. (Whether the still missing continuation functionality is actually useful in practice is beyond the scope of this post)
Posted by Daniel Martin at April 28, 2005 7:27 AMHere is a proper example of generators using Python that is equivalent to the C# code:
def IteratorFilter(alist, predicate):
for value in alist:
if (predicate(value)):
yield value
def main():
values = range(10) # same as [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
for i in IteratorFilter(values, lambda v: v%2 == 0):
print i
if __name__ == "__main__":
main()
Posted by Grant McDonald at June 15, 2005 8:42 PM
Hello Luke,
in fact the JGA filter() returns an Iterable, so it works pretty much like your original Java counter-example with Iterator, with the principal difference that it can be used in the "new for" construct.
I'm not sure it makes a difference eight months after your posting, but here it is...
Posted by Dimitrios Souflis at December 20, 2005 10:08 AMA note for Behrang: it's not the syntax, it's the semantics. Ie., no language has simpler syntax than Scheme, which arguably has no syntax at all...but Scheme has full-fledged continuations, closures, and code generation built into the language. The powerful semantics can make your code a lot shorter.
Posted by dennis at January 4, 2006 12:46 PM