Feature request: an early-terminating iteration form (while / conditional fold)

[vbmithr]

Observed on a rayforce-git build of dev: 2.6.2.r219.g88c03a90.

---

Summary

Rayfall has no way to stop iterating before the end of a sequence. Every
iteration primitive visits every element, and there is no loop construct, so a
"repeat until done" loop has to be written as a fold over a fixed range whose
full length is paid on every call — however early the work actually finishes.

We would like an early-terminating iteration form: a while special form, a
conditional fold, or the While form of a fold/scan operator. Any one of them
solves it.

Why this cannot be expressed today

Control flow has no loop. Per the function reference, the Control Flow &
Special Forms section is set, let, if, do, fn, try, raise,
return, quote, alter, del. There is no while, do[n;...], or
until.

Every iteration primitive is exhaustive. map, pmap, fold,
fold-left, fold-right, scan, scan-left, scan-right and prior all
consume the whole input. None takes a predicate that can stop them.

return does not help. It exits the lambda, not the iteration. The fold
keeps going and calls the lambda for every remaining element:

(set n 0)
(set probe
  (fn []
    (fold-left (fn [acc i] (do (set n (+ n 1)) (if (> i 3) (return 'early) (+ acc i)))) 0 (til 10))))
(show (list 'result (probe) 'lambda_calls n))
;; => (result early lambda_calls 10)

Ten invocations, though the work was finished after four.

Recursion is not an alternative. Rayfall has no tail-call elimination and
the stack tops out between roughly 1000 and 2000 frames (measured), so a
recursive loop over a queue of unbounded length overflows. That is what pushed
us to the bounded fold in the first place.

What it costs us

We run a market-data service in Rayfall that drains a queue of completed
messages on every incoming batch. The natural shape is "process one wave,
repeat until nothing is left". Written with the tools available, that is:

(set DRAIN_STEPS 4096)
(set loop_
  (fn [step]
    (fold-left (fn [more _i] (if more (step) false)) true (til DRAIN_STEPS))))

DRAIN_STEPS is a safety bound for a pathological batch, not a step count we
expect to reach — a normal batch drains in a handful of steps. But the fold
cannot stop, so every call:

• allocates a 4096-element range, and
• evaluates (if more ... false) 4096 times, almost all of them after the
  drain has already finished.

At our ingest rate (~107 batches/s) that is roughly 440,000 interpreted lambda
invocations per second whose only purpose is to re-establish that there is
nothing left to do, plus a discarded 4096-element allocation per batch. It is
visible in a perf profile of the running service.

The workaround, and why it is not a fix

We now nest two folds of 64, so an early finish costs one block plus a pass of
the outer fold (~128 iterations) instead of 4096:

(set DRAIN_BLOCK (til 64))
(set DRAIN_BLOCKS (til (max 1 (div (+ DRAIN_STEPS 63) 64))))
(set loop_
  (fn [step]
    (if (fold-left
          (fn [more _b]
            (if more (fold-left (fn [m _i] (if m (step) false)) true DRAIN_BLOCK) false))
          true DRAIN_BLOCKS)
        (set drain_truncations (+ drain_truncations 1))
        null)))

This is a 32x improvement and still the wrong thing. It is not zero, the block
size is an arbitrary constant traded against the bound, and the bound now has
to be rounded up to a multiple of the block size so a tuned value is not
silently lowered. None of that would exist with a loop that stops.

What we are asking for

Any one of these would be enough, in rough order of preference:

1. A while special form — (while cond-fn body-fn), iterative, no stack
   growth.
2. A conditional fold — e.g. (fold-while pred f init xs), stopping at the
   first element where pred fails.
3. A converge / While form on the existing fold family, matching how /
   already works in q.

The first is the most direct fit for "repeat until done", where there is no
sequence to fold over in the first place — the range in our code is pure
scaffolding.

Prior art

q, whose vocabulary Rayfall already mirrors closely (fold, scan, prior,
map), provides all three shapes:

while[cond; body]        / statement form
do[n; body]              / bounded statement form
f/[x]                    / Converge: until the result stops changing
n f/[x]                  / Do: exactly n times
{x<100} {x*2}/[1]        / While: until the condition fails  -> 128

The While form of Over is exactly the missing construct: iterate until the
step says stop. It terminates on the condition, allocates no range, and does
not recurse.

Given fold-left, scan and prior already exist with q-like semantics, this
would extend the existing vocabulary rather than introduce a new concept.

Secondary note: stack depth

Worth flagging alongside: the absence of tail-call elimination is the root
reason the loop cannot simply be recursive. Either an early-terminating loop
form or TCE would remove the need for a step bound entirely. A loop form is
the smaller and more predictable change, which is why it is the request here.

[singaraiona]

Confirmed, all of it. Thanks for the unusually precise write-up — the repro made this quick to verify against the tree rather than take on faith.

What I checked

No loop construct. The special forms registered in src/lang/eval.c are exactly the list you quote — set, let, if, do, fn, try, raise, return, quote, alter, del. do is sequencing (progn), not a bounded do[n; ...]. There is no while, until, converge or fixpoint primitive anywhere in src/ or the docs.

Every iterator is exhaustive. ray_fold_fn (src/ops/collection.c:513) is an unconditional for (i = 0; i < len; i++) whose only exit before the end is an error return. fold-right, scan, scan-left and the map helpers have the same shape. Nothing takes a predicate.

return does not stop the fold. Ran your probe verbatim on a current dev build:

(result early lambda_calls 10)

Exactly as you reported. return is a normal function, not an unwind signal the fold observes, so the fold runs the lambda for all ten elements.

One thing your write-up understates

fold routes its collection through unbox_vec_arg → to_boxed_list (src/lang/eval.c:372). So (fold-left f init (til 4096)) does not just allocate a 4096-element I64 range — it also allocates 4096 boxed atoms plus a LIST on every call, because the fold body wants boxed elements.

At your ~107 batches/s that is roughly 450k throwaway heap objects per second on top of the ~440k interpreted lambda invocations. Your perf profile is measuring something real, and it explains why the nested-64 workaround bought you 32x: it shrank the boxed list, it did not make the loop any smarter.

Direction

We are going to add your option 1, a while special form. Reasoning:

• It is the smallest change — a RAY_FN_SPECIAL_FORM sitting next to if/do, evaluating the condition in the caller's environment and the body for effect, iteratively. No stack growth, no range allocation, no boxing, no new concept in the language.
• It is the right shape for your actual problem. In the drain loop there is no sequence to fold over; the til is pure scaffolding, so a fold-shaped fix would still be working around the absence of a loop.
• fold-while is more invasive for less benefit: an extra predicate call per element through the call machinery, and the boxing cost stays.
• The While/Converge form on the fold family is the most elegant of the three and the one we would want eventually, but it implies a general adverb mechanism that does not exist yet. That is a design commitment, not a bug fix, and it should not gate this.

On the secondary note: agreed that TCE would independently remove the need for a step bound, and agreed it is the larger and less predictable change. We are treating it as a separate track and not blocking the loop form on it.

I will follow up here with the PR. When it lands, your drain becomes a plain while with no DRAIN_STEPS, no block size, and no truncation counter.

[singaraiona]

PR up: #590.

(while cond body...) — evaluates cond, and while truthy evaluates each body expression in order, then tests again. Returns null. A body-less form is legal, so your drain becomes:

(set loop_ (fn [step] (set more true) (while more (set more (step)))))

No DRAIN_STEPS, no block size, no drain_truncations.

It is implemented on both evaluators — ray_while_fn for the tree walker and a real sf_while case in the bytecode compiler, which emits JMPF over a backward JMP. That second part matters for you beyond speed: because the body compiles inline rather than through a dynamic eval, return inside a while body still exits the enclosing lambda instead of degrading to the identity return you documented. And the VM's op_jmp already had an interrupt check gated on a negative displacement, dormant for want of a loop, so Ctrl-C breaks out of a runaway while with no new machinery.

Measured on your drain shape — 4-step drain under the 4096 bound, release build, driver baseline subtracted:

drain form	µs/batch	vs fold-left
fold-left over (til 4096)	1420	1×
nested 64×64 workaround	45.8	31×
while	3.8	374×

The middle row lands on 31×, which independently reproduces your reported 32×. At ~107 batches/s the original form was spending ~150 ms of CPU per wall-clock second re-establishing that there was nothing left to do; while spends ~0.4 ms.

One design note worth stating since it is observable. while pushes no scope of its own, so a let in the body binds in the enclosing frame and survives the iteration — which is what makes let usable as a loop variable:

((fn [n] (let i 0) (let acc 0) (while (< i n) (let acc (+ acc i)) (let i (+ i 1))) acc) 4)  ; => 6

The alternative, a fresh frame per pass, would have worked in a compiled lambda (where let writes a function-level slot) and hung in the tree walker (where let binds only in the top frame), so the two evaluators would have disagreed on identical source. When you do want per-iteration isolation, (while cond (do ...)) composes — do is the thing that pushes a scope.

Docs updated in language/control-flow.md and the function reference. Tests are in test/rfl/lang/while.rfl, asserting each behaviour on both paths.

do[n; ...], fold-while, the converge/adverb forms and TCE remain out of scope, as discussed above.

[singaraiona]

The other two forms from your list are up as #594, stacked on #590.

Bounded loop — (times n body...). Named times rather than do[n; ...] because do is already progn here. Overloading it on an integer head would have been ambiguous: (do 5) would have to mean either "loop five times over nothing" or "return 5", and a computed first expression that happened to be an integer would silently change meaning.

(times 5 (set n (+ n 1)))

The count is evaluated once on entry, so the bound is fixed however the body mutates its source. Zero or less runs zero times rather than trapping. Like while, it compiles to a real loop, so return inside the body still unwinds the lambda.

Conditional fold — (fold-while pred f init xs). The predicate receives the accumulator, tested before each step including the first:

(fold-while (fn [acc] (< acc 100)) + 0 (til 1000))   ; => 105

Your wording ("stopping at the first element where pred fails") reads either way, and I went with the accumulator because that is the form that expresses iterate until the running result says stop — the While-Over shape you pointed at as the missing construct. A predicate on the element would be a fused take-while, which cannot stop based on what the fold has computed so far.

One thing from your report deserves credit here. You noted the fold allocates the range; it also boxes it — fold runs its collection through to_boxed_list, so every element becomes a heap object before the first step. fold-while pulls elements one at a time instead, which is where the numbers come from:

	per call
fold-left stopping after 3 of 1e6	369 ms
fold-while same	3.9 µs	~95 000×

times is a smaller win over a hand-rolled while counter — 100 ns/pass against 180 ns over a million passes — since it drops one builtin call per pass.

That covers all three shapes you asked for. Converge / the While form on the fold family, and TCE, remain open; if the adverb form still matters to you once these land, that is worth its own issue, since it implies a general adverb mechanism rather than a single primitive.