Edwin Watkeys
History: Originally written September 8, 2005. Updated December 27, 2005; lightly edited December 20, 2013; revised and retitled[0] November 21, 2018; revised November 24, 2018.
One of the big new features of Java 5.0 was a new syntax for iterating over collections. Instead of tediously typing the following:
for (Iterator i = c.iterator(); i.hasNext(); ) {
String s = (String) i.next();
...
}
You can now, thanks to this new syntax, along with the introduction of generic types, substitute for the above the following code:
for (String s : c) {
...
}
That's clearly a lot less keyboard pounding. But a question begs to be answered: Why did it take ten years from debut of the Java language to introduce this feature? Let's set aside that important question for now and look at another programming language, Python.
Python is in many ways a much nicer language to program in. And it evolves more quickly than Java. For example, generators were introduced in Python 2.2. A generator is a function that can produce multiple values, maintaining state between each call. Here's a simple example:
def counter(n):
while True:
yield n
n = n + 1
Because this function definition contains the keyword yield, Python
knows it's a generator. You use the counter generator like this:
c12 = counter(12)
c12.next()
c12.next()
The first line creates an instance of the generator that starts counting at twelve. The second line tells the generator to run until it yields a value. The third tells the generator to resume running until it yields another value. The first two values yielded by this generator are the integers twelve and thirteen.
This is a cool feature: It lets programmers write simple code that without generators would be complex and error-prone. Why can't Java be more like Python?
Lets put this second question aside and think about how me might implement Python's generators in a language used by some of the most smug weenies in the world, Scheme. Scheme is a dialect of Lisp that's been around in one form or another for about thirty years. Lisp itself has been around in one form or another for almost fifty years.
Here's the best Scheme implementation I could come up with that works like the Python counter generator:
An aside for experienced Lisp programmers: The procedure I'm about to show you is far more complicated than the canonical example[1] of an accumulator, because I'm duplicating the semantics of Python's generators[2].
(define (counter n)
(letrec ((generator
(lambda (yield)
(let counter ((n n))
(call-with-current-continuation
(lambda (continue)
(set! generator (lambda (k)
(set! yield k)
(continue n)))
(yield n)))
(counter (+ n 1))))))
(lambda () (call-with-current-continuation
(lambda (yield)
(generator yield))))))
"OMFG!" you must be saying to yourself. OMFG indeed! In the original version of this scrap, I said writing this wasn't so difficult. I then found a bug that would lead to an infinite loop when the counter was used in certain non-trivial ways. So I'm going to come out and admit it: People shouldn't have to write procedures like this if they simply want to write a function that acts like a Python generator. On the plus side, this monstrosity can be used very simply by client code:
(define c12 (counter 12))
(c12)
(c12)
The first line defines c12 to be the result of the procedure
counter called with twelve as its sole argument. The second and
third lines call c12 with no argument and return, just like the
Python examples, the values twelve and thirteen. But this is all
academic, because no sane person would write procedures like this on a
regular basis.
Writing procedures like counter regularly leads to cramped fingers and
a head ready to explode. But it's interesting to note that it is
possible to write counter, and that, to the outside world, the
Scheme generator is easier to use than the Python version, because the
Scheme version returns a procedure, which can be called like any other
procedure, unlike Python generators, which return generator objects,
which require programmers to call the next method.
(An aside: The designers of Python's generators could have opted to
implement generator objects in such a way that the next value could be
retrieved via c12() and c12.next(), but they didn't. The
decision doesn't make any sense to me. And while I love many things
about Python, there's a sort of ugliness that pervades the non-trivial
corners of the language.)
Now, back to Scheme: The error-prone tedium of writing these generators
in Scheme would seemingly make them impractical, but they're not,
because Scheme includes a feature that Python and Java lack: the
ability to extend the syntax of the language. If you can manage to
write the Scheme version of counter, it isn't much more effort to
create a macro that makes this feature available in an accessible
way. Here's the macro code I wrote that does just that:
(define-syntax generator
(syntax-rules ()
((generator (YIELD ARG ...) E1 E2 ...)
(lambda (ARG ...)
(letrec ((g (lambda (yield)
(let ((YIELD
(lambda v
(call-with-current-continuation
(lambda (continue)
(set! g (lambda (k)
(set! yield k)
(apply continue v)))
(apply yield v))))))
(let ((ARG ARG) ...) E1 E2 ...))
(yield (if #f #f)))))
(lambda () (call-with-current-continuation g)))))))
(define-syntax define-generator
(syntax-rules ()
((define-generator (NAME YIELD ARG ...) E1 E2 ...)
(define NAME (generator (YIELD ARG ...)
(let NAME ((ARG ARG) ...) E1 E2 ...))))))
Once you've defined these macros, the Scheme version of the counter generator reads like this:
(define-generator (counter yield n)
(counter (+ 1 (yield n))))
Not bad, eh? The only thing that bothers me about this version is that
I need to specify the name of the yield procedure. But one could
argue that it gives programmers flexibility to give the procedure
whatever name make most sense given the context of the code. (Again,
experienced Lispers will know that this "feature" could be
fixed by using non-hygenic macros, but we're sticking to standard,
R5RS+ Scheme here.)
If you compare the first and second versions of counter, you might
notice that I did something tricky in the definition of the generator
macro: The yield procedure returns the value that it yields, so it
can be used in the recursive call to counter. You can't do that
with Python's generators.
So why can't Java be more like Python? The answer is Java is a lot like Python: Python users had to wait around for about ten years before they got generators. I added support for generators in Scheme in a few hours of playing over three days. We can argue that generators, as well as other recent features of Python, like list comprehensions, make Python a more pleasing language to work in — and I wholeheartedly agree with that argument — but fundamentally, Java and Python are alike in that you can't modify the language itself.
Java, Python, and nearly every other non-Lisp language in existence put you at the mercy of language designers. You need to wait for them to implement the language features at the top of your wish list. And when they do manage to scratch your itch, who's to say you'll like the result?
So why did it take ten years for the enhanced iteration syntax to make its way into Java? It took so long because in Java, as in most other programming languages, syntax is a big deal. You just don't go changing a language's syntax. It's hard to do, and only a select few have the skills to do it. And when it happens, expressiveness and clarity take a back seat to preserving backwards compatibility.
In Scheme, adding syntax is relatively easy and can be done on a per-problem basis, so you don't have to worry about coming up with the ideal-for-all-time solution. This ability to build the language up to a problem trumps any concern over writing in a language that uses a lot of parentheses.
Schemers.org: http://schemers.org/
- Originally titled “Why Java (and almost every other programming language) sucks.“
- http://www.paulgraham.com/accgen.html
- http://www.python.org/peps/pep-0255.html