Creative Commons License 
M. Buliga version: 21.06.2019

chemlambda and hapax

This page explains the following:

The mol notation

Is a very compact notation for the kind of graphs used in all these graph-rewriting formalisms. In order to understand the notation, we need first to define these graphs.


The most usual way to define a graph is the following:
The valence of a node is the number of times the node appears at an extremity of an edge. There is no particular order of the edges which have this node at one of the extremities. We think that the node connects with an edge via a node port. So, in this definition there is no particular order of the node ports of a node.

Also, remark that in this definition the extremities of an edge are given in no particular order. We say this is a graph with un-oriented or undirected edges.

These graphs don't have enough structure for our needs. That is why we shall add some structure:

The mol notation of a graph

The mol notation for such a graph is a list of nodes of the graph, where for each node we have a line (item) of the list. Each line represents a node, in the following format: ( "LS" means line separator and "FS" means "field separator")

[type of node] FS [list of ports]

The [type of node] is, in chemlambda "A", "L", "FI", "FO", "FOE", "Arrow", "FRIN", "FROUT", "T", in interaction combinators is "γ", "δ", "ε".

The [list of ports] is an array (a list) with FS as field separator, where the element "i" of the list is the name of the edge connected at the edge port "i".

Let's revisit the definitions we have until now, by adding to them a bit of details, in order to pass from the mathematical notation to a notation we can use with computers.

A graph is: The mol notation for such a graph is an array of node lines, where each line is in the mol format.

For example, in chemlambda we use the LS as "newline" and FS as " " and the mol notation

A a b c
L c b a

describes a graph which has 2 nodes and 3 edges. In JSON notation we would write:

graphMol = [["A", "a", "b", "c"],
["L", "c", "b", "a"]

In javascript we could define this as

graphMol = [{type:"A", ports:["a", "b", "c"]},
{type:"L", ports:["c", "b", "a"]}

This describes a graph with 2 nodes and 3 edges, where:
In the class of graphs that we use, this graph is different from the graph with the mol notation

A b a c
L c b a

because even if this second graph has also 2 nodes, of types "A" and "L", also 3 edges, named "a", "b", "c", there is a difference between the way edges are connected to ports. While for the first graph:
for the second graph we have:
therefore even if we rename the edges and even if we renumber the nodes, we can't transform a graph into the other.

Similarly, in interaction combinators the following mol notation

δ b a c
δ a b c

describes a graph with 2 nodes and 3 edges, etc.

As you see, the mol notation of such a graph does introduce a supplimentary structure, namely the ordering of the nodes of the graph. For the purposes of graph rewriting, this ordering is irrelevant. Otherwise we would not have a graph-rewriting formalism, we would have a term-rewriting formalism.

The mol notation abstractly

If we start from the mol notation of a graph, how can we know that there is a graph which has this as a mol notation?

There are two conditions:

However, we may work with mol files, which are mol notations for graph which may have free edges. In a mol file an edge name appears at most twice. Why? because this way a sub-array of a mol notation array is a mol file. This is important because when we shall discuss about graph rewrites, we shall need to define patterns, which are sets of nodes in a graph with certain properties. We shall denote patterns as mol files.

Also, we shall accept graphs which have some edge extremities "free", that is dangling without being connected to a node port. The mol notation for such a graph has the property that each edge name appears at most twice. All in all a mol file describes the graphs we need, as well as their subgraphs.

Oriented graphs, the first difference between chemlambda and interaction combinators

In chemlambda (and generally in hapax) we use graphs as previously, along with a supplimentary structure: the edges are oriented, that is
The "in" and "out" are with respect to the node: a target of an edge is an "in" of a node...

This supplimentary structure, which is not present in usual interaction combinators, forces us to modify the type of a node, namely, a node type specifies, as previously, the name of the type ("A", "L", "FI", etc.), the number of ports, but also the type "in" or "out" of each port.

For example, the nodes of type "A" and "FI" have 3 ports, with the types ["in", "in", "out"]. The nodes "L", "FO", FOE" have 3 ports, with the types ["in", "out", "out"]. In the hapax repository this is specified in the hapax-nodes.js.

In general, in hapax we shall strive to impose for 3-valent node types, the following: always the 1st port has type "in" and the 3rd port has type "out", while the middle port has either "in" or "out" type.

The second modification we have, due to the oriented edges, is that an admissible mol file for a graph with oriented edges has the supplimentary property:
That is why, for example, the list

δ b a c
γ a b c

is a valid mol file of an interaction combinator graph, but the list

A b a c
L a b c

is not a valid mol file for chemlambda, because the edge "c" appears twice in a port of type "out" and the edge "a" appears twice in a port of type "in".

In chemlambda (in general in hapax) there is an unique way to add nodes to an oriented graph which has some edges with free extremities. We simply define two new node types:
Then, if in a mol file the edge "e" appears only once, in a node port of type "in", it means that the edge has a free source, therefore we add a node


which becomes the source of the edge "e".

In the same way, if the edge "e" appears only once, in a node port of type "out", it means that the edge has a free target, therefore we add a node


which becomes the target of the edge "e".

(We could do the same in the un-oriented case, by using only one new node type, say "FREE" with only one port.)

Rewrites in chemlambda vs. rewrites in hapax

The rewrites of chemlambda are explained in [1], [2]. With the mol notiation we can equally describe the rewrites from interaction combinators, or those from other small graph rewrite systems.

First we explain the way we do rewrites in chemlambda v2 and interaction combinators. Then we explain how we do the chemlambda rewrites in hapax, because we do them in a different way.

Rewrites in chemlambda v2 and in interaction combinators, in mol notation

With the mol notation, each rewrite consists in the following:
Here is a chemlambda rewrite ("A-L" or "beta" rewrite):

LEFT = [["L", "a", "b", "c"], ["A", "c", "d", "e"]]   becomes   RIGHT = [["Arrow", "a", "e"], ["Arrow", "d", "b"]]

And here is an interaction combinators rewrite, where we add the node types "Arrow", as in chemlambda (and we'll have to add the COMB rewrites as well, but this is for later):

LEFT = [["γ", "a", "b", "c"], ["γ", "d", "e", "c"]]   becomes   RIGHT = [["Arrow", "a", "e"], ["Arrow", "b", "d"]]

In chemlambda and in interaction combinators the LEFT and RIGHT patterns, as mol files, have certain properties: There are some problems with this kind of rewrites: These problems are significant, especially if we want to use small graph rewrite systems as artificial chemistries, after all, even in an open system, a chemical reaction (which implements a graph rewrite) is conservative.

Chemlambda rewrites in hapax

In hapax we see a rewrite as a pair of permutations of the edges sources and targets. This way, any rewrite is conservative. Let's exemplify with the "A-L" rewrite from chemlambda.

In hapax the LEFT and RIGHT patterns are mol files of connected graphs, with a specified edge name. See hapax-mol.js for a list of paterns used in chemlambda, as done in hapax.

Any rewrite needs a pattern and a "token", and outputs a pattern. The tokens are small graphs (patterns). In hapax these are specified in hapax-chem.js. For example the "A-L" rewrite, as done in hapax, is:

{kind:"A-L", needs:"Arrow-Arrow", gives:["Arrow", "Arrow", "L-A"], pisource:[4,0,3,2,1], pitarget:[3,4,0,2,1]}

which means:

LEFT pattern "A-L" + token "Arrow-Arrow" becomes Pattern "Arrow" + Pattern "Arrow" + token "L-A"
by using the following permutations of sources and targets: pisource:[4,0,3,2,1], pitarget:[3,4,0,2,1]

Let's explain the same in mol notation. Instead of the LEFT pattern from chemlambda v2, we have a pattern

mol:[["L", "c", "b", "a"],
["A", "a", "d", "e"]]

and a token

mol:[["Arrow", "b", "a"],
["Arrow", "a", "b"]]

which corresponds (i.e. recognizes the pattern in the graph) to the mol file:

L c b a
A a d e
Arrow b' a'
Arrow a' b'

Now, according to the type "in" or "out" of the ports, we see that we have 5 sources, colored red, and five targets, colored yellow:

L c b a
A a d e
Arrow b' a'
Arrow a' b'

This is transformed into another pattern, by permuting the sources and the targets. We get:

L b' a b'
A a' a a'
Arrow c e
Arrow d b

which is, as the rewrite claims, recognized as two patterns "Arrow"

mol:[["Arrow", "a", "b"]]

and a token "L-A"

mol:[["A", "c", "a", "c"],
["L", "b", "a", "b"]]

The permutation of sources is described by the array pisources and the permutation of targets is described by the array pitarget. In order to understand how this is done, first recall that (in javascript in particular) arrays elements are numbered starting with 0, therefore the array pisource = [4,0,3,2,1], for example, represents a permutation in the sense that the element 0 goes to 4, 1 goes to 0, 2 goes to 3, etc.

Then, in order to apply the permutations pisource and pitarget correctly, we need to be sure in what order the pattern recognition function sees the sources and targets. The problem is that we could easily pick an order by hand of the sources and targets, but how does the program picks them? We need to know this only once, when we define the rewrites. For this we apply the pattern recognition program to the patterns themselves. (At some point in the future this has to be automatized). The page [9] tells us exactly this, namely that for the pattern recognition program the order of the sources for this rewrite is:

a, b, e, a', b'

and the order of the targets for this rewrite is:

a, c, d, a', b'

You can check by hand that pisource and pitarget permutation do indeed what they are expected to. For this see that, for example a which is source 0, appears in position 1 in pisource, therefore it will go in the place of source 1, which is b, and so on.

The hapax way of doing rewrites is more general and more flexible than the usual way. It can be applied to interaction combinators easily (one needs a way to add the sources-targets supplimentary information, in a way which respects the original formalism), but more interestingly, it can be applied to a variety of other graph rewrite systems which appear in science or mathematics. Even more, it can be used for random systems of graph rewrites, which are in vast numbers. This justifies the "hapax" name, which means "only once". See first descriptions of this idea in [10], [11].


[1] chemlambda moves
[2] chemlambda v2 page
[3] Y. Lafont, Interaction Combinators
[4] hapax repository
[5] small graph rewrite systems
[6] Molecular computers
[7] hapax-mol.js
[8] hapax-chem.js
[9] hapax-explore.html
[10] 14400 alternatives to the beta rewrite
[11] What is the purpose of the project hapax?