This post is part of the Tutorial: Graphic lambda calculus. It describes the set .
What is graphic lambda calculus?
Graphic lambda calculus is a formalism working with oriented, locally planar, trivalent graphs, with decorated nodes. It has a number of moves (transformations) acting on such graphs, which can be local or global moves.
It contains differential calculus in metric spaces, untyped lambda calculus and that part of knot theory which can be expressed by using knot diagrams.
The set GRAPH.
This is the set of graphs which are subjected to the moves. Any assembly of the following elementary graphs, called “gates” is a graph in .
- The gate, which corresponds to the lambda abstraction operation from lambda calculus, see lambda terms. It is this:
But wait! This gate looks like it has one input (the entry arrow) and two outputs (the left and right exit arrows respectively). This could not be a graph representing an operation, because an operation has two inputs and one output. For example, the lambda abstraction operation takes as inputs a variable name and a term and outputs the term .
Remember that the graphic lambda calculus does not have variable names. There is a certain algorithm which transforms a lambda term into a graph in , such that to any lambda abstraction which appears in the term corresponds a gate. The algorithm starts with the representation of the lambda abstraction operation as a node with two inputs and one output, namely as an elementary gate which looks like the gate, but the orientation of the left exit arrow is inverse than the one of the gate. At some point in the algorithm the orientation is reversed and we get gates as shown here. There is a reason for this, wait and see.
It is cool though that this gate looks like it takes a term as input and it outputs at the left exit arrow the variable name and at the right exit arrow the term . (It does not do this, properly, because there will be no variable names in the formalism, but it’s still cool.)
- The graph, which corresponds to the application operation from lambda calculus, see lambda terms. It is this:
This looks like the graph of an operation, there are no clever tricks involved. The sign I use is like a curly join sign.
- The graph, which will be used as a FAN-OUT gate, it is:
- The graph. For any element of an abelian group (think about as being or ) there is an “exploration gate”, or “dilation gate”, which looks like the graph of an operation:
(Therefore we have a family of operations, called “dilations”, indexed by the elements of an abelian group. This is a structure coming from emergent algebras.)
We use these elementary graphs for constructing the graphs in . Any assembly of these gates, in any number, which respects the orientation of arrows, is in .
Remark that we obtain trivalent graphs, with decorated nodes, each node having a cyclical order of his arrows (hence locally planar graphs).
There is a small thing to mention though: we may have arrows which input or output into nothing. Indeed, in particular the elementary graphs or gates are in and all the arrows of an elementary graph either input or output to nothing.
Technically, we may imagine that we complete a graph in , if necessary, with univalent nodes, called “leaves” (they may be be decorated with “INPUT” or “OUTPUT”, depending on the orientation of the arrow where they sit onto).
- For this reason we admit into arrows without nodes which are elementary graphs, called wires
and loops (without nodes from the elementary graphs, nor leaves)
- Finally, we introduce an univalent gate, the termination gate:
The termination gate has an input leaf and no output.
and now, any graph which is a reunion of lines, loops and assemblies of the elementary graphs (termination graph included) is in .