Streams and delayed evaluation

Lesson 12 left us holding a cure worse than convenient: serializers, mutexes, and deadlock-avoidance orderings, all of it machinery to re-impose the serial order that assignment threw away. We named the disease precisely — mutable shared state plus time. This lesson attacks the disease itself. A stream is a list whose tail is not computed until you ask for it (and then cached) — a pair with a delayed, memoized tail. With that one device we represent infinite sequences, process them with the same map/filter from Lesson 05, and — the headline move — re-express a stateful, assignment-driven system as a stream containing no assignment at all, recovering the functional modularity Lesson 09 made us pay for. And there is a meta-lesson hiding in delay: changing when a tail is computed is changing the language's evaluation rule. If bending one rule buys this much, the next move is to seize the rule wholesale.

1 · The tension: state is a sequence, but the sequence is endless

Lesson 09 modeled a changing balance with one cell rewritten in place: balance = balance - amount. That mutation is precisely what forced a notion of time (Lesson 09) and then detonated under concurrency (Lesson 12). But notice what the balance is across a session: the values 100, 90, 70, 130, … — a sequence. If we could name that whole sequence as a single immutable value, there would be no cell to overwrite and nothing to race on. The obstacle: the sequence is conceptually unbounded — a long-running account has no last balance. A finite list (Lesson 05) cannot hold it, and eagerly computing "all future values" is impossible. We need a list that is finite to build but unbounded to consume: produce each element only when demanded.

2 · delay, force, and the delayed tail

The whole trick is one primitive. A thunk is a zero-argument function wrapping an expression you have not yet evaluated; calling it later runs the expression then. delay(() => expr) takes that thunk and wraps it with memoization; force(thunk) runs it — and memoizes, so a second force returns the cached value without recomputing. (Memoization is safe precisely because the delayed expression is pure — Lesson 04 again earning its keep.)

// A memoizing thunk: compute at most once, then cache.
function delay(thunkBody) {            // in real JS we wrap by hand:  () => expr
  let forced = false, value;
  return function () {
    if (!forced) { value = thunkBody(); forced = true; }   // run ONCE
    return value;                                          // reuse forever
  };
}
const force = (thunk) => thunk();

// A stream is a PAIR: an eager head, and a delayed (memoized) tail.
const stream_cons = (head, delayedTail) => ({ head, tail: delayedTail }); // tail is a thunk
const stream_head = (s) => s.head;
const stream_tail = (s) => force(s.tail);          // forcing computes the next pair on demand
const empty = null;
const is_empty = (s) => s === empty;

The asymmetry is the entire idea: the head is computed now, the tail is computed only when forced, and once forced its value is cached. So a stream looks like an ordinary pair but unfolds lazily — touching stream_head never triggers the rest of the sequence. Note carefully: stream_cons can't be an ordinary function call, because JavaScript would evaluate the tail argument before the call. The tail must be wrapped in delay (a () => …) at every construction site, so the delay is never sprung prematurely.

ones = stream_cons(1, delay(() => ones))      // a stream that is 1, 1, 1, …

ones                      ⇒ { head: 1, tail: <thunk, not run> }
stream_head(ones)         ⇒ 1                  (no tail forced)
stream_tail(ones)         ⇒ force(thunk) ⇒ ones again   (now cached)
stream_head(stream_tail(ones)) ⇒ 1

Only the thunks you force ever run. An infinite stream sits in memory as
ONE pair plus a promise to make the next — never the whole sequence.

3 · Stream versions of the conventional interface

Lesson 05 gave us map/filter as a signal-flow pipeline over finite lists. The stream versions are the same operations, rebuilt to honor the delayed tail: do the head's work eagerly, and wrap the recursive call on the tail in a fresh delay so the pipeline itself stays lazy.

function stream_map(f, s) {
  if (is_empty(s)) return empty;
  return stream_cons(f(stream_head(s)),               // transform the head now
                     delay(() => stream_map(f, stream_tail(s))));  // defer the rest
}
function stream_filter(pred, s) {
  if (is_empty(s)) return empty;
  const h = stream_head(s);
  return pred(h)
    ? stream_cons(h, delay(() => stream_filter(pred, stream_tail(s))))
    : stream_filter(pred, stream_tail(s));            // skip; recurse on tail
}
function stream_ref(s, n) {                            // the nth element, 0-indexed
  return n === 0 ? stream_head(s) : stream_ref(stream_tail(s), n - 1);
}

This is the payoff Lesson 05 promised, now without a length limit: you compose stream_map and stream_filter into a pipeline, and demand drives it — asking for the 5th result pulls exactly enough through each stage to produce 5 elements. The signal-flow metaphor finally describes a true on-demand signal rather than a batch.

4 · Infinite streams: integers and primes

Because the tail is delayed, a stream may refer to itself and so be infinite. Define the integers, then sieve them into primes.

function integers_from(n) {
  return stream_cons(n, delay(() => integers_from(n + 1)));   // n, n+1, n+2, …
}
const integers = integers_from(1);          // 1, 2, 3, 4, …  (built lazily)

// Sieve of Eratosthenes as a stream: the head is prime; filter its multiples
// out of the tail, then sieve what remains.
function sieve(s) {
  const p = stream_head(s);
  return stream_cons(p, delay(() =>
    sieve(stream_filter((x) => x % p !== 0, stream_tail(s)))));
}
const primes = sieve(integers_from(2));     // 2, 3, 5, 7, 11, …
stream_ref(primes, 0); // 2
stream_ref(primes, 4); // 11   — only as many integers as needed are ever produced

