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 patterns and tokens.

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:

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]

Instead of the LEFT pattern from chemlambda v2, we have a pattern

{named:”A-L”,

edge:”a”,

mol:[[“L”, “c”, “b”, “a”],

[“A”, “a”, “d”, “e”]]

}

and a token

{named:”Arrow-Arrow”,

edge:”a”,

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 black:

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”

{named:”Arrow”,

edge:”a”,

mol:[[“Arrow”, “a”, “b”]]

}

and a token “L-A”

{named:”L-A”,

edge:”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.

In order to apply the permutations pisource and pitarget correctly, we need to be sure about how the pattern recognition algorithm 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].

## References:

[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?

[This is a slightly edited part of the source: chemlambda and hapax.]