Generators and streams

You have a sequence to produce, and you do not want to build it.

Maybe it is long. Maybe it is endless. Maybe the consumer will look at the first four values and stop. Every language answers this, and every answer costs something: a callback inverts your control flow, an iterator object makes you hand-write the state machine your loop already was, and returning a collection makes you compute all of it to find out you needed four.

Mica’s answer is a generator: a body that runs, produces a value, and stops where it stands until somebody asks for the next one.

The example is examples/Generators. Build and run it:

make -C examples/Generators run

A body that suspends

A generator declares what it produces and emits values instead of returning them:

generator Counting(last : int64) : stream of int64;
var
    i : int64;
begin
    i := 1;

    while i <= last do
    begin
        WriteLn("    body: about to emit %lld", i);
        emit i;
        WriteLn("    body: resumed after emitting %lld", i);
        i := i + 1;
    end;
end;

The consumer is a for-in loop — the same loop you would write over an array:

for n in Counting(3) do
    WriteLn("  loop: received %lld", n);

Run it and the interleaving tells you exactly what emit does:

    body: about to emit 1
  loop: received 1
    body: resumed after emitting 1
    body: about to emit 2
  loop: received 2
    body: resumed after emitting 2
    body: about to emit 3
  loop: received 3
    body: resumed after emitting 3

The body’s line, then the loop’s line, then the body’s line — strictly alternating, every time. emit hands one value over and suspends the body where it stands. The loop body runs. When the loop asks for the next value, the generator resumes on the line after the emit, which is why resumed after emitting 1 appears before about to emit 2.

And notice what is not in that output: no scheduling, no waiting, no concurrency. The generator ran on the consumer’s carrier and only while the consumer was asking. A generator is a call and a return, written the other way round.

The locals are still there

Suspending mid-body is only useful if the body’s variables survive it. They do, and the cleanest proof is a recurrence — a sequence where losing a single local would restart rather than continue:

generator Fibonacci(limit : int64) : stream of int64;
var
    a, b, t : int64;
begin
    a := 0;
    b := 1;

    while a <= limit do
    begin
        emit a;
        t := a + b;
        a := b;
        b := t;
    end;
end;

  fib 0
  fib 1
  fib 1
  fib 2
  fib 3
  fib 5
  fib 8
  fib 13
  fib 21
  fib 34

Ten values, each computed from the two before it across a suspension. a, b and t are ordinary locals of an ordinary body. You did not write a state struct, you did not hoist anything into fields, and you did not mark the function async or yield-coloured — the body is just a body.

That is what stackful means: a suspended generator keeps a real stack, so suspending is cheap to write, at the cost of a stack per live instance. It is the same substrate tasks run on, which is why the two features feel like one idea.

Look at the last line of Fibonacci and note what is missing: there is no “I am done” signal. The body’s end is the stream’s end. When the while loop exits and the body falls off its end, the consumer’s next pull reports exhaustion and the for-in finishes. Producing and terminating are the same piece of code, so they cannot disagree.

An instance you can name

So far every stream has been anonymous: born in the for-in, dead at its end. Give one a name and something more interesting becomes possible.

var
    count : stream of int64;

count := From(10);

firstpass : for v in count do
begin
    WriteLn("  %lld", v);
    leave firstpass when v = 12;
end;

secondpass : for v in count do
begin
    WriteLn("  %lld", v);
    leave secondpass when v = 14;
end;

From is endless — it emits forever — so nothing but you can decide where it stops:

  10
  11
  12
  — the loop above ended; the instance is frozen, not finished —
  13
  14

The second loop resumed at 13. It did not restart at 10 and it did not fail: leaving the first loop early froze the instance, and the second loop thawed it exactly where it stopped.

That works because of one rule with real consequences: a for-in over a variable borrows what the variable owns. The loop opens nothing and closes nothing. Only the variable owns the instance, so only the variable’s fate ends it.

Naming is owning, and one live body can have exactly one owner — which is why you cannot copy a stream variable:

t := s;

a stream variable is bound by a generator call and by nothing else: a stream
names a single live activation, so copying it into 't' would give one frozen
body two owners and its scope death two cancellations — bind with
's := <generator>(...)' and hand the variable itself around instead of a copy

