# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Generate a graph of branch pair ancestry for a combinator evaluation "glocal" (hybrid of global and local) multiway system

Contributed by:
Jonathan Gorard

ResourceFunction["CombinatorGlocalBranchialGraph"][ generates the graph of branch pair ancestry after | |

ResourceFunction["CombinatorGlocalBranchialGraph"][ uses the function |

Glocal multiway systems combine the global events (and the corresponding causal structure) of ordinary multiway systems, with the individual token philosophy of local multiway systems. A single event vertex in the evolution causal graph (or token event graph) will, in general, have many incoming and outgoing evolution edges, corresponding to the fact that several tokens must be assembled together in order to reconstruct a single global input or output state for the event.

The branchial graph for a glocal multiway system shows the branch pair (i.e. critical pair) ancestry for a glocal evolution causal graph/token event graph. Unlike the branchial graph for an ordinary (global) multiway system, which only contains information regarding the evolution ancestry of states, glocal branchial graphs contain information about both the causal ancestry of events and the evolution ancestry of states/tokens.

Argument and option patterns for ResourceFunction["CombinatorGlocalBranchialGraph"] match those of the resource function MultiwayCombinator (and, to a lesser extent, the resource function MultiwaySystem).

Rule and state specifications for ResourceFunction["CombinatorGlocalBranchialGraph"] are rules and expressions of some combinatory calculus.

ResourceFunction["CombinatorGlocalBranchialGraph"] accepts both individual rules of combinatory calculus and lists of rules, and likewise for initial conditions. ResourceFunction["CombinatorGlocalBranchialGraph"][*rules*,*init*,*n*] is interpreted as ResourceFunction["CombinatorGlocalBranchialGraph"][*rules*,{*init*},*n*], etc.

The event selection function *sel* in ResourceFunction["CombinatorGlocalBranchialGraph"][*rules*→*sel*,…] can have the following special forms:

"Sequential" | applies the first possible replacement (sequential substitution system) |

"Random" | applies a random replacement |

{"Random",n} | applies n randomly chosen replacements |

Duplicated tokens are displayed separately at each time step by default, although this can be overridden by setting "DeduplicateTokens"→True.

Events are represented in the form {*rule*,*input*,*rest*}, where *rule* is the rule used in the updating event, *input* is the part of the state to which the rule is applied and *rest* is the remainder of the state. For substitution systems, *rest* is given in the form {*prefix*,*suffix*}.

Options for ResourceFunction["CombinatorGlocalBranchialGraph"] include:

"DeduplicateTokens" | False | whether to merge all instances of equivalent tokens that appear at each time step |

"VertexRendering" | True | whether to use special rendering for state/token and event vertices |

"StateRenderingFunction" | Automatic | how to label states/tokens that appear in the evolution causal graph/token event graph |

"EventRenderingFunction" | Automatic | how to label events that appear in the evolution causal graph/token event graph |

All of the standard options for the Graph function can also be applied to ResourceFunction["CombinatorGlocalBranchialGraph"].

Possible settings for "StateRenderingFunction" and "EventRenderingFunction" include:

Automatic | make a label from the name of the vertex |

Inherited | use the explicit vertex name as the label |

None | use no label for the vertex |

"string" | use a shape from the VertexShapeFunction collection |

func | apply the function func to the name of the vertex |

Generate glocal branchial graphs for two simple multiway combinator evaluations for the fixed-point combinator (i.e. the y-combinator):

In[1]:= |

Out[1]= |

In[2]:= |

Out[2]= |

Show just the structure of the graphs, without labels:

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]= |

Generate a glocal branchial graph for a more complicated multiway evaluation for the S-K calculus:

In[5]:= |

Out[5]= |

Show just the structure of the graph, without labels:

In[6]:= |

Out[6]= |

Merge all instances of equivalent tokens that appear at each time step:

In[7]:= |

Out[7]= |

Run the system for more steps:

In[8]:= |

Out[8]= |

Show just the structure of the graphs, without labels:

In[9]:= |

Out[9]= |

In[10]:= |

Out[10]= |

Specify an event selection function that picks only up to two events at each step:

In[11]:= |

Out[11]= |

CombinatorGlocalBranchialGraph supports all forms of combinatory calculi, including the single-variable fixed-point (y) combinator:

In[12]:= |

Out[12]= |

The two-variable fixed-point (y) combinator:

In[13]:= |

Out[13]= |

The S-K calculus:

In[14]:= |

Out[14]= |

The S-K-I calculus:

In[15]:= |

Out[15]= |

Schönfinkel's B and C combinators:

In[16]:= |

Out[16]= |

Due to the undecidability of the S-K-I combinatory calculus, the following evaluation does not terminate at a normal form:

In[17]:= |

Out[17]= |

CombinatorGlocalBranchialGraph accepts both individual combinator rules and lists of combinator rules:

In[18]:= |

Out[18]= |

In[19]:= |

Out[19]= |

CombinatorGlocalBranchialGraph accepts both individual initial conditions and lists of initial conditions:

In[20]:= |

Out[20]= |

In[21]:= |

Out[21]= |

Apply only the first possible event at each step:

In[22]:= |

Out[22]= |

Apply the first and last possible events at each step:

In[23]:= |

Out[23]= |

Compare this to the full branchial graph for the unrestricted glocal multiway evaluation:

In[24]:= |

Out[24]= |

By default, equivalent tokens remain unmerged at each time step:

In[25]:= |

Out[25]= |

Merging of equivalent tokens at each time step can be enforced using the option "DeduplicateTokens":

In[26]:= |

Out[26]= |

By default, state/token vertices and event vertices use special rendering (inherited from the MultiwayCombinator resource function):

In[27]:= |

Out[27]= |

This rendering can be disabled using the option "VertexRendering":

In[28]:= |

Out[28]= |

By default, states/tokens are labeled by their contents:

In[29]:= |

Out[29]= |

Use no labeling for states/tokens:

In[30]:= |

Out[30]= |

Use raw state/token names as vertex labels:

In[31]:= |

Out[31]= |

Use a named shape as each state/token label:

In[32]:= |

Out[32]= |

By default, both states/tokens and events are labeled by their contents:

In[33]:= |

Out[33]= |

Use no labeling for states/tokens:

In[34]:= |

Out[34]= |

Also use no labeling for events:

In[35]:= |

Out[35]= |

Disabling vertex rendering yields an equivalent result:

In[36]:= |

Out[36]= |

Use raw event expressions as their labels:

In[37]:= |

Out[37]= |

Generate an example glocal branchial graph for a multiway combinator evaluation:

In[38]:= |

Out[38]= |

Force a spring embedding (as opposed to the default spring electrical embedding):

In[39]:= |

Out[39]= |

- The Wolfram Physics Project
- Stephen Wolfram's A New Kind of Science | Online
- Multiway System–Wolfram MathWorld

- 1.0.0 – 03 January 2022

This work is licensed under a Creative Commons Attribution 4.0 International License