Effect Branches vs LINQ: Iteration as a Checked Protocol

Ask two languages “how do I do something for each element?” and you get two different inventions.

LINQ’s answer is a value. An IEnumerable<T> is an object — you can hold it, pass it to a function, compose Where over Select over Take, defer it, run it twice, or hand the whole expression tree to a provider that turns it into SQL. The query is the data structure.

Koru’s answer is a protocol. A tor declares ! effect branches — pulses it may fire — and | terminal branches — the outcomes it must end in. The consumer’s arms are spliced into the producer’s call at compile time. There is no iterator object; the choreography itself is the checked surface, and exhaustiveness means every declared pulse has a handler and every declared required outcome has an arm (| ?done marks the optional ones).

Same problem, different placement of the contract. This post is the Rosetta stone — for readers who think in LINQ — plus the codegen difference that decides what an optimizer may see, honest benchmarks, and a measured list of what Koru still can’t say. Every Koru sample is a pure .k file — including the producers, which are Koru subflows, not host procedures.

The claim, measured first

Here’s the task both sides ran — filter, map, sum, the shape that covers most of what LINQ gets written for:

int[] data = Enumerable.Range(1, 10_000_000).ToArray();
data.Where(x => x % 2 == 0).Select(x => x * 3L).Sum()

capture { sum: 0[i64] }
! as acc |> for(1..(n + 1))
    ! each i when i % 2 == 0 |> captured { sum: acc.sum + @as(i64, @intCast(i)) * 3 }
| captured c |> std/io:print.ln("{{ c.sum:d }}")

Where → the when guard on the arm. Select → the * 3 in the capture write. Sum → capture, the declared accumulator — and | captured is where it escapes, here into the checksum. Two disclosures the snippets owe: data is a materialized int[] — LINQ’s best case, the array-specialized path; the same filter over lazy Enumerable.Range, the true source-equivalent of for(1..(n+1)), measured 20.7ms in the producer row below. And | ?captured is declared optional on capture’s contract — arm it to read the result, omit it to drop it; the benchmark arms it because the sum is the point. The other rows: yield producers vs !-pulse tors (a -> on the arm is a resume value — the consumer answers the producer mid-iteration), FirstOrDefault vs an early-exit resume flag. More ceremony at the call site — and the numbers say what the ceremony buys:

10M integers, same machine, .NET Release vs koruc → Zig ReleaseFast, std/benchmarking:run timing windows, results consumed into a printed checksum so the work can’t be optimized away. Three honest reads. LINQ-to-Objects is genuinely good on arrays — specialized iterator paths keep it within ~1.3x of a hand loop. A yield producer roughly triples the cost: the state machine, the enumerator allocation, the virtual dispatch per element. And the Koru pulse runs at-or-below the hand loop because it is a direct call — ~0.6ns per element including the resume round trip — while comptime-visible bounds let LLVM fold ~4× further. The early-exit row’s analytic number (~0.75ms) shows the optimizer partially solving the “find i == target” scan even at runtime bounds; the hash-predicate number (~1.8ms for ~2.7M actual visits) is what a genuinely unpredictable early exit costs — still under LINQ’s constant-predicate scan.

A confession on the fold column. An earlier run of this benchmark measured ~15ns per pass and looked like total constant folding. It was dead-code elimination: the producer results were computed and discarded, so LLVM deleted the entire 10M-element pipeline — exactly what it does to unused arithmetic, and exactly what it can’t do to a LINQ Sum() whose enumerator’s virtual calls aren’t provably side-effect-free. The numbers above keep every result observable — which is also how we know the work is real.

The rest of this post is the model that produces those numbers — the grammar rows first, then the codegen that explains the fold, then what’s genuinely missing.

The translation table

yield / IEnumerable — the producer is a tor, and its body is a subflow. C#‘s yield return hides a compiler-generated state machine. Koru declares the pulse on the tor’s contract — and implements the producer in Koru, no host code:

