Generator functions

A generator function, written function*, is a function whose body can pause. Calling it runs none of the body; it returns a generator object. Each call of the generator’s next() runs the body until the next yield expression, hands that value out as { value, done: false } and freezes the function where it stopped, local variables included. The next next() resumes right after that yield. When the body returns, the result is { value, done: true }. A generator object follows both iteration protocols, so for…of, spread and destructuring work with it directly, and a generator method is the shortest way to make a class iterable. Because values are produced only when asked for, a generator can describe an endless sequence, or walk a million lines while keeping one in memory. This lesson traces a generator step by step and measures what laziness saves.

Calling a generator function runs nothing

The console.log calls inside this generator show exactly when its body runs:

// Calling a generator function runs none of its body; each next() runs it to the next yield.
function* innings() {
  console.log('  body starts');
  yield 'first over';
  console.log('  resumed after the first yield');
  yield 'second over';
  console.log('  resumed after the second yield');
  return 'innings closed';
}

const gen = innings(); // nothing is printed: the body has not started
console.log('created:', Object.prototype.toString.call(gen));
console.log('call 1:', gen.next());
console.log('call 2:', gen.next());
console.log('call 3:', gen.next());
console.log('call 4:', gen.next());

created: [object Generator]
  body starts
call 1: { value: 'first over', done: false }
  resumed after the first yield
call 2: { value: 'second over', done: false }
  resumed after the second yield
call 3: { value: 'innings closed', done: true }
call 4: { value: undefined, done: true }

innings() printed nothing: it only created the generator object, which reports itself as [object Generator]. The first next() started the body, which printed “body starts” and stopped at the first yield; that call returned { value: 'first over', done: false }. The second call resumed after that yield, printed its line and stopped at the second one. The third call ran to return 'innings closed', so its result carried the returned value with done: true. From then on the generator is finished, and every further call returns { value: undefined, done: true }.

A generator can be declared in four ways: a function* declaration, a function* expression such as const g = function* () {}, and a method marked with a star in a class or an object literal, *items() {}. There is no arrow-function form. A generator function is not a constructor either: new innings() throws a TypeError.

A generator is an iterator you can loop over

A generator object has a next() method, so it is an iterator, and its [Symbol.iterator]() returns the object itself, so it is also an iterable. That makes it usable everywhere an iterable is expected, with two consequences worth seeing once:

// A generator is an iterator and an iterable at once; its return value ends the walk and is not one of the values.
function* scores() {
  yield 52;
  yield 17;
  return 'total 69';
}

console.log([...scores()]);
for (const score of scores()) console.log('for…of:', score);

const manual = scores();
manual.next();
manual.next();
console.log(manual.next()); // only next() shows the return value

const gen = scores();
console.log(gen[Symbol.iterator]() === gen); // it is its own iterator
console.log([...gen], [...gen]); // so it walks once

[ 52, 17 ]
for…of: 52
for…of: 17
{ value: 'total 69', done: true }
true
[ 52, 17 ] []

• The return value is not one of the values. Spread and for…of stop at the first result with done: true and ignore its value, so 'total 69' appears only to code that calls next() itself. Use return for “how it ended”, rarely, and yield for anything a loop should see.
• A generator object walks once. It is its own iterator, so the first spread uses it up and the second gets [], exactly like array.values() in the previous lesson. Call the generator function again for a new walk.

Iterables in a few lines

The Range class of the previous lesson needed an object literal with next(), a position variable and two kinds of result objects. A generator method replaces all of it:

// The Range class of the previous lesson, with a generator method doing the iterator's work.
class Range {
  constructor(start, end, step = 1) {
    this.start = start;
    this.end = end;
    this.step = step;
  }

  *[Symbol.iterator]() {
    for (let n = this.start; n <= this.end; n += this.step) yield n;
  }
}

const evens = new Range(0, 10, 2);
console.log([...evens]);
console.log([...evens]); // each call of the method makes a new generator, so this starts again

// The same shorthand works in an object literal.
const squad = {
  players: ['Asha', 'Ravi', 'Meera'],
  *[Symbol.iterator]() {
    for (const name of this.players) yield name.toUpperCase();
  },
};
console.log([...squad]);

