M3 The front end

[tamnd]

Roughly eight weeks. Lessons F01 through F12, source text to code object. This is where the first of CPython's three machine readable self specifications gets taught properly: the PEG grammar generates the parser, and ASDL generates the AST.

Exit criterion. BP-CODEOBJ is complete enough that a reader implements a line table and exception table decoder in a language of their choice, from the blueprint alone, and it agrees with CPython across the whole standard library. Tested by actually having someone do it, not by opinion. compile_explorer is live and diffs 3.13, 3.14 and 3.15.

Content

• F01 through F12: the tokenizer, f strings, the PEG parser, the AST, the symbol table, the code generator, the CFG, the optimizer, the assembler, code objects, line and exception tables, and marshal

Blueprints

• BP-TOK, BP-FSTR, BP-GRAMMAR, BP-AST, BP-SYMTAB, BP-CFG, BP-CODEOBJ, BP-MARSHAL

Artifacts

• The compile_explorer app with multi version diffing
• Golden corpora for tokens, ast, symtable, bytecode, linetable, exctable and marshal

Gates

• Whether Tools/peg_generator can run in the browser on a toy grammar, which decides whether F03 is a live experiment or a recording

[tamnd]

F01 is in, as #116.

It is the first lesson of this milestone and the fifteenth overall. T02 already covered the tokenizer from Python, so F01 is deliberately only about the C: where the token numbers come from, the four constructors and the single function pointer they differ in, the eight fields of struct tok_state that carry state between lines, the pendin counter, and why some tokenizer error messages are written in lexer.c and others get their words from a switch in pegen_errors.c a hundred lines away.

Twenty cells, six diagrams, fifteen citations at v3.15.0rc1, and one Tier 1 experiment that runs a debug build with -d to show the tokenizer refilling its one line buffer. A file that parses cleanly is read once. A file with an unclosed bracket is read three times, because a good error message costs a re-read. That recording came out byte identical on arm64 and amd64.

Two glossary terms added, coding cookie and underflow, which puts the glossary at 89.

The content checklist here is a single line covering F01 through F12, so it stays unticked until F12. Progress so far is 1 of 12. F02, f-strings in the lexer, is next and is already in progress. It picks up the one field of struct tok_state that F01 skipped, tok_mode_stack.

One thing worth writing down while it is fresh: the citation grammar cannot express a path with no file extension, so Grammar/Tokens had to be described in prose rather than linked. That will come up again in F03 for Grammar/python.gram's neighbours. Filing it separately.

[tamnd]

F02, f-strings in the lexer, is merged in #118. That is 2 of the 12 lessons on the front end line.

The lesson picks up the one field of struct tok_state that F01 deliberately left alone, tok_mode_stack, and the small language the lexer switches into when it meets an f-string. Nine tokens where a plain string would be one.

Everything in it is observable from a stock interpreter, which took some finding. The mode stack cannot be printed, so its two depth limits are located by growing the source until it stops compiling: 149 nested f-strings, and 3 nested fields inside a format spec. The brace counting shows up as a one column gap in the token positions where a doubled brace was collapsed. The private copy the lexer keeps of your source text is sitting in plain view in the output of any f-string ending in an equals sign, and in Interpolation.expression for t-strings.

The sharpest cell is the one for escape decoding. f\"a\\nb\" and rf\"a\\nb\" produce byte identical FSTRING_MIDDLE tokens and different AST constants, which is about as direct a proof as you can get that the lexer is not the thing making that decision.

Seven claims, none unobservable. Six diagrams, three new glossary terms.

One thing worth flagging for anyone touching that lesson later. ruff format normalises whitespace inside f-string expressions, and one cell exists specifically to show that the spacing survives. The f-strings in that cell are stored as string literals and passed to eval, with a comment in the cell saying why.

[tamnd]

F03, the parser nobody wrote, is merged in #119. That is 3 of the 12 lessons on the front end line, and it answers the open gate above, which is now ticked.

The gate asked whether Tools/peg_generator could run in the browser on a toy grammar. It cannot, and not because of Pyodide. pegen is a plain Python package that ships only inside the CPython source tree, so there is no installed interpreter anywhere that can import it, in a browser or otherwise. F03 therefore uses a Tier 1 recording, f03-a-parser-nobody-wrote.

That turned out better than a live cell would have been. The recording prints the real ratio, 1645 lines of grammar against 39486 lines of generated C, then points the same generator at an 11 line arithmetic grammar and gets 117 lines of Python back. It shows the generated @memoize_left_rec def expr with the grammar rule copied above it as a comment, and then parses three expressions with the parser it just wrote. Only the timing line is marked as measured, and the rest was checked identical on arm64 and amd64.

