Wolfram Research

Function Repository Resource:

CombinatorEvolutionGraph

Source Notebook

Visualize the state transformations and causal structure of a combinator evolution

Contributed by: Wolfram Research

ResourceFunction["CombinatorEvolutionGraph"][cmb, t, prop]

displays the graph type specified by prop for a combinator expression cmb over t evolution steps.

Details and Options

The argument cmb should be given as a combinator expression in nested bracket form.
The argument t should be given as an integer number of time steps for the combinator evolution.
ResourceFunction["CombinatorEvolutionGraph"] supports the following properties for the prop argument:
"HaltedStatesGraph" displays the multiway states graph of cmb over t evolution steps, sizing nodes according to leaf count and highlighting nodes representing halted states
"PathHighlight" displays "HaltedStatesGraph" of cmb over t evolution steps, but also highlights one path in the graph according to the specified option value for "EvaluationScheme"
"CausalGraph" displays the causal structure of cmb over t evolution steps; takes the causal graph instance corresponding to the specified option value for "EvaluationScheme"
ResourceFunction["CombinatorEvolutionGraph"] accepts the same options as Graph, with the following additions:
"MinimalHaltedStatesGraph" False whether to include the leaf count as a vertex label in "HaltedStatesGraph"
"NodeSizeMultiplier" 0.75 scalar factor for the node size in "HaltedStatesGraph"
"PathThickness" 2.5 edge thickness for the highlighted path in "PathHighlight"
"CombinatorRules" Automatic combinator rules used to evolve cmb
"SKGlyphs" Automatic glyphs used for S and K combinators in cmb
"EvaluationScheme" {"Leftmost", "Outermost", 1} evaluation scheme used to evolve cmb
"RenderCausalEvents" False whether to display causal events as vertices of "CausalGraph"

Examples

Basic Examples (3) 

Show the states graph of a combinator evolution, with labeled vertices sized according to the leaf count of the state; terminal states indicated by a thick, dark border; and states that can be further evolved indicated by a thick, orange border:

In[1]:=
ResourceFunction["CombinatorEvolutionGraph"][
 CombinatorS[CombinatorS[CombinatorS[CombinatorS]]][CombinatorS][
   CombinatorS][CombinatorK], 9, "HaltedStatesGraph"]
Out[1]=

Highlight a path in the halted states graph of a combinator evolution according to the leftmost-outermost evaluation scheme; notice that other states attainable at the given time step are colored in a darker blue than the rest of the vertices:

In[2]:=
ResourceFunction["CombinatorEvolutionGraph"][
 CombinatorS[CombinatorS[CombinatorS[CombinatorS]]][CombinatorS][
   CombinatorS][CombinatorK], 9, "PathHighlight"]
Out[2]=

Show the causal structure of events in a combinator evolution according to the leftmost-outermost evaluation scheme:

In[3]:=
ResourceFunction["CombinatorEvolutionGraph"][
 CombinatorS[CombinatorS[CombinatorS[CombinatorS]]][CombinatorS][
   CombinatorS][CombinatorK], 9, "CausalGraph"]
Out[3]=

Options (5) 

CombinatorRules (1) 

Specify the rules used to evolve a combinator expression and show a halted states graph:

In[4]:=
ResourceFunction["CombinatorEvolutionGraph"][
 s[s[s[s]]][s][s][k], 9, "HaltedStatesGraph", "CombinatorRules" -> {s[x_][y_][z_] :>  x[z][y[z]]}]
Out[4]=

EvaluationScheme (1) 

Show the causal structure of events in a combinator evolution according to the single-match rightmost-innermost evaluation scheme:

In[5]:=
ResourceFunction["CombinatorEvolutionGraph"][
 CombinatorS[CombinatorS[CombinatorS[CombinatorS]]][CombinatorS][
   CombinatorS][CombinatorK], 9, "CausalGraph", "EvaluationScheme" -> {"Rightmost", "Innermost", 1}]
Out[5]=

MinimalHaltedStatesGraph (1) 

Highlight the state transformation path for a combinator expression evolved with a rightmost-innermost evaluation scheme, using options to omit vertex labels, make the nodes smaller and increase the thickness of edges along the path:

In[6]:=
ResourceFunction["CombinatorEvolutionGraph"][
 CombinatorS[CombinatorS[CombinatorS[CombinatorS]]][CombinatorS][
   CombinatorS][CombinatorK], 9, "PathHighlight", "MinimalHaltedStatesGraph" -> True, "NodeSizeMultiplier" -> 0.5, "PathThickness" -> 3, "EvaluationScheme" -> {"Rightmost", "Innermost", 1}]
Out[6]=

RenderCausalEvents (1) 

Show the causal structure of events in a combinator evolution according to the rightmost-innermost evaluation scheme, this time rendering vertices with the event information:

In[7]:=
ResourceFunction["CombinatorEvolutionGraph"][
 s[s[s[s]]][s][s][k], 9, "CausalGraph", "SKGlyphs" -> {s, k}, "EvaluationScheme" -> {"Rightmost", "Innermost", 1}, "RenderCausalEvents" -> True, AspectRatio -> 1/1.5]
Out[7]=

SKGlyphs (1) 

Specify the glyphs used for the S and K combinators in the argument cmb:

In[8]:=
ResourceFunction["CombinatorEvolutionGraph"][
 s[s[s[s]]][s][s][k], 9, "HaltedStatesGraph", "SKGlyphs" -> {s, k}]
Out[8]=

Resource History

Related Resources

License Information