Tree Calculus captures the essence of computation

add 58 42 100

One operator. Trivial semantics. Turing complete. Intensional.



Democratizing Functions
Democratizing Metatheory



  • Intensional

    Tree Calculus can perform program analysis without quotation: The ability to reflect on programs is built right into the reduction rules. This means that anything from type checking to compilation and optimization can happen from within programs and without additional external tools (🚀demo, 🚀fusion demo). In particular, this supports arbitrary type systems and truly gradual typing or verification: Static vs dynamic checks are one and the same function call, just at different points in time (🚀demo).

    Furthermore, intensionality allows compiling and deploying programs (or elaborate combinations like tier splitting) right from the program itself. This makes for all-powerful REPLs; translated to Python, imagine using nothing but a Jupyter Notebook for an entire product lifecycle, from prototyping to productionization.

  • Powerful

    Tree Calculus is Turing-complete and intensional (🚀demo). Combined with its trivial abstract syntax, it becomes easy to serialize any value, including programs (🚀demo).

    But furthermore, there is in fact no distinction between a program and its encoding. Such distinctions complicate descriptions and formal proofs of the Halting Problem, whereas with Tree Calculus as the substrate, Halting Problem formulations become more straightforward (🚀demo).

    Despite its simplicity, Tree Calculus is not a Turing tarpit. Data encodings and algorithms are asymptotically optimal. In practice: Typical functions to manipliate lists (map, filter, concat, fold, …) are binary trees with a few hundred nodes (🚀demo). The compiler used in all demos is also written in Tree Calculus, not particularly optimized, yet quite efficient.

  • Concise

    The abstract syntax of Tree Calculus is trivial: Values are unlabeled binary trees. The reduction rules act on trees of higher degree, until they are binary. (Bonus for readers familiar with λ-calculus: Recursive functions have normal form/are values in Tree Calculus.) The definition is compact, precise and imports no other “well known” definitions or standards, such as JSON, UTF8, two’s complement integers, IEEE floats or their respective arithmetic operations, which have tricky corner cases.

    However, arbitrary concepts like that can be bootstrapped in Tree Calculus swiftly and explicitly (🚀demo). This makes Tree Calculus a great language for modeling and formal specifications, but also very suitable for education: There are no incumbent towers of abstraction, but they can be introduced and modeled incrementally.

  • Portable

    The syntax and semantics of Tree Calculus are minimal and self-contained, relying on no platform-specific concepts or abstractions. As a result, it is trivial to write interpreters on any platform or in any programming language (🚀demo). Such interpreters are effectively safe by construction, since the reduction rules are simple (resulting in little code) and pure (no inherent access to the environment or resources).

    The ability to bootstrap the full power of Tree Calculus anywhere makes it an excellent configuration as code language in a heterogeneous system. Developers could write Tree Calculus programs that generate, say, JSON, and use an interpreter (that is tiny compared to a JSON parser) to materialize the configuration anywhere (🚀demo). This article describes how Meta uses Python for a similar purpose.