Tree Calculus

# A visual introduction to tree calculus Source: [https://olydis.medium.com/a-visual-introduction-to-tree-calculus-2f4a34ceffc2](https://olydis.medium.com/a-visual-introduction-to-tree-calculus-2f4a34ceffc2) Press enter or click to view image in full size The reduction rules of[triage calculus](https://github.com/barry-jay-personal/blog/blob/main/2024-12-12-calculus-calculi.md)\. 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](https://latypoff.com/tree-calculus-visualized/)\! ## Why is it useful? How does it work? [](https://olydis.medium.com/?source=post_page---byline--2f4a34ceffc2-----------------------------------------) Tree calculus is a[minimal, modular, Turing\-complete and reflective](https://treecalcul.us/)calculus\. The goal of this post is to convey this, quickly and intuitively\. I strongly recommend reading Barry’s[book](https://github.com/barry-jay-personal/tree-calculus/blob/master/tree_book.pdf),[blog](https://github.com/barry-jay-personal/blog)or[recent paper](https://github.com/barry-jay-personal/typed_tree_calculus)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](https://github.com/barry-jay-personal/blog/blob/main/2024-12-12-calculus-calculi.md)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 motivation Before 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 size Press enter or click to view image in full size Press enter or click to view image in full size **Left**: 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](https://treecalcul.us/#minimal), yet it is also[reflective](https://treecalcul.us/#reflective), which allows it to[do exciting things](https://github.com/barry-jay-personal/blog/blob/main/2024-12-14-logic.md)directly and[safely](https://github.com/barry-jay-personal/blog/blob/main/2024-12-20-infinity.md)\. Dig into the linked resources to learn exactly how and why, but the gist is: Tree calculus is[minimal](https://treecalcul.us/#minimal)\(note narrow, almost singularity\-like “base” of the funnel\), which makes it nice to reason about and[trivial to run in any environment](https://treecalcul.us/implementation/)— including pen and paper\. It can do more than λ\-calculus natively \([reflective](https://treecalcul.us/#reflective),[finite normal forms for recursive programs](https://github.com/barry-jay-personal/blog/blob/main/2024-12-20-infinity.md)\), which also reduces the distance between core calculus and high\-level applications\.[Our website](https://treecalcul.us/)hosts a number of fully self\-contained, interactive demos that aim to convey that\. Enough context, let’s get started\! ## Tree Calculus Think 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](https://treecalcul.us/specification/)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 Data If 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 size Suggestion 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, etc### Running Programs > In[his 2021 book](https://github.com/barry-jay-personal/tree-calculus/blob/master/tree_book.pdf), 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](https://github.com/barry-jay-personal/blog/blob/main/2024-12-12-calculus-calculi.md)\. This post and[our website](https://treecalcul.us/)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 size The reduction rules of[triage calculus](https://github.com/barry-jay-personal/blog/blob/main/2024-12-12-calculus-calculi.md)\. 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](https://en.wikipedia.org/wiki/Combinatory_logic#Completeness_of_the_S-K_basis)\. 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 Programs From 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 size The “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](https://treecalcul.us/)hosts various more advanced demos, such as a[program optimizer](https://treecalcul.us/live/?example=demo-fusion)or programs that[emit trees as programs in other languages](https://treecalcul.us/live/?example=demo-portability)\. 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](https://treecalcul.us/live/)is a tree of size ~200k\. ### Conclusion Hopefully 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](https://treecalcul.us/#minimal): Programs are trees, few reduction rules bootstrap everything\. - [Modular](https://treecalcul.us/#modular): Programs can be composed into larger programs\. - [Turing\-complete](https://treecalcul.us/#turing-complete): Tree calculus can model λ\-calculus via rules 1 and 2\. - [Reflective](https://treecalcul.us/#reflective): Rules 3 allow reflecting on programs, e\.g\.[to optimize them](https://treecalcul.us/live/?example=demo-fusion)\. ### Appendix: An alternative way to think of expressions and reduction This 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 size An 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: Implementation If 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](https://treecalcul.us/implementation/)\. 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: Notation Pictures 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](https://github.com/barry-jay-personal/typed_tree_calculus)or[our website](https://treecalcul.us/specification/)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 --> true ``` The[interactive playground on the website](https://treecalcul.us/live/)allows assigning names to trees just like this and provides additional syntactic sugar for convenience\.