pub tor gen { n: usize }
! each usize
| done usize

gen = for(0..n)
! each i |> each(i)
| done => done n

gen(n: 3)
! each i |> std/io:print.ln("{{ i:d }}")
| done _ |> _

gen’s impl is a for: when for fires ! each, the impl fires its own each(i) — firing is a call. When for ends in | done, the impl maps it to its own terminal: => done n. The consumer arms ! each (once per element) and | done (once, with the payload) — and cannot drop either; that’s exhaustiveness, not politeness. The option is declared too: for’s own terminal is | ?done — an optional branch the impl could leave unarmed — while gen’s | done is required. Required vs optional lives on the contract, not in a docstring.

Where(pred) — the arm carries a when guard. Filtering isn’t an operator on a sequence; it’s a condition on the arm. Over for’s builtin ! each source it looks like this — from the benchmark program, pure .k:

for(1..10_000_001)
! each i when i % 2 == 0 |> ...

An unmatched fire isn’t an error — it’s a filter, the same way Where skips an element. The guard works on custom pulses too (inside evens’s impl below, ! each i when i % 2 == 0 decides which elements become ! item pulses).

Select(f) — the arm body is the projection, and -> sends a value back. LINQ lambdas are one-way: elements flow out, nothing flows back mid-enumeration. A Koru effect branch can declare a resume type — ! ask i64 -> i64 — so the arm’s -> produces a value the producer receives at the fire site:

pub tor query { q: i64 }
! ask i64 -> i64
| done i64

query = ask(q): a => done a

query(q: 41)
! ask v -> v + 1
| done r |> std/io:print.ln("{{ r:d }}")

query fires ask(41), the consumer’s arm answers 42, the producer binds it (: a) and returns it as | done. Two-way choreography per element — MoveNext has no channel for this. And the resume can itself be a union: ! ask i64 | result { halved: i64, quadrupled: i64 } | timeout lets the consumer pick which branch answers the fire — a query that can ask its caller a multiple-choice question.

Sum/Aggregate — the accumulator lives inside the pipeline. LINQ’s Sum consumes the stream from the outside. In Koru the producer can own a capture and let the consumer’s -> resume feed it — the sum is computed by the pipeline, not after it. This is the actual benchmark producer, compiled and run this session, pure .k:

pub tor evens { n: usize }
! item i64 -> i64
| done i64

evens = capture { sum: 0[i64] }
! as acc |> for(1..(n + 1))
    ! each i when i % 2 == 0 |> item(@as(i64, @intCast(i))): t |> captured { sum: acc.sum + t }
| captured c => done c.sum

evens(n: 10)
! item v -> v * 3
| done total |> std/io:print.ln("total {{ total:d }}")   // prints 90

The producer loops evens, fires ! item, the consumer maps each to v * 3 — and the resume value feeds the producer’s own capture. | done returns the total. Filter + map + sum in one declared protocol, on both sides of the fire.

FirstOrDefault — early exit is a resume flag, and the miss is a branch. First throws; FirstOrDefault returns a sentinel you can drop on the floor. Koru’s -> bool resume lets the consumer signal “stop”; for’s keep: reads a captured flag per iteration; | found/| done are exhaustiveness-forced so the miss cannot be dropped:

pub tor scan { n: usize }
! visit i64 -> bool
| found i64
| done

scan = capture { stop: 0[i64], hit: -1[i64] }
! as c |> for(0..n, keep: c.stop == 0)
    ! each i |> visit(@as(i64, @intCast(i))): keepgoing
        |> captured { stop: @as(i64, @intFromBool(keepgoing == false)), hit: @as(i64, @intCast(i)) }
| captured fin |> if(fin.stop == 1)
    | then => found fin.hit
    | else => done

scan(n: 10_000_000)
! visit v -> v != 2
| found f |> std/io:print.ln("found {{ f:d }}")
| done |> std/io:print.ln("not present")

