Glossary

# A B C D E F G H I J K L M N O P Q R S T U V W Z

$\Theta$

f(n) = Θ(g(n)): f grows like g, up to constant factors; both O(g) and Ω(g). Chapter 13 · What a program costs

$O$

f(n) = O(g(n)): from some n on, f(n) is at most c·g(n) for some constant c. An upper bound on growth. Chapter 13 · What a program costs

, , that say where a paragraph, a heading or a link is. The browser turns it into a DOM tree.">HTML

Chapter 43 · Anatomy of this page

0. A lower bound on growth.">$\Omega$

Chapter 13 · What a program costs

::= alternative | alternative. It first appeared in the description of ALGOL 60 (1960); it and its extensions describe the syntax of most programming languages.">Backus–Naur form

Chapter 50 · The field linguist

= 7.">predicates

Chapter 10 · Functions as values

>>, the browser console and Jupyter all work this way.">REPL

Chapter 51 · The nesting doll

A binary search tree

A binary tree in which, for every node, all keys of the left subtree are smaller than its key and all keys of the right subtree are larger. Search, insertion and deletion follow a single path down from the root. Chapter 17 · A garden of search trees

abstract data type

A description of a data structure by its operations and what they mean, without saying how it is built. A stack is push, pop and peek; whether it sits on an array or on a linked list is a matter of implementation. Chapter 15 · Stacks, queues and a calculator

abstract syntax tree

Abstract syntax tree: the structure of a program without the details of how it is written, with no parentheses, separators or intermediate grammar rules. Its nodes are operations, calls, assignments, loops; this is how an interpreter or a compiler sees a program. Chapter 50 · The field linguist

accumulators

A variable that gets a starting value before a loop and is updated on every iteration: a sum, a count, the largest value so far. Chapter 4 · Again and again

ACID

Four properties of transactions: atomicity (all or nothing), consistency (the database’s rules hold before and after), isolation (concurrent transactions don’t see each other’s halves), durability (what is committed survives a failure). Chapter 46 · The library and the bank

acknowledgment

The receiver’s answer that such-and-such a packet, or such-and-such bytes, have arrived. When no acknowledgment comes, the sender sends again. Chapter 42 · Inventing a protocol

address

The number of a byte in a computer’s memory. Given an address, the processor reads or writes that place in memory in a single access, wherever it is. Chapter 14 · How a list lives in memory

address space

All the virtual addresses available to a process. Each process has its own: the same address in two processes means two different cells. Chapter 38 · The hotel of addresses

adjacency lists

A way of storing a graph: for each vertex, the list of its neighbors. In Python, a dictionary whose key is a vertex and whose value is a list. It takes memory in proportion to the number of vertices and edges. Chapter 19 · Six handshakes

adjacency matrix

A way of storing a graph as an n × n table: cell (a, b) holds 1 if there is an edge from a to b, and 0 if there isn’t. Checking for an edge takes O(1), but the table needs n² cells whatever the number of edges. Chapter 19 · Six handshakes

admissible

A heuristic in path search that never exceeds the true distance to the goal. With it, A* finds a shortest path. Chapter 24 · The navigator

AES

Advanced Encryption Standard: a block cipher, a U.S. standard since 2001 (the Rijndael cipher of Daemen and Rijmen). It encrypts 128-bit blocks with a key of 128, 192 or 256 bits in 10, 12 or 14 rounds. Chapter 59 · The cipher bureau

aggregate functions

A function that folds many rows into one value: count, sum, avg, min, max. With GROUP BY it is computed separately for each group of rows. Chapter 45 · The archivist

aging

A way to fight starvation: a job’s priority rises gradually while it waits, so that every job gets the processor sooner or later. Chapter 37 · Mission control

AIMD

Additive increase, multiplicative decrease: a congestion control rule under which the window grows by a constant amount per round trip without losses and shrinks by a constant factor on a loss (by half in TCP). It shares a link equally among flows. Chapter 42 · Inventing a protocol

algebraic data types

A data type built from products (a record: this and that) and sums (a variant: this or that). Maybe in Haskell, enum in Rust, a union of dataclasses with | in Python. Chapter 53 · Null on trial

alpha-beta pruning

Alpha-beta pruning: a speedup of minimax. We keep α, the best already guaranteed to the maximizing player, and β, the best guaranteed to the opponent. As soon as a branch cannot improve the result (its value falls outside α…β), it is no longer examined. The answer is the same one minimax gives. Chapter 62 · The bot tournament

ambiguous

A grammar under which some phrase has more than one parse tree. For a programming language this is a flaw in the description: a program must mean one thing. Chapter 50 · The field linguist

Amdahl’s law

If a fraction p of a program’s work divides among N cores and the rest is serial, the speedup is 1 / ((1 − p) + p/N) and never exceeds 1 / (1 − p). Chapter 35 · The pipeline and the fortune-teller

amortized

The cost of an operation averaged over a long sequence of operations: rare expensive steps are spread over many cheap ones. Appending to a Python list costs O(1) amortized. Chapter 14 · How a list lives in memory

amplitudes

A number (in general a complex one) that a quantum state assigns to each possible outcome of a measurement. The probability of the outcome is the squared magnitude of its amplitude. Chapter 64 · The qubit lab

API

Application Programming Interface: an agreement by which one program uses another. On the web, a set of addresses and rules: which request to send and which response, usually JSON, comes back. Chapter 43 · Anatomy of this page

approximation algorithm

An algorithm for a hard optimization problem that runs in polynomial time and guarantees that its answer is worse than the optimum by at most a given factor, the approximation ratio. Chapter 58 · The salesman’s expedition

arbitrage

A deal that makes a profit without risk out of a difference in prices, such as a round of currency exchanges after which there is more money than before. Chapter 24 · The navigator

argument

A value passed to a function when it is called: in draw_square(40) it is 40. Chapter 5 · Words of your own

arithmetic logic unit

Arithmetic logic unit: the part of a processor that, according to the opcode, adds, subtracts, compares, shifts or does bitwise operations on numbers from the registers, and sets the flags. Chapter 30 · The machine does arithmetic

array

A block of memory made of identical cells lying in a row. The address of cell i is the start of the block plus i times the cell size, so any cell can be reached in one step. Chapter 14 · How a list lives in memory

array programming

A programming paradigm in which operations apply to whole arrays at once, without explicit loops: x + 1 adds one to every element. APL, J, MATLAB, numpy. Chapter 49 · The museum of languages

assembler

A program that translates text in assembly language (instruction mnemonics and labels) into machine code. The language itself is also often called assembler. Chapter 32 · You are the processor

assignment

The command “name = expression”: work out the expression on the right and tie the name on the left to the result. In Python the sign = is not equality. Chapter 2 · Names and values

associativity

The rule for grouping repeated operations without parentheses: left associativity goes from left to right, 8 − 3 − 2 = (8 − 3) − 2; right associativity from right to left, 2 ** 3 ** 2 = 2 ** (3 ** 2). In a grammar it is set by the direction in which the recursion grows. Chapter 50 · The field linguist

atomic rename

A rename of a file that happens completely or not at all: anyone who opens the file by that name sees either the old version or the new one. Safe saving is built on it: write a temporary file, fsync, rename. Chapter 40 · The rescue operation

atomicity

The property of an operation to run whole, as one indivisible step: other threads see either the state before it or the state after it, never the middle. Chapter 39 · Races

attributes

A name tied to an object, such as bunny.energy or point.x. You read and change it through a dot. Chapter 12 · The island of rabbits and foxes

augmenting path

A path from the source to the sink in the residual network. Sending along it as much as its narrowest edge allows makes the flow larger. Chapter 25 · Flows and matchings

avalanche effect

A property of a good hash function or cipher: changing one bit of the input changes on average half the bits of the output, and which ones can’t be predicted. Chapter 60 · A secret in plain sight

average case

An algorithm’s running time averaged over the inputs of size n, under some assumption about how those inputs are distributed, such as “all permutations are equally likely.” Chapter 13 · What a program costs

AVL tree

A binary search tree in which at every node the heights of the left and right subtrees differ by at most one. After insertions and deletions it restores the rule with rotations, and its height is always O(log n). Invented by Adelson-Velsky and Landis in 1962. Chapter 17 · A garden of search trees

B-tree

A balanced search tree with wide nodes: each node holds up to hundreds of keys in order and has one more child than keys. All leaves are at the same depth, and the height grows as the logarithm to the base of the node width. Databases and file systems keep their indexes this way. Chapter 46 · The library and the bank

backdoor

A backdoor: a deliberately hidden way around a defense: a secret password built into a program, or code added to a build tool. Unlike a vulnerability, a backdoor is left on purpose. Chapter 61 · The training range

backpropagation

A way to compute the gradient of the loss function with respect to all the weights of a network in a single pass from the output back to the input: derivatives by the chain rule, layer by layer. Chapter 63 · The machine learns

bandwidth

How much data a link carries per second, usually counted in bits per second (bit/s, Mbit/s, Gbit/s). Not to be confused with latency, the time it takes the first bit to arrive. Chapter 41 · A day in the life of a packet

bandwidth-delay product

The bandwidth of a link multiplied by the round-trip time: how much data must be on the way at once so that the link doesn’t stand idle. That is the window a sender needs. Chapter 42 · Inventing a protocol

base case

The simplest case of a recursive problem, solved at once without any new recursive calls; it is where the recursion stops. Chapter 9 · A problem inside a problem

Bell states

The four maximally entangled states of two qubits: (|00⟩ ± |11⟩)/√2 and (|01⟩ ± |10⟩)/√2. The first is made from |00⟩ by H on the first qubit and a CNOT. Chapter 64 · The qubit lab

best-effort delivery

Delivery in which the network tries to get a packet through but promises nothing: it may be lost, duplicated or arrive after the next one. This is how IP works. Chapter 41 · A day in the life of a packet

binary search

Search in a sorted list: compare the target with the middle of the range and throw away the half where it can’t be. About log₂ n comparisons. Chapter 20 · The sorting tournament

bipartite

A graph whose vertices split into two parts so that every edge joins vertices from different parts. Chapter 25 · Flows and matchings

bits

A binary digit: 0 or 1. The smallest portion of information; everything a computer stores and transmits is written in bits. Chapter 28 · Everything is bits

Bloch sphere

A picture of the states of one qubit as points on the unit sphere: cos(θ/2)|0⟩ + e^{iφ} sin(θ/2)|1⟩ is the point at angle θ from the north pole and longitude φ. Gates rotate the sphere. Chapter 64 · The qubit lab

block

Several lines indented by the same amount under a line that ends in a colon (if, else, while, def…): they run together, as one unit. Chapter 3 · Forks in the road

block cipher

A cipher that turns a block of fixed length (128 bits for AES) into a block of the same length under the control of a key. Long messages are encrypted block by block, following special rules (modes). Chapter 59 · The cipher bureau

blocking pair

A student and a school (or any two from opposite sides) who are not together but would both prefer each other to their current partners. Chapter 25 · Flows and matchings

blocks

The smallest portion in which a disk and a file system read and write data, usually 4,096 bytes. A file takes up a whole number of blocks. Chapter 40 · The rescue operation

Bloom filter

An array of m bits plus k hash functions: adding an item sets its k bits to one; an item is “possibly there” if all its k bits are ones and “certainly not” if any of them is zero. Chapter 26 · Let's flip a coin

BM25

A ranking formula (Robertson, Spärck Jones and colleagues, the Okapi system, 1990s): like TF-IDF, but the contribution of a word’s frequency saturates (parameter k₁ ≈ 1.2), and the document’s length is compared with the average (b ≈ 0.75). Chapter 48 · A search engine for our textbooks

Boolean algebra

An algebra over the values 0 and 1 with the operations AND (multiplication), OR (addition) and NOT (a bar on top); the design of digital circuits rests on it. Chapter 29 · Logic from switches

Boolean value

The logical type bool: only two values, True and False. Comparisons produce them, and conditions rest on them. Chapter 2 · Names and values

border

A border of a string is a beginning of it that is also its end, but not the whole string. “abracadabra” has two borders: “abra” and “a”. Chapter 27 · A needle in a haystack

BQP

Bounded-error Quantum Polynomial time: the problems a quantum computer solves in polynomial time with an error probability of at most 1/3. It contains P and lies inside PSPACE; factoring is in BQP. How BQP relates to NP is unknown. Chapter 64 · The qubit lab

branch predictor

The part of a processor that guesses, before a conditional branch has executed, whether it will be taken, so that the pipeline doesn’t stand idle. It guesses from how this branch and its neighbors behaved before. Chapter 35 · The pipeline and the fortune-teller

breadth-first search

A way of walking a graph in circles: first the neighbors of the starting vertex, then their neighbors, and so on. Vertices wait their turn in a FIFO queue. In a graph without weights it finds the paths with the fewest edges, in O(V + E) time. Chapter 19 · Six handshakes

brute force

An attack on a cipher that tries all possible keys one after another. The defense against it is so many keys that the search can’t finish in any reasonable time. Chapter 59 · The cipher bureau

buckets

A slot of a hash table: the place for the records whose key hash, modulo the size of the table, equals the slot’s number. Chapter 16 · Hash tables: attack and defense

buffer overflow

A buffer overflow: a write past the end of an array (a buffer) in a language with no bounds checking, so that the data overwrites the neighboring memory: other variables, bookkeeping fields, the return address. If the data comes from outside, its author can choose what to overwrite. Chapter 61 · The training range

Burrows–Wheeler transform

The Burrows–Wheeler transform (1994): write out all cyclic shifts of a string, sort them and take the last characters. The result is a permutation of the same string in which equal characters stand in runs, and it can be reversed. bzip2 is built on it. Chapter 47 · The packing contest

busy beaver

BB(n) is the largest number of steps that a Turing machine with n states and the symbols 0 and 1 makes before halting, started on a blank tape. Tibor Radó introduced the function in 1962; it is uncomputable and grows faster than any computable function. Chapter 56 · A conversation with the Oracle

byte

Eight bits. The smallest portion of memory with an address of its own; it holds a number from 0 to 255. Chapter 28 · Everything is bits

bytecode

A program for a virtual machine: a sequence of simple instructions into which an interpreter translates the source code before running it. In CPython each instruction takes two bytes, an opcode and an argument. Chapter 33 · An X-ray of Python

Byzantine

The worst kind of failure: a node behaves arbitrarily, answering wrongly and telling different nodes different things, as if on purpose. Surviving f such nodes with ordinary messages takes at least 3f + 1 nodes. Chapter 44 · The parliament of Paxos

