We maintain a zoo of implementations on GitHub. Contributions welcome! The snippets below are some notable examples.

• 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 △) (\u f (△ u)) (\u \v f (△ u v)) x
  apply = fix $ \self
    triage
      (\u △ u)
      (\u \v △ 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 = △
  _true = △ △
  _not = △ (△ _true (△ △ _false)) △
  apply _not _false # △ △ = _true
  apply _not _true  # △   = _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.

  
  A branch-first evaluator as a regular expression

  Consider a binary encoding of trees, such as bitstr_encode in this demo. The application of two trees with encoding a and b is 0ab and the reduction rules are

  00011ab -> a
  000101abc -> 00ac0bc
  0001001abc1 -> a
  0001001abc01 -> 0b
  0001001abc001 -> 00c
  

  for any subtrees a, b and c. Leveraging capture groups and backreferences, the PCRE expression (1|0(?k)(?k)) matches subtrees (replace k with the actual index of the capture group in the overall regular expression). The resulting PCRE substitutions for the above reduction rules:

  s/00011(1|0(?1)(?1))(1|0(?2)(?2))/$1/g;
  s/000101(1|0(?1)(?1))(1|0(?2)(?2))(1|0(?3)(?3))/00$1${3}0$2$3/g;
  s/0001001(1|0(?1)(?1))(1|0(?2)(?2))(1|0(?3)(?3))1/$1/g;
  s/0001001(1|0(?1)(?1))(1|0(?2)(?2))(1|0(?3)(?3))01/0$2/g;
  s/0001001(1|0(?1)(?1))(1|0(?2)(?2))(1|0(?3)(?3))001/00$3/g;
  

  You can see these rules in action in this demo.