Wolfram Research

Function Repository Resource:

CombinatorEvolutionPlot

Source Notebook

Visualize the evolution of a combinator expression

Contributed by: Wolfram Research

ResourceFunction["CombinatorEvolutionPlot"][evol, type]

renders the combinator evolution evol according to the specified type of visualization.

Details and Options

The combinator evolution evol is a list of combinator expressions generated by application of rules in a defined traversal scheme on an initial combinator condition. Use either the resource function CombinatorEvolveList or the resource function CombinatorFixedPointList to generate possible combinator evolutions.
ResourceFunction["CombinatorEvolutionPlot"] accepts following type specifications:
"StatesDisplay" displays the combinator evolution in a list, or multiple combinator evolutions in a list of lists, in a stylized way
"ExpressionDepthPlot" displays an array plot showing the depths of subexpressions throughout the combinator evolution
"SizeAndMatches" visualizes the leaf count of expressions and which leaves are changed by which rule at each step in evolution
"UpdateDepthPlot" visualizes the depth at which rule applications occur relative to the overall leaf counts at each step in evolution
"DepthAndUpdatePlot" visualizes depths of subexpressions throughout the combinator evolution, as well as which leaves are changed by which rule in evolution
"DepthCuboidPlot" visualizes depths of subexpressions throughout the combinator evolution in 3D, as well as which leaves are changed by which rule in evolution
"ArrayPlot" displays an array plot of evol
"ArrayPlotLeftAssociative" displays an array plot wherein the application operator is left associative
"ArrayPlotRightAssociative" displays an array plot wherein the application operator is right associative
"ArrayPlotBracketsOnly" displays an array plot wherein only the brackets are shown
"ArrayPlotPolishNotation" displays an array plot wherein each step is written in Polish notation
"ArrayPlotReversePolishNotation" displays an array plot wherein each step is written in reverse Polish notation
ResourceFunction["CombinatorEvolutionPlot"] accepts options from the resource function CombinatorPlot (including options from ArrayPlot), Grid, ListPlot3D, ListStepPlot and Graphics3D, as well as the following:
"SpanThickness" 0.2 the thickness of match indicator line in "SizeAndMatches", "DepthAndUpdatePlot"
"IncludeDepthAxis" False whether to show expression depth in 3D in "ExpressionDepthPlot"
"DisplayStyles" Automatic styling for rendering evol in a grid in "StatesDisplay"
"IncludeUpdateHighlighting" True whether updates are indicated in "DepthCuboidPlot"
"UpdateHighlightingStyles" Automatic styling for update highlighting

Examples

Basic Examples (12) 

Display the fixed-point evolution of a combinator expression:

In[1]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorFixedPointList"][
  s[s[s][s][s[s][k[k][s]][s]]][s[k[s][k]][k][s]], "SKGlyphs" -> {s, k}], "StatesDisplay"]
Out[1]=

Generate a plot showing the position depths in each expression of the combinator evolution:

In[2]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorFixedPointList"][s[s][s][s[s[s]]][k][s], "SKGlyphs" -> {s, k}], "ExpressionDepthPlot",  "SKGlyphs" -> {s, k}]
Out[2]=

Show the expression depths of the combinator evolution in 3D:

In[3]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorFixedPointList"][s[s][s][s[s[s]]][k][s], "SKGlyphs" -> {s, k}], "ExpressionDepthPlot", "IncludeDepthAxis" -> True]
Out[3]=

Show the leaf count and position/type of the matches throughout the combinator evolution:

In[4]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorFixedPointList"][s[s][s][s[s[s]]][k][s], "SKGlyphs" -> {s, k}], "SizeAndMatches",  "SpanThickness" -> 0.3, "SKGlyphs" -> {s, k}]
Out[4]=

Show the total depth of the combinator expressions and the depth at which the updates occur:

In[5]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorFixedPointList"][s[s][s][s[s[s]]][k][s], "SKGlyphs" -> {s, k}], "UpdateDepthPlot", "SKGlyphs" -> {s, k}]
Out[5]=

Show the leaf count, depth of subexpressions, and position and type of the matches throughout the combinator evolution:

In[6]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorFixedPointList"][s[s][s][s[s[s]]][k][s], "SKGlyphs" -> {s, k}], "DepthAndUpdatePlot", "SpanThickness" -> 0.6, "SKGlyphs" -> {s, k}]
Out[6]=

Visualize the same information from the previous example in 3D:

In[7]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorFixedPointList"][s[s][s][s[s[s]]][k][s], "SKGlyphs" -> {s, k}], "DepthCuboidPlot", "SKGlyphs" -> {s, k}, Boxed -> False]
Out[7]=

