CATEGORICAL ABSTRACT MACHINE compile the lambda calculus to categorical combinators — and Caml is born
The Categorical Abstract Machine (CAM) compiles the lambda calculus into categorical combinators — composition, pairing, application — drawn straight from cartesian closed categories. There are no variable names in the target: a term becomes a point-free composition of combinators operating on a single accumulator plus a stack. The theory of categories, it turned out, is directly executable. Cousineau, Curien & Mauny built it at INRIA, and it became the runtime of the first Caml — the C-A-M in the name. It is the cleanest demonstration that a deep mathematical structure can be an execution model.
THE TECHNIQUE lambda terms → categorical combinators (composition, pairing)
A term compiled to combinators and run point-free. The demo composes (·+3) after identity and applies it to 5: live demo
HISTORY & CREDIT Cousineau, Curien & Mauny, 1987
“Category theory is abstract nonsense with no machine behind it.” — the CAM compiles lambda terms directly into categorical combinators and runs them; the first Caml was this machine. The abstraction executes. cited
1985–87 · Cousineau, Curien & Mauny (INRIA) — the Categorical Abstract Machine, lambda calculus via cartesian-closed-category combinators. lineage · became the runtime of the first Caml (the C-A-M). now · superseded by the ZINC machine (dart 270) in Caml Light / OCaml, but the point-free idea persists.
Names vanish; a program becomes a composition of categorical arrows on an accumulator. A branch of pure mathematics, compiled and executed. Cousineau-Curien-Mauny 1987
RECOMMEND FOR I-13 combinator composition, computed
On the canonical compiler, composing (id ; +3) and applying to 5 gives 8 — a point-free evaluation:
$ i13 run m_cam.i13 # (id ; +3) applied to 5
RUN OK . 9 step(s) . peak stack 2 . call depth 1
result = 8
Recommend: the CAM's lesson — a deep structure can be the execution model — is one i13 shares in spirit. i13 runs point-free in its own way: its IVM has no variable-name lookup at runtime, only stack positions (dart 262), the same “names compiled away” move the CAM makes with categorical combinators. i13 does not compile to category theory, but it agrees with the CAM that a runtime is cleaner when names are gone by the time you execute. The mechanism differs; the aesthetic — compile the names out, run the structure — is shared.