Tree calculus is minimal, Turing-complete, reflective, modular

Tree Calculus was discovered by Barry Jay. Check out his book and blog!
The demos on this website were developed by Johannes Bader.
See here for more background, resources and contact info.

• Minimal

  There is one operator $\mathrm{△}$ that computes whenever it is acting on three values. Grammar: $E::=\mathrm{△}|EE$

  Visually, $\mathrm{△}$ is a tree node and the application of $E_1$ to $E_2$ attaches $E_2$ to the root of $E_1$ on the right. This forms trees like that in the picture above. Values are natural binary trees. We call their nodes leaves, stems or forks.

  Practical consequences

  🚀 Demo: Trivial, safe interpreters on any platform.
  🚀 Demo: Good fit for cross-plat config generation.

• Turing-complete

  1. $K=\mathrm{△}\mathrm{△}$

  2. $Sx=\mathrm{△}(\mathrm{△}x)$

  Unlike λ-calculus, recursive functions can be represented as normal forms, using fixpoint constructions like orange/brown in the picture above.

• Reflective

  $triage\{l,s,f\}=\mathrm{△}(\mathrm{△}ls)f$ performs case analysis on leafs, stems and forks.

  We can represent natural number $n$ as ${\mathrm{△}}^n\mathrm{△}$. The zero test is $triage\{true,$ $Kfalse,$ $K^{2}false\}$.

  Since programs are also values, intensional programs can be self-applied, to achieve reflection. The picture above shows program $size$, which computes its argument’s number of nodes. For instance, $sizesize$ evaluates to 180.

  Practical consequences

  🚀 Demo: Abillity to serialize programs.
  🚀 Demo: Simpler formulation of the halting problem.
  🚀 Demo: Program analysis/optimization as a function.
  🚀 Demo: Static vs dynamic typing? Just function calls.

• Modular

  Sub-terms are represented as sub-trees. The $size$ program pictured at the top of this page uses $triage$ $\{$ $(+0),$ $\lambda u.$ $(+sizeu),$ $\lambda uv.$ $(+sizeu)$ $\circ$ $(+sizev)$ $\}$ $\circ$ $(+1)$ to count nodes recursively.

  Practical consequences

  🚀 Demo: Common functionality is easy to bootstrap.
  🚀 Demo: Powerful programs need not be large trees.

• Democratizing functions

• Democratizing metatheory