[ 0, 2, 4, 6, 8, 10 ]
[ 0, 2, 4, 6, 8, 10 ]
[ 'ASHA', 'RAVI', 'MEERA' ]

*[Symbol.iterator]() is a generator method whose name is the symbol. Each for…of or spread calls it, and each call creates a new generator object, so a Range can be walked any number of times, the property that a single generator object lacks. The loop inside the method is plain code; the generator turns each yield n into a result object and the end of the loop into done: true. The object literal squad shows the same shorthand, and that this inside a generator method is the object the method was called on, as in any method.

Lazy and endless sequences

A generator computes a value only when next() asks for it, so it can describe a sequence with no end:

// An endless supply of ticket numbers, handed out a few at a time.
function* ticketIds(prefix) {
  for (let n = 1; ; n++) yield `${prefix}-${String(n).padStart(4, '0')}`;
}

/** The next `size` values of an iterator, without closing it. */
function nextBatch(iterator, size) {
  const batch = [];
  while (batch.length < size) {
    const { value, done } = iterator.next();
    if (done) break;
    batch.push(value);
  }
  return batch;
}

const desk = ticketIds('TKT');
console.log(nextBatch(desk, 5));
console.log(nextBatch(desk, 5)); // the same generator resumes where it paused

// for…of with break closes the generator, so a second loop over it gets nothing.
const counter = ticketIds('ABC');
for (const id of counter) {
  console.log('loop:', id);
  if (id === 'ABC-0002') break;
}
console.log('after break:', counter.next());

[ 'TKT-0001', 'TKT-0002', 'TKT-0003', 'TKT-0004', 'TKT-0005' ]
[ 'TKT-0006', 'TKT-0007', 'TKT-0008', 'TKT-0009', 'TKT-0010' ]
loop: ABC-0001
loop: ABC-0002
after break: { value: undefined, done: true }

ticketIds contains an endless loop, which is safe because each next() runs only one more turn of it. nextBatch calls next() itself and never closes the iterator, so the second batch continues at TKT-0006: the generator remembered n between calls. The for…of loop behaves differently. Its break calls the generator’s return() method, which finishes the generator, so the next() after the loop returns done: true. To take values from one generator in several steps, call next(); a loop with break is a goodbye.

Laziness also keeps arithmetic exact for as long as you want to look. Number holds whole numbers exactly only up to Number.MAX_SAFE_INTEGER, 9,007,199,254,740,991, so a Fibonacci generator that uses BigInt can be compared with one that uses Number until they disagree:

// An endless, lazy Fibonacci sequence, with BigInt so that every value stays exact.
function* fibonacci() {
  let [a, b] = [0n, 1n];
  for (;;) {
    yield a;
    [a, b] = [b, a + b];
  }
}

function* fibonacciAsNumbers() {
  let [a, b] = [0, 1];
  for (;;) {
    yield a;
    [a, b] = [b, a + b];
  }
}

const first = [];
for (const f of fibonacci()) {
  if (first.length === 10) break;
  first.push(f);
}
console.log(first.join(', '));

// Walk both sequences side by side until Number loses exactness.
const exact = fibonacci();
const approximate = fibonacciAsNumbers();
for (let n = 0; ; n++) {
  const big = exact.next().value;
  const num = approximate.next().value;
  if (BigInt(num) !== big) {
    console.log(`F(${n}) is ${big}, but Number gives ${num}`);
    break;
  }
}

let n = 0;
for (const f of fibonacci()) {
  if (n++ === 100) {
    console.log(`F(100) = ${f}`);
    break;
  }
}

0, 1, 1, 2, 3, 5, 8, 13, 21, 34
F(79) is 14472334024676221, but Number gives 14472334024676220
F(100) = 354224848179261915075

The two sequences agree up to F(78) and part at F(79), 14,472,334,024,676,221, the first Fibonacci number above Number.MAX_SAFE_INTEGER. Above that limit Number can store only every second whole number, so it keeps the nearest one, 14,472,334,024,676,220. The BigInt generator goes on exactly, to F(100) = 354,224,848,179,261,915,075 and beyond, and none of those values exists until a loop asks for it. The one thing never to do with an endless generator is to give it to a consumer that reads to the end: [...fibonacci()], Array.from or Math.max(...) would run until memory runs out.

