Watch a compiler think

In university I took a compilers course built on Aarne Ranta's Implementing Programming Languages. Over a semester I wrote a compiler in Haskell for a subset of C++: a grammar, a type checker, and a code generator that emits JVM bytecode. This post takes that compiler apart, one stage at a time.

The figures below are the compiler, not drawings of it. A compiler is much easier to watch than to read about, so the programs are editable: change one and you can see the tokens, the tree, the types and the bytecode change with it, then step a small JVM through the instructions that come out. Nothing here is a mockup or a simplification for the page. Section 08 covers how I know that.

The whole thing is four transformations in a row.

flowchart LR
    chars --> tokens --> AST --> typedAST["typed AST"] --> instructions

01 · The language

The subset is small but real: int, double, bool and void, functions with arguments and recursion, while, if/else, blocks, and the usual operators. The book calls this little language CPP. Ranta is blunt about the name: it's a small part of the immense language C++, but it could just as well be called C or Java. Here's the heart of the grammar, written for BNFC, the grammar compiler the book builds on:

DInit.    Decl ::= Type Id "=" Exp ";" ;
SWhile.   Stm  ::= "while" "(" Exp ")" Stm ;
SIfElse.  Stm  ::= "if" "(" Exp ")" Stm "else" Stm ;

ETimes.   Exp12 ::= Exp12 "*"  Exp13 ;
EPlus.    Exp11 ::= Exp11 "+"  Exp12 ;
ELt.      Exp9  ::= Exp9  "<"  Exp10 ;
EAnd.     Exp4  ::= Exp4  "&&" Exp5 ;
EAss.     Exp2  ::= Exp3  "="  Exp2 ;

That isn't Haskell, by the way, even though the compiler around it is. It's BNFC's own notation, a grammar file, and it's the only part of the front end I wrote by hand. Each line is one rule: a constructor name, then the shape of the text it matches. From seventy-odd rules like these, BNFC generates the entire front end: a lexer spec for Alex, an LALR parser spec for Happy, the Haskell types for the syntax tree, even a pretty printer. I never wrote a lexer or a parser. I wrote a grammar and got both for free.

The numbers after Exp are worth a second look, because they encode precedence. EPlus lives at level 11 and only accepts a level 12 expression on its right, so * binds tighter than + before any code runs. One thing is missing on purpose: there's no unary minus, so negative numbers only exist as 0 - x. The grammar is the spec. If a rule isn't there, the construct doesn't exist.

The lab below parses exactly this grammar, which is why it turns down if without else.

02 · Chars to tokens to tree

The first two transformations run in the lab below. Type in the program box and watch both panels follow.

The lexer turns the character stream into tokens. It knows that whilee is a name and while is a keyword, that <= is one token and not two, and that comments aren't anything at all (they get dropped right here, which is why no later stage has to think about them). Each token remembers which characters it came from. Those spans look like bookkeeping, but they're what turns "type error" into "type error here".

The parser turns tokens into a tree, using the grammar's constructor names as node names. This is where precedence stops being a convention and becomes shape: 2 + 3 * 4 puts ETimes under EPlus, and (2 + 3) * 4 flips them. The parentheses themselves don't survive parsing. Their only job is choosing the shape, and once the shape exists there's nothing left for them to do.

Try breaking it. Delete a semicolon and the parser stops at the exact token that surprised it. Write if without else and it turns it down: this language only has SIfElse. The counter strip up top keeps score: how many chars became how many tokens became how many nodes became how many instructions, and where the pipeline stopped if it stopped.

03 · What the checker knows that the parser doesn't

The parser happily accepts double d = 5;. It's grammatically perfect. The type checker rejects it, because this language has no implicit coercions: every rule demands the exact type, and an int is not a double, not even when it obviously could be. That reads like pedantry, and it does cost you convenience, but it's what makes the next stage possible.

The checker does two passes. First it collects every function signature, which is why main can call a function defined below it. Then it walks each body with a stack of scopes, checking every expression against the declared types. When something doesn't fit, it stops at the first error and points at the span where the reasoning broke.

The checker is only the first of three nets, though, and the gallery below lines all three up. The first row of programs gets caught at compile time. The last two sail through the checker and still die: one at class load, when the verifier vetoes it, and one at run time, mid-output. Pick them and watch who says no, and when:

Rejecting bad programs is only half the checker's job, and honestly the less interesting half. On success, the checker rewrites the tree so that every expression node carries its type. The parser built EPlus, and the checker turns it into EPlus : int or EPlus : double. Look at the AST panel in the lab above: those cyan annotations weren't there after parsing. That annotated tree is the entire interface between the front end and the back end, because + on ints and + on doubles are different machine instructions, and something has to know which one to emit.

The checker is short enough to read end to end. It's also the first Haskell in this post, the grammar in section 01 being BNFC's notation rather than a program, so it's worth half a minute on how to read the stuff. Four idioms carry almost all of it, and this function has three of them:

lookupVar :: Env -> Id -> Err Type
lookupVar (_, [])   x = fail ("variable " ++ show x ++ " is not defined")
lookupVar (s, c:cs) x = case Map.lookup x c of
    Nothing -> lookupVar (s, cs) x
    Just t  -> return t

The :: line is a type signature and nothing else: lookupVar takes an Env and an Id and hands back either a Type or an error. The two lines under it are the same function, written twice. A Haskell function is a list of equations, one per shape its input can have, and the first one that matches is the one that runs. The shapes here are the scope stack: (_, []) matches a stack with no scopes left to search, so the name is undefined, and (s, c:cs) matches a stack with at least one, binding c to the innermost scope and cs to everything behind it. An underscore means "something goes here and I don't care what". Then case ... of handles the two things a map lookup can answer, Nothing or Just t.