Bélády’s anomaly

A property of some eviction policies, such as FIFO: on some sequences of accesses, more frames give more page faults. LRU and OPT are not subject to it. Chapter 38 · The hotel of addresses

cache line

The portion in which data moves between memory and a cache: usually 64 consecutive bytes (128 on Apple processors). Reading one byte brings its whole line into the cache. Chapter 34 · Near and far

cache miss

A memory access that doesn’t find its data in the cache, so the data has to be brought from a slower step. The opposite is a hit. Chapter 34 · Near and far

caches

A small, fast memory that keeps copies of data from a large, slow one, so that a repeated access doesn’t have to go far. Chapter 34 · Near and far

call stack

The pile of frames of the calls that have started and not yet finished: a new call puts a frame on top, a return takes it off. Chapter 5 · Words of your own

calling convention

An agreement on how functions pass arguments and results to one another: in which registers and in what order, what goes on the stack, which registers the called function must preserve. Chapter 33 · An X-ray of Python

CAP theorem

Brewer’s theorem (proved by Gilbert and Lynch in 2002): when the network is partitioned, a distributed system must choose between answering requests (availability) and guaranteeing that the answers agree (consistency); it can’t have both. Chapter 44 · The parliament of Paxos

capacity

How many places are reserved for the items of a dynamic array; the length is how many of them are taken. The capacity is never less than the length. Chapter 14 · How a list lives in memory

capacity

The capacity of an edge in a flow network is the number c(u, v): no more than that can be carried along the edge. Chapter 25 · Flows and matchings

capacity of the cut

The sum of the capacities of the edges that run from the source’s side of a cut to the sink’s side. Chapter 25 · Flows and matchings

catastrophic backtracking

Exponential (or high-degree polynomial) growth of regex search time in backtracking engines: when there is no match, the engine tries every way of dividing the string among the parts of the expression. The attack built on it is ReDoS. Chapter 54 · Automata and regular expressions

cellular automaton

A grid of cells, each in one of finitely many states; at each step all the cells change state at once by one and the same rule, which looks at the cell and its neighbors. Conway’s Game of Life is an example. Chapter 55 · The Turing machine

certificate

A short hint that confirms the answer “yes” to a decision problem: a seating, a filled board, a satisfying assignment, a divisor of a number. Its length is polynomial in the input, and checking it takes polynomial time. Chapter 57 · Gödel’s letter

certificate

A document in which a certificate authority uses its signature to bind a name, such as a website’s address, to a public key. The browser checks the chain of signatures up to a root authority whose key is built into the system. Chapter 60 · A secret in plain sight

chaining

A way of resolving collisions: every bucket of a hash table holds a chain (a list) of all the records that landed in it. Chapter 16 · Hash tables: attack and defense

check digit

A digit added to a number so that the other digits can show whether the number was typed correctly. Chapter 5 · Words of your own

checksum

A short number computed from data when it is written and checked when it is read: if the data has changed, the number will almost certainly not match. Examples: the parity bit, Adler-32, CRC-32, SHA-256. Chapter 40 · The rescue operation

Chomsky hierarchy

The classification of languages (and grammars) by the power of the machine that recognizes them: regular ones need a finite automaton, context-free ones a pushdown automaton, context-sensitive ones a machine with a tape as long as the input, recursively enumerable ones a Turing machine. Chomsky, 1956. Chapter 54 · Automata and regular expressions

Church–Turing thesis

The claim that every function computable by a mechanical procedure (an algorithm) is computable by a Turing machine. It is an agreement about the meaning of the word “algorithm” rather than a theorem, and it is supported by the fact that every model of computation ever proposed has turned out to be equivalent. Chapter 55 · The Turing machine

cipher

A rule for turning plaintext into ciphertext and ciphertext back into plaintext. The rule is general; the key picks the particular transformation. Chapter 59 · The cipher bureau

ciphertext

The result of encryption: text or bytes from which no meaning can be extracted without the key. Chapter 59 · The cipher bureau

circuit switching

A way to build a network in which two parties get an end-to-end circuit for the length of a call, and it belongs to them alone, even when they are silent. The telephone network worked this way. Chapter 41 · A day in the life of a packet

class

A description of a kind of object: what attributes its objects have and what they can do (their methods). From a class, as from a blueprint, you can make as many objects as you like. Chapter 12 · The island of rabbits and foxes

clock

A metronome signal that jumps steadily between 0 and 1; on its edges all the flip-flops of a machine take their new values at once. One period of it is a clock cycle. Chapter 31 · Memory and the clock

clock

A page replacement policy that approximates LRU with one bit per page: a hand goes round the frames in a circle; a page whose accessed flag is up has the flag lowered and is passed over (a second chance), a page whose flag is down is evicted. Chapter 38 · The hotel of addresses

closure

A function together with the variables of the place where it was created: it remembers them even after the function that created it has finished. Chapter 10 · Functions as values

co-NP

The problems whose “no” answer is confirmed by a short certificate that is quick to check: the complements of problems in NP. The unsatisfiability of a formula, the absence of a Hamiltonian cycle, and whether a formula is a tautology are in co-NP. Chapter 57 · Gödel’s letter

code generation

The compiler stage that translates the intermediate representation into instructions for a particular processor: it chooses the instructions and decides which values go in registers and which in memory. Chapter 52 · Closing the circle

code point

A character’s number in Unicode, from 0 to 0x10FFFF, written like U+0416 (“Ж”). Python’s ord returns it, and a string is a sequence of code points. Chapter 28 · Everything is bits

collision

The case when a hash table picks the same bucket for two different keys (or their hashes are equal outright). Collisions are unavoidable; a table has to know how to live with them. Chapter 16 · Hash tables: attack and defense

commit

A snapshot of a project in a version control system: the address of the tree of files, the addresses of the parent commits, the author and a message. In git a commit’s address is the hash of all of this, so it vouches for the contents and for the whole history before it. Chapter 40 · The rescue operation

comparison sorts

A sort that learns about the data only by comparing pairs of items. Selection, insertion, bubble sort, merge sort, quicksort, heapsort and Timsort are all comparison sorts. Chapter 20 · The sorting tournament

compiler

A program that translates a whole program from one language into another ahead of time, usually into the processor’s machine code; the translation then runs without it. Chapter 33 · An X-ray of Python

complete

A binary tree whose levels are all full, except perhaps the last, which is filled from left to right without gaps. It is convenient to store in an array. Chapter 18 · Who is next

complexity

How an algorithm’s work (the number of steps, or the time) grows with the size of the input n: linearly, quadratically, exponentially. Chapter 13 · What a program costs

composition

Joining functions so that the result of one becomes the argument of another: f(g(x)). Chapter 5 · Words of your own

comprehension

The notation [expression for x in data if condition]: a new list (dictionary, set) made of the items of the data that pass the condition, transformed by the expression. Chapter 10 · Functions as values

Compression

Writing data in fewer bits. After lossless compression the original data is restored bit for bit (ZIP, PNG); after lossy compression, only approximately (JPEG, MP3). Chapter 47 · The packing contest

condition

An expression the program checks before it chooses a path: its value is True or False. Chapter 3 · Forks in the road

configuration

The complete instantaneous description of a Turing machine: the contents of the tape, the position of the head and the state. A configuration and the table determine the next configuration uniquely. Chapter 55 · The Turing machine

congestion collapse

A state of a network in which the links are almost fully busy, yet hundreds of times less useful data gets through: the queues are full, and the network carries mostly resends of lost packets. Chapter 42 · Inventing a protocol

conjunctive normal form

Conjunctive normal form: a formula of the form “clause and clause and …,” where each clause is an “or” of several literals (variables and their negations). For example, (x₁ ∨ ¬x₂) ∧ (x₂ ∨ x₃). This is the form in which SAT solvers take their formulas. Chapter 57 · Gödel’s letter

connected components

A largest piece of an undirected graph in which every vertex can be reached from every other. A graph with only one component is called connected. Chapter 19 · Six handshakes

consensus

The problem of agreement: several nodes propose values, and all working nodes must choose the same value from among those proposed. The solution must stay correct when nodes fail and messages are lost. Chapter 44 · The parliament of Paxos

constant folding

An optimization: when all the operands of an expression are known at compile time (2 * 4, 8 - 1), the compiler computes it itself and puts in the result, so the program doesn’t compute it on every run. Chapter 52 · Closing the circle

content addressing

A way of storing data in which an object’s address is the hash of its contents. Identical data gets one address and is stored once, changed data gets a new address, and a damaged object gives itself away when its hash no longer matches. Chapter 40 · The rescue operation

content delivery network

Content Delivery Network: servers around the world keep copies of a site’s files and serve them to people nearby, so that a request doesn’t have to travel to the origin server. Chapter 34 · Near and far

context switch

Changing the program on a processor core: the OS kernel saves the registers, the program counter and the rest of the interrupted process’s state and loads the saved state of the next one. Chapter 37 · Mission control

context-free

A grammar in which the left side of every rule is a single nonterminal, and the rule may replace it regardless of its surroundings. The syntax of almost every programming language is described by such grammars. Chapter 50 · The field linguist

cookies

A small piece of data that a server hands the browser in a Set-Cookie header and the browser returns with every later request to the same site. This is how a server that remembers no clients recognizes its own: by a session number. Chapter 43 · Anatomy of this page

cooperative multitasking

Multitasking in which the jobs give up the processor themselves, at points that suit them, and the scheduler interrupts nobody. Cheap and predictable, but a single job that won’t yield stops all the others. Chapter 37 · Mission control

copy-on-write

A technique in which a copy of data first shares memory with the original, and a page is copied only on the first write to it. That is how fork creates a process without copying all its memory. Chapter 38 · The hotel of addresses

core

One of several independent processors on a single chip: each core runs its own stream of instructions, while the last-level cache and the path to memory are usually shared. Chapter 35 · The pipeline and the fortune-teller

coroutine

A function that can pause in the middle, hand over control and later carry on from the same place. In Python, generators and async def functions. Chapter 37 · Mission control

counter

A register that adds one to its value (or subtracts one) on every clock cycle; it wraps around, so after the largest number comes 0 again. Chapter 31 · Memory and the clock

counting sort

A sort without comparisons for a small set of possible values: count how many times each value occurs and write the values out in order. Time n + k, where k is the number of possible values. Chapter 20 · The sorting tournament

covering

An index that contains every column a query needs, so the database never has to go to the table itself. In SQLite’s plan: USING COVERING INDEX. Chapter 46 · The library and the bank

crash failure

A failure in which a node stops working: it doesn’t answer and sends no messages, but it doesn’t lie either. After recovering, it may come back with the data it had saved. Chapter 44 · The parliament of Paxos

crawler

The program of a search engine that walks the web: it downloads a page, pulls out its links and queues them for downloading. This is how a search engine learns that pages exist. Chapter 48 · A search engine for our textbooks

crib

A guessed piece of plaintext that is probably in the ciphertext: a standard greeting, a weather report, a signature. A known-plaintext attack starts from a crib. Chapter 59 · The cipher bureau

critical section

A stretch of a program where a thread works with shared data and where only one thread may be at a time. Chapter 39 · Races

cross-site scripting

Cross-site scripting (XSS): an attack in which user data reaches a page without escaping and the browser runs it as a script in the site’s context. The defense is escaping output (html.escape) and the HttpOnly flag on important cookies. Chapter 61 · The training range

cryptanalysis

The art and science of breaking ciphers: reading ciphertexts without the key, or finding the key itself. Chapter 59 · The cipher bureau

cryptographic hash function

A hash function for which it is practically impossible to find an input from its value, a second input with the same value as a given one, or any two inputs with the same value. Examples: SHA-256, SHA-3; MD5 and SHA-1 no longer meet these requirements. Chapter 60 · A secret in plain sight

CSS

Cascading Style Sheets, the style language of the web: rules of the form “selector { property: value }” set the colors, fonts, spacing and layout of the elements of the DOM tree. Chapter 43 · Anatomy of this page

cut

A division of a graph’s vertices into two non-empty groups; the edges of the cut are those joining vertices in different groups. Chapter 23 · Greed and electricity

cycle

A path along the edges of a graph that returns to its starting vertex without using any edge twice. In a directed graph, a path along the arrows. A graph of dependencies without cycles can be sorted topologically. Chapter 19 · Six handshakes

D flip-flop

A one-bit memory cell that takes the value of its input D only at the moment of a clock edge and holds it the rest of the time. It is built from two D latches that open in turn. Chapter 31 · Memory and the clock

database

A collection of data that a separate program, a database management system (DBMS) such as SQLite, PostgreSQL or Oracle, stores and hands out on request. In a relational database the data lives in tables. Chapter 45 · The archivist

De Morgan’s laws

The rules for moving a negation inside parentheses: “not (a and b)” equals “not a or not b,” and “not (a or b)” equals “not a and not b.” Chapter 29 · Logic from switches

dead code

A part of a program that never runs (after an unconditional jump, in an if branch whose condition is always false) or whose result nobody needs. The optimizer removes it. Chapter 52 · Closing the circle

deadlock

A standstill in which several threads wait for each other in a circle: each holds what the next one needs and waits for what the previous one holds, and none can go on. Chapter 39 · Races

decidable

A yes-or-no problem is decidable if some program halts on every input and gives the right answer. If there is no such program, the problem is undecidable. Chapter 56 · A conversation with the Oracle

decision problem

A problem whose answer is yes or no: is there a seating, can the sudoku be completed, is the formula satisfiable. Complexity theory is built on them: P, NP and NP-completeness are about problems of this kind. Chapter 57 · Gödel’s letter

decision tree

A tree of all the possible moves of an algorithm: comparison questions in the internal nodes, answers on the branches, results in the leaves. The number of comparisons on an input is the length of the path from the root to a leaf. Chapter 20 · The sorting tournament

declarative

A way of programming in which you describe what the result should be rather than a sequence of steps. SQL and regular expressions are declarative; Python is mostly imperative. Chapter 45 · The archivist

decoder

A circuit that takes an n-bit number and lights exactly one of its 2ⁿ output lines; in memory it picks a cell by its address. Chapter 31 · Memory and the clock

decoherence

The decay of a quantum state through interaction with its surroundings: the amplitudes lose their coordinated phases, and the qubit gradually comes to behave like an ordinary random bit. Chapter 64 · The qubit lab

decomposition