A pipeline that never holds the whole input

Generators that read from other generators form a pipeline. Each stage pulls one value from the stage before it, so a value travels through every stage before the next one is even created:

// A pipeline of generators over a million log lines: each line exists only while it moves through the stages.
let created = 0;

function* readLines(count) {
  for (let n = 1; n <= count; n++) {
    created += 1;
    const level = n % 97 === 0 ? 'ERROR' : n % 13 === 0 ? 'WARN' : 'INFO';
    yield `${level} request ${n} took ${(n * 37) % 500} ms`;
  }
}

function* onlyErrors(lines) {
  for (const line of lines) if (line.startsWith('ERROR')) yield line;
}

function* parse(lines) {
  for (const line of lines) {
    const [level, , id, , ms] = line.split(' ');
    yield { level, id: Number(id), ms: Number(ms) };
  }
}

// 1. Stop after the first three errors.
const firstErrors = [];
for (const entry of parse(onlyErrors(readLines(1_000_000)))) {
  firstErrors.push(entry.id);
  if (firstErrors.length === 3) break;
}
console.log('first errors:', firstErrors, '· lines created:', created);

// 2. Walk all of them, keeping only a count and a maximum.
created = 0;
let errors = 0;
let slowest = 0;
for (const entry of parse(onlyErrors(readLines(1_000_000)))) {
  errors += 1;
  slowest = Math.max(slowest, entry.ms);
}
console.log('errors:', errors, '· slowest:', slowest, 'ms · lines created:', created);

// 3. The same count with an array: all lines exist at once before filtering starts.
created = 0;
const all = [...readLines(1_000_000)];
console.log('array length:', all.length, '· errors:', all.filter((line) => line.startsWith('ERROR')).length);

first errors: [ 97, 194, 291 ] · lines created: 291
errors: 10309 · slowest: 499 ms · lines created: 1000000
array length: 1000000 · errors: 10309

The numbers come from the run itself:

• To find the first three errors, the pipeline created 291 lines out of a possible 1,000,000, because the 291st line produced the third error and the break then closed all three generators.
• To count every error, it created all 1,000,000 lines, but each one became garbage as soon as onlyErrors dropped it or parse turned it into an object that the loop read and forgot. At no point did the program hold more than one line, which is what “constant memory” means.
• The array version found the same 10,309 errors only after [...readLines(1_000_000)] had stored all 1,000,000 strings at once. With a real log file of several gigabytes, that line is where a program runs out of memory, while the generator version runs in the same small amount of memory for any size of file.

Laziness does not make the work itself smaller when every value is needed: both versions read every line. It changes how much exists at once, and it lets a consumer stop early without anyone producing the rest.

Errors wait for the first next()

Because the body starts only on the first next(), so does every check at its top:

// A check at the top of a generator runs on the first next(), not when the generator function is called.
function* pages(items, size) {
  if (size < 1) throw new RangeError(`size must be at least 1, got ${size}`);
  for (let i = 0; i < items.length; i += size) yield items.slice(i, i + size);
}

const report = pages(['a', 'b', 'c'], 0);
console.log('created, no error yet');
try {
  report.next();
} catch (error) {
  console.log('first next():', error.name, error.message);
}

// A plain function that checks first and then returns the generator reports the mistake at the call.
function checkedPages(items, size) {
  if (size < 1) throw new RangeError(`size must be at least 1, got ${size}`);
  return pages(items, size);
}

try {
  checkedPages(['a', 'b', 'c'], 0);
} catch (error) {
  console.log('at the call:', error.name, error.message);
}
console.log([...checkedPages(['a', 'b', 'c'], 2)]);

created, no error yet
first next(): RangeError size must be at least 1, got 0
at the call: RangeError size must be at least 1, got 0
[ [ 'a', 'b' ], [ 'c' ] ]

pages([...], 0) returned a generator without complaint, and the RangeError appeared only when something first asked for a page, possibly far away from the bad call. When a mistake in the arguments should be reported where it happens, split the function in two: a plain function that checks the arguments and then returns the generator, as checkedPages does.

When an array is the better choice

A generator is the right tool when values are expensive, endless, read once or best produced while they are consumed. An array is better when you need the values more than once, their count, access by index, sorting, or to send them through JSON.stringify, none of which a generator object offers. Converting is one spread away, [...gen()], as long as the sequence ends.

