MediumA visual introduction to tree calculus | by Johannes Bader | MediumSitemapOpen in appSign upSign inMedium LogoGet appWriteSearchSign upSign inPlaying field and motivationTree CalculusRepresenting DataRunning ProgramsConstructing ProgramsConclusionAppendix: An alternative way to think of expressions and reductionAppendix: ImplementationAppendix: NotationJohannes BaderDeveloper Experience ImproverPress enter or click to view image in full sizeThe reduction rules of triage calculus. Black/filled nodes are ordinary tree nodes, colored triangles represent arbitrary subtrees, “@” nodes represent the application of a program (left child) to its input (right child). These rules apply as long as there are applications left. Shout-out to to Timur Latypoff who was first to blog a visualization of these rules!Combinatory LogicLambda CalculusRewrite RuleRecursionTree CalculusA visual introduction to tree calculusWhy is it useful? How does it work?Johannes Bader7 min read·Jan 8, 2025--ListenShareTree calculus is a minimal, modular, Turing-complete and reflective calculus. The goal of this post is to convey this, quickly and intuitively. I strongly recommend reading Barry’s book, blog or recent paper to dig both more deeply and broadly!One thing I love about tree calculus is that, while it is incredibly exciting to the theorist in me for pushing some technical boundaries, at the same time its specification is utterly compact and self-contained. That should make it very teachable. I tested this theory on my mom. After under 1h of me explaining and sketching things with pen and paper, she successfully rendered out the reductions of “not false → true” and “not true → false” and understood what’s going on. Whoa! Now, my mom is very smart, but she has never heard of λ-calculus, combinatory logic or term rewriting systems. And this still holds true now, because tree calculus can be explained — and used — without any Greek letters or parentheses. Because it’s all trees. Thanks for volunteering as my test subject, mom! ❤Playing field and motivationBefore jumping into how tree calculus works, let’s talk about what kind of thing it is, and what it accomplishes. The real world is complicated, so computer scientists and software engineers alike love looking at things abstractly: Start from simple assumptions or standards and bootstrap complexity on top of it, layer by layer. The vast majority of people can swim in the top layers, producing powerful apps or science. Something like this:Press enter or click to view image in full sizePress enter or click to view image in full sizePress enter or click to view image in full sizeLeft: Real processors come in many shapes, but standardized instruction sets like x86 helped tame the mess. Higher-level languages/runtimes can target that standard rather than worrying too much about underlying hardware details. Center: A similar thing is done in theoretical computer science. λ-calculus is comparably simple but Turing-complete, which makes it an exciting starting point to do science! Right: Tree calculus is even simpler, yet it is also reflective, which allows it to do exciting things directly and safely.Dig into the linked resources to learn exactly how and why, but the gist is: Tree calculus is minimal (note narrow, almost singularity-like “base” of the funnel), which makes it nice to reason about and trivial to run in any environment — including pen and paper. It can do more than λ-calculus natively (reflective, finite normal forms for recursive programs), which also reduces the distance between core calculus and high-level applications. Our website hosts a number of fully self-contained, interactive demos that aim to convey that.Enough context, let’s get started!Tree CalculusThink of programs and values as unlabeled binary trees. Every node is either a leaf, stem (has one child) or fork (has two children).A simple example program (logical “not”, takes a boolean argument and negates it) with 4 leafs, 1 stem and 3 forks, giving it an overall size of 8.Programs act on values. Tree calculus provides the rules for how a tree (program) applied to a tree (argument value) reduce into a new tree (result value). Programs are a kind of value, so programs can consume and produce programs as well.Representing DataIf all values are unlabeled binary trees, we need to decide on ways to represent them. The reduction rules of tree calculus prescribe how to represent a certain program as a tree, but the choice is ours when it comes to representing “inert” data like numbers, lists, etc. How about:Press enter or click to view image in full sizeSuggestion for how to represent booleans or lists, with elements represented by their respective subtrees. One could imagine representing a small natural number k as a chains with k edges, or larger integers as lists of booleans, etcRunning ProgramsIn his 2021 book, Barry proposes a set of just three rules that describe how to reduce trees. In 2024, I suggested an alternative set of rules that seems to make some things more straightforward. This post and our website uses those latter rules, which we call triage calculus.To visualize the rules that describe how a tree applied to a tree reduces to another tree, it is convenient to explicitly represent this “applied to” step as another kind of node. Let’s draw an “@” node:Representation of the (reducible) expression “not true”, i.e. the tree representation of “not” applied to the tree representation of “true”.Note that programs/values continue to only have one kind of node. The above is how we represent expressions that only become values upon reduction. Here are the reduction rules:Press enter or click to view image in full sizeThe reduction rules of triage calculus. Rules 0a-b describe how leafs and stems simply “absorb” their argument. Only forks are programs that “do” stuff. Rules 1 and 2 seem arbitrary to the unsuspecting reader, but behave analogous to the K and S operators of combinatory logic, which is sufficient to bootstrap λ-calculus. Rules 3a-c “triage” what happens next based on whether the argument tree is a leaf, stem or fork. This allows writing reflective programs.It is left as an exercise for the reader to apply these rules to reduce “not true” (see previous picture) and “not false” with pen and paper.Constructing ProgramsFrom here, it is an engineering challenge to come up with the trees for increasingly useful and complex programs. For instance, here is a program that computes the size (number of nodes) of its argument. So applied to the “not” program from earlier, it returns 8. Applied to itself, it returns 180.Press enter or click to view image in full sizeThe “size” program. Colors are just for readability and carry no semantics. The orange part of the tree provides the ability to recurse on the argument tree (fix point). The green/blue/purple subtrees are the three subtrees (w/x/y, respectively, see rules 3a-c) of a triage, accounting and recursing appropriately depending on which kind of node is encountered.Our website hosts various more advanced demos, such as a program optimizer or programs that emit trees as programs in other languages. The trees constructed in these demos may be too large to render reasonably — but they are all just trees! The compiler that compiles the pseudo-language used by the interactive playground is a tree of size ~200k.ConclusionHopefully this visual introduction conveyed an intuition about the motivation and workings of tree calculus. And hopefully you’re excited enough to follow all the links for a deep dive! Let’s revisit the attributes I promised in the very first sentence of this post:Minimal: Programs are trees, few reduction rules bootstrap everything.Modular: Programs can be composed into larger programs.Turing-complete: Tree calculus can model λ-calculus via rules 1 and 2.Reflective: Rules 3 allow reflecting on programs, e.g. to optimize them.Appendix: An alternative way to think of expressions and reductionThis post visualized application explicitly, as an “@” node. I think this emphasizes the distinction between reducible expression and value. However, one can also represent and think of reducible expressions as non-binary trees. Starting with a binary tree that represents a program, we can attach arguments to it as new, right-most child trees. Then the reduction rules are about turning non-binary trees into binary trees:Press enter or click to view image in full sizeAn alternative way to represent rules 1, 2 and 3a-c.Note that rules 0a-b become unnecessary as they also just attach the argument to the program as a right-most child. Caution: In rule 3c (analogous for rule 3b and rule 2), what does it mean for “y” to be an arbitrary subtree, but also have children “u” and “v”? Again, the way to read this is that “u” and “v” attach as additional right-most children to “y”. That’s the way application is implicitly encoded here, compared to the explicit “@” node. Despite not needing rules 0a-b, I felt like this is a bit confusing. But let me know if you have a different impression!Appendix: ImplementationIf you are a software engineer, you’re probably thinking about implementing this in your favorite language or platform. Please don’t hesitate to reach out if you created something cool, I’m happy to link to it!Check out the website for reference implementations. You will find the OCaml version implementing the rules exactly as visualized in this post, with function “apply” taking the role of the “@” node. The JavaScript version takes the alternative perspective introduced above: The reduction rules are implemented as mutating trees until they are binary. More mutation instead of allocation makes the garbage collector happy.Appendix: NotationPictures don’t scale well to trees of massive size. Talking about them precisely benefits from some kind of notation or even pseudo-language. Barry fittingly chose △ to denote tree nodes. The “not” program from earlier would be written as “△ (△ (△ △) (△ △ △)) △”, with applications written just like is standard in λ-calculus or combinatory logic (left-associative). Check out Barry’s recent paper or our website for a formal specification and reduction rules using this notation.For readability and brevity, it makes sense to then assign names to trees. For instance:// If we definenot = △ (△ (△ △) (△ △ △)) △false = △true = △ △// then we can say thatnot true --> falsenot false --> trueThe interactive playground on the website allows assigning names to trees just like this and provides additional syntactic sugar for convenience.Combinatory LogicLambda CalculusRewrite RuleRecursionTree Calculus----Written by Johannes Bader64 followers·32 followingDeveloper Experience ImproverHelpStatusAboutCareersPressBlogStorePrivacyRulesTermsText to speech

