Tree Calculus

Tree calculus is minimal*,* Turing-complete*,* reflective*,* modular

Tree Calculus was discovered by Barry Jay. It represents a fundamental shift in how we perceive computation by using binary trees as the primary structure for both data and logic.

Minimal

There is one operator that computes whenever it is acting on three values. Values are natural binary trees, categorized into nodes called leaves, stems, or forks.

Practical consequences

• Safe interpreters: Trivial to implement on any platform.
• Config generation: A good fit for cross-platform configuration management.

Turing-complete

Combinatory logic with operators S and K is complete within this system. Unlike λ-calculus, recursive functions can be represented as normal forms, using fixpoint constructions.

Reflective

Tree Calculus performs case analysis on leaves, stems, and forks. Since programs are also values, intensional programs can be self-applied to achieve introspection and reflection.

Practical consequences

• Serialization: Ability to easily serialize programs.
• Program analysis: Optimization and analysis can be treated as standard functions.
• Typing: Simplifies the distinction between static and dynamic typing into simple function calls.

Modular

Sub-terms are represented as sub-trees, allowing complex functionality to be bootstrapped from common components. Powerful programs do not require massive tree structures due to this modular nature.