Splitting a problem into subproblems, each solved by a function of its own; top down means the main function first, then the ones it relies on. Chapter 5 · Words of your own

decorator

A function that takes a function and returns a new, wrapped one: timed, counting its calls, remembering its answers. It is written as a line @name above def. Chapter 10 · Functions as values

defense in depth

Defense in depth: several independent measures, each of which stops an attack on its own. If one layer is breached or forgotten, the next still holds. The opposite of a single wall. Chapter 61 · The training range

deferred acceptance

The Gale–Shapley algorithm: the free members of one side apply down their lists, while the other side holds on to the best offer received so far and rejects the rest, until everyone is placed. Chapter 25 · Flows and matchings

DEFLATE

A lossless compression format: first LZ77 replaces repeats with references (a 32 KiB window), then a Huffman code encodes the characters, lengths and distances. Used in ZIP, gzip, PNG, zlib and HTTP. Chapter 47 · The packing contest

delay

The time a logic gate’s output takes to respond to a change at its inputs; picoseconds for modern gates, but along a long chain the delays add up. Chapter 30 · The machine does arithmetic

depth-first search

A way of walking a graph that goes forward while it can and, at a dead end, returns to the last fork with unexplored edges. Written with recursion or with a stack of your own (LIFO), in O(V + E) time. It does not look for shortest paths. Chapter 19 · Six handshakes

deque

A double-ended queue: items can be added and removed at both ends in O(1). It can serve as a stack or as a queue. In Python: collections.deque. Chapter 15 · Stacks, queues and a calculator

derivation

A chain of replacements by the rules of a grammar, from the start nonterminal to a phrase made of terminals only. A phrase belongs to the language if it has a derivation. Chapter 50 · The field linguist

deterministic finite automaton

Deterministic finite automaton: a finite set of states, an alphabet, a transition table (state, symbol) → state, a start state and a set of accepting states. It reads a string one symbol at a time and accepts it if it ends up in an accepting state. Chapter 54 · Automata and regular expressions

dictionary

A data structure made of key–value pairs: a key leads straight to its value, as in code["o"] → "---". Chapter 8 · Dictionaries and the telegraph

Diffie–Hellman key exchange

A protocol by which two parties obtain a shared secret key while exchanging only public messages, A = g^a mod p and B = g^b mod p; the shared key is g^ab mod p. An eavesdropper would need a discrete logarithm. Chapter 60 · A secret in plain sight

digital signature

A number that the holder of a private key computes from a message. Anyone can check it with the public key, nobody else can forge it, and the slightest change to the message makes the check fail. Chapter 60 · A secret in plain sight

directed

A graph whose edges have a direction: an arrow from one vertex to another. Examples: “read this chapter before that one,” “this page links to that one.” Chapter 19 · Six handshakes

directed acyclic graph

A directed acyclic graph (DAG): a graph with arrows in which you can never return to a vertex by following the arrows. The dependencies of tasks, packages and the chapters of this course form such graphs. Chapter 19 · Six handshakes

dirty read

An anomaly: a transaction reads changes made by another transaction that are not yet committed and may still be undone. Chapter 46 · The library and the bank

discrete cosine transform

The discrete cosine transform: writing a block of numbers (say, 8 × 8 pixels of a picture) as a sum of cosine waves of different frequencies. In JPEG and MP3 it lets the small high-frequency details be stored coarsely. Chapter 47 · The packing contest

discrete logarithm

The problem of finding the exponent x, given g, p and A = g^x mod p. No fast method is known for large p; the Diffie–Hellman key exchange rests on this. Chapter 60 · A secret in plain sight

disjoint-set structure

A data structure that splits items into groups: find(x) returns the representative of x’s group, union(a, b) merges two groups. With union by size and path compression both operations take almost constant time. Chapter 23 · Greed and electricity

disjunctive normal form

A way of writing a logical function as an OR of several products (ANDs) of the inputs and their negations; for example, ab + āc. Chapter 29 · Logic from switches

distributed system

Several computers that communicate only by messages over a network and together do one job. They share no memory and no clock, and each can fail independently of the others. Chapter 44 · The parliament of Paxos

divide and conquer

A way of designing algorithms: split a problem into subproblems of the same kind, solve them recursively and build the answer from their answers. Chapter 21 · Divide and conquer

DNS

Domain Name System: a distributed, hierarchical system that turns names like legost.in into IP addresses. Each level of the tree of names is served by its own servers, and no one keeps all of it. Chapter 43 · Anatomy of this page

docstring

A string in triple quotes right under a function’s header: what the function does, what it takes and what it returns. help() shows it. Chapter 5 · Words of your own

DOM

Document Object Model: the tree the browser builds from HTML, whose nodes are elements and pieces of text. The page’s scripts read and change it, and the browser redraws whatever has changed. Chapter 43 · Anatomy of this page

doubly linked list

A linked list in which every node holds references to both the next and the previous node, so it can be walked in either direction. Chapter 14 · How a list lives in memory

duck typing

Python’s principle that any object with the right methods will do, whatever its class. The island calls step on anything in its list of animals. Chapter 12 · The island of rabbits and foxes

dynamic

The rule by which a function looks up unfamiliar names in the frame of its caller, and further along the chain of calls. Early Lisps had it; it survives in the shell’s local variables. Chapter 51 · The nesting doll

dynamic array

An array that grows by itself: it keeps spare places, and when they run out, it moves to a bigger block of memory. The Python list works this way. Chapter 14 · How a list lives in memory

Dynamic programming

A method for problems whose subproblems repeat: the answer to each subproblem is computed once and remembered, by recursion with memory or by a table filled from the bottom up. Chapter 22 · Remember instead of recomputing

dynamic typing

Checking types while the program runs: the type belongs to the value rather than the variable, and an error is found only when execution reaches it. Python, JavaScript, Lisp. Chapter 49 · The museum of languages

EDF

Earliest deadline first: a scheduling policy that gives the core to the task with the earliest deadline. On a single core it meets every deadline that can be met at all, but under overload everyone is late. Chapter 37 · Mission control

edge

The moment when a digital signal changes level: a rising edge goes from 0 to 1, a falling edge from 1 to 0. Chapter 31 · Memory and the clock

edges

A link between two vertices of a graph. An undirected edge goes both ways; a directed edge (an arc) goes only from one vertex to the other. Chapter 19 · Six handshakes

Edit distance

The smallest number of insertions, deletions and substitutions of characters that turn one string into another. The Levenshtein distance; a table computes it in time proportional to the product of the lengths. Chapter 22 · Remember instead of recomputing

ELIZA effect

People’s tendency to credit a program with understanding and feelings it doesn’t have; named after the ELIZA chatbot (1966). Chapter 7 · A conversation made of strings

encapsulation

The principle that an object hides how it is built and changes its state only through its own methods, which enforce its rules. From outside you can see what the object can do, but not how it does it. Chapter 12 · The island of rabbits and foxes

encoding

An agreement on which number (or which bytes) stands for each character: ASCII, KOI-8, CP1251, UTF-8. Bytes can be read correctly only with the same encoding they were written in. Chapter 28 · Everything is bits

entangled

The property of a state of several qubits that can’t be written as a product of the states of each one: the results of measuring them are correlated more strongly than any classical arrangement allows. Chapter 64 · The qubit lab

entropy

The average amount of information in one character of a source: H = −Σ p(x) log₂ p(x) bits. By Shannon’s theorem it is a lower bound on the average number of bits per character for any lossless compression. Chapter 47 · The packing contest

environment

The chain of frames in which an interpreter looks up the values of names: first the current frame, then the outer one, and so on to the global frame. Every function call gets a new frame, and its outer frame is the one where the function was made (under lexical scope). Chapter 51 · The nesting doll

environment variables

A “name = value” pair that a process receives from its parent along with the rest of its environment: PATH, HOME, LANG and others. Children get a copy; changes made in the child don’t affect the parent. Chapter 36 · A tour of a living system

evaluation function

Evaluation function: an approximate score for an unfinished position (who is closer to winning), used when the game can’t be counted out to the end. The search stops at a set depth and takes this score in place of the exact value. Chapter 62 · The bot tournament

event loop

The dispatcher of cooperative coroutines: it keeps a queue of ready ones and a list of waiting ones (for a timer, the network, a file), resumes the ready ones in turn and, when none is ready, sleeps until the nearest event. Chapter 37 · Mission control

event-driven simulation

A way to simulate a system by jumping from event to event: future events wait in a priority queue ordered by time, and the program takes out the nearest one, handles it and adds new ones. Chapter 18 · Who is next

eventual consistency

The guarantee that if no new changes arrive, all copies of the data eventually become identical. At any given moment, different copies may answer differently. Chapter 44 · The parliament of Paxos

exception

A signal of an error that interrupts normal execution: instead of returning a value, a function “throws” an exception object, which flies up to the functions that called it until one of them catches it. Chapter 11 · The inquiry report

exchange argument

A way to prove a greedy algorithm correct: take any optimal solution and show that it can be changed, by swapping part of it for the greedy choice, without becoming worse. Chapter 23 · Greed and electricity

exclusive or

Exclusive or: a logical operation that equals 1 when exactly one of two bits is 1. In Python, the operator ^ applies it to every pair of bits of two numbers. XOR-ing twice with the same key gives back the original: (m ^ k) ^ k == m. Chapter 59 · The cipher bureau

exit code

The number a process finishes with, which its parent receives: 0 means all is well, anything else means something went wrong. Chapter 36 · A tour of a living system

exploit

An exploit: a specific technique or program that uses a vulnerability to achieve an attacker’s goal. Knowing a vulnerability and having a working exploit are two different things. Chapter 61 · The training range

exponential

Time that grows as 2ⁿ (or some other number to the power n): every new item of the input multiplies the work. Going through all subsets, the naive recursive fib. Chapter 13 · What a program costs

f-string

A string with the letter f before the quote: f"…{expression}…". Python works out the expressions in curly braces and puts their values into the text. Chapter 2 · Names and values

false positive

A “yes” where the correct answer is “no”: for example, a Bloom filter reporting an item as added when it never was. Chapter 26 · Let's flip a coin

feedback

A connection in which a circuit’s output is fed back to its input. An odd number of inversions in the loop gives oscillation, an even number a stable state, that is, memory. Chapter 31 · Memory and the clock

fetch–decode–execute cycle

The work of a processor in a loop: fetch an instruction from memory at the address in the program counter, decode it, execute it, then go on to the next one. Chapter 32 · You are the processor

file descriptor

A small integer by which a process knows an open file, pipe or device: its index in the process’s table of open files. 0, 1 and 2 are standard input, standard output and standard error. Chapter 36 · A tour of a living system

file system

The part of the operating system that turns a disk’s array of blocks into a tree of named directories and files: it records which blocks belong to which file and updates those records on every change. Chapter 40 · The rescue operation

filters

A program that reads data from standard input, transforms it and writes the result to standard output; a link in a shell pipeline, such as grep, sort, uniq, cut, tr or head. Chapter 36 · A tour of a living system

fingerprints

A small sample of the hashes of a document’s shingles that is enough to find pieces it shares with other documents. Winnowing chooses the fingerprints so that any long enough shared piece gives at least one shared fingerprint. Chapter 27 · A needle in a haystack

finite-state machine

A device or program with a finite number of states: at every step the next state is chosen from the current state and the next input. Chapter 31 · Memory and the clock

flags

A single bit in a processor that reports something about the result of the last operation: whether it is zero, whether there was a carry, whether it is negative. Chapter 30 · The machine does arithmetic

floating-point numbers

A fractional number in the IEEE 754 format: a sign, an exponent (a power of two) and a mantissa (the significant binary digits). A 64-bit float has 1, 11 and 52 bits for them; its precision is about 16 decimal digits. Chapter 28 · Everything is bits

flow

Numbers f(u, v) on the edges of a network that never exceed the capacities and that, at every vertex except the source and the sink, balance: as much flows in as flows out. Chapter 25 · Flows and matchings

flow control

The receiver tells the sender how much free room is left in its buffer, and the sender sends no more than that. It protects a slow receiver from a fast sender. Chapter 42 · Inventing a protocol

fold

Reducing a sequence to a single value: a function of two arguments stirs each item in turn into an accumulator; in Python, functools.reduce. Chapter 10 · Functions as values

for a function’s result, after a colon for a variable. Python itself doesn’t check them; mypy and code editors read them.">type annotations

Chapter 53 · Null on trial

foreign key

A column of a table whose values are primary keys of another table. This is how a relational database records a link: an airport refers to its country by the country’s code. Chapter 45 · The archivist

forwarding

A remedy for data hazards: a result the ALU has just computed is fed straight to the input of the next instruction, without waiting for it to be written to a register. Chapter 35 · The pipeline and the fortune-teller

frames

A piece of physical memory the size of a page. Every page of a process that is in memory right now sits in some frame. Chapter 38 · The hotel of addresses

full adder

A circuit that adds three bits (one bit of each number and the carry from the column to the right) and puts out a sum bit and a carry into the next column. Chapter 29 · Logic from switches

full scan

A way of carrying out a query in which the database reads every row of the table in turn and checks the condition for each one. It costs O(n); in SQLite’s plan it is called SCAN. Chapter 46 · The library and the bank

function

A named piece of a program that can be called many times with different arguments; it may hand back a result with return. Chapter 5 · Words of your own

functional programming

A programming paradigm in which a program is a composition of functions rather than a sequence of commands: new values instead of assignments, recursion and higher-order functions instead of loops. Lisp, ML, Haskell. Chapter 49 · The museum of languages

galactic algorithms

An algorithm with a better asymptotic bound than the known ones, but with constant factors so large that the gain would show only on inputs that don’t exist on Earth. Its value is that it moves the boundary of what is known. Chapter 65 · The blank spots

game tree

Game tree: the root is the current position, the branches from each node are all the legal moves, and the leaves are finished games (a win, a loss, a draw). The levels alternate: one player’s move, then the other’s. Chapter 62 · The bot tournament

garbage collector

The part of a language that finds and frees objects the program can no longer reach. In CPython it supplements reference counting and looks for cycles of objects that hold each other. Chapter 38 · The hotel of addresses

generators

A function with yield. Calling it only creates an object that hands out values one at a time, each time carrying on from where it stopped. Chapter 10 · Functions as values

generic types

A type with a type parameter: list[T], dict[K, V], Option<T>. One generic function works with any T, and at each call the type checker puts a concrete type in place of T. Chapter 53 · Null on trial

global interpreter lock

