Change foreach iteration protocol?

[JarrettBillingsley]

Currently there are two protocols: one for "iterator functions" and one for threads. Threads are fine, I think; it's the iterator function protocol that's.. hmmm.

It's borrowed from Lua, and like many things in Lua it's designed to be lightweight and not impose a lot of structure. It does a good job of letting you iterate over simple things without much overhead (by not having to allocate closures to iterate over simple list-like things), but the problem with it is that it's.. not very intuitive. Pretty much everyone who's used Croc on any large scale has asked me just how the hell to write an iterator. Even I have to really think about it when I write one.

Iterator functions also have one major shortcoming: when the first index is null, iteration ends. This works fine for tables, which is what Lua designed it for, but it limits general-purpose use of iterator functions. What if you want to iterate over the rows of a database query, where the first column is nullable? What if you have a map container that DOES allow null as a key? What if you zip over two arrays, the first of which contains nulls? In all of these cases, you have to either put a dummy index at the beginning (which makes the interface less intuitive and increases cognitive load), or you have to use thread iterators (which are overkill for a lot of use cases).

Thread iterators are really simple to write and use, and use out-of-band signaling to end the loop (when the thread dies), but they're pretty heavyweight. They're great for when you want to do a lot of processing and abstract it all behind a foreach loop, but you wouldn't want to invoke one to iterate over an array or table. So there's still a definite use case for lightweight iteration, it's just.. how do you redesign it to be more straightforward?

An important question is: how bad is it, really, to have to allocate something on the heap to perform an iteration? I don't want to discount a solution JUST because it might force you to allocate something at the beginning of each foreach loop. Of the built-in and stdlib types, really the only ones that DON'T need to allocate any state are the ones that are suuuuuuper simple list-like objects: arrays, memblocks, StringBuffers, Vectors, Regexps. Just about everything else (including tables and even strings, due to the difference between codepoint and byte offsets) requires at least a little more state than what the iterator function protocol gives you -- which is just "the object being iterated" and "the index of the last iteration". So it seems that allocating state to do iteration will be the rule rather than the exception, and maybe that isn't such a big problem.

So let's see what other languages have done to solve this.

Iterator objects

Like in Java. It's a small object, usually only with a couple methods like "hasNext" and "next", and maybe a "remove". While this interface is simple, it's a little more heavyweight than I'd like. You have to make a class, separate from the object it belongs to (or perhaps use a table?), and this class has a LOT of boilerplate. You might even have to create two different classes, one for "removable" iterator and one read-only one, because forcing EVERY iteration to allow removing is inefficient. One iterator object consists of the class instance AND a namespace to hold its fields, and a namespace has a blob of memory; that's three memory allocations for one iteration. Ehhhhh, don't think so.

Inversion of control

Like D. The foreach loop's body becomes a closure that's passed to the object's opApply method. It's a clever solution and makes iterators easy to write, but has a major problem unique to Croc: seamlessly returning multiple values from inside the loop becomes very tricky. You have to somehow save an arbitrary number of results, return THROUGH the opApply metamethod, and then return the results that you saved. I can't think of any way to do this short of introducing extra opcodes/complexity in the interpreter and/or allocating all the return values on the heap, somehow. Also, debugging/stepping through inside-out foreach loops is, in my experience, rather annoying B| Not to mention the extra entries in exception tracebacks due to it.

Generator functions

Like in Squirrel. These are a form of restricted thread, and like threads, they allow you to yield some values while saving the state of the generator, and then the generator can be resumed to get the next values. Unlike a thread, a generator can only yield from the top-level function; this means that the stack space that it needs to store between yields is constant and can be allocated in a single blob along with a generator function object. This also means that a new type would have to be introduced. Generator functions give you a lot of the ease of using threads (or inversion of control), but without the overhead; in fact, if generators were available, many thread iterators could probably just be turned into generators instead. The downside of generator functions is increased complexity in the interpreter. Now there's ANOTHER callable type to deal with; the interpreter has to keep track of whether or not it's inside a generator; things work differently inside generators.. blah blah blah. It's a good bit of work, but it IS an attractive solution.

So generators look nice. There's also a nice parallel between them and threads; all iteration is handled by threadlike objects. Neat.

Maybe! Possibly! Probably!

[JarrettBillingsley]