That's why these files look strangely flat if you're coming from C or Python. There are no if ladders and no early returns, just a run of one-liners, each one handling a single case of the input. For a compiler that turns out to be exactly the right shape, because "one case per kind of node" is the entire job. A file of forty equations is forty tree nodes being handled, not forty steps happening in sequence.

The fourth idiom arrives in section 04: a do block runs steps in order, and x <- step names the result of one. That's how state moves through the code generator. emit and newLabel read like they mutate something global, and underneath the notation they're threading an environment from each step to the next.

Both files below are complete, nothing elided. Env.hs is the scope stack the checker walks with, and TypeChecker.hs is the rules themselves.

One thing to notice when you open the second one, because it's the difference between the two jobs I just described. Its entry point is typecheck :: Program -> Err (). The () is Haskell for "nothing useful", so this version only answers yes or no: it walks the tree, proves every expression has a type, and then throws all of it away. It's a checker and nothing more. Handing the annotated tree to the back end means changing that signature to Err Program and having every case return the node it just typed, ETyped e t, instead of only the type t. Same walk, same rules, same order, but the results get threaded out instead of dropped. That second version is what section 04 is reading from, and going from one to the other is mostly typing. The distinction has a name, checking versus elaboration, and it's the reason real compilers rarely stop at yes or no. Proving the program is well typed and writing down what you proved are two different things, and only the second one is worth anything to the stage after you.

module Env where

import AbsCPP
import PrintCPP
import ErrM

import qualified Data.Map.Strict as Map

-- A signature of every function, plus a stack of variable scopes.
type Env = (Sig,[Context])
type Sig = Map.Map Id ([Type],Type)
type Context = Map.Map Id Type

lookupVar :: Env -> Id -> Err Type
lookupVar (_, [])  x = fail ("variable "++ show x ++" is not defined")
lookupVar (s, c:cs) x = case Map.lookup x c of
    Nothing -> lookupVar (s, cs) x
    Just t -> return t

lookupFun :: Env -> Id -> Err ([Type], Type)
lookupFun (s, _) f = case Map.lookup f s of
    Nothing -> fail ("function "++ show f ++" is not defined")
    Just p -> return p

updateVar :: Env -> Id -> Type -> Err Env
updateVar (_, []) _ _ = fail "there is no context I can update"
updateVar (s, c:cs) x t = case Map.lookup x c of
    Nothing -> return (s, Map.insert x t c:cs)
    Just _ -> fail ("cannot redeclare variable "++ show x)

updateFun :: Env -> Id -> ([Type],Type) -> Err Env
updateFun (s, cs) f p = case Map.lookup f s of
    Nothing -> return (Map.insert f p s, cs)
    Just _ -> fail ("cannot redeclare function "++ show f)

newBlock :: Env -> Env
newBlock (s, cs) = (s, Map.empty : cs)

emptyEnv :: Env
emptyEnv = (Map.empty, [Map.empty])

module TypeChecker where

import AbsCPP
import PrintCPP
import ErrM
import Env

import Control.Monad

typecheck :: Program -> Err ()
typecheck (PDefs defs) = do
    env' <- addFunctionsSignaturesToEnv emptyEnv defs
    checkDefs env' defs

-- Pass 1: collect every function signature, so a call can precede its definition.
addFunctionsSignaturesToEnv :: Env -> [Def] -> Err Env
addFunctionsSignaturesToEnv env [] = return env
addFunctionsSignaturesToEnv env (DFun typ f args stms:defs) = do
    haveRepeatedArgs args
    env' <- updateFun env f (map aux args,typ)
    addFunctionsSignaturesToEnv env' defs
    where
        aux :: Arg -> Type
        aux (ADecl typ _) = typ

haveRepeatedArgs :: [Arg] -> Err ()
haveRepeatedArgs [] = return ()
haveRepeatedArgs ((ADecl _ id):args) = do
    if (isIdAlreadyExistADecl id args)
        then fail "The arguments have repeated names"
        else haveRepeatedArgs args

isIdAlreadyExistADecl :: Id -> [Arg] -> Bool
isIdAlreadyExistADecl _ [] = False
isIdAlreadyExistADecl id ((ADecl _ i):xs) = id == i || isIdAlreadyExistADecl id xs

-- Pass 2: walk every body against the signatures collected above.
checkDefs :: Env -> [Def] -> Err ()
checkDefs env defs = mapM_ (checkDef env) defs

checkDef :: Env -> Def -> Err ()
checkDef env (DFun typ _ args stms) = do
    env' <- addArgumentsToEnv env args
    checkStms typ env' stms
    return ()

addArgumentsToEnv :: Env -> [Arg] -> Err Env
addArgumentsToEnv env [] = return env
addArgumentsToEnv env (ADecl typ x : args) = do
    env' <- updateVar env x typ
    addArgumentsToEnv env' args

checkStms :: Type -> Env -> [Stm] -> Err Env
checkStms _ env [] = return env
checkStms typ env (stm:stms) = do
    env' <- checkStm typ env stm
    checkStms typ env' stms

checkStm :: Type -> Env -> Stm -> Err Env
checkStm _ env (SExp e) = do
    _ <- inferExp env e
    return env
checkStm t env (SDecls typ (i:is)) = do
    env' <- updateVar env i typ
    case is of
        [] -> return env'
        _  -> checkStm t env' (SDecls typ is)
checkStm _ env (SInit typ x e) = do
    checkExp env e typ
    updateVar env x typ
checkStm t env (SReturn e) = do
    typ <- inferExp env e
    if (t == typ)
        then return env
        else fail "The return type does not match the function type"
