Tree Calculus
What Tree Calculus Is
- Formal system where every expression is an unlabeled ordered tree built from a single symbol
twith 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
KandS. - 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.