Logical conjunction. Returns True if and only if both operands are True.

(And True True) ;; => True
(And False True) ;; => False

Append list xs to the head of list ys.

(Append (List x y z) (List a b c)) ;; => (List x y z a b c)

Apply tree left-hand tree L to right-hand tree R. L and R are “alternate function invoke” vectors, which, when at the head of an evaluated S-expression, invoke a custom function.

Following reductions listed at Barry Jay’s Reflective Programs in Tree Calculus (2021, pages 5 and 28).

Rules:

• Rule 0a: Δ ␣b → Δb
• Rule 0b: Δa ␣b → Δab
• Rule 1: ΔΔ y␣z → y Kernel Rule, or K-Rule
• Rule 2: Δ(Δx) y␣z → (y␣z)␣(x␣z) Stem Rule, or S-Rule
• Rule 3: Δ(Δwx)y␣z → (z␣w)␣x Fork Rule, or F-Rule

Δ is the tree operator, which represents a node in an unlabelled, binary tree.

a, b, w, x, y, z are arbitrary sub-trees. The letters convey no semantics, but are chosen to help track of their original position.

␣ is the space operator, which represents application of one tree to another.

Note the structural progression. Rules 0a and 0b concern applying a plain leaf and plain stem, respectively. Rules 1, 2, and 3 concern applying a fork whose left value is a plain leaf, plain stem, or fork, respectively.

B combinator. When applied to three arguments, subverts the left-associative application ordering.

(B x y z) ;; => (x (y z))

Branch-First self-evaluator. Apply x to y using a strategy that evaluates all branches before evaluating the root.

(BF Not False) ;; => True

Given eight tree calculus bits b0 to b7, returns a tree calculus byte.

Note: Convert Clojure/Java bits with (map bit->Bit bits)

C combinator. Swaps position of second and third arguments.

(C x y z) ;; => (x z y)

D combinator. When applied to three arguments, reverses order of of first two arguments and broadcasts their application to the third argument.

(D x y z) ;; => ((y z) (x z))

See also d.

Shortcut function for D combinator. The D combinator applied to the first, x, of its three arguments always reduces to (Δ (Δ x)).

(D x y z) ;; => ((Δ (Δ x)) y z)

is equivalent to

((d x) y z)

See page 29 of Reflective Programs in Tree Calculus.

Divide two natural numbers.

(Divide x y) ;; => (/ x y)

Returns True if the two arguments are equal.

(Equal? (Δ Δ) (Δ Δ Δ)) ;; => False

Returns True if two arguments are equal. Variant of Equal? implemented with Triage.

(Equal?-Variant (Δ Δ) (Δ Δ Δ)) ;; => False

Value returned when Type-Check determines that two tags fail to conform. See also Typed-App.

Pattern matching. Returns a function accepting a single argument x, that when applied to x returns various patterns below. Extension requires a pattern p, body s, and a ‘always-applied’ functions r.

Use when you have a pattern (Δ :a :b) and a test (Δ :c :d), and want to ask What is the thing in test at the same location as :a in pattern? Answer: :c.

See unit tests for example usage.

Variant of Extension that uses native tree calculus predicates, i.e., does not rely on Clojure host’s conditional form.

Logical false. Opposite of True.

(Not False) => True

In the operator position, returns the second of two arguments.

Returns the first element of a Pair.

(First (Pair x y)) ;; => x

See also Second.

Apply a function f to an initial value x and the first element of a list y, then apply the function to that result and next element of the list, etc.

(Fold-Left Divide sixty (List three four)) ;; => five

Apply function f to an initial value x and a value obtained by applying f to the first element of list y and the value obtained by applying f to the second element, etc.

(Fold-Right Divide one (List sixty one-hundred-twenty four)) ;; => two

Returns True when supplied with a fork, otherwise False.

(Fork? ΔΔΔ) ;; => True

See also Leaf? and Stem?.

When argument is a:

• leaf, returns (K K)
• stem of form (Δ x), returns (K (Δ x (K (K Δ))))
• fork, returns Δ.

Used by Triage.

Returns the tag of a tagged form.

(Get-Tag (Tag t f)) ;; => t

See also Tag and Get-Tag.

I combinator. When applied to a single argument, x, returns exactly x, i.e., its identity.

(I x) ;; => x

Biconditional. Returns True if both operands are True or both operands are False.

(Iff True True) ;; => True
(Iff True False) ;; => False
(Iff False True) ;; => False
(Iff False False) ;; => True

Material implication. Returns True if and only if first operand is True and the second operand is False.

(Implies True False) ;; => True
(Implies True True) ;; => False
(Implies True False) ;; => False
(Implies False False) ;; => False

K combinator. When supplied with two arguments, returns the first, discarding the second.

(K x y) ;; => x

Returns True when supplied with a leaf, otherwise False..

(Leaf? Δ) ;; => True

See also Stem? and Fork?

