Glossary
Glossary
29 words you meet working through Crafting Interpreters and The Art of Computer Programming, each defined in a sentence and linked to the week that teaches it.
- Binary decision diagram (BDD)
- A binary decision diagram is a directed acyclic graph that represents a Boolean function; in its reduced ordered form it is canonical, so equal functions have identical diagrams.
- Bytecode virtual machine
- A bytecode virtual machine runs a program that has been compiled into a compact sequence of simple instructions (bytecode), decoding and executing one instruction at a time in a loop.
- CDCL (conflict-driven clause learning)
- Conflict-driven clause learning is the algorithm behind modern SAT solvers: when a partial assignment leads to a contradiction, the solver analyzes why, adds a new clause that rules the cause out, and jumps back.
- clox
- clox is the bytecode virtual machine for the Lox language, written in C in chapters 14 to 30 of Crafting Interpreters.
- Dancing links
- Dancing links is a technique for backtracking in which nodes are removed from doubly linked lists and later restored from their own stale pointers, used by Knuth's Algorithm X to solve exact cover problems.
- Euclid's algorithm
- Euclid's algorithm computes the greatest common divisor of two positive integers by repeatedly replacing the larger with its remainder modulo the smaller until the remainder is zero.
- Exact cover
- An exact cover problem gives a set of items and a collection of options, each a subset of the items, and asks for options that together contain every item exactly once.
- Fisher-Yates shuffle
- The Fisher-Yates shuffle produces a uniformly random permutation of an array in one pass by swapping each position with a randomly chosen position at or before it.
- Generating function
- A generating function represents a sequence a0, a1, a2, ... as the coefficients of a power series a0 + a1 z + a2 z^2 + ..., so that operations on the series correspond to operations on the sequence.
- Gray code
- A Gray code is an ordering of all n-bit binary strings in which each string differs from the next in exactly one bit.
- Harmonic numbers
- The n-th harmonic number is H(n) = 1 + 1/2 + 1/3 + ... + 1/n, which grows like the natural logarithm of n plus Euler's constant (about 0.5772).
- jlox
- jlox is the tree-walk interpreter for the Lox language, written in Java in chapters 4 to 13 of Crafting Interpreters.
- Linear congruential generator
- A linear congruential generator produces pseudorandom numbers by the recurrence X(n+1) = (a X(n) + c) mod m for a fixed multiplier a, increment c and modulus m.
- Lox
- Lox is a small, dynamically typed scripting language designed by Robert Nystrom for the book Crafting Interpreters, implemented twice in it: as jlox and as clox.
- Mark-sweep garbage collection
- Mark-sweep is a garbage collection algorithm that first marks every object reachable from a set of roots, then sweeps through all objects and frees the unmarked ones.
- MIX
- MIX is the imaginary computer Donald Knuth designed for The Art of Computer Programming, so that every algorithm in the books could be written, run and timed on one simple machine.
- MIXAL
- MIXAL (MIX Assembly Language) is the symbolic assembly language Knuth defines for writing programs for the MIX computer.
- MMIX
- MMIX is a 64-bit RISC computer designed by Donald Knuth to replace MIX in The Art of Computer Programming.
- NaN boxing
- NaN boxing is a value representation that stores non-number values such as pointers, booleans and nil inside the spare bits of IEEE 754 double-precision NaN values, so that every value fits in 64 bits.
- Open addressing
- Open addressing is a hash table collision strategy in which every entry lives in the table's own array, and a collision is resolved by probing other slots until a free one is found.
- Pratt parser
- A Pratt parser, or top-down operator precedence parser, parses expressions using a table that gives each token a prefix function, an infix function and a precedence.
- Recursive descent parser
- A recursive descent parser is a top-down parser in which each grammar rule becomes a function, and functions call each other to match nested structure.
- String interning
- String interning stores exactly one copy of each distinct string value, so two equal strings are always the same object and can be compared by address.
- SWAR (broadword computing)
- SWAR, SIMD within a register, is the technique of using ordinary integer instructions on a full machine word to operate on many small packed fields at once; Knuth calls it broadword computing.
- Topological sort
- A topological sort arranges the items of a partial order (or the vertices of a directed acyclic graph) in a sequence where every item comes after all the items that must precede it.
- Tree-walk interpreter
- A tree-walk interpreter executes a program by recursively evaluating the nodes of its abstract syntax tree, with no compilation to another form.
- Upvalue
- An upvalue is a reference from a closure to a local variable of an enclosing function, which stays valid after that function returns.
- WalkSAT
- WalkSAT is a randomized local search algorithm for satisfiability that repeatedly picks an unsatisfied clause and flips one of its variables, mixing greedy and random choices.
- ZDD (zero-suppressed decision diagram)
- A ZDD is a variant of the binary decision diagram, introduced by Shin-ichi Minato, that represents families of sets compactly by removing nodes whose HI branch leads to 0.