checkStm Type_void env SReturnVoid = do return env
checkStm _ _ SReturnVoid = do fail "Cannot return void because the function is not of type void"
checkStm t env (SWhile e stm) = do
    etyp <- inferExp env e
    if (etyp == Type_bool)
        then checkStm t env stm
        else fail "The expression inside the While is not of type Boolean"
checkStm typ env (SBlock stms) = do
    checkStms typ (newBlock env) stms
    return env
checkStm t env (SIfElse e stm1 stm2) = do
    etyp <- inferExp env e
    if (etyp == Type_bool)
        then do
            checkStm t env (SBlock [stm1])
            checkStm t env (SBlock [stm2])
        else fail "The evaluated expression is not of type Boolean"
checkStm _ _ _ = fail ("Invalid statement")


inferExp :: Env -> Exp -> Err Type
inferExp _ ETrue = return Type_bool
inferExp _ EFalse = return Type_bool

inferExp _ (EInt _ ) = return Type_int
inferExp _ (EDouble _ ) = return Type_double
inferExp _ (EString _) = return Type_string

inferExp env (EId x) = do
    t <- lookupVar env x
    return t

inferExp env (EApp f es) = do
    (ts, t) <- lookupFun env f
    inferExpAppAux env es ts
    return t

inferExp env (EPIncr e) = inferSimpleOp env e "increment applied to wrong argument"
inferExp env (EPDecr e) = inferSimpleOp env e "decrement applied to wrong argument"
inferExp env (EIncr e) = inferSimpleOp env e "increment applied to wrong argument"
inferExp env (EDecr e) = inferSimpleOp env e "decrement applied to wrong argument"

inferExp env (ETimes e1 e2) = inferBinOp env e1 e2 [Type_int, Type_double] "multiplication applied to wrong arguments"
inferExp env (EDiv e1 e2) = inferBinOp env e1 e2 [Type_int, Type_double] "division applied to wrong arguments"

inferExp env (EPlus e1 e2) = inferBinOp env e1 e2 [Type_int, Type_double, Type_string] "addition applied to wrong arguments"
inferExp env (EMinus e1 e2) = inferBinOp env e1 e2 [Type_int, Type_double] "subtraction applied to wrong arguments"

inferExp env (ELt e1 e2) = inferBoolBinOp env e1 e2 [Type_int, Type_double] "less than applied to wrong arguments"
inferExp env (EGt e1 e2) = inferBoolBinOp env e1 e2 [Type_int, Type_double] "greater than applied to wrong arguments"
inferExp env (ELtEq e1 e2) = inferBoolBinOp env e1 e2 [Type_int, Type_double] "less or equal applied to wrong arguments"
inferExp env (EGtEq e1 e2) = inferBoolBinOp env e1 e2 [Type_int, Type_double] "greater or equal applied to wrong arguments"

inferExp env (EEq e1 e2) = inferBoolBinOp env e1 e2 [Type_int, Type_double, Type_bool] "Equals applied to wrong arguments"
inferExp env (ENEq e1 e2) = inferBoolBinOp env e1 e2 [Type_int, Type_double, Type_bool] "Not equals applied to wrong arguments"

inferExp env (EAnd e1 e2) = inferBoolBinOp env e1 e2 [Type_bool] "And applied to wrong arguments"
inferExp env (EOr e1 e2) = inferBoolBinOp env e1 e2 [Type_bool] "Or applied to wrong argument"

inferExp env (EAss (EId x) e) = do
    t <- lookupVar env x
    checkExp env e t
    return t
inferExp _ (EAss _ _ ) = fail "Error tried to assign to a non-variable expression"

inferExpAppAux :: Env -> [Exp] -> [Type] -> Err ()
inferExpAppAux _ [] (_:_) = fail "applied the function with fewer arguments than expected"
inferExpAppAux _ (_:_) [] = fail "applied the function with more arguments than expected"
inferExpAppAux _ [] [] = return ()
inferExpAppAux env (e:es) (t:ts) = do
    checkExp env e t
    inferExpAppAux env es ts

inferSimpleOp :: Env -> Exp -> String -> Err Type
inferSimpleOp env e mess = do
    typ <- inferExp env e
    if typ `elem` [Type_int, Type_double]
        then do
            return typ
        else
            fail mess

inferBinOp :: Env -> Exp -> Exp -> [Type] -> String -> Err Type
inferBinOp env e1 e2 typs mess = do
    typ <- inferExp env e1
    if typ `elem` typs
        then do
            checkExp env e2 typ
            return typ
        else fail mess

inferBoolBinOp :: Env -> Exp -> Exp -> [Type] -> String -> Err Type
inferBoolBinOp env e1 e2 typs mess = do
    typ <- inferExp env e1
    if typ `elem` typs
        then do
            checkExp env e2 typ
            return Type_bool
        else fail mess

checkExp :: Env -> Exp -> Type -> Err ()
checkExp env exp typ = do
    typ2 <- inferExp env exp
    if typ /= typ2
        then fail ("expecting type "++ show typ ++" but got "++ show typ2)
        else return ()

04 · Expressions become stack code

Ranta opens his code generation chapter with a name for what has to happen next: the semantic gap. Statements and expressions become instructions, variables become memory addresses, control structures become jumps, tree structure becomes linear structure. His point is that machine code is simpler than source code, and that's what makes the crossing possible. The compiler mostly gets there by throwing source-level information away.

The JVM is a stack machine: instructions pop their inputs off an operand stack and push their result back. That choice is what makes the rest of this section short. On a machine with registers, the compiler has to decide where every intermediate value lives, and when two of them can share a register, which is an entire field of its own. A stack machine has one answer for every value: it goes on top. So compiling an expression tree comes down to one idea, postorder. Emit the children first, then yourself.