primes = sieve(2,3,4,5,6,7,…)
 head = 2;  tail = delay( sieve( filter(not-mult-of-2, 3,4,5,6,7,…) ) )
forcing the tail once:
   filter(not-mult-of-2, …) ⇒ 3,5,7,9,11,…          (4,6 dropped lazily)
   sieve(3,5,7,…) ⇒ head 3; tail = delay( sieve( filter(not-mult-of-3, 5,7,9,…) ) )
 → 3,5,7,11,…  (9 will be dropped when the not-mult-of-3 filter reaches it)

5 · The headline move — a stateful system with no assignment

Here is the lesson's center of gravity. Lesson 09's account threaded a balance through time by mutating one cell. We can produce the very same sequence of balances as a stream, with no let-rebinding, no = after the first, and therefore nothing to share or lock. Given a stream of transaction amounts (positive deposits, negative withdrawals), the balances are the running sums:

// IMPERATIVE (Lesson 09): time lives in a mutated cell; concurrency-fragile.
function make_account(balance) {
  return function withdraw(amount) { balance = balance - amount; return balance; };
}

// FUNCTIONAL (this lesson): time IS the stream index. No assignment anywhere.
function add_streams(a, b) {                 // elementwise sum of two streams
  return stream_cons(stream_head(a) + stream_head(b),
                     delay(() => add_streams(stream_tail(a), stream_tail(b))));
}
function scan(f, init, s) {                   // running fold: emits each partial result
  return stream_cons(init,
    delay(() => scan(f, f(init, stream_head(s)), stream_tail(s))));
}
// the balance history is just a running sum of the transaction stream:
const balances = (init, txns) => scan((acc, t) => acc + t, init, txns);
// balances(100, stream[−10, −20, +100, …])  ⇒  100, 90, 70, 170, …

Read what changed. The mutable balance cell is gone; "the balance after k transactions" is just stream_ref(balances, k) — an index into an immutable sequence. There is no cell two processes can interleave on, so the entire Lesson 12 apparatus — serializers, mutexes, deadlock ordering — evaporates: you cannot have a lost update on a value that is never updated. The notion of time hasn't vanished; it has been made explicit and harmless, relocated from a hidden mutation-order into an honest position in the stream. This is exactly the functional modularity Lesson 09 spent to buy state — now recovered, with state modeled instead of mutated.

6 · The meta-point — delaying a tail changes the evaluation rule

Step back from accounts and primes to what delay actually did. JavaScript's default rule is applicative order: evaluate every argument before the call. stream_cons deliberately broke that rule for one argument — the tail is not evaluated at the call; it waits for force. We changed when an expression is evaluated, and from that single change flowed infinite data, on-demand pipelines, and an assignment-free model of state. That is a startling amount of leverage from bending one evaluation rule by hand, at one position, with a hand-written thunk at every call site.

Which raises the obvious question: if reaching in and altering when things evaluate is this powerful, why keep doing it manually, one delay at a time? The real power is to control evaluation wholesale — to own the rule that decides how every expression is evaluated. To own that rule, you must first build the thing that applies it: an evaluator for the language, written in the language. That is the next lesson.

Common mistakes / failure modes

Checkpoint exercise

Where this points next

We cured the concurrency disease by removing the assignment that caused it — modeling state as an immutable delayed sequence so there is no cell to race on. But the technique exposed something larger than streams. The single act that powered all of it was delay: changing when an expression is evaluated. We did it by hand, one tail at a time, and it bought infinite data and assignment-free state. The unmistakable implication is that controlling evaluation is the deepest lever in the language — and to control it generally rather than locally, we must build the machine that performs evaluation. Lesson 14 takes that step: the metacircular evaluator, a program that reads expressions and evaluates them, written in the very language it evaluates. Once you own the evaluator, "delay this tail" becomes a one-line change to a rule — and so does normal-order, lazy, nondeterministic, and logic evaluation. Bending the rule by hand was the appetizer; writing the rule is the meal.

Interview prompts

• What exactly is a stream, and how does it differ from a list? (§2 — a pair with an eager head and a delayed, memoized tail; unlike a list it computes each element only on demand and so can be infinite, existing at any instant as one pair plus a pending thunk.)
• What do delay and force do, and why must force memoize? (§2 — delay wraps an expression as an unevaluated thunk; force runs it; memoization caches the result so a recursive/self-referential stream doesn't recompute earlier tails and blow up exponentially — safe because the expression is pure.)
• Why must stream_cons not be an ordinary function call? (§2 — JS uses applicative order and would evaluate the tail argument before the call, springing the delay and looping on infinite streams; the tail must be wrapped in a delay/() => … at every call site.)
• Show how the sieve of Eratosthenes produces primes as a stream. (§4 — head is prime; filter its multiples out of the tail lazily, then sieve the remainder; no multiple is produced-then-discarded eagerly — each filter applies only as a tail is forced.)
• Re-express a bank account as a stream with no assignment — what concretely goes away? (§5 — balances are a running fold (scan) over the transaction stream; "balance after k txns" is stream_ref(balances,k); the mutable cell disappears, so there is nothing to interleave on and the serializer/mutex/deadlock machinery is unnecessary.)
• How do streams "cure" the concurrency disease of Lesson 12? (§5 — they decouple computation order from event order by modeling state as an immutable sequence; with no value ever updated there can be no lost update, so time is made explicit and harmless instead of hidden and racy.)
• What is the meta-point of delay, and why does it force the metacircular evaluator? (§6 — delaying a tail changes when an expression evaluates, i.e. bends the evaluation rule by hand at one spot; to control evaluation generally you must build the evaluator itself, which Lesson 14 does.)