Definition: Tree Calculus expressions $E$ have abstract syntax $E::=\mathrm{\Delta }|EE$ and are reduced according to the following small-step semantics:

$$\begin{array}{rlrlrlrlrlrl}& \mathrm{\Delta }& & \mathrm{\Delta }& & a& & b& & ⟶a& & (1)\\ & \mathrm{\Delta }& (& \mathrm{\Delta }a)& & b& & c& & ⟶ac(bc)& & (2)\\ & \mathrm{\Delta }& (& \mathrm{\Delta }ab)& & c& & \mathrm{\Delta }& & ⟶a& & (3a)\\ & \mathrm{\Delta }& (& \mathrm{\Delta }ab)& & c& (& \mathrm{\Delta }u)& & ⟶bu& & (3b)\\ & \mathrm{\Delta }& (& \mathrm{\Delta }ab)& & c& (& \mathrm{\Delta }uv)& & ⟶cuv& & (3c)\end{array}$$

Notation: Binary operator is left associative, unless overridden using parentheses.

Conventions:

• We call irreducible expressions “values”.
• We can think of expressions as unlabeled trees, generated by interpreting every subexpression $(\mathrm{\Delta }arg\dots arg)$ as a node with $arg\dots arg$ as child trees. Note that this is not the same as the ASTs that arise from the abstract syntax above (they would have inner nodes that represent the $EE$ “function application” operator, while the trees we propose have inner/all nodes correspond to one $\mathrm{\Delta }$ each).
  • We call expression $\mathrm{\Delta }$ “leaf”.
  • We call expressions $\mathrm{\Delta }a$ “stem of $a$”.
  • We call expressions $\mathrm{\Delta }ab$ “fork of $a$ and $b$”.

Tip: Check out Timur Latypoff’s visualization of these rules and conventions. Thanks Timur!

Consequences:

• Values are binary trees, i.e. only consist of leafs, stems and forks: As long as there is a subexpression $(\mathrm{\Delta }abc)$, one of the reduction rules apply.
• Tree Calculus is Turing complete: Reduction rules $1$ and $2$ are analogous to K and S combinators.
• Tree Calculus is intensional: Rules $3a\text{-}c$ allow reflecting on values by distinguishing leafs, stems and forks.
• Tree Calculus is confluent: The five reduction rules are non-overlapping and only allow observing values, not reducible expressions.

For significantly more detail and discussion, read Reflective Programs in Tree Calculus by Barry Jay. (Note: the reduction rules above are a revised version of the ones presented in the book.)

Example reduction: Negating booleans

If we define $\mathtt{\text{false}}=\mathrm{\Delta }$, $\mathtt{\text{true}}=\mathrm{\Delta }\mathrm{\Delta }$ and $\mathtt{\text{not}}=\mathrm{\Delta }(\mathrm{\Delta }(\mathrm{\Delta }\mathrm{\Delta })(\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }))\mathrm{\Delta }$ then

$$\mathtt{\text{not}}\mathtt{\text{false}}\stackrel{\text{def}}{=}\mathrm{\Delta }(\mathrm{\Delta }(\mathrm{\Delta }\mathrm{\Delta })(\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }))\mathrm{\Delta }\mathrm{\Delta }\stackrel{\text{3a}}{⟶}\mathrm{\Delta }\mathrm{\Delta }\stackrel{\text{def}}{=}\mathtt{\text{true}}$$

and

$$\mathtt{\text{not}}\mathtt{\text{true}}\stackrel{\text{def}}{=}\mathrm{\Delta }(\mathrm{\Delta }(\mathrm{\Delta }\mathrm{\Delta })(\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }))\mathrm{\Delta }(\mathrm{\Delta }\mathrm{\Delta })\stackrel{\text{3b}}{⟶}\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\stackrel{\text{1}}{⟶}\mathrm{\Delta }\stackrel{\text{def}}{=}\mathtt{\text{false}}$$

The tree representation of $\mathtt{\text{not}}$ is

• Basic implementation in OCaml

  Try this at try.ocamlpro.com

  (* TC       |  OCaml
   * ---------+-------------
   * t        |  Leaf
   * t a      |  Stem a
   * t a b    |  Fork (a, b)
   *)
  
  type t =
    | Leaf
    | Stem of t
    | Fork of t * t
  
  let rec apply a b =
    match a with
    | Leaf -> Stem b
    | Stem a -> Fork (a, b)
    | Fork (Leaf, a) -> a
    | Fork (Stem a1, a2) -> apply (apply a1 b) (apply a2 b)
    | Fork (Fork (a1, a2), a3) ->
      match b with
      | Leaf -> a1
      | Stem u -> apply a2 u
      | Fork (u, v) -> apply (apply a3 u) v
  
  (* Example: Negating booleans *)
  let _false = Leaf
  let _true = Stem Leaf
  let _not = Fork (Fork (_true, Fork (Leaf, _false)), Leaf)
  apply _not _false (* Stem Leaf = _true  *)
  apply _not _true  (* Leaf      = _false *)
  

• More efficient implementation in JavaScript

  Try this at runjs.app

  // TC       |  JS
  // ---------+-----------
  // t        |  []
  // t a      |  [a]
  // t a b    |  [b, a]
  // t a b c  |  [c, b, a]
  
  const apply = (a, b) => {
    const expression = [b, ...a]
    const todo = [expression];
    while (todo.length) {
      const f = todo.pop();
      if (f.length < 3) continue;
      todo.push(f);
      const a = f.pop(), b = f.pop(), c = f.pop();
      if (a.length === 0) f.push(...b);
      else if (a.length === 1) {
        const newPotRedex = [c, ...b];
        f.push(newPotRedex, c, ...a[0]);
        todo.push(newPotRedex);
      }
      else if (a.length === 2)
        if (c.length === 0) f.push(...a[1]);
        else if (c.length === 1) f.push(c[0], ...a[0]);
        else if (c.length === 2) f.push(c[0], c[1], ...b);
    }
    return expression;
  };
  
  // Example: Negating booleans
  const _false = [];
  const _true = [[]];
  const _not = [[],[[_false,[]],_true]];
  apply(_not, _false); // [[]] = _true
  apply(_not, _true);  // []   = _false