Branch-first evaluator in OCaml

Try this at try.ocamlpro.com

(* TC       |  OCaml
 * ---------+-------------
 * △        |  Leaf
 * △ a      |  Stem a
 * △ 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 *)

Branch-first evaluator in tree calculus

Try this right here

eager = \f \x triage (f t) (\u f (t u)) (\u \v f (t u v)) x
apply = fix $ \self
  triage
    (\u t u)
    (\u \v t u v)
    (triage
      (\u2 \v u2)
      (\u1 \u2 \v eager (self (self u1 v)) (self u2 v))
      (\u0 \u1 \u2 \v
        triage
          u0
          (\v self u1 v)
          (\v1 \v2 self (self u2 v1) v2)
          v))

# Example: Negating booleans
_false = t
_true = t t
_not = t (t _true (t t _false)) t
apply _not _false # t t = _true
apply _not _true  # t   = _false
# Direct evaluation for reference
_not _false
_not _true

More efficient branch-first evaluator in JavaScript

Try this at runjs.app

// TC       |  JS
// ---------+-----------
// △        |  []
// △ a      |  [a]
// △ a b    |  [b, a]
// △ 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

A root-first evaluator in Haskell by James Eversole

James in fact created a purely functional interpreted language, tricu (pronounced “tree-shoe”), that uses tree calculus.