Tree Calculus

Original Article ↗ Hacker News Discussion ↗

Tree Calculus is presented as an extremely minimal, tree-based computational calculus where all programs are unlabeled trees and evaluation is defined by a handful of reduction rules, making it Turing-complete and capable of reflecting on its own structure. Commenters compare it to lambda calculus, SKI combinators, and homoiconic languages like Lisp, noting that its key claimed advantage is “intensionality”: programs are already data, so analysis, transformation, and even attempts at function inversion can be expressed within the same system without separate quotation or ASTs. While many find the core idea theoretically elegant and potentially useful as a universal intermediate representation or configuration language, others criticize the website’s opaque presentation and question the practicality and performance of such a low-level formalism in real-world programming.

What Tree Calculus Is

  • Formal system where every expression is an unlabeled ordered tree built from a single symbol t with application: E ::= t | E E.
  • Semantics given by a handful of small-step rewrite rules on trees.
  • Trees with 0, 1, or 2 children represent values; nodes with 3+ children represent computations to be reduced.
  • Programs and data are the same kind of trees; booleans, pairs, lists, numbers, and strings are all encodings on top of this.

Relation to Other Calculi and Languages

  • Closely related to combinatory logic, especially SK calculus; two of the rules correspond directly to K and S.
  • Can encode SKI, fixed-point combinators, and thus is Turing-complete.
  • Compared frequently to lambda calculus: similar expressive power but different primitives (trees + triage instead of lambdas + substitution).
  • Compared to Lisp/Forth/APL/Prolog: like a homoiconic, reflective core calculus, but reflection happens on the raw program trees rather than quoted ASTs.

Intensionality, Reflection, and “Inversion”

  • Key claimed feature: intensionality—programs can inspect and branch on their own tree structure, not just their extensional behavior.
  • This enables “honest reflection”: self-evaluation, program analysis, optimization, serialization, and type-checking defined within the calculus, without an external quoting layer.
  • “Invert function” demos impress some readers, but others note inversion must be partial (halting-problem limits) and similar capabilities exist in APL, Prolog, and other systems.

Usefulness and Performance

  • Proposed uses: universal intermediate representation, configuration-as-code with first-class functions, self-hosted optimizers (e.g., stream fusion).
  • Some see it as mainly of theoretical interest, analogous to unary counting or SKI: elegant but unwieldy.
  • Concern about performance: e.g., thousands of reduction steps for simple tasks like lowercasing a string; counterpoint is that compiled patterns and JITs could mitigate this.

Website Design and Communication

  • Many readers find the landing page confusing: marketing-style headings, dense academic text, but little plain explanation of “what this is.”
  • Frequent requests for a “for dummies” intro, a one-sentence definition, and clear separation between the bare calculus and the sugared programming language.
  • Several commenters emphasize that diagrams of the tree rules and visualizations greatly improve comprehension.

Learning Resources and Theory

  • References shared to a detailed book, technical papers (including a typed version), and Coq proofs.
  • Multiple community-made expositions and toy interpreters (OCaml, JS, Python, Scheme/Racket) help clarify the reduction rules and encodings.