If this changes, should the "implicit dummy index insertion" behavior of foreach be removed? That is, currently when you write foreach(v; x) the compiler inserts a dummy index before v so that v is actually the second value returned by the iterator function. This was really added to make it prettier to loop through just the values of array-like types, but it causes other headaches (if you want to iterate over a "set table" or a thread that only yields one value, you have to use foreach(val, _; t); some containers like linked lists don't need to give two indices and you're stuck doing the same thing).

The only problem with removing this behavior is that makes iterating over array-like types more annoying. Either you have the default opApply behavior only return values, in which case you'd have to have something like foreach(i, v; arr, "pairs") (which is also very common); or the opApply would stay the same as it is now and to just loop over the values either you'd do foreach(v; arr, "values") (verbose) or foreach(_, v; arr) (ugly). Hmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm.

[JarrettBillingsley]

Another issue -- native generators? Howwwwwwww

[JarrettBillingsley]

The more I think about it, the less I like the generator idea.

For one, it's not significantly better than the iterator approach when it comes to memory allocation -- the generator object itself is going to be fairly heavy, saving a bunch of call record, stack frame, and EH state, meaning it'll probably be on the order of 80+ bytes. Then there's the generator's closure, which will almost always be uncacheable and therefore has to be allocated every time. So that's two fairly hefty allocations for each iteration, whereas the current function iteration method only incurs at most one. Hm.

For two, it's.. complicated. It adds a bunch of extra cases in the interpreter which would probably add a lot of potential for bugs, since it's really fiddly call stack manipulation stuff. It's also tricky to figure out what other features could potentially interact with generators (such as tailcalls in generators, though there are probably several other interactions).

For three, it doesn't afford any real benefit when writing native iterators. Since native functions have unbounded stack space, there's no way to reliably store the state of the native function's Croc stack without incurring a THIRD allocation; and of course that doesn't save the host language stack at all. So the only reasonable thing is to only allow native generators to keep all their state in upvalues, which means that native generators look pretty much identical to native iterator functions as they are now.

Okay, so maybe sticking with function iteration, in some form, is worth investigating. To summarize the problems with them as laid out in the original post: they use in-band signaling to indicate the end of iteration; and they're difficult to write since you have to handle a lot of tricky protocol issues and have to turn control inside out.

The first problem could be solved by having iterator functions return another value to signal end-of-iteration. The first return value would always a boolean that's true for continue and false for stop; any values after that are always the indices, never touched by the interpreter. Simple enough.

The second problem is harder to tackle. The protocol is actually rather elegant and flexible, from an implementation perspective; it's just that it doesn't present a very pleasant interface to human programmers. It might be possible to come up with some kind of syntactic sugar to make writing iterators easier, but..

[JarrettBillingsley]

The new field privacy mechanism has introduced another level of complexity in writing iterators. opApply returns an iterator function, which has typically been another method in the class. When that iterator function is called, the invariant state (usually the class instance) is passed as this; but in order to avoid holes in the privacy system, the proto is NOT set to the invariant state's owning class.

As a result, those iterator methods can't access any protected or private fields.

The fix is to use a thunk which does a method call of the instance's iterator method. Either you do it manually, like:

function opApply(_)
{
    local self = this
    return function(idx) { return self.iterator(idx) }, null, 0
}

function iterator(idx) { /* blah blah */ }

Or you use object.bindClassMethod to do it:

// BEFORE the class..
local boundIter

// IN the class..
function opApply(_)
    return boundIter, this, 0

function iterator(idx) { /* blah blah */ }

// AFTER the class..
boundIter = object.bindClassMethod(Class, "iterator")

This has the advantage of not allocating a closure at the beginning of each loop, but.... ew. That is grody. And if you have multiple iterators, you have to bind EACH iteration method.

So you think "well I'll just not use separate iterator methods then; I'll just always return a closure that's defined in opApply!" Nope, sorry, can't do that, since you still have the same problem: the closure's proto is NOT set to the class, so it can't access any prot/priv members. This means that those nontrivial iterators which need closure state become really.. really annoyingly complex to write.

UGH

[JarrettBillingsley]

Returning a bool as the first value from the iterator function would work if it weren't for the fact that threads are also iterable and use a different way of signaling loop completion.. so the variables would be one slot off if you were iterating over a thread. Ugh.

[JarrettBillingsley]

This is something I'd rather punt to a later backwards-incompatible version of the language. A more comprehensive solution would be in order.