Global Interpreter Lock: a lock that in the standard build of CPython lets only one thread of a process execute Python bytecode at a time. A thread releases it while waiting for input or output, and every few milliseconds when the interpreter asks. Chapter 39 · Races

GPU

Graphics processing unit: thousands of simple cores that run the same program on different data. Built to compute pixels, today it is the main machine for training neural networks. Chapter 35 · The pipeline and the fortune-teller

gradient descent

A way to find the minimum of a function of many variables: from the current point, take a step against the gradient, w ← w − η·∂L/∂w, and repeat. Almost every machine learning model is trained this way. Chapter 63 · The machine learns

gradual typing

Typing in which static types can be added to a program a little at a time: the annotated parts are checked before the program runs, the rest only while it runs. Python with mypy and TypeScript work this way. Chapter 53 · Null on trial

grammar

A finite set of rules that builds all the correct phrases of a language, and only those. Each rule says what a nonterminal can be replaced with: S → ka | ka lo S. Chapter 50 · The field linguist

graph

A set of vertices and edges, each edge joining two vertices. A graph records only what is connected to what; distances, shapes and positions are not in it. Chapter 19 · Six handshakes

greedy algorithm

An algorithm that builds its answer step by step, at each step making the choice that is best by a simple local rule and never undoing it. Chapter 23 · Greed and electricity

half adder

A circuit that adds two bits: it puts out a sum bit (a XOR b) and a carry bit (a AND b). Chapter 29 · Logic from switches

halting problem

The question: given the text of a program P and its input x, determine whether P finishes on x in a finite number of steps. Turing (1936) proved that no algorithm answers it for all P and x. Chapter 56 · A conversation with the Oracle

happened before

A relation between the events of a distributed system: a → b if a and b happened on one node and a came first, or a is the sending of a message and b its arrival, or a chain of such steps leads from a to b. If neither a → b nor b → a, the events are concurrent. Chapter 44 · The parliament of Paxos

hash function

A function that turns a key (a string, a number, a tuple) into an integer. It must turn equal keys into equal numbers; different keys it should preferably turn into different numbers, scattered far apart. Chapter 16 · Hash tables: attack and defense

hash table

A data structure: an array of buckets in which the record with key k sits in bucket number hash(k) mod m. Lookup, insertion and deletion take O(1) on average. Python’s dict and set are built this way. Chapter 16 · Hash tables: attack and defense

hashable

An object that has a hash (hash(x) works) which doesn’t change during the object’s lifetime. Hashable objects can be dictionary keys and set elements: numbers, strings, tuples of hashable items. Chapter 16 · Hash tables: attack and defense

headers

A “Name: value” line in an HTTP request or response. Headers carry everything except the content itself: the site’s name, the type and length of the data, caching rules, cookies. Chapter 43 · Anatomy of this page

heap

A binary tree in which the key of every node is no larger than the keys of its children (the heap property); the smallest key is at the root. Usually stored in an array: the children of cell i are in cells 2i+1 and 2i+2. Chapter 18 · Who is next

Heapsort

A sort: build a heap from the array, then n − 1 times move the root to the end and sift down. Time O(n log n) in the worst case, extra memory O(1); not stable. Chapter 18 · Who is next

height of the tree

The number of nodes on the longest path from the root of a tree down to a leaf: an empty tree has height 0, a single node 1. A search in a search tree makes no more comparisons than the height. Chapter 17 · A garden of search trees

heuristic

A quick estimate that guides a search, for example the straight-line distance to the goal. By itself it doesn’t guarantee a correct answer. Chapter 24 · The navigator

hexadecimal

Writing numbers in base 16 with the digits 0–9 and the letters a–f. One hexadecimal digit is four bits, a byte is two digits: 0xFF = 255. Chapter 28 · Everything is bits

higher-order function

A function that takes other functions as arguments or returns a function as its result: map, filter, sorted with key, decorators. Chapter 10 · Functions as values

HTTP

HyperText Transfer Protocol, the protocol of the web: the client sends a request (a method, a path, headers, sometimes a body), and the server answers with a status code, headers and a body. In version 1.1 it is plain text. Chapter 43 · Anatomy of this page

HTTPS

HTTP inside an encrypted TLS connection: an outsider on the path sees which server you are talking to but sees neither the addresses of the pages nor their contents, and can’t quietly alter them. Chapter 43 · Anatomy of this page

Huffman code

A prefix code of the least cost for given letter frequencies; built by repeatedly merging the two rarest letters (subtrees) into one. Chapter 23 · Greed and electricity

imperative programming

A programming paradigm in which a program is a sequence of commands that change the state of memory: assignments, loops, jumps. FORTRAN, C, Pascal, most Python code. Chapter 49 · The museum of languages

index

The number of an item in a list or string, counting from zero: a[0] is the first item, a[-1] the last. Chapter 6 · Lists

index

A separate structure next to a table: the values of the chosen columns, kept in order for fast searching, each with the address of its row (in SQLite, the rowid). It speeds up searching and sorting but slows down writing and takes up space. Chapter 46 · The library and the bank

index of coincidence

The probability that two letters picked from a text at random are the same. About 0.066 for English text, 1/26 ≈ 0.038 for a uniform random mix of 26 letters. A substitution cipher doesn’t change it. Chapter 59 · The cipher bureau

infinite loop

A loop whose condition never turns false, so the loop itself never ends. Chapter 4 · Again and again

infix notation

The familiar way of writing an expression, with the operator between its operands: 3 + 4 · 5. It needs brackets and rules of operator precedence. Chapter 15 · Stacks, queues and a calculator

inheritance

A way to define a class through another one: class Fox(Animal) gets all the attributes and methods of Animal and can add its own or replace the inherited ones. Chapter 12 · The island of rabbits and foxes

inode

Index node: a Unix file system’s record of a file, with its size, owner, permissions, modification time and the list of blocks that hold its contents. The file’s name is not in it: names are kept in directories. Chapter 40 · The rescue operation

insertion sort

A sort: items are taken one at a time and inserted into their place in the already ordered left part, shifting larger items to the right. From n − 1 to n(n − 1)/2 comparisons, depending on how shuffled the data is. Chapter 20 · The sorting tournament

instance

An object made from a class: after bunny = Rabbit(3, 5), bunny is an instance of the class Rabbit. Every instance has attributes of its own. Chapter 12 · The island of rabbits and foxes

instruction set

The complete list of instructions a processor understands, together with the rules for writing them as bytes. Chapter 32 · You are the processor

integer programming

The problem of minimizing a linear function of some variables under linear constraints when the variables must be integers (often 0 or 1). It is NP-hard, but solvers handle huge practical instances with branching and cutting planes. Chapter 58 · The salesman’s expedition

interference

The adding up of the amplitudes of different computational paths that lead to the same outcome: equal signs reinforce the outcome, opposite signs cancel it. It is where quantum algorithms get their advantage. Chapter 64 · The qubit lab

interleaving

One of the possible orders in which the steps of several threads are mixed together, each thread’s own steps keeping their order. Chapter 39 · Races

intermediate representation

A compiler’s internal form of a program: simpler than the source language and not tied to any particular processor, for example instructions for an imaginary stack machine or three-address code. Optimizations are done on it, and machine code is generated from it. Chapter 52 · Closing the circle

interpreter

A program that runs another program instruction by instruction, on the fly: it reads an instruction, carries it out and moves on to the next. Chapter 33 · An X-ray of Python

interrupt

A signal to the processor from the timer or a device: the processor sets the current program aside, remembers where it stopped and runs a handler in the operating system kernel. Chapter 37 · Mission control

inversion

A pair of positions i < j where a[i] > a[j]: two items that are out of order. A sorted list has no inversions, a reversed one has n(n − 1)/2. Chapter 20 · The sorting tournament

inverted index

A dictionary “word → list of the documents that contain it” (usually with the number of occurrences and their positions). It is built in advance, and a query comes down to a few dictionary lookups and an intersection of lists. Chapter 48 · A search engine for our textbooks

IP address

The address of a machine on the internet. In IPv4 it is 32 bits, written as four numbers from 0 to 255 separated by dots: 192.168.1.23. The first bits name the network, the rest the machine in it. Chapter 41 · A day in the life of a packet

isolation level

A database setting: which anomalies of concurrent work the transactions are protected from. The SQL standard names four levels: READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ, SERIALIZABLE. Chapter 46 · The library and the bank

iteration

One pass through the body of a loop. Chapter 4 · Again and again

Jaccard index

A measure of the similarity of two sets: the size of their intersection divided by the size of their union. 1 means the sets are equal, 0 means they have nothing in common. Chapter 27 · A needle in a haystack

JIT compilation

Compilation while the program runs: the runtime notices the pieces of code that run most often and translates them into machine code tailored to the types it has met. Chapter 33 · An X-ray of Python

join

An operation on two tables: each row of the first is glued to those rows of the second for which the ON condition holds. LEFT JOIN also keeps the rows of the first table that have no match, filling in the missing values with NULL. Chapter 45 · The archivist

journal

A separate area of the disk where a file system (or a database) first writes all the intended changes, with a “done” mark, and only then makes them in place. After a crash, complete records in the journal are replayed and incomplete ones are thrown away. Chapter 40 · The rescue operation

JSON

JavaScript Object Notation: a text format for data made of dictionaries (in curly braces), lists, strings, numbers, true/false and null; websites and programs use it to exchange data. Chapter 8 · Dictionaries and the telegraph

Karnaugh map

A truth table laid out as a rectangle so that neighboring cells differ in the value of one input; groups of neighboring ones give a simplified formula. Chapter 29 · Logic from switches

Kerckhoffs’s principle

Auguste Kerckhoffs’s rule (1883): the security of a cipher must not depend on keeping its design secret. The enemy knows the system; only the key stays secret. Chapter 59 · The cipher bureau

kernel

The central part of the operating system: it runs in the processor’s privileged mode, manages memory, processes, files and devices, and carries out programs’ requests, the system calls. Chapter 36 · A tour of a living system

key

What a dictionary looks a value up by: a word, a letter, a number or a tuple. Keys in a dictionary don’t repeat. Chapter 8 · Dictionaries and the telegraph

key

The secret parameter of a cipher: a number, a word, a table or random bytes. Whoever knows the cipher and the key reads the ciphertext; whoever knows only the cipher should not be able to. Chapter 59 · The cipher bureau

Knuth–Morris–Pratt algorithm

The substring search algorithm of Knuth, Morris and Pratt (1977): it walks through the text without going back and, after a mismatch, shifts the pattern according to the prefix function. Time O(n + m). Chapter 27 · A needle in a haystack

Kolmogorov complexity

The length of the shortest program that prints a given string and halts. The limit of compression for an individual string; no algorithm can compute it. Chapter 47 · The packing contest

Lamport clocks

Lamport’s logical clock: every node keeps a counter. It goes up by 1 before every event; a message carries the sender’s counter, and the receiver sets its own to the larger of the two plus 1. If a → b, the stamp of a is less than the stamp of b. Chapter 44 · The parliament of Paxos

language model

A model that takes the beginning of a text and estimates the probabilities of the next character, word or piece of a word. Choosing continuations one after another, it writes text. Chapter 63 · The machine learns

Las Vegas algorithm

A randomized algorithm that always answers correctly; only its running time is random. Chapter 26 · Let's flip a coin

latch

The simplest one-bit memory cell: a loop of two gates with inputs for writing. An SR latch is set to 1 or reset to 0 through separate inputs; a D latch copies its input D while it is open, and once closed it holds the last value. Chapter 31 · Memory and the clock

latency

The time from a request to its answer: how long one access to memory, a disk or a server takes. Not to be confused with bandwidth, how much data gets through per second. Chapter 34 · Near and far

lazy evaluation

Computing values only when they are asked for, and no more than asked: that is how generators, map and filter work. Chapter 10 · Functions as values

leader election

The procedure by which the nodes of a distributed system choose one coordinator. In Raft a candidate needs the votes of a majority, and each node votes at most once per term. Chapter 44 · The parliament of Paxos

learning rate

The factor η in gradient descent: what share of the gradient is subtracted from the weights at each step. Too small, and training drags on; too large, and the loss grows and the weights fly apart. Chapter 63 · The machine learns

leaves

A tree node without children: the place where a branch ends. Chapter 17 · A garden of search trees

lexer

The first stage of parsing a program: it walks the text from left to right and cuts it into tokens (numbers, names, operators, strings), throwing away spaces and comments. Also called a lexical analyzer or tokenizer. Chapter 50 · The field linguist

lexical scope

The rule by which a function looks up unfamiliar names where it is written in the program text (in the frame where it was made), not where it is called from. Python, Scheme, JavaScript and almost every modern language work this way. Chapter 51 · The nesting doll

linear

Time proportional to the size of the input n: twice the data, twice the time. A list’s sum and a search by brute force work this way. Chapter 13 · What a program costs

linear search

Search by brute force: check the items one by one until the right one turns up. At most n comparisons; works on any list. Chapter 20 · The sorting tournament

link farm

A set of pages created only to link to the page being promoted and raise its PageRank. One of the kinds of search spam. Chapter 48 · A search engine for our textbooks

linked list

A chain of nodes in which every node holds a value and a reference to the next one. Inserting and deleting next to a known node cost O(1), access by position O(n). Chapter 14 · How a list lives in memory

list

An ordered collection of values under one name: [5.4, 5.1, 6.6]. Its items are numbered from zero, and a list can be changed: items added, removed, rearranged. Chapter 6 · Lists

load factor

The ratio of the number of records in a hash table to the number of its buckets, α = n/m. It sets the average chain length, and so the time of a lookup. Chapter 16 · Hash tables: attack and defense

local optimum

A solution that no single move of local search can improve. It may be much worse than the best one, the global optimum. Chapter 58 · The salesman’s expedition

local search

A way to solve optimization problems: take some solution and improve it by small changes (moves) for as long as improvements can be found. An example is 2-opt for the traveling salesman. Chapter 58 · The salesman’s expedition

local variables

A variable created inside a function, parameters included; it exists only while the call lasts and can’t be seen from outside. Chapter 5 · Words of your own

locality

The tendency of programs to access data in a non-random way: what was touched recently gets touched again (in time), and so do the neighbors of what was touched recently (in space). Every cache relies on it. Chapter 34 · Near and far

lock

A synchronization object (a mutex, from “mutual exclusion”): only one thread can hold it, and the others wait until the owner lets it go. In Python, threading.Lock. Chapter 39 · Races

