Most terms are shown by a figure in the book. Follow the link to see it in place, or open the widget to try it.
The tree a parser builds from the tokens, which makes the program's grouping explicit. In the book's arithmetic language each inner node is an addition and each leaf a number or a variable; for (a + b) + c the root is the outer addition, and both the interpreter and the compiler walk this same tree.
Chapter 7, Figure 7.2 See also Parser; Interpreter; Compiler; Tree node; Root, child and leaf; Tree walk
Two views of one part: what it does, and how it is built. The chapter draws NAND twice, as the gate symbol, the abstraction it reuses from there on, and as the CMOS implementation, the transistors that actually do the work, set side by side in one view.
Chapter 1, Figure 1.5 See also Gate symbol; Logic gate; Model
The marks on a real page-table entry that say what a program may do with that page. A forbidden access is one of the things a real page fault can report. The book's tables carry none: each entry is only a frame number, so they show mappings, not an enforced security boundary.
Chapter 9.c See also Page table; Page mapping; Page fault; Protection
The single working register of the book's CPU, through which all arithmetic flows. Every ADD reads one operand from memory and adds it to what the accumulator holds; it keeps eight bits, so adding 1 to 255 leaves 0.
Chapter 5 Try it See also Program counter; ALU; Accumulator machine; ADD; LOAD; STORE
A CPU in which all arithmetic flows through a single working register, the accumulator. The book's machine is one: every ADD reads one operand from memory and adds it to whatever the accumulator currently holds. It has no general-purpose register file.
Chapter 5 Try it See also Accumulator; Register file; Instruction set; CPU
An acknowledgement that goes missing on its way back, so the sender cannot tell that its segment arrived. The book's model leaves this out: its ACKs are immediate and reliable, so an arrived segment is never resent. TCP's ACKs can be lost, and a TCP sender may therefore retransmit data that already arrived.
Chapter 12 See also Acknowledgement (ACK); TCP; Retransmission
The receiver's report to the sender of which segments have arrived. The book's receiver names every segment it holds, a selective acknowledgement: after segment 1 is lost it answers ack 0, 2. TCP uses a cumulative acknowledgement, a single number meaning everything up to here has arrived, with optional selective information.
Chapter 12, Figure 12.3 See also Retransmission; Sequence number; TCP; Cumulative acknowledgement; Selective acknowledgement; ACK loss
The instruction that adds a memory word to the accumulator, opcode 3. The ALU adds the word at the operand's address to the accumulator, which keeps the low eight bits of the sum. In the example program ADD 14 and ADD 15 take the accumulator from 10 to 30 and then to 42.
Chapter 5 Try it See also Accumulator; ALU; Wraparound; LOAD
One full adder in a ripple-carry chain, handling a single bit position. Each stage's carry-out feeds the next stage's carry-in: the lowest stage receives a carry-in of 0, and the highest stage's carry-out becomes the extra top bit of the result. The chapter's figure shows a four-stage chain.
Chapter 3, Figure 3.4 Try it See also Full adder; Ripple-carry adder; Carry chain; Bit position
Giving every instruction and data word its place in memory, the job of an assembler's first pass. The book's assembler hands out addresses in sequence and records each label at the address of the next word, so a label alone on a line names the instruction below it. The programmer never counts an address.
Chapter 6, Figure 6.2 Try it See also Two-pass assembler; Symbol table; Assembly label
Two programs landing on the same memory cell because both use the same address. If all programs used real addresses, two that both wanted address 3 would collide, and one could overwrite the other's data. With their own page tables, the book's two programs both write virtual address 3 and land at physical 83 and 131.
Chapter 9.c, Figure 9.c.3 Try it See also Virtual memory; Memory isolation; Disjoint frames
The part of a RAM that turns address bits into one-hot select lines: a 2-to-4 decoder raises exactly one of four lines, choosing a single register. On a write, only that register's load line is asserted.
Chapter 4, Figure 4.6 Try it See also RAM; One-hot; Memory address; Instruction decoder
A stretch of consecutive addresses, given by where it starts and how long it is. The book's Heap tracks address ranges rather than storing the bytes in them: the allocator decides which ranges are free, and in a real process a page table decides where they land in physical memory.
Chapter 9.b, Figure 9.b.2 See also Free run; Live block; Memory allocator
Finding the link address that goes with a neighbour's network address, so that a frame can be addressed for the local hop. The chapter's run resolves B to 02:00:00:0b and C to 02:00:00:0c, answers a repeat from the cache, and fails for Z, an address no machine on the link owns.
Chapter 10.b, Figure 10.b.2 Try it See also ARP; ARP cache; Link address; Broadcast; Stale mapping
The full set of addresses a machine can name. A 4-bit operand can address 16 memory words directly, so the book's CPU has a 16-word address space, addresses 0 to 15. The example program fits five instructions, a result slot and three data cells in it with room to spare.
Chapter 5, Figure 5.5 Try it See also Memory address; Memory cell; Memory image; Opcode and operand
A fixed list of the memory addresses a program reads, in order, used to test a cache without running the program. The book feeds its cache three: SCAN, addresses 0 to 63 once; LOOP, 0 to 15 four times; and THRASH, 0, 32, 64 and 96 eight times. Each run starts with an empty cache.
Chapter 5.c See also Cache hit and miss; Locality; Thrashing
Turning the address a program uses into the address of a real memory cell, on every access. The address splits into a page number and an offset; the page table swaps the page for a frame and the offset passes through unchanged. In the book, program A's virtual address 3 becomes 5 × 16 + 3 = 83.
Chapter 9.c, Figure 9.c.2 Try it See also Virtual address; Physical address; Page table; Page number and offset; Page size
A frame that names the link address of the interface meant to receive it, needed on a shared local link where several interfaces hear every frame. The book's model writes the addressed result as a (mac, payload) pair; it does not extend or transmit the encoded frames of the framing chapter.
Chapter 10.b See also Link-layer frame; Link address; MAC address; Payload
The customary names for the two ends of a cryptographic exchange. In the book Alice keeps private exponent 6 and sends the public value 15625, Bob keeps 15 and sends 452807067, and each derives the same secret, 1893334806, from the other's public value.
Chapter 13.a, Figure 13.a.2 Try it See also Private exponent; Public value; Endpoint; Intermediary
What happens when no single free run is large enough for a request: the book's malloc raises a MemoryError and returns no address. Total free space is not what counts. Without coalescing, two small runs side by side would refuse a request for their combined size even though the room exists.
Chapter 9.b Try it See also Heap fragmentation; Free run; Coalescing
A filesystem's rule for deciding which blocks hold a file and how to find them again. The book builds one, linked allocation, in which a table records for each block which block holds the next piece; the chapter notes that filesystems can also use indexed blocks or runs of adjacent blocks.
Chapter 9.d See also Linked allocation; Filesystem; Indexed blocks; Contiguous blocks
The arithmetic-logic unit. It computes several candidate results, one per operation, and a multiplexer picks one by a control signal called the opcode; the book's minimal ALU offers add, bitwise AND, OR and XOR.
Chapter 3 See also Multiplexer; Accumulator; ALU opcode; ADD; Bitwise operation; Four-to-one multiplexer
The control signal that tells an ALU which of its candidate results to output. The book's minimal ALU takes a two-bit opcode: 00 selects add, 01 bitwise AND, 10 bitwise OR and 11 bitwise XOR.
Chapter 3 See also ALU; Opcode and operand; Four-to-one multiplexer; Select line; Power of two
Two ways to treat a wire's voltage. Analog takes the continuous value itself; digital recognises only two bands and calls them 0 and 1. Real circuits are analog underneath: during a transition both transistors of a CMOS pair can briefly conduct. The book's binary model leaves such analog effects out.
Chapter 1 See also LOW and HIGH; Voltage; Noise; Model; Floating input
The three gates behind the operations of Boolean algebra. AND is 1 only when both inputs are 1, OR is 0 only when both inputs are 0, and NOT flips its input; all three can be built from NAND alone.
Chapter 2, Figure 2.3 Try it See also NAND; Boolean algebra; Conjunction, disjunction and complement; Inverter; Logic gate; Bitwise operation
The Address Resolution Protocol, a bridge that maps a next-hop network address to a local link address. It asks everyone on the link who has B?, and only the machine that owns that network address answers, with its MAC address. For a distant destination, that MAC address belongs to the next router, not to the final recipient.
Chapter 10.b, Figure 10.b.2 Try it See also ARP cache; Broadcast; MAC address; Address resolution; Ethernet; Stale mapping
The asker's memory of earlier ARP answers, from network address to MAC address. The second time B is needed, the cache answers and the wire stays quiet. The book's inventory never changes, so its cache never expires; on a real network a cached answer can go stale and must be revalidated or discarded.
Chapter 10.b, Figure 10.b.3 Try it See also ARP; Address resolution; Stale mapping
A program that translates readable assembly text into the words a CPU executes, assigning every address so no one counts them by hand. The book's first piece of software turns its sum program into ten 8-bit words, and the CPU runs them to the same 42 as the hand-encoded version.
Chapter 6, Figure 6.3 Try it See also Assembly language; Symbol table; Machine code; Two-pass assembler; Linker; Hand encoding
A name written before a colon that stands for the address its line will occupy. Code refers to the name, never the number: start: lands at address 5, so JUMP start is encoded with operand 5, and moving the data cells would change that operand without changing the source.
Chapter 6, Figure 6.2 See also Symbol table; Assembly language; Address assignment; Operand resolution; Local address; Named memory
Plain text with one instruction per line: an optional label:, then a mnemonic such as LOAD with an operand, or the directive DATA, which places a literal value in memory. An operand is a number or a label's name, and anything after a semicolon is a comment.
Chapter 6, Figure 6.3 Try it See also Mnemonic; Assembly label; Assembler; Comment; Directive; Source code
To drive a line to a chosen value, most often to raise a control line so that something happens. To write to the chapter's RAM you assert the data and the address and raise the write line. Later, the control unit of the CPU reads an opcode and asserts the right signals.
Chapter 4 See also LOW and HIGH; Write line; Load line; Control unit; Control signal
The statement name = expr ;: evaluate the expression, then bind the result to the name. A name can be assigned again, which is what lets a program build a result step by step. In the book's loop, product = product + a; reads the old value of product and stores a new one.
Chapter 8, Figure 8.2 Try it See also Statement; Mutable state; Variable environment; Binding; Variable
The property of an operation whose result does not depend on how its operands are grouped. Addition associates, even when every sum wraps at 256, so a tree built only from additions is just the sum of its leaves in order. The book's compiler relies on this to flatten (a + b) + c.
Chapter 7 Try it See also Flattening; Grouping; Wraparound; Compiler; Precedence
Able to change at any time, not on a shared beat. The bare SR latch is asynchronous: it can be set and reset at any moment, so signals in a system built from dozens of such latches can ripple through unpredictably. The clock is the chapter's answer: update only now, on command.
Chapter 4 See also SR latch; Clock; Gated D latch
The average cost of one memory access through a cache: the hit time, paid on every access, plus the miss penalty on the fraction that miss. With a miss penalty a hundred times the hit time, even a few percent of misses decide the average.
Chapter 5.c Try it See also Hit rate; Cache hit and miss; Hit time; Miss penalty
How much data a memory system can deliver in a given time. The chapter says it comes from moving many bits in parallel: wide buses, bursts, multiple banks and multiple channels all let a memory deliver more than one bit or word per internal operation.
Chapter 4 See also Bus; Main memory; Memory hierarchy
The address where a module's first word lands once the linker has placed it. An exported label's final address is its module's base address plus where it sat inside that module. The book's data module follows the five words of main, so value, at 0 inside its module, lands at address 5.
Chapter 6.a, Figure 6.a.2 Try it See also Local address; Memory layout; Relocation
The two public numbers both sides of a Diffie-Hellman exchange agree on first: a base g, which each side raises to its private exponent, and a prime modulus p, by which every result is reduced. The book uses g = 5 and p = 2147483647, held in its code as _BASE and _PRIME.
Chapter 13.a, Figure 13.a.2 Try it See also Modular arithmetic; Public value; Diffie-Hellman key exchange; Modular exponentiation
A placement policy that takes the smallest free run still large enough for the request, rather than the first one found. The chapter names it among the policies real allocators use in place of first fit, to trade speed against how much the heap fragments; the book's Heap does not build it.
Chapter 9.b See also First fit; Placement policy; Heap fragmentation; Size class
The service the network gives: it carries what it can and apologises for nothing. Each hop along a path can drop a packet when a buffer fills, deliver packets out of order when two take different routes, or even duplicate one, so a path found by routing is only a promise to try.
Chapter 12 See also Transport layer; Duplicate segment; Lossy channel; Packet loss; Reliable delivery
Division as a loop over the dividend's bits, most significant first. Each step shifts the running remainder left and brings down the next bit; if the remainder is at least the divisor, the divisor is subtracted and the quotient bit is 1, otherwise 0.
Chapter 3.a, Figure 3.a.2 See also Two's complement; Dividend and divisor; Quotient and remainder; Running remainder; Bring down; CRC
A number written in bits, whose places are worth the powers of two, 1, 2, 4, 8 and so on from the right, instead of decimal's 1, 10, 100. A subscript 2 marks one: 11012 = 8 + 4 + 1 = 13, and 102 is 2.
Chapter 3 See also Bit; Least and most significant bit; Decimal; Power of two; Weight (of a place)
The tie between one name and its current value. An environment is a set of bindings; an assignment evaluates its expression and binds the result to a name, replacing any earlier binding. In the book's loop product is bound to 0 and then rebound on every pass, until it holds 42.
Chapter 8 Try it See also Variable; Variable environment; Assignment; Dictionary; Program input
A single value that is only ever 0 or 1, the value one wire carries as LOW or HIGH. Several bits together can hold a larger number: the four bits of 11012 hold 13.
Chapter 3 See also Binary numeral; LOW and HIGH; Boolean variable; Memory word; Signal; Byte
A single bit that arrives as the opposite of what was sent, because noise or a misread voltage changed it on the wire. The chapter's run flips one bit of a frame on purpose: that frame's CRC no longer matches, and the receiver drops it while keeping the good one.
Chapter 10 See also Error detection; CRC; Dropped frame; Checksum
How the book's Python circuits hold a number: a list of bits starting with bit 0, so that addition can follow the carry from low places to high ones. to_bits(13, 4) produces [1, 0, 1, 1], the reverse of the written 11012, and from_bits converts that list back to 13.
Chapter 3 See also Bit position; Least and most significant bit
The agreed order in which the bits of a byte cross a link. The book's sender clocks out the most significant bit first, so the letter A leaves as 01000001, and the receiver shifts each bit it reads into the byte it is building in that same order. Both ends must agree on it.
Chapter 10.a, Figure 10.a.2 Try it See also Least and most significant bit; Bit-banging; Byte
The numbered place of one bit in a binary number, counted from bit 0 at the least significant end. A single full adder handles one bit position; the four-bit adder in the chapter's figure runs from bit 0 to bit 3, one full adder each.
Chapter 3, Figure 3.4 Try it See also Least and most significant bit; Weight (of a place); Adder stage; Bit list; Bit width; Bitwise operation
How many bits a number or a circuit has. Adding two n-bit numbers takes a chain of n full adders, and the chapter's adder is four bits wide. Its result is one bit wider than its inputs, because the final carry-out becomes an extra top bit.
Chapter 3, Figure 3.4 Try it See also Bit position; Overflow; Ripple-carry adder; Fixed width
Sending bits by driving a clock line and a data line by hand, with no networking hardware, the same basic pattern a processor can use to talk to a chip beside it. Eight clock pulses, most significant bit first, carry a byte: the letter A goes out as 01000001. Real protocols such as SPI and JTAG have this shape.
Chapter 10.a, Figure 10.a.2 Try it See also Clock line; Sampling; Clock pulse; Data line; JTAG; SPI
The configuration loaded into an FPGA. It sets both what each block's table holds and which wires reach which inputs, so a different bitstream turns the same fabric into a different circuit.
Chapter 5.d, Figure 5.d.5 Try it See also FPGA; Lookup table; Configuration bit; Fabric; Reconfiguration; Configurable interconnect
An operation applied to two numbers one bit position at a time, each result bit depending only on the two input bits in that position. Three of the book's four ALU operations are bitwise: on a = 12 and b = 10, AND gives 8, OR gives 14 and XOR gives 6.
Chapter 3 See also ALU; AND, OR and NOT; XOR; Bit position
The empty line that separates a message's head from its body. It marks where the head ends, but it cannot mark where the body ends, because the body is raw bytes and may contain a blank line of its own. The book's parser raises an error for a message without this separator.
Chapter 13, Figure 13.2 See also Message head; Message body; Content-Length; Message framing
The operand an assembler leaves unfilled when an instruction names a label its module does not define. It records the position as an import, and the linker fills the blank later. The book's figures write it as LOAD ?; once value lands at address 5 the instruction becomes LOAD 5.
Chapter 6.a, Figure 6.a.3 Try it See also Imports and exports; Relocation; Opcode and operand; Symbol resolution
The fixed number of bytes one disk block holds. A file is cut into pieces of this size, and only the last may be shorter. The book's blocks hold four bytes, so the 13 bytes of long need four blocks: HELL, O, F, ILES and a final !.
Chapter 9.d, Figure 9.d.2 Try it See also Disk block; File; Chain of blocks
The doped regions of a transistor's silicon. In the chapter's n-channel device the body is p-type, and set into it are two n-type wells, the source and the drain, marked n+ in the figure. With the gate LOW nothing connects the wells; a HIGH gate bridges them with a channel.
Chapter 1, Figure 1.2 Try it See also Source, drain and gate; n-type and p-type; Channel
The algebra whose variables take only the values 0 and 1, with three operations that match the gates: AND written a · b, OR written a + b (a Boolean sum, not ordinary addition), and NOT written a.
Chapter 2, Figure 2.2 See also Truth table; De Morgan's laws; AND, OR and NOT; Boolean function; Boolean identity; Boolean notation
A rule that turns input bits into one output bit; a truth table lists one and a gate network computes one. NOT and AND, together with NAND, span the full set of Boolean functions, which is why each new gate in the chapter is only a short composition of NAND calls.
Chapter 2 Try it See also Truth table; Boolean algebra; Universal gate; Boolean variable
An equation between Boolean expressions that holds for every value of its variables. The chapter lists a handful worth memorising, among them a + 0 = a, a · 1 = a, a + a = a and a + a = 1; each follows directly from the definitions of the three operations.
Chapter 2 See also Boolean algebra; De Morgan's laws; Conjunction, disjunction and complement
The symbols the chapter writes its operations with. Its algebra writes AND as a · b or ab, OR as a + b and NOT as a bar, a; its figures and its XOR identity write AND as a ∧ b, OR as a ∨ b and XOR as a ⊕ b.
Chapter 2 See also Boolean algebra; Conjunction, disjunction and complement; XOR
A letter such as a or b that stands for a value that is only ever 0 or 1. Boolean algebra is the algebra of such variables. In the chapter's circuits each one is an input wire, and its complement a is that wire inverted.
Chapter 2 See also Boolean algebra; Bit; Boolean function
An instruction that can send execution somewhere other than the next address by overwriting the program counter. The book's CPU has two: JUMP always sets the counter to its operand, and JZ does so only when the accumulator is 0.
Chapter 5 See also Program counter; Branch predictor; Branch target; Conditional jump; JZ; Branch misprediction
A wrong guess by the branch predictor. The instructions fetched behind the branch were the wrong ones, so they are flushed, cycles of work thrown away: two instructions in the book's figure. Deeper pipelines fetch further ahead, so a wrong guess costs even more.
Chapter 5.b, Figure 5.b.4 See also Branch predictor; Pipeline; Branch; Flush; Pipeline depth; Two-bit counter
The logic that bets on a branch's outcome from past behaviour, so the pipeline can keep fetching before the branch executes. The book's predictor is a two-bit counter that each taken outcome raises and each not-taken outcome lowers; states 2 and 3 predict taken.
Chapter 5.b, Figure 5.b.4 See also Pipeline; Two-bit counter; Branch; Branch misprediction; Taken and not-taken; Flush
The address a branch sends execution to. In the book's CPU it is the operand of a JUMP or JZ: the control unit receives it from the decoder, and a taken branch overwrites the already-incremented program counter with it, so the next fetch starts there.
Chapter 5 See also Branch; Program counter; JUMP; JZ
A graph search that visits the source's neighbours first, then their neighbours, and so on outward in rings. Because it reaches nodes in order of distance, the first time it touches a node it has found a shortest path; the first step on that path is the routing table entry, and the distance is the hop count.
Chapter 11 See also Routing table; Hop; Hop count; Neighbour; Shortest path; Tie-breaking
The long-division step that appends the next digit of the dividend to the running remainder. In binary it is one shift: the remainder moves left one place and the next dividend bit drops into the empty low bit. For 13 / 3 the bits brought down are 1, 1, 0, 1.
Chapter 3.a, Figure 3.a.2 See also Left shift; Running remainder; Binary long division; Dividend and divisor
A message sent to every machine on a shared link at once. ARP broadcasts its question, who has B?; every machine hears it, but only the owner answers. A question about an address no machine owns, such as Z, is broadcast too but gets no answer.
Chapter 10.b, Figure 10.b.2 Try it See also ARP; Shared link; Address resolution; Network interface
An allocation scheme that splits free memory into halves and rejoins two matching halves when both are free. The chapter only names it, beside best fit and size classes, as a choice real allocators make to trade speed against how much the heap fragments; the book's Heap uses first fit.
Chapter 9.b See also Placement policy; Coalescing; First fit
A group of wires that carries the bits of one word side by side. In the chapter's register the data bus fans out to every bit. A real CPU drives an address bus and reads a data bus, and wide buses are one way a memory system moves many bits in parallel.
Chapter 4, Figure 4.5 See also Memory word; Register; Bandwidth
A group of eight bits, enough for any whole number from 0 to 255. Every memory word of the book's CPU is one byte, and its byte_word helper rejects any program word outside that range. To run a different program on this machine, you write different bytes into memory.
Chapter 5 See also Bit; Nibble; Memory word; Memory cell; Octet; Bit order
Bytes arriving one after another with nothing to mark where a message starts or stops. That unbroken stream is all the physical layer delivers, so the receiver cannot tell one message from the next until framing puts a FLAG byte at every boundary and the receiver splits the stream there.
Chapter 10 Try it See also Framing; Link-layer frame; Flag byte; Wire; Message
Escaping a payload byte that equals a delimiter, so it is never read as one. Before sending, each FLAG or ESC byte becomes ESC followed by the byte with one bit flipped, so 7e becomes 7d 5e; a bare FLAG then appears only at true frame boundaries, and the receiver reverses the substitution after splitting.
Chapter 10, Figure 10.3 Try it See also Link-layer frame; Delimiter; Escape byte; Flag byte; Framing; Mask
Instructions for a machine that exists only as software, a form between source text and real machine code. The chapter notes that Python compiles its source to bytecode first and runs that on a virtual machine, so it only resembles the book's tree-walking interpreter in style.
Chapter 7 See also Virtual machine; Interpreter; Compiler; Machine code; Python
A small, fast memory right beside the core, backed by larger, slower memory further out. It works because programs show locality, and it does not make memory fast; it makes the slow trip rare.
Chapter 5.c, Figure 5.c.3 Try it See also Cache line; Hit rate; Cache hit and miss; Locality; L1, L2 and L3 caches; Memory hierarchy
The two outcomes of a cache access. A hit finds the wanted line already in its slot; a miss fetches the line from slower memory and evicts whatever the slot held. Reading addresses 0 to 63 once through the book's four-slot cache gives 56 hits and 8 misses, one miss per new line.
Chapter 5.c, Figure 5.c.3 Try it See also Cache; Hit rate; Cache line; Miss penalty; Average access time; Eviction
The block of neighbouring words a cache moves at once. A miss on any word loads its whole line, eight words in the book's model, so the other seven words of that line are then hits; spatial locality is why caches move lines, not single words.
Chapter 5.c, Figure 5.c.3 See also Direct-mapped cache; Cache; Spatial locality; Cache hit and miss; Cache slot; Line number
One place in a cache that can hold one line. In the book's direct-mapped cache every line of memory has exactly one slot it may occupy, chosen by its line number; the model has four slots and records which line sits in each, not the data words themselves.
Chapter 5.c, Figure 5.c.3 See also Direct-mapped cache; Cache line; Eviction; Line number
A component that holds electric charge. A DRAM cell stores its bit as charge on a tiny capacitor controlled by a transistor, which makes the cell much smaller than an SRAM latch. The charge leaks, so the stored value fades unless the memory controller refreshes it.
Chapter 4 See also SRAM and DRAM; Refresh; Memory controller; Transistor
To take in the value on a data input at a clock edge and keep it. A flip-flop's Q captures the value d holds at each rising edge and ignores later changes until the next one; a register with load HIGH captures all four data bits together at the next edge.
Chapter 4, Figure 4.4 Try it See also Rising edge; D flip-flop; Register; Load line
The bit an addition passes to the next column when one column's sum is too large for a single bit: 1 + 1 = 102 writes 0 and carries 1.
Chapter 3, Figure 3.3 Try it See also Half adder; Full adder; Ripple-carry adder; Carry-in and carry-out; Intermediate sum and carry; Critical path
The path a carry follows through a ripple-carry adder, from the carry-out of each stage to the carry-in of the next. The chapter's figure draws it in red, flowing right to left from bit 0 to bit 3. It is what makes the adder slow at scale.
Chapter 3, Figure 3.4 Try it See also Ripple-carry adder; Critical path; Carry-in and carry-out; Latency; Adder stage; Carry-lookahead adder
The two carry connections of a full adder. The carry-in, cin, arrives from the less significant position and is added to a and b; the carry-out goes on to the next position. In a ripple-carry adder the lowest stage's carry-in is fixed at 0.
Chapter 3, Figure 3.3 Try it See also Carry; Full adder; Carry chain; Overflow
A faster adder design that real processors use in place of the ripple-carry adder. Carry-lookahead and prefix adders compute their carries in parallel instead of letting each wait for the stage before it. The book keeps the ripple design because its logic is transparent: you can trace the carry with your finger.
Chapter 3 See also Ripple-carry adder; Carry chain; Latency; Critical path
Cutting a request off the front of a free run and leaving the remainder free; a run exactly the size of the request is used up whole. The book's sixteen-cell heap starts as [(0, 16)], and three requests of four cells are carved from the front, leaving only [(12, 4)].
Chapter 9.b, Figure 9.b.2 Try it See also Free list; First fit; Free run
A document that ties a server's name to a public key, used to check who is at the other end. In a typical web TLS connection the client validates a certificate for the expected server name and verifies a handshake signature made with the matching private key. The book's toy leaves this step out.
Chapter 13.a See also Peer authentication; TLS; Handshake; Handshake signature; Intermediary; Pre-shared key
The ordered sequence of blocks that holds one file, each linked to the block with the next piece. The blocks need not sit side by side: the book's long is the chain 0 to 2 to 3 to 4, hopping over block 1, and reading the file in sequence is just following the links.
Chapter 9.d, Figure 9.d.2 Try it See also Linked allocation; File allocation table; End-of-chain marker; Disk block; File; Contiguous blocks
The thin conducting bridge that forms from source to drain when a voltage is put on a transistor's gate: the gate's electric field pulls electrons up to the surface. Take the voltage away and the channel vanishes.
Chapter 1, Figure 1.2 Try it See also MOSFET; Electron; Body and wells; Conductor and insulator; Field effect; n-type and p-type
One letter, digit, space or symbol of text, and the unit a lexer reads. A program arrives as flat text, a row of characters, and a parser can do nothing with it until they are grouped: in total = 12 + 3 the five letters of total form one name and the two digits of 12 one number.
Chapter 6.b, Figure 6.b.2 Try it See also Lexer; Token; String; Source code; Unexpected character
A loose charge that is free to move through a material and so carry a current. Pure silicon has few, and the chapter's program prints “few carriers” for it. Doping supplies them: a free electron from each phosphorus atom in n-type silicon, a hole from each boron atom in p-type.
Chapter 1, Figure 1.2 See also Electron; Hole; Current; n-type and p-type
A published result for one agreed input, used to confirm that code computes a checksum variant correctly. For the book's CRC the input is the bytes 123456789 and the check value is 0x29B1; the book's test compares against it as a reference vector.
Chapter 10 See also CRC-16/CCITT-FALSE; CRC; Checksum
A short value computed from a message and sent alongside it, so the receiver can recompute it and compare. If the two disagree, a bit was corrupted. The book's link uses a two-byte CRC and drops a frame that fails; a match does not prove that nothing changed.
Chapter 10 Try it See also CRC; Keyed checksum; Link-layer frame; Error detection; Bit flip; Check value
A signal that enters the fabric from outside the chip, as opposed to one a block produces. The book's fabric has two, a and b. A block input may be wired to a chip input or to an earlier block's output; in the half adder both blocks read the two chip inputs directly.
Chapter 5.d, Figure 5.d.4 Try it See also Fabric; Wiring entry; Configurable logic block
A rule for scrambling a message with a key so that only a holder of the key can unscramble it. The book's record cipher XORs each message byte with a byte of a repeating keystream. It demonstrates the operation and provides no real security, and strengthening it would not supply the missing peer authentication.
Chapter 13.a See also Encryption and decryption; Keystream; XOR; Ciphertext
The scrambled bytes that encryption produces and that cross the wire in place of the message. In the book's run the message attack at dawn becomes the ciphertext 11ad8b7713b2df7704f99b7707b7, sent with a checksum; flipping the low bit of its first byte is enough for the receiver's check to reject it.
Chapter 13.a, Figure 13.a.3 See also Encryption and decryption; Keystream; Encrypted record; Tampering; Cipher
Parts wired together so that signals flow from inputs to outputs. The book's circuits are gates joined by wires: the half adder is a gate-level circuit of one XOR and one AND sharing two inputs. Every circuit in the adder chapter is combinational; memory circuits come later, from the same gates.
Chapter 3, Figure 3.2 See also Logic gate; Gate network; Combinational logic; Netlist
A program that works out what a described circuit computes, testing a chip before it is built. Each round, the book's simulator fires every gate whose input wires are all known, so the XOR netlist settles in three rounds in any listing order; if gates remain but none can fire, a wire is undriven or gates form a loop.
Chapter 5.a, Figure 5.a.3 Try it See also Netlist; Hardware description language; Fire; Ready gate; Simulation round; Undriven wire
The two ends of a request and response exchange: the client encodes a request and parses the reply, and the server parses the request and answers. A server is then nothing more than a function from a request to a response; the book's looks the path up in a table of paths and the bytes each one serves.
Chapter 13, Figure 13.3 Try it See also Request and response; HTTP; Lookup server; Web server
A signal that ticks between 0 and 1 at a steady rate, giving every circuit in the machine the same beat to update on. It is what makes all the bits of a register change together.
Chapter 4, Figure 4.4 See also Gated D latch; D flip-flop; Clock cycle; Clock tick; Rising edge; Edge-triggered
One tick of the clock, and the unit in which the book counts a processor's time. Each of the pipeline's three stages takes one cycle, so four instructions run one at a time need twelve cycles and the overlapped pipeline needs six. Scheduling a pipeline is bookkeeping over cycle numbers.
Chapter 5.b, Figure 5.b.2 Try it See also Clock; Pipeline stage; Pipeline schedule; In flight
The slipping apart of two clocks that should keep the same time. The chapter lists it among the ways the physical layer is unreliable: the clock can drift, a voltage can be misread, noise can flip a bit. The bit-banged link removes that worry by sending the clock alongside the data.
Chapter 10 See also Clock tick; Free-running clock; Clock line; Physical layer
A wire that carries the sender's clock alongside the data line. The sender sets the data line while the clock is low, then raises the clock, and that rising edge tells the receiver the data is ready to read. Because the clock travels with the data, the receiver needs no separate free-running clock that could drift.
Chapter 10.a, Figure 10.a.2 Try it See also Bit-banging; Clock; Edge-triggered; Data line; Free-running clock; Clock pulse
One of the two stretches of a clock's beat: the time it stays LOW or the time it stays HIGH. A gated latch whose enable stays HIGH for a whole phase lets Q race through several values. In a flip-flop the master is transparent during the LOW phase and the slave during the HIGH phase.
Chapter 4, Figure 4.4 See also Clock; Rising edge; Transparent latch; Master-slave flip-flop
One swing of the clock line from low to high and back. Sending one bit takes three moves: set the data line, raise the clock, lower it again. The rising edge in the middle tells the receiver the data line is ready to be read, and eight pulses, one per bit, carry a byte.
Chapter 10.a, Figure 10.a.3 Try it See also Clock line; Rising edge; Data line; Bit-banging
One fixed slice of time marked out by a clock. On the book's wire the sender holds the data line high or low for one tick per bit and the receiver samples the line at each tick, so eight ticks carry the eight bits of the byte 0x68.
Chapter 10, Figure 10.2 See also Clock; Sampling; Clock drift; Physical layer
A complementary pair of transistors, the standard way modern logic gates are built. A p-channel pulls the output HIGH and an n-channel pulls it LOW; both see the same input, so for either valid input exactly one conducts.
Chapter 1, Figure 1.4 Try it See also Inverter; Pull-up and pull-down networks; Drive; MOSFET; n-channel and p-channel
Merging adjacent free runs into one each time a block is freed. Two runs are adjacent when the first's start plus its length equals the second's start, so (0, 4) and (4, 4) become (0, 8); without it, a request for the combined size would fail even though the room exists.
Chapter 9.b, Figure 9.b.3 Try it See also Free list; Heap fragmentation; Free run; Heap hole; Allocation failure; Buddy system
The compiler's work of emitting instructions from the tree. A while loop becomes a test label, the condition's value, a JZ that exits when it is zero, the body, and a JUMP back; the book's countdown loop becomes test0, JZ done0 and JUMP test0 for an idealized accumulator machine.
Chapter 8.a, Figure 8.a.2 Try it See also Compiler; Control-flow graph; Compiler temporary; Conditional jump; Emitter; Lowering
Logic whose output is a pure function of its present inputs, with no memory of any earlier input, so the same inputs always give the same output. The adders are combinational; the memory circuits built from the same gates are not.
Chapter 3, Figure 3.2 See also Half adder; SR latch; Feed-forward circuit; State; Propagation delay; Pure function
The two parts a shell splits a typed line into: the first word names the program to run, and the rest are handed to it. The line cat greeting splits into the command cat and the argument greeting, and add 40 2 prints 42.
Chapter 9.e, Figure 9.e.2 Try it See also Shell; Command dispatch; Command line
The shell's step of mapping a command name to one of the installed programs and running it. In the book the programs are already-resident Python functions, so nothing is loaded from storage; a name that matches none, such as spork, gets spork: command not found and nothing else happens.
Chapter 9.e, Figure 9.e.3 Try it See also Shell; Command and arguments; Command line; Resident program; Dispatch
One line of text typed at a shell, naming a program and what to hand it. The shell reads it, splits it into words and treats the first as the command. The book's session types six, among them echo hello world, cat greeting and add 40 2; an empty line does nothing.
Chapter 9.e, Figure 9.e.3 Try it See also Shell; Command and arguments; Command dispatch
Text in a program meant for a human reader and ignored by the translator. In the book's assembly anything after a semicolon is a comment: the parser drops everything from the first semicolon onward, so ; acc = a beside LOAD a never reaches the assembler.
Chapter 6 Try it See also Assembly language; Source code; Assembler
Deciding which of two numbers is the larger. It is the divider's only decision: is the running remainder at least as large as the divisor? In the run of 13 / 3 the test fails at bit 3, where 1 < 3, and succeeds at bit 2, where 3 ≥ 3, so the divisor is subtracted there.
Chapter 3.a, Figure 3.a.2 See also Running remainder; Binary long division; Quotient bit; Divider
An expression that asks a question about two values and answers with a number. The book's imperative language has one, a < b, which yields 1 when true and 0 when false, so a loop has something to test: i < b stays 1 until i reaches b, then becomes 0.
Chapter 8 Try it See also Loop condition; Expression; Operator; Loop
A program that writes a program: it translates a language down into one the machine already runs. The book's compiler walks the tree of (a + b) + c and emits assembly that loads a, adds b and c, and stores the result; assembled and run on the CPU, that program also gives 42.
Chapter 7, Figure 7.3 Try it See also Interpreter; Assembler; Abstract syntax tree; Code generation; High-level language; Lowering
The short pipeline, shared by compilers and interpreters, that reads a program before it is run or compiled. The lexer turns text into tokens, the parser turns tokens into a tree, and the tree is then run or compiled; each stage hands the next a tidier form of the program.
Chapter 6.b, Figure 6.b.3 See also Lexer; Parser; Abstract syntax tree
A memory cell the compiler invents to hold an intermediate value. The accumulator holds one value at a time, so the outer addition saves its left side in _t0, computes the right side, then adds the saved value; a nested addition uses the next depth, and the underscore keeps these names apart from any the source can use.
Chapter 8.a See also Code generation; Accumulator; Emitter
Building a new part by feeding the outputs of existing parts into the inputs of others. Each new gate in the chapter is a short composition of nand calls: OR is nand(not_(a), not_(b)), and NOR is not_(or_(a, b)) and nothing else.
Chapter 2, Figure 2.3 Try it See also Universal gate; NAND; Gate network; Gate count
A jump taken only when a test comes out a certain way; the book's is JZ, taken when the accumulator is zero. A compiled loop needs one conditional jump and one unconditional: JZ done0 leaves the loop when the condition is zero, and JUMP test0 after the body returns to the test.
Chapter 8.a, Figure 8.a.2 Try it See also Branch; Code generation; Loop; Control-flow graph; Unconditional jump; JZ
A conductor lets current flow easily; an insulator blocks it. Silicon is neither, hence semiconductor, and doping lets its conductivity be engineered. In the MOSFET the thin glass under the gate is an insulator, while the channel a HIGH gate forms is a conducting bridge between the wells.
Chapter 1, Figure 1.2 Try it See also Semiconductor; Oxide insulator; Current; Channel
The loadable wiring between an FPGA's blocks: a mesh of programmable switch points, each a transistor whose gate is driven by a stored configuration bit. Write 1 and the two wires it straddles connect; write 0 and they do not, so the connections are memory too, set by the bitstream.
Chapter 5.d, Figure 5.d.5 Try it See also Bitstream; Fabric; Switch; Configuration bit; Switch point; Wiring entry
One of the identical blocks that make up an FPGA. The book's is a two-input lookup table whose four loaded entries decide which gate it is; a real logic block also pairs its LUT with a flip-flop on its output, so a fabric can hold state between clock ticks.
Chapter 5.d, Figure 5.d.2 Try it See also Lookup table; Fabric; Chip input
One stored bit of an FPGA's setup. Some fill the lookup tables, four one-bit entries for a two-input block; others drive the switch points of the wiring, where a 1 connects the two wires a switch straddles and a 0 leaves them apart. The bitstream is all of them together.
Chapter 5.d Try it See also Bitstream; Configurable interconnect; Lookup table; Switch point
The names Boolean algebra gives its three operations. Conjunction is AND, the product a · b, which is 1 only when both are 1. Disjunction is OR, the Boolean sum a + b, which is 0 only when both are 0. Complement is NOT, written a, which flips the value.
Chapter 2 See also Boolean algebra; AND, OR and NOT; Boolean identity; Boolean notation; Q and NOT Q
The header that states a message body's length up front, so the receiver counts out exactly that many bytes and stops. The blank line marks where the head ends but cannot mark where the body ends, since a body may hold a blank line of its own; the book's reply says Content-Length: 23.
Chapter 13, Figure 13.2 See also HTTP header; Blank line; Message body; Message framing; Message parsing
Swapping one process out of the processor and the next one in. There is only one set of registers, so the operating system saves the current process's context and restores the next one's; because this is faithful, the book's two processes still end holding 42 and 9, exactly as when each runs alone.
Chapter 9, Figure 9.2 Try it See also Process; Time-sharing; Process context; Running and waiting; Save and restore; Scheduler
Blocks that sit next to each other in one unbroken row. A file rarely gets them once files have been written and deleted for a while. The book's long lands in blocks 0, 2, 3 and 4, which are not contiguous, yet the chain links them in order and the file reads back whole.
Chapter 9.d Try it See also Chain of blocks; Linked allocation; Allocation scheme
The order in which a program's statements run, including repetition. The book's while loop tests i < b each pass and runs the body while the test is nonzero, so repeated addition yields multiplication; as jumps, a JUMP would return to the test and a JZ would leave the loop once the test reaches zero.
Chapter 8, Figure 8.3 Try it See also Statement; Control-flow graph; Loop; Sequencing; Straight-line code; Imperative language
The wire whose voltage decides whether a switch conducts, as distinct from the signal line it gates. In a transistor read as a switch the gate is the control line and the drain-to-source path is the signal. A HIGH control closes the chapter's switch; a LOW one leaves it open.
Chapter 1, Figure 1.3 Try it See also Switch; Signal; Source, drain and gate; Open and closed switch; Wire; Select line
A line by which the control unit directs another part of the CPU. For each opcode the book's control unit asserts the right ones: it enables the accumulator write or the STORE write to memory, steers the selector in front of the accumulator, and lets a taken branch override the advanced program counter.
Chapter 5 See also Control unit; Datapath; Assert; Write line; STORE
The small piece of logic that reads an opcode and asserts the right signals, directing the other parts of a CPU. In the book's model it is a conditional with one case per instruction; it enables the accumulator or memory write and takes the accumulator's zero test for JZ.
Chapter 5 See also CPU; Opcode and operand; Datapath; Instruction decoder; Control signal; Zero test
The graph of where control can go next among a program's instructions. A loop is a cycle in it: while the test is nonzero, control enters the body and the body jumps back to the test; when it reaches zero, JZ sends control out to done.
Chapter 8.a, Figure 8.a.3 See also Control flow; Code generation; Graph; Conditional jump
One complete processor: the part of a chip that fetches, decodes and executes instructions. The book measures every memory by its distance from the core. An addition takes it about a cycle and a read from main memory a few hundred, so without a cache beside it a core would spend almost all of its life waiting.
Chapter 5.c See also CPU; Cache; Memory hierarchy; Pipeline
A loop whose counter starts at the number of passes wanted and falls to zero, so the counter itself can be the condition. The book rewrites its multiplication this way, with i = b and while i do. Its grammar has no negative literals, so each pass adds an input named minusone, which holds -1.
Chapter 8.a Try it See also Loop counter; Repeated addition; Loop; Conditional jump
A machine that reads instructions from memory and obeys them one at a time. The book's CPU is the ALU, a memory and a control unit wired together; its state is a 16-word memory holding both program and data, the accumulator, the program counter and a halted flag.
Chapter 5 Try it See also Fetch-decode-execute cycle; Control unit; Datapath; Accumulator machine; Core; Virtual machine
A cyclic redundancy check: a checksum computed from the data and sent with it, the remainder of a long division carried out in binary by a fixed generator polynomial. The receiver recomputes it and drops a frame whose CRC disagrees. The book's CRC-16/CCITT-FALSE gives 0x29B1 for the bytes 123456789; a match is not proof that nothing was corrupted.
Chapter 10, Figure 10.3 Try it See also Generator polynomial; Link-layer frame; Binary long division; Checksum; CRC-16/CCITT-FALSE; Bit flip
The particular CRC the book computes: a 16-bit remainder sent as two bytes, in the variant that starts its register at the initial value 0xFFFF and uses no bit reflection. Each variant has its own published check value, and this one gives 0x29B1 for the bytes 123456789.
Chapter 10 See also CRC; Generator polynomial; Check value; Checksum
The slowest chain of stages a result must wait on before it is valid, which sets a circuit's latency. In a wide ripple-carry adder it runs the full width of the carry chain, one full adder deep per bit, because each stage's carry waits for every stage to its right to settle.
Chapter 3, Figure 3.4 Try it See also Ripple-carry adder; Carry; Propagation delay; Carry chain; Latency; Carry-lookahead adder
Two gates wired so that each one's output feeds an input of the other. The SR latch is a cross-coupled pair of NOR gates, and its two crossed feedback wires are the memory: they are what makes the latch different from any circuit in the earlier chapters.
Chapter 4, Figure 4.2 Try it See also SR latch; Feedback; NOR
An acknowledgement that is a single number meaning everything up to here has arrived, instead of a list naming each segment. TCP uses it, with optional selective information. The book's receiver does not: it names every segment it holds, so it can report segments 0 and 2 while segment 1 is still missing.
Chapter 12 See also Acknowledgement (ACK); Selective acknowledgement; TCP
The flow of charge along a conducting path. A switch either lets it pass or blocks it. In the chapter's NAND the output is dragged LOW only when current can flow all the way down to the LOW rail, which needs both series switches closed at once.
Chapter 1, Figure 1.6 Try it See also Voltage; Charge carrier; Switches in series; Rail; Conductor and insulator; Open and closed switch
A one-bit store whose output Q changes only at the rising edge of the clock, taking the value d held at that instant. Two gated D latches in series, a master and a slave, produce this behaviour.
Chapter 4, Figure 4.3 See also Edge-triggered; Register; Master-slave flip-flop; Rising edge; Gated D latch; Clock
A memory cell that holds a value for the program to work on, not an instruction. A DATA directive makes one: a raw byte, not split into opcode and operand. The book's program names four, a, b, c and result, and opens with JUMP start so the CPU never tries to execute them.
Chapter 6, Figure 6.3 Try it See also Directive; Memory cell; Byte
The case where an instruction in a pipeline needs a value the instruction just ahead of it has not finished computing. It must wait until the value exists, so a bubble opens and everything behind it slips a cycle.
Chapter 5.b, Figure 5.b.3 Try it See also Stall; Forwarding; Pipeline; Dependent chain; Hazard rule; Independent instructions
The wire that carries the bits themselves, beside the clock line that says when to read them. To send a bit, the sender puts it on the data line and then pulses the clock from low to high. Eight pulses, most significant bit first, carry a byte: 01000001 is the letter A.
Chapter 10.a, Figure 10.a.2 Try it See also Clock line; Sampling; Bit-banging; Clock pulse; SPI
The layer that turns the wire's raw, unmarked stream of bytes into something usable. It has two jobs: mark where one message ends and the next begins, by wrapping each in a frame, and notice when the wire corrupts a bit, by a CRC. A frame that fails the check is dropped.
Chapter 10 See also Physical layer; Link-layer frame; CRC; Layer; Network layer
The routes values take between a CPU's parts. In the book's CPU the program counter drives the memory address, the decoder splits the fetched word, and a multiplexer chooses whether the ALU's sum or a loaded word enters the accumulator, so loading 1 and then 2 leaves 2, not 3.
Chapter 5 See also CPU; Control unit; Multiplexer; Control signal
Two laws that tie AND and OR together through complementation: a · b = a + b and a + b = a · b. The first is why a NAND fed inverted inputs behaves as OR.
Chapter 2, Figure 2.2 See also Boolean algebra; NOR; Boolean identity; Equivalence; Inversion bubble
The everyday way of writing numbers, in which places have weights 1, 10, 100 from right to left. The book states values in decimal and builds circuits in binary: decimal 13 is 11012, and the chapter's sum of 11 and 6 is 10112 + 01102 = 100012, which is 17.
Chapter 3 See also Binary numeral; Weight (of a place)
A value set aside to mark a boundary instead of carrying data. The book's frames use two, the FLAG byte that opens and closes a frame and the ESC byte that announces a stuffed byte. Byte stuffing leaves no bare delimiter inside a frame, so a payload may contain the very bytes used as delimiters.
Chapter 10, Figure 10.3 Try it See also Flag byte; Escape byte; Byte stuffing; Framing
One turn of the book's delivery loop: the sender sends every segment not yet acknowledged, the channel delivers some of them, and the sender immediately learns what the receiver holds. Rounds are synchronous, a simplification; real delivery uses timers. The book's run takes two rounds, sending [0, 1, 2, 3] and then [0, 2].
Chapter 12 Try it See also Retransmission; Lossy channel
A run of instructions in which each needs the result of the one before it, so every link is a data hazard. In the book's timing model each then waits two cycles past the instruction it depends on, and four chained instructions take nine cycles where four independent ones take six. The accumulator CPU's arithmetic forms such chains.
Chapter 5.b, Figure 5.b.3 Try it See also Data hazard; Stall; Independent instructions; Accumulator
A table that pairs each key with a value and finds the value by its key. The book's interpreter holds a program's whole state in an ordinary dictionary keyed by variable name; after the multiplication loop it holds a as 6, b as 7, product as 42 and i as 7.
Chapter 8 Try it See also Variable environment; Mutable state; Binding; Named memory; Python
A way for two strangers to agree on a number they never send. Both publicly agree on a base g and a prime p; each keeps a private exponent, publishes g raised to it modulo p, then raises the other's public value to it, again modulo p. With g = 5, private exponents 6 and 15 both reach 1893334806.
Chapter 13.a, Figure 13.a.2 Try it See also Modular arithmetic; Shared secret; Peer authentication; Public value; Key agreement; Passive observer
The simplest cache that works: each line of memory maps to exactly one slot, chosen by its number. A load hits if that slot already holds its line; otherwise it misses, fetches the line and evicts whatever was there.
Chapter 5.c, Figure 5.c.3 See also Cache line; Cache slot; Eviction; Line number; Thrashing
A line of assembly that instructs the assembler, not the CPU. The book has one, DATA, which places a literal value in memory: where an instruction is encoded into an opcode and an operand, a DATA line becomes one raw byte, a data cell.
Chapter 6, Figure 6.3 Try it See also Assembly language; Mnemonic; Memory cell; Data cell
The small table that maps each file's name to the first block of its chain. It remembers only where a file begins: for long it records block 0, and the file allocation table leads from there to the end.
Chapter 9.d, Figure 9.d.3 See also File allocation table; Linked allocation; File; File deletion; File name; Filesystem
Sets of frames with no frame in common. The book's isolation rests on them: program A's table maps its pages to frames 5 and 2, program B's to frames 8 and 9, so both can write virtual address 3 without meeting. Through fixed, disjoint mappings each program reaches only its own cells.
Chapter 9.c, Figure 9.c.3 Try it See also Memory isolation; Page and frame; Shared frame; Address collision
A storage device divided into a grid of fixed-size blocks, each known by its number. It is not a smooth surface to lay a file down on: a file takes whichever blocks have room. The book's Disk keeps the bytes of each block, a table of links and a directory; the figure draws eight blocks, numbered 0 to 7.
Chapter 9.d, Figure 9.d.2 Try it See also Disk block; Persistent storage; Filesystem
One of the fixed-size pieces in the grid a disk is divided into. A file rarely fits in one block, nor in blocks next to each other once files have been written and deleted for a while, so the book's 13-byte file long is cut into four pieces that land in blocks 0, 2, 3 and 4.
Chapter 9.d, Figure 9.d.2 See also Linked allocation; File allocation table; Disk; Block size; Chain of blocks; Free block
Routing a request to the routine that serves it by looking it up in a table. The book's kernel dispatches a trap by its number, so syscall(WRITE, 42), carrying number 0, reaches the write routine; its shell dispatches a typed line by its command name. Dispatch alone is not protection.
Chapter 9.a, Figure 9.a.3 Try it See also System call; Menu of services; Handler; Command dispatch; Request number
The number being divided and the number it is divided by. In the book's run of 13 / 3 the dividend is 1101 and the divisor is 0011. The divider walks the dividend's bits from the most significant, bringing one down at a time, and subtracts the divisor whenever the running remainder is large enough.
Chapter 3.a, Figure 3.a.2 See also Binary long division; Quotient and remainder; Bring down; Integer division
The circuit or routine that carries out a division. The book's divider is a loop that, for each dividend bit, shifts, compares, subtracts and records a quotient bit. Real processors use faster divider circuits, handle signed numbers and also divide fractions, all of which the chapter leaves out.
Chapter 3.a See also Binary long division; Quotient and remainder; Comparison; Signed and unsigned; Integer division
Mixing a trace of another element into silicon on purpose, so that its conductivity can be engineered. Phosphorus, with five outer electrons, leaves spare electrons free; boron, with three, leaves holes that behave like mobile positive charges.
Chapter 1, Figure 1.2 Try it See also n-type and p-type; Electron; Hole; Silicon; Semiconductor
Inverting a signal twice, which gives back the original value. Follow a NAND with a NOT and the two inversions cancel, leaving plain AND; the chapter's program writes it as not_(nand(a, b)).
Chapter 1, Figure 1.7 See also Tied inputs; AND, OR and NOT; NAND
To set a wire's level by connecting it to a rail through a conducting switch. In the CMOS inverter the input drives both gates, and for either valid input exactly one transistor conducts, so the output is driven cleanly HIGH or LOW. An input left disconnected is driven by nothing and can float.
Chapter 1, Figure 1.4 Try it See also Rail; Pull-up and pull-down networks; CMOS; Floating input; Input and output; Signal restoration
A frame the receiver throws away instead of passing on, because the CRC it recomputes does not match the one the frame carried. In the chapter's run both frames are sent again with one bit flipped; the receiver drops the corrupted frame and keeps the good one, so one message arrives.
Chapter 10 See also Error detection; Bit flip; CRC; Link-layer frame
A second copy of a segment the receiver already holds; a best-effort network can duplicate a packet as well as drop it. The book's reassembly indexes segments by sequence number, so a segment that arrives twice just overwrites itself with identical data. The example channel never duplicates.
Chapter 12 See also Reassembly; Sequence number; Best-effort delivery
Changing only at one instant, the rising edge of the clock, rather than for as long as an enable is HIGH. A D flip-flop is edge-triggered: Q takes the value d held at each rising edge and ignores changes in between.
Chapter 4, Figure 4.3 See also D flip-flop; Clock; Rising edge; Transparent latch; Clock line; Sampling
A particle that carries negative charge. The chapter counts each atom's outer electrons: silicon has four, phosphorus five and boron three. Phosphorus's fifth electron has no bond to join, so it drifts free, and the electrons a HIGH gate pulls up to the surface form the channel.
Chapter 1, Figure 1.2 Try it See also Hole; Charge carrier; Channel; Doping
The part of a compiler that writes out instructions, appending each to the program it is building. The book's code generator has two: an expression emitter, which leaves an expression's value in the accumulator, and a statement emitter, which stores an assignment's result or tests a loop's condition and plants the jumps.
Chapter 8.a Try it See also Code generation; Compiler; Compiler temporary
The input that decides whether a latch listens to its data. While enable is HIGH the gated D latch passes d through to Q; while it is LOW the latch feeds its held value back to itself. In code the whole latch is a multiplexer that selects either d or the stored value.
Chapter 4, Figure 4.3 See also Gated D latch; Transparent latch; Clock; Load line; Opaque latch
One protected message on a secure channel. The book's toy record XORs the message with a repeating keystream derived from the shared secret and adds a one-byte keyed checksum, which the receiver checks before XORing the same keystream back. A matching one-byte tag establishes neither cryptographic integrity nor the sender's identity.
Chapter 13.a, Figure 13.a.3 See also Keystream; Shared secret; Integrity; Keyed checksum; Secure channel; Ciphertext
Turning a message into ciphertext with a key, and turning it back. The book's toy does both with one operation, XORing the bytes with a keystream derived from the shared secret. Its decrypt checks the checksum first and only then XORs the keystream back, so Bob reads attack at dawn.
Chapter 13.a, Figure 13.a.3 See also Ciphertext; Keystream; Cipher; Encrypted record; Key; In the clear
The entry in the file allocation table that says a block is the last of its file, with no block after it. Writing marks the final block this way, and reading follows the chain until it meets the mark. For the book's long, block 3 leads to block 4, and 4 is the end.
Chapter 9.d, Figure 9.d.3 See also File allocation table; Chain of blocks; Free block
One of the two machines a conversation is meant to be between, as distinct from anything on the wire in the middle; the chapter also calls the other endpoint the peer. Agreement alone does not identify the other endpoint: with an intermediary in place, neither endpoint detects that it agreed with the intermediary.
Chapter 13.a See also Alice and Bob; Peer authentication; Intermediary
Two circuits are equivalent when they produce identical outputs for every combination of inputs, however differently they are drawn. The chapter's example is De Morgan's: a NAND and an OR with inverted inputs are the same gate, an equivalence its figure makes visible as geometry.
Chapter 2, Figure 2.2 See also Truth table; De Morgan's laws; Inversion bubble
Noticing that data was damaged on its way. The receiver has no other copy to compare against, so the sender sends a checksum alongside the data and the receiver recomputes it; if the two disagree, a bit was corrupted. The book's link then drops the frame, which makes corruption visible.
Chapter 10 See also CRC; Checksum; Bit flip; Dropped frame
The special byte, ESC, that begins a two-byte escape sequence and tells the receiver that the byte after it was stuffed; it is 7d in the book. An ESC that occurs in the data must itself be escaped: the chapter's second message contains one, and it crosses the wire as 7d 5d.
Chapter 10, Figure 10.3 Try it See also Byte stuffing; Flag byte; Delimiter; Mask
A widely used technology for local links, and the setting in which link addresses are called MAC addresses. An Ethernet MAC address has six octets, which the book shortens to four in its examples, and the standard that defines ARP describes mapping a next-hop network address to an Ethernet address.
Chapter 10.b See also MAC address; ARP; Link-layer frame; Octet; RFC
Working out the value of an expression. In the book's interpreter a number node evaluates to its value, a variable node to whatever the environment binds it to, and an addition node to the wrapped sum of its two children, so (a + b) + c evaluates to 42. A statement, by contrast, is executed.
Chapter 7 Try it See also Expression; Interpreter; Tree walk; Variable environment
Removing a line from a cache slot to make room for another. In a direct-mapped cache each line has exactly one slot, so a miss always evicts whatever that slot held. The book's thrashing trace visits lines 0, 4, 8 and 12, which all map to slot 0, so each visit evicts the line before.
Chapter 5.c Try it See also Cache hit and miss; Direct-mapped cache; Thrashing; Cache slot
The way a running Python function reports that it cannot carry on: it stops and hands the problem to its caller. The book's translator raises one, a PageFault, for a virtual page its table does not map, since no physical address can be returned. A real page fault goes to a kernel handler instead.
Chapter 9.c See also Page fault; Page mapping
A file that holds a program's bytes, ready to be loaded into memory and run. A real shell asks the operating system to load one for a command. The book's commands are not executable files loaded onto its CPU; they are Python functions already available in the shell.
Chapter 9.e See also Loader; File; Program
A cap on how many steps a run may take, so that an experiment cannot run forever. The book's interpreter spends one step at every assignment and every condition test, 10,000 by default across the whole program, and raises an execution-limit error when they run out. Reaching the limit means the run was stopped, not that it finished.
Chapter 8 Try it See also Nonterminating loop; Loop; Interpreter
A piece of a program that computes a value. In the book's first language an expression is numbers and variable names joined by +, with parentheses to group, and groups can nest: (a + b) + c is one, and with a, b and c bound to 10, 20 and 12 it evaluates to 42.
Chapter 7, Figure 7.2 See also Abstract syntax tree; Statement; Parser; Operator; Sub-expression; Evaluation
A language whose whole program is one expression: a fixed formula, evaluated once, as a calculator does. The book's first language has only integer literals, variable names, addition and parentheses, and (a + b) + c is the whole of it. With no state and no loop it can add but cannot multiply.
Chapter 7 Try it See also Expression; Imperative language; High-level language; Programming language
What a language is able to say. Neither the book's machine nor its expression language can multiply, yet a loop over addition does; the chapter's lesson is that control flow buys expressiveness the hardware does not have on its own. With state, sequencing and repetition a language can compute anything the machine can.
Chapter 8 See also Control flow; Imperative language; Repeated addition
The generic hardware of an FPGA: identical configurable blocks plus loadable wiring between them. The hardware itself never changes; only the bits loaded into it do. The book's model is a row of blocks; two of them, loaded as XOR and AND and fed the same two inputs, make the half adder.
Chapter 5.d, Figure 5.d.4 Try it See also FPGA; Configurable logic block; Bitstream; Configurable interconnect; Reconfiguration; Wiring entry
The property of a scheduling policy that gives every unfinished process its turn. Round-robin is the simplest fair policy: the book's scheduler goes around its list giving each process the same quantum, skipping only those that have halted. An exercise adds a third program to confirm each still gets its fair turn.
Chapter 9 Try it See also Round-robin scheduling; Scheduling policy; Time slice
What happens when a conditional jump is not taken: execution carries on with the next instruction. In the book's jump-driven machine JZ moves the program counter to its label only if the accumulator is zero and otherwise falls through, which is how a loop's test lets control into the body.
Chapter 8.a See also Conditional jump; Program counter; Unconditional jump; Straight-line code
A circuit in which signals flow one way, from inputs to outputs, with no path leading back. The book's fabric allows nothing else: a block may only read the chip inputs or blocks before it, so a loaded circuit can never chase its own tail and always settles. The model stops at combinational fabrics.
Chapter 5.d See also Feedback; Combinational logic; Fabric; Wiring entry
Wiring a circuit's output back to one of its inputs, so the circuit can reach a state that it reinforces and hold itself there. No combinational circuit has it, and it is what lets a latch remember a bit.
Chapter 4, Figure 4.2 Try it See also SR latch; State; Cross-coupled gates; Hold state; Memory; SRAM and DRAM
The loop a CPU runs until HALT: fetch the word at the program counter, advance the counter, decode the word, and execute the operation. Each turn runs one instruction; a JUMP or JZ that fires overwrites the advanced counter.
Chapter 5 Try it See also Program counter; Pipeline; CPU; Instruction; Stored program; Pipeline stage
Controlling whether a path conducts with an electric field alone. A voltage on the gate sets up a field that reaches through the thin glass and pulls electrons up to the silicon surface, where they form the channel. It gives the field-effect transistor its name.
Chapter 1, Figure 1.2 Try it See also MOSFET; Channel; Oxide insulator; Voltage
Able to be given its circuit after it leaves the factory. The factory ships the same blank chip to everyone, and it is programmed in the field, after manufacture, by whoever loads it. The two words open the name FPGA, a field-programmable gate array.
Chapter 5.d See also FPGA; Bitstream; Fixed silicon
A named sequence of bytes kept on a disk, where it outlives the program that wrote it. On the disk it is not one piece: its bytes are cut into block-size pieces and chained. The book's long holds the 13 bytes HELLO, FILES! in four blocks and reads back exactly as written.
Chapter 9.d, Figure 9.d.2 Try it See also Filesystem; Directory; Chain of blocks; File name; Persistent storage; Executable file
The table, one entry per disk block, that gives the next block in each file's chain or marks the block as the last. Reading long, the directory says start at block 0, and the table says 0 leads to 2, 2 to 3, 3 to 4, and 4 is the end.
Chapter 9.d, Figure 9.d.3 See also Directory; Linked allocation; Disk block; Chain of blocks; End-of-chain marker; File deletion
Removing a file by dropping its name from the directory and marking every block in its chain free. In the book's run, deleting a and c frees blocks 0 and 2, which the next file reuses. Writing over an existing name frees its old chain first, so no blocks are leaked.
Chapter 9.d See also Free block; Directory; File allocation table
The label by which a file is asked for. It is not kept with the file's bytes: the directory maps each name to the first block of its chain, and the blocks hold only data. The book's directory lists long at block 0 and b at block 1.
Chapter 9.d, Figure 9.d.3 See also Directory; File; File allocation table
The scheme that keeps named files on a disk of fixed-size blocks and finds their bytes again. The book's model uses linked allocation, held together by a directory and a file allocation table; filesystems can also use indexed blocks or runs of adjacent blocks. The book's model lives in Python memory, so nothing survives a restart.
Chapter 9.d, Figure 9.d.3 Try it See also Linked allocation; Directory; File allocation table; Disk; File; Allocation scheme
To evaluate a gate during simulation. A gate can fire only once every wire it reads is known; firing computes its output wire by calling the function its kind names, and that newly known wire may let other gates fire. In the XOR netlist shared fires first, then left and right, then out.
Chapter 5.a, Figure 5.a.3 Try it See also Ready gate; Simulation round; Circuit simulator
The placement policy that takes the first free run at least as large as the request; the book's Heap uses it, carving each request off the front of that run. It is the simplest choice, not the only one: real allocators also use best fit, buddy systems and size classes to trade speed against how much the heap fragments.
Chapter 9.b Try it See also Free list; Memory allocator; Best fit; Buddy system; Carving; Placement policy
A circuit cast directly into a chip, its gates and wires set at manufacture. It is the fastest and most frozen end of the chapter's spectrum: change one gate and you manufacture a new chip. A CPU is one fixed circuit made universal by running programs; an FPGA sits between the two.
Chapter 5.d See also FPGA; CPU; Field-programmable; Prototyping; Hardware
Keeping every number in the same set count of bits. It makes subtraction cheap: after the two's complement is added, the final carry-out is discarded and the remaining fixed-width bits are the answer. The chapter's run writes its numbers in four bits: 1101, 0011 and 0100.
Chapter 3.a See also Bit width; Two's complement; Wraparound; Minuend and subtrahend; Signed and unsigned
The chosen byte that marks where a frame starts and ends, 7e in the book. A receiver watching an unmarked stream of bytes treats each FLAG as a frame boundary, which is why a payload byte equal to it must be escaped before sending.
Chapter 10, Figure 10.3 Try it See also Link-layer frame; Byte stuffing; Payload; Delimiter; Escape byte; Framing
Turning a tree into a plain list of its leaves, left to right. The book's compiler flattens the addition tree of (a + b) + c to a, b, c, gives each distinct operand a memory cell, then emits code that loads the first and adds the rest. Associativity is what makes the flat list correct.
Chapter 7 See also Associativity; Root, child and leaf; Compiler; Code generation; Operand (of an expression)
An input left disconnected, so that nothing drives it and it can float at an unpredictable voltage. The chapter's account of CMOS assumes settled, valid LOW or HIGH inputs; a floating input is one of the analog effects its binary model leaves out.
Chapter 1 See also Drive; Voltage; Analog and digital
Throwing away instructions that entered the pipeline on a wrong guess. When a branch is mispredicted, the instructions fetched behind it were the wrong ones, so the cycles spent on them are lost. The book's figure flushes two; a deeper pipeline fetches further ahead and would flush more.
Chapter 5.b, Figure 5.b.4 See also Branch misprediction; Branch predictor; Pipeline; Pipeline depth
Routing a value straight from the execute stage that computes it to the instruction behind, instead of making that instruction wait for the write-back. Many stalls disappear, but a value needed before it exists is still a hazard.
Chapter 5.b, Figure 5.b.3 See also Data hazard; Write-back
A multiplexer with four data inputs, chosen between by two select bits. Three 2-to-1 multiplexers compose into one. The book's ALU uses one per bit position, written mux4, to pick among the add, AND, OR and XOR results according to the two opcode bits.
Chapter 3 See also Multiplexer; Select line; ALU; ALU opcode
A field-programmable gate array: a chip of identical generic blocks into which a circuit is loaded as data after manufacture, not wired. The same chip can be an adder one minute and something else the next.
Chapter 5.d, Figure 5.d.4 Try it See also Lookup table; Bitstream; Field-programmable; Fabric; Fixed silicon; Reconfiguration
Marking where each message begins and ends in a stream of bytes, one of the link layer's two jobs. The book's sender appends a two-byte CRC to the payload, stuffs the bytes and adds a FLAG at each end; the receiver splits the stream at the flags, un-stuffs each frame and checks its CRC.
Chapter 10, Figure 10.3 Try it See also Link-layer frame; Byte stuffing; Flag byte; Delimiter; Byte stream; Sender and receiver
A disk block that belongs to no file, marked as free in the file allocation table. The book's writer takes free blocks in index order, earliest first, and never looks for a row of them: once two deletions free blocks 0 and 2, the next file lands in blocks 0, 2, 3 and 4.
Chapter 9.d, Figure 9.d.2 Try it See also Disk block; File allocation table; File deletion; End-of-chain marker
The allocator's record of the runs of memory not in use, each a start and a length. A request is carved off the front of a run large enough: the book's sixteen-cell heap starts as [(0, 16)] and, after three allocations of four, holds only [(12, 4)].
Chapter 9.b, Figure 9.b.2 Try it See also Memory allocator; Coalescing; Heap; Carving; First fit; Free run
One unbroken stretch of memory not currently in use, recorded on the free list as a start and a length. The book writes (12, 4) for four free cells starting at address 12. Two runs that touch, such as (0, 4) and (4, 4), merge into one, (0, 8).
Chapter 9.b, Figure 9.b.3 Try it See also Free list; Coalescing; Live block; Heap hole; Carving; Allocation failure
A clock that ticks on its own, independent of the machine at the other end of a link. Two such clocks can drift apart, the worry of the framed wire. On the book's two-line link the clock travels alongside the data, so the receiver needs no separate free-running clock and reads only on the sender's rising edges.
Chapter 10.a See also Clock drift; Clock line; Clock; Bit-banging
A one-bit adder that also accepts a carry-in from the less significant position. It is two half adders and an OR: the first adds a and b, the second adds that sum to the carry-in, and the OR merges the two carries.
Chapter 3, Figure 3.3 Try it See also Half adder; Carry; Adder stage; Carry-in and carry-out; Intermediate sum and carry
How many gates a circuit uses, a first measure of its cost. Counted as NANDs, the chapter's NOR is four: two input inverters, the OR NAND and one final NAND acting as NOT. XOR is also four, because one NAND is shared instead of being computed twice.
Chapter 2 See also Composition; Universal gate
Several gates wired together, outputs into inputs, to compute one result. The chapter's XOR is a four-gate network of NANDs that detects whether two bits disagree, and the chapter calls it part of the skeleton of every binary adder.
Chapter 2, Figure 2.3 Try it See also XOR; Level (of gates); Composition; Circuit
One entry of a netlist, describing one gate: the wire it drives, its kind, and the wires it reads. The first record of the chapter's XOR netlist says that a nand gate drives the wire shared and reads a and b; four such records are the whole circuit.
Chapter 5.a, Figure 5.a.2 See also Netlist; Wire; Graph; Node and edge
The tidy shape an engineer draws for a logic gate in place of its transistors. The chapter shows NAND both ways, the symbol on the left and the CMOS switches that do the work on the right, and reuses the symbol from there on.
Chapter 1, Figure 1.5 See also Logic gate; Abstraction and implementation; Inversion bubble
A latch with a single data input d and an enable input. While enable is HIGH the latch is transparent and Q follows d; while enable is LOW, Q ignores d and holds its last value.
Chapter 4, Figure 4.3 See also Clock; D flip-flop; Enable; Transparent latch; Opaque latch; Master-slave flip-flop
The fixed divisor of a CRC. The whole message is treated as one enormous binary number and divided by it, bit by bit: whenever the leading bit of the 16-bit register is 1, the register is shifted and the polynomial subtracted, which modulo 2 is an XOR. What is left after the whole message is the checksum.
Chapter 10 See also CRC; XOR; CRC-16/CCITT-FALSE
The one table a linker builds from the exports of every object, giving each symbol its final address in the image. An assembler's symbol table serves a single file; this one spans all the modules. For the book's two modules it maps value to 5, addend to 6 and result to 4.
Chapter 6.a, Figure 6.a.3 Try it See also Symbol table; Symbol; Imports and exports; Linker; Undefined symbol
The rules that define a language's syntax, one per kind of phrase. The book's imperative language needs seven, from program, a list of statements, down to atom, a number, a name or a parenthesized expression; its recursive-descent parser has one method per rule.
Chapter 8 See also Syntax; Recursive descent; Grammar rule; Syntax error
One line of a grammar: it names a kind of phrase and says what it may be made of. The book's rule for a loop is while, an expression, do, a list of statements and end. Its recursive-descent parser has one method per rule, so a rule that mentions another becomes a method that calls another.
Chapter 8 See also Grammar; Recursive descent; Syntax; Term (of an expression); Look-ahead
A set of nodes joined by edges. Strip a circuit to its essentials and it is one: gates are nodes, and the wires between them are edges. Writing that graph down gives a netlist, so the chapter's drawing of XOR and its list of gate records are the same circuit, written two ways.
Chapter 5.a, Figure 5.a.2 See also Node and edge; Netlist; Network graph; Control-flow graph; Gate record
Which operands of an expression belong together. Parentheses state it in the text and the tree makes it explicit: in (a + b) + c the inner a + b is one child of the outer addition. Without parentheses the book's parser groups addition left to right, so a + b + c builds the same tree.
Chapter 7, Figure 7.2 Try it See also Abstract syntax tree; Associativity; Sub-expression; Precedence; Nesting
The simplest binary adder. It takes two single bits and returns a sum and a carry; the sum is their XOR and the carry is their AND.
Chapter 3, Figure 3.2 See also Carry; Full adder; XOR; Combinational logic; Intermediate sum and carry; Sum bit
The instruction that stops the book's CPU, opcode 0. The fetch-decode-execute loop runs until a HALT executes; it sets the halted flag, and after that a step does nothing. The example program ends with one at address 4, stored as the word 0.
Chapter 5 Try it See also Halted flag; Instruction set; Fetch-decode-execute cycle
The one bit of the book's CPU state that records that the machine has stopped. It starts false; executing HALT sets it, and from then on a step returns without fetching anything. The run() method returns normally only once it is set.
Writing a program as machine words yourself, working out every opcode and address. The book's CPU chapter did it with calls like program[0] = encode(LOAD, 13). The numbers are correct but fragile: insert one instruction near the top and every address below it shifts by one. An assembler takes over that bookkeeping.
Chapter 6 See also Assembler; Machine code; Opcode and operand
The kernel routine that carries out one kind of request. The book's kernel keeps a table of three, for WRITE, READ and GETPID; the matching one runs in the kernel's privileged mode, and its result is what the program gets back. The write routine appends its argument to the output and returns 0.
Chapter 9.a, Figure 9.a.3 See also Menu of services; Dispatch; Kernel; Page fault; Return value
The opening exchange in which two ends set up a secure channel before any message is protected. In the book's, each side sends one public value and both derive the same secret. A real TLS handshake must also authenticate the peer, and it checks a transcript of the exchange before accepting it.
Chapter 13.a, Figure 13.a.2 Try it See also Diffie-Hellman key exchange; Peer authentication; TLS; Handshake signature; Certificate
A value computed over the handshake with a private key, which the other side verifies to confirm who took part. In a typical web TLS connection the client validates a certificate for the expected server name and verifies a handshake signature made with the corresponding private key. The book's code deliberately leaves this step out.
Chapter 13.a See also Certificate; Peer authentication; Handshake; TLS
The physical machine: transistors, gates, wires and chips, as opposed to the programs and data loaded into them. Until the FPGA chapter every circuit in the book was wired in place; an FPGA's hardware is generic and its circuit is loaded, which gives it hardware speed with software's ability to be reloaded.
Chapter 5.d See also Software; FPGA; Fixed silicon; Transistor
A language for writing a circuit down as source text, since circuits with billions of transistors are never wired by hand. Verilog is one; tools compile its source into a netlist of gates and wires, which a simulator can test long before the chip is built in silicon.
Chapter 5.a See also Netlist; Circuit simulator; Verilog; Toolchain
The condition that lets an overlapped pipeline give the same result as running its instructions one at a time: no instruction reads an operand before the instruction that produces it has computed it. The book's checker calls a schedule safe when every read comes strictly later than the execute that writes the register.
Chapter 5.b See also Data hazard; Stall; Pipeline schedule; Sequential execution; Timing model
The region of memory that serves a program as it asks for some, uses it and gives it back, in sizes and at moments it cannot predict. In the book's sixteen-cell model, three requests of four carve blocks a, b and c off the front; freeing a then leaves a hole at the start that the allocator must reuse.
Chapter 9.b, Figure 9.b.2 Try it See also Memory allocator; Free list; Coalescing; Heap fragmentation; Live block; Malloc and free
The breaking of free memory into small separate holes as blocks come back in any order, so a request can fail even though the room exists. Left unmerged, the book's freed runs (0, 4) and (4, 4) would stay two holes and refuse a request for eight cells; coalescing undoes the fragmentation that freeing creates.
Chapter 9.b See also Coalescing; Heap; Allocation failure; Best fit; Heap hole; Placement policy
A free run left among live blocks when a block comes back out of order. In the book's run, freeing a leaves a hole at 0 while b and c stay in use; freeing b, whose run touches the hole, merges the two. The allocator must reuse holes, or the heap fills with gaps and can satisfy nothing.
Chapter 9.b, Figure 9.b.2 Try it See also Free run; Coalescing; Heap fragmentation
A language more abstract than assembly: a program says what to compute and leaves the choice of instructions to a translator. The book's arithmetic language is one level up, so the single line (a + b) + c stands for a program that loads a, adds b, adds c and stores the result.
Chapter 7 See also Assembly language; Compiler; Interpreter; Expression language
The fraction of a cache's accesses that hit. Every access pays the fast hit time and the misses also pay the slow miss penalty, so when that penalty is a hundred times the hit, even a small miss rate dominates the average.
Chapter 5.c Try it See also Cache; Locality; Hit time; Average access time; Cache hit and miss; Memory hierarchy
The cost of a cache access that hits, and a cost every access pays, hit or miss. The book's model sets it to one cycle, so a program that always hit would average exactly one cycle an access; anything above that is the work of the miss penalty.
Chapter 5.c Try it See also Average access time; Miss penalty; Hit rate
What an SR latch does while S and R are both LOW: each gate's output holds the other gate's input, so both outputs stay at their last value. The chapter calls it the point of the circuit: the latch sits in one of two stable states, exactly one bit of memory.
Chapter 4, Figure 4.2 Try it See also SR latch; Set and reset; State; Feedback
A bond left unfilled in doped silicon. An element with three outer electrons, such as boron, cannot complete the fourth bond a silicon atom would, and the gap behaves like a mobile positive charge. Silicon whose current is carried by holes is p-type.
Chapter 1, Figure 1.2 Try it See also Doping; n-type and p-type; Electron; Charge carrier
One crossing of a single link, from a machine to its neighbour. The book's network treats every link as one hop, so the shortest route is the one with the fewest links; a real network weighs its links by speed or cost instead. The route from A to F is three hops.
Chapter 11 Try it See also Network graph; Breadth-first search; Hop count; Link; Neighbour; Route
The number of links on a route, and so the distance between two machines when every link counts as one hop. The book's breadth-first search records it as it goes: each newly reached node is one hop farther than the node it was reached from. From A to F the count is 3.
Chapter 11 See also Hop; Breadth-first search; Shortest path
The protocol the web is made of. The book builds the text shape of HTTP/1.x, requests and responses that share one layout of start line, headers, blank line and body, as in GET /hello HTTP/1.0. HTTP/2 uses binary framing instead, so the wire form is not universal.
Chapter 13, Figure 13.2 Try it See also Request and response; Protocol; HTTP method; HTTP version; Client and server; Web server
A name and value pair in the head of an HTTP message, after the start line and before the blank line that ends the head. The book's messages carry Content-Length; a real web server adds headers that negotiate format and caching.
Chapter 13, Figure 13.2 See also Content-Length; Request and response; Message body; Message head
The word that opens a request's start line and says what the client wants done with the path. The book's client uses only GET, which asks for whatever the server holds at a path, as in GET /hello; a real web server accepts methods beyond fetching.
Chapter 13, Figure 13.2 Try it See also Start line; Request and response; HTTP; Request path
The label in a start line that says which form of HTTP a message is written in. HTTP/1.0 closes the book's request line, GET /hello HTTP/1.0, and opens its reply, HTTP/1.0 200 OK. The chapter's messages have the text shape of HTTP/1.x; HTTP/2 uses binary framing instead.
Chapter 13, Figure 13.2 See also Start line; HTTP; Wire representation
A language whose programs keep state, do one thing after another, and repeat; those three turn a calculator into a language. The book's tiny one, with assignment, addition, a comparison and while, multiplies 6 by 7 by adding 6 seven times, though neither it nor the machine has a multiply.
Chapter 8 Try it See also Statement; Control flow; Semantics; Expressiveness; Programming language; Sequencing
The two lists an object carries for the linker. An export is a label the module defines, offered to others; an import is a position whose operand names a label defined elsewhere, left blank. The book's main module imports value and addend, which the data module exports.
Chapter 6.a, Figure 6.a.2 Try it See also Object file; Relocation; Module; Global symbol table; Undefined symbol; Symbol
Said of an instruction that has entered a pipeline and has not yet finished its last stage. Once the book's three-stage pipeline fills, three instructions are always in flight and one finishes every cycle; the figure lights cycle three, where three of its four instructions overlap.
Chapter 5.b, Figure 5.b.2 Try it See also Pipeline; Pipeline stage; Clock cycle
Sent as plain bytes with no protection, so that anyone sitting on the wire between the two machines can read them. Every message in the book before this chapter crosses the network this way, the protocol chapter's request included. A secure channel must protect the bytes and establish who is at the other end.
Chapter 13.a See also Secure channel; Passive observer; Encryption and decryption
Instructions none of which reads a value that another of them writes, so a pipeline can overlap them without waiting. The book's figure shows four: each runs its stages one cycle behind the instruction above it, and all four finish in six cycles with no stall.
Chapter 5.b, Figure 5.b.2 Try it See also Dependent chain; Pipeline; Data hazard
An allocation scheme in which a file's blocks are found through a list of their numbers, rather than by following a link from each block to the next. The chapter only names it, beside runs of adjacent blocks, as something filesystems can use in place of the chain the book builds.
Chapter 9.d See also Allocation scheme; Linked allocation; File allocation table
The wires on which a part receives its values, and the wire on which it delivers its result. In the CMOS inverter a single input a drives both transistor gates and the output is its opposite; the NAND has two inputs, a and b, and one output.
Chapter 1, Figure 1.4 Try it See also Signal; Drive; Logic gate; Truth table
One step of a program, as the CPU reads it from memory: a word that names an operation and a memory address. The CPU fetches it, decodes the two fields, carries out the operation, and returns for the next. In the book's machine ADD 14 adds the value at address 14 to the accumulator.
Chapter 5, Figure 5.2 Try it See also Instruction set; Opcode and operand; Fetch-decode-execute cycle; Program
The part of a CPU that splits a fetched instruction word into its fields. The book's decode expands the 8-bit word into bits and reads the two nibbles: the high one is the opcode, which goes to the control unit, and the low one is the operand, which selects a memory address.
Chapter 5, Figure 5.2 See also Opcode and operand; Instruction encoding; Control unit; Address decoder; Unused opcode
The rule that packs an instruction into bits. The book's encode puts a 4-bit opcode in the high nibble and a 4-bit address in the low nibble of one 8-bit word, so LOAD 13 becomes 0001 1101, the number 29. A data cell is not encoded: it holds its value as is.
Chapter 5, Figure 5.2 See also Opcode and operand; Instruction decoder; Instruction set; Machine code
The contract between software and hardware: it names every operation a CPU can perform and specifies how each instruction is encoded. The book's CPU has six opcodes, enough to compute, store results and branch.
Chapter 5, Figure 5.2 See also Opcode and operand; Instruction; Accumulator machine; HALT; Instruction encoding; LOAD
Division of whole numbers that stops at a whole quotient and reports what is left over as a remainder, with no fraction. The chapter's run divides 13 by 3 and prints quotient 4, remainder 1. Real processors also divide fractions; the chapter keeps to the integer idea.
Chapter 3.a See also Quotient and remainder; Divider; Dividend and divisor
The assurance that a message is exactly what its sender wrote, with any change on the way detected. The book's record falls short of it: a mismatched checksum rejects the record, but many different records share a one-byte checksum, so a matching tag establishes neither cryptographic integrity nor the sender's identity.
Chapter 13.a See also Keyed checksum; Tampering; Encrypted record; Peer authentication
The mixing of several programs' steps on one processor, a few from one and then a few from another. With a quantum of three steps the book's two programs interleave as adder, pair, adder, pair, and it changes nothing about either answer: the accumulators still hold 42 and 9.
Chapter 9, Figure 9.3 Try it See also Time-sharing; Time slice; Transparency
An attacker in the middle who replaces messages instead of only watching them. In the chapter's example an intermediary swaps both public values for its own, computed from private exponent 9: Alice derives 1493771129, Bob derives 849309108, and the intermediary derives both keys, so it can read each message and encrypt it again unnoticed.
Chapter 13.a See also Peer authentication; Passive observer; Public value; Certificate; Tampering; Alice and Bob
The values a full adder passes between its two half adders. The first adds a and b, giving an intermediate sum and a carry; the second adds that sum to the carry-in and may give a second carry. At most one of the two carries can be 1, so a simple OR merges them.
Chapter 3, Figure 3.3 See also Full adder; Half adder; Carry
The worldwide network of networks. The chapter describes it as billions of machines joined by many local links, not a single shared wire that every machine can hear, so a message from here to anywhere crosses a chain of intermediate machines, each passing it one step closer. The book studies the problem on six machines.
Chapter 11 See also Network; Routing; Router; Shared link
A program that runs a program: it reads the new language and computes its meaning directly. The book's interpreter is one recursive function that walks the tree of (a + b) + c, evaluating each node and wrapping every sum at 256, and returns 42 without producing any machine code.
Chapter 7, Figure 7.3 Try it See also Compiler; Abstract syntax tree; Tree walk; Evaluation; Bytecode; Variable environment
A small circle drawn on a gate symbol's input to stand for a NOT. Bubbles on both inputs of a NAND draw an OR gate, and an OR with bubbled inputs is the same gate as a NAND, as De Morgan's first law says.
Chapter 2, Figure 2.2 See also De Morgan's laws; NAND; Gate symbol; Equivalence
The simplest CMOS gate: it outputs the opposite of its input. When the input is LOW the p-channel pull-up drives the output HIGH; when the input is HIGH the n-channel pull-down drives it LOW.
Chapter 1, Figure 1.4 Try it See also CMOS; AND, OR and NOT; LOW and HIGH; Signal restoration; Tied inputs
A real network-layer address, the kind used by version 4 of the Internet Protocol. The book writes none out: its letters A through F are readable stand-ins for such addresses, here and in the routing chapter. They are not host names such as example.com, which DNS resolves later.
Chapter 10.b See also Network address; Network layer; Link address
A real chip-testing protocol, named after the Joint Test Action Group. The chapter names it beside SPI as having the shape of its bit-banged link, in which a clock and a data line driven by hand carry bits across one at a time.
Chapter 10.a See also Bit-banging; SPI; Clock line
The unconditional branch of the book's CPU, opcode 4: it sets the program counter to its operand, so the next fetch starts there. The counter has already advanced by the time an instruction executes, so JUMP overwrites the already-incremented value with the branch target.
Chapter 5 See also Branch; JZ; Branch target; Program counter
Branch on zero, opcode 5 of the book's CPU: it sets the program counter to its operand only if the accumulator is 0, and otherwise lets the next instruction follow. The control unit decides from a zero test of the accumulator. It is the machine's only conditional instruction.
Chapter 5 See also Branch; JUMP; Zero test; Conditional jump; Branch target
The privileged core of the operating system, which holds the resources and enforces protection. A program cannot reach the disk, the network or another program's memory on its own; it asks, and the book's kernel checks each request number against a menu of three services: write a value, read one, and report the program's id.
Chapter 9.a, Figure 9.a.2 See also System call; User mode and kernel mode; Operating system; Privilege; Protection; Resource
A secret value that encryption depends on, so that only someone who holds it can undo the encryption. In the book's toy record the shared secret keys the keystream at both ends, as four repeating key bytes. In the intermediary example Alice and Bob each end up with a different key, and the intermediary holds both.
Chapter 13.a, Figure 13.a.3 See also Shared secret; Keystream; Key derivation; Encryption and decryption; Pre-shared key
The job of getting two ends to hold the same secret without ever sending it. The book models it with a Diffie-Hellman exchange in which both sides reach 1893334806. Agreement is only one job of a secure channel: it does not identify the other endpoint, and whether the secret stays hidden is a separate computational claim.
Chapter 13.a, Figure 13.a.2 Try it See also Diffie-Hellman key exchange; Shared secret; Peer authentication; Key derivation; Secure channel; Secrecy
Turning the secret that two ends agreed on into the key bytes that protect their records. The book's toy derives a repeating keystream of four key bytes from the shared secret, one of the things that prevent it from being a secure channel; real TLS combines suitable key agreement and key derivation.
Chapter 13.a See also Key; Shared secret; Keystream; TLS; Key agreement
A checksum that depends on a secret as well as on the message, so that only a holder of the secret should be able to produce a matching one. The book's toy record carries a one-byte keyed checksum, checked before decoding; many records share one byte, so a match establishes neither integrity nor the sender's identity.
Chapter 13.a, Figure 13.a.3 See also Encrypted record; Checksum; Shared secret; Integrity; Tampering
A run of key bytes XORed with a message to encrypt it; XORing the same keystream again recovers the message. The book derives its keystream from the shared secret as four repeating key bytes, one of the reasons its toy record is not a secure channel.
Chapter 13.a, Figure 13.a.3 See also Encrypted record; XOR; Key; Shared secret; Cipher; Ciphertext
The three levels of cache a real processor places between its registers and main memory, each trading size for distance. The book's ladder prices them at 4, 12 and 40 cycles, against 1 for a register and 400 for main memory: on your desk, across the room and down the hall.
Chapter 5.c, Figure 5.c.2 See also Cache; Memory hierarchy; Main memory
The wait between presenting inputs and having a valid result. It is the cost of the ripple-carry design: before bit position k can produce a valid carry, every stage to its right must have settled, so the wait grows with the adder's width.
Chapter 3, Figure 3.4 Try it See also Critical path; Propagation delay; Carry chain; Carry-lookahead adder; Settling
One level in the design of a network, which builds on the level beneath it and offers something more usable to the level above. The book builds its network one layer at a time from the bottom: the physical layer moves raw bits, and the link layer turns that unmarked stream into frames and makes corruption visible.
Chapter 10 See also Physical layer; Data link layer; Network layer; Transport layer
Putting off giving a page real memory until the program first touches it. The chapter lists it among the valid work a real page fault can ask the kernel to complete: the handler supplies the missing mapping and resumes execution. The book's model does nothing lazily; an absent entry simply raises an exception.
Chapter 9.c See also Page fault; Page mapping; Kernel
The two ends of a binary numeral, whose places are worth 1, 2, 4, 8 and so on from the right. The least significant bit is bit 0, the rightmost, worth one; the most significant bit is the leftmost occupied place.
Chapter 3, Figure 3.4 Try it See also Ripple-carry adder; Binary numeral; Bit list; Bit position; Weight (of a place); Bit order
Moving every bit of a number one place to the left, towards the more significant end, which leaves the lowest bit empty. Each step of binary long division shifts its running remainder left and drops the next dividend bit into that empty low bit, the binary form of bringing down the next digit.
Chapter 3.a See also Binary long division; Running remainder; Bring down
A rank of gates that all sit the same number of gates away from the inputs, so a signal crosses one gate per level. The chapter's XOR is four NANDs in three levels: a shared NAND, two NANDs combining it with each input, then an output NAND.
Chapter 2, Figure 2.3 Try it See also Gate network; XOR; Propagation delay
The first stage of every compiler and interpreter: it scans flat source text left to right and cuts it into tokens. Its one subtlety is grouping, so a run of digits such as 12 becomes one number and total one name; a character that begins no token, such as ?, is rejected.
Chapter 6.b, Figure 6.b.2 Try it See also Token; Compiler front end; Scanning; Character; Parser; Unexpected character
Ready-made code that someone else wrote, joined to a program when it is linked. The chapter names libraries as part of why a real program is not one file: its pieces are written and assembled separately, then joined at the end. The book's own example links two modules and no library.
Chapter 6.a See also Linker; Module; Object file
The number that names the cache line an address belongs to: the address divided by the line size, remainder dropped. With the book's eight words per line, addresses 0, 32, 64 and 96 fall in lines 0, 4, 8 and 12. The line number then chooses the slot; in a four-slot cache all four of those land in slot 0.
Chapter 5.c See also Cache line; Cache slot; Direct-mapped cache
A direct connection between two machines, across which one can send to the other without help from a third. In the book's network graph every link is an edge and counts as one hop. A has links to B and C only, so a message from A to F must cross intermediate machines.
Chapter 11, Figure 11.2 See also Hop; Network graph; Shared link; Wire; Link cost; Network
The address that names one interface on a local link, so that a frame can say which interface should receive it. On Ethernet it is commonly called a MAC address, and the chapter's captions also call it a hardware address. The book's link addresses are abbreviated labels such as 02:00:00:0b.
Chapter 10.b, Figure 10.b.3 Try it See also MAC address; Network address; Address resolution; Network interface; Addressed frame; IPv4 address
A weight given to a link, such as its speed or its cost, so that routes can be compared by more than their number of links. A real network weighs its links this way and its shortest route is the cheapest one; the book treats every link as one hop, which keeps the search in its simplest correct form.
Chapter 11 See also Shortest path; Hop; Link
The order in which objects are handed to the linker, which decides where each one lands in the image. The book's linker resolves a module's own labels as local addresses, correct only at the start of the image, so the main module is linked first; a real linker relocates every reference by wherever its module lands.
Chapter 6.a Try it See also Memory layout; Local address; Linker
A message wrapped for the wire so the receiver can find its boundaries in an unmarked stream of bytes: a chosen FLAG byte opens and closes it, with the payload and a two-byte CRC between. Framing the payload hi gives the six bytes 7e 68 69 62 03 7e.
Chapter 10, Figure 10.3 Try it See also Byte stuffing; CRC; Framing; Payload; Flag byte; Checksum
Storing a file as a chain: its bytes are cut into block-size pieces, dropped wherever there is room, and a table records which block holds the next piece. The book's writer takes free blocks earliest first, so long chains 0 to 2 to 3 to 4 around another file's block, yet reads back whole.
Chapter 9.d, Figure 9.d.2 Try it See also Disk block; File allocation table; Directory; Allocation scheme; Chain of blocks; Contiguous blocks
The single runnable block of machine words a linker builds from its objects, with every blank filled. The book's has seven words, 21, 54, 36, 0, 0, 7 and 35: five from main, then the two data values. Addresses must fit the machine's 4-bit operand, so an image holds at most sixteen words.
Chapter 6.a, Figure 6.a.2 Try it See also Linker; Memory layout; Machine code
The program that joins separately assembled objects into one runnable image. It lays them out in memory one after another, which fixes every exported label's address, then fills each import's blank. The book links a code module and a data module, and the image is byte for byte what assembling one file would give.
Chapter 6.a, Figure 6.a.2 Try it See also Object file; Relocation; Assembler; Linked image; Global symbol table; Link order
A value written directly in the program text, such as the 1 in 255 + 1, as opposed to a variable, whose value comes from the environment. The book's first language allows integer literals from 0 to 255, and its compiler gives each one a data cell with a name like _lit42.
Chapter 7 Try it See also Variable; Unsigned byte; Literal operand
An operand that is the value itself, not the place where a value is kept. On the book's toy CPU every operand is an address. The idealised machine of this chapter lets LOAD carry a literal value, so LOAD 0 puts 0 in the accumulator while LOAD b still reads memory.
Chapter 8.a Try it See also Opcode and operand; Literal; Target machine; Named memory
A run of memory the allocator has handed out and not yet taken back. The book's Heap keeps a map of them, from each start address to its length, beside the free list; after three requests of four cells its live blocks a, b and c start at 0, 4 and 8.
Chapter 9.b, Figure 9.b.2 Try it See also Heap; Memory allocator; Free run; Address range
The instruction that copies a memory word into the accumulator, opcode 1. The loaded word bypasses the adder and replaces what the accumulator held, so loading 1 and then 2 leaves 2, not 3. The example program opens with LOAD 13, which puts the 10 stored at address 13 into the accumulator.
Chapter 5 Try it See also STORE; Accumulator; Instruction set; Memory address; ADD
The control input, shared by every bit, that tells a register whether to take a new word. When load is HIGH, the next rising edge captures the data word; when load is LOW, each flip-flop feeds its own output back and the word holds. A RAM write asserts only the selected register's load line.
Chapter 4, Figure 4.5 Try it See also Register; Capture; Enable; Write line; Assert
The part of a system that copies a program's bytes from storage into memory before it executes. The book builds none: its shell's commands are already resident, which lets the chapter follow command dispatch on its own. A real shell asks the operating system to load executable programs.
Chapter 9.e See also Executable file; Process creation; Resident program; Shell
An address counted from the start of a module's own code, before the linker has placed that module. The book's assembler resolves a label the module itself defines to a local address at once: main exports result at 4, so its STORE 4 is complete before any linking.
Chapter 6.a, Figure 6.a.2 Try it See also Base address; Assembly label; Link order; Symbol resolution
The predictability that makes caches work. A word just used is likely to be used again soon (temporal locality), and the words next to it are likely to be used soon after (spatial locality).
Chapter 5.c, Figure 5.c.3 See also Cache; Spatial locality; Temporal locality; Address trace; Hit rate
A small circuit of switches whose output bit is fixed by its input bits, the next unit up from the transistor. The first the book builds is NAND, from two n-channel and two p-channel switches. Not to be confused with a transistor's gate, the terminal that controls one switch.
Chapter 1, Figure 1.5 Try it See also NAND; Gate symbol; AND, OR and NOT; Truth table; Circuit; Input and output
Peeking at the next token without consuming it, to decide which grammar rule applies. The book's statement parser needs a single look-ahead: a statement that begins with while is a loop, and anything else is an assignment. The same peek tells a loop's body where to stop, at the matching end.
Chapter 8 See also Recursive descent; Parser; Token; Grammar rule
The book's toy server: a function that answers a request by looking its path up in a table of paths and the bytes each one serves. Whether the path is known is the whole decision: a known path is answered 200 OK with its bytes, and an unknown one falls through to 404 Not Found.
Chapter 13, Figure 13.3 Try it See also Client and server; Request handler; Request path; Web server
The block at the heart of an FPGA: a small stored table indexed by its inputs, one entry per input combination, so loading NAND's four entries makes a two-input block a NAND gate. It is a tiny RAM whose inputs are the address.
Chapter 5.d, Figure 5.d.3 Try it See also FPGA; RAM; Table index; Bitstream; Configurable logic block; Configuration bit
A statement that runs a block again and again while a condition holds. The book's is while expr do ... end: the condition i < b is tested before each pass, the body adds a to product and advances i, and the loop ends when the test yields 0. With inputs 6 and 7, seven passes leave 42.
Chapter 8, Figure 8.3 Try it See also Control flow; Statement; Conditional jump; Loop body; Loop condition; Loop counter
The block of statements a loop repeats. In the book's language it is the list of statements between do and the matching end; the example loop's body is two assignments, product = product + a and i = i + 1. Because a body is read as ordinary statements, loops nest inside loops.
Chapter 8, Figure 8.2 Try it See also Loop; Loop condition; Statement; Nesting; Loop pass
The expression a loop evaluates before every pass to decide whether its body runs again. In the book's language a nonzero value means carry on and zero means stop, the same test the CPU's JZ performs. The example's condition is i < b, and in the tree it belongs to the While node.
Chapter 8, Figure 8.2 Try it See also Loop; Comparison expression; Loop body; Conditional jump; Loop counter; Nonterminating loop
A variable that keeps track of how far a loop has got. In the book's multiplication loop it is i: it starts at 0, each pass advances it by 1, and when it reaches b the comparison becomes zero and the loop ends. The next chapter's version counts down from b to zero instead.
Chapter 8 Try it See also Loop; Loop pass; Loop condition; Countdown loop
One trip through a loop: the condition is tested and, if it is nonzero, the body runs once. The book calls each trip a pass, where many texts say iteration. With a as 6 and b as 7, its multiplication loop makes seven passes, each adding 6 to product.
Chapter 8, Figure 8.3 Try it See also Loop; Loop body; Loop counter; Repeated addition
The book's stand-in for an unreliable network: whatever carries the sender's segments toward the receiver and may drop or reorder them. The example channel drops the even-numbered segments on their first try, delivers the odd ones reordered, never duplicates, and delivers a lost segment on its second attempt.
Chapter 12, Figure 12.3 Try it See also Packet loss; Reordering; Best-effort delivery; Delivery round
The two voltage bands a wire is read as, called exactly 0 and 1. A voltage that drifts into the low band is snapped back to a clean 0, and one in the high band to a clean 1: gates drive their settled output towards a rail, restoring signals as long as noise stays within the bands.
Chapter 1, Figure 1.4 See also Bit; Inverter; Noise; Rail; Signal; Voltage
Rewriting a construct of the source language in the simpler terms of the machine below it. A processor has no idea what a loop is, so the compiler lowers while to a test and two jumps. The book's compiler lowers only addition and a loop tested against zero; a comparison such as i < b would need more cases.
Chapter 8.a, Figure 8.a.2 Try it See also Code generation; Compiler; Target machine; Control flow
The link address of a network interface, which a frame on a shared local link names to say which interface should receive it. Ethernet MAC addresses have six octets; the book abbreviates them to four, as in 02:00:00:0b. They can be assigned or locally configured, so they are not necessarily fixed in hardware.
Chapter 10.b, Figure 10.b.3 Try it See also Network address; ARP; Ethernet; Link address; Network interface; Octet
The words a CPU actually executes, and the assembler's output. Each instruction becomes one 8-bit word of opcode and operand nibbles, so JUMP start becomes 0100 0101, or 69, while a DATA line becomes one raw byte holding its value.
Chapter 6, Figure 6.3 Try it See also Assembler; Opcode and operand; Instruction encoding; Hand encoding; Source code; Bytecode
The large working memory of a computer, as distinct from the CPU's own registers and caches. It is usually DRAM, whose small cells let a chip hold far more bits. In the memory hierarchy it sits beyond the SRAM caches, larger but slower, with storage larger still.
Chapter 4 See also SRAM and DRAM; Memory hierarchy; Refresh; RAM; Bandwidth; L1, L2 and L3 caches
The usual names of an allocator's two library routines: malloc hands out a block of the size asked for and returns its start address, and free takes a block back. In the book's run, malloc(4) three times returns 0, 4 and 8, and freeing all three leaves the single run [(0, 16)].
Chapter 9.b, Figure 9.b.2 Try it See also Memory allocator; Heap; Free list
A fixed pattern of bits combined with a value to change or pick out chosen bits. The book's byte stuffing masks each escaped byte with 20 by XOR, which flips one bit, so 7e becomes 5e and 7d becomes 5d; the receiver undoes the flip when it un-stuffs the frame.
Chapter 10, Figure 10.3 Try it See also XOR; Byte stuffing; Escape byte
Two gated D latches in series on opposite clock phases, the arrangement that makes a D flip-flop. The master is transparent while the clock is LOW and the slave while it is HIGH. At the rising edge the master closes, locking in the last d, and the slave opens to present it as Q.
Chapter 4, Figure 4.3 See also D flip-flop; Gated D latch; Rising edge; Clock phase; Opaque latch
A circuit that keeps what was written to it: a stored bit survives after the signal that wrote it changes. No combinational circuit can do this, so the chapter builds memory from feedback: one bit in a latch, then a word in a register, then a small RAM of four words.
The number that picks one word out of a memory. The chapter's four-word RAM takes two address bits, a1 and a0, and its decoder raises the one select line they name. To read or write a word you supply its address; large memories split the address into a row and a column.
Chapter 4, Figure 4.6 Try it See also RAM; Address decoder; Select line; Memory cell; Write line; Address space
The heap's bookkeeper, usually library routines inside the process such as malloc and free. It subdivides memory already obtained from the operating system, so each small allocation or release need not make a system call; the book's Heap tracks address ranges rather than the bytes in them.
Chapter 9.b, Figure 9.b.2 Try it See also Heap; Free list; First fit; Malloc and free; Placement policy; Live block
One addressable slot of memory, holding one word. The book's CPU has sixteen: its example program fills cells 0 to 4 with instructions and keeps a result slot and three data cells at 12 to 15. In a memory chip a cell is smaller, the store for a single bit, as in an SRAM or DRAM cell.
Chapter 5, Figure 5.5 Try it See also Memory word; RAM; SRAM and DRAM; Memory address; Byte; Data cell
The part of a memory system that manages its DRAM. Because the charge in a DRAM cell leaks, the controller must periodically refresh rows before the stored values fade. The chapter's small RAM needs none: like SRAM, it holds each bit by feedback for as long as power remains.
Chapter 4 See also Refresh; SRAM and DRAM; Capacitor; Row buffer
The several memories a machine uses at once, since no single memory can be both large and close: a small, fast one right beside the core, backed by larger, slower ones further out. Each level trades size for distance.
Chapter 5.c, Figure 5.c.2 Try it See also Cache; Hit rate; L1, L2 and L3 caches; Main memory; SSD; Bandwidth
The whole contents of a memory at one moment. The chapter draws the image its example program builds, just before the first cycle: instruction words at addresses 0 to 4, zeros between, the result slot at 12 and data at 13 to 15. Program and data are the same kind of thing, words in one memory.
Chapter 5, Figure 5.5 Try it See also Stored program; Program; Memory cell; Address space
Keeping each program's memory out of every other's reach. With trusted tables mapping to disjoint frames, programs A and B both write virtual address 3, yet A's value lands at physical 83 and B's at physical 131; if a caller remapped A's page to B's frame, translation alone would not stop A reading B's 99.
Chapter 9.c, Figure 9.c.3 Try it See also Virtual memory; Page table; Disjoint frames; Address collision; Shared frame; Protection
The linker's first job: placing the objects in memory one after another, which finally fixes the address of every exported label. Relocation can only follow it. In the book main takes addresses 0 to 4 and the data module the next two, so value and addend land at 5 and 6.
Chapter 6.a, Figure 6.a.2 Try it See also Linker; Base address; Linked image; Relocation; Link order
A stretch of memory handled as one piece. Kernel requests acquire or release larger regions as needed, and the allocator subdivides what it already holds, so each small allocation need not make a system call. The region managed this way is the heap; the book's is one fixed region of sixteen cells, with no kernel calls.
Chapter 9.b See also Heap; Memory allocator; System call
A fixed group of bits stored and moved as one unit. A register holds one word, one flip-flop per bit, and its shared clock makes all the bits change together; the chapter's register holds a 4-bit word, and its RAM holds four words of equal width, picked by address.
Chapter 4, Figure 4.5 Try it See also Register; RAM; Bit; Bus; Byte; Memory cell
The small, fixed list of things a kernel will do for a program, each service a number the program names. The book's menu has three: write a value out, read one in, and report the program's own id. The program strings these together to get its work done, never touching the resources behind them.
Chapter 9.a, Figure 9.a.3 See also Kernel; Request number; Handler; System call; Dispatch; Process id
A run of bytes that one machine means another to receive as a whole. A wire delivers only an unbroken stream, so the link layer must mark where one message ends and the next begins. The chapter's run sends two messages, the first the two letters hi, and both come back exactly as sent.
Chapter 10 Try it See also Payload; Link-layer frame; Byte stream; Packet
The content an HTTP message carries, after the blank line that ends its head. Its length is written in the Content-Length header, since a body may hold a blank line of its own. The book's reply carries 23 bytes of body, the text Hello from the server.; its request, with Content-Length: 0, carries none.
Chapter 13, Figure 13.2 Try it See also Content-Length; HTTP header; Request and response; Blank line; Message framing; Message head
Writing a message's parts out as the bytes that travel, the opposite of parsing. The book's client encodes a request for /hello as the lines GET /hello HTTP/1.0 and Content-Length: 0 followed by a blank line; the server encodes its reply in the same shape, beginning HTTP/1.0 200 OK.
Chapter 13, Figure 13.3 Try it See also Message parsing; Wire representation; Start line
Marking where a message ends inside a stream that never stops. The chapter's messages do it in two steps: a blank line ends the head, and Content-Length states the body's length, so the body is taken by count and not by searching for a delimiter. HTTP/2 uses binary framing instead.
Chapter 13 See also Content-Length; Blank line; Message body; Wire representation
Everything in a message before the blank line: the start line and the headers. The book's parser splits the head from the body at the blank line, takes the first line of the head as the start line, and reads every later line as a header, a name and value pair such as Content-Length: 23.
Chapter 13, Figure 13.2 See also Start line; HTTP header; Blank line; Message body; Message parsing
Turning a message's bytes back into its parts. The book's parser splits head from body at the blank line, reads the start line and headers, and takes the body by Content-Length. It raises an error if the separator is missing, the length is not a nonnegative decimal, or the body is too short.
Chapter 13 See also Message head; Content-Length; Message encoding
The two numbers of a subtraction: in a - b the minuend a is the one subtracted from, and the subtrahend b is the one taken away. The book's subtraction inverts every bit of the subtrahend, adds one, and adds the result to the minuend.
Chapter 3.a See also Two's complement; Fixed width; Signed and unsigned
The extra cost of a cache miss: the slow trip to fetch the line from memory further out, paid on top of the hit time. The book's model charges a hundred cycles against a one-cycle hit, so at 99 hits in a hundred the average access already costs two cycles, double the hit time.
Chapter 5.c Try it See also Average access time; Hit time; Cache hit and miss
The readable name of an operation in assembly, such as LOAD, ADD or JUMP. The assembler swaps it for its opcode, so JUMP becomes opcode 4, 0100; a mnemonic outside the instruction set is rejected in the second pass, not guessed at.
Chapter 6, Figure 6.3 Try it See also Opcode and operand; Assembly language; Directive
The hardware bit with which a real processor enforces the boundary between a program's restricted mode and the kernel's privileged one. The book has no such bit: its program holds a reference to the kernel object and is only meant to cross through the syscall, so nothing the machine does prevents a shortcut.
Chapter 9.a, Figure 9.a.2 See also User mode and kernel mode; Privilege; Trap
A simplified description of a real thing that keeps only what the question needs. The book's code is a binary model: a switch passes its signal only when its control is HIGH, and analog effects are left out. The truth tables it prints come from running that model, not from typing them in.
Chapter 1 See also Analog and digital; Truth table; Switch; Abstraction and implementation
Arithmetic with a remainder operation: 17 mod 5 = 2, since dividing 17 by 5 leaves 2. Working modulo a prime p keeps every result between 0 and p-1, even when the unreduced power is enormous: 515 is 30517578125, and modulo p = 2147483647 it is 452807067.
Chapter 13.a, Figure 13.a.2 Try it See also Diffie-Hellman key exchange; Base and modulus; Modular exponentiation; Private exponent
Raising a number to a power and keeping only the remainder after dividing by a modulus. Reducing intermediate results modulo p gives the same answer, so the enormous ordinary power never has to be built: Python's three-argument pow(g, a, p) computes ga mod p, which for Alice's exponent 6 is 15625.
Chapter 13.a, Figure 13.a.2 Try it See also Modular arithmetic; Public value; Private exponent; Base and modulus
One source file of a program, written and assembled on its own. It cannot know where in memory it will finally sit, or the address of a label defined in another file, so it is assembled into an object with blanks. The book links two: main, with the code, and data, with the values.
Chapter 6.a, Figure 6.a.2 Try it See also Object file; Imports and exports; Linker; Library
The metal-oxide-semiconductor field-effect transistor. A voltage on its gate forms a channel between source and drain, so it conducts only when told to.
Chapter 1, Figure 1.2 Try it See also Source, drain and gate; Channel; CMOS; Transistor; Field effect; n-channel and p-channel
A circuit that passes one of its data inputs to its output, chosen by a select line. A 2-to-1 multiplexer built from NOT, AND and OR is a two-way switch made of gates.
Chapter 3 See also ALU; Four-to-one multiplexer; Select line; Datapath
The values a running program keeps and can change. In the book's interpreter it is the environment, the dictionary of variable values: an assignment writes into it, which is what lets a later statement see an earlier one's work. State, sequencing and repetition are what separate a language from a calculator.
Chapter 8 Try it See also Assignment; Variable environment; Statement; State; Dictionary; Sequencing
The two flavours of the transistor switch. An n-channel device conducts when its gate is HIGH; a p-channel device is the mirror, conducting when its gate is LOW. CMOS gates use both: p-channel switches pull the output HIGH and n-channel switches pull it LOW.
Chapter 1, Figure 1.4 Try it See also MOSFET; CMOS; Pull-up and pull-down networks
The two kinds of doped silicon. In n-type silicon, spare electrons from an element such as phosphorus carry the current; in p-type, holes left by an element such as boron act as mobile positive charges.
Chapter 1, Figure 1.2 Try it See also Doping; Channel; Hole; Body and wells; Charge carrier; Semiconductor
Memory whose cells are found by name, not by numeric address. The book's code generator keeps variables and labels as names, the form assembly takes before a linker places it, and its jump-driven machine holds them in a table that starts as the input environment. Such memory is unbounded, unlike the toy CPU's sixteen words.
Chapter 8.a Try it See also Target machine; Assembly label; Linker; Dictionary; Literal operand
The first gate the book builds: its output is LOW only when both inputs are HIGH. In CMOS it is two n-channel switches in series pulling the output LOW and two p-channel switches side by side pulling it HIGH.
Chapter 1, Figure 1.5 Try it See also Universal gate; Truth table; Switches in series; AND, OR and NOT; Inversion bubble; Logic gate
A machine one link away, which can be reached directly. In the book's network A has two neighbours, B and C, and D has three. A routing table names one neighbour for each destination, and breadth-first search visits the source's neighbours first, then their neighbours, and so on outward.
Chapter 11, Figure 11.2 See also Link; Next hop; Hop; Breadth-first search
One structure placed inside another of the same kind. In the book's first language parentheses group sub-expressions and groups can nest; a single recursive call in the parser lets expressions nest to any depth. In the next language a loop's body is read as ordinary statements, so loops nest inside loops with no extra machinery.
Chapter 7 Try it See also Sub-expression; Recursion; Recursive descent; Grouping; Loop body
A circuit written down as data: one record per gate, naming the wire it drives, its kind and the wires it reads. A simulator evaluates it in rounds, firing each gate once every wire it reads is known.
Chapter 5.a, Figure 5.a.2 Try it See also Gate record; Circuit simulator; Hardware description language; Verilog; Graph; Simulation round
A set of machines joined by links so that any of them can send messages to any other, including machines that share no direct link. The chapter's example network is six machines with addresses A through F; its run lists the links of each, beginning with A connects to B, C.
Chapter 11, Figure 11.2 Try it See also Network graph; Link; Internet; Node and edge
The address that says where a packet should eventually arrive, as distinct from the link address of an interface on the local wire. The book writes A to F as readable stand-ins for network-layer addresses such as IPv4 addresses; they are not host names such as example.com.
Chapter 10.b, Figure 10.b.3 Try it See also MAC address; Next hop; IPv4 address; Link address; Packet; Network interface
A network with the wires stripped away: machines are nodes, and a link between two machines is an edge. The book's example is six machines, A to F, arranged as two triangles joined by two links, so a message from A to F must cross intermediate machines.
Chapter 11, Figure 11.2 See also Hop; Routing; Link; Network; Topology; Graph
A machine's point of attachment to a link. On a shared local link an addressed frame must say which interface should receive it, so each interface has a link address, its MAC address. A machine can move or an interface can change, which is why a real ARP cache must revalidate or discard old answers.
Chapter 10.b, Figure 10.b.2 Try it See also MAC address; Broadcast; Network address; Link address; Shared link; Stale mapping
The layer above the link, concerned with where a packet should eventually arrive and not with which interface receives the next frame. Its addresses are the book's letters A through F, stand-ins for addresses such as IPv4 addresses. The chapter's figure calls it the routing layer and shows ARP turning its next-hop address into a link address.
Chapter 10.b, Figure 10.b.3 See also Layer; Network address; Routing; Data link layer; IPv4 address
The neighbour a machine forwards a packet through toward a given destination, the single step its routing table stores. Toward F, the next hop from A is B, from B it is D, and from D it is F itself; during forwarding each machine consults only this entry, never a full route.
Chapter 11, Figure 11.3 Try it See also Routing table; Packet forwarding; ARP; Neighbour; Routing; Router
Half of an 8-bit word, four bits. The book's instruction word splits into two: the high nibble, bits 7 to 4, carries the opcode, and the low nibble, bits 3 to 0, carries the operand, so each field has room for 16 values.
Chapter 5, Figure 5.2 See also Opcode and operand; Memory word; Byte
The two ingredients of a graph: a node is a thing, and an edge joins one node to another. In the chapter's circuit each gate is a node and each wire an edge, so the XOR built from four NAND gates is drawn as four gate nodes, with edges leading from a and b through to out.
Chapter 5.a, Figure 5.a.2 See also Graph; Netlist; Gate record; Wire; Network; Topology
Unwanted disturbance of a wire's voltage, such as what a wire picks up from its neighbours. Gates restore signals whose noise stays within the valid input bands, snapping them back to a clean 0 or 1; they cannot rescue a disturbance that crosses into the wrong band.
Chapter 1 See also Signal restoration; Voltage; LOW and HIGH; Wire; Analog and digital
A loop whose condition never reaches zero, so it would run forever. The book's language permits such loops, and its interpreter therefore runs every program on a budget of steps. The chapter is careful: reaching the limit shows that the run was stopped, not that the program has been proved nonterminating.
Chapter 8 Try it See also Loop; Execution budget; Loop condition
OR with its output inverted, so it outputs 1 only when both inputs are 0. De Morgan's second law reads it equally as an AND of inverted inputs.
Chapter 2 Try it See also De Morgan's laws; Cross-coupled gates
The output of assembling one module on its own, which the book calls an object: its machine code, the labels it exports, and the imports it needs, left as blanks. In the book, main.o holds code whose LOAD and ADD operands are blank, and data.o holds the values 7 and 35.
Chapter 6.a, Figure 6.a.2 See also Imports and exports; Linker; Module; Library
A group of exactly eight bits, the word network standards use for a byte when they give the size of an address. Ethernet MAC addresses contain six octets; the book's MAC strings, such as 02:00:00:0b, have four, and the chapter calls them abbreviated teaching labels.
Chapter 10.b See also Byte; MAC address; Ethernet
A way of marking one choice on a group of lines: exactly one line is HIGH and the rest are LOW. The chapter's 2-to-4 decoder turns two address bits into four one-hot select lines; its four AND gates cover every combination of the address bits with no overlaps and no gaps.
Chapter 4, Figure 4.6 Try it See also Address decoder; Select line; RAM
A latch while its enable is LOW: Q ignores d and holds its last value, the opposite of transparent. In the master-slave flip-flop the master is opaque while the clock is HIGH and the slave while it is LOW, so between rising edges neither latch changes Q.
Chapter 4, Figure 4.3 See also Transparent latch; Gated D latch; Enable; Master-slave flip-flop
The two fields of an instruction word. In the book's 8-bit instruction the opcode, in the high four bits, names the operation and the operand, in the low four bits, gives a memory address: LOAD 13 encodes as 0001 1101.
Chapter 5, Figure 5.2 See also Instruction set; Instruction; Instruction decoder; Instruction encoding; Mnemonic; Machine code
The two states of a switch: closed, it conducts; open, it leaves a gap and blocks. The chapter's NAND figure draws a switch whose control is HIGH closed and lit green, and one whose control is LOW open and grey. The series path conducts only when both switches close.
Chapter 1, Figure 1.6 Try it See also Switch; Control line; Switches in series; Current; Small multiple
A value that an operation works on. In (a + b) + c the outer addition has two operands, the sub-expression a + b and c; flattened, the whole sum has three, and the book's compiler gives each distinct operand a memory cell. An instruction's operand is a narrower thing, an address field.
Chapter 7 See also Operator; Opcode and operand; Flattening; Expression
Replacing a label written as an operand with the address that label stands for. The book's assembler does it in pass two by looking the name up in the symbol table: JUMP start became operand 5 because start landed at address 5, and LOAD a became operand 1 because a landed at address 1.
Chapter 6, Figure 6.3 Try it See also Symbol table; Assembly label; Two-pass assembler; Opcode and operand
The program in charge: a program like any other, but privileged, which decides which program runs and shares the single processor among them all. The book's tiny one is a scheduler that runs several programs on the sixteen-word CPU by letting each take a turn.
Chapter 9 See also Process; Scheduler; Kernel; Timer interrupt; Process creation
A symbol that stands for an operation on the values beside it. The chapter's lexer gives the plus sign a token of its own, PLUS; its exercises ask for a times token, the star, and for a two-character operator such as ==.
Chapter 6.b, Figure 6.b.2 Try it See also Token kind; Expression; Operand (of an expression); Precedence; Comparison expression
A sum too large for the width of its inputs. The four-bit adder's last stage, bit 3, emits it as the overflow carry-out, and the book's adder keeps it as a fifth bit: 10112 + 01102 = 100012, which is 17. Without that bit the carry would be lost from a four-bit result.
Chapter 3, Figure 3.4 Try it See also Carry-in and carry-out; Wraparound; Bit width; Ripple-carry adder
The whisker-thin layer of glass that holds a transistor's metal gate just off the silicon. It keeps the gate apart from the path it controls, so only the gate's electric field reaches through to form the channel. Metal gate, oxide and semiconductor give the MOSFET the first three words of its name.
Chapter 1, Figure 1.2 Try it See also Source, drain and gate; Field effect; MOSFET; Conductor and insulator
A message as it travels across a network of many machines. It carries its destination but not its route: each machine it reaches looks that destination up in its own routing table and hands the packet to one neighbour. The book's packet from A to F goes by way of B and D.
Chapter 11, Figure 11.3 Try it See also Packet forwarding; Network address; Routing table; Segment; Message; Source and destination
Delivery one hop at a time: the machine a packet sits on looks the packet's destination up in its own routing table and hands the packet to that neighbour, and the next machine does the same. The packet is never handed a full route; each step of the book's table moves it one hop closer, so the steps cannot loop.
Chapter 11, Figure 11.3 Try it See also Next hop; Routing table; Packet; Routing; Router; Source and destination
The disappearance of a packet or segment on its way, as when a hop drops a packet because a buffer fills. Numbering cannot repair it, because a lost segment never arrives to be sorted; the sender must resend what is missing. The book's figure marks seg 1 lost.
Chapter 12, Figure 12.3 Try it See also Retransmission; Lossy channel; Best-effort delivery
The units of translation: a program's virtual pages, and the physical frames its page table maps them to. The book's page size is sixteen cells, and a physical address is the frame number times the page size plus the offset, which passes through unchanged, so page 0 in frame 5 puts offset 3 at physical address 83.
Chapter 9.c, Figure 9.c.2 Try it See also Page table; Virtual address; Page size; Page number and offset; Physical address; Page mapping
The event raised when an access touches a page the table does not map. In the book's model it is simply an exception, since no physical address exists; a real one can also ask the kernel to finish valid work, such as allocating a page lazily, and the handler then either supplies a mapping and resumes or rejects the access.
Chapter 9.c See also Page table; Kernel; Exception; Handler; Access permissions; Lazy allocation
One entry of a page table: a virtual page paired with the physical frame it may use. Program A's table holds two, page 0 to frame 5 and page 1 to frame 2. A page with no mapping raises a page fault, and a real handler may supply the missing mapping and resume the program.
Chapter 9.c, Figure 9.c.2 Try it See also Page table; Page and frame; Access permissions; Page fault; Exception; Lazy allocation
The two parts a virtual address splits into: which page it falls in, and how far into that page. The page table turns the page number into a frame number, while the offset rides through untouched. In the book's figure, page 0, offset 3 becomes frame 5, offset 3.
Chapter 9.c, Figure 9.c.2 Try it See also Virtual address; Page table; Page and frame; Address translation; Page size
The number of cells in one page, and so in one frame. Dividing a virtual address by it gives the page number, with the offset as remainder; a frame number times the page size, plus the offset, gives the physical address. The book's is 16 cells, so frame 8, offset 3 is physical address 131.
Chapter 9.c, Figure 9.c.2 Try it See also Page and frame; Page number and offset; Address translation
The per-program table that maps virtual page numbers to the physical frames the program may access, while the offset rides through untouched. The book's program A maps page 0 to frame 5 and page 1 to frame 2; its Python functions trust whatever table the caller passes, so they show mappings, not an enforced security boundary.
Chapter 9.c, Figure 9.c.2 Try it See also Virtual address; Page and frame; Page fault; Address translation; Page number and offset; Memory isolation
The stage that assembles a lexer's tokens into a tree that makes the program's grouping explicit. Given (a + b) + c, it puts the outer addition at the root, with a + b as its left child and c as its right; addition groups left to right, so a + b + c parses the same way.
Chapter 7, Figure 7.2 See also Abstract syntax tree; Recursive descent; Lexer; Token; Precedence; Syntax error
Someone who can watch every message on the wire but cannot replace any of them. The chapter assumes one first: the observer knows g and p and sees both public values, yet the secret itself never crosses the wire. The book's tiny arithmetic and cipher provide no real security even against a passive observer.
Chapter 13.a, Figure 13.a.2 See also Intermediary; Public value; Diffie-Hellman key exchange; In the clear; Secrecy
The data a frame or packet exists to carry, as distinct from the bytes wrapped around it for the trip. In the book's frame for hi, the payload is the two bytes 68 69; the flags at each end and the two-byte CRC, 62 03, are added by the sender and removed by the receiver.
Chapter 10, Figure 10.3 Try it See also Link-layer frame; CRC; Flag byte; Message; Addressed frame
Establishing who is at the other end, which agreement alone does not do. An intermediary that replaces both public values agrees separately with each side, so it can read a message and encrypt it again for the other side without recovering either private exponent. In a typical web TLS connection, the client validates a certificate for the expected server name.
Chapter 13.a See also Diffie-Hellman key exchange; TLS; Certificate; Intermediary; Handshake signature; Pre-shared key
Storage that keeps its contents without power, so data outlives any running program. Memory forgets everything when the power goes; a disk does not. The book's Disk is not persistent itself: it lives in Python memory and nothing is saved across process restarts, so it shows how file blocks are found, not the device.
Chapter 9.d See also Disk; File; RAM
An address in the machine's real memory, the result of translating a virtual address. It is the frame number times the page size, plus the offset: frame 5 with sixteen-cell pages and offset 3 gives 83. Two programs can use the same virtual address 3 and land in different physical cells, one in frame 5 and the other in frame 8.
Chapter 9.c, Figure 9.c.2 Try it See also Virtual address; Page and frame; Memory isolation; Address translation; Physical memory
The bottom layer of a network, where a bit is nothing but a voltage. The sender holds the wire high or low for one tick of a shared clock per bit and the receiver reads its level once per tick; eight ticks carry the byte 0x68. It is unreliable: a clock can drift and noise can flip a bit.
Chapter 10, Figure 10.2 See also Data link layer; Clock; Layer; Clock drift; Clock tick
The machine's one real memory, shared by every program and divided into frames. Virtual memory lets each program believe that memory is its own. In the book's figure, frame 5 holds A's 42 and frame 8 holds B's 99, at physical addresses 83 and 131.
Chapter 9.c, Figure 9.c.3 Try it See also Physical address; Page and frame; Virtual memory; RAM
Overlapping the stages of successive instructions, so the next instruction is fetched while the one before it is still being decoded or executed.
Chapter 5.b, Figure 5.b.2 Try it See also Data hazard; Fetch-decode-execute cycle; Pipeline bubble; Pipeline schedule; Pipeline stage; Branch misprediction
The empty slot a stall leaves in a pipeline: a cycle in which a stage has no instruction to work on. In the book's hazard figure r2 is held back at cycle 2, drawn as a dashed box, and everything behind the bubble slips a cycle.
Chapter 5.b, Figure 5.b.3 Try it See also Stall; Data hazard; Pipeline
The number of stages an instruction passes through in a pipeline; the book's has three. A deeper pipeline fetches further ahead before a branch executes, so a wrong guess costs more: the book's figure flushes two instructions, and a deeper pipeline would flush more.
Chapter 5.b, Figure 5.b.4 See also Pipeline stage; Flush; Branch misprediction
The plan that gives every stage of every instruction a cycle number. The book builds one by placing each instruction one cycle after the last, unless it must wait for a register an earlier instruction is still computing; the run then takes as many cycles as the last instruction's execute, plus one.
Chapter 5.b, Figure 5.b.2 Try it See also Pipeline; Stall; Hazard rule; Clock cycle; Timing model
One step of an instruction's passage through a pipeline; the book's has three, fetch, decode and execute. Each instruction runs its stages a cycle behind the one before, so once the pipeline fills, three are in flight at once and one finishes every cycle: four instructions take six cycles, not twelve.
Chapter 5.b, Figure 5.b.2 Try it See also Pipeline; Fetch-decode-execute cycle; Stall; In flight; Clock cycle; Pipeline depth
The rule an allocator follows to choose which free run serves a request. The book's Heap takes the first run large enough, the policy called first fit. It is the simplest choice, not the only one: real allocators use others, such as best fit, buddy systems and size classes.
Chapter 9.b Try it See also First fit; Best fit; Memory allocator; Heap fragmentation; Buddy system; Size class
A number reached by doubling from 1: 1, 2, 4, 8 and so on. Powers of two are the weights of binary places, and they count what a group of bits can tell apart: the two opcode bits of the book's ALU select one of four operations.
Chapter 3 See also Weight (of a place); Binary numeral; ALU opcode
A secret that both ends already hold before the handshake begins. The chapter names it as another way, besides a certificate and a handshake signature, to authenticate a peer and the handshake. The book's toy uses none of them: its exchange has no authentication at all.
Chapter 13.a See also Peer authentication; Certificate; Key; TLS
The rule that decides which operator takes its operands first when no parentheses say. The book's first language has only addition, so the question does not arise in it; an exercise adds multiplication, binding tighter than addition, and asks where in the parser that precedence lives.
Chapter 7 See also Grouping; Operator; Parser; Associativity
Stopping a process that has not halted in mid-run, the moment its quantum is spent. The book's scheduler gets this free because the CPU is simulated one step at a time and it counts steps from outside; a real operating system needs a timer interrupt to regain control from a running core.
Chapter 9 See also Scheduling quantum; Scheduler; Timer interrupt; Runaway process
The number each side of a key exchange keeps to itself and never sends. In the book Alice's is 6 and Bob's is 15. Each raises the other's public value to its own private exponent, modulo the prime, and both arrive at 1893334806. A real exchange needs large enough exponents and groups, and the book's small constants do not meet that requirement.
Chapter 13.a, Figure 13.a.2 Try it See also Public value; Shared secret; Modular arithmetic; Alice and Bob; Modular exponentiation; Secrecy
The right to touch the machine's resources directly. Only the kernel has it: its routines run in the privileged mode, while a program has no privileged state of its own and learns even its own id by asking. The operating system is a program like any other, but a privileged one.
Chapter 9.a, Figure 9.a.2 See also Kernel; User mode and kernel mode; Mode bit; Protection
A running program together with its state, called its context. On the book's CPU the context is exactly four things: the program counter, the accumulator, the memory, and whether the program has halted. Saving those stops a process cold; restoring them resumes it as if nothing happened.
Chapter 9, Figure 9.2 See also Context switch; Operating system; Process context; Process id; Process creation; Running and waiting
Everything the operating system must remember to pause a program and later resume it exactly where it left off. Each of the book's processes keeps its own: the saved program counter, the accumulator, a reference to its memory list and the halted flag. Only one context is loaded into the processor at a time.
Chapter 9, Figure 9.2 See also Process; Context switch; Save and restore; Running and waiting
Asking the operating system for a new process in which a program can run. A real shell does this, and has an executable program loaded, for the commands it is given. The book's shell stops earlier, at dispatching functions that are already resident; the scheduler and memory translator remain separate models.
Chapter 9.e See also Process; Loader; Shell; Operating system
The number by which a kernel tells one process from another. A program has no privileged state of its own, so it learns even its own id by asking: the book's GETPID call, number 2 on the menu, returns 7, which the program then hands back to the kernel to write out.
Chapter 9.a, Figure 9.a.3 Try it See also Process; System call; Menu of services
A sequence of instructions, with the data they work on, that a machine carries out in order. The book's first one is five instructions followed by three data cells: it sums the values at addresses 13, 14 and 15, writes the result to address 12, and halts.
Chapter 5 Try it See also Stored program; Instruction; Machine code; Memory image; Software; Executable file
The register that holds the address of the next instruction. Each cycle the CPU fetches the word it points to and advances it by one through the ripple adder; a JUMP or JZ that fires overwrites it with the branch target.
Chapter 5 Try it See also Fetch-decode-execute cycle; Branch; Branch target; JUMP; Accumulator; Fall-through
A value handed to a program from outside before it runs. In the book's languages inputs enter only through the starting environment: the multiplication program is given a as 6 and b as 7, and b must be a nonnegative integer for the loop to multiply. Everything else the program computes for itself.
Chapter 8 Try it See also Variable environment; Variable; Binding
A notation for programs, with two halves: syntax, the rules for which texts are programs, and semantics, what a program does once it is understood. The chapter asks what separates one from a calculator and answers with three things: a way to keep state, a way to do one thing after another, and a way to repeat.
Chapter 8 See also Syntax; Semantics; Imperative language; Expression language
The time a gate's output takes to settle to the result for new inputs. A combinational answer, such as a RAM read, is valid only once its gate delays settle; and when the inputs change, a gate has no separate way to retain the old result, which is why memory needs feedback.
Chapter 4 See also Combinational logic; Critical path; Latency; Settling; Level (of gates)
The half of an operating system's job that stops one buggy or hostile program from wrecking every other: a program cannot reach the disk, the network or another program's memory on its own. Real systems enforce it with hardware privilege and kernel checks; the book's Python trace demonstrates dispatch, not protection against a caller that bypasses it.
Chapter 9.a, Figure 9.a.2 See also Kernel; User mode and kernel mode; Privilege; Memory isolation; Resource; Access permissions
An agreement between two machines on where their messages end and what the bytes mean. Without one, two machines holding an open stream are like two people on a phone line who have not agreed on a language: the line works and still they cannot talk. The book's protocol has the text shape of HTTP/1.x.
Chapter 13 See also HTTP; Request and response; RFC
Trying a design out in a form that is cheap to change before committing to the final one. Chip designers prototype on FPGAs: the book's processor could be loaded into a fabric, tested against real inputs for months, and recast in silicon only once it stops changing.
Chapter 5.d See also FPGA; Fixed silicon; Bitstream
The number each side of a key exchange sends in the open: the base g raised to its private exponent, modulo the prime p. With g = 5 and p = 2147483647, Alice's exponent 6 gives 15625 and Bob's 15 gives 452807067. Both cross the wire in plain view; the secret they lead to never does.
Chapter 13.a, Figure 13.a.2 Try it See also Private exponent; Diffie-Hellman key exchange; Shared secret; Base and modulus; Modular exponentiation; Passive observer
The two halves of a CMOS gate: the pull-up, p-channel switches that drive the output HIGH, and the pull-down, n-channel switches that drive it LOW. In NAND the pull-down is two switches in series and the pull-up two side by side.
Chapter 1, Figure 1.4 Try it See also CMOS; Drive; Switches in series; n-channel and p-channel; Rail
A rule whose result depends only on the inputs it is given now, never on anything earlier. A combinational circuit's output is a pure function of its present inputs: feed it the same inputs twice and it gives the same output twice, which makes it easy to trace.
Chapter 3 See also Combinational logic; State; Truth table
The programming language in which the book writes its models, including both of its interpreters. The chapter notes that Python itself is no tree walker: it compiles source to bytecode and runs that on a virtual machine. Its integers do not wrap at eight bits, so the book's first interpreter wraps each sum at 256 itself.
Chapter 7 See also Interpreter; Bytecode; Virtual machine; Dictionary
The two outputs of a latch: Q is the stored bit, and the other is its complement, which the chapter's code calls qbar. In the SR latch the bottom NOR gives Q and the top NOR the complement. With S and R both HIGH, both are forced LOW and are no longer complements.
Chapter 4, Figure 4.2 Try it See also SR latch; Set and reset; Conjunction, disjunction and complement
The two results of a division: how many times the divisor fits, and what is left over. Each binary quotient digit can only be 0 or 1. For 13 / 3 the book's divider returns quotient 0100, which is 4, with remainder 1, and the result checks as every division must: 3 × 4 + 1 = 13.
Chapter 3.a, Figure 3.a.2 See also Binary long division; Dividend and divisor; Divider; Integer division; Quotient bit; Running remainder
One bit of the quotient, settled by one step of binary division: 1 if the divisor could be subtracted at that bit position, 0 if not. In the run of 13 / 3 only the step at bit 2 can subtract, so only bit 2 is set and the quotient is 0100, which is 4.
Chapter 3.a, Figure 3.a.2 See also Quotient and remainder; Comparison; Bit position
One of the two fixed supply lines a gate sits between, the HIGH rail above and the LOW rail below. In the inverter the p-channel is the path to the HIGH rail and the n-channel the path to the LOW rail, so a settled output is always driven to one of them.
Chapter 1, Figure 1.4 Try it See also LOW and HIGH; Pull-up and pull-down networks; Drive; Current
Random-access memory: a bank of registers selected by an address. To write, you supply data and address and raise the write line; to read, you supply the address and combinational logic picks the word without waiting for a clock edge.
Chapter 4, Figure 4.6 Try it See also Address decoder; Register; Refresh; Memory cell; Memory address; SRAM and DRAM
A test that a value fits the space it is about to be written into. The book's assembler range-checks a DATA value, rejecting anything outside 0 to 255, but not a resolved operand: an address of sixteen or more would silently wrap in the four-bit operand field instead of being rejected.
Chapter 6 Try it See also Wraparound; Byte; Opcode and operand; Assembler
A gate whose input wires all have values already, so it can be evaluated. Each round, the book's simulator collects the ready gates and fires them all at once. With only a and b known, shared is the one ready gate of the XOR netlist; left and right must wait for it.
Chapter 5.a Try it See also Fire; Simulation round; Circuit simulator; Wire; Undriven wire
The short text that follows the status code in a response's start line and says the same thing in words; the chapter calls it the reason. The book's server sends OK after 200 and Not Found after 404, so the reply to /hello opens with HTTP/1.0 200 OK.
Chapter 13, Figure 13.2 Try it See also Status code; Start line; Request and response
Putting received segments back into one message, the inverse of cutting it up. The book's receiver indexes the segments by sequence number, which discards duplicates, then sorts the numbers and joins the data. Segments that arrived as [3, 1] and then [2, 0] still give back HELLO, NETWORK!.
Chapter 12, Figure 12.3 Try it See also Segmentation; Sequence number; Duplicate segment; Receiver buffer; Reordering
Where the receiver keeps the segments that have arrived until the message is complete. The book's is a table from sequence number to segment, and the receiver acknowledges every segment in it. In the run it holds [1, 3] after the first round and [0, 1, 2, 3] after the second.
Chapter 12 See also Segment; Reassembly; Acknowledgement (ACK)
Loading a different bitstream into the same fabric so that it becomes a different circuit. Nothing physical changes; configuring is only a memory write. The book loads one two-block fabric twice: bitstream A makes the half adder, and bitstream B, two NANDs with block 1 reading block 0, makes AND.
Chapter 5.d, Figure 5.d.5 Try it See also Bitstream; Fabric; FPGA
A function calling itself on a smaller piece of the same problem. The book's interpreter is one recursive function: an addition recurses into both children, so the whole tree collapses to one byte from the leaves upward. In the parser, the recursion in the grammar becomes recursion in the code.
Chapter 7 See also Recursive descent; Tree walk; Nesting; Interpreter
The smallest kind of parser that handles nesting. One method reads an expression as terms joined by +; another reads a single term, and a parenthesized term calls the first method again, so the recursion in the grammar becomes recursion in the code and expressions nest to any depth.
Chapter 7 See also Parser; Grammar; Nesting; Recursion; Term (of an expression); Grammar rule
What a DRAM memory controller must do to its rows periodically, before the stored values fade: a DRAM cell keeps its bit as charge on a tiny capacitor, and the charge leaks. SRAM, held by feedback, needs no refresh.
Chapter 4 See also RAM; Capacitor; Memory controller; Main memory; SRAM and DRAM
A store for one word: one flip-flop per bit, sharing a clock and a load line. When load is HIGH the register captures the data word at the next rising edge; when load is LOW each bit feeds back and the word holds.
Chapter 4, Figure 4.5 Try it See also D flip-flop; RAM; Capture; Load line; Register file; Bus
A set of general-purpose working registers inside a CPU, any of which an instruction may name. The book's CPU has none: it is an accumulator machine, so every ADD reads one operand from memory and adds it to the single accumulator.
Chapter 5 See also Accumulator machine; Register; Accumulator
Delivery in which a message arrives complete and in order, or the failure is reported. The book's loop makes a narrower promise: when it succeeds under the stated channel contract, the returned message is complete and ordered. Retrying cannot guarantee success through a permanent outage, so past the round limit the call fails.
Chapter 12 Try it See also Transport layer; Best-effort delivery; Retransmission
The linker's step of filling each blank operand with its symbol's final address, once the layout has fixed it. The book's LOAD left its operand blank because value was unknown; once the data module is placed, value lands at address 5, and only the operand changes, never the opcode.
Chapter 6.a, Figure 6.a.3 Try it See also Linker; Imports and exports; Blank operand; Base address; Memory layout; Symbol resolution
Arrival of pieces in a different order from the one they were sent in, as when two packets take different routes. In the book's run the first round sends segments [0, 1, 2, 3] and the two that get through arrive as [3, 1]; sorting by sequence number restores the original order.
Chapter 12 See also Sequence number; Reassembly; Lossy channel
Multiplying with nothing but adding: add one number to a running total as many times as the other says. The book's machine has no multiply instruction, yet its loop adds a to product b times; with 6 and 7 that is seven additions of 6, ending at 42.
Chapter 8 Try it See also Loop; Expressiveness; Loop pass; Countdown loop
The two messages of an HTTP exchange, which share one shape: a start line, headers, a blank line, then a body. Only the start line differs: a request leads with a method and a path, as in GET /hello, and a response with a status and a reason, as in 200 OK.
Chapter 13, Figure 13.2 Try it See also HTTP; Status code; Client and server; Start line; HTTP header; HTTP method
The code a server runs to answer one request. In the book's small protocol it is a lookup in a table of paths; a real web server has handlers that compute a page rather than look one up. Either way, a handler can still be understood as a function from a request to a response.
Chapter 13 See also Web server; Lookup server; Request and response
The number by which a program names the service it wants. It leaves the number and an argument where the kernel will look, then traps. In the book, 0 is WRITE, 1 is READ and 2 is GETPID; a number that is not on the menu is refused, so a program cannot invent a service.
Chapter 9.a, Figure 9.a.3 See also System call; Menu of services; Dispatch
The part of a request's start line that names what the client is asking for, after the method: /hello in GET /hello HTTP/1.0. The book's server answers by finding the path in its table, so /hello earns 200 OK and the page, while /missing, a path it does not have, earns 404 Not Found.
Chapter 13, Figure 13.2 Try it See also Start line; HTTP method; Lookup server; Status code
A program already in memory and ready to run when it is asked for, so nothing has to be loaded first. The book's commands are all resident: they are Python functions already available in the shell, so dispatch only maps a command name to one of them and runs it.
Chapter 9.e See also Loader; Command dispatch
Something a program needs but must not touch directly: the screen, the disk, the network, another program's memory. The kernel holds the resources and the routines that touch them, and serves one request at a time; the book's program reaches the screen only by handing the kernel a value to write.
Chapter 9.a, Figure 9.a.2 See also Kernel; Protection; System call
Sending a segment again because it went unacknowledged. Each round the book's sender retransmits exactly the segments not yet acknowledged, until none remain or the round limit, 100 by default, is reached. With its perfect acknowledgements an arrived segment is never resent, and a lost one is simply sent again.
Chapter 12, Figure 12.3 Try it See also Acknowledgement (ACK); ACK loss; Delivery round; Packet loss; Reliable delivery
What a call hands back to its caller when it finishes. Each of the book's system calls returns one number, the result of the routine the kernel ran: GETPID returns 7, the two READ calls return the inputs 40 and 2, and each WRITE returns 0.
Chapter 9.a Try it See also System call; Handler; Trap
A Request for Comments, one of the numbered public documents in which the internet's protocols are written down. The chapter cites two: RFC 826, which describes ARP's mapping from a next-hop protocol address to an Ethernet address, and RFC 1122, for its section on validating an ARP cache.
Chapter 10.b See also ARP; Protocol; Ethernet
An n-bit adder made by chaining n full adders, each stage's carry-out feeding the next stage's carry-in. It is easy to trace but slow at scale, because a stage's carry is valid only after every less significant stage has settled.
Chapter 3, Figure 3.4 Try it See also Carry; Adder stage; Bit width; Carry chain; Carry-lookahead adder; Critical path
The instant a clock signal goes from LOW to HIGH. A D flip-flop's output changes only then, capturing the value d held at that moment and ignoring later changes until the next one. The bit-banged link reuses the idea: its receiver reads the data line on each rising edge of the clock line.
Chapter 4, Figure 4.4 See also Clock; Edge-triggered; D flip-flop; Sampling; Capture; Clock phase
The positions a node can hold in a tree: the root is the top node, a child sits directly beneath another node, and a leaf has no children. In the tree of (a + b) + c the outer addition is the root, the inner a + b its left child and c its right; the three variables are leaves.
Chapter 7, Figure 7.2 See also Tree node; Abstract syntax tree; Flattening
A test that sends a value out and brings it back, then compares the result with the original. The bit-banging run clocks every byte from 0 to 255 out as line states and reads each back by sampling; all 256 survive, so the two lines carry any byte intact.
Chapter 10.a Try it See also Bit-banging; Sender and receiver; Byte
The simplest fair scheduling policy: go around a list of processes, giving each a quantum in turn and skipping any that have halted. With a quantum of three steps, the book's adder runs three, the pair three, the adder three more and finishes, and the pair runs its last two.
Chapter 9, Figure 9.3 Try it See also Scheduler; Scheduling quantum; Time-sharing; Scheduling policy; Fairness; Time slice
The chain of machines a packet passes through, source first and destination last. No packet carries its route and no table stores a whole one, since each machine holds only the first step. The chapter's run forwards a packet along the route A to B to D to F, three hops.
Chapter 11, Figure 11.3 Try it See also Shortest path; Routing; Hop; Source and destination
A machine that passes a packet on toward a destination other than itself. The routing chapter calls it an intermediate machine: on the journey from A to F, B and D each forward the packet one step. For a distant destination, the link address that ARP finds belongs to the next router, not to the final recipient.
Chapter 11, Figure 11.3 Try it See also Packet forwarding; Next hop; Routing table; ARP; Internet
The process by which each machine decides, for any destination, which neighbour to forward a message through, so a message can cross machines that share no single wire without carrying its whole route. From A to F, three local decisions send it through B and D, a shortest path.
Chapter 11, Figure 11.3 Try it See also Routing table; Next hop; Packet forwarding; Route; Internet; Network graph
A machine's list giving, for every destination, the neighbour to forward a message through. It holds only the first step toward each destination, since the next machine holds the next step. The book builds it by breadth-first search of the whole static graph; A's table sends destination F to B.
Chapter 11, Figure 11.3 See also Next hop; Breadth-first search; Packet forwarding; Router; Routing; Shortest path
The store that holds the row a large memory has opened. The address is split into a row and a column: activating a row copies many nearby cells into the buffer, and column selection picks the requested bytes. A second access to the same row is a row hit and can be quick; another row must first be activated.
Chapter 4 See also SRAM and DRAM; Memory controller
A small gate network that outputs 1 for exactly one row of a truth table. For the row where a is LOW and b is HIGH, a · b inverts a, keeps b and ANDs them. OR the detectors for every 1-row and any truth table follows; since NOT, AND and OR all come from NAND, NAND is enough.
Chapter 1 See also Truth table; Universal gate
A process whose program never halts. The book's scheduler has no guard against one: its loop runs until every process has halted, so a single runaway would spin the scheduler forever. The chapter names this as what its toy scheduler lacks.
Chapter 9 See also Scheduler; Halted flag; Preemption
The two conditions of a process that has not yet halted. The running one has its context loaded into the processor; a waiting one sits saved until its turn. The book's figure shows adder running and pair waiting, and only one context is loaded at a time.
Chapter 9, Figure 9.2 See also Process; Process context; Context switch
The value a divider carries from step to step, which ends as the remainder. It starts at zero; each step shifts it left, brings down one dividend bit, and subtracts the divisor if it is large enough. For 13 / 3 it reads 1, 0, 0, 1 after the four steps.
Chapter 3.a, Figure 3.a.2 See also Quotient and remainder; Binary long division; Bring down; Left shift; Comparison
Reading a line's level at one chosen instant. The bit-banged receiver samples the data line only on a rising edge of the clock, when the clock was low and is now high, and shifts each bit into the byte it is building. Holding the data steady and moving only on the edge keeps the two ends in step.
Chapter 10.a, Figure 10.a.3 Try it See also Clock line; Edge-triggered; Data line; Rising edge; Bit-banging; Clock tick
Stopping at a limit instead of going past it or wrapping round. The book's two-bit counter rises with each taken outcome and falls with each not-taken one, stopping at 3 or 0, so a steady branch saturates fast and then stays right. From a saturated state it takes two contrary outcomes to change the prediction.
Chapter 5.b See also Two-bit counter; Wraparound; Branch predictor
The two halves of a context switch. Restore loads a process's saved context into the one shared processor before it runs; save copies the processor's state back into the process when its slice ends. The book's mechanism is just these two and a loop, and it swaps a reference to a memory list rather than copying the memory.
Chapter 9, Figure 9.2 See also Context switch; Process context; Scheduler
Reading text one character at a time, left to right, and deciding at each what to do: skip a space, gather a number, gather a name, make a symbol token, or refuse. The book's lexer is one such scan, and the small lexers of the next two languages reuse the idea.
Chapter 6.b Try it See also Lexer; Token; Whitespace
The heart of the operating system, the part that decides which process runs next. The book's uses round-robin, the simplest fair policy: it gives each process a quantum of steps in turn around a list, saving and restoring contexts and skipping any process that has halted, until all have finished.
Chapter 9, Figure 9.3 Try it See also Scheduling quantum; Context switch; Operating system; Preemption; Round-robin scheduling; Scheduling policy
The rule by which a scheduler decides who runs next and for how long, as distinct from the mechanism that carries the decision out. The book's policy is round-robin, and the quantum is the whole of it; its mechanism is just save, restore and a loop.
Chapter 9 Try it See also Round-robin scheduling; Scheduling quantum; Scheduler; Fairness
The fixed positive number of steps a process may run before the scheduler moves to the next; the book's trace uses three. A small quantum switches often and feels responsive, while a large one switches rarely and wastes less time saving and restoring contexts.
Chapter 9, Figure 9.3 Try it See also Time-sharing; Preemption; Scheduler; Round-robin scheduling; Scheduling policy; Time slice
Keeping a value from everyone who can watch the wire. The chapter treats it as a separate claim from agreement: the arithmetic makes both sides reach the same number, but hiding it rests on the belief that deriving it from the public values is infeasible, given suitable large groups and private exponents. The book's small constants do not qualify.
Chapter 13.a See also Shared secret; Key agreement; Private exponent; Passive observer
A way of talking across a network that protects the bytes and establishes who is at the other end. The book's toy is not one: its tiny parameters, four repeating key bytes, weak checksum and unauthenticated exchange each prevent it. Real TLS combines key agreement and key derivation, authentication of the peer and handshake, and secure record protection.
Chapter 13.a See also TLS; Peer authentication; Encrypted record; Key agreement; In the clear
One numbered piece of a message cut small enough to send. Each carries a sequence number and a few bytes of data: the book cuts HELLO, NETWORK! into four segments of at most four bytes, numbered 0 to 3.
Chapter 12, Figure 12.2 Try it See also Sequence number; Transport layer; Segmentation; Receiver buffer; Packet
Cutting a message into pieces small enough to send and numbering each one, the first step of the book's transport; reassembly is the inverse. The number travels with its piece. With at most four bytes per segment, HELLO, NETWORK! becomes HELL, O, N, ETWO and RK!.
Chapter 12, Figure 12.2 Try it See also Segment; Sequence number; Reassembly
The input of a multiplexer that chooses which data input reaches the output. In the 2-to-1 multiplexer a LOW select passes the first input and a HIGH select passes the second; the book's code is or_(and_(not_(sel), a), and_(sel, b)).
Chapter 3 See also Multiplexer; Four-to-one multiplexer; ALU opcode; Control line; Memory address; One-hot
An acknowledgement that names each segment the receiver holds, so the sender can resend exactly the missing ones. The book's receiver works this way: with three segments and the middle one lost it answers ack 0, 2, and later ack 0, 1, 2. TCP carries selective information only as an option beside its cumulative acknowledgement.
Chapter 12, Figure 12.3 See also Acknowledgement (ACK); Cumulative acknowledgement; TCP
The half of a language that fixes meaning: what a program does once it is understood. The book gives it by an interpreter that walks the tree, evaluating expressions and executing statements, so its multiplication loop leaves product at 42 when a is 6 and b is 7.
Chapter 8 See also Syntax; Interpreter; Imperative language; Programming language
A material that is neither a good conductor nor a true insulator. Silicon, the main ingredient of sand, is one: in a crystal, each atom's four outer electrons are locked into bonds with neighbours, so pure silicon has few loose charges to carry a current until doping changes that.
Chapter 1, Figure 1.2 See also Doping; n-type and p-type; Silicon; Conductor and insulator
The two ends of one transfer across a wire. The sender holds the wire high or low for each bit, and the receiver watches it and reads its level once per tick. Whatever the sender adds, the receiver undoes: it splits the stream at the flags, un-stuffs each frame and recomputes the CRC.
Chapter 10, Figure 10.2 See also Wire; Sampling; Framing; Round trip
The number a segment carries, which lets the receiver rebuild the message however the pieces arrive. Reassembly indexes the received segments by it, so a duplicate simply overwrites itself with identical data, then sorts the numbers: the numbers, not the order of arrival, fix the message back together.
Chapter 12, Figure 12.2 Try it See also Segment; Acknowledgement (ACK); Reassembly; Duplicate segment; Reordering; Segmentation
Doing one thing after another: with state and repetition, one of the three things that turn a calculator into a language. In the book's interpreter it is just the order of the statements, run one after another, each able to see what the earlier ones left in the environment.
Chapter 8 Try it See also Statement; Control flow; Mutable state; Imperative language
Running instructions one at a time, each finishing before the next begins, as the book's accumulator CPU does. It is the standard a pipeline is held to: overlapping is allowed only because the result is the same. Run this way, the chapter's four three-stage instructions take twelve cycles; overlapped, six.
Chapter 5.b Try it See also Pipeline; Hazard rule; Fetch-decode-execute cycle
The two control inputs of an SR latch, written S and R. Raising S sets the latch, so Q goes HIGH; raising R resets it, so Q goes LOW. Both HIGH together is excluded from normal use, and the book's model rejects that combination with ValueError.
Chapter 4, Figure 4.2 Try it See also SR latch; Hold state; Q and NOT Q
A circuit's outputs reaching their final values after its inputs change; until then an output is not yet valid. In the ripple-carry adder each stage must wait for the stage to its right to settle before its own carry-out is valid.
Chapter 3, Figure 3.4 Try it See also Propagation delay; Critical path; Latency
A physical frame that appears in the page tables of several processes at once. Real systems map frames this way on purpose, for example to share data or read-only code. The book's example never does: its two programs get disjoint frames, so neither touches the other's cells.
Chapter 9.c See also Disjoint frames; Page and frame; Memory isolation
A local link that several machines are attached to, so that every one of them hears what is sent on it. The chapter's wire joins three machines, A, B and C. A frame there must say which interface should receive it, and a question can be broadcast to them all.
Chapter 10.b, Figure 10.b.2 Try it See also Broadcast; Link; Link address; Network interface; Internet
The value both ends of a key exchange reach without sending it: Ba mod p = Ab mod p = gab mod p, 1893334806 in the book's example. With suitable large groups and private exponents, deriving it from the public values is believed infeasible; the book's small constants do not meet that requirement.
Chapter 13.a, Figure 13.a.2 Try it See also Diffie-Hellman key exchange; Keystream; Public value; Private exponent; Key derivation; Key agreement
The program a person types at to start the others. It runs a short loop: read a line, split it into a command and its arguments, look the command up among the installed programs, run it and show what it returns, then read again. The book's shell can write a file and read it back.
Chapter 9.e, Figure 9.e.2 Try it See also Command and arguments; Command dispatch; Filesystem; Command line; Loader; Process creation
The route between two machines that costs least. The book counts every link as one hop, so the shortest path is the one with the fewest links, three from A to F; a real network weighs its links by speed or cost. Breadth-first search finds a shortest path to every node.
Chapter 11, Figure 11.2 Try it See also Breadth-first search; Hop; Routing table; Route; Hop count; Link cost
The value a wire carries, read as one of two levels, LOW or HIGH. In a switch, the signal line is the path that conducts or does not, and the control line is the wire that decides. The deciding wire carries a signal too, which is how one switch can flip another.
Chapter 1, Figure 1.3 See also Switch; LOW and HIGH; Bit; Control line; Wire; Input and output
A gate's driving of its settled output towards a rail, which wipes out small errors on its input. A lone switch only passes its input along; the inverter and the NAND do the restoring. Repeated at every gate, within the valid bands, it is why two values work so reliably.
Chapter 1 See also Noise; LOW and HIGH; Inverter; Drive
An unsigned number is never negative; a signed one may be. The chapter stays unsigned, so its subtraction refuses any result that would go below zero and its divider takes only unsigned values. Real processors also handle signed numbers, which the chapter leaves out.
Chapter 3.a See also Two's complement; Fixed width; Divider; Minuend and subtrahend
The element a transistor is made from, and the main ingredient of sand. A silicon atom has four outer electrons, each locked into a bond with a neighbour in the crystal, so pure silicon carries little current. The MOSFET's p-type body and n-type wells are the same silicon, doped two ways.
Chapter 1, Figure 1.2 See also Semiconductor; Doping; Transistor
One pass of the book's simulator, in which every ready gate fires at once; the chapter also calls the rounds waves. Values spread outward from the inputs, round by round, until every wire is settled. The XOR netlist takes three, and listing its gates in any order gives the same rounds.
Chapter 5.a, Figure 5.a.3 Try it See also Fire; Ready gate; Circuit simulator; Netlist
One of a fixed set of block sizes an allocator serves, each request being rounded up to the nearest. The chapter only names size classes, beside best fit and buddy systems, as a choice real allocators make to trade speed against how much the heap fragments.
Chapter 9.b See also Placement policy; Free list; Best fit
A figure that repeats one small drawing several times, changing only what differs; the caption credits the form to Tufte. The chapter draws the same NAND pulldown four times, once per input combination, and the four output bits read left to right, 1,1,1,0, are the NAND truth table.
Chapter 1, Figure 1.6 See also Truth table; NAND; Open and closed switch
Programs: instructions and data loaded into a machine, as opposed to the hardware that runs them. The assembler is the first piece of software in the book. Assembling the sum program changes nothing about the machine, only the bytes placed in its memory, and the accumulator still ends holding 42.
Chapter 6 See also Hardware; Program; Assembler; Stored program
The machine a packet starts from and the machine it is meant to reach. A packet carries its destination and nothing about the way there; each machine it reaches looks that destination up in its own routing table. In the book's journey the source is A and the destination is F, and both must be nodes of the network.
Chapter 11, Figure 11.3 Try it See also Packet; Route; Packet forwarding; Network address
A program as a person writes it: plain text, which the book calls the source. A translator reads it and produces the form the machine runs. The assembler walks its source twice, each line becoming one machine word; a lexer cuts higher-level source into tokens before a parser builds the tree.
Chapter 6, Figure 6.2 See also Assembly language; Assembler; Machine code; Compiler; Translator; Comment
The parts of an n-channel MOSFET: the source and drain are two n-type wells in a p-type body, and the gate is metal above the gap between them, held off the silicon by thin glass. Read as a switch, the gate is the control line.
Chapter 1, Figure 1.2 Try it See also MOSFET; Control line; Body and wells; Oxide insulator; Transistor
The habit of programs to use the words next to one they have just used. It is why a cache moves whole lines: a miss on one word loads its eight-word line, and the next seven words then hit. The book's SCAN trace never reads an address twice, yet it hits 56 times and misses only 8.
Chapter 5.c, Figure 5.c.3 See also Locality; Temporal locality; Cache line
The Serial Peripheral Interface, a real protocol by which a processor talks to a chip beside it. The chapter names it, with JTAG, as having the shape of its bit-banged link: a clock line beside a data line, with each bit set on the data line and then clocked across.
Chapter 10.a See also Bit-banging; Clock line; Data line; JTAG
The smallest useful feedback loop: two NOR gates, each one's output feeding an input of the other. S sets Q HIGH, R resets it LOW, and with both LOW the latch holds its last value, one bit of memory.
Chapter 4, Figure 4.2 Try it See also Feedback; Gated D latch; Cross-coupled gates; Set and reset; Hold state; Q and NOT Q
Two kinds of real RAM. An SRAM cell is a tiny latch that feedback holds while power remains, fast but physically large, so SRAM serves registers and caches. A DRAM cell stores a bit as charge on a tiny capacitor: much smaller, so DRAM is denser, cheaper and usually main memory, but the charge leaks and needs refresh.
Chapter 4 See also RAM; Refresh; Feedback; Capacitor; Main memory; Memory controller
A solid-state drive: storage that keeps its contents without power, far larger and far slower than main memory. It is the disk rung of the book's ladder, 400,000 cycles from the core, which is 4.6 days at one second a cycle: a parcel in the post.
Chapter 5.c, Figure 5.c.2 See also Memory hierarchy; Main memory
A remembered answer that is no longer true. On a real network a machine can move or an interface can change, so a cached pairing of network address and MAC address can become stale; implementations must revalidate or discard old mappings and resolve them again. The book's inventory never changes, so its cache does not expire.
Chapter 10.b See also ARP cache; ARP; Network interface; Address resolution
The wait a data hazard forces on a pipeline: an instruction that reads a value still being computed is held back, and the bubble it leaves delays everything behind it. Forwarding makes many stalls disappear.
Chapter 5.b, Figure 5.b.3 Try it See also Data hazard; Dependent chain; Hazard rule; Pipeline bubble; Pipeline schedule; Pipeline stage
The first line of an HTTP message, and the only part of its shape that differs between the two directions. A request's start line gives a method, a path and a version, as in GET /hello HTTP/1.0; a response's gives a version, a status and a reason, as in HTTP/1.0 200 OK.
Chapter 13, Figure 13.2 Try it See also Request and response; Status code; HTTP method; Request path; Reason phrase; HTTP version
What a circuit remembers of its past. A combinational circuit has none: its output depends only on the present inputs. Feedback lets a circuit hold itself in a state, and with both inputs LOW the SR latch sits in one of two stable states, which is exactly one bit of memory.
Chapter 4, Figure 4.2 Try it See also Feedback; SR latch; Combinational logic; Hold state; Memory; Mutable state
A piece of a program that changes the program's state, unlike an expression, which only computes a value. The book's language has two kinds: an assignment, name = expr ;, which binds an expression's value to a name that can later be reassigned, and a loop, while expr do ... end, which repeats a block while a condition holds.
Chapter 8, Figure 8.2 Try it See also Variable environment; Control flow; Assignment; Loop; Expression; Imperative language
The number in a response's start line, followed by a reason, as in HTTP/1.0 200 OK. The book's server answers a path it knows with 200 OK and that path's bytes, and any other with 404 Not Found, the status every reader of the web has met.
Chapter 13, Figure 13.2 Try it See also Request and response; Start line; Reason phrase; Request path
The instruction that copies the accumulator into a memory word, opcode 2, and the only one of the six instructions that writes to memory. The control unit enables the memory write for it. In the example program STORE 12 puts the sum, 42, into the result slot at address 12.
Chapter 5 Try it See also LOAD; Accumulator; Memory cell; Control signal
The idea that a program's instructions are data in addressable memory, alongside the numbers they operate on. To run a different program you write different bytes into memory; you do not touch the hardware.
Chapter 5, Figure 5.5 Try it See also Fetch-decode-execute cycle; Program; Memory image; Software
Instructions that run once each, in the order written, with no jump among them. The chapter starts from this shape: two jumps, one conditional and one not, turn a straight line of instructions into a loop. In its compiled program the four instructions before test0 form a straight line.
Chapter 8.a Try it See also Control flow; Unconditional jump; Conditional jump; Program counter; Fall-through
A piece of text held as one value in a program: a sequence of characters. The lexers of the next two languages return each token as a plain string, where this chapter's returns a Token(kind, value) pair, and their parsers recognize the kind from the string itself.
Chapter 6.b See also Character; Token; Token kind
An expression that forms part of a larger one. Parentheses mark it in the text, and in the tree it is a sub-tree: the a + b inside (a + b) + c is the left child of the outer addition. The book's parser descends into the parentheses and comes back with that sub-tree.
Chapter 7, Figure 7.2 Try it See also Expression; Nesting; Grouping; Term (of an expression)
The bit an adder writes in its own column, as distinct from the carry it passes on. For two bits it is their XOR: 1 when exactly one input is 1, and 0 when both are 1, where the sum wraps around and the carry records that 1 + 1 = 102.
Chapter 3, Figure 3.2 See also Half adder; Carry; XOR
The repeated active element of digital computing: a small voltage on a control line decides whether a second, signal line conducts. A transistor is such a switch, flipped by another wire rather than by hand.
Chapter 1, Figure 1.3 See also MOSFET; Open and closed switch; Control line; Transistor; Signal; Configurable interconnect
One programmable connection in a real FPGA's wiring: a transistor straddling two wires, its gate driven by a stored configuration bit. A signal crossing a mesh of switch points travels further and slower than one on a soldered wire, which is why an FPGA is typically several times slower than the same circuit cast in silicon.
Chapter 5.d See also Configurable interconnect; Configuration bit; Transistor; Wiring entry
Switches stacked end to end on one path, so current passes only when every one of them is closed. NAND's pulldown is two n-channel switches in series, which is why its output goes LOW only when both inputs are HIGH. Its two pull-up switches sit side by side instead, so either can conduct alone.
Chapter 1, Figure 1.5 Try it See also NAND; Pull-up and pull-down networks; Current; Open and closed switch
A name that stands for an address, as a linker sees it: a label one module defines and others may refer to. An import records that a position needs a symbol, and relocation fills in the symbol's address. The book's symbols are value, addend and result; defining one twice is an error.
Chapter 6.a Try it See also Symbol table; Global symbol table; Imports and exports; Undefined symbol; Symbol resolution
Replacing a name with the address it stands for. The book's assembler resolves a label its own module defines at once, to a local address; a label defined in another file it cannot resolve, so the operand stays blank until the linker has gathered every export and can look the name up.
Chapter 6.a, Figure 6.a.3 Try it See also Symbol; Local address; Relocation; Blank operand
The table from each label to its address, built during an assembler's first pass and consulted during the second to resolve label operands. For the book's sum program it holds a:1, b:2, c:3, result:4 and start:5.
Chapter 6, Figure 6.2 See also Assembly label; Two-pass assembler; Assembler; Global symbol table; Address assignment; Operand resolution
The half of a language that fixes its shape: the rules that say which texts are programs and how they are built. A parser applies them to turn text into a tree, which for the book's multiplication program holds two assignments and then a While whose body is two more.
Chapter 8, Figure 8.2 See also Grammar; Semantics; Abstract syntax tree; Grammar rule; Programming language
What a parser reports when the tokens do not fit the grammar. The book's parsers stop at the first token that cannot belong: another token where a group should close gives missing closing parenthesis, and tokens that run out early give unexpected end of input.
Chapter 7 Try it See also Parser; Grammar; Unexpected character
A request from a program to the kernel, made through a trap and named by number. The kernel looks the number up in its menu and runs the matching routine, so syscall(WRITE, 42) routes number 0 to the write routine, while a number with no entry is refused before anything runs.
Chapter 9.a, Figure 9.a.3 Try it See also Trap; Kernel; Request number; Menu of services; Return value; User program
The position in a stored table that the inputs select. A lookup table's two inputs, packed side by side, spell the index: with a = 1 and b = 0 they pick row 10, and the block's output is the bit stored there, read out and not computed. It is a RAM address by another name.
Chapter 5.d, Figure 5.d.3 Try it See also Lookup table; Truth table; RAM
The two outcomes of a branch: taken when execution goes to the branch's target, not-taken when it carries on with the next instruction. The book's predictor raises its counter by one for each taken outcome and lowers it by one for each not-taken outcome, and guesses whichever way the counter leans.
Chapter 5.b See also Branch; Branch predictor; Two-bit counter
Changing a message on its way between sender and receiver. The book's run flips one bit of the ciphertext, and the receiver refuses it with checksum mismatch: the message was tampered with. Catching that one edit proves little, since many different records share a one-byte checksum.
Chapter 13.a See also Keyed checksum; Integrity; Ciphertext; Intermediary
The machine a compiler writes its instructions for. This chapter's target is an idealised version of the book's CPU: the same LOAD, STORE, ADD, JZ, JUMP and HALT, one accumulator and one program counter, but LOAD may carry a literal, memory is named and unbounded, and arithmetic does not wrap at eight bits.
Chapter 8.a Try it See also Code generation; Named memory; Literal operand; Accumulator; Lowering
The real transport protocol whose heart is the acknowledgement-and-retry idea the book builds. Unlike the book's model it carries a persistent byte stream, relies on timers, and uses a cumulative acknowledgement, one number meaning everything up to here has arrived; its ACKs can be lost, so it may resend data that already arrived.
Chapter 12 See also Transport layer; Acknowledgement (ACK); Cumulative acknowledgement; ACK loss; Selective acknowledgement
The habit of programs to use again soon a word they have just used. A cache profits by keeping recently loaded lines close. The book's LOOP trace reads addresses 0 to 15 four times; its two lines stay cached after their first visits, giving 62 hits and only 2 misses.
Chapter 5.c See also Locality; Spatial locality; Cache
One of the pieces an expression joins with +. In the book's first grammar an expression is a sequence of terms, and a single term is a number, a name or a parenthesized expression; that last case sends the parser back to the expression method. The next chapter's grammar calls the same piece an atom.
Chapter 7 See also Expression; Recursive descent; Sub-expression; Grammar rule
The two labels a compiler plants around a loop. The test label marks the top, the point the loop returns to and re-checks its condition each time around; the done label marks the end, where JZ sends control when the condition is zero. The book numbers them per loop, so its one loop gets test0 and done0.
Chapter 8.a, Figure 8.a.2 Try it See also Assembly label; Code generation; Conditional jump; Unconditional jump
Lines that map to the same slot of a direct-mapped cache evicting one another on every visit. The book's THRASH trace visits lines 0, 4, 8 and 12, which all map to slot 0 of a four-slot cache, so it never hits, even though four lines would fit in four slots.
Chapter 5.c See also Direct-mapped cache; Cache hit and miss; Address trace; Eviction
The rule that chooses among routes of equal length. The book's breadth-first search visits neighbours in sorted order, so ties break the same way on every run. From A, the ways to F through B and through C are both three hops, and the routing table at A records B.
Chapter 11 See also Breadth-first search; Shortest path; Routing table; Next hop
Two inputs of one gate wired to the same signal, so that they always agree. Tie a NAND's inputs together and “both high” collapses to “input high”, so the output is the input inverted: NOT from a single NAND, which the chapter's program writes as nand(a, a).
Chapter 1, Figure 1.7 See also NAND; Inverter; Double inversion; Universal gate
One unbroken turn of a process on the processor. A slice lasts at most a quantum and ends early if the process halts partway through: with a quantum of three steps, the book's trace has four slices of 3, 3, 3 and 2 steps, the last one short because the pair finishes.
Chapter 9, Figure 9.3 Try it See also Scheduling quantum; Time-sharing; Round-robin scheduling; Fairness; Interleaving
Giving each program the processor for a brief slice and then moving on, so all of them make progress. With a quantum of three steps the book's adder and pair run 3, 3, 3 and 2 steps in turn; the processor never does two things at once, only one at a time, fast enough that both finish.
Chapter 9, Figure 9.3 Try it See also Scheduler; Scheduling quantum; Context switch; Interleaving; Round-robin scheduling; Time slice
A signal from a hardware timer that stops the running program and hands control back to the operating system. The book's scheduler does not need one, because it counts the steps of a simulated CPU from outside; a real operating system does, to regain control from a core that is actually running.
Chapter 9 See also Preemption; Scheduling quantum; Operating system
A model that keeps only when each step happens. The book's pipeline chapter uses one: a separate machine with several named registers and three one-cycle stages, whose instruction records say only which registers are read and written. It checks the hazard rule but does not prove that overlapping keeps the sequential result.
Chapter 5.b Try it See also Pipeline schedule; Pipeline; Hazard rule
The real protocol for a secure channel on the web, one that protects the bytes and establishes who is at the other end. It combines suitable key agreement and key derivation, authentication of the peer and handshake, and secure record protection; the book's toy models only key agreement and record encoding, and provides no real security.
Chapter 13.a See also Peer authentication; Diffie-Hellman key exchange; Encrypted record; Handshake; Key derivation; Secure channel
One piece of source text as a parser reads it: a kind paired with a value. The line total = 12 + 3 becomes five of them, NAME total, EQUALS, NUMBER 12, PLUS and NUMBER 3.
Chapter 6.b, Figure 6.b.2 Try it See also Lexer; Parser; Token kind; Scanning; Look-ahead; Character
The label on a token that says what sort of piece it is, apart from its text. The book's lexer pairs every value with a kind, and its run shows six: NAME, NUMBER, EQUALS, PLUS, LPAREN and RPAREN. Two tokens can share a kind and differ in value, as 12 and 3 do.
Chapter 6.b, Figure 6.b.2 Try it See also Token; Operator; String
The set of programs that turns a design into the form a machine loads. The chapter names one for the FPGA: a real toolchain compiles a netlist into the bitstream, so the description-as-data of the netlist chapter becomes configuration-as-data.
Chapter 5.d See also Netlist; Bitstream; Hardware description language; Compiler
The shape of a network: which machines exist and which links join them. Every table builder in the book receives the complete, static graph, so the topology is simply given. Discovering it, and updating routes after a link changes, are outside the book's model.
Chapter 11 See also Network graph; Routing table; Link; Node and edge
The physical switch the book's whole machine is wired from, a sandwich of doped silicon. An n-channel transistor sets two n-type wells, the source and the drain, in a p-type body, with a metal gate above the gap; read as a switch, the gate is the control line and the drain-to-source path is the signal it gates.
Chapter 1, Figure 1.3 Try it See also Switch; MOSFET; Source, drain and gate; Silicon; Switch point; Capacitor
A program that reads a program in one form and writes it out in another. The assembler is the book's first: its only job is to translate readable text into the words the CPU executes. It starts a chain of translators that, many chapters later, ends at a browser.
Chapter 6 See also Assembler; Compiler; Source code; Machine code
The property that a paused and resumed process cannot tell it was ever interrupted. Because the context switch saves and restores every register faithfully, the book's adder still ends holding 42 and its pair holding 9, exactly what each computes when run alone. That is what lets one machine pretend to be many.
Chapter 9 Try it See also Context switch; Interleaving; Process
A latch while its enable is HIGH: any change in d passes straight through to Q. If enable stays HIGH for a whole clock phase, Q can race through several values, and a circuit reading it may see a changing value instead of a settled one. The book calls this the transparency problem, and the flip-flop solves it.
Chapter 4, Figure 4.3 See also Gated D latch; Enable; Edge-triggered; Clock phase; Opaque latch
The layer that supplies the contract a best-effort network lacks: a successful download returns its bytes whole and in order, and failure is reported when that cannot be done. The book's model cuts a message into numbered segments, acknowledges and retransmits, and reassembles in order, over a channel that drops and reorders.
Chapter 12 See also Best-effort delivery; TCP; Segment; Layer; Reliable delivery
The only door from a program into the kernel. The program leaves a request number and an argument where the kernel will look, then runs a special instruction that hands control to the kernel in its privileged mode; the kernel does the work and returns. In the book, a Python method call stands for it.
Chapter 9.a, Figure 9.a.2 Try it See also System call; User mode and kernel mode; Mode bit; Return value
One point of a tree, holding a single piece of the program and joined to the nodes beneath it. The book's expression tree has three kinds: a number node, a variable node and an addition node with two children. The tree of (a + b) + c has five nodes, two additions and three variables.
Chapter 7, Figure 7.2 See also Abstract syntax tree; Root, child and leaf; Tree walk
Visiting the nodes of a tree one by one and doing some work at each. The book's interpreter walks the tree and computes as it goes; its compiler walks the same tree and emits assembly. The chapter notes that shell scripts and early BASIC interpreters ran in much this direct way, walking the source itself.
Chapter 7, Figure 7.3 Try it See also Interpreter; Abstract syntax tree; Recursion; Evaluation; Tree node
A listing of a gate's output for every combination of its inputs, one row each. NAND's reads 1,1,1,0 for inputs 00, 01, 10, 11, and whatever behaviour you can tabulate this way, you can build from NAND.
Chapter 1, Figure 1.6 Try it See also NAND; Boolean algebra; Logic gate; Boolean function; Input and output; Row detector
The value formed by inverting every bit of a number b and adding one. Adding it to a computes a - b with the adder alone: keep the fixed-width low bits and discard the final carry-out.
Chapter 3.a See also Binary long division; Fixed width; Minuend and subtrahend; Signed and unsigned; Wraparound
A counter with four states, 0 to 3, and the whole of the book's branch predictor. States 0 and 1, strongly and weakly not-taken, predict not-taken; states 2 and 3, weakly and strongly taken, predict taken. From a strong state two contrary outcomes change the prediction; from a weak state, one is enough.
Chapter 5.b See also Branch predictor; Taken and not-taken; Saturation; Branch misprediction; Warm-up
An assembler that reads its source twice so a label may be used before it is defined. Pass one assigns addresses and records every label in the symbol table without encoding anything; pass two encodes each line, looking label operands up, so JUMP start resolves though start is defined five lines later.
Chapter 6, Figure 6.2 See also Symbol table; Assembler; Address assignment; Operand resolution
A jump that is always taken: it sets the program counter to its label whatever the accumulator holds. The book's is JUMP. Placed after a loop's body, JUMP test0 sends control back to the test, and that return is what makes the body repeat; the conditional JZ is what lets the loop end.
Chapter 8.a, Figure 8.a.2 Try it See also Conditional jump; Branch; Loop; Program counter; Fall-through; Straight-line code
The error a linker reports when an import names a symbol that no object exports, so its blank can never be filled. The book's linker stops with undefined symbol and the missing name. The mirror-image mistake, two modules exporting one name, stops it with symbol defined twice.
Chapter 6.a See also Symbol; Imports and exports; Global symbol table
A wire that some gate reads but that no gate drives and no input supplies, so it never becomes known. It is one of two faults that stop the book's simulator: gates remain, none is ready, and it raises ValueError. The other fault is a set of gates that feed back into a loop.
Chapter 5.a See also Wire; Circuit simulator; Ready gate; Feedback
The lexer's error for a character that begins no token: not a space, a digit, a letter or a known symbol. The book's lexer rejects it at once and does not guess; given a stray ? it stops with the message unexpected character.
Chapter 6.b Try it See also Lexer; Character; Syntax error
A gate from which every other gate can be built. NAND is one: tie its inputs together for NOT, follow it with NOT for AND, feed it inverted inputs for OR, and any truth table follows from those.
Chapter 2, Figure 2.3 Try it See also NAND; Boolean function; Composition; Gate count; Row detector; Tied inputs
Eight bits read as a whole number with no sign, from 0 to 255. To match the CPU, the book's first language works in unsigned bytes: literals and inputs must lie in that range, and each addition keeps only its low eight bits, so 255 + 1 is 0 and 200 + 100 is 44.
Chapter 7 Try it See also Wraparound; Literal; Accumulator; Bit
An opcode value to which the instruction set gives no meaning. A 4-bit opcode has room for 16 operations and the book's CPU defines six, so ten are unused. The model rejects them with a ValueError and does not treat them as hidden instructions.
Chapter 5 See also Opcode and operand; Instruction set; Instruction decoder
The two sides of the protection boundary. A program runs in the restricted user mode, unable to touch resources directly; the kernel runs in the privileged mode where that work is done. A real processor enforces the boundary with a hardware mode bit; the book models it only by discipline.
Chapter 9.a, Figure 9.a.2 See also Kernel; Trap; Mode bit; Privilege; Protection; User program
A program running in the restricted mode, which gets outside work done only by asking the kernel. The chapter's example asks for its id, writes it, reads its two inputs, 40 and 2, and writes their sum, 42: five requests cross the boundary and it makes no direct resource access.
Chapter 9.a, Figure 9.a.2 Try it See also User mode and kernel mode; System call; Kernel
A name that stands for a value kept elsewhere. In the book's first language a variable is a leaf of the tree, and the interpreter looks it up in the environment, where a is 10, b is 20 and c is 12. The next language adds assignment, so a variable's value can change as the program runs.
Chapter 7, Figure 7.2 Try it See also Variable environment; Literal; Assignment; Binding; Program input
The mapping from variable names to values that an interpreter consults, and the only place a program's inputs enter. To run (a + b) + c, the book's environment binds a to 10, b to 20 and c to 12, so the tree evaluates to 42.
Chapter 7 See also Interpreter; Variable; Evaluation; Assignment; Binding; Dictionary
A hardware description language, the one the chapter names. A circuit too large to draw by hand is written as source in such a language; tools compile that source into a netlist, the gate-and-wire description, and a simulator tests the chip long before it is built in silicon.
Chapter 5.a See also Hardware description language; Netlist; Circuit simulator
An address as a program sees it, which translation turns into a physical address. It splits into a page number and an offset; with sixteen-cell pages, virtual address 3 is page 0, offset 3, and a table mapping page 0 to frame 5 gives physical address 5 × 16 + 3 = 83.
Chapter 9.c, Figure 9.c.2 Try it See also Page and frame; Page table; Physical address; Address translation; Page number and offset; Virtual memory
A machine built in software: a program that runs instructions the way a CPU would. The chapter mentions it as the way Python really runs, compiling source to bytecode and running that on a virtual machine, where the book's own interpreter walks the tree and never mentions an opcode.
Chapter 7 See also Bytecode; Interpreter; CPU; Python
A layer of translation that lets each program believe memory is its own. Each program uses virtual addresses numbered from zero, and every access passes through a page table to a physical frame, so two programs that both want address 3 need not collide.
Chapter 9.c, Figure 9.c.3 Try it See also Virtual address; Page table; Memory isolation; Address collision; Physical memory
The electrical level of a wire, the quantity a circuit reads as LOW or HIGH. A voltage put on a transistor's gate forms the channel; take it away and the channel vanishes. On a real wire it is continuous: it sags over distance and picks up noise from neighbouring wires.
Chapter 1, Figure 1.2 Try it See also LOW and HIGH; Signal; Noise; Field effect; Wire; Analog and digital
The first outcomes a predictor sees, before its state reflects how the branch usually behaves. The book's counter starts at 0, strongly not-taken, so it needs two taken outcomes before it predicts taken; after warming up on a loop that runs many times and leaves once, it misses mostly on the way out.
Chapter 5.b See also Two-bit counter; Branch predictor; Branch misprediction
A real program that answers HTTP requests, the grown-up version of the book's lookup server. It adds methods beyond fetching, headers that negotiate format and caching, and handlers that compute a page rather than look one up. None of that changes the idea: a request goes in, a response comes out.
Chapter 13 See also Client and server; Request handler; HTTP; Lookup server
What one place of a numeral is worth. Decimal places have weights 1, 10, 100 from right to left; binary places double instead: 1, 2, 4, 8. In the book's bit list [1, 0, 1, 1] the entries have weights 1, 2, 4 and 8, so it stands for 1 + 4 + 8 = 13.
Chapter 3 See also Binary numeral; Power of two; Least and most significant bit; Decimal; Bit position
The spaces between the pieces of a line of text. The book's lexer steps over each one without making a token, so spacing separates tokens but is never one itself, and names and numbers come out whole however the spacing falls.
Chapter 6.b Try it See also Lexer; Scanning; Token
A conducting connection that carries one signal between parts. The book's switch is flipped by another wire, not by hand. A real wire carries a continuous voltage that sags over distance and picks up noise, so the book reads every wire as only LOW or HIGH.
Chapter 1, Figure 1.3 See also Signal; Voltage; Control line; Noise; Undriven wire; Link
The exact bytes a message takes while it travels, as distinct from what the message means. HTTP/1.x uses the textual envelope the chapter builds, readable lines such as GET /hello HTTP/1.0; HTTP/2 uses binary framing. The wire representation is therefore not universal, while the request/response idea stays the same.
Chapter 13 See also HTTP; Message framing; HTTP version; Message encoding
One number in the book's bitstream that names where a block input gets its signal: a chip input or an earlier block's output. A two-block fabric has four. The half adder's are [0, 1, 0, 1], both blocks reading the chip inputs; [0, 1, 2, 2] makes block 1 read block 0 twice.
Chapter 5.d, Figure 5.d.5 Try it See also Bitstream; Configurable interconnect; Chip input; Fabric; Feed-forward circuit; Switch point
What a fixed-width register does when a sum needs more bits than it keeps: the extra carry is discarded and only the low bits remain. The accumulator keeps eight bits, so its value wraps around at 256: adding 1 to 255 leaves 0, and adding 255 to a nonzero value decrements it.
Chapter 5 See also Accumulator; Two's complement; ADD; Fixed width; Saturation; Overflow
The control input that turns a memory access into a write. To write to the chapter's RAM you assert the data and the address and raise the write line; the selected register then loads the data input at the next clock edge. A read needs neither the write line nor an edge: its path is combinational.
Chapter 4, Figure 4.6 Try it See also RAM; Load line; Assert; Memory address; Control signal
The step in which an instruction's computed result is stored into its destination register. The book's three-stage model has no separate write-back stage: a value exists once its instruction's execute has run. A real pipeline has one, and forwarding spares the instruction behind from waiting for it.
Chapter 5.b See also Forwarding; Register; Pipeline stage
XOR with its output inverted, so it outputs 1 when its two inputs are equal. For inputs 00, 01, 10, 11 its outputs are 1, 0, 0, 1; like the chapter's other gates, the book builds it from NAND calls alone.
Chapter 2 Try it See also XOR; Truth table
The gate whose output is 1 when its two inputs differ, written a ⊕ b. The book builds it from four NANDs in three levels, and in the adder it computes the sum bit.
Chapter 2, Figure 2.3 Try it See also Half adder; Sum bit; XNOR; Bitwise operation; Keystream; Generator polynomial
The check of whether the accumulator holds 0. In the book's datapath its result goes to the control unit, which needs it for JZ: if the accumulator is 0 the branch is taken and the operand becomes the program counter; if not, the already-advanced counter stands.
Chapter 5 See also JZ; Accumulator; Control unit; Branch