Five instructions come out of 2 + 3 * 4, and the operand stack tells the whole story:

Notice that imul never names its operands. It takes whatever the two instructions before it left behind. The tree is gone, flattened into a list, but its shape survives in the order. And because the rule is recursive, it scales from 2 + 3 to anything the parser can build.

That's not my paraphrase of the compiler, by the way, it's what the compiler literally says. Here's the multiplication case, straight out of Compiler.hs:

compileExp (ETyped (ETimes exp1 exp2) t) = do
  compileExp exp1
  compileExp exp2
  if t == Type_int
    then emit "imul"
    else emit "dmul"

That first line is one of the equations from section 03, and everything interesting happens in it. The pattern (ETyped (ETimes exp1 exp2) t) says: this equation only handles a multiplication node, and while matching it, pull the two operands out into exp1 and exp2 and the type annotation into t. Matching and unpacking are the same step, which is why there's no node.left anywhere in this compiler. ETyped is the wrapper the checker added, so the back end never sees an unannotated node.

The body is then the whole strategy: compile the left child, compile the right child, emit one instruction, and let the annotation pick which one. emit does nothing cleverer than push a string onto the list of instructions being built up.

Or don't take my word for the walk. The figure below does it in front of you: the tree, the visit order, the instruction each visit emits, and the stack the instructions will later produce. Step through it, then switch to the parenthesized version and watch the same five instructions come out in a different order because the tree changed shape:

The figure below is the code generator running on whatever program the lab holds. Hover an instruction and the source that produced it lights up. Hover a piece of source and its instructions light up. A click (or a tap, on a phone) pins the link so it survives your cursor leaving. And when you edit the lab, the instructions that changed flash as they land. Every instruction in this post's figures traces back to a span of your program, because the compiler carries those spans all the way through.

A few things worth hovering. The annotation at work: initialize a double and you get dstore where an int got istore, and that choice is the checker's annotation getting spent. A function call: invokestatic Main/fac(I)I, where (I)I is the JVM's type descriptor spelling of "takes an int, returns an int" (D is double, Z is bool, V is void). And an assignment used as an expression emits a dup before storing, because a = b = 5 needs the value to survive the first store. When the statement is done with it, a pop throws it away.

One inconsistency you'll spot: pushing the constant 1 happens three different ways in this compiler. There's a ladder of instructions for getting a small number onto the stack, and each rung is cheaper than the one above it. ldc is the general one: it takes an index and fetches the value from the class file's constant pool, so the number has to be stored somewhere else in the file first. bipush carries the value itself as one byte of argument, so anything from -128 to 127 needs no pool entry at all. iconst_1 carries no argument whatsoever: the value is baked into the opcode, one byte for the whole instruction. The book mentions the ladder and then tells you to emit ldc everywhere anyway, because a code generator that picks the right rung is a code generator with a special case in it. Mine took the advice for integer literals, ignored it for true and false, which come out as bipush 1 and bipush 0, and ignored it again for ++, which reaches all the way down to iconst_1. Three answers to one question, which is what happens when the schemes get written a week apart.

05 · Control flow becomes labels and jumps

A tree has no loops, so while has to be built out of the only control flow a flat instruction list has: named positions and jumps to them. My compiler emits this shape (this is its real output for the while loop program, only condensed):

label0:            ; test
  …condition…
  ifeq label1      ; false (0) jumps out
  …body…
  goto label0      ; back to the test
label1:            ; out

That shape isn't a diagram I drew for the post. It's the entire while case, verbatim:

compileStm (SWhile exp stm) = do
  test <- newLabel
  end <- newLabel
  emit (test ++ ":")
  compileExp exp
  emit("ifeq " ++ end)
  compileStm stm
  emit ("goto " ++ test)
  emit (end ++ ":")

test <- newLabel is the <- from earlier: it asks the environment for a label number nobody has used yet and names it. After that it reads top to bottom. Two fresh labels, the test, the escape hatch, the body, the jump home. Nine lines, and you have loops.

The JVM has no booleans on the stack, just ints, so false is 0 and ifeq reads "jump if the value equals zero", which makes it the "if false" instruction.

if/else is the same trick with one more label, and the shape is worth seeing next to the loop:

  …condition…
  ifeq label1      ; false: skip the then-branch
  …then…
  goto label0      ; jump over the else-branch
label1:
  …else…
label0:

Two labels again. Don't read anything into the numbers, by the way: labels are numbered when the compiler asks for them, not by where they end up, so label0 sits at the top of the loop and at the bottom of the branch. What matters is the direction. The loop's second jump goes backwards, and this one goes forwards, and that is the entire distinction between a loop and a branch at this level.

From here on, the bytecode figures draw the jumps for you. Every goto and every if grows an arc in the margin pointing at its label, the way disassemblers have always done it. A loop is the arc that points backwards. Once you see that, you can read a listing's control flow without reading a single instruction. (Every opcode also explains itself on hover, with the meaning the JVM specification gives it.)

The condition itself uses the cleverest scheme in the book. To compute i < 3 as a value with a single label, push the answer before asking the question:

bipush 1           ; optimistically push "true"
iload 1            ; i
ldc 3
if_icmplt label2   ; if i < 3, jump: the 1 is already correct
pop                ; otherwise throw the 1 away
bipush 0           ; and push "false"
label2:

if_icmplt pops both operands, so whichever path runs, exactly one value is left: the answer. Doubles can't use these int comparisons. They go through dcmpg, which collapses two doubles into an int (negative, zero or positive) that the int jumps can then look at. The g in the name is its NaN policy: dcmpg answers 1 for NaN, its sibling dcmpl answers -1. The book leaves the double comparison schemes as an exercise, so the dcmpg sequences in these figures are mine.

