Support generators to make it easier to write iterators
Summary
Currently Inko supports both internal and external iterators. Internal iterators are easy to write, pretty fast, but they are not composable. This means that a combination of map
and filter
would produce intermediate collections, such as arrays.
External iterators are composable, as you pull values out of them as you go along. Unfortunately, external iterators are horribly verbose to write. Generators would allow one to more easily write external iterators, and in a less verbose way.
Motivation
Here is an iterator for traversing the keys and values in a HashMap:
object Iterator!(K: Hash + Equal, V) {
def init(table: Table!(K, V)) {
let @table = table
let mut @index = 0
}
}
impl IteratorTrait!(Pair!(K, V)) for Iterator!(K, V) {
def next? -> Boolean {
@index < @table.buckets.length
}
## Returns the next `Pair` in a `HashMap`.
def next -> ?Pair!(K, V) {
{ next? }.while_true {
let pair = @table.buckets[@index]
@index += 1
pair.if_true {
return pair
}
}
Nil
}
}
Here we can see that just writing a basic iterator is already quite verbose. Having to do this many times will likely result in developers using internal iterators more often, leading to non composable iteration interfaces.
Using a hypothetical generator setup, we could rewrite this as follows (return type omitted for the sake of clarity):
object HashMap!(K: Hash + Equal, V) {
def iter {
@table.buckets.each do (bucket) {
bucket.if_true {
yield *bucket
}
}
}
}
Here we significantly reduced the amount of code we had to write, while still achieving the same result.
Implementation
The exact implementation is still to be decided, but we need at least the following mechanisms:
- Two extra fields on a
ExecutionContext
:managed
, andyielded
. Managed will be set tofalse
by default, andtrue
when using generators. - When popping a context, forget about it (using
std::mem::forget
in Rust) ifmanaged = true
. - The means of running a block with a prepared context, setting
yielded
tofalse
before running. - An instruction to yield values. This acts much like the
Return
instruction, except it sets theyielded
flag of a context totrue
- A way of turning a regular method into a generator, in the least verbose way possible
- When running a
Return
in a managed context, we want to drop the context right away. This doesn't work with the above setup of reusing the context, so we need something special for this.
Drawbacks
Generators will require additional changes in both the compiler and virtual machine. For the compiler, depending on the setup, we may also need to do some kind of source transformation. For example, a generator method returns a generator, not a regular value. We could work around this by requiring developers to explicitly return a generator.