trlisp

Setup

Leiningen/Boot

[com.sagevisuals/trlisp "0"]

Clojure CLI/deps.edn

com.sagevisuals/trlisp {:mvn/version "0"}

Require

(require '[tree-calculus.definitions :refer :all])

Introduction

Barry Jay's unlabelled binary tree calculus is reflective, which means we can inspect the internal structure of every  function. Without quotation, every function is always open to:

• Inspection We may view the function's structure and  contents.
• Analysis We may measure the function's size, etc.
• Comparison We may test two functions for equality,  equivalence, etc.
• Optimization We may precompute some static branch of the  function, or alter it for more efficiency.
• Decomposition We may pull out different pieces of the  function, perhaps for use in a different context.
• Modification We may change some facet of the function at  runtime to suit our needs.

trlisp is an implementation of tree calculus with Lisp's compact,  uniform grammar. The element at the head of a list, the function position, is  invoked, with the elements of the tail of the list providing the arguments.

Unlike traditional Lisps, trlisp functions may be transparently decomposed  so that the function may be inspected, analyzed, compared, optimized,  decomposed, and modified, without the need for quotation. That is to say,  trlisp functions are reflective.

trlisp is intended to be used to explore practical questions such  as

• How useful is it to have unquoted access to the contents of a function?
• Can new functions be composed from pulled-apart pieces of others?
• Could a function be automatically inverted?

Usage

Lisp-y

trlisp inherits its evaluation model from its host, Clojure, a  Lisp dialect. In Lisp, the fundamental evaluation unit is a list enclosed in  parentheses. The first element of the list is the function, and any trailing  list elements are the function's arguments, like this.

(function argument-1 argument-2 ... argument-n)

If we'd like to sum the integers two and three, we'd write this.

(+ 2 3)

In this example, the parentheses contain the expression we'd like to  evaluate. The symbol for addition, +, is the first  element, so it serves as the function. The trailing elements, integers 2 and 3, supply the two arguments to +.

When we evaluate the expression (+ 2 3), we obtain a  value, integer 5.

(+ 2 3) ;; => 5

trlisp follows this model. Parenthesized lists form a unit of evaluation,  with the function at the head of the list applying to zero or more arguments  in the tail.

Δ, the do-everything operator

A notable aspect of tree calculus is that every thing, functions as well as values, is composed of a single, basic unit, Δ. So we must continually keep in mind that there is not a strict delineation  between tree calculus functions, such as the + function, and tree calculus scalar values, such as integer 3. Every entity in tree calculus is a binary tree composed only of different  patterns of Δ. The application rules govern how one or two trees produce another tree.

Tree calculus defines six application rules. Five rules are the result  of dispatching on whether the tree in the function position of the list is a  leaf, stem, or fork, the last of which further dispatches on whether the left  child is a leaf, stem, or fork.

The sixth rule is merely the degenerate case with zero arguments, which  we'll discuss first.

Rule 0: Applying a leaf to nothing

Let's imagine a picture of the first rule: applying a leaf to nothing.

Δ

It doesn't look like much. Just a Greek delta character floating on the  page, but as the rules progress and we add more elements, our picture will  become more informative.

Applying the Δ operator to zero arguments returns merely itself. We put the node symbol in  function position of the list, followed by zero arguments, and evaluate the  expression.

(Δ)

This returns a single tree node with zero children.

Often, a function definition will involve a bare leaf in the middle of a  sequence of applications, so those parentheses might get visually distracting.  If we only need a bare leaf, we may skip the parentheses.

(= (Δ) Δ) ;; => true

We can see that (Δ) and Δ are equivalent.

Rule 1: Applying a leaf to something

Our picture grows with Rule 1. Since we are applying a leaf to something,  we'll imagine a leaf as before, plus something else standing to its right.  Let's call it z.

Δ     z

z will be some unspecified tree that can be operated on,  either another leaf, a stem, or some unspecified fork.

To make our picture exceedingly explicit, let's introduce a symbol ␣ to visually separate the function and the argument.

Δ  ␣  z

We can interpret that picture as Function Δ applied to argument z.

As with all Lisps, trlisp uses parentheses for function invocation. To  evaluate that expression, we put the function Δ at the head of the list and the single argument z in the tail.

(Δ z)

A Lisp programmer would read that expression as Function Δ applied to argument z, which is the same interpretation we just gave our picture.

When the Δ function is evaluated with one argument, a stem  results with the argument forming the single child branch. Here is a picture of  the result.

Δ
|
z

The expression returns a stem: a root node at the top, with a single child  element z branching straight off its bottom.

Rule 2: Applying a stem

Let's visualize applying a stem to something.

Δ
|  ␣  z
x

The stem, serving as our function, is on the left and applies to the  argument immediately to its right, the z, which may be any valid tree.

To evaluate this in trlisp, we put a stem in the function position and the  argument in the tail. Let's take it step by step. To compose the function, a  stem, we'll recall the previous subsection where we constructed a stem by applying a leaf node to something.

(Δ x)

The stem we just now composed consists of a root node at top and an  unspecified child tree x.

Now we have a stem in hand to serve as a function. We place that stem at  the head of our list, followed by the argument, some unspecified tree z.

((Δ x) z)

Tree calculus declares that evaluating that expression yields a fork,  with x forming the left child branch and z forming the right child branch.

We could visualize the result like this.

  Δ
 / \
x   z

Root node at top and two children, in order, branching off the bottom.

An upcoming section discusses ways to write this more efficiently.

Note that application Rules 0, 1, and 2 form a basis for  constructing trees. Applying a bare leaf to nothing returns a leaf. Applying a  leaf to something creates a stem. And applying a stem creates a fork.

Application Rules 3, 4, and 5 involve applying three varieties of  forks. When applying a fork, trlisp dispatches on whether the left child itself  is a leaf, stem, or fork.

Rule 3: Applying a fork with left child leaf

Here is a picture of applying a fork, where the left child is a leaf, to  an argument z.

  Δ
 / \   ␣  z
Δ   y

Both the right child branch y and argument z can be any valid tree.

To express this application in trlisp, let's first construct the function,  a fork. We know how to construct a fork from the previous subsection. A fork is constructed by applying a stem to something, and a stem itself is  constructed by applying a leaf to something. We'll do each step in turn.

The left branch of our function is a leaf, so we need a root node and a  child Δ. To construct a stem, we apply a leaf to another leaf.

(Δ Δ)

We visualize that resulting stem like this.

Δ
|
Δ

Now that we have a stem, we know from Rule 2 that applying a stem to  something constructs a fork. So we can apply that stem to some branch y.

((Δ Δ) y)

Which produces a tree that will serve as our function.

  Δ
 / \
Δ   y

A root node at top, a leaf node is the left child, and some subtree y is the right child.

Finally, we insert this function at the head of the list and supply z as the argument in the tail position.

(((Δ Δ) y) z)

Tree calculus declares that if the left child of a fork is a leaf,  application of that fork to anything returns the fork's right branch and  discards the argument. In this case, the function's right child is y, which is returned. Argument z is discarded.

One way to look at this is the sequential application of a stem to two  arguments y, then z.

Δ
|  ␣  y  ␣  z
Δ

This is a pattern that we see repeatedly in tree calculus: Applying a  stem to two arguments selects the first of two arguments y and discards the second argument z.

trlisp strives to be forgiving when it comes to parentheses. We  can discard any pair of parentheses if the implied left-association holds. The  following

(((Δ Δ) y) z)
 ((Δ Δ) y  z)
 ((Δ Δ  y) z)
  (Δ Δ  y  z)

are all equivalent: All return y.

Rule 4: Applying a fork with left child stem

Here is a picture of a function composed of a fork with a left child  stem.

  Δ
 / \
Δ   y  ␣  z
|
x

Working up from the bottom, the left child stem is itself composed of a  node with some unspecified tree x as it single child. To make this stem

Δ
|
x

we evaluate

(Δ x)

Then, to make our desired fork, we supply that stem as the left child  branch and some unspecified tree y as the right child branch.

(Δ (Δ x) y)

Which evaluates to this picture.

  Δ
 / \
Δ   y
|
x

See the note at the end of the previous subsection on why we're allowed to sometimes drop  parentheses.

Finally, we apply this function to some unspecified tree as argument z by inserting the function at the head of the list and the  argument in the tail.

((Δ (Δ x) y) z)

Tree calculus declares this expression to evaluate to

((y z) (x z))

The order of the function's right child y and left grandchild x are swapped, and the argument z is broadcast to each. Then the result of the first evaluation is applied to  the result of the second evaluation. This pattern often appears in definitions  because it's useful to be able to swap two items.

Rule 5: Applying a fork with left child fork

The final application rule involves a function whose left fork is itself a  fork. Let's visualize that situation.

    Δ
   / \
  Δ   y  ␣  z
 / \
w   x

Examining the function on the left, we see a child fork with two branches,  designated w and x. Using what we've discussed so far, let's construct this function from the  bottom up. We know how to construct a fork, so let's make one with a left  branch some unspecified w and right branch some unspecified x.

(Δ w x)

That trlisp expression creates this sub-tree.

  Δ
 / \
w   x

With that sub-tree in hand, let's move up one level. That sub-tree becomes  the left child of the root node, while some unspecified tree y becomes the right child node.

(Δ (Δ w x) y)

Now we have this picture.

    Δ
   / \
  Δ   y
 / \
w   x

This is our function, which we insert into the head of our trlisp  expression, followed by some unspecified argument z

((Δ (Δ w x) y) z)

to obtain our final expression.

Tree calculus declares that this expression evaluates to the following.

(z w x)

Applying a fork with a left child fork results in making the argument z the new function, with the decomposition of the function's left child's  branches w and x the new arguments. This pattern is useful when we need to pull apart a fork  and send the pieces to a function.

The next two subsections introduce a few conveniences.

Variadic application

trlisp provides a convenience to minimize parentheses: We may supply any  number of arguments and trlisp will sequentially apply them by  left-association. For example, when we evaluate the Δ function with two arguments, we obtain a fork. Let's supply arguments x and y, two unspecified trees.

(Δ x y)

When evaluated, this returns a fork, a node whose left child is some  tree x and whose right child is y, some other tree. Under the hood, trlisp applied Δ to x, then applied that result to y, exactly as if we had evaluated

((Δ x) y)

This principle can be extended as needed. Five applications

(((((Δ Δ) Δ) Δ) Δ) Δ)

may be more succinctly written like this

(Δ Δ Δ Δ Δ Δ)

with the understanding that application is left-associative.

Variable binding and convenience functions

Usually, we'll find it convenient to forgo combinatory logic's goal of  avoiding names. In those situations, we can rely on our host platform's  variable binding to give meaningful names to commonly used trees. Clojure's def binds a name to a value.

(def foo (Δ Δ))

Here, we bound the Clojure symbol foo to a two-node stem. Now we can use foo in future expressions, and it will evaluate to (Δ Δ).

Also, we will sometimes find it convenient to use a lambda calculus-like  expression. We can express

λa.λb.ab

as

(fn [a] (fn [b] (a b)))

in Clojure.

In trlisp , such a function will appear hanging off a tree somewhere. We  might see something like this.

    Δ
   / \
  Δ   y  ␣  z
 / \
w   (fn [a] (fn [b] (a b)))

trlisp's application machinery handles that tree without any additional  effort from us.

Application rules quick summary

Here are all six application rules at once. Notice that the first three  rules describe how to construct a leaf, stem, or fork. The last three rules  describe how to evaluate the application of a fork with a left child leaf, a  left child stem, and left child fork, respectively.

Δ ␣ 

 (Δ)      = Δ

Δ ␣ z

((Δ)   z) = (Δ   z)

Δ
|  ␣  z
x

((Δ x) z) = (Δ x z)

  Δ
 / \   ␣  z
Δ   y

((Δ  Δ      y) z) = y

  Δ
 / \
Δ   y  ␣  z
|
x

((Δ (Δ   x) y) z) = ((y z) (x z))

    Δ
   / \
  Δ   y  ␣  z
 / \
w   x

((Δ (Δ w x) y) z) = (z w x)

And that's it. One operator and six rules are all that is necessary for a  combinatorially-complete system.

Implementation Note

Tree calculus trees have a dual nature: they are both structures and  functions. That is, trees contain an arbitrary pattern of descendants, but at the same time, they  conceptually apply a transform to an argument. Any implementation must therefore capture these  two properties.

Clojure vectors are handy because, while they are exceedingly capable at  storing and retrieving arbitrary values, they support an interface that allows  them to behave as a Lisp function. When a Clojure vector is placed in the  function position of a list and an integer argument follows in the tail, the  vector invokes an implied accessor function, nth, which returns the value at the index.

For example, we could explicitly access the third element with nth like so.

;; plain Clojure
(nth [98 99 100] 2) ;; => 100

Equivalently, we could rely on a Clojure vector's ability to behave as a  Lisp function.

;; plain Clojure
([98 99 100] 2) ;; => 100

Putting a vector at the head of a list is a widely-used Clojure idiom.

Since Clojure hosts trlisp, vectors possess the machinery to serve as  functions. We merely need to change that machinery from the accessor  function nth to a different machine that implements tree calculus' application rules.

trlisp models a tree as an altered Clojure vector containing up to two other such altered vectors. These nested vectors  provide the reified structure representing tree calculus' unlabelled binary  trees. Since trlisp's vectors are altered so that the invocation machinery  implements tree calculus' application rules, these nested vectors may serve as  functions when placed at the head of a list.

A single node is simply an empty vector, i.e., it has no descendants. We  can observe this by evaluating a bare node.

(Δ) ;; => []

Applying the Δ function to nothing returns trlisp's literal representation, an empty  vector.

Let's consider a simple stem.

Δ
|
Δ

We can construct a node with a single child leaf by applying one node to  another node.

(Δ Δ) ;; => [[]]

Now we see that the parent vector contains a single element, another  vector of the same kind.

We could have equivalently written the following.

([] []) ;; => [[]]

If these were Clojure's normal vectors, evaluating that expression would  result in an error. But since trlisp uses a special vector that implements tree  calculus' application rules, it works fine.

The first special vector in the function position [] applied to another special vector [] invokes tree calculus' application rules. In this case, according to  Rule 1, a leaf (empty vector) applied to another tree (also a leaf in this  case), constructs a stem.

Extending this principle further, consider this simple fork.

  Δ
 / \
Δ   Δ

(Δ Δ Δ) ;; => [[] []]

Here we see that the root vector now contains two child vectors.

trlisp's main usefulness in exploring tree calculus is the fact that these  special vectors invoke the tree calculus application rules instead of the  built-in nth.

One practical consequence of using vectors this way is that rendering  trees as nested empty vectors is not very ergonomic for human eyes. After some  practice, it's not too difficult to mentally translate (Δ Δ Δ) to

  Δ
 / \
Δ   Δ

but it requires much more eyestrain to see that both are equivalent to

[[] []]

And it only gets worse as the trees grow beyond three nodes.

One option is to use Clojure keywords to represent arbitrary subtrees.  The evaluation of this expression

(Δ :a :b) ;; => [:a :b]

can be visualized like this.

   Δ
  / \
:a   :b

But we can't use this option when a Clojure keyword would end up in the  function position of a tree application rule, like in Rule 4,

;; this won't work
((:a :b) (:c :d))

because Clojure keywords don't implement the tree calculus application  rules.

In that case, we must define concrete trees to which to apply the rules.

(def h Δ)
(def i Δ)
(def j Δ)
(def k Δ)

((h i) (j k)) ;; => [[] [[]]]

The expression can now return a valid value, but we are still left with  the problem of figuring out what the tree [[] [[]]] looks like.

trlisp doesn't currently (and may never) have a utility which renders tree  diagrams. When walking through our discussion, I will silently replace things  like [[] [[]]] with its equivalent (Δ Δ K).

Just keep in mind that if you are evaluating trlisp expressions on your  own computer, you will see [[] [[]]].

To illustrate how function trees apply to arguments trees and return  other trees, we can test for equality with the expected value. For example,  Rule 2 tells us that a stem applied to an argument leaf returns a fork with  the argument leaf as the right child.

((Δ Δ) Δ) ;; => [[] []]

That's...okay. But working it out with pencil and paper, we expect it to  return (Δ Δ Δ). Is that the case?

(= ((Δ Δ) Δ)
   (Δ Δ Δ)) ;; => true

Yup. The value returned from the original application, in the upper row,  is equal to the value returned by the expression in the lower row. By directly  comparing return values with =, we don't have to squint at a pile of nested square brackets.

Conventions

Clojure names are lower-case-with-hyphens, such as inc, first, and map. trlisp names are Upper-Case-With-Hyphens, such as Inc, First, and Map.

The exceptions are:

• d

  The D combinator already claims the capital 'D'. Since the d function is used extensively in definitions, and it is so closely related  to the D combinator, I chose to keep it as a single, lower-case 'd'.

• error

  Java (Clojure's host) already uses Error.

• Conversion utilities that accept Clojure types (which are lower-cased)  and return trees. E.g.,

  str->String.

Java claims Byte while Clojure claims byte, so trlisp uses Bite to denote eight binary digits.

Recommendations

First, work out the examples with a pencil and paper, and only then check  their evaluations in trlisp. Letting the computer do all the work stymies a  deeper understanding we might get by slinging around tree nodes by hand.

The unit testing namespace (and its auxiliary) contain working examples of every trlisp function.

Finally, the tree calculus book is the authoritative and complete reference on the subject. This ReadMe is merely a description of how to use trlisp to evaluate tree calculus  expressions. Use it as a companion to the Tree Calculus Book.

Fundamental combinators

Tree calculus functions and values could be defined purely in terms of Δ, but some judicious naming helps make programming in trlisp more ergonomic.  Let's define a small number of fundamental functions, and along the way, we will see the  application rules in action.

K combinator

We'll start with the simplest function, the K combinator: simple in what it does, simple in structure, and simple in its  application.

The K combinator always returns the first of its two arguments.

(K Δ (Δ Δ Δ)) ;; => Δ

Given trees Δ and (Δ Δ Δ), K returns Δ, the first argument, and discards the second argument. Here, we are using  concrete trees to demonstrate the behavior, but K works the same on any pair of trees.

We've already seen in our discussion of the tree calculus application  rules that Rule 3 declares that a fork-leaf always returns the first of a pair of arguments.  So we know that we can create a K combinator by adopting that fork-leaf  pattern.

Putting an expression that evaluates to a fork-leaf (Δ Δ) in the function position and applying it to two arguments, dispatches on  application Rule 3, and returns the first argument.

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

(Δ Δ) evaluates to K, so this expression returns the exact same Δ as before.

We've demonstrated that once we've composed a tree that triggers a  particular tree calculus application rule, we can use that tree to get a  wanted behavior.

In fact, trlisp's actual definition shows us that K is simply defined as (Δ Δ). Now that the symbol K is bound to a tree that creates a fork-leaf tree when given two arguments, we  can easily re-use the semantic idea of Take the first argument, discard the second argument in any future expression.

D combinator

A step up in complexity is the D combinator. Applied to three arguments, it does this.

(D x y z) = ((y z) (x z))

This operation is useful when we want to replicate an element and/or when  we want to swap the order of two items.

We define D like so.

(Def D (Δ (Δ Δ) (Δ Δ Δ)))

We can visualize D like this.

  Δ
 / \
Δ   (K Δ)
|
Δ

To see D in action, we'll assign x, y, and z to concrete trees, any of which may occupy the function position.

(def x (K Δ))
(def y (K Δ))
(def z K)

These are merely small trees with no particular semantics. We use them  only because it's straightforward to apply them by hand.

Let's evaluate the sub-components.

(y z) ;; => Δ

because (K Δ K) yields Δ due to application of the K combinator.

The second sub-component is identical to the first.

(x z) ;; => Δ

Now let's evaluate the value of (y z) applied to the value of (x z).

(Δ Δ) ;; => K

Let's check that against evaluating the entire expression.

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

Finally, let's invoke trlisp's definition of D with x, y, and z as arguments.

(D x y z) ;; => K

Notice that, as with the K combinator, the D combinator is a tree  deliberately composed to invoke a particular application rule, in this  instance, Rule 4 for fork-stems. After a couple rounds of application, we  obtain the following picture.

  Δ
 / \
Δ   y  ␣  z
|
x

Rule 4 immediately declares this to evaluate to

((y z) (x z))

which is the D combinator's essence.

If we work out that sequence of evaluations by hand, we notice that D  applied to the first argument x always eventually evaluates to

(Δ (Δ x))

which looks like this.

Δ
|
Δ
|
x

It's convenient to short-cut those steps, so we designate a function d such that

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

which is the same result produced by the D combinator.

S combinator

The D combinator, in addition to broadcasting the third argument, also  swaps the order of the first two arguments. It just so happens that there is  a combinator that broadcasts the third argument to the first two arguments  while maintaining the order.

The S combinator works like this

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

and can be defined in terms of d, D, and K.

We can test the definition by evaluating with arguments x, y, and z from the previous subsection.

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

The definition for S checks out.

It may be a little surprising to learn that the S combinator plays almost  no role in any upcoming definition. It's main utility is that with only S and K in hand, we know that tree calculus is S‑K complete, and therefore can compute any function whatsoever.

I combinator

Another crucial combinator is the I combinator, which returns exactly its single argument.

(I x) ;; => x

The I combinator could be defined in terms of S and K, but such a definition is extensionally equivalent to trlisp's simpler definition,

(Δ K K)

which we can visualize like this.

  Δ
 / \
Δ   Δ
|   |
Δ   Δ

Note that the tree structure of I combinator is designed to invoke  Rule 4, applying fork-stems, then immediately thereafter applies  Rule 3, for fork-leaves to discard the second expression, returning  exactly the argument. The structure encodes the behavior.

The I combinator appears in many upcoming definitions, including a key  role in defining Boolean entities.

Y combinator

trlisp supports recursion via the fixpoint combinator, or Y combinator, used in many of the upcoming definitions. Y is awkward to use directly,  but know that it exists and is available.

Other combinators

For completeness, trlisp also provides the B, C, and W combinators, but does not use them for any further purposes.

It turns out that we wouldn't often directly use any of these combinators  in day-to-day programming, but they are critical building blocks for the functions we do use.

Base functions

In contrast to the fundamental combinators, these functions might be useful for solving day-to-day problems. We should  continually keep in mind that these functions are defined (almost) solely in terms of Δ, or other trees themselves defined with Δ, a key characteristic of tree calculus.

Booleans

The two Boolean values behave like Church Booleans, with True returning the first of two arguments, and False returning the second of two arguments.

(True x y) ;; => x
(False x y) ;; => y

In addition to Not, trlisp provides the usual suspects: And, Or, Implies, and Iff. Here's just a sampling.

(And True (Not True)) ;; => False
(Or True False) ;; => True
(Iff False False) ;; => True
(Implies True False) ;; => False

See the testing namespace for the complete truth tables.

Arithmetic

Similar to Church encoding, tree calculus represents natural numbers as  repeated application of K such that number n is represented by KⁿΔ. Let's formulate the first few numbers and visualize them.

Δ

  Δ

(K Δ)

  Δ
 / \
Δ   Δ

(K (K Δ))

  Δ
 / \
Δ   Δ
   / \
  Δ   Δ

(K (K (K Δ)))

  Δ
 / \
Δ   Δ
   / \
  Δ   Δ
     / \
    Δ   Δ

It's obnoxious to have to bash those out on the keyboard, so the utility namespace provides a pair of functions to interconvert integers and trees.

(nat->tree 2) ;; => [[] [[] []]]

(tree->nat (K (K Δ))) ;; => 2

All the following functions require us to supply the arguments as trees,  not plain integers, so we'll often be relying on nat->tree and tree->nat. Here's why.

trlisp provides the classic increment and decrement functions. Let's calculate what arrives after integer One.

(Successor [[] []]) ;; => [[] [[] []]]

That's…not excellent. The argument and return value are a pile of  brackets.

Let's insert the nat->tree and tree->nat utilities to convert the argument and return value trees back to plain  integers.

Clojure provides a handy threading macro so we don't have to read the  expression from the inside out.

(-> 2
    nat->tree
    Successor
    tree->nat) ;; => 3

That's a tad better.

We feed plain integer 2 into nat->tree, which converts it into the tree representation [[] [[] []]]. Then, we feed that tree into Successor, which does its calculation, returning yet another tree. Finally, we feed  that tree into tree->nat, which hands us an understandable integer 3, which, since we paid attention in school, we have good reason to believe is  the correct answer.

trlisp also provides the companion function, Predecessor.

(-> 5
    nat->tree
    Predecessor
    tree->nat) ;; => 4

trlisp provides functions for addition, subtraction, multiplication, and  division.

Let's demonstrate addition by first binding trees to Two and Three.

(def Two (nat->tree 2))
(def Three (nat->tree 3))

Then we evaluate the addition expression, feeding the result into tree->nat to convert the tree into a readable integer.

(-> (Plus Two Three)
    tree->nat) ;; => 5

Yup. Adding two to three results in five.

Beware: the Divide function is doubly-recursive, and performs poorly.

Lists and tuples

trlisp implements 2-tuples with Pair and provides accessor functions First and Second.

(Pair Two Three) ;; => [[[] [[] []]] [[] [[] [[] []]]]]

(-> (Second (Pair Two Three))
    tree->nat) ;; => 3

Tree calculus lists are serial forks with the values v_n in the left branches.

  Δ
 / \
v0  Δ
   / \
  v1  Δ
     / \
    v2  Δ
       / \
      …   …

trlisp provides List to quickly construct a list from its arguments.

Bite constructs an 8-tuple of bits, while String constructs strings from Bites representing the characters' ascii byte encodings.

Append to trlisp lists with Append and reverse a trlisp list with Reverse.

Mapping and folding

Tree calculus defines functions for operating on elements of a list.  trlisp implements a mapping function that applies a function to every element of a list a returns  a new list with updated values.

Let's construct a list of integers.

(def Our-List (List (nat->tree 2) (nat->tree 3) (nat->tree 4)))

Pretend we'd like to have a new list containing each of those integers  incremented by one. The Successor function makes a solid choice for incrementing.

The function signature for mapping is

(Map function list)

Our expression will look like this.

(Map Successor Our-List)

Map returns a tree, which is difficult to decipher. So we'll use List->seq to convert the tree calculus list into a Clojure sequence of tree integers,  and then Clojure's map with tree->nat to convert each tree integer into a plain integer.

(->> (Map Successor Our-List)
     List->seq
     (map tree->nat)) ;; => (3 4 5)

Excellent. Map incremented three integers contained in our list.

trlisp also implements tree calculus' folding operations. The function signature for left-folding is

(Fold-Left function init list)

Let's compose those arguments. We'll use Plus since it's easy to eyeball it's effects. We'll assign a tree to an initial  value.

(def Our-Init (nat->tree 1))

We'll use the same list of integers from earlier, Our-List.

Now, we invoke the fold, and convert the result to an integer we can  recognize.

(-> (Fold-Left Plus Our-Init Our-List)
    tree->nat) ;; => 10

Fold-Left adds one to two, then that result to three, then that result to four,  yielding ten.

Fold-Right works analogously.

Tagging

Tree calculus defines a system for tagging values, removing tags,  reading the tags, retrieving the values, and for applying tagged functions  to tagged values.

Based on those tagging utilities, tree calculus defines a simple type  system that tags a tree with a type, which can later be checked during  application.

trlisp implements the both the tagging and type-check systems, but they're  not user-friendly, nor comprehensive, so we won't discuss them further. See  the testing namespace for basic usage.

Tree analysis

Tree calculus' tentpole feature is the ability of one function to inspect  another function directly, without quoting. This feature, reflection, is enabled by the fact that all entities, functions and values, are  composed of the same stuff: trees.

trlisp implements several functions in this category, such as measuring  the size of a function, determining the equality of two functions, and running  generic queries on the branching structure.

For example, we can use the Size function to measure the size of the K combinator.

(-> (Size K)
    tree->nat) ;; => 2

Yes, the K combinator is composed of two nodes as we expect. And we didn't  need to operate on some quoted expression preceding a compilation step. Size operated directory on K's defined value.

We could also ask if two functions are equal. Let's see if the K  combinator is equal to one leaf node descendant from another node.

(Equal? K (Δ Δ)) ;; => True

Yes, the two trees are equal as we expect. Equal? dived straight into the internal structures of K and (Δ Δ) to do its job.

Tree calculus' triage defines a basic system for testing for leaves, stems, or forks. With triage  in hand, tree calculus goes on to define pattern matching. As I understand it, pattern-matching answers the following question.

Given tree A,

  Δ
 / \
Δ   foo

and some target component of A,

foo

and test tree B,

  Δ
 / \
Δ   baz

What is the thing located in tree B at the same location as foo in tree A? The answer is baz.

trlisp implements both triage and pattern matching, and they pass some rudimentary unit tests, but I am not confident the tests are correct nor sufficient.

At any rate, we should be impressed with the fact that all these functions, sophisticated as they  are, are defined in terms of the basic node operator.

Self evaluators

Tree calculus demonstrates its ability for programs to act on themselves  by defining four self-evaluators. trlisp implements all four: Branch-first, Root, Root-and-branch, and Root-first evaluate their arguments with different strategies for inspecting the  interior structure of their arguments.

See the testing namespace for example usage.

Comments

Two of tree calculus' ideas caught my attention.

1. One operator plus six application rules

   Tree calculus' minimalism hints that it could be implemented in  constrained environments. Almost certainly a 6502 microprocessor, probably on a  punch card machine, but maybe even a marble machine by someone really clever.

   Tree calculus is so concise, we can evaluate the expressions by hand. I  wrote trlisp so that I could evaluate tree calculus expressions to check my pencil and paper work, and to feel what it's like to program with. In  that regard, trlisp provides that. While working through the book's examples,  trlisp can quickly validate an expression that takes multiple sheets of paper.

   On the other hand, it is immediately apparent that trlisp is in no way a  practical, general-purpose programming language. The inputs and return values  are trees, not plainly understandable integers and strings, and bugs are  tedious to track down. trlisp kinda grafts tree calculus' evaluation model onto  an existing language. What advantages could an entirely new programming  language based on tree calculus offer?

   Instead of adding tree calculus itself to another programming language,  adapting some of tree calculus' features to an existing programming language could be beneficial.

2. Decomposable functions

   Check this out.

   (Second D) ;; => (K Δ)

   We just reached into the D combinator, a function-like thing, and pulled  out its second element, i.e., the right child. We didn't resort to quoting or a  macro. The tree that implements the D combinator is, at any moment, available  for inspection. There is no separate notion of a function's definition that is  distinct from the thing that executes the task.

   Having such reflective functions, i.e., direct access to a function's  definition, suggests some interesting possibilities. Being able to inspect,  analyze, optimize, modify, and borrow pieces from a function could enable tasks  that are not currently easy, or even possible. In recent memory, I have at  least one utility that would have been faster and more elegant to write if I had run-time  (not compile-time) access to the function's definition.

   Could it be generally useful to be able to define a new function by  modifying an existing one?

   ;; pseudo-code
   (def my-new-fn (assoc old-fn ...))

   When we speak of 'first-class functions', we generally mean that functions may be passed as values and returned from other functions. But what if we could dive into a function and do something useful with its contents? Wouldn't reflective functions truly be 'first-class'?

   We probably wouldn't use it often, but it could be a nice tool in the toolbox. Something akin to writing a Lisp macro when a regular function won't suffice. I can more easily imagine how this particular tree calculus feature might be added to an existing language.

References

Tree calculus references

• Barry Jay's Reflective Programs in Tree Calculus (pdf, 2021)

  trlisp's primary reference. See also the other materials in Jay's GitHub page, particularly the Coq proofs.

• Johannes Bader's Tree Calculus page

  Tree calculus advocacy, examples, and interactive demos. Note: The application rules are different than here, but the systems are equivalent. Bader also wrote a nice introduction blog post.

• Timur Latypoff's Tree calculus, visualized

• James Eversole's tricu

  Tree calculus implemented in Haskell.

Other references

• Palmer, Filardo, & Wu Intensional functions (pdf, 2024)

  Discusses how intensional functions offer non-application operations, such as comparison, serialization, hashing, etc.

Glossary

apply

Consume two trees, yielding a single tree according to the tree calculus rules. In trlisp, we apply by evaluating a list with a function (a tree) at the head and an argument (also a tree) at its tail.

An instance of applying one tree to another is an application. trlisp provides six distinct applications, selected by the branching pattern of the tree in the function position.

argument

A tree appearing in the tail of a list to be evaluated. The argument is consumed in the course of applying the function.

Note: All trees may serve as an argument, even trees that are semantically functions, such as Inc. In other words, trees are first-class functions and may be passed as values and manipulated.

define

Bind a name (a Clojure symbol) to tree. That name evaluates to the original tree wherever it appears in an expression.

fork

A node with exactly two children.

function

A tree appearing at the head of a list to be evaluated. The function's branching pattern determines which application rule to invoke.

Note: All trees are potentially functions, i.e., any tree may competently invoke one of the applications.

leaf

A node with exactly zero children.

node

The basic unit of an unlabelled, binary tree. May be either a leaf, stem, or fork.

stem

A node with exactly one child.

tree

An arrangement of only leafs, stems, and forks.

License

This program and the accompanying materials are made available under the terms of the MIT License.

Copyright © 2024–2025 Brad Losavio.
Compiled by ReadMoi on 2025 July 12.
24d7622e-9828-4fe1-831b-4a4314e293e0