RFC: Loops and iterators

A requirement of window aggregation (#308) is to be able to iterate over events in a window and aggregate them.

Loops

There are three kinds of loops which should ideally be supported:

for <pattern> in <expression> <block>
- Note: <expression> must evaluate into an iterator.
while <expression> <block>
- Note: <expression> must evaluate into a boolean.
loop <block>
- Note: Infinite loop

There are also two kinds of control-statements:

continue
break

Of these constructs, only loop and break need to be supported in Arc-MLIR (assuming that we have mutability and if-else expressions). Everything else can be represented in terms of loop and break. It might still be beneficial to support continue since it makes life easier in the compiler.

Loop Desugaring

Loops are desugared as follows:

While-loops desugaring

while <expression> <block>

becomes

loop { if <expression> <block> else { break; } }

For-loop desugaring

for <pattern> in <expression> <block>

becomes

loop { if let Some(<pattern>) = <expression>.next() <block> else { break; } }

Continue desugaring

loop {
    if <expression> {
        continue;
    } else {
        break;
    }
}

becomes

loop {
    var break_loop = true;
    loop {
        if <expression> {
            break_loop = false;
            break;
        } else {
            break;
        }
    }
    if break_loop {
        break;
    }
}

Iterators

Iterators can be represented as abstract data types:

extern type Iterator[T]() {
    fn next() -> Option[T];
}

and implemented in Rust as:

pub struct Iterator<T> {
    pub concrete: std::rc::Rc<std::cell::RefCell<dyn Iterator<Item = T>>>,
}

impl<T> Iterator<T> {
    pub fn next(self) -> Option<T> {
        self.concrete.borrow_mut().next()
    }
}

Anything iterable (ranges, vectors, strings) can be converted into an iterator. Since we do not have overloading yet we might need to create explicit methods for each. One consideration for later may be if iterators can be used as streams.

cda-group / arc