Ranta shows exactly this comparison-inside-a-while output, calls it terrible spaghetti code, and then shows the tight version a smarter compiler produces: jump on the negated comparison directly and the whole bipush dance disappears. So why doesn't this compiler emit that? Because every scheme here is compositional. A node compiles knowing only its own children, never the context it sits in. i < 3 can't know it's feeding a while, so it dutifully manufactures a boolean that ifeq consumes one instruction later. The book's verdict is to keep the schemes dumb and clean the output in a separate optimization pass, because non-compositional cleverness doesn't scale.

So I wrote the pass: a peephole that recognizes the compare-then-immediately-test pattern and folds it into one negated jump. Below, the while program before and after, both actually executed (same output on my VM and on OpenJDK 8, ten fewer steps per run):

&& and || compile to jumps too, and that's all short-circuit evaluation is. safe(6, 2) || safe(1, 0) never calls the second function if the first answers true, because a jump carries execution right past the call. In the short circuit program that's not a style preference, it's the difference between working and crashing: the skipped call would divide by zero.

One confession. Compile the short circuit program and read the emitted ||: my compiler emits goto label9 twice in a row. The second one can never execute. No path reaches it and the JVM never complains, so it sat there unnoticed for years. Compilers are software, and software collects dust in the corners.

06 · The bookkeeping nobody talks about

In between the elegant transformations sits an accountant, and nothing works without it. It's a single record that the State monad threads through the entire code generator:

data Env = Env {
  funs      :: Map.Map Id FunType,
  vars      :: [Map.Map Id Int],    -- one map per open block: name -> slot
  maxvars   :: [Int],               -- next free slot, per open block
  maxstk    :: Int,                 -- meant to hold the deepest the stack gets
  labels    :: Int,                 -- counter for jump labels
  code      :: [Instruction]
}

That's a record declaration: six named fields, and Env is the one value carrying all of them. Everything the rest of this section talks about is one of those fields. Look at vars in particular: it's a stack of maps, one per open block. That's how a name finds its slot, and how a slot gets recycled the moment its block ends.

Variables become slot numbers. Each method invocation gets a frame with a local variable array, and the spec says parameters land in consecutive slots starting at 0. Names die at compile time. iload 1 means "push slot 1", and which variable that is depends entirely on the compiler's ledger. The stepper below keeps that ledger visible as dim little names next to the slot numbers, but don't be fooled: the machine never sees them, and slot 2 will happily change its name mid-run when a block ends. There's also a squatter in main, because slot 0 holds the String[] args the JVM passes to every entry point, which is why your first variable lives in slot 1.

Blocks recycle slots. When a block ends, its variables are gone, so their slots are free. In the blocks and slots program, y gets slot 2, its block ends, and z gets slot 2 again. Two different variables, two different types, same slot, no conflict, because their lifetimes can't overlap.

Doubles cost two. A double occupies two consecutive local variables and is addressed by the lesser index, and on the operand stack it contributes two units to the depth. That's why in the doubles program d lands in slot 1, sum starts at slot 3 instead of 2, and n ends up in slot 5, and why pop has a big sibling pop2.

Someone has to compute the maximum. A frame is allocated in one shot when a method is called, so the class file has to declare up front the deepest the operand stack will ever get and how many local slots the method needs: the max_stack and max_locals of the Code attribute, fixed at compile time. A careful compiler works them out by simulating stack depth through every path. The book offers an out, "one can use rough limits such as 1000", and my compiler took it: .limit stack 1000 and .limit locals 1000 on every method, every time. Look back at that Env record. maxstk is right there, declared and initialized to 0, and then never touched again. I built the drawer for the honest number and never put anything in it. Nothing breaks, the JVM just allocates comically oversized frames. The stepper below graphs the stack depth of every step as a little sawtooth, and the dashed line is its peak, which is exactly the max_stack that unused field should have held. Click anywhere on the graph to jump to that moment and see how much was left on the table.

That is every field in Env accounted for. Here is the whole file those fields live in, the code generator that sections 04 through 06 have been quoting a few lines at a time.

module Compiler where

import AbsCPP
import TypeChecker

import qualified Data.Map as Map
import Control.Monad
import Control.Monad.Trans.State.Lazy

type Instruction = String
type FunType     = String
type Label       = Int

data Env = Env {
  funs      :: Map.Map Id FunType,
  vars      :: [Map.Map Id Int],    -- one map per open block: name -> slot
  maxvars   :: [Int],               -- next free slot, per open block
  maxstk    :: Int,                 -- deepest the operand stack gets (never filled in)
  labels    :: Int,                 -- counter for jump labels
  code      :: [Instruction]
}

emptyEnv :: Env
emptyEnv = Env { funs=Map.empty,
                 vars=[],
                 maxvars=[0],
                 maxstk=0,
                 labels=0,
                 code=[]}

-- Append one instruction. The list is built backwards and reversed at the end.
emit :: Instruction -> State Env ()
emit i = do
  env <- get
  put (env { code = i : code env })

typeSize :: Type -> Int
typeSize Type_double = 2
typeSize _           = 1

-- Give a variable the next free slot in the innermost block, and move the
-- block's counter past it (by two, for a double).
extendVar :: Type -> Id -> State Env ()
extendVar t i = do
  env <- get
  put (env { vars = Map.insert i (head (maxvars env)) (head (vars env)) : tail (vars env)
           , maxvars = head (maxvars env) + typeSize t : tail (maxvars env)
           }
      )

extendVars :: Type -> [Id] -> State Env ()
extendVars t ids = mapM_ (extendVar t) ids