A stream variable is bound by a generator call and by nothing else. This is the same value model as everywhere else in Mica: what looks like a value is a value, and a thing with an identity is not silently duplicated behind your back.

Closing belongs to the owner

If a loop does not close a borrowed instance, who does? Its owner, at two moments: when the owner is rebound, and when the owner’s activation ends.

The example makes that visible with a defer inside the generator body:

generator From(first : int64) : stream of int64;
var
    i : int64;
begin
    defer WriteLn("    from(%lld): closed", first);
    ...

Watch where the cleanup line lands:

Closing belongs to the owner, not to the loop
    from(10): closed
  100
  101

Neither of the two loops above closed anything. count := From(100) did — the rebind closed the live instance before the new one opened, which is why from(10): closed stands at the head of this section rather than at either loop’s end.

That is a promise worth stating plainly: an abandoned generator body is resumed exactly once with its cancellation set, and its deferred statements run. A generator that opened something closes it, whether it ran to exhaustion, was frozen and forgotten, or was crossed by a leave, a fail, or the end of the activation that owned it. defer inside a generator body is not best-effort.

Generators compose

A generator can take a stream as a parameter. That one fact is the whole pipeline story:

generator Take(source : stream of int64, wanted : int64) : stream of int64;
var
    taken, item : int64;
begin
    taken := 0;

    pull : for item in source do
    begin
        emit item;
        taken := taken + 1;
        leave pull when taken >= wanted;
    end;
end;

Take consumes one stream and produces another, so it can stand between any producer and any consumer:

for n in Take(Fibonacci(1000), 4) do
    WriteLn("  taken %lld", n);

for n in Take(From(7), 3) do
    WriteLn("  taken %lld", n);

  taken 0
  taken 1
  taken 1
  taken 2
  taken 7
  taken 8
  taken 9

The second pipeline is the interesting one: From(7) is endless, and only four values of it were ever computed. Take stopped pulling after three, which ended its own stream, which ended the loop. Nothing upstream ran that nobody downstream wanted — laziness falls out of the pull protocol rather than being a feature bolted onto it.

There is no adapter type here, no interface to implement, no allocation between the stages. Take is a generator like any other; source is a parameter like any other.

Try it. Write a Doubling(source : stream of int64) : stream of int64 that emits each value it pulls, multiplied by two, and stack it: Take(Doubling(From(7)), 3). Three stages, and the innermost one still only computes what the outermost one asks for.

Who owns a stage

One detail is worth knowing before you build long pipelines. From(7) above stands as an argument, so no loop and no variable owns it — the activation that wrote it does, and it closes at that activation’s end:

The program's end closes what is still open
    from(7): closed
    from(100): closed

When the same pipeline expression sits inside a loop, each round rebinds that site: the previous round’s instance is closed before the next one opens, exactly as rebinding a named variable does. So a pipeline in a hot loop holds one live upstream instance, not one per iteration.

Generators are not tasks

Both suspend. Both are stackful. They are not the same thing, and mixing them up is the one confusion worth heading off:

A generator is a control-flow construct that happens to use the suspension machinery. Nothing about Counting(3) is concurrent, and its output ordering is not a scheduling result — it is a call sequence.

The two do combine: a generator can run inside a task, and a stream can be fed by a scheduled producer so that pulls and emits genuinely overlap. That is the point where the ordering guarantees of this article stop applying and the carriers article takes over.

What this does not do

A generator cannot be resumed from two places. One instance, one owner. The compiler enforces it at the bind, and the message quoted above is what you get.

A generator is not free. Every live instance holds a stack. That is what buys you an ordinary body with ordinary locals, and it means instances are a resource you own rather than a value you scatter.

There is no stream you can store in a record or hand back from a function. Streams are bound to activations, which is what makes the closing provable.

Pull is the only protocol. There is no push, no subscribe, no backpressure knob. A consumer that stops asking stops the whole chain, which is usually what you wanted, and never what you would have had to arrange yourself.

What the compiler proved

You wrote no state machine, and the locals were still there after every suspension. You wrote no termination protocol, and the sequence ended where the body ended. You wrote no cleanup at the call sites, and every abandoned body still ran its defer — exactly once, at a point you can name.

Next

Carriers, multicore and busy loops — what changes when the program stops running on one carrier: which guarantees survive, which disappear, and what a compute loop that never suspends does to a scheduler.