https://taylor.town/scrapscript-001 taylor.town about spam rss Lil' Fun Langs' Guts I'm still thinking about those lil' fun langs. How do they work? What's inside them? Do I need my pancreas? What if I don't want to normalize my IR? Is laziness a virtue? Haskell-esque languages may look alike, but they differ across many dimensions: * strict vs. lazy * curried vs. bland * bootstrapped vs. hosted * interpreted vs. compiled * nominal vs. structural types * pretty vs. ugly errors Most implementations use standard compilation phases: 1. Lexing: Source - Token stream 2. Parsing: Tokens - Surface AST 3. Desugaring: Surface AST - Core AST 4. Type Inference: Core AST - Typed AST 5. Pattern Match Compile: Typed AST - Case trees 6. Normalization (ANF/K): Typed AST - Normalized IR 7. Optimization: Normalized IR - Normalized IR 8. Closure Conversion: Normalized IR - Closure-explicit IR 9. Code Generation: Closure IR - Target (asm/bytecode/C/LLVM) 10. Register Allocation: Virtual regs - Physical regs (if native) 11. Runtime System: GC, primitives, entry point --------------------------------------------------------------------- Strict vs. Lazy In strict evaluation, arguments are evaluated before being passed to a function. In lazy evaluation, arguments are only evaluated if their value is actually needed; the result is cached, so the work happens at most once. -- lazy eval returns `3` without applying `foo` length [ 1, foo 2, 4 ] Aspect Strict (ML, OCaml) Lazy (Haskell) Normalization ANF / K-normal form STG / thunks required Closure Standard flat closures Closures + thunks + update conversion frames Code generation Straightforward Requires eval/apply or push /enter Memory Values are always May contain unevaluated management evaluated thunks Tail calls Simple (jump) Complex (enters, updates) Debugging Easy (call stack is Hard (thunks obscure meaningful) control flow) Runtime Simpler (~200 LOC C) More complex (~500-2000 LOC complexity C) Strict evaluation is the simple choice. If you want laziness, Peyton Jones's STG machine is the standard approach. MicroHs sidesteps the STG machine by compiling directly to combinatory logic with graph reduction. Lazy evaluation also unlocks infinite collections -- you can define an infinite list and consume only what you need. Curried vs. Bland Style Examples Implementation cost Haskell, Ben Free in combinator backends; native Curried Lynn, MicroHs backends need arity analysis to avoid allocating a closure per argument MinCaml, OCaml Simpler codegen -- multi-arg functions are Bland (internally), just functions that take tuples or multiple Grace, EYG params In a curried language, f x y is ((f) x) y: two function applications. If your backend doesn't detect that f always takes two arguments (arity analysis), you pay for a heap allocation on every multi-argument call. Bootstrapped vs. Hosted I tried to teach myself to play the guitar. But I'm a horrible teacher -- because I do not know how to play a guitar. -- Mitch Hedberg Most compilers are written in an existing language (e.g. C, Rust, Haskell, OCaml) and lean on that host's ecosystem for parsing libraries, build tools, and package management. A bootstrapped compiler compiles itself. You write the compiler in the language it compiles, then use an earlier version of the compiler (or a minimal seed runtime) to build the next version. Your language becomes self-sustaining; the compiler is its own test suite. There are many exemplary self-hosted languages to study: * MicroHs is a Haskell compiler that compiles Haskell to combinators. The combinator reducer is implemented in C. The compiler is written in Haskell and can compile itself. Bootstrapping requires only a C compiler -- no pre-existing Haskell installation. * Ben Lynn starts with a minimal runtime in C (~350 LOC), then constructs increasingly capable compilers, each written in the subset that the previous one can compile. Each stage is ~100-300 LOC of the language being defined. The total chain is ~2000 LOC + 350 LOC C. C runtime (350 LOC) - compiler1: lambda calculus + integers - compiler2: + let, letrec, ADTs - compiler3: + type inference - compiler4: + pattern matching - compiler5: + type classes - ... - compiler[?]: near-Haskell-98 * Newt is a dependently typed language whose compiler is written in Newt, targeting JavaScript. It bootstraps by keeping the generated JS checked in. This works best when your target is a high-level runtime (JS, JVM) rather than native code. Interpreted vs. Compiled An interpreter executes the program directly by walking its AST or stepping through bytecode. A compiler translates the program into another language (e.g. x86, C, JS) and lets that target handle execution. The boundary here is blurry. Bytecode VMs compile to an intermediate form. "Transpilers" compile to source code rather than machine instructions. Strategy Examples LOC Trade-off estimate Tree-walking PLZoo poly, Simplest. No codegen, no interpreter Eff, Frank, 50-200 runtime. Slow (10-100x native) Grace, 1ML OCaml (ZINC), Middle ground. Portable, Bytecode VM Tao, PLZoo 200-500 reasonable speed. Write ~30-50 miniml instructions Native MinCaml, mlml, Fast execution, but you own compilation AQaml 500-1500 register allocation, calling conventions, ABI Koka, Best of both worlds -- portable Transpile to Scrapscript, 200-500 native speed, C compiler does C Chicken, the hard parts Austral Transpile to Newt, SOSML, Web/ecosystem deployment, but JS/Go Borgo 200-400 you inherit the target's performance model Combinator Ben Lynn, No closures, no registers. reduction MicroHs 100-300 Graph reduction evaluator in C. Simple but slow Lil' fun langs are usually interpreters. Without compilation, you can skip closure conversion, register allocation, and runtime systems. The leap from interpreter to compiler costs ~500-2000 LOC. Nominal vs. Structural Types type Meters = Int type Seconds = Int -- Nominal: Meters [?] Seconds (different names) -- Structural: Meters = Seconds (same shape) Style Examples Consequence Nominal OCaml, Haskell, Name is identity -- same shape Austral doesn't mean same type EYG, Grace, Shape is identity -- same fields/ Structural TypeScript, variants means same type Simple-sub Most ML-family languages are nominal for algebraic data types but structural for records (if implemented). Row polymorphism (EYG, Grace, Koka) is inherently structural -- it acts on "any record with at least these fields." Simple-sub goes further: union and intersection types, with principal inference intact. Pretty vs. Ugly Errors -- Ugly: Error: type mismatch: int vs string -- Pretty: 3 | let x = 1 + "hello" | ^^^^^^^^ Error: I expected an `int` here, but got a `string`. The left side of `+` is `int`, so the right side must be too. Pretty errors cannot be achieved with a coat of paint. To point at a line/region of code, you must thread source locations through every compiler phase. A minimum viable error system: 1. Source spans on every AST node. Every expression, pattern, and type carries { file, start_line, start_col, end_line, end_col }. This costs one extra field per node. 2. Preserve spans through desugaring. When you lower where to let, the new let node inherits the span of the where. 3. Preserve spans through type inference. When unification fails, you need the spans of both conflicting types. 4. Format errors with context. Show the source line, underline the relevant span, explain the mismatch. Quality Examples Cost Elm-tier Elm, Austral Purpose-built error messages per failure mode. Highest effort, best UX Good Tao, Ante, OCaml Source spans + generic formatting. enough Covers 90% of cases Positional MinCaml, most Line numbers but no span highlighting or small compilers explanation De Bruijn Elaboration Zoo Variable names lost -- fine for indices (intentionally) research, bad for users --------------------------------------------------------------------- Lexing Approach Used by LOC Notes estimate Hand-written MinCaml (Rust port), 100-300 Full control, recursive Tao, Ante best errors ocamllex / mlllex MinCaml (original), 50-100 Standard for HaMLet, PLZoo OCaml/SML hosts Alex (Haskell) MicroHs, many 50-100 Standard for Haskell-hosted Haskell hosts Parser combinator Ben Lynn, some 0 (part of Lexerless parsing (integrated) educational parser) Optional enhancements: * Layout/indentation sensitivity (Haskell-style offside rule): Ben Lynn implements this in later bootstrapping stages. MicroHs includes full layout parsing. Adds 100-300 LOC. The algorithm is well-described by the Haskell Report's Section 2.7. * Unicode identifiers: Most small compilers skip this entirely. Koka supports it. * Interpolated strings: Syntax like "hello ${name}" is not standard in ML-family, but some newer languages add it. Parsing Parsing converts the flat token stream into a tree. The surface syntax is parsed into a concrete syntax tree (CST) or directly into an abstract syntax tree (AST). ML-family languages have a well-behaved grammar that is almost LL(1). Approach Used by LOC Notes estimate Recursive descent + MinCaml (Rust Best error Pratt/precedence port), Tao, 200-500 messages, easiest climbing Ante to extend ocamlyacc / mlyacc MinCaml 100-200 Standard, but poor (LALR) (original), (grammar error recovery HaMLet file) Parser combinators Ben Lynn, Elegant, (Parsec-style) MicroHs, PLZoo 100-400 compositional, backtracking PEG / Packrat Rare in 100-300 Linear time ML-family guarantee Every subsequent phase transforms this type. In ML-family languages, the AST typically looks like: type expr = | Lit of literal (* 42, 3.14, "hello", true *) | Var of name (* x *) | App of expr * expr (* f x *) | Lam of name * expr (* fun x -> e *) (or \x -> e) | Let of name * expr * expr (* let x = e1 in e2 *) | LetRec of name * expr * expr (* let rec f = e1 in e2 *) | If of expr * expr * expr (* if c then t else f *) | Tuple of expr list (* (a, b, c) *) | Match of expr * branch list (* match e with p1 -> e1 | ... *) | Ann of expr * type (* (e : t) *) Name Resolution & Desugaring Before type inference, the surface AST is simplified: 1. Alpha-renaming: Every binder is assigned a unique identifier to eliminate shadowing. MinCaml's Rust port does this during type checking. Most do this while parsing or during a separate pass. 2. Fixity resolution: Infix operators are re-associated according to declared precedence and associativity. HaMLet does this as a separate pass. Many small compilers hardcode operator precedence in the parser. 3. Desugaring: Surface constructs are lowered into core constructs: + where clauses - let + Guards in pattern matching - nested if + do notation (monadic) - >>= chains + List comprehensions - concatMap + Operator sections - lambdas: (+ 1) becomes fun x -> x + 1 + Record syntax - positional constructors + accessor functions + Type class instances - dictionary passing (elaboration) Type Inference This is the heart of an ML-family language. The "standard" algorithm is Hindley-Milner (HM) type inference, specifically Algorithm W or Algorithm J. Core components: 1. Type representation: Types are terms built from type variables, type constructors, and function arrows: type ty = TVar of tvar | TCon of string | TArr of ty * ty | TTuple of ty list 2. Unification: Given two types, find the most general substitution that makes them equal. Implemented as a union-find structure over type variables with occurs-check. 3. Generalization: At let boundaries, free type variables in a type are universally quantified to produce a polymorphic type scheme: [?]a. a - a. 4. Instantiation: When a polymorphic name is used, its scheme is instantiated with fresh type variables. -- Given: let id = fun x -> x in (id 1, id true) -- Type inference trace: -- 1. id : a - a (infer: x has fresh type a, body is x) -- 2. generalize: id : [?]a. a - a (a is free at let boundary) -- 3. id 1: instantiate a=b, unify b-b with int-g, get int -- 4. id true: instantiate a=d, unify d-d with bool-e, get bool -- 5. result: (int, bool) Approach Used by LOC Notes estimate Algorithm W Algorithm W Simplest to (substitution-based) Step-by-Step, 150-400 understand, compose PLZoo substitutions eagerly Algorithm J (mutable MinCaml, most More efficient, uses refs) production 100-300 mutable unification compilers variables Constraint-based (HM GHC, some Separates constraint (X)) research 500-2000 generation from compilers solving; extensible Elaboration Zoo, Alternates checking/ Bidirectional type some dependent 200-500 inference modes; checking type systems scales to dependent types But fancy type system features aren't free: Enhancement Complexity Used by added Type classes / traits +500-2000 Haskell, MicroHs, Ben Lynn LOC (later stages), Tao Row polymorphism (extensible +300-800 Koka, 1ML, EYG, Grace records/variants) LOC Higher-kinded types +200-500 Haskell, Koka LOC GADTs +500-1500 GHC, OCaml 4.x+ LOC Algebraic effects (typed) +500-1500 Koka, Eff, Frank LOC Dependent types (full) +1000-5000 Elaboration Zoo, Idris, Lean LOC Algebraic subtyping (union/ +500 LOC Simple-sub, MLscript intersection) First-class polymorphism +300-1000 1ML, MLF (System F) LOC Module system (functors, +1000-5000 HaMLet, OCaml, 1ML signatures) LOC Other strategies: * Polymorphism: Monomorphic type inference only (no [?] quantification). Every type is fully determined. This cuts the type checker to ~100 LOC by eliminating generalization and instantiation entirely. Functions like id x = x get a concrete type at each use site. * Elaboration: Modern type checkers increasingly separate elaboration (translating surface syntax to a fully explicit core) from unification (solving type constraints). The Elaboration Zoo demonstrates this cleanly: each stage is a single Haskell file of 200-800 LOC, progressively adding features. * Type class desugaring via dictionary passing: Haskell-style type classes are implemented by translating class constraints into explicit dictionary arguments. sort :: Ord a => [a] -> [a] becomes sort :: OrdDict a -> [a] -> [a]. Ben Lynn's compiler and MicroHs both use this approach. Pattern Match Compilation With types inferred, pattern matching can be compiled to efficient decision trees or case trees. Approach Used by LOC Notes estimate Decision trees Most modern Optimal -- no redundant (Maranget's compilers, Tao, 200-600 tests, good code algorithm) Ante Older Backtracking compilers, 100-300 Simpler but can duplicate automata simple work implementations Nested if/switch Many Correct but exponentially (naive) educational 50-100 bad in worst case compilers Omitted entirely MinCaml, PLZoo 0 Only supports if/then/else poly on primitives Some Sequence of partial Defunctionalized educational 50-150 functions with fallthrough; compilers simpler but less efficient Key phases: 1. Exhaustiveness checking: Warn/error if a match doesn't cover all cases. 2. Redundancy checking: Warn if a pattern is unreachable. 3. Guard compilation: Guards add a "backtrack" obligation. 4. Nested pattern flattening: (Cons (x, Cons (y, Nil))) - sequence of tests. The canonical reference is Compiling Pattern Matching to Good Decision Trees. Luc Maranget's algorithm produces provably optimal decision trees in terms of the number of tests. OCaml and Rust use this approach. Normalization -- Before (nested expression): f (g x) (h y) -- After (A-normal form): let a = g x in let b = h y in f a b Every intermediate value gets a name. Every function argument becomes trivial. Evaluation order is now explicit in the let chain. Normalization strategies: Strategy Used by Character K-normal form MinCaml and Direct-style; names all (MinCaml's variant derivatives intermediate values with let of ANF) Flanagan et al. Essentially the same as A-normal form (ANF) 1993, many K-normal form; the standard modern compilers name Continuation-passing Appel's SML/NJ, Every function takes an extra style (CPS) Rabbit, CertiCoq continuation argument; all calls are tail calls Typed AST - combinatory logic No normalization Ben Lynn directly. Works for graph reduction, not for native codegen Skips ANF/CPS; SSA IR with SCCP SSA directly Scrapscript + DCE. Lets LLVM/C handle the rest Some dependent Like ANF but uses monadic bind Monadic normal form type systems instead of let; cleaner for (Bowman, 2024) certain optimizations Optimization With the program in normal form, optimization passes can simplify it. In small compilers, optimizations are kept minimal -- the goal is to not be embarrassingly slow, not to compete with GCC. MinCaml's optimization passes (totaling ~300 LOC): Pass LOC Effect (MinCaml) Beta reduction ~50 Inline let x = y in ... x ... - ... y ... Let flattening 22 let x = (let y = e1 in e2) in e3 - let (assoc) y = e1 in let x = e2 in e3 Inline expansion ~100 Replace calls to small functions with their bodies Constant folding ~50 3 + 4 - 7 Dead code ~50 Remove let x = e1 in e2 when x is not elimination free in e2 Common subexpression ~50 (optional in MinCaml, via hash-consing) elimination These six passes cover 80%+ of the optimization value for a small compiler. They are applied iteratively until a fixpoint is reached (typically 2-3 iterations). Beyond the basics: Optimization Complexity Effect Tail call +50-100 Essential for functional languages; loops optimization LOC are recursive calls Known-call +50 LOC When the target of a call is statically optimization known, skip closure indirection Unboxing +200-500 Avoid boxing for monomorphic uses of (specialization) LOC polymorphic functions Contification +100-300 Convert functions that are always called LOC in tail position to local jumps Demand analysis +500-2000 For lazy languages: determine which (strictness) LOC arguments are always evaluated Worker/wrapper +200-500 Separate strict args from lazy ones for transform LOC better codegen Deforestation / +500-2000 Eliminate intermediate data structures fusion LOC (e.g., map f . map g - map (f . g)) Whole-program varies JHC does this via GRIN; eliminates unused optimization constructors, specializes globally Closure Conversion -- Before: let f = \ x -> x + y -- After: let f = { fun = \ env x -> x + env.y , env = { y = y } } The optimized IR still has functions with free variables. Closure conversion makes all functions "closed" -- because hardware doesn't understand lexical scoping. Every function becomes a pair: (code pointer, environment record). The environment captures the function's free variables at the point of definition. Approach Used by Trade-offs MinCaml, Environment is a flat vector of Flat closures OCaml, most captured values. O(1) access, one compilers allocation per closure. Standard choice. Some older Environment is a linked list of Linked/shared Scheme frames. Shares structure between closures compilers closures. More allocation, slower access. GHC Eliminates closures entirely by (selectively), adding extra parameters. No heap Lambda lifting some allocation for the closure itself. educational But callers must pass more compilers arguments, and call sites must be updated. Replace higher-order functions Reynolds with first-order dispatch on a sum Defunctionalization (1972), MLton type. Eliminates function pointers entirely. Requires whole-program analysis. Combinatory logic Replace lambdas with SKI (bracket Ben Lynn, combinators (or variants). No abstraction) MicroHs closures, no environments. Evaluation by graph reduction. Code Generation Codegen is wholly determined by your choice of target: Target Used by LOC Trade-offs estimate Native assembly MinCaml, mlml, Best performance, most (x86-64, ARM, AQaml 300-800 work, platform-specific etc.) Koka, Portable, leverages C C source Scrapscript, 200-500 compiler's optimizer, but Chicken, JHC, indirection Austral Ante, gocaml, Good native perf, LLVM IR Harrop's MiniML 200-500 cross-platform, but large dependency MinCaml (Rust Faster compilation than Cranelift port), some new 200-500 LLVM, good codegen, languages Rust-native Bytecode OCaml (ZINC Portable, simple, but (custom VM) machine), PLZoo 200-500 slower execution miniml JavaScript / MinCaml-wasm, Web deployment, but Wasm SOSML, Newt, 200-400 limited performance model various Inherit Go's ecosystem, Go source Borgo 200-500 tooling, and concurrency model Combinatory Ben Lynn, MicroHs 100-300 No register allocation logic needed, but slow execution Normalizer (no "Compilation" = reduce to runtime target) Dhall 200-500 normal form. No executable output Register Allocation Programs use arbitrarily many variables, but CPUs have a fixed number of registers. Register allocation decides which variables live in registers and which spill into memory. If you target native assembly, you implement this yourself. The backend handles this for you if you target C/LLVM/Cranelift/etc. Approach Used by LOC Quality estimate Graph coloring MinCaml, Appel's 200-500 Optimal for most (Chaitin-Briggs) textbook cases, standard Linear scan Some JITs, simple 100-200 Fast compilation, compilers slightly worse code Naive (spill Some educational 50 Correct but terrible everything) compilers performance Not applicable Compilers targeting 0 Delegated to backend C/LLVM/bytecode Runtime System The minimal setup includes: Component Complexity Notes Entry point / stack 10-30 LOC C Set up initial heap and stack setup pointers Garbage collector 100-1000 LOC See below C Primitive operations 50-200 LOC C/ I/O, math, string operations asm Allocation routine 10-50 LOC Bump allocator (if GC handles collection) Closure part of How closures are laid out in representation codegen memory Lil' fun langs allocate frequently -- every closure, every cons cell, every partial application. Without reclamation, you run out of memory fast. You need to prevent garbage from accumulating: Strategy Used by Complexity Notes Some No GC (leak educational Viable for short-running memory) compilers, 0 programs MinCaml benchmarks Many small Cheney copying compilers, 100-300 LOC C Simple, fast, but uses 2x (semispace) Appel's memory textbook Mark-and-sweep Various 100-300 LOC C Doesn't move objects, no forwarding needed Koka No pause times; Perceus Reference (Perceus), 200-500 LOC achieves it precisely counting Carp, with no overhead via Swift-like compile-time insertion MLKit, some Compile-time memory Region-based research 300-1000 LOC management, no GC pauses languages Arena / stack Very simple 20-50 LOC Allocate in arenas, free only compilers all at once Ownership / Rust, Carp, 0 No runtime GC needed, but affine types Lean 4 (compile-time) restricts the language If your language has algebraic effects (Eff, Frank, Koka, Ante), the runtime needs support for delimited continuations or a CPS-transformed calling convention. Effect handlers essentially require a second stack or a segmented stack to capture continuations. Koka handles this via evidence-passing; Eff and Frank use interpretation.