typeJVM :: Type -> String
typeJVM Type_int    = "I"
typeJVM Type_double = "D"
typeJVM Type_void   = "V"
typeJVM Type_bool   = "Z"
typeJVM Type_string = "Ljava/lang/String;"

funJVMType :: String -> [Type] -> Type -> FunType
funJVMType i typs rty = i ++ "(" ++ (foldr (\ t s -> typeJVM t ++ s) "" typs) ++ ")" ++ typeJVM rty

funJVM :: String -> String -> [Type] -> Type -> FunType
funJVM i clas argty rty = "invokestatic " ++ clas ++"/" ++ funJVMType i argty rty

extendFunEnv :: Id -> FunType -> State Env ()
extendFunEnv f t = do
  env <- get
  put (env {funs = Map.insert f t (funs env)})

extendDef :: String -> Def -> State Env ()
extendDef cls (DFun t (Id f) args _) = extendFunEnv (Id f) (funJVM f cls (map aux args) t)
  where
    aux (ADecl t _) = t

-- printInt, printDouble and friends, which live in a Runtime class.
extendBuiltinDefs :: State Env ()
extendBuiltinDefs = mapM_ ( \ ((Id i),(argTys,rty)) -> extendFunEnv (Id i) $ funJVM i "Runtime" argTys rty) buildInFunctions

-- Open a scope: a fresh name map, and a slot counter that starts where the
-- enclosing block left off.
newBlock :: State Env ()
newBlock = do
  env <- get
  put (env {vars = Map.empty : vars env
           , maxvars = head (maxvars env) : maxvars env
           }
      )

-- Close a scope, which frees its slots for whatever block comes next.
exitBlock :: State Env ()
exitBlock = do
  env <- get
  put (env { vars = tail (vars env)
           , maxvars = tail (maxvars env)
           }
      )

newLabel :: State Env String
newLabel  = do
  env <- get
  put (env { labels = labels env + 1 })
  return ("label" ++ show (labels env))

lookupFun :: Id -> State Env FunType
lookupFun f = do
  env <- get
  return ((funs env) Map.! f)

-- Innermost block first, so an inner declaration shadows an outer one.
lookupVars :: Id -> [Map.Map Id Int] -> Int
lookupVars _ [] = error "the type checker already proved this cannot happen"
lookupVars x (m:ms) = case Map.lookup x m of
                        Nothing -> lookupVars x ms
                        Just d -> d

lookupVar :: Id -> State Env Int
lookupVar i = do
  env <- get
  return (lookupVars i (vars env))

-- Entry point: cls is the class name, p is the typed tree from the checker.
compile :: String -> Program -> [Instruction]
compile cls p = reverse ( code (execState (compileP cls p) emptyEnv) )

compileP :: String -> Program -> State Env ()
compileP cls (PDefs defs) = do
  emit $ ".class public " ++ cls
  emit $ ".super java/lang/Object"
  emit $ ""
  emit $ ".method public <init>()V"
  emit $ "  aload_0"
  emit $ "  invokenonvirtual java/lang/Object/<init>()V"
  emit $ "  return"
  emit $ ".end method"
  emit $ ""
  extendBuiltinDefs
  mapM  (extendDef cls) defs
  mapM_ compileDef defs

compileDef :: Def -> State Env ()
compileDef (DFun t (Id i) args stmts) = do
  newBlock
  if i == "main" then do
       emit $ ".method public static main([Ljava/lang/String;)V"
       -- main's slot 0 is taken by the String[] the JVM passes in.
       extendVar Type_string (Id "args")
  else emit $ ".method public static " ++ (funJVMType i (map (\ (ADecl t _) -> t) args) t)
  -- The honest numbers are max_locals and max_stack. These are not them.
  emit $ ".limit locals 1000"
  emit $ ".limit stack  1000"
  mapM (\ (ADecl t i) -> extendVar t i) args
  mapM compileStm stmts
  exitBlock
  emit $ "return"
  emit $ ".end method"
  emit ""

compileStm :: Stm -> State Env ()
-- A statement must leave the stack as it found it, so whatever the expression
-- pushed gets thrown away again.
compileStm (SExp e@(ETyped _ t)) = do
  compileExp e
  if t `elem` [Type_int, Type_bool, Type_string]
    then emit "pop"
    else if t == Type_double
      then emit "pop2"
      else return ()
compileStm (SDecls t ids) = extendVars t ids
compileStm (SInit t id exp) = do
  extendVar t id
  compileExp exp
  x <- lookupVar id
  if t `elem` [Type_int, Type_bool]
    then do
      emit ("istore " ++ show x)
    else if t == Type_double
      then do
        emit ("dstore " ++ show x)
      else
        emit ("astore " ++ show x)
compileStm (SReturn (ETyped exp t)) = do
  compileExp (ETyped exp t)
  if t == Type_string
    then emit "areturn"
  else if t == Type_double
    then emit "dreturn"
  else emit "ireturn"
compileStm SReturnVoid = emit "return"
compileStm (SWhile exp stm) = do
  test <- newLabel
  end <- newLabel
  emit (test ++ ":")
  compileExp exp
  emit("ifeq " ++ end)
  compileStm stm
  emit ("goto " ++ test)
  emit (end ++ ":")
compileStm (SBlock stms) = do
  newBlock
  mapM_ compileStm stms
  exitBlock
compileStm (SIfElse e s1 s2) = do
  t <- newLabel
  f <- newLabel
  compileExp e
  emit ("ifeq " ++ f)
  compileStm s1
  emit ("goto " ++ t)
  emit (f ++ ":")
  compileStm s2
  emit (t ++ ":")
