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
that computes whenever it is acting on three values. Grammar:Visually,
is a tree node and the application of to attaches to the root of 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.
2.
Unlike λ-calculus, recursive functions can be represented as normal forms, using fixpoint constructions like orange/brown in the picture above.
-
Reflective
performs case analysis on leafs, stems and forks.We can represent natural number
as . The zero test is .Since programs are also values, intensional programs can be self-applied, to achieve reflection. The picture above shows program
, which computes its argument’s number of nodes. For instance, 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
program pictured at the top of this page uses 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