Display an ArrayPlot of the combinator evolution in standard form:

In[8]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorFixedPointList"][s[s][s][s[s[s]]][k][s], "SKGlyphs" -> {s, k}], "ArrayPlot", "SKGlyphs" -> {s, k}]
Out[8]=

Display an ArrayPlot of the combinator evolution with left associative combinator application:

In[9]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorFixedPointList"][s[s][s][s[s[s]]][k][s], "SKGlyphs" -> {s, k}], "ArrayPlotLeftAssociative", "SKGlyphs" -> {s, k}]
Out[9]=

Display an ArrayPlot of the combinator evolution with right associative combinator application:

In[10]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorFixedPointList"][s[s][s][s[s[s]]][k][s], "SKGlyphs" -> {s, k}], "ArrayPlotRightAssociative", "SKGlyphs" -> {s, k}]
Out[10]=

Display an ArrayPlot of the combinator evolution with only the brackets kept in each expression:

In[11]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorFixedPointList"][s[s][s][s[s[s]]][k][s], "SKGlyphs" -> {s, k}], "ArrayPlotBracketsOnly", "SKGlyphs" -> {s, k}]
Out[11]=

Display an ArrayPlot of the combinator evolution in Polish notation:

In[12]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorFixedPointList"][s[s][s][s[s[s]]][k][s], "SKGlyphs" -> {s, k}], "ArrayPlotPolishNotation", "SKGlyphs" -> {s, k}]
Out[12]=

Display an ArrayPlot of the combinator evolution in reverse Polish notation:

In[13]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorFixedPointList"][s[s][s][s[s[s]]][k][s], "SKGlyphs" -> {s, k}], "ArrayPlotReversePolishNotation", "SKGlyphs" -> {s, k}]
Out[13]=

Scope (4) 

Display a combinator evolution with left associative combinator application:

In[14]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorPlot"][#, "CharactersLeftAssociative", "SKGlyphs" -> {s, k}, "ApplicationGlyph" -> "\[NegativeVeryThinSpace]"] & /@ ResourceFunction["CombinatorFixedPointList"][
   s[s[s][s][s[s][k[k][s]][s]]][s[k[s][k]][k][s]], "SKGlyphs" -> {s, k}], "StatesDisplay"]
Out[14]=

Add styling to the same rendering of the combinator evolution:

In[15]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorPlot"][#, "CharactersLeftAssociative", "SKGlyphs" -> {s, k}, "ApplicationGlyph" -> "\[NegativeVeryThinSpace]"] & /@ ResourceFunction["CombinatorFixedPointList"][
   s[s[s][s][s[s][k[k][s]][s]]][s[k[s][k]][k][s]], "SKGlyphs" -> {s, k}], "StatesDisplay", "DisplayStyles" -> {s -> Style[s, FontWeight -> "DemiBold"], k -> Style[k, FontWeight -> "DemiBold"]}]
Out[15]=

Display a combinator expression evolved via two different evaluation schemes:

In[16]:=
ResourceFunction["CombinatorEvolutionPlot"][
 Map[ResourceFunction["CombinatorPlot"][#, "CharactersLeftAssociative", "SKGlyphs" -> {s, k}, "ApplicationGlyph" -> "\[NegativeVeryThinSpace]"] &, (ResourceFunction[
       "CombinatorFixedPointList"][
      s[s[s][s][s[s][k[k][s]][s]]][s[k[s][k]][k][s]], #, "SKGlyphs" -> {s, k}]) & /@ {{"Leftmost", "Outermost"}, {"Rightmost", "Innermost"}}, {2}], "StatesDisplay"]
Out[16]=

Display a combinator evolution with match framing at each step:

In[17]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorPlot"][#, "FramedMatches", "IncludeArgumentFraming" -> True, "SKGlyphs" -> {s, k}] & /@ ResourceFunction["CombinatorFixedPointList"][
   s[s[s][s][s[s][k[k][s]][s]]][s[k[s][k]][k][s]], "SKGlyphs" -> {s, k}], "StatesDisplay"]
Out[17]=

Define the color rules for an ArrayPlot of a combinator evolution in reverse Polish notation:

In[18]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorFixedPointList"][s[s][s][s[s[s]]][k][s], "SKGlyphs" -> {s, k}], "ArrayPlotReversePolishNotation", "SKGlyphs" -> {s, k}, ColorRules -> {"\[Application]" -> LightGray, "k" -> Blue, "s" -> Purple}]
Out[18]=

Resource History

Related Resources

License Information