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

shuffle

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!
fotreeleft
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.
fotreeright
______________________________________________________________
Advertisements

One thought on “The illustrated shuffle trick, used for tree duplication”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s