#!/usr/bin/env python3 """Generate the hands-on markdown pages from the scripts and their REAL output. Every code block on every generated page is sliced out of the corresponding hNN_*.py file, and every output block is captured by executing that file. There is no hand-copied output anywhere in the generated pages: run this again and any number that drifted will change on the page. python3 build_pages.py # regenerate all pages python3 build_pages.py h04 # regenerate one """ import io import os import re import subprocess import sys import textwrap HERE = os.path.dirname(os.path.abspath(__file__)) OUT = os.path.dirname(HERE) # the book root PY = sys.executable # ───────────────────────────────────────────────────────────────────────────── # Per-page framing. Everything else on the page is generated from the script. # ───────────────────────────────────────────────────────────────────────────── PAGES = { "h01_transformer": dict( num="P01", slug="p01", title="Transformer, block by block", project="p01-transformer.md", blurb="Attention from a dot product, then a language model that trains.", intro=""" Every line of this page runs. The file builds a decoder-only transformer out of nine independent pieces, each of which proves one mechanism on its own before anything is stacked, and then trains the assembled model on a real corpus until the loss falls to 0.11 nats. The order is deliberate. Attention is introduced as a *weighted average whose weights are computed from the data*, which is all it is, and only then do the scaling factor, the causal mask, and multiple heads get added --- each one motivated by a failure you can see in the numbers of the block before it. The same discipline applies to the training loop: the overfit test in the assembly exists because a language model that cannot memorise sixty tokens has a bug that no amount of hyperparameter tuning will fix. Read the outputs, not just the code. Block 3 shows what the `sqrt(d_k)` denominator is actually protecting you from, and it is not obvious from the formula.""", close=""" ### What to do with this Run it, then break it. Delete the `/ sqrt(dk)` and watch block 3's entropy collapse. Remove the causal mask and watch the loss drop below the entropy of the data --- the classic leakage bug, which looks like brilliant training. Change the initialisation scale and see how far it moves the trainable range. Each of those is a two-character edit with a visible, measurable consequence, which is the fastest way to build the intuition that reading the paper alone will not.""", ), "h02_ann": dict( num="P02", slug="p02", title="Approximate nearest neighbours, block by block", project="p02-ann-index.md", blurb="Why a random graph fails, why a navigable one works, and what recall costs.", intro=""" This is the project where the *baseline* teaches more than the algorithm. Brute force is trivially correct and its cost is knowable in advance; everything an index does is buy latency by giving up recall, so the only interesting question is the exchange rate. The file builds that comparison honestly. It measures relative contrast on the data before touching an index, because a dataset with low contrast has no nearest neighbour worth finding and no graph will rescue it. It then builds a deliberately random graph to show that connectivity alone is worthless, and only then the navigable small-world construction that makes greedy descent work. The two-factor model in the assembly is the point of the whole exercise: it predicts the speedup from first principles and lands on the measured number.""", close=""" ### What to do with this The parameter that matters most is the one this file leaves at a default. Sweep `M` (edges per node) rather than `ef` and you will find the memory/recall curve that most benchmark tables omit entirely. Then re-run the contrast measurement on a real embedding set --- CLIP or a sentence encoder --- and compare it with the synthetic number here. If the real contrast is lower, every recall figure you have read about that dataset is easier than it looks.""", ), "h03_vectordb": dict( num="P03", slug="p03", title="Vector database, block by block", project="p03-vector-database.md", blurb="An index is not a database: filtering, persistence, and a planner that chooses.", intro=""" An index answers one question. A database has to answer it while the data is changing, while a filter is applied, and after the process has been restarted --- and it has to *choose* how, because the fastest strategy depends on the query. That choice is what this page builds toward. Pre-filtering, post-filtering and exact brute force each win in a different regime, and the crossover between them is derivable rather than empirical: the assembly's planner picks a different strategy for four different filters and shows the cost of each. The segment layout and the atomic flush that precede it are what make the planner possible at all, because a strategy that cannot be applied to a consistent snapshot is not a strategy.""", close=""" ### What to do with this Add a fourth strategy: an index built per filter value. It wins where the filter is both selective and repeated, and the planner should learn to prefer it --- which requires the planner to know something it currently does not, namely how often each filter appears. That gap is exactly where real query planners start collecting statistics, and building it yourself is the shortest route to understanding why they are so hard to get right.""", ), "h04_lsm": dict( num="P04", slug="p04", title="LSM storage engine, block by block", project="p04-lsm-engine.md", blurb="Durability first, then the Bloom filter that makes reads survivable.", intro=""" The order of this file is the order the mechanisms have to be built in. The write-ahead log comes first, because a storage engine that loses acknowledged writes is not a storage engine and every later optimisation is meaningless without it. The crash test in the assembly is therefore not a nice extra: it is the only result on the page that would make the others worth reading. After durability comes the read path, and the read path is where the design earns its name. Writes are cheap because they are appended; reads are expensive because a key could be in any run. The sparse index, the Bloom filter, and compaction are three different answers to that one problem, and the file measures each of them separately so you can see how much each actually buys.""", close=""" ### What to do with this The measurement to add is write amplification under a sustained random-write load, which is the number that decides whether an LSM is the right structure at all. Then implement levelled compaction alongside the tiered scheme here and watch the RUM trade move: levelling cuts read amplification and raises write amplification, and the crossover depends on your read/write ratio rather than on anyone's benchmark.""", ), "h05_distkv": dict( num="P05", slug="p05", title="Distributed key-value store, block by block", project="p05-distributed-kv.md", blurb="Leader election and log replication under loss, duplication and partition.", intro=""" Consensus is hard to learn from the paper because the paper describes the protocol that works, not the failures that force each rule to exist. This file inverts that. It builds a message network that can drop, duplicate and delay, then adds the Raft rules one at a time and shows what breaks when each is missing. The election-safety argument is the clearest example. One vote per term plus a majority quorum gives at most one leader, and the file demonstrates it under a partition rather than asserting it --- including the case where a single round elects nobody at all, which is why real Raft retries on a randomised timeout instead of assuming success.""", close=""" ### What to do with this The rule this file does not exercise hard enough is §5.4.2 --- a leader may not commit an entry from a previous term by counting replicas. Construct the scenario: an entry replicated to a majority under an old term, a new leader, a crash before the new leader appends anything of its own. Then remove the rule and watch a committed entry disappear. It is the subtlest correctness argument in the protocol and the one most implementations get wrong.""", ), "h06_mapreduce": dict( num="P06", slug="p06", title="MapReduce framework, block by block", project="p06-mapreduce.md", blurb="Why a restricted programming model is what makes fault tolerance possible.", intro=""" MapReduce is usually taught as a way to process large data. It is more usefully understood as a bargain: you give up arbitrary computation, and in exchange the framework may re-run any task, anywhere, at any time, without asking you. This file makes that bargain concrete. The assembly runs the same job with three different worker-failure schedules and gets byte-identical output every time, which is possible only because map and reduce are pure functions of their input. The atomic-rename commit is what extends that guarantee to the outside world: duplicate task attempts produce one file, so at-least-once execution becomes exactly-once effect. The straggler simulation at the end is the part most implementations skip, and it is where the wall-clock time actually goes.""", close=""" ### What to do with this Replace the in-process tasks with real subprocesses and a coordinator that detects a dead worker by timeout rather than by return value. The moment tasks can fail *silently* rather than by raising, the design pressure changes completely --- and that is the environment the original paper was written for.""", ), "h07_streaming": dict( num="P07", slug="p07", title="Stream processing, block by block", project="p07-streaming.md", blurb="Event time, watermarks, and the accuracy/latency dial made explicit.", intro=""" The hardest idea in stream processing is that correctness is a parameter. A batch job is either right or wrong; a streaming job is right *as of* a certain completeness assumption, and the assumption is yours to choose. This file builds the machinery that makes the choice explicit. Two clocks, window assignment that depends only on event time, watermarks as a falsifiable promise about completeness, and triggers that emit the same window repeatedly as more data arrives. The assembly then runs one pipeline under three policies --- dashboard, alerting, billing --- and shows the same code producing 93.6% accuracy in two seconds or 100% in a hundred. The checkpoint block is what makes any of it survivable, and it is smaller than most people expect: state and input offset advance together, or not at all.""", close=""" ### What to do with this Add a session window. It is the first window type whose *boundaries depend on the data*, so a late event can merge two windows that were already emitted --- which forces retractions into the design rather than leaving them optional. Every comfortable assumption from the tumbling-window case breaks, and the exercise is the fastest way to understand why the Dataflow model separates windowing from triggering.""", ), "h08_recsys": dict( num="P08", slug="p08", title="Recommender system, block by block", project="p08-recommender.md", blurb="Three of four models lose to popularity. This page is about why.", intro=""" This page is mostly a record of being wrong, which is why it is the most useful of the fifteen. The plan was straightforward: build matrix factorisation, beat the popularity baseline, show the two-stage architecture. What the measurements said instead was that an under-regularised model scores *below* popularity, that copying word2vec's negative-sampling constant makes it worse still, that more training makes it worse rather than better, and that the whole question of how much a model can win is decided by a property of the data rather than by the model. Every one of those findings is in the file, with the experiment that produced it and, where a mechanism was proposed, a prediction tested against a measurement. Block 6 is the clearest case: a theory about `p(i|u)/q(i)`, a prediction it implies, and a verdict of *partially confirmed* with the residual explained.""", close=""" ### What to do with this Run block 8 on your own data. Estimate the head mass --- what fraction of interactions go to the top 1% of items --- before writing any modelling code. It tells you the size of the prize, and it is the single cheapest analysis in this entire curriculum. If the answer is that popularity explains most of the behaviour, the correct engineering decision may be to ship the bincount.""", ), "h09_simulator": dict( num="P09", slug="p09", title="Recsys simulator, block by block", project="p09-simulator.md", blurb="Feedback loops, position bias, and a bandit that loses for a findable reason.", intro=""" A simulator exists to answer the question an A/B test cannot: what would have happened under a policy nobody ran? Its answers are only as good as its user model, so the model has to be stated at the top and stress-tested at the bottom. Between those two, this file demonstrates the feedback loop that gives recommender systems their characteristic pathology --- a greedy policy narrows its own catalogue from 599 items to 96 while every individual step is locally optimal --- and then measures what exploration costs to prevent it. The best block is the one where the textbook answer fails. Thompson sampling loses badly to greedy here; the file forms a hypothesis about why, derives a prediction from it, tests the prediction with a modified policy, and confirms it --- and then block 7 independently confirms the same mechanism from a completely different direction.""", close=""" ### What to do with this Add supplier-side utility and re-run every policy. A marketplace has two populations whose interests do not coincide, and exposure inequality --- the gini column that greedy maximises --- stops being an aesthetic concern and becomes the thing that drives sellers off the platform. That is a question no offline metric can answer and a simulator can.""", ), "h10_abtest": dict( num="P10", slug="p10", title="A/B testing platform, block by block", project="p10-ab-testing.md", blurb="Peeking, SRM, CUPED, and the type-M error that inflates every underpowered win.", intro=""" The statistics in an experimentation platform are twelve lines. Everything else --- and everything that makes it valuable --- is process enforced by software instead of remembered by people under launch pressure. This file builds both. Deterministic hash assignment, a sample-size calculator that kills impossible tests before anyone writes the feature, an A/A calibration suite that validates the platform against itself, and then the four failure modes that produce most false launches: peeking, sample-ratio mismatch, uncorrected multiple comparisons, and underpowered tests whose surviving estimates are inflated by construction. The assembly runs one experiment end to end in the order a real launch uses: power, health checks, one primary metric, variance reduction --- and a note on what peeking would have done to it.""", close=""" ### What to do with this Implement a sequential test --- mSPRT or an always-valid confidence sequence --- and re-run block 4 against it. The false-positive rate should stay at 5% no matter how many times the dashboard is checked, which is the only real fix for peeking, because "do not look" is not a policy that survives contact with an organisation.""", ), "h11_language": dict( num="P11", slug="p11", title="Programming language, block by block", project="p11-language.md", blurb="A lexer, a Pratt parser, two backends, and a textbook optimisation that loses.", intro=""" The interesting part of this file is not that it implements a language. It is that the standard next step after a tree-walking interpreter --- compile to bytecode, run a VM --- makes the program *slower*, and that finding out why is more instructive than the speedup would have been. The investigation is the model for how to handle any performance surprise. Count what actually executes. Notice that dispatch is an if/elif chain of string comparisons, so an opcode's cost depends on its position. Compute the mean comparisons per dispatch under the current ordering and under a frequency-sorted one. Predict a ratio. Reorder the branches, measure, and compare the delivered gain against the predicted one --- then explain the gap rather than ignoring it. The conclusion is not "bytecode is slow". It is that an optimisation's benefit lives in the host's cost model, and porting a design without porting the cost model ports nothing.""", close=""" ### What to do with this Port the VM loop to C with a computed-goto dispatch table and run the same two programs. That is where the textbook's speedup lives, and measuring it in both hosts is the clearest possible demonstration that "which algorithm is faster" is an incomplete question.""", ), "h12_kernel": dict( num="P12", slug="p12", title="Operating system kernel, block by block", project="p12-kernel.md", blurb="Frames, page tables, Bélády's anomaly, scheduling, and a race you can watch.", intro=""" You cannot boot a kernel inside a Python process, but every mechanism a kernel depends on can be built and measured in one --- and the mechanisms are the part that transfers. This file builds eight of them and ends with the observation that a process control block is simply one field per mechanism. Two results are worth arriving for. Bélády's anomaly is demonstrated rather than described: FIFO with four frames faults more often than with three, on the classic 1969 reference string, which is why "add more cache" is a hypothesis rather than a fix. And the assembly's page-fault sweep contradicts its own prediction --- there is no working-set cliff, because a mixture of reference distributions does not have one, and that turns out to be the more useful lesson.""", close=""" ### What to do with this The next step is xv6 or an equivalent, on real hardware or QEMU, where the page tables are the CPU's rather than a dictionary. Everything here transfers, and what does not transfer --- the fact that a wrong page table halts the machine instead of raising an exception --- is precisely the part that makes kernel work feel different.""", ), "h13_tensor": dict( num="P13", slug="p13", title="Tensor framework, block by block", project="p13-tensor-framework.md", blurb="Reverse-mode autodiff that matches PyTorch to 5.6e-17 over 300 steps.", intro=""" Autodiff is bookkeeping, not calculus, and this file is structured to make that obvious. Each operator records how to push a gradient to its inputs; `backward()` replays the recording in reverse topological order. There is no symbolic differentiation anywhere and no numerical differentiation in the training path. The blocks that follow are the three things that actually go wrong: gradient accumulation on a diamond in the graph, un-broadcasting on the backward pass, and the absence of a check that would have caught either. Block 3 corrects a claim I made without testing it --- the failure mode of a missing un-broadcast is not what I assumed, and the real one is considerably more dangerous. The reward is in the assembly: 400 lines of numpy training a network step for step alongside PyTorch, agreeing to machine precision after 300 optimisation steps.""", close=""" ### What to do with this Add a fused operator --- `linear_relu` as one node with one backward --- and measure it against the two-node version at several tensor sizes. The gain is entirely in avoided intermediate allocation and dispatch, so it should track block 8's overhead curve exactly. If it does not, the model of where the time goes is incomplete.""", ), "h14_hardware": dict( num="P14", slug="p14", title="Hardware-aware ML, block by block", project="p14-hardware-aware.md", blurb="Two measured numbers predict a workload, and two modelling bugs get caught.", intro=""" A roofline is two measured numbers and a claim: no kernel can run faster than its arithmetic intensity times the machine's bandwidth, or than the machine's peak compute, whichever is lower. The claim is falsifiable, which is the whole point --- a measurement that beats it is proof that the *model* is wrong. This page catches two such bugs. The first version measured peak throughput in fp64 and priced an fp32 workload against it, a factor of four, and the assembly duly reported kernels running at twice the speed of light. The second is subtler and lives in the byte count: a 25 MB working set that stays in cache never pays the DRAM cost the model charges it, and the ratio wanders across 1.0 from run to run as a result. Both were invisible in the absolute timings. Both were unmissable the moment the number was divided by a bound it could not legally cross.""", close=""" ### What to do with this Apply it to something you already run. Count the FLOPs and the bytes on paper, measure the two machine constants once, and predict the runtime before you measure it. The value is not the prediction --- it is that a ratio far from 1.0 tells you which of your assumptions is wrong, and it does so before you have spent a week optimising a kernel that was already at its bound.""", ), "h15_integrated": dict( num="P15", slug="p15", title="The integrated system, block by block", project="p15-integrated.md", blurb="Five earlier projects, imported rather than reimplemented, wired into one service.", intro=""" Nothing on this page is reimplemented. Every mechanism is imported from the hands-on file that built it --- the NSW index from P02, the Bloom-filtered LSM runs from P04, the windowing and watermarks from P07, the assignment and statistics from P10, the measured roofline from P14 --- because importing them is the only honest test of whether they compose. The first attempt failed with a `KeyError`. I had assumed the ANN module exported `build_nsw` and `search_nsw`; it exports `greedy`, `graph` and `entry`. That failure is left in the page deliberately, because it is the normal cost of integration and it is the thing a curriculum of separate exercises can otherwise hide from you. What the assembled system produces is a table that is a product decision: recall against latency against throughput, with a hardware ceiling beside each row saying how much of the machine is being left unused.""", close=""" ### What to do with this Close the last loop. The service currently chooses `ef` offline; make block 5's experiment choose it, and block 6's stream monitor detect when the choice stops working. At that point the three loops --- offline hypothesis, online experiment, production monitor --- are closed around the same system, which is the actual deliverable of the final project and the thing that distinguishes a portfolio of exercises from an engineered system.""", ), } ORDER = list(PAGES.keys()) def project_titles(): """Read the canonical project titles out of SUMMARY.md so they stay in sync.""" out = {} for line in open(os.path.join(OUT, "SUMMARY.md")): m = re.match(r"\s*- \[(.+?)\]\(projects/(.+?)\)", line) if m: out[m.group(2)] = m.group(1) return out PTITLE = project_titles() def load_notes(slug): """Per-block annotations from notes/.md, split on '### B' headers. A note may contain <<>> and <<>> placeholders; whatever it does not contain is appended, so a note can be pure prose or a full layout. """ path = os.path.join(HERE, "notes", slug + ".md") if not os.path.exists(path): return {} out, cur, buf = {}, None, [] for line in open(path): m = re.match(r"^### B(\d+)\s*$", line) if m: if cur is not None: out[cur] = "".join(buf).strip() cur, buf = int(m.group(1)), [] continue if cur is not None: buf.append(line) if cur is not None: out[cur] = "".join(buf).strip() return out def slice_blocks(src): """Return [(n, title, teaches, code)] plus the assembly source.""" out = [] pat = re.compile(r'^@block\((\d+), "(.*?)", "(.*?)"\)$', re.M) marks = [(m.start(), int(m.group(1)), m.group(2), m.group(3)) for m in pat.finditer(src)] asm = src.index("\ndef assembly(") for i, (pos, n, title, teaches) in enumerate(marks): end = marks[i + 1][0] if i + 1 < len(marks) else asm out.append((n, title, teaches, src[pos:end].rstrip())) tail = src.index('\nif __name__ == "__main__":') return out, src[asm:tail].strip() def capture(path): """Run the script and split its stdout into per-block bodies + assembly.""" r = subprocess.run([PY, path], capture_output=True, text=True, cwd=HERE) if r.returncode != 0: raise SystemExit(f"{path} failed:\n{r.stdout[-3000:]}\n{r.stderr[-3000:]}") txt = r.stdout bodies, asm = {}, "" cur, buf = None, [] for line in txt.splitlines(): m = re.match(r"^BLOCK (\d+) — ", line) if m: if cur is not None: bodies[cur] = buf cur, buf = int(m.group(1)), [] continue if line.startswith(" ASSEMBLY — "): if cur is not None: bodies[cur] = buf cur, buf = "asm", [] continue if cur is None: continue if line.startswith("teaches: ") or set(line.strip()) in ({"·"}, {"─"}, {"="}): continue if re.match(r"^\[block \d+ ok, ", line): bodies[cur] = buf; cur, buf = None, [] continue buf.append(line) if cur is not None: bodies[cur] = buf asm = bodies.pop("asm", []) trim = lambda ls: "\n".join(ls).strip("\n") return {k: trim(v) for k, v in bodies.items()}, trim(asm) def anchor(title): a = title.lower() a = re.sub(r"[^a-z0-9 -]", "", a) return a.replace(" ", "-") def build(key): meta = PAGES[key] path = os.path.join(HERE, key + ".py") src = open(path).read() blocks, asm_src = slice_blocks(src) outputs, asm_out = capture(path) L = [] w = L.append w(f"# {meta['num']} hands-on — {meta['title']}") w("") w(f"> {meta['blurb']}") w(">") w(f"> Source: [`handson/{key}.py`]({key}.py) --- run it with " f"`python3 handson/{key}.py` ") w(f"> Full project spec: [{PTITLE.get(meta['project'], meta['project'])}]" f"(../projects/{meta['project']})") w("") w(textwrap.dedent(meta["intro"]).strip()) w("") w("## Contents") w("") for n, title, _, _ in blocks: w(f"- [Block {n} — {title}](#block-{n}--{anchor(title)})") w("- [The assembly](#the-assembly)") deep_path = os.path.join(HERE, "deep", meta["slug"] + ".md") if os.path.exists(deep_path): for h in re.findall(r"^## (.+)$", open(deep_path).read(), re.M): w(f"- [{h}](#{anchor(h)})") w("- [Running it](#running-it)") w("- [What to do with this](#what-to-do-with-this)") w("") w("## How to read this page") w("") w("Each block below is a self-contained lego piece: it builds one mechanism, " "proves it works on its own, and returns what the next block needs. The " "code is the real source, sliced out of the script. The output underneath " "it is the real output, captured by running that script --- not " "transcribed, not idealised. Where a measurement contradicted what I " "expected, the contradiction is in the output and the prose says so.") w("") w("The assembly at the end wires every block into one working thing and " "measures it.") w("") notes = load_notes(meta["slug"]) for n, title, teaches, code in blocks: w(f"## Block {n} — {title}") w("") w(f"**Teaches:** {teaches}") w("") body = outputs.get(n, "").rstrip() code_md = "```python\n" + code + "\n```" out_md = ("**Output:**\n\n```text\n" + body + "\n```") if body else "" if n in notes: # The annotation IS the block's layout: it says where code and output # go, so the dissection can be interleaved rather than appended. sec = notes[n] if "<<>>" not in sec: sec = sec.rstrip() + "\n\n<<>>\n\n<<>>" if "<<>>" not in sec: sec = sec.rstrip() + "\n\n<<>>" sec = sec.replace("<<>>", code_md).replace("<<>>", out_md) w(sec.strip()) w("") else: w(code_md) w("") if out_md: w(out_md) w("") w("## The assembly") w("") w("Every block above, wired together into one working system:") w("") w("```python") w(asm_src) w("```") w("") w("Output:") w("") w("```text") w(asm_out) w("```") w("") deep = os.path.join(HERE, "deep", meta["slug"] + ".md") if os.path.exists(deep): w(open(deep).read().strip()) w("") w("## Running it") w("") w("```bash") w(f"python3 handson/{key}.py # every block, then the assembly") w(f"python3 handson/{key}.py --block 3 # just block 3 and its prerequisites") w(f"python3 handson/{key}.py --quiet # the assembly only") w("```") w("") w(textwrap.dedent(meta["close"]).strip()) w("") w("---") w("") w(f"Milestones, experiments, readings and exit criteria for this project: " f"[{PTITLE.get(meta['project'], meta['project'])}]" f"(../projects/{meta['project']}).") w("") dest = os.path.join(OUT, "handson", f"{meta['slug']}.md") os.makedirs(os.path.dirname(dest), exist_ok=True) open(dest, "w").write("\n".join(L)) return dest, len("\n".join(L)) def main(): want = sys.argv[1:] or ORDER keys = [k for k in ORDER if any(w in k for w in want)] for k in keys: dest, size = build(k) print(f"{k:<18} -> {os.path.relpath(dest, OUT):<28} {size/1024:>6.1f} KB") if __name__ == "__main__": main()