The lesson itself stays observable from a stock interpreter throughout. keyword.__doc__ names the grammar file and the command that regenerates it, which is the opening evidence and needs no checkout. Associativity is read off ast: 1 - 2 - 3 leans left, 2 ** 3 ** 4 leans right, a < b < c comes back flat, and all three follow from which side of its own rule a rule names itself on. Soft keywords get a cell that uses match as a variable and as a statement four lines apart. Error messages get four mistakes that produce a specific message, each cited to the grammar line the string is written on, plus one control case that gets the generic invalid syntax because nobody has written that rule yet.

Three new glossary terms: parser generator, soft keyword and left recursion. GLOSSARY.md is at 95.

Next up is F04, the AST, which is the second generated thing in a row.

[tamnd]

F04, the tree is generated too, is merged in #120. That is 4 of the 12 lessons on the front end line.

Two generated things in a row was not a coincidence, and the lesson says so. F03 was the parser coming out of Grammar/python.gram. This one is the tree the parser builds coming out of Parser/Python.asdl, which is 154 lines with no code in it at all.

The thing that keeps it distinct from T03 is the direction. T03 used the AST. F04 asks where ast.BinOp came from, and the answer is that _fields is the schema read back, because the ast module is itself one of the generator's outputs. Every cell reads the schema through the module rather than through the file.

Worth recording for later lessons: the sums and products cell has to filter six classes the generator still emits for code written before 3.9, Suite, AugLoad, AugStore, Param, Index and ExtSlice. They are not in the schema and nothing the parser builds is ever one of them. That filter is a named constant with a comment saying why, because anyone reading the cell will otherwise wonder where mod got five alternatives from when the file lists four.

The validator section is the one I would point a reimplementer at. Three broken trees give three complaints and the first is a different species. required field "lineno" missing from stmt comes out of generated conversion code, and its format string is cited to the line of asdl_c.py that writes it. The other two come from _PyAST_Validate and enforce rules a schema has no way to state, like a target list not being empty. Anyone building a compatible front end needs both layers, not just the schema.

Two new glossary terms, sum type and product type. GLOSSARY.md is at 97.

Next is F05, the symbol table.

[tamnd]

F05 is merged in #121. The symbol table, which is the first pass the compiler runs on the tree and the only one that produces no code at all.

The opening is five programs that ast.parse accepts without a word and compile refuses. nonlocal x at module level is the cleanest of them: the grammar has a rule for it, the parser matches it, a tree comes back, and only then does the compile fail. That is a direct demonstration that a pass sits between the two, and that it is the pass that knows about scopes.

The rest of the lesson reads the answers back out of the symtable module, which wraps the same C structures the compiler uses.

• Five scope constants in a header, and every name in every block is exactly one of them. The repr prints both the scope and the DEF_ flags the first walk collected, so you can see the input and the conclusion side by side.
• The decision is per block, not per line. print(x) with x = 1 four words later makes x local for the whole function, so the compiler emits LOAD_FAST_CHECK. Delete the assignment and the same line becomes LOAD_GLOBAL. That is where UnboundLocalError actually comes from.
• CELL and FREE are two ends of one wire. co_cellvars and co_freevars on the finished code objects are this pass's answers written down a second time, and total is not in outer.co_varnames at all.
• The one name the pass adds for you. Reading the name super inside a method makes __class__ a free variable of it, so a method that only mentions super and never calls it still gets the cell, and one that reaches the same builtin as builtins.super() gets nothing and fails at run time.

Every cell was run on 3.14 and 3.15.0rc1. One difference showed up: 3.15 reworded duplicate argument to duplicate parameter, so that cell carries a note.

Six diagrams, five claims all observable, fifteen citations into Python/symtable.c, Python/compile.c and Include/internal/pycore_symtable.h. Two new glossary terms, symbol table pass and class cell, taking GLOSSARY.md to 99. The browser probe is at 21 lessons and 242 cells, all of which run on Pyodide.

Next is F06, the code generator. It walks the same tree this pass just walked, and every time it meets a name it asks F05 what to do.

[tamnd]

F06 is merged in #122. The code generator, which is the third of the five compiler passes and the first one that emits anything.

The opening is that there is no and instruction. Search the opcode table and it is not there, and it never was. What you get instead is a copy of the left hand value, a TO_BOOL and a jump past everything after it. Short circuiting is a compile time behaviour, written out by hand in twenty five lines of C, and the interpreter never sees a boolean operator at all.

The rest of the lesson makes the same argument in four more places.

• One branch of a switch per node kind, and the branches are tiny. The one covering every arithmetic operator you have ever written is three lines: visit the left, visit the right, emit the operator.
• The shape a node compiles to does not depend on where the node is. The same base + 1 at module level, inside a function and inside a nested function emits the same BINARY_OP every time, and the only instruction that moves is the load of the name. The generator did not work that out either, it called into the symbol table on one line.
• Evaluation order falls out of the order the walk visits children in. For an assignment that means the value before the target, which is why box[key] = value runs the value first, and why a chained assignment runs its value exactly once.
• Dead code is emitted in full. if False gets the constant, the test, the jump and the whole unreachable branch, twelve instructions where the finished code object has six.
• Some instructions in your function belong to no line of your source, and dis prints a dash where the line number goes. MAKE_CELL and COPY_FREE_VARS are the two ends of the wire F05 ended on, turned into instructions.

