Tree Calculus

What it is

It has been reported that Tree Calculus was discovered by Barry Jay, and that the demos on the project website were developed by Johannes Bader. At its core there is a single operator, △, with grammar E ::= △ | E E. Visually, △ is a tree node; applying E1 to E2 attaches E2 to the root of E1 on the right, producing natural binary trees whose nodes are called leaves, stems or forks.

How it works

Combinatory logic with K and S is complete, and Tree Calculus reportedly encodes similar expressive power while letting recursive functions appear as normal forms via built-in fixpoint constructions — unlike the usual lambda-calculus tricks. Triage-like primitives perform case analysis on leaf/stem/fork shapes; numbers are encoded as repeated △ structure and basic tests are expressed as small tree programs. It may sound abstract, but the model is concrete: sub-terms are literal sub-trees, so program structure and data coincide.

Demos and claims

The project site includes demos for trivial, safe interpreters, cross-platform configuration generation, program serialization and even a simpler take on the halting problem, it has been reported. Programs-as-values enables self-application, introspection and reflection; allegedly the pictured size program evaluates size size to 168. The demos are pitched as showing that common functionality is easy to bootstrap and that powerful programs need not be large trees.

Why it matters

Why care? Because Tree Calculus treads familiar ground — homoiconicity à la Lisp, combinatory logic and the long-running hunt for compact universal models — but with a new, tree-first twist. It’s a neat thought experiment and a pragmatic toolbox at once: small interpreters, cross-platform configs, and program analysis-as-function are all on the table. Curious? The site links to a book, a blog and further resources for those who want to poke the tree and see what falls out.

Sources: treecalcul.us, Hacker News