Tag Archives: shuffle trick

Small graph rewrite systems (I)

What happens if we use the sticks and rings description of  oriented fatgraphs, like in this post, but we drop the orientation? Moreover, what if we use as few colors as  possible and as few rewrites as possible?

For the sticks and rings version of chemlambda see this.

If we have oriented edges then the sticks and rings  image is equivalent with the usual oriented trivalent fatgraph. But if we drop the edges orientation something interesting happens. The trivalent nodes become invertible. Indeed, take for example, with the notations from chemlambda, a node as seen in a mol file:

A 1 2 3

It means that we have a node “A” (i.e. application)   with a left.in port named “1”, a right.in port named “2” and a out port named “3”. To get a more precise idea, think about “1” as a term “T_1”, about “2” as a term “T_2” and about “3” as the term “T_1 T_2”.

In the sticks and rings version there is an edge which connects “1” and “3”, which is perhaps part  of a stick (which has two ends) or a ring (which has none). “1” and “3” appear as marks on that stick (or ring) and the stick (or ring) has an orientation so that the successor of “1” is “3”.

Another stick, which ends with the mark “2” and the node “A”, is glued between the marks “1” and “2”.

For a node like

FO 1 2 3

(i.e. a fanout) the oriented stick passes from “1” to “3” but this time the second stick starts with the node “FO” and the mark “2”.

Now, if we drop the sticks orientations, it means that we can no longer discern between say “A 1 2 3” and “A 3 2 1”. As an expression which depends on the port “2”,  we can go from “1” to “3” as easily as we go from “3” to “1”, so it  looks invertible.

As a first try let’s see how does a non-oriented sticks and rings version of Lafont interaction combinators look like. We need only two colors, to discern between the \gamma and \delta combinators. We shall not use the combinators with only one port.

The IC-2.1 system

The \gamma \delta  rewrite will be like a DIST rewrite from chemlambda, only unoriented.



Then, the \gamma \gamma looks like this


and finally the \delta \delta may be seen like this


As you see all rewrites are made conservative in the number of nodes, by the addition of supplementary 2-nodes sticks, call them “pairs” from now.


Now we have some problems:

  • the RHS of the DIST rewrite contains the pattern from the LHS  if we add another pair yellow-blue. That is bad because it means we can continue indefinitely the same rewrite if we have enough yellow-blue pairs  at our  disposal
  • practically almost any sticks and rings graph is extremely reactive, because any combination of nodes colors which are neighbours on a stick or ring will trigger a rewrite. Question: which are the graphs which are fully reduced?
  • if we look back to Lafont interaction combinators, then we see that our system has more rewrites than the original. Indeed, that is because the non-oriented sticks and rings image is ambiguous, not equivalent with the interaction combinators. This explains the abundance of patterns for reduction.


The SH-2.1 system

Let’s try another rewrite system, non-oriented sticks and rings and two colors. We’ll take the shuffle trick rewrite as basic, this time:


Then we add a “glue” rewrite


and a “remove” rewrite



Now we are in the realm of emergent algebras, with the yellow node as a generic dilation and the blue node as a fanout (more about this later). We can do lots of funny things with this small system, for example we can do a DIST:





There is a remarkable behaviour here. Look at the pair blue-blue, you have it at the left of the “simulated” DIST and at the right of it.

The pair blue-blue behaves like an enzyme!

[Continues with this post.]

The illustrated shuffle trick, used for tree duplication

 Duplication of trees of fanouts is done in chemlambda by the shuffle trick.
The actors are the nodes FO (fanout), FOE (the other fanout) and FI (fanin). They are related by the rewrites FI-FOE (which resembles to the beta rewrite, but is a bit different), FO-FOE (which is a distributivity rewrite of the FO node wrt to the FOE node) and FI-FO (which is a distributivity rewrite of the FI node wrt the FO node.
In the shuffle trick there are used the rewrites FO-FOE and FI-FOE.
Properly speaking there is no trick at all, in the sense that it is unstaged. It happens when there is a FO-FOE pattern for a rewrite, which in turn, after application, creates a FI-FOE pattern.
The effects are several:
  • FO nodes migrate from the root to the leaves
  • FOE nodes migrate from the leaves to the root
  • and there is a shuffle of the leaves which untangles correctly the copies of the tree.

All this is achieved not by setting as goal the duplication! As I wrote, there is no scenario behind, it is just an emergent effect of local rewrites.

Here is the shuffle trick illustrated


For explanatory reasons the free out ports (i.e the FROUT nodes) are coloured with red and blue.

Watch carefully to see the 3 effects of the shuffle trick!
Before: there are two pairs of free out ports, each pair made of a blue and a red out ports. After the shuffle trick there is a pair of blue ports and a pair of red ports.

Before: there is a green node (FO fanout) and two pale yellow nodes (FOE fanouts).
After: there is one pale yellow node instead (FOE fanout) and two green nodes (FO fanouts)

OK, let’s see how this trick induces the duplication of a tree made of FO nodes.
First, we have to add a FI node at the root and FOE nodes at the leaves. In the following illustrations I coloured the free in ports (of the FI node) and the free out ports (of the FROUT nodes) with red and blue, for explanatory purposes.
There are two extremal cases of a tree duplication.
The first is the duplication of a tree made of FO nodes, such that all right ports are leaves (thus the tree extends only in the left direction).
In this case the shuffle trick is applied (unstaged!) all over the tree at once!
In the opposite extremal case we want to duplicate a tree made of FO nodes, such that all LEFT ports are leaves (thus the tree extends only in the RIGHT direction).
In this case the shuffle trick propagates towards the root.