The lesson also adds pyxray.compiler.innermost_codegen, which follows nested instruction sequences down to the innermost code unit. It exists because a disassembly is not a fair picture of what this pass produced: on 3.15 the optimizer rewrites the generator's LOAD_FAST into LOAD_FAST_BORROW, so a lesson about the third pass that used dis would be showing the fourth. Three tests, one of which pins exactly that.

Six diagrams, six claims all observable, ten citations into Python/codegen.c and Python/compile.c. Two new glossary terms, short circuiting and evaluation order, taking GLOSSARY.md to 101. The browser probe is at 22 lessons and 250 cells.

Next is F07, the control flow graph. The flat list this pass produced becomes a graph of blocks, and questions that were unanswerable about a list become easy: which code can never run, how deep the stack gets, and which blocks are only ever reached by an exception.

[tamnd]

F07, the list becomes a graph, is merged in #123.

The fourth compiler pass. F06 handed over a flat list of instructions and a promise that something later would tidy it up, and this is the pass that turns that list into a control flow graph, works in that shape for a while, and then flattens it back down.

The hook is a four line function whose disassembly runs 5, then 8, then back to 6. The return that comes last in the source is compiled ahead of the handler in the middle of it, and nothing is wrong.

What the lesson covers:

• Three rules for where a basic block starts, written out as a splitter in Python that agrees with dis. Twenty one instructions in a loop fall into six blocks, and the one instruction block is FOR_ITER.
• The basicblock struct field by field, with the warning that b_next is the next block in memory rather than the next one control flow reaches.
• A try compiling out of source order, with the exception table at the bottom of the disassembly as the closest thing to an edge that survives into a code object.
• Unreachable code going because nothing points at its block. The while True case is the nicest: the block the jump would have skipped to has no way in, so it goes, and the reason for the test goes with it.
• Stack depth. Adding dis.stack_effect up along the flat list gets co_stacksize right for three functions and gives 3 where the answer is 4 for the one with a handler, because a handler starts one deeper than empty. That is the sharpest reason the pass needs a graph at all.
• push_cold_blocks_to_end, and the JUMP_FORWARD the pass has to add where a cold block used to fall through into a warm one.
• The flattening, and what is left: bytes, one number that took a graph walk to work out, a table of ranges, and co_branches, which looks like it might be the graph and is a flat list of offsets for coverage tools.

Six diagrams. Two new glossary terms, cold block and stack depth, taking the glossary to 103. Twelve citations, all against the pinned tree. Every cell run on 3.15.0rc1 and 3.14, with four notes where they differ.

The F01 through F12 line is now six of twelve done. Next is F08, the optimizer: what actually happens in the middle, while the graph is in that shape.

[tamnd]

F08, the optimizer, is merged in #124.

This is the pass that runs while the graph from F07 is in that shape, and the angle the lesson takes is that there is nothing clever in it. Every rewrite is small and local, and most of them have a number in them that somebody picked and wrote down.

Constant folding is the one you can feel from outside. 2 ** 64 is worked out at compile time and 2 ** 65 is not, and the difference is a #define of 128 near the top of the folding code. There are four such limits, and the lesson walks across all four boundaries: 128 bits for an integer, 256 items for a collection, 4096 characters for a string, and 1024 items counting nested ones. The integer one is an estimate rather than a measurement, bit length times exponent, because measuring would mean doing the expensive thing first.

The nicest find is the docstring rule. Fold 1000 * 1000 in a module with no docstring and the leftover 1000 stays in co_consts forever. Put a docstring on the module and it goes. The reason is two lines of C with a comment saying the first constant may be the docstring, so slot zero is always kept, and you can see the whole thing from Python in three lines.

The rest of the lesson is jump threading, the pass that deletes a jump by copying the four instruction ending it pointed at, the three superinstruction pairs and the two conditions they need, and the graph walk that decides whether a local read gets LOAD_FAST_BORROW or LOAD_FAST_CHECK. That last one is the only real analysis in the pass, and it is why UnboundLocalError is not checked for on every local read.

Two glossary terms this lesson needed already existed, but the constant folding entry was wrong. It said folding happens twice, once on the tree and once on the graph. Python/ast_opt.c does not exist in 3.15, and ast.parse("x = 6 * 7") still shows an unfolded BinOp on 3.14 too, so all of it now runs on the graph. Fixed in the same PR.

Eighteen cells, six diagrams, twelve citations into Python/flowgraph.c. Five claims, all observable.

Eight of twelve on the F01 through F12 line. F09, the assembler, is open in #125.