Tree calculus is presented as a minimal, modular, Turing-complete, and reflective calculus designed to provide an intuitive framework for understanding program representation and reduction, aiming to make concepts like lambda calculus and combinatory logic accessible without relying on Greek letters or parentheses. The core concept of the calculus is that both programs and values are fundamentally represented as unlabeled binary trees, where nodes can be either leaves, stems, or forks. This structure allows for the representation of programs and values in a structured, tree-based manner.

The calculus defines the rules governing how a program, represented as a tree, applies to an argument value, resulting in a new value tree. The representation of expressions explicitly involves an application step, marked by a node, such as an "@" node, which denotes the application of a program (left child) to its input (right child).

The reduction rules are described in detail, introduced by the author, and are often referred to as triage calculus. These rules define how leaves and stems simply absorb their arguments, while forks are the nodes that perform actions. Rules one and two are noted to be analogous to the K and S operators found in combinatory logic, which is sufficient for bootstrapping the $\lambda$-calculus. Rules threea through 3c introduce the concept of triage, allowing the system to reflect on the structure of the argument—whether it is a leaf, a stem, or a fork—to guide the subsequent reduction process, thereby enabling the construction of reflective programs.

The calculus provides a mechanism for constructing increasingly complex programs, suggesting an engineering challenge in designing tree structures for sophisticated computations, such as programs that compute the size of their arguments, which involve recursive notions like fix points.

Aside from the explicit application representation, an alternative perspective for expressing the rules exists where expressions are initially represented as non-binary trees. In this view, arguments are attached to programs as new right-most child trees. The reduction rules in this formulation focus on transforming these non-binary trees into binary trees. This alternative view implies that the application operation is implicitly encoded within the structure, although the author notes that this representation can be less intuitive, citing confusion regarding the meaning of arbitrary subtrees within the rules.

For notation, the text suggests using triangle symbols to denote tree nodes, and names can be assigned to trees to improve readability, allowing for concise expressions of reductions. This notation facilitates the direct mapping of program operations, such as the reduction of "not true" to "true," using tree structures.

The key attributes of tree calculus emphasized are minimality, where a few reduction rules suffice to bootstrap the system; modularity, allowing complex programs to be composed from smaller units; Turing-completeness, demonstrated by its ability to model $\lambda$-calculus through specific rules; and reflectivity, provided by rules that allow programs to analyze and optimize themselves. Implementation efforts have been pursued, with software versions existing in languages like OCaml and JavaScript, demonstrating how the rules can be realized, with some implementations favoring mutation over allocation for memory management.