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 ]

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

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)
    → compiler₁: lambda calculus + integers
    → compiler₂: + let, letrec, ADTs
    → compiler₃: + type inference
    → compiler₄: + pattern matching
    → compiler₅: + 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.

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)

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.

Lexing

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).

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: ∀α. α → α.
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 : α → α                (infer: x has fresh type α, body is x)
-- 2. generalize: id : ∀α. α → α    (α is free at let boundary)
-- 3. id 1:  instantiate α=β, unify β→β with int→γ, get int
-- 4. id true: instantiate α=δ, unify δ→δ with bool→ε, get bool
-- 5. result: (int, bool)

But fancy type system features aren't free:

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.

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:

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):

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:

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.

Code Generation

Codegen is wholly determined by your choice of target:

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.

Runtime System

The minimal setup includes:

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:

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.