compileStm stm = error "undefined statement"

compileExp :: Exp -> State Env ()
compileExp (ETyped ETrue _) = emit "bipush 1"
compileExp (ETyped EFalse _) = emit "bipush 0"
compileExp (ETyped (EInt n) _) = emit ("ldc " ++ show n)
compileExp (ETyped (EDouble d) _) = emit ("ldc2_w " ++ show d)
compileExp (ETyped (EString s) _) = emit ("ldc " ++ s)
compileExp (ETyped (EId x) t) = do
  dir <- lookupVar x
  if t `elem` [Type_int, Type_bool]
    then emit ("iload " ++ show dir)
    else if t == Type_double
      then emit ("dload " ++ show dir)
      else if t == Type_string
        then emit ("aload " ++ show dir)
        else error "should not get here"
compileExp (ETyped (EApp f exps) t) = do
  mapM_ compileExp exps
  invf <- lookupFun f
  emit invf
compileExp (ETyped (EPIncr id) t) = do
  x <- lookupVar id
  emit ("iload " ++ show x)
  emit "dup"
  emit "iconst_1"
  emit "iadd"
  emit ("istore " ++ show x)
compileExp (ETyped (EPDecr id) t) = do
  x <- lookupVar id
  emit ("iload " ++ show x)
  emit "iconst_1"
  if t == Type_int 
  then do
    emit "isub"
    emit "dup"
  else
    do
      emit "dsub"
      emit "dup2"
  emit ("istore " ++ show x)
compileExp (ETyped (EIncr id) t) = do
  x <- lookupVar id
  emit ("iload " ++ show x)
  emit "iconst_1"
  if t == Type_int 
    then do
      emit "iadd"
      emit "dup"
    else
      do
        emit "dadd"
        emit "dup2"
  emit ("istore " ++ show x)
compileExp (ETyped (EDecr id) t) = do
  x <- lookupVar id
  emit ("iload " ++ show x)
  emit "iconst_1"
  if t == Type_int 
    then do
      emit "isub"
      emit "dup"
    else
      do
        emit "dsub"
        emit "dup2"
  emit ("istore " ++ show x)
compileExp (ETyped (ETimes exp1 exp2) t) = do
  compileExp exp1
  compileExp exp2
  if t == Type_int
    then emit "imul"
    else emit "dmul"
compileExp (ETyped (EDiv exp1 exp2) t) = do
  compileExp exp1
  compileExp exp2
  if t == Type_int
    then emit "idiv"
    else emit "ddiv"
compileExp (ETyped (EPlus exp1 exp2) t) = do
  compileExp exp1
  compileExp exp2
  if t == Type_int
    then emit "iadd"
    else if t == Type_double
      then emit "dadd"
      else
        do
          inv <- lookupFun (Id "concatStr")
          emit inv
compileExp (ETyped (EMinus exp1 exp2) t) = do
  compileExp exp1
  compileExp exp2
  if t == Type_int
    then emit "isub"
  else
    emit "dsub"
compileExp (ETyped (ELt e1@(ETyped _ Type_int) e2) Type_bool) = compileExpCmp e1 e2 Lt
compileExp (ETyped (ELt e1@(ETyped _ Type_double) e2) Type_bool) = compileExpCmpDouble e1 e2 Lt
compileExp (ETyped (EGt e1@(ETyped _ Type_int) e2) Type_bool) = compileExpCmp e1 e2 Gt
compileExp (ETyped (EGt e1@(ETyped _ Type_double) e2) Type_bool) = compileExpCmpDouble e1 e2 Gt
compileExp (ETyped (ELtEq e1@(ETyped _ Type_int) e2) Type_bool) = compileExpCmp e1 e2 Le
compileExp (ETyped (ELtEq e1@(ETyped _ Type_double) e2) Type_bool) = compileExpCmpDouble e1 e2 Le
compileExp (ETyped (EGtEq e1@(ETyped _ Type_int) e2) Type_bool) = compileExpCmp e1 e2 Ge
compileExp (ETyped (EGtEq e1@(ETyped _ Type_double) e2) Type_bool) = compileExpCmpDouble e1 e2 Ge
compileExp (ETyped (EEq e1@(ETyped _ Type_int) e2) Type_bool) = compileExpCmp e1 e2 Equal
compileExp (ETyped (EEq e1@(ETyped _ Type_double) e2) Type_bool) = compileExpCmpDouble e1 e2 Equal
compileExp (ETyped (ENEq e1@(ETyped _ Type_int) e2) Type_bool) = compileExpCmp e1 e2 NEqual
compileExp (ETyped (ENEq e1@(ETyped _ Type_double) e2) Type_bool) = compileExpCmpDouble e1 e2 NEqual
compileExp (ETyped (EAnd exp1 exp2) _) = do
  compileExp exp1
  emit "bipush 1"
  true <- newLabel
  true2 <- newLabel
  end <- newLabel
  emit ("if_icmpeq " ++ true)
  emit "bipush 0"
  emit ("goto " ++ end)
  emit (true ++ ":")
  compileExp exp2
  emit "bipush 1"
  emit ("if_icmpeq " ++ true2)
  emit "bipush 0"
  emit ("goto " ++ end)
  emit (true2 ++ ":")
  emit "bipush 1"
  emit (end ++ ":")
compileExp (ETyped (EOr exp1 exp2) t) = do
  compileExp exp1
  emit "bipush 1"
  true <- newLabel
  true2 <- newLabel
  end <- newLabel
  emit ("if_icmpeq " ++ true)
  compileExp exp2
  emit "bipush 1"
  emit ("if_icmpeq " ++ true2)
  emit "bipush 0"
  emit ("goto " ++ end)
  emit ("goto " ++ end)
  emit (true ++ ":")
  emit (true2 ++ ":")
  emit "bipush 1"
  emit (end ++ ":")