logarithmic

Time that grows as log n: doubling the input adds one step. Binary search works this way. Chapter 13 · What a program costs

logic gate

An electronic circuit with several inputs and one output that computes a logical function: AND, OR, NOT, NAND and others. Chapter 29 · Logic from switches

logic programming

A programming paradigm in which a program is a set of facts and rules, and computation is a search for the answer to a query: the system tries the rules itself, substitutes values for the variables and backs out of dead ends. Prolog, Datalog. Chapter 49 · The museum of languages

logical qubit

A qubit encoded by an error-correcting code in many physical qubits. If physical errors are rarer than a threshold, the logical qubit’s errors fall exponentially as the code grows. Chapter 64 · The qubit lab

longest common subsequence

The longest sequence that can be obtained by striking out elements from each of two given ones. The basis of programs that compare texts: everything not in it was deleted or added. Chapter 22 · Remember instead of recomputing

loop

A construction that repeats a block of instructions: a set number of times, or for as long as a condition holds. Chapter 4 · Again and again

loop invariant

A claim about the variables of a loop that is true before the first iteration and stays true after each one. Together with the exit condition it proves that the loop does what it should. Chapter 20 · The sorting tournament

loss function

A number that shows how wrong a model is on the examples of the training set. Training is a search for the weights that make it as small as possible. Chapter 63 · The machine learns

lossless compression

Compression after which unpacking returns the original data bit for bit. Texts, programs and tables are compressed this way: ZIP, gzip, PNG, bzip2. Chapter 47 · The packing contest

lossy compression

Compression after which unpacking returns the data only approximately: what the eye or the ear won’t catch is thrown away. JPEG, MP3, video. Chapter 47 · The packing contest

lost update

An anomaly of concurrent work: two transactions read the same value, each writes its own, and the change made by the one that wrote first is lost. Chapter 46 · The library and the bank

LRU

Least Recently Used: an eviction rule that throws out of a full cache the item that has gone the longest without being accessed. Chapter 34 · Near and far

LZ77

The compression algorithm of Lempel and Ziv (1977): a repeat is replaced by a reference “go back so many characters and copy so many.” References are sought in a sliding window of the last few thousand characters. Chapter 47 · The packing contest

LZW

The Lempel–Ziv–Welch compression algorithm (1984): the packer and the unpacker build the same dictionary of phrases as they go, and the output is phrase numbers. Used in compress and GIF. Chapter 47 · The packing contest

MAC address

The address of a network card at the link layer (Ethernet, Wi-Fi): 48 bits, usually written as six pairs of hexadecimal digits. It means something only within one local network. Chapter 41 · A day in the life of a packet

machine code

A program in the form in which the processor executes it: a sequence of numbers, the instructions, in memory. Chapter 32 · You are the processor

machine learning

A way to build programs from examples with answers: the rule is fitted by changing the model’s adjustable numbers until it gives the right answers on the examples. Chapter 63 · The machine learns

man-in-the-middle attack

An attack in which an adversary gets between two parties, poses to each as the other and relays their messages, reading or changing them. The defense is authentication: a signature. Chapter 60 · A secret in plain sight

mark and sweep

A way of collecting garbage in two passes: mark every object reachable by references from the roots (the program’s variables and stack), then go through the whole memory and free the unmarked ones. Unlike reference counting, it also collects loops. Chapter 51 · The nesting doll

matching

A set of edges of a graph with no shared endpoints: every vertex belongs to at most one pair. Chapter 25 · Flows and matchings

matrix multiplication exponent

The number ω: the infimum of the exponents a for which n×n matrices can be multiplied in O(nᵃ) arithmetic operations. It is known that 2 ≤ ω < 2.371177 (2026); the exact value is unknown. Chapter 65 · The blank spots

measurement

An operation that gives a classical result: the basis state |k⟩ with probability |amplitude of k|². After the measurement the system is in that basis state, and the old amplitudes are lost. Chapter 64 · The qubit lab

memoization

Remembering a function’s answers: before computing, look in the table of what is already known; after computing, write the result there. Turns repeated recursive calls into one. Chapter 22 · Remember instead of recomputing

memory hierarchy

The arrangement of a computer’s memory in steps: registers, L1–L3 caches, main memory, disk. Each step is larger and slower than the one above it; frequently needed data is kept on the upper steps. Chapter 34 · Near and far

memory leak

Memory a program holds although it no longer uses it. In garbage-collected languages these are usually objects still reachable through a forgotten reference: a growing list, a cache without a limit. Chapter 38 · The hotel of addresses

memory-mapped input/output

A way for a processor to talk to devices in which a device answers to certain memory addresses: writing to such an address hands a byte to the device, and reading takes a byte from it. Chapter 32 · You are the processor

message queue

A way for threads or processes to communicate: the sender puts messages into a queue, and the receiver takes them out in the same order; the waiting and the locking are hidden inside the queue. Chapter 39 · Races

metacircular

An interpreter for a language written in that same language, in which every feature of the language is defined through the same feature of the host: if through if, a call through a call. The classic example is Lisp’s eval written in Lisp. Chapter 51 · The nesting doll

metastability

A state of a memory cell in which its output hangs between 0 and 1 for a while and then falls unpredictably to one of the two values. It happens when an input changes at the moment of writing. Chapter 31 · Memory and the clock

method

The first word of an HTTP request: what the client wants done. GET fetches, HEAD fetches only the headers, POST sends data, PUT puts a document at an address, DELETE deletes. Chapter 43 · Anatomy of this page

methods

A function defined inside a class. You call it through a dot, as in bunny.hop(1, 0); the object before the dot goes into the parameter self. Chapter 12 · The island of rabbits and foxes

minimax

Minimax: a way to evaluate a position in a two-player game. The value of a node is the maximum over its children when it is the turn of the player who wants more, and the minimum when it is the turn of the one who wants less. A move chosen this way assumes the opponent replies as well as possible. Chapter 62 · The bot tournament

minimum spanning tree

A spanning tree of a weighted graph with the smallest total weight of its edges. Chapter 23 · Greed and electricity

MMU

Memory management unit: the part of the processor that, on every memory access, translates the virtual address into a physical one and checks the access rights. Chapter 38 · The hotel of addresses

model

In machine learning, a function with adjustable numbers (weights): it turns an input into an answer, and training fits the weights to examples. Chapter 63 · The machine learns

Monte Carlo algorithm

A randomized algorithm whose running time is bounded but whose answer may be wrong with a small probability; repetition makes that probability as small as you like. Chapter 26 · Let's flip a coin

Monte Carlo method

A way to find a number (a probability, an area, an average) by setting up a random experiment in which that number is the share of successes or the average outcome, and repeating the experiment many times. Chapter 26 · Let's flip a coin

Monte Carlo tree search

Monte Carlo tree search (MCTS): instead of an evaluation function, a position is judged by many random playouts to the end (the share of wins). The tree grows toward promising moves but keeps trying the others. The core of AlphaGo’s strength at Go. Chapter 62 · The bot tournament

Moore’s law

Gordon Moore’s observation (1965, revised in 1975): the number of transistors on a chip doubles about every two years. It describes an industry, not a law of nature. Chapter 35 · The pipeline and the fortune-teller

MTU

Maximum Transmission Unit: the largest packet a link can carry in one go. For Ethernet it is 1500 bytes; a larger packet has to be cut up. Chapter 41 · A day in the life of a packet

multilevel feedback queue

Multilevel feedback queue: several queues with different priorities; a new job starts in the top one, and a job that uses up its whole quantum moves down a level, where the quanta are longer. Invented for CTSS (1962). Chapter 37 · Mission control

multiplexer

A selector circuit: a control signal (an address) decides which of several inputs gets through to the output. Chapter 29 · Logic from switches

mutable

A mutable object can be changed in place, without creating a new one: a list, a dictionary, a set. Immutable ones—numbers, strings, tuples—can only be replaced by others. Chapter 6 · Lists

mutants

A copy of a program with one small bug planted on purpose: a different comparison, a shifted limit, a missing check. Good tests should catch it. Chapter 11 · The inquiry report

NAND

The NOT-AND gate: it puts out 0 only when both inputs are 1, and 1 in every other case. Any logic circuit can be built from such gates alone. Chapter 29 · Logic from switches

NAT

Network Address Translation: the router at the edge of a home network replaces the private address and port in outgoing packets with its own public address and a free port, remembers the pair, and uses it to pass the answers back. Chapter 42 · Inventing a protocol

negative cycle

A cycle in a weighted graph whose weights add up to a negative number; if it is reachable, shortest paths through it don’t exist. Chapter 24 · The navigator

nested loop

A loop inside the body of another loop: on every iteration of the outer loop it runs from start to finish. Chapter 4 · Again and again

network

A directed graph with two marked vertices, the source s and the sink t, in which every edge has a capacity: how much can be carried along it. Chapter 25 · Flows and matchings

network partition

A break in the network after which the nodes fall into groups: messages travel within a group but not between groups. Each group sees the other as failed. Chapter 44 · The parliament of Paxos

neural network

A model made of layers of “neurons”: each neuron computes a weighted sum of the previous layer’s outputs and passes it through a nonlinear activation function. The layers between input and output are called hidden. The weights of all layers are fitted by gradient descent. Chapter 63 · The machine learns

node

An element of a linked data structure: an object that holds a value and references to neighboring nodes. Chapter 14 · How a list lives in memory

nondeterministic

Nondeterministic finite automaton: one symbol may lead from a state along several transitions or along none, and ε-transitions read no symbol. It accepts a string if at least one path for that string leads to an accepting state. Chapter 54 · Automata and regular expressions

nonterminals

The name of a part of a phrase in a grammar (expression, term, statement). The rules replace it with sequences of other nonterminals and terminals, the words of the language itself. Chapter 50 · The field linguist

normalization

Restructuring a database schema so that every fact is stored in one place: repeated information moves to a separate table and is referred to by a key. It protects against discrepancies when data is edited. Chapter 45 · The archivist

NP

The decision problems in which every “yes” answer is confirmed by a certificate of polynomial length that can be checked in polynomial time. Seating guests, sudoku and the satisfiability of formulas are in NP. Chapter 57 · Gödel’s letter

NP-complete

A problem in NP to which every problem in NP reduces in polynomial time. A fast algorithm for one NP-complete problem would give fast algorithms for all of NP. Examples: SAT, 3-SAT, clique, Hamiltonian cycle, n²×n² sudoku. Chapter 57 · Gödel’s letter

NP-hard

A problem to which every problem in NP reduces in polynomial time. It is no easier than the NP-complete problems but need not lie in NP itself: it may be an optimization problem (the traveling salesman’s shortest tour) or even an undecidable one. Chapter 57 · Gödel’s letter

NULL

A mark in a table cell: there is no value, or it is unknown. NULL is not equal to anything, not even another NULL; a comparison with it gives “unknown.” You test for it with IS NULL. Chapter 45 · The archivist

object

A value in the machine’s memory: it has a type, contents and an identity of its own (its id number). Names in Python point to objects. Chapter 2 · Names and values

object composition

Building an object out of other objects: the island keeps a meadow and a list of animals in its attributes and hands work over to them. The relation is “the island has a meadow,” unlike inheritance, where “a fox is an animal.” Chapter 12 · The island of rabbits and foxes

object-oriented programming

Object-oriented programming: a paradigm in which a program is a collection of objects, each keeping its own state and answering messages (method calls). Simula, Smalltalk, Java; in Python, classes. Chapter 49 · The museum of languages

one-time pad

A cipher whose key is a random sequence as long as the message and used only once; each symbol is encrypted with its own symbol of the key (by a shift or by XOR). Unbreakable if these conditions are met. Chapter 59 · The cipher bureau

one-way

A function whose value is quick to compute, while finding an argument from the value is practically impossible: multiplying two large primes, say, against factoring the product. Nobody has proved that such functions exist. Chapter 60 · A secret in plain sight

opcode

The number in a processor instruction that says which operation to perform: in Iskra-8, for example, 5 means addition and 6 means subtraction. Chapter 30 · The machine does arithmetic

open addressing

A way of resolving collisions without chains: each cell of a hash table holds at most one record, and if a cell is taken, the record looks for a free one along a route known in advance. CPython’s dict and set are built this way. Chapter 16 · Hash tables: attack and defense

operating system

The program that manages a computer’s hardware and shares it among other programs: it gives them processor time, memory, and access to files and devices, and it protects programs from one another. Chapter 36 · A tour of a living system

optimal substructure

A property of an optimization problem: the best solution of the whole problem is made of the best solutions of its subproblems. Without it, a table of best answers doesn’t help. Chapter 22 · Remember instead of recomputing

option types

The type “a value or nothing”: str | None (Optional[str]) in Python, String? in Kotlin, Option in Rust, Maybe in Haskell. The type checker won’t let you use the value until it is proved to be there. Chapter 53 · Null on trial

overfitting

When a model answers well on its training examples and noticeably worse on new ones: it has memorized the quirks of the examples instead of the pattern. Chapter 63 · The machine learns

overflow

What happens when the result of a computation doesn’t fit in the number of bits set aside for it: the machine either wraps it around or reports an error. Chapter 11 · The inquiry report

P

The decision problems that an algorithm solves in polynomial time. Shortest paths, sorting, matching and testing whether a number is prime are all in P. Chapter 57 · Gödel’s letter

packet

A portion of data with a header that says where it is going and where it came from. A network carries packets one by one: each node takes in a whole packet and sends it on. Chapter 41 · A day in the life of a packet

packet switching

A way to build a network in which data is cut into packets with addresses, and nodes pass each packet on separately. The links are shared by everyone sending at the moment; nobody has a line of their own. Chapter 41 · A day in the life of a packet

page fault

An interrupt the processor raises when the page a program has accessed is not in memory (or may not be accessed that way). The OS kernel brings the page in, from disk or as a fresh one, fixes the table and repeats the instruction. Chapter 38 · The hotel of addresses

page table

A table the OS kernel keeps for each process: for every page, which frame it is in (or that it isn’t in memory) and what may be done with it. The MMU reads it when it translates addresses. Chapter 38 · The hotel of addresses

PageRank

A measure of a page’s importance computed from the links to it (Brin and Page, 1998): the share of time a random reader spends on the page if with probability d they follow a random link and otherwise open a random page. Computed by the power method. Chapter 48 · A search engine for our textbooks

pages

A fixed-size piece of the address space (usually 4 KiB); the unit in which virtual memory translates addresses, protects data and moves it around. Chapter 38 · The hotel of addresses