Exercises

/**
 * The items of an iterable in pages of `pageSize` (the last page may be shorter).
 * @template T
 * @param {Iterable<T>} items
 * @param {number} pageSize a whole number of at least 1, or a RangeError
 * @returns {Generator<T[]>}
 */
export function* paginate(items, pageSize) {}

/**
 * The values of an iterable, repeated for ever in the same order (nothing for an empty iterable).
 * @template T
 * @param {Iterable<T>} iterable
 * @returns {Generator<T>}
 */
export function* cycle(iterable) {}

import { test, assert } from 'mysmartcopilot:test';
import { paginate, cycle } from './sequences.mjs';

/** The first `count` values of an iterator (with next(), so the iterator stays open). */
function first(iterator, count) {
  const out = [];
  while (out.length < count) {
    const step = iterator.next();
    if (step.done) break;
    out.push(step.value);
  }
  return out;
}

/** 1, 2, 3 … for ever. */
function* naturals() {
  for (let n = 1; ; n++) yield n;
}

test('paginate splits items into pages, the last one shorter', () => {
  assert.deepEqual([...paginate([1, 2, 3, 4, 5, 6, 7], 3)], [[1, 2, 3], [4, 5, 6], [7]]);
  assert.deepEqual([...paginate(['a', 'b', 'c', 'd'], 2)], [['a', 'b'], ['c', 'd']]);
  assert.deepEqual([...paginate('xyz', 5)], [['x', 'y', 'z']]);
});

test('paginate gives no page for no items', () => {
  assert.deepEqual([...paginate([], 3)], []);
  assert.deepEqual([...paginate(new Set(), 1)], []);
});

test('paginate rejects a page size that is not a whole number of at least 1', () => {
  assert.throws(() => [...paginate([1, 2], 0)], RangeError);
  assert.throws(() => [...paginate([1, 2], -3)], RangeError);
  assert.throws(() => [...paginate([1, 2], 2.5)], RangeError);
});

test('paginate is lazy: it works on an endless iterable', () => {
  const pages = paginate(naturals(), 4);
  assert.deepEqual(first(pages, 2), [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
  ]);
});

test('cycle repeats the values in order', () => {
  assert.deepEqual(first(cycle(['red', 'amber', 'green']), 7), ['red', 'amber', 'green', 'red', 'amber', 'green', 'red']);
  assert.deepEqual(first(cycle('ab'), 5), ['a', 'b', 'a', 'b', 'a']);
});

test('cycle repeats values from an iterator that walks only once', () => {
  const once = new Set([1, 2]).values();
  assert.deepEqual(first(cycle(once), 6), [1, 2, 1, 2, 1, 2]);
});

test('cycle of nothing ends at once', () => {
  assert.deepEqual([...cycle([])], []);
});

test('cycle is lazy: the first values of an endless iterable come through', () => {
  assert.deepEqual(first(cycle(naturals()), 3), [1, 2, 3]);
});

Interview questions

Fresher · What happens when you call a generator function in JavaScript?

Calling a generator function does not run its body. It returns a generator object, suspended before the first line. The body runs only when something calls the object’s next() method, and then only until the next yield: that next() returns { value, done: false } with the yielded value, and the function pauses with its local variables kept. Each further next() resumes after the yield where it stopped. When the body reaches return or its end, next() returns { value, done: true }, and from then on always { value: undefined, done: true }. The generator object is both an iterator and an iterable, so for…of and spread can consume it directly, but only once, and a check at the top of the body, such as validating an argument, runs only on the first next().

Key takeaways

• Calling a function* returns a generator object and runs nothing; each next() runs the body to the next yield.
• A generator object is its own iterator: loop over it once, and call the generator function again for a new walk.
• for…of and spread ignore the value of return; only next() sees it.
• break in a for…of loop calls return() and finishes the generator; call next() yourself to take values in several steps.
• A generator method, *[Symbol.iterator](), makes a class or object iterable in a few lines, and walkable again and again.
• Generators are lazy: endless sequences are safe while every consumer stops, and pipelines hold one value at a time.
• Checks at the top of a generator body run on the first next(); validate in a plain function that returns the generator when errors must appear at the call.