compileExp (ETyped (EAss x e) t) = do
  compileExp e
  x <- lookupVar x
  if t `elem` [Type_int, Type_bool]
    then do
      emit "dup"
      emit ("istore " ++ show x)
    else if t == Type_double
      then do
        emit "dup2"
        emit ("dstore " ++ show x)
      else do
        emit "dup"
        emit ("astore " ++ show x)
compileExp exp = error "undefined exp"

compileExpCmp :: Exp -> Exp -> Cmp -> State Env ()
compileExpCmp e1 e2 cmp = do
  true <- newLabel
  emit "bipush 1"
  compileExp e1
  compileExp e2
  emit (show cmp ++ true)
  emit "pop"
  emit "bipush 0"
  emit (true ++ ":")

compileExpCmpDouble :: Exp -> Exp -> Cmp -> State Env ()
compileExpCmpDouble e1 e2 cmp = do
  true <- newLabel
  emit "bipush 1"
  compileExp e1
  compileExp e2
  emit "dcmpg"
  emit (showDbl cmp ++ true)
  emit "pop"
  emit "bipush 0"
  emit (true ++ ":")

-- The comparison operators, and how each one spells its jump.
data Cmp = Equal | NEqual | Lt | Gt | Ge | Le
  deriving (Eq)

instance Show Cmp where
  show Equal  = "if_icmpeq "
  show NEqual = "if_icmpne "
  show Lt     = "if_icmplt "
  show Gt     = "if_icmpgt "
  show Ge     = "if_icmpge "
  show Le     = "if_icmple "

showDbl :: Cmp -> Instruction
showDbl Equal  = "ifeq "
showDbl NEqual = "ifne "
showDbl Lt     = "iflt "
showDbl Gt     = "ifgt "
showDbl Ge     = "ifge "
showDbl Le     = "ifle "

07 · Run it

Time to close the loop. The stepper below is a small JVM. It takes the instructions from the figures above and executes them one at a time, showing the program counter, the operand stack, the locals table and the call stack, with your source above the code and the exact span the machine is inside lit up. It is also exercise 5-1 in the book: "implement an interpreter for a fragment of JVM", working on text files of assembly.

Clicking an instruction runs straight to it, which turns the listing into a breakpoint bar. Load recursion, step into fac, then click its ireturn over and over and watch the recursion unwind one level per click. Play the while loop program and watch the pc bounce off goto label0 back to the test, around and around, three times. That bounce is the loop. There's nothing else to it.

Things to try, each one a section of this post you can poke at:

• The two-slot double. Load doubles and watch ldc2_w 2.5 claim two stack slots at once, and dstore 1 fill slots 1 and 2 of the locals table.
• Recursion. Load recursion and watch invokestatic stack up fac frames, each with its own locals (a new frame is created each time a method is invoked), then watch ireturn pop a frame and hand the value to the caller's stack.
• The high-water mark. The stack panel tracks the deepest the stack has been. That number is the max_stack a careful compiler would have declared instead of 1000.
• A real crash. Edit the lab so safe(1, 0) runs. idiv throws ArithmeticException when the divisor is zero, and the stepper dies exactly like OpenJDK does.
• The verifier's veto. Change void main() to int main() and return 0, C++ style. The compiler emits ireturn inside main([Ljava/lang/String;)V, which the JVM's entry point signature says returns void, and a real JVM refuses the class before running a single instruction: java.lang.VerifyError: Wrong return type in function. I got that message out of an actual OpenJDK 8, and the stepper reproduces the refusal. Ranta describes bytecode verification as a light-weight type checking the JVM runs before executing a class file, there to catch what a type-checking compiler should never produce in the first place, like treating half a double as an int.

08 · The colophon, which is also the proof

The compiler under this post is a TypeScript port of the Haskell one, so the obvious question is whether it cheats. It doesn't. I ran both compilers over every demo program here and the emitted assembly is byte for byte identical, dead gotos and all. Then I assembled it with Jasmin and ran it on a real JVM, and its output matches the browser VM's, down to how Java prints a double. Every JVM behavior this post asserts is either quoted from the specification or was run against OpenJDK, usually both.

There's one thing the port refuses to reproduce. The original happily lets you compare two bools with == and then crashes generating code for it. The one under this post rejects the program instead. Some dust isn't worth preserving.

One thing the stepper quietly misleads you about. It walks the bytecode one instruction at a time, and a real JVM does that too, but only at first. Once it notices a method running hot, it hands the bytecode to a JIT compiler, which does the whole pipeline again: it parses the bytecode into a tree of its own, types it, optimizes it far harder than my peephole ever will, and emits actual x86 or ARM. So the instructions in these figures aren't the end of the line. They're an intermediate representation that gets compiled a second time, at runtime, by a compiler that knows things mine never could, like which branch actually gets taken.

The pipeline you played with is the real shape of the real thing. GCC and V8 have more stages, more tiers and thirty years of optimization between the tree and the instructions, but they're answering the same four questions: what are the words, what is the shape, what are the types, what are the instructions. Once you've watched a while loop become three labels and a conditional jump, no compiler is a black box anymore. It's just a very long pipeline.

None of this stayed on the shelf. Years later, at Radiant Security, I designed and built RQL (Radiant Query Language), a SQL-like language purpose-built for querying security events: graph traversal, fuzzy matching, anomaly detection, all compiled down from one query. It leaned on Nearley.js instead of BNFC, and I can't get into the internals here for confidentiality reasons, but it was an extremely fun problem to own, and every bit of it traces straight back to what's on this page.