It’s a convention — First isn’t a builtin — but every piece is checked: the stop flag, the guard, the two terminal arms.

FirstOrDefault on a store — the miss is a named branch. The store query’s | none arm is the same idea at the stdlib surface: you cannot silently drop the absent case.

std/store:query(players)
    ! first p when p.key == 30 |> std/io:print.ln("moved {{ p.val:d }}")
    | none |> std/io:print.ln("moved LOST")

And the whole pipeline composes — the prime sieve shows for ! each, a guard, a nested pulse, and a when-guarded sweep accumulating into a store, in one real pure .k program:

std/grid:sweep(sieve)
! sweep c when c.composite == 0 |> std/store:stored { acc.n: acc.n + 1 }

Two ways to codegen an iterator

Here’s where the models diverge underneath — and it’s the part that decides what an optimizer is allowed to see.

C# rewrites yield into a state machine. This is the producer from the benchmark — innocent-looking source:

static IEnumerable<int> EvensTo(int n)
{
    for (var i = 2; i <= n; i += 2) yield return i;
}

The compiler rewrites it into a synthesized private class — <EvensTo>d__ — implementing IEnumerable<int> and IEnumerator<int>, with fields for the machine state (<>1__state), the current element (<>2__current), and the captured parameter. Every element costs a MoveNext() call through a switch dispatch on the state field. The JIT sees an opaque object with an interface method; the pipeline is invisible by construction.

Koru splices the consumer into the producer. The ! arm lowers to a comptime handler type — __H. This is the actual emitted Zig for evens’s subflow impl above (whitespace-normalized; identifiers untouched):

for (1..(n + 1)) |__koru_item_0| {
    { const i = __koru_item_0; _ = &i; if (@rem(i, 2) == 0) {
        const t = __H.item(@as(i64, @intCast(i)));
        _ = &t;
        acc.sum = acc.sum + t;
    } }
}
const c = acc;
return .{ .done = c.sum };

Read it the way the optimizer does: a for with a known trip-count expression (vectorizable), the when guard as a plain if, the fire as a direct, statically-known call __H.item(...), the -> resume as a bound const, the => terminal as a union return. No enumerator object, no MoveNext dispatch, no heap allocation — the whole produce→consume→produce-back round trip is inline code. And scan’s early exit emits the honest thing: if (!(c.stop == 0)) break; inside the for, with => found/=> done becoming return .{ .found = … } / return .{ .done = … }.

And that is where the table’s two Koru columns come from. With the trip count comptime-visible, LLVM partially folds the pipeline — the ~4× in the right column. With the bound forced opaque (derived from argc), the pulses run for real — the ~0.6ns-per-element middle column. LINQ’s dispatch model makes even the partial fold impossible in principle: IEnumerator.MoveNext is an interface call the JIT cannot see through, and a yield enumerable allocates its machine before the first element. Same visibility, one more corollary — the dead-code elimination described above: a pipeline whose results go unused is dead arithmetic, and it gets deleted like any other.

What LINQ still says that pulses don’t

Measured this session — every row compiled, not claimed:

Three rows are bugs, not design: capture wrapping a custom pulse (400_098), std/store sites inside a user-defined ! arm (690_332), and an arm written at the wrong continuation level being discarded without a diagnostic (400_195 — pinned this session; ticker’s declared | done went unhandled and the compiler emitted _ = __koru_eff_disc_0 instead of refusing). All one family: the compiler’s arm/site bookkeeping loses things inside nested continuations. The std-provided sources work fine; the fold just doesn’t reach everywhere yet.

The deepest row is the last-but-one: a pulse protocol is not a value. You cannot store half a query in a variable, return it from a tor, or compose it lazily. LINQ’s deferred, composable, pass-around-able query is the thing the whole design pays for — and the thing IQueryable needs to remote a plan to a provider. Koru doesn’t have that concept today; whether it wants one is a design question, not an oversight.

