caml-prépa: a compiler you can look inside¶

examples/ocaml/ is a complete compiler for the OCaml subset taught in French preparatory classes, built on astero. It reads a programme, works out what its names refer to and what type everything has, and then either runs it or turns it into Python.

Most compilers are opaque: source goes in, a result comes out. This one will show you its working.

$ python -m ocaml corpus/fact.ml
120
120
120

That is the ordinary use. The interesting ones are the other four.

Five views of one programme¶

Take a small programme, sum.ml:

let rec sum l =
  match l with
  | [] -> 0
  | t :: rest -> t + sum rest

What type did it get? Nothing in that file says int, and there is no annotation anywhere. The compiler works it out from 0 and +:

$ python -m ocaml --types sum.ml
val sum : int list -> int

Which name refers to what? This is the view no other OCaml playground has, and the one this project exists to show:

$ python -m ocaml --names sum.ml   # abridged: the first of five trees
── vals ──
module    top              {sum}
  binding                    {l}
    case                       {}
    case                       {rest, t}

Read it as a nesting of scopes. The whole file binds sum. Inside it, the function's own block binds l. Inside that, the two match arms each have a block of their own: the first binds nothing, and the second binds rest and t. So t and rest exist only inside that arm, and sum is visible everywhere, which is what makes the recursive call work.

There are four more trees below that one, because OCaml keeps five kinds of name apart: values, constructors, record fields, type names and type variables. A record label x and a variable x are unrelated names, and keeping them in separate trees is what stops a rename of one touching the other.

What does it compile to?

$ python -m ocaml --python sum.ml
from ocaml.back import runtime as _rt
def sum(l):
    _s1 = l
    _ok3 = False
    _m2 = None
    if not _ok3 and _s1.tag == '[]':
        _m2 = 0
        _ok3 = True
    if not _ok3 and _s1.tag == '::':
        t = _s1.args[0]
        rest = _s1.args[1]
        _m2 = t + sum(rest)
        _ok3 = True
    if not _ok3:
        _rt.fail('Match_failure')
    return _m2

A match has become a chain of tests. Each one asks what kind of value it has, and where it fits, pulls the pieces out into the names the pattern gave them.

And how did the compiler read what I wrote?

$ python -m ocaml --printed sum.ml
let rec sum l = match l with [] -> 0 | t :: rest -> t + sum rest;;

Printing the tree back out is how you check that the grouping is what you meant. If a bracket appears that you did not write, the parser read it differently from you.

In a browser¶

All five views, side by side, with the forty-one worked programmes in a dropdown:

make -C examples web-serve

Then http://localhost:8000/. It runs the whole compiler in the page — no server, no install, nothing uploaded — and it runs the compiled Python as well as the tree, telling you whether the two agreed. See the playground.

How it is put together¶

The layout is the one a compiler course uses, and each part is a directory:

syntax.py sits above all three, because the tree is what they all talk about.

About 3,500 lines of Python. The largest single file is 523 lines, and the smallest thing in it is the piece this whole repository is about:

ROLES = {
    "PVar": {"name": defines(VALS)},
    "PAlias": {"name": defines(VALS)},
    "Var": {"name": uses(VALS)},
    "Variant": {"name": defines(CONS)},
    "ExnItem": {"name": defines(CONS)},
    ...
}

Sixteen lines like that, plus five scope entries, and the Names view above is derived from them. The middle end is where that happens.

The language¶

let rec, pattern matching, lists, arrays, records, sum types, references, loops, exceptions. The subset is chosen by one test: does a first- or second-year programme use it? So there are no functors, no objects, no GADTs, no labelled arguments, and no Printf yet.

examples/ocaml/SPEC.md is the specification: lexical structure, the full grammar, the precedence table, static and dynamic semantics, the standard library, and eleven places where it knowingly differs from real OCaml. The playground ships a reference card whose tables are generated from the compiler itself.

Is it correct?¶

Every stage is compared against something that is not itself:

The last row is the one that keeps paying. Two back ends sharing one runtime means a disagreement is a defect in one of them, and it found two: a runtime function that assumed how a closure was spelled, and a top-level let that wrote into a scope a closure had already captured. Neither crashed, and nothing else in the suite would have noticed either.

The corpus those rows run over¶

Forty-one programmes, each checked in beside the output it prints and the signature it infers. Ten cover the language, eight cover the syllabus one chapter at a time, and twenty-three are in corpus/simonet/, one per subject of the exercise series Vincent Simonet set at the Lycée Janson-de-Sailly between 1998 and 2003. Those twenty-three go well past the syllabus: LZW, red-black insertion, Knuth-Morris-Pratt and Boyer-Moore, Thompson's construction with the subset construction after it, Barnes-Hut over a quadtree.

Every concrete production of the grammar is reached by one of them, and test_the_corpus_reaches_every_production fails otherwise, so a production nothing writes does not belong in the subset.

Writing the Simonet set added no production and produced no wrong answer. It found three constructs the compiler refuses and OCaml accepts: C _ where C takes more than one argument, an unparenthesised if to the right of a binary operator, and for _ = 1 to n. All three are rejections rather than silent errors. They are now rows in SPEC.md section 12, each with the way out.

What the real compiler says¶

Installing a real ocaml found the fourth divergence, which no programme of the corpus could have. With OCaml 5.5.0 present, ocamlc compiles all forty-one without a warning and ocaml prints for every one of them exactly what both back ends print. ocamlc -i then infers every signature but two lines of records.ml, where it keeps a type abbreviation that this checker expands: the two types are equal and only the printed name differs, so nothing else in the suite noticed. The test carries those two lines by name rather than skipping the file, so the other three hundred-odd are still compared exactly, a second divergence still fails, and the entry itself fails once it is no longer needed.

410 tests. The two rows needing a real OCaml skip where there is none.