Tree Calculus

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.