crml

May 2003 · age 21

What it was

A small declarative rule language written in OCaml in eight days for a programming-languages course. A program listed starting facts, their type signatures, and rules of the form "when these facts match and these guards hold, create these facts." The engine ran every rule against the fact database, added what was new, and repeated until nothing changed. Patterns could bind records and even invert arithmetic, so matching x+1 against 7 bound x to 6. A type inferencer with its own unifier checked the whole program before it ran. The showpiece was Conway's Game of Life written as a single rule over a nine-cell neighborhood, with generations as a field in the key and the engine's fixpoint as the simulation. It parsed, type-checked, ran and rendered, and stopped the day it was handed in.

Wins, for the age

• At twenty-one, in a week, Jeff reinvented the working core of Datalog: facts, rules, and evaluation to a fixpoint.
• Noticed the engine re-firing forever and fixed it in the semantics, rewriting each rule to require that its own output not yet exist. This primate found on their own what semi-naive Datalog evaluation had already found in 1986.
• Wrote type unification from scratch, over records and lambdas, getting most of the way to Hindley-Milner inference without the textbook.
• Chose the Game of Life as the demo because it stressed every feature at once and its output could be checked by eye. A 5x5 box evolved correctly into a pair of blocks.

What it taught

• Build a language when the problem is a language. By the next year the move was reflexive.
• The type checker is the product. It came last, took real thought, and made the language trustworthy.
• Fix convergence structurally, not with a step counter.
• Know where design decisions belong. The comparison operators were silently backwards, and a comment admits the planner "probably should have done this at parse time."

Genealogy

Ancestors: The Before Times in QBasic: the first tiny language, read and turned into something runnable. Descendants: Adama Language: the pull toward declarative, convergent, typed systems. Tutor: patterns and rewrite rules driven to a result. Vec4U: the next camlp4 language, eighteen months later.

Epitaph

Here lies crml. In eight days of May it reinvented Datalog, taught itself unification, and ran the Game of Life as one rule, then was printed, submitted, and set aside for twenty years.