Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 38 ยท Continuations and Tail Calls

Generators and Coroutines

Build generators and coroutines from continuations, use Racket's racket/generator library, and model the same ideas with JavaScript generators in runnable stand-ins.

A generator is a function you can pause and resume. Each time you ask it for a value, it runs until it produces one, then freezes with all its local variables intact until you ask again. A coroutine is the two-way version: two or more routines hand control to each other, each remembering where it left off.

These are exactly the things full continuations make easy: pausing means saving the continuation, and resuming means calling it. In this lesson you will see the idea in Racket, use the ready-made racket/generator library, and run JavaScript stand-ins built on function*, which is JavaScript's own limited form of the same feature. It continues from call/cc and Escapes.

Racket code is shown read-only. JavaScript's generators are a stand-in: they model the control flow, but they are not continuations (you cannot copy and resume a JavaScript generator from the same point twice).

Generators in Racket

You do not have to write continuation code by hand. The standard library provides generator and yield:

RACKET
(require racket/generator)

(define counter
  (generator ()
    (for ([i (in-range 1 4)])
      (yield i))
    'done))

(counter) ; => 1
(counter) ; => 2
(counter) ; => 3
(counter) ; => 'done

Each call to (counter) resumes the body after the last yield. When the body finishes, its final value is returned (and later calls keep returning it). in-generator turns a generator into a sequence usable in for loops, so a generator can feed any for/list or for/sum.

RACKET
(for/list ([x (in-generator
               (for ([i (in-range 5)]) (yield (* i i))))])
  x)
;; => '(0 1 4 9 16)

Because values are produced on demand, a generator can describe an infinite sequence, and the consumer decides how much of it to take.

How a generator works underneath

A hand-written version uses two continuations: one remembering where the consumer was waiting, one remembering where the generator body paused. In outline:

  1. next captures the consumer's continuation, then jumps into the generator body (or resumes its saved continuation).
  2. yield v captures the generator's continuation, saves it, then jumps back to the consumer's continuation with v.

Each side keeps swapping which continuation is "the current one". That swapping is what we call a context switch, but nothing here uses threads or the operating system.

sequenceDiagram
  participant C as Consumer
  participant G as Generator body
  C->>G: call (next)
  G-->>C: yield 1 (save my place)
  C->>G: call (next)
  G-->>C: yield 2 (save my place)
  C->>G: call (next)
  G-->>C: body ends, returns done

Both sides alternate; each resumes exactly where it stopped.

Stand-in: JavaScript generators

The code below models the Racket examples with function* and yield. The counter produces three values, then finishes:

JS Stand-in: a counter generator

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Notice that naturals has an infinite loop but does not hang: it only runs when asked for a value. That is the same laziness the Racket generator has.

Coroutines: taking turns

Two routines that produce and consume can swap control so neither needs to store a whole sequence. A classic example: one routine walks a tree and yields leaves; another compares them against a second tree, so two differently shaped trees can be checked for "same fringe" without building two full lists.

RACKET
(define (tree->generator tree)
  (generator ()
    (let walk ([t tree])
      (cond [(null? t) (void)]
            [(pair? t) (walk (car t)) (walk (cdr t))]
            [else (yield t)]))
    '()))

(define (same-fringe? t1 t2)
  (let ([g1 (tree->generator t1)]
        [g2 (tree->generator t2)])
    (let loop ()
      (let ([a (g1)] [b (g2)])
        (cond [(not (equal? a b)) #f]
              [(null? a) #t]
              [else (loop)])))))

The two trees may have different shapes, but if their leaves appear in the same order, the answer is true. It stops at the first difference without flattening anything.

JS Stand-in: same-fringe with two generators

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The last call stops after the very first comparison: neither tree was fully traversed.

Backtracking with re-entry (read-only)

Full continuations let you go further: save a continuation at a choice point, and if later work fails, call it again with a different choice. This is how the classic amb operator is built:

RACKET
;; sketch: (amb 1 2 3) picks a value; (require ...) fails and retries
(let ([x (amb 1 2 3 4 5 6 7)]
      [y (amb 1 2 3 4 5 6 7)])
  (require (= (+ x y) 10))
  (list x y))

JavaScript generators cannot rewind to an earlier point, so we do not stand in for amb here. Racket users usually reach for the racket/control operators (prompt, control) or libraries when they want this kind of search, because they confine the re-entry to a bounded region.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does yield do inside a Racket generator?

    yield saves the generator's continuation and returns the given value to whoever asked for the next one.
  2. 2. Why can a generator describe an infinite sequence safely?

    Work is demand-driven: each call produces one value and pauses again.
  3. 3. In the same-fringe example, what is the advantage of generators?

    Each tree is traversed lazily, one leaf at a time, so the work stops early when the trees differ.
  4. 4. Which statement about the JavaScript stand-in is true?

    A JavaScript generator advances forward only. Full Scheme continuations can be invoked again and again.

Summary

  • A generator pauses at yield and later resumes from the same place with its locals intact.
  • Racket gives you racket/generator; underneath, it swaps continuations.
  • Generators make lazy and infinite sequences natural, and let two traversals proceed in lock step.
  • Coroutines are routines that hand control to each other.
  • Full continuations also allow backtracking (amb); JavaScript generators cannot model that part.

Next: Quote and Code as Data