# 9.2 Appendix: Implementation

### Tools Created for This Project

A variety of new functions have been added to the Wolfram Function Repository to directly implement, visualize and analyze the models defined here .

### Basic Direct Symbolic Transformation

The class of models defined here can be implemented very directly just using symbolic transformation rules of the kind on which the Wolfram Language  is based.

It is convenient to represent relations as Wolfram Language lists, such as {1,2}. One way to represent collections is to introduce a symbolic operator σ that is defined to be flat (associative) and orderless (commutative):

SetAttributes[\[Sigma], {Flat, Orderless}]

Thus we have, for example:

\[Sigma][\[Sigma][a, b], \[Sigma][c]]

We can then write a rule such as

{{x, y}} -> {{x, y}, {y, z}}

more explicitly as:

\[Sigma][{x_, y_}] :> Module[{z}, \[Sigma][{x, y}, {y, z}]]

This rule can then be applied using standard Wolfram Language pattern matching:

\[Sigma][{a, b}] /. \[Sigma][{x_, y_}] :> Module[{z}, \[Sigma][{x, y}, {y, z}]]

The Module causes a globally unique new symbol to be created for the new node z every time it is used:

\[Sigma][{a, b}] /. \[Sigma][{x_, y_}] :> Module[{z}, \[Sigma][{x, y}, {y, z}]]

But in applying the rule to a collection with more than one relation, there is immediately an issue with the updating process. By default, the Wolfram Language performs only a single update in each collection:

\[Sigma][{a, b}, {c, d}] /. \[Sigma][{x_, y_}] :> Module[{z}, \[Sigma][{x, y}, {y, z}]]

As discussed in the main text, there are many possible updating orders one can use. A convenient way to get a whole “generation” of update events is to define an inert form of collection σ1 then repeatedly replace collections σ until a fixed point is reached:

\[Sigma][{a, b}, {c, d}] //. \[Sigma][{x_, y_}] :> Module[{z}, \[Sigma]1[{x, y}, {y, z}]]

By replacing σ1 with σ at the end, one gets the result for a complete generation update:

\[Sigma][{a, b}, {c, d}] //. \[Sigma][{x_, y_}] :> Module[{z}, \[Sigma]1[{x, y}, {y, z}]] /. \[Sigma]1 -> \[Sigma]

NestList applies this whole process repeatedly, here for 4 steps:

evol = NestList[# //. \[Sigma][{x_, y_}] :> Module[{z}, \[Sigma]1[{x, y}, {y, z}]] /. \[Sigma]1 -> \[Sigma] &, \[Sigma][{1, 1}], 4]

Replacing σ by a Graph operator, one can render the results as graphs:

evol /. \[Sigma] -> (Graph[DirectedEdge @@@ {##}] &)

IndexGraph creates a graph in which nodes are renamed sequentially:

evol /. \[Sigma] -> (IndexGraph[DirectedEdge @@@ {##}, VertexLabels -> Automatic] &)

Here is the result with a different graph layout:

evol /. \[Sigma] -> (IndexGraph[DirectedEdge @@@ {##}, GraphLayout -> "SpringElectricalEmbedding"] &)

Exactly the same approach works for rules that involve multiple relations. For example, consider the rule:

{{x, y}, {x, z}} -> {{x, z}, {x, w}, {y, w}, {z, w}}

This can be run for 2 steps using:

NestList[# //. \[Sigma][{x_, y_}, {x_, z_}] :> Module[{w}, \[Sigma]1[{x, z}, {x, w}, {y, w}, {z, w}]] /. \[Sigma]1 -> \[Sigma] &, \[Sigma][{1, 1}, {1, 1}], 2]

Here is the result after 10 steps, rendered as a graph:

Nest[# //. \[Sigma][{x_, y_}, {x_, z_}] :> Module[{w}, \[Sigma]1[{x, z}, {x, w}, {y, w}, {z, w}]] /. \[Sigma]1 -> \[Sigma] &, \[Sigma][{1, 1}, {1, 1}], 10] /. \[Sigma] -> (Graph[DirectedEdge @@@ {##}] &)

### Alternative Syntactic Representation

As an alternative to introducing an explicit head such as σ, one can use a system-defined matchfix operator such as AngleBracket (entered as <, >) that does not have a built-in meaning. With the definition

SetAttributes[AngleBracket, {Flat, Orderless}]

one immediately has for example

\[LeftAngleBracket]a, \[LeftAngleBracket]b, c\[RightAngleBracket]\[RightAngleBracket]

and one can set up rules such as

\[LeftAngleBracket]{x_, y_}, {x_, z_}\[RightAngleBracket] :> Module[{w}, \[LeftAngleBracket]{x, z}, {x, w}, {y, w}, {z, w}\[RightAngleBracket]]

### Pattern Sequences

Instead of having an explicit “collection operator” that is defined to be flat and orderless, one can just use lists to represent collections, but then apply rules that are defined using OrderlessPatternSequence:

{{0, 0}, {0, 0}, {0, 0}} /. {OrderlessPatternSequence[{x_, y_}, {x_, z_}, rest___]} :> Module[{w}, {{x, z}, {x, w}, {y, w}, {z, w}, rest}]

Note that even though the pattern appears twice, /. applies the rule only once:

{{0, 0}, {0, 0}, {0, 0}, {0, 0}} /. {OrderlessPatternSequence[{x_, y_}, {x_, z_}, rest___]} :> Module[{w}, {{x, z}, {x, w}, {y, w}, {z, w}, rest}]

### Subset Replacement

Yet another alternative is to use the function SubsetReplace (built into the Wolfram Language as of Version 12.1). SubsetReplace replaces subsets of elements in a list, regardless of where they occur:

SubsetReplace[{a, b, b, a, c, a, d, b}, {a, b} -> x]

Unlike ReplaceAll (/.) it keeps scanning for possible replacements even after it has done one:

SubsetReplace[{a, a, a, a, a}, {a, a} -> x]

One can find out what replacements SubsetReplace would perform using SubsetCases:

SubsetCases[{a, b, c, d, e}, {_, _}]

This uses SubsetReplace to apply a rule for one of our models; note that the rule is applied twice to this state (Splice is used to make the sequence of lists be spliced into the collection):

SubsetReplace[{{0, 0}, {0, 0}, {0, 0}, {0, 0}}, {{x_, y_}, {x_, z_}} :> Splice[Module[{w}, {{x, z}, {x, w}, {y, w}, {z, w}}]]]

This gives the result of 10 applications of SubsetReplace:

Nest[SubsetReplace[{{x_, y_}, {x_, z_}} :> Splice[Module[{w}, {{x, z}, {x, w}, {y, w}, {z, w}}]]], {{1, 2}, {1, 3}}, 10] // Short

This turns each list in the collection into a directed edge, and renders the result as a graph:

Graph[DirectedEdge @@@ %]

IndexGraph can then for example be used to relabel all elements in the graph to be sequential integers.

Note that SubsetReplace does not typically apply rules in exactly our “standard updating order”.

### Parallelization

Our models do not intrinsically define updating order (see section 6), and thus allow for asynchronous implementation with immediate parallelization, subject only to the local partial ordering defined by the graph of causal relationships (or, equivalently, of data flows). However, as soon as a particular sequence of foliationsor a particular updating orderis defined, its implementation may require global coordination across the system.