[ljouhet]

In Python:

    Leaf = []
    Stem = lambda x: [x]
    Fork = lambda a, b: [a, b]

    is_leaf = lambda x: len(x)==0
    is_stem = lambda x: len(x)==1
    is_fork = lambda x: len(x)==2

    def apply(a, b):
        """ From https://treecalcul.us/specification/ (OCaml) """
        if is_leaf(a): return Stem(b)
        if is_stem(a): return Fork(a[0], b)
        x, y = a       # a == Fork(x, y)
        if is_leaf(x): return y
        if is_stem(x): return apply(apply(x[0], b), apply(y, b))
        u, v = x       # x == Fork(u, v)
        if is_leaf(b): return u
        if is_stem(b): return apply(v, b[0])
        s, t = b       # b == Fork(s, t)
        return apply(apply(y, s), t)

    T = {}
    T["false"] = Leaf
    T["true"]  = Stem(Leaf)
    T["not"]   = Fork (Fork (T["true"], Fork (Leaf, T["false"])), Leaf)

    def show(tree):
        name = [k for k in T if T[k]==tree][0]
        print(name or tree)

    show(apply(T["not"], T["false"])) # true
    show(apply(T["not"], T["true"]))  # false

[nemoniac]

And here it is in Racket or Scheme:

    (define (apply a b)
      (cond ((null? a) (list b))
            ((procedure? a) (cons (car a) b))
            ((null? (car a)) (cdr a))
            ((procedure? (car a)) (apply (apply (caar a) b) (apply (cdr a) b)))
            ((null? b) (caar a))
            ((procedure? b) (apply (cdar a) (car b)))
            (else (apply (apply (cdr a) (car b)) (cdr b)))))
    
    (define t-false null)
    (define t-true (list null))
    (define t-not (cons (cons (list null) (cons null null)) null))
    
    (apply t-not t-false)
    (apply t-not t-true)

Leaf is null, Stem is list and Fork is cons.