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: E ::=  | E E

    Visually, is a tree node and the application of E1 to E2 attaches E2 to the root of E1 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= 

    2. S x= ( 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}= ( l s) f performs case analysis on leafs, stems and forks.

    We can represent natural number n as n. The zero test is triage{true, Kfalse, K2false}.

    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, size  size 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), λu. (+ size u), λuv. (+ size u) (+ size v) } (+ 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