palindrome

A word or phrase that reads the same from left to right and from right to left, if you ignore spaces, punctuation and case. Chapter 7 · A conversation made of strings

paradigms

A general view of what a program is and what it is made of: commands, functions, facts and rules, objects, or operations on arrays. A paradigm shapes the look of code more than syntax does. Chapter 49 · The museum of languages

parameter

A name in a function’s header under which the function receives an input value: in def draw_square(size) it is size. Chapter 5 · Words of your own

parity bit

An extra bit that makes the number of ones in a word even (or odd). If the parity comes out wrong when the word is read, some bit has been corrupted. Chapter 31 · Memory and the clock

parse tree

The tree of a phrase’s derivation by a grammar: the start nonterminal at the root, the children of each nonterminal are the right-hand side of the rule applied to it, and the leaves, in order, are the words of the phrase. Chapter 50 · The field linguist

partition

The step of quicksort that rearranges the items so that those smaller than the pivot end up on the left and those larger on the right. Chapter 21 · Divide and conquer

pattern matching

Taking a value apart by patterns: the statement checks which variant the value matches and at once binds its parts to names. match in Python, case in Haskell and OCaml, match in Rust. Chapter 53 · Null on trial

peephole optimization

An optimization that looks at finished code through a narrow window of a few neighboring instructions and replaces wasteful combinations with cheaper ones: a PUSH followed at once by a POP becomes nothing, and so does a jump to the next line. Chapter 52 · Closing the circle

perceptron

The simplest trainable model: a weighted sum of the inputs plus a bias, and the answer is the sign of the sum. It learns by Rosenblatt’s rule (1958): on every mistake it adds the example to the weights with the sign of the right answer. Chapter 63 · The machine learns

perfect secrecy

The property of a cipher whose ciphertext carries no information about the message except its length: the probability of every message after the interception is the same as before. Proved by Shannon for the one-time pad. Chapter 59 · The cipher bureau

permissions

Nine bits on every file in Unix: read (r), write (w) and execute (x) for the owner, for the group and for everyone else. The kernel checks them against the process’s user every time a file is opened. Chapter 36 · A tour of a living system

Permutations

An arrangement of items in some order; n different items have n! permutations. Chapter 9 · A problem inside a problem

phishing

Phishing: faking an email, site or call so it looks like a trusted source, to get a person to type in a password or code themselves. It is checked by the sender’s address and by the fact that a legitimate service never asks for your password. Chapter 61 · The training range

PID

Process ID: the number by which the kernel knows a process. In Unix every process except the first has a parent with a PID of its own. Chapter 36 · A tour of a living system

pipe

A buffer in the kernel with two ends: what one process writes into one end, another reads from the other in the same order. The writer waits when the buffer is full, the reader when it is empty. Chapter 36 · A tour of a living system

pipeline

A way of building a processor in which an instruction passes through several stages (fetch, decode, execute, write-back) and different stages of different instructions run at the same time: a new instruction enters the pipeline every cycle. Chapter 35 · The pipeline and the fortune-teller

pipeline hazards

A situation in which the next instruction can’t move on to the next pipeline stage in this cycle: it needs a result that isn’t ready yet (a data hazard), nobody knows which instruction comes after a branch (a control hazard), or the unit it needs is busy (a structural hazard). Chapter 35 · The pipeline and the fortune-teller

pivot

The item quicksort splits the list around: smaller items go to its left, larger ones to its right. Chapter 21 · Divide and conquer

plaintext

A message in a form that can be read: before encryption or after decryption. Chapter 59 · The cipher bureau

ply

Ply: one move by one player. Search depth in games is measured in plies: “four plies ahead” means me, the opponent, me, the opponent. Chapter 62 · The bot tournament

pointer

A variable whose value is the address of another value in memory. In C, &x is the address of x, *p is whatever lies at address p, and p + 1 is the address of the next element of the same type. Chapter 33 · An X-ray of Python

polymorphism

The ability of code to treat objects of different classes alike: animal.step(island) calls different methods for a rabbit and for a fox, and the caller doesn’t care which one it has. Chapter 12 · The island of rabbits and foxes

polynomial reduction

A translation of the inputs of problem A into inputs of problem B, done in polynomial time, that turns “yes” into “yes” and “no” into “no.” If A reduces to B and B can be solved quickly, then A can be solved quickly too. Chapter 57 · Gödel’s letter

polynomial time

The algorithm makes at most C·nᵏ steps on an input of length n, for some constants C and k: n, n log n, n², n³… The exponential 2ⁿ and the factorial n! are not polynomials. Chapter 57 · Gödel’s letter

port

A number from 0 to 65535 in the transport header (UDP, TCP) by which the kernel decides which program on the machine gets the packet. A program “listens” on a port by binding a socket to it. Chapter 41 · A day in the life of a packet

Post-quantum cryptography

Cryptography built on problems for which no fast algorithm is known even on a quantum computer: lattices, hash functions, codes. NIST published the first standards in 2024. Chapter 60 · A secret in plain sight

posting list

The list of documents (page numbers) that contain a word: one line of an inverted index. It is kept sorted so that lists can be intersected quickly. Chapter 48 · A search engine for our textbooks

power method

A way to find the main eigenvector of a matrix: multiply a vector by the matrix again and again and see what it converges to. This is how PageRank is computed. Chapter 48 · A search engine for our textbooks

precedence

The rule for which operation in an expression without parentheses is done first: multiplication outranks addition, so 2 + 3 * 4 = 14. In a grammar it is set by levels: each rank of precedence gets its own nonterminal. Chapter 50 · The field linguist

preemption

Taking the processor away from a running program without its consent, on a timer interrupt or because a more urgent job has turned up. Chapter 37 · Mission control

prefix code

A code in which no codeword is the beginning of another, so that a message can be read without separators. Chapter 23 · Greed and electricity

prefix function

For a string p, the list π in which π[i] is the length of the longest border of the beginning p[:i + 1]. It takes linear time to compute and tells the KMP algorithm where to shift the pattern after a mismatch. Chapter 27 · A needle in a haystack

preprocessing

Work an algorithm does once, in advance, so that it can later answer many queries quickly: tables, indexes, shortcuts in a graph. Chapter 24 · The navigator

primary key

A column (or several columns) whose value names a row of a table unambiguously: the database won’t allow two rows with the same primary key. Chapter 45 · The archivist

principle of least privilege

The principle of least privilege: every part of a system runs with the minimum rights needed for its task, and no more. Then a bug or a break-in of one part does the least possible damage. Chapter 61 · The training range

priority inheritance

A rule for mutexes: while a higher-priority task waits for a mutex, the task holding it temporarily gets that higher priority; once it releases the mutex, it returns to its own. Chapter 39 · Races

priority inversion

A situation in which a high-priority task waits for a resource held by a low-priority task, which in turn is preempted by medium-priority tasks, so that the high-priority task in effect runs below medium priority. Chapter 39 · Races

priority queue

An abstract data type: items with priorities; the operations are adding an item and taking out the item with the highest priority (usually the one with the smallest key). Chapter 18 · Who is next

private addresses

An address from the ranges set aside for internal networks (10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16): anyone may use them at home, but they are not routed on the internet. Chapter 42 · Inventing a protocol

private key

The half of a key pair that the owner shows to no one: it is used to decrypt and to sign. Computing it from the public key is practically impossible. Chapter 60 · A secret in plain sight

process

A program while it runs: its code, its own memory, registers, open files and number (PID). One program can be run as several processes at once. Chapter 36 · A tour of a living system

processor

A device that fetches instructions from memory and executes them, over and over. It consists of a control unit, an ALU and registers. Chapter 32 · You are the processor

profiler

A program that watches another program run and shows how much time went into each function: where the time burns. Chapter 13 · What a program costs

program counter

A processor register that holds the address of the next instruction. After an instruction is fetched, it grows by the instruction’s length; a jump instruction writes a new address into it. Chapter 32 · You are the processor

protocol

An agreement on the format and order of the messages between the parties to an exchange: which fields come in which order, what to answer, and what to do if something goes wrong. Chapter 41 · A day in the life of a packet

protocol stack

A set of protocols stacked in layers: each layer solves one problem, uses the services of the layer below and serves the layer above. The internet has five layers: physical, link, network, transport and application. Chapter 41 · A day in the life of a packet

PSPACE

The problems that can be solved with polynomial memory, however much time it takes. It contains P, NP and co-NP. Typical PSPACE-complete problems are two-player games on boards of arbitrary size and formulas in which the quantifiers “there exists” and “for all” alternate. Chapter 57 · Gödel’s letter

public key

The half of a key pair that is published: it is used to encrypt messages to the owner or to check the owner’s signatures. For RSA it is the pair (n, e). Chapter 60 · A secret in plain sight

public-key encryption

Encryption with paired keys: you encrypt with the public key, known to everyone, and decrypt with the private key, known only to its owner. RSA is an example. Chapter 60 · A secret in plain sight

pumping lemma

A property of regular languages: every long enough string of the language can be cut into xyz with a nonempty y so that xy…yz (y repeated any number of times, zero included) is in the language too. A language that breaks the lemma is not regular. Chapter 54 · Automata and regular expressions

pure

A function whose result depends only on its arguments and which changes nothing around it: it prints nothing and leaves outside variables alone. Chapter 5 · Words of your own

pushdown automaton

A finite automaton with a stack of unlimited depth: at each step it can push a symbol onto the stack or pop the top one. Its languages are the context-free ones: balanced parentheses, the syntax of programming languages. Chapter 54 · Automata and regular expressions

quadratic

Time that grows as the square of the input size: twice the data, four times the time. The usual sign is that every item is compared with every other. Chapter 13 · What a program costs

quantization

Rounding values to steps of a given size: instead of the number itself, the number of its step is stored. The main source of loss in JPEG and MP3; the bigger the steps, the smaller the file and the worse the quality. Chapter 47 · The packing contest

quantum gates

An operation on qubits: a unitary matrix that the state vector is multiplied by. Unitary matrices preserve the length of a vector, and with it the sum of the probabilities, and they are always invertible. Chapter 64 · The qubit lab

qubit

A quantum bit: a system with two basis states |0⟩ and |1⟩ whose state is a unit vector α|0⟩ + β|1⟩ with complex amplitudes, |α|² + |β|² = 1. Chapter 64 · The qubit lab

query plan

A description of how the database intends to carry out a query: which tables to read in full, where to search by an index, in what order to join. In SQLite it is shown by EXPLAIN QUERY PLAN. Chapter 46 · The library and the bank

query planner

The part of a database that, for every query, goes through the ways of carrying it out (a full scan, different indexes, the order of joins), estimates their cost and picks the cheapest. Chapter 46 · The library and the bank

queue

A data structure where items are added at one end (the tail) and removed from the other (the head): first in, first out (FIFO). Chapter 15 · Stacks, queues and a calculator

quines

A program that prints its own source code without reading it from a file. Chapter 0 · What a program can do

quorum

A set of nodes whose agreement is enough for a decision. Usually any majority: any two majorities overlap, so two decisions can’t both pass without one of them learning of the other. Chapter 44 · The parliament of Paxos

race condition

A bug in which a program’s result depends on the order in which several threads performed their steps on shared data, and on how those steps were interleaved. Chapter 39 · Races

radix sort

A sort of numbers (or strings) by their digits: several passes of stable distribution into pockets, from the lowest digit to the highest. Time: the number of digits × (n + the base), without a single comparison. Chapter 20 · The sorting tournament

random-access memory

Random-access memory (RAM): memory in which any cell can be read or written by its address in a single access. It loses its contents without power. Chapter 31 · Memory and the clock

read past the end of a buffer

A buffer over-read: a program hands out more data than the buffer holds, taking in the neighboring memory. That is how Heartbleed worked: the server returned as many bytes as the client asked for, without checking how many it had sent. Chapter 61 · The training range

read-only memory

Read-only memory (ROM): its contents are fixed at manufacture and can only be read; it keeps them without power. Chapter 31 · Memory and the clock

real-time systems

A system in which a result must be ready by a set deadline: a late result counts as an error. Hard real time: lateness is never acceptable; soft real time: it is acceptable once in a while. Chapter 37 · Mission control

recurrence

An equation that expresses a function’s value through its values at smaller arguments, such as T(n) = 2T(n/2) + n. Chapter 21 · Divide and conquer

recursion

A technique in which a function solves a problem by calling itself on a problem of the same kind but of a smaller size. Chapter 9 · A problem inside a problem

recursive descent

A way of parsing in which every nonterminal of the grammar has a function: it looks at the next token, chooses a rule and calls the functions for its parts. The tree is built from the top down, and the nesting of parentheses becomes the depth of the recursion. Chapter 50 · The field linguist

reduction

A way to solve problem A with a solver for problem B: every input of A is translated into an input of B with the same answer. If A reduces to B and A is undecidable, then B is undecidable too. Chapter 56 · A conversation with the Oracle

redundancy

The predictable part of data, what need not be stored: the difference between the length of a record and the amount of information in it. Lossless compression removes redundancy. Chapter 47 · The packing contest

reference

A value that points to an object; in CPython, the object’s address in memory. A list stores references to its items, not the items themselves. Chapter 14 · How a list lives in memory

reference count

A way of freeing memory: every object stores the number of references to it; a new reference adds one, a vanished one subtracts one, and the object is freed as soon as the count drops to zero. This is how CPython works. Chapter 38 · The hotel of addresses

register

Several flip-flops sharing one clock signal and holding one number. In a processor, registers are the fastest memory: the ALU takes its operands from them and writes its result into them. Chapter 31 · Memory and the clock

register allocation

The compiler stage that decides which values to keep in processor registers and which in memory. Registers are few, so values that are needed at the same time must get different registers; the problem is often reduced to graph coloring. Chapter 52 · Closing the circle

regular

A language (a set of strings) accepted by some finite automaton. By Kleene’s theorem, these are the same languages that regular expressions describe. Chapter 54 · Automata and regular expressions

regular expressions

A formula describing a set of strings: symbols, “or” (|), repetition (*) and grouping; practical languages add classes such as [a-z], counted repeats {n,m}, anchors and much more. In Python, the re module. Chapter 54 · Automata and regular expressions

relaxation

Checking an edge u → v in a shortest-path search: if dist[u] + w(u, v) is less than dist[v], the estimate dist[v] is lowered to that sum. Chapter 24 · The navigator

relay