What pulses say that LINQ can’t

Fairness runs both ways, and the reverse column is not empty:

• The miss is forced. | none, | done, | out-of-bounds are declared outcomes — dropping them is a compile error. FirstOrDefault’s sentinel is droppable by design.
• -> is a back-channel. The consumer answers the producer mid-iteration — MoveNext has nothing like it. And the answer can be a union (| result | timeout), so the producer’s question is multiple-choice.
• The producer can ask “is anyone listening?” An optional arm (! ?note) can be tested at comptime inside the impl — gen = for(0..n) ! each i when note |> note(i) fires only when the consumer installed the handler, and skips evaluating the payload entirely when nobody did. There is no C# spelling for “don’t compute this element if it’s unobserved.”
• Effects are declared. A ! pulse is on the tor’s contract; a LINQ lambda’s side effects are invisible.
• The plan explains itself. store:explain reports sweep-vs-index per query site, using the transform’s own fold — EXPLAIN in LINQ-land is a database tool, not the language.
• The pipeline is optimizer-visible — and eliminable. Bounds-visible pipelines fold; un-consumed pipelines are deleted like dead arithmetic.

Does this mean the language grows?

The honest answer after compiling every row: mostly no, and the parts that are yes aren’t syntax.

The three broken rows are one defect — bookkeeping that loses arms, captures, and transform sites inside nested continuations — and that’s an src/ fix with pins already in the suite. The buffered operators (OrderBy, GroupBy, Distinct) and the multi-source shapes (Join, Zip) are expressible today as conventions over std/list and stores; making them feel like operators is a combinator vocabulary in std/, not grammar. The one genuinely structural gap — the query as a passable value — is a design question worth its own ruling, and it rhymes with the !-branches-for-protocols work parked elsewhere: whether the pulse protocol becomes a named convention anything can produce and transforms can compose over.

What did change while writing this post is a refusal, not a feature. | done |> _ on for’s optional | ?done had spread to 68 sites across the suite by cargo-cult — arming an optional branch only to discard it adds nothing an omitted arm doesn’t already mean, and silently satisfies the obligation if the branch is ever promoted to required. It’s now a compile error (KORU054, the terminal-side twin of KORU037, which already refused the same wart on optional effects). Deleting the warts surfaced a fourth, latent defect: the compiler synthesizes the omitted arm’s replacement downstream, but the for template’s rendered body had frozen against the arm list as it was before the synthesis — the discharge existed in the AST and emitted nothing. Fixed and pinned by 330_046 in its now-legal omitted spelling. So the section’s answer holds literally: nothing new to say, one more thing you’re no longer allowed to say wrong.

And the pure-.k question that started this round has a clean answer: producers don’t need host procedures at all. gen = for(0..n) ! each i |> each(i) | done => done n is the whole generator — the subflow impl, the resume binds, the presence tests, and the => terminal maps are all shipped grammar, pinned in 400_131 through 400_147. What remains host-side is inside std/ itself — and the rule stays: where the .k surface can’t say it, the post says so rather than hiding a ~proc.

LINQ is a feature: a beautiful, battle-tested way to make one domain feel native. Effect branches are a medium: the same mechanism does iteration, store queries with reported plans, time pulses, and protocol obligations — each branch kind mapping to a message type in a checked conversation. Different bet, different ceiling.

Grounding: regression pins cited inline — 400_131, 400_132, 400_135, 400_146, 400_147, 400_072, 400_087, 2105_prime_sieve, 690_327, 690_330, 330_046, 400_197 (green), 400_098, 690_332, 400_195 (aspirational). Benchmarks are session artifacts — the C# harness (dotnet 9.0.100, Release) and the pure-.k programs (koruc → Zig ReleaseFast, std/benchmarking timing windows) measured this session on Apple Silicon at N=10M; numbers in the table are per-pass means from the timing windows.