Returns a tree calculus list containing elements of args

Apply a function to each element of a list.

(Map Successor (List x y z)) ;; => (List (Successor x) (Successor y) (Successor z))

Subtract two natural numbers.

(Minus x y) ;; => (- x y)

For all thingys, applies Apply until args exhausted.

Logical negation. Returns opposite Boolean.

(Not True) ;; => False
(Not False) ;; => True

Logical disjunction. Returns True if either of two operands are True.

(Or True False) ;; => True
(Or False False) ;; => False

Returns a 2-tuple of x and y.

See also First and Second.

(First (Pair x y)) ;; => x
(Second (Pair x y)) ;; => y

Add two natural numbers.

(Plus x y) ;; => (+ x y)

Returns the previous natural number.

(Predecessor n) ;; => (- n 1)

See also Successor.

Quotation. Halts immediate application. Recursively descends through a tree and pushes all nodes to leaves of the quoted form. Quoted trees are explicitly consumed by Root and RB, and implicitly by RF.

(Quote (Δ Δ Δ)) ;; => (Δ (Δ Δ Δ) Δ)

Root-Branch self-evaluator. Performs root evaluation then recursively evaluates the branches to produce a normal form. Consumes a single tree, a fork whose branches are each Quoted.

(RB (Δ (Quote Not) (Quote False))) ;; => True

Reverses list z.

(Reverse (List a b c)) ;; => (List c b a)

Root-First self-evaluator. Applies f to z, quotation implicit.

(RF Not False) ;; => True

Root self-evaluator. Apply m to n, doing only enough computation to determine the nature of the root. Requires Quote-ing the arguments.

Relationship between the input and output are not straightforward. E.g.,

(Root (Δ (Quote (Δ y)) (Quote z))) ;; => (Δ (Quote y) (Quote z))

See RB and RF for more ergonomic evaluators.

S combinator. When applied to three arguments, broadcasts the third argument to each of the first two arguments.

(S x y z) ;; => ((x z) (y z))

Returns the second element of a Pair.

(Second (Pair x y)) ;; => y

See also First.

Applies a single argument to itself.

(Self-Apply x) ;; => (x x)

Returns the number of nodes in the argument.

(Size (Δ Δ Δ)) ;; => three

Returns the number of nodes in argument. Variant of Size implemented with Triage.

(Size-Variant (Δ Δ Δ)) ;; => three

Returns True when supplied with a stem, otherwise False..

(Stem? ΔΔ) ;; => True

See also Leaf? and Fork?.

Returns Δ if argument is a leaf or a fork, or returns (Δ (K (K Δ)) (x (K (K Δ)))) for a stem of form (Δ x). Used by Triage.

Returns the next natural number.

(Successor n) ;; => (+ n 1)

See also Predecessor.

Swap the argument order of 2-arity function f.

((Swap f) x y) ;; => (f y x)

Construct a list by appending h to list t.

(T-Cons h (List t1 t2 t3)) ;; => (h t1 t2 t3)

Returns the head of a list.

(T-Head (List x1 x2 x3)) ;; => x1

Empty list.

Returns the tail of a list.

(T-Tail (List x1 x2 x3)) ;; => (List x2 x3)

Apply a tag t to form f. The tagged f applied to some other argument x is indistinguishable from untagged f applied to the same argument x.

((Tag t f) x) ;; => (f x)

See also Get-Tag and Un-Tag.

Multiply two natural numbers.

(Times x y) ;; => (* x y)

Applies a specified function, fn, depending on whether argument is a leaf, stem, or fork.

If argument is a:

• leaf Δ, returns (f0)
• stem (Δ x), returns (f1 x)
• fork (Δ x y), returns (f2 x y)

Logical true. Opposite of False.

(Not True) ;; => False

In the operator position, returns the first of two arguments.

Compare tags of x and u. Returns error if tags do not conform. See also Typed-App.

Typed application. Apply tagged function f to tagged argument x, returning a tagged value.

(Typed-App (Tag True Successor) (Tag True n)) ;; => (Tag true (+ n 1))

Recover f after tagging.

(Un-Tag (Tag t f)) ;; => f

See also Tag and Get-Tag.

W combinator. Duplicates the second argument.

(W x y) ;; => (x y y)

Y combinator. Recursively apply a function to itself.

(Y f) ;; => (f (Y f))

Tagged Y combinator. Apply tag t to fixpoint function f.

(Y-t t f) ;; => (f (Y-t t f))

Tags can not be added after the fixpoint has been formed, so the usual Y combinator can not be used.

Returns True if operand, a tree representation of a natural number, is zero, False otherwise.

Node operator. Both a value and a function. By itself, equivalent to an empty Clojure vector. When at the head of an evaluated list, behaves as a function, invokes Apply, the tree calculus application rules.

(Δ) ;; => Δ, or equivalently []

(Δ x) ;; returns a stem of x
(Δ x y) ;; returns a fork of x and y```