A switch worked by an electromagnet: current in a coil pulls an iron armature, which closes or opens the contacts of another circuit. Chapter 29 · Logic from switches

replica

A copy of the data on one of the servers of a distributed system. Copies are kept so that the data survives the failure of any machine; the hard part is keeping them identical. Chapter 44 · The parliament of Paxos

representation

A value written the way it is written in Python code: repr('a\nb') is the string 'a\\nb', quotes included. Chapter 7 · A conversation made of strings

reservoir sampling

A way to choose k random items from a stream of unknown length in a single pass while storing only k items: the i-th item replaces a random stored one with probability k/i. Chapter 26 · Let's flip a coin

residual network

For a network and a flow in it, the graph in which an edge u→v with the number r means that r more can be sent from u to v, either through free room on the edge u→v or by undoing part of the flow on the opposite edge v→u. Chapter 25 · Flows and matchings

resolver

A server (or program) that finds the address for a name: it asks the DNS root, then the servers of domains further and further down the tree, and remembers the answers for as long as they live. Chapter 43 · Anatomy of this page

response time

The time from a job’s arrival to the moment it first gets the processor: s − a. The main yardstick for interactive programs. Chapter 37 · Mission control

responsible disclosure

Responsible (coordinated) disclosure: a procedure in which whoever finds a vulnerability first tells the owner quietly and gives time to fix it (usually up to 90 days), and only then makes it public. It protects users while there is no patch. Chapter 61 · The training range

retransmission timeout

How long a sender waits for an acknowledgment before deciding that the packet or the acknowledgment was lost and sending the packet again. Chapter 42 · Inventing a protocol

return address

The address of the instruction to continue from after a function returns. The call instruction pushes it onto the stack; ret pops it and jumps there. Chapter 33 · An X-ray of Python

return value

The value a function hands back with return to the place it was called from; in an expression, the call is replaced by this value. Chapter 5 · Words of your own

reverse Polish notation

A way of writing expressions with the operator after its operands: 3 4 + instead of 3 + 4. It needs no brackets or precedence rules and is evaluated in a single pass with a stack. Chapter 15 · Stacks, queues and a calculator

ring buffer

A queue on an array of fixed length bent into a ring: the head and the tail move forward and wrap around to the start, modulo the length. Nothing shifts, and the memory never grows. Also called a circular buffer. Chapter 15 · Stacks, queues and a calculator

ripple-carry adder

A multi-bit adder made of a chain of full adders in which the carry out of each bit goes into the next; simple but slow, because a carry may have to run through every bit. Chapter 30 · The machine does arithmetic

rolling

A hash of a fixed-length window that takes O(1) to recompute when the window slides by one character: subtract the share of the departing character, multiply by the base, add the arriving one. The basis of the Rabin–Karp algorithm and of document fingerprints. Chapter 27 · A needle in a haystack

root

The topmost node of a tree, the only one without a parent. Every path and every search starts from it. Chapter 17 · A garden of search trees

roots

The places from which a garbage collector starts looking for live objects: global variables, local variables in the frames of the stack, registers. Whatever can’t be reached from them by references is garbage. Chapter 51 · The nesting doll

rotation

Rearranging three links in a search tree: a child of a node rises into its place and the node becomes its child, while the middle subtree passes from one to the other. The order of the keys is kept; the heights of the branches change by one. Chapter 17 · A garden of search trees

router

A device at the junction of several networks: it takes in a packet, reads the destination address in its IP header and decides from its routing table which way to send it. Chapter 41 · A day in the life of a packet

routing table

A router’s table of lines of the form “address prefix → where to send.” For each packet the line with the longest matching prefix is chosen. Chapter 41 · A day in the life of a packet

run-length encoding

Run-length encoding: a run of identical values in a row is replaced by a pair “how many times, which value.” It compresses pictures with large areas of one color well and does nothing for text. Chapter 47 · The packing contest

runtime library

Subroutines the compiler adds to every program to do what the processor’s instructions can’t: multiplication on a machine with no multiply instruction, output to the screen, memory allocation, garbage collection. Chapter 52 · Closing the circle

S-expression

The notation Lisp uses for both data and programs: either an atom (a number, a name) or a parenthesized list of other S-expressions. A Lisp program is made of S-expressions, so its tree is visible right in the text. Chapter 51 · The nesting doll

salt

A random secret value that a hash function depends on. It is chosen anew, for example at every start of the program, so that an adversary can’t prepare keys with equal hashes in advance. Chapter 16 · Hash tables: attack and defense

sandbox

A sandbox: a confined environment in which someone else’s code runs with no access to the rest of the system: the network, other files, extra rights. Crossing any boundary is stopped safely. Chapter 61 · The training range

satisfiability problem

The satisfiability problem: can the variables be given values that make a CNF formula true? The first problem proved NP-complete (Cook, 1971; Levin, 1973). 3-SAT is the same problem for clauses of three literals. Chapter 57 · Gödel’s letter

scheduler

The part of the operating system that decides which of the processes (or threads) that are ready to run gets a processor core next, and for how long. Chapter 37 · Mission control

schema

The description of a database: which tables it has, their columns and types, their keys, and how the tables refer to each other. Chapter 45 · The archivist

scope

The part of a program where a variable’s name means something: a function’s local names are visible only inside it. Chapter 5 · Words of your own

segmentation fault

Segmentation fault: the crash of a program that accessed memory it was never given, or accessed it in a forbidden way (a write to a read-only page). The MMU notices the violation, and the kernel sends the SIGSEGV signal. Chapter 38 · The hotel of addresses

selection sort

A sort: find the smallest item and put it first, then the smallest of the rest second, and so on. Always n(n − 1)/2 comparisons and at most n − 1 swaps. Chapter 20 · The sorting tournament

self-hosting

A compiler written in the language it compiles: a C compiler in C, a Go compiler in Go. Its first version has to be built with another compiler or run in an interpreter; this is called bootstrapping. Chapter 52 · Closing the circle

Semantics

The meaning of a correctly written program: what it does when it runs. Text that looks the same can have different semantics in different languages, and different text can have the same semantics. Chapter 49 · The museum of languages

semaphore

A counter with two indivisible operations: P (acquire) decreases it by one, waiting if it is zero; V (release) increases it and wakes a waiting thread. A semaphore of n lets at most n threads into a stretch of code at once. Chapter 39 · Races

sequence number

The number a sender writes into every packet so that the receiver can put the data in place, throw away duplicates and notice gaps. TCP numbers bytes rather than packets. Chapter 42 · Inventing a protocol

set

A collection of distinct values with no order and no repeats; checking whether x is in it is as fast as looking up a key in a dictionary. Chapter 8 · Dictionaries and the telegraph

set cover

The problem: given a set of elements and a collection of its subsets, choose as few subsets as possible that together contain all the elements. It is NP-hard; the greedy algorithm is off by a factor of at most about ln n. Chapter 58 · The salesman’s expedition

shell

The command interpreter (sh, bash, zsh): an ordinary program that reads commands, runs them with fork and exec, connects them with pipes and redirects their input and output. Chapter 36 · A tour of a living system

shell pipeline

A chain of programs connected by pipes: the standard output of each one is connected to the standard input of the next. In the shell it is written with a vertical bar: sort | uniq -c. Chapter 36 · A tour of a living system

shift

An operation that moves all the bits of a number one or more places to the left or right; a shift left by one place multiplies the number by 2, a shift right does integer division by 2. Chapter 30 · The machine does arithmetic

shingles

A run of k consecutive words (or characters) of a text. The set of shingles is a “fingerprint” of the text that ignores the order of its paragraphs; the shingles two texts share are the pieces they share. Chapter 27 · A needle in a haystack

shortest path

The path between two vertices of a graph with the fewest edges or, if the edges have lengths, the smallest total length. The number of edges on a shortest path is the distance between the vertices. Chapter 19 · Six handshakes

shunting-yard algorithm

Dijkstra’s algorithm (1961) for turning an infix expression into reverse Polish notation by keeping operators and brackets on a stack. Chapter 15 · Stacks, queues and a calculator

side-channel attack

A way to learn a secret not from what a program outputs but from by-products of its work: timing, power use, the state of the cache, sound. Chapter 35 · The pipeline and the fortune-teller

sifting

Restoring the heap property after one item has changed: the item swaps places with its parent (sifting up) or with the smaller of its children (sifting down) until it settles in place. Chapter 18 · Who is next

simple substitution cipher

A cipher in which each letter of the alphabet is always replaced by the same other letter, according to a secret table. The key is a permutation of the alphabet. Chapter 59 · The cipher bureau

simulated annealing

Local search that sometimes accepts a worse solution: a move that lengthens the solution by Δ is accepted with probability e^(−Δ/T), and the “temperature” T is gradually lowered. This lets the search climb out of local optima. Chapter 58 · The salesman’s expedition

slice

A piece of a list or string: a[start:stop:step]. The stop is not included; the result is a new list. Chapter 6 · Lists

sliding window

A sender keeps up to W unacknowledged packets on the way; the acknowledgment of the first of them moves the window forward and lets the next one go. That way the link doesn’t stand idle while acknowledgments travel. Chapter 42 · Inventing a protocol

slow password hashes

A hash function for storing passwords: salted and slow on purpose (many rounds or a lot of memory), so that running through a dictionary costs the attacker dearly. Examples: Argon2, scrypt, bcrypt, PBKDF2. Chapter 60 · A secret in plain sight

social engineering

Social engineering: gaining access by fooling a person rather than breaking the technology: a fake email, a call from “support,” an “urgent” request to give up a code. Rules and the habit of checking are the defense. Chapter 61 · The training range

socket

The point through which a program exchanges data over a network: the kernel hands it out as a file descriptor, and the program writes to it and reads from it. A socket has a machine address and a port number. Chapter 41 · A day in the life of a packet

solved

Solved game: one whose outcome with perfect play on both sides is known (a win for the first player, for the second, or a draw), and often the perfect strategy itself. Tic-tac-toe is a draw, checkers is a draw, Connect Four is a win for the first player. Chapter 62 · The bot tournament

sound

A property of a type system: if a program passes the check, no type errors will happen while it runs. The price of soundness is that the checker sometimes rejects correct programs. Chapter 53 · Null on trial

spanning tree

A tree made of a graph’s edges that reaches all of its vertices: it leads from any vertex to any other, and it has no cycles. Chapter 23 · Greed and electricity

special forms

An expression that is evaluated by its own rule instead of the general “evaluate all the arguments and call the function”: if, define, quote, lambda in Lisp; if, def, and, or in Python. Chapter 51 · The nesting doll

special methods

A method with a name of the form __name__ that Python calls by itself: __init__ when an object is created, __repr__ and __str__ when it is shown, __eq__ for ==, __add__ for +. Chapter 12 · The island of rabbits and foxes

speculative execution

Executing instructions before it is known whether they are needed: the processor follows the guessed path, keeps the results as a draft and cancels them if the guess turns out wrong. Chapter 35 · The pipeline and the fortune-teller

SQL injection

SQL injection: an attack in which user data pasted into the text of a SQL query is parsed by the database as part of the command. It lets you bypass checks and read or erase other people’s data. The defense is query parameters (?), not gluing strings. Chapter 61 · The training range

stable

A sort that doesn’t change the relative order of items with equal keys. Insertion, bubble, merge sort and Python’s sorted are stable; selection and heapsort are not. Chapter 20 · The sorting tournament

stable

A matching with no blocking pairs: no two people will want to leave their partners for each other. Chapter 25 · Flows and matchings

stack

A data structure where items are added and removed at one end, the top: last in, first out (LIFO). The operations push, pop and peek cost O(1). Chapter 15 · Stacks, queues and a calculator

stack frame

The part of the stack that belongs to one function call: the return address, saved registers and local variables. It appears when the function is called and is released when it returns. Chapter 33 · An X-ray of Python

standard input

Three file descriptors every process has open from birth: 0 is standard input (stdin), 1 is standard output (stdout), 2 is standard error (stderr). A program reads and writes them without knowing what they are connected to. Chapter 36 · A tour of a living system

starvation

A situation where an item with a low priority waits for service indefinitely because items with a higher priority keep turning up. Chapter 18 · Who is next

state machine replication

A way to build a reliable service from unreliable machines: every replica carries out the same commands in the same order, recorded in a shared log, and so arrives at the same state. Chapter 44 · The parliament of Paxos

static typing

Checking types before the program runs, from its text: every variable and function has a known type, and a program with mismatched types won’t build. C, Java, Haskell, Rust. Chapter 49 · The museum of languages

statistics

Facts about the data that the planner uses to estimate the cost of the ways to carry out a query: how many rows a table has, how many rows on average share one value of an index’s column. In SQLite they are collected by ANALYZE into the table sqlite_stat1. Chapter 46 · The library and the bank

status code

The three-digit number in the first line of an HTTP response. The first digit is the class: 2 is success, 3 means go elsewhere, 4 is the client’s error, 5 the server’s. 200 OK, 301 moved, 404 not found, 500 the server fell over. Chapter 43 · Anatomy of this page

stemming

Reducing a word to its stem by cutting off endings according to rules: “sorting” → “sort”. Fast and needs no dictionary, but it trips over irregular forms and over different words that happen to look alike. Chapter 48 · A search engine for our textbooks

stored-program architecture

A computer design in which the program is kept in the same memory as the data and consists of the same kind of numbers. It can be loaded, read and changed like data. Chapter 32 · You are the processor

string

A text value: a sequence of characters in quotes, such as "Hello". Chapter 1 · First program, first bug

subclasses

A class that inherits from another: in class Fox(Animal), Fox is a subclass of Animal. An instance of a subclass also counts as an instance of the parent, so isinstance(fox, Animal) is true. Chapter 12 · The island of rabbits and foxes

subsequence

A sequence obtained from a given one by striking out elements: the rest keep their order but need not stand together. Unlike a substring. Chapter 22 · Remember instead of recomputing

subset construction

Building a DFA from an NFA (Rabin and Scott, 1959): each DFA state is a set of states the NFA could be in, and the transitions come from a breadth-first search starting at the start set. In the worst case there are 2 to the power n states. Chapter 54 · Automata and regular expressions

substring

A run of consecutive characters inside a string: “Kamchatsky” is a substring of “Petropavlovsk-Kamchatsky.” Chapter 7 · A conversation made of strings

substring search

The problem of finding every place where a short string, the pattern, occurs in a long string, the text. The naive solution lays the pattern against every position and spends up to n·m comparisons; KMP and Rabin–Karp manage in linear time. Chapter 27 · A needle in a haystack

suffix array

The starting positions of all the suffixes of a string, ordered alphabetically by suffix. It finds any pattern by binary search in O(m log n) and shows repeats as the common beginnings of neighbors. Chapter 27 · A needle in a haystack

superposition

A state of a quantum system in which several basis states have nonzero amplitudes at once, for example (|0⟩ + |1⟩)/√2. Chapter 64 · The qubit lab

supply-chain attack

A supply-chain attack: planting malicious code in something a system depends on (a library, a package, a build tool), from where it spreads into everything built or linked with it. Chapter 61 · The training range

swap space

A place on disk where the operating system puts pages that didn’t fit in physical memory, to bring them back on the next access. Swapping is that exchange itself. Chapter 38 · The hotel of addresses

symmetric

A cipher in which the sender and the receiver use the same secret key. All the ciphers from Caesar to AES are symmetric. Chapter 59 · The cipher bureau

Syntax

The rules by which symbols make up valid programs of a language: which words and signs may stand where. A syntax error is caught before the program runs: in Python it is a SyntaxError. Chapter 49 · The museum of languages

system call

A program’s request to the operating system kernel: open a file, read bytes, create a process, allocate memory. It is made with a special processor instruction that switches the processor into kernel mode. Chapter 36 · A tour of a living system

tables

The basic unit of storage in a relational database: a set of rows with the same named columns. Each column has its own type. The rows of a table have no defined order. Chapter 45 · The archivist

tail call

A function call that is the last action of another function: its result immediately becomes that function’s result. After such a call the caller’s frame is no longer needed, so an interpreter or a compiler can avoid keeping it. Chapter 51 · The nesting doll

TCP

Transmission Control Protocol: the internet’s transport protocol that gives a reliable stream of bytes on top of unreliable IP, with numbers, acknowledgments, resends, a window, flow control and congestion control. The web, mail and ssh run on it. Chapter 42 · Inventing a protocol

terms

In Raft, a numbered stretch of time that begins with an election. A term has at most one chair; a node that sees a higher term number accepts it at once and becomes a follower. Chapter 44 · The parliament of Paxos

test set

Examples that are not shown to the model during training and on which its accuracy is checked once, at the end. Only it shows how the model will do on new data. Chapter 63 · The machine learns

TF-IDF

The weight of a word in a document: its frequency in the document (tf) times log(N / df), where df is how many of the N documents contain the word. Words frequent in the document and rare in the collection weigh the most. Chapter 48 · A search engine for our textbooks

thrashing

The state in which processes don’t have enough memory for their working sets and the system spends nearly all its time moving pages between memory and disk, doing almost no useful work. Chapter 38 · The hotel of addresses

thread

A line of execution inside a process, with its own program counter, registers and call stack; memory, global variables and open files are shared with all the other threads of the same process. Chapter 39 · Races

threat model

A threat model: an explicit list of what a system protects (data, money, availability), against which adversary (a casual visitor, a neighbor on the server, a state), and at what cost. Defenses are built for a specific threat model. Chapter 61 · The training range

three-valued logic

Logic with three values: true, false and unknown. In SQL any comparison with NULL gives “unknown,” and WHERE lets through only the rows that are true. Chapter 45 · The archivist

three-way handshake

The start of a TCP connection: the client sends SYN, the server answers SYN-ACK, the client sends ACK. The two sides agree on their starting numbers and make sure the connection works in both directions. Chapter 42 · Inventing a protocol

time slice

The stretch of time for which the scheduler gives a core to a process; when it runs out, a timer interrupt hands control back to the scheduler. Chapter 37 · Mission control

time-sharing

A way of running a computer in which the processor switches quickly among the programs of many users, giving each short slices of time, so that every user sees a machine that answers only them. Chapter 37 · Mission control

timing diagram

A picture of a digital circuit’s signals over time: each wire is a track, the high level is 1, the low level is 0, and all the tracks share one time axis. Chapter 31 · Memory and the clock

TLB

Translation lookaside buffer: a small, fast cache inside the processor that holds recent “page → frame” translations. If a translation is there, the page table needn’t be read. Chapter 38 · The hotel of addresses

tokens

An indivisible “word” of a program, as the parser sees it: a number, a name, an operator, a parenthesis, a string. A token has a kind (NUM, NAME, OP…) and a value. Chapter 50 · The field linguist

topological sort

An arrangement of the vertices of a directed graph in a row such that every arrow points from left to right: everything a vertex depends on comes before it. It exists if and only if the graph has no cycles. Chapter 19 · Six handshakes

traceback

The error report Python prints when a program crashes: where it stopped and why. Chapter 1 · First program, first bug

training set

Examples with right answers, on which a model’s weights are fitted. Chapter 63 · The machine learns

transaction

A group of operations on a database that is carried out as one whole: either all its changes take effect (COMMIT) or none do (ROLLBACK). Other users of the database don’t see its intermediate states. Chapter 46 · The library and the bank

transistor

A semiconductor switch with no moving parts: the voltage on its control terminal (the gate) opens or closes a path for current between its two other terminals. Chapter 29 · Logic from switches

traveling salesman problem

The traveling salesman problem: find the shortest closed route that passes through every city exactly once. Its version “is there a route of length at most L?” is NP-complete. Chapter 58 · The salesman’s expedition

traversals

A way of visiting every node of a tree once. Pre-order: the node, then its left and right subtrees; in-order: left, node, right; post-order: left, right, node; breadth-first: level by level. Chapter 17 · A garden of search trees

tree

A structure of nodes in which every node except one, the root, has a single parent, while it may have any number of children; no path goes round in a circle. A binary tree is a tree in which a node has at most two children: a left one and a right one. Chapter 17 · A garden of search trees

trie

A tree for a set of strings: every arrow is labeled with a letter, the path from the root to a node spells the beginning of a string, and strings with a common beginning share a path. It finds a string, or every string with a given beginning, in time proportional to the length of the query. Chapter 27 · A needle in a haystack

truth table

A table that gives the value of a logical expression for every combination of True and False in its variables. Chapter 3 · Forks in the road

TTL

Time To Live: a field of the IP header that every router decreases by one; when it reaches zero, the packet is thrown away. It protects the network from packets that go around in circles. Chapter 41 · A day in the life of a packet

tuple

An immutable sequence of values in parentheses: (time, latitude, longitude). Handy for records with a fixed set of fields. Chapter 6 · Lists

Turing complete

The property of a language, machine or system of rules that can run any Turing machine, and so, by the Church–Turing thesis, any computation, given enough memory and time. Python, C, Brainfuck, the λ-calculus and the Game of Life are Turing complete; finite automata and regular expressions are not. Chapter 55 · The Turing machine

Turing machine

An imaginary computing machine: an infinite tape of cells holding symbols, a head over one cell, and a finite table of rules “in state q, reading symbol a: write b, move left or right, go to state r.” When no rule fits, the machine halts. Chapter 55 · The Turing machine

turnaround time

The time from a job’s arrival to its completion: f − a. Chapter 37 · Mission control

two-bit saturating counter

The two-bit counter of a branch predictor: it runs from 0 to 3, a taken branch adds one, a branch not taken subtracts one, and the counter never goes past either end. 2 and 3 predict “taken,” 0 and 1 “not taken”: changing the prediction takes two misses in a row. Chapter 35 · The pipeline and the fortune-teller

two’s complement

A way to store signed integers in n bits: a negative number −x is written as 2ⁿ − x. The top bit is the sign, there is only one zero, and addition and subtraction use the same circuit as for unsigned numbers. Chapter 28 · Everything is bits

type checker

A program that reads the text of another program and, without running it, checks that no operation will receive a value of the wrong type. It is built into the compilers of C, Java and Rust; for Python it is a separate program, such as mypy. Chapter 53 · Null on trial

type inference

Finding the types of expressions from the way they are used, without annotations. The Hindley–Milner algorithm finds the most general type by solving a system of equations on types with unification. Chapter 53 · Null on trial

type narrowing

Refining the type of a variable after a check in the program itself: after if x is None: return, the type checker treats a variable of type str | None as a str. isinstance, comparisons and match narrow types the same way. Chapter 53 · Null on trial

type system

The rules by which every expression in a program is given a type and the types are checked to fit together. The type system decides which errors a language promises to find before the program runs. Chapter 53 · Null on trial

types

The kind of a value, which decides what you can do with it: int is a whole number, float a fractional one, str a string, bool true or false. The function type() tells you the type. Chapter 2 · Names and values

UDP

User Datagram Protocol: a transport protocol without guarantees, with separate datagrams carrying port numbers and a checksum and no connection, acknowledgments or resends. DNS, video calls and games run on it. Chapter 42 · Inventing a protocol

undefined behavior

An operation whose result the language standard makes no promises about (in C, writing past the end of an array or overflowing a signed integer). The program may crash, quietly corrupt data or carry on as if nothing had happened. Chapter 33 · An X-ray of Python

Unicode

A single table of the characters of all the world’s scripts: every character has its own number, a code point from U+0000 to U+10FFFF. How these numbers lie in bytes is set by the encodings UTF-8, UTF-16 and UTF-32. Chapter 28 · Everything is bits

unification

Solving a system of equations on types (or on expressions with unknowns): finding a substitution after which the two sides of every equation become the same. The basis of Hindley–Milner type inference and of the Prolog language. Chapter 53 · Null on trial

unit test

A small function that calls the code under test on a known input and compares the result with the expected one; if they differ, the test fails. Chapter 11 · The inquiry report

universal machine

A Turing machine that receives on its tape the description of any other machine and that machine’s input, and runs that machine. Turing described it in 1936; it is the idea of a program stored together with its data. Chapter 55 · The Turing machine

URL

Uniform Resource Locator: the address of a document on the network. A scheme (the protocol), a server name, an optional port, a path on the server, optional parameters after ? and a fragment after #. Chapter 43 · Anatomy of this page

user mode

The processor mode in which ordinary programs run: instructions that control the hardware are forbidden, and only the program’s own memory is accessible. For everything else the program asks the kernel. Chapter 36 · A tour of a living system

UTF-8

An encoding of Unicode in which a character takes 1 to 4 bytes: ASCII one, Cyrillic and accented Latin letters two, most Chinese characters three, emoji four. The first bits of a byte tell how many bytes the character has. Almost everything on the internet is written in it. Chapter 28 · Everything is bits

variable

A name tied to a value. In Python a variable is a label on an object: the same name can be moved to another object. Chapter 2 · Names and values

Vector clocks

Logical clocks in which every node keeps a vector of counters, one for each node of the system. a → b if and only if a’s vector is no greater than b’s in every position and differs from it. Chapter 44 · The parliament of Paxos

vector instruction

Single instruction, multiple data: a processor instruction that performs the same operation on several numbers at once, lying side by side in a wide register (128, 256 or 512 bits). Chapter 35 · The pipeline and the fortune-teller

vectorization

Rewriting a computation so that it works on whole arrays at once (in numpy, with array operations instead of a Python loop); the work is then done by a loop in C, often with the processor’s vector instructions. Chapter 35 · The pipeline and the fortune-teller

vertices

An object in a graph: a person, a station, a cell of a maze. Vertices are joined by edges. Chapter 19 · Six handshakes

Vigenère cipher

A cipher in which the letters are shifted in turn by the numbers of the letters of a keyword repeated over and over: several Caesar ciphers interleaved. Described by Bellaso in 1553, named after Vigenère. Chapter 59 · The cipher bureau

virtual addresses

An address as a program uses it. The processor translates it, by the page table, into a physical address, the number of an actual cell in the memory chips; in different processes the same virtual address usually leads to different cells. Chapter 38 · The hotel of addresses

virtual machine

A program that plays the part of a processor: it has its own instruction set, its own program counter and its own memory, and a hardware processor runs it. Inside CPython is a stack-based virtual machine. Chapter 33 · An X-ray of Python

virtual memory

The way the processor and the operating system give every process an address space of its own: virtual addresses are translated into physical ones by the page table, and pages that didn’t fit in memory are kept on disk. Chapter 38 · The hotel of addresses

vulnerability

A vulnerability: a flaw or feature of a system that lets someone achieve what its creator didn’t intend: read other people’s data, gain extra rights, crash the server. Most often it is an ordinary bug in the code, not a weakness in the mathematics. Chapter 61 · The training range

waiting time

How long a job stood in the ready queue: its turnaround time minus the time it spent running, f − a − b. Chapter 37 · Mission control

watchdog timer

A timer that expects a regular “I’m alive” signal from a program and, if the signal doesn’t come in time, restarts the program or the whole computer. Chapter 39 · Races

weak typing

A language’s habit of quietly converting values of the wrong type instead of raising an error: in JavaScript "5" * 3 gives 15, and in C a fraction passed where an integer is expected is cut down to a whole number. The opposite is strong typing; the border between them is blurry. Chapter 49 · The museum of languages

weighted

A graph in which every edge carries a number, its weight: a length, a time, a price. The length of a path in a weighted graph is the sum of the weights of its edges. Chapter 24 · The navigator

weights

The adjustable numbers of a machine learning model; training fits them. A line has two weights; networks have anything from thousands to hundreds of billions. Chapter 63 · The machine learns

winnowing

A way to choose a document’s fingerprints: in every window of w consecutive shingle hashes, keep the smallest. Any shared piece of w + k − 1 words is guaranteed to give a shared fingerprint. MOSS is built on it. Chapter 27 · A needle in a haystack

witness

A number a that quickly shows that n is composite (in the Fermat or the Miller–Rabin test). Chapter 26 · Let's flip a coin

working set

The pages a process has accessed recently. If the working sets of all processes fit in memory, there are few misses; if not, thrashing begins. Chapter 38 · The hotel of addresses

worst case

The longest running time of an algorithm over all inputs of size n. A worst-case bound is a guarantee: the algorithm may be no faster, but it will never be slower. Chapter 13 · What a program costs

write skew

An anomaly: two transactions read the same data, check a shared rule against it and change different records; each one alone keeps the rule, but together they break it. Chapter 46 · The library and the bank

write-ahead log

The write-ahead log (WAL): the database first appends changes to the end of a separate log file, and only later, at a checkpoint, copies them into the database file itself. A transaction counts as committed once its “done” record has reached the log. Chapter 46 · The library and the bank

Zipf’s law

An observation about texts: the word in place r by frequency occurs about r times less often than the most frequent one. Chapter 8 · Dictionaries and the telegraph