Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 CombinatorToDAG

Source Notebook

Convert a combinator expression to a directed acyclic graph (DAG)

Contributed by: Wolfram Research

ResourceFunction["CombinatorToDAG"][cmb]

displays the combinator expression cmb as a directed acyclic graph, splitting the expression into heads and parts down to the level of atoms.

ResourceFunction["CombinatorToDAG"][cmb,t]

displays the possible subexpressions of the combinator expression cmb if cmb were allowed to evolve t steps, assuming the S and K combinator transformation rules.

ResourceFunction["CombinatorToDAG"][rules,cmb,t]

displays the possible subexpressions of the combinator expression cmb if cmb were allowed to evolve t steps via the possible transformations in the list rules.

Details and Options

The input cmb must be given as a combinator expression in nested bracket form.
The combinator transformations of interest must be given in rules as a list of Rule or RuleDelayed elements.
The number of steps t should be a non-negative integer.
ResourceFunction["CombinatorToDAG"] accepts options from Graph, with the following additions:
"SKGlyphs"{CombinatorS, CombinatorK}symbols used to specify default transformation rules
"ShowCausalGraph"Falsewhether to display causal graph of combinator evolution

Examples

Basic Examples (3) 

Display a combinator expression as a directed acyclic graph:

In[1]:=
ResourceFunction["CombinatorToDAG"][CombinatorS[x][y][z]]
Out[1]=

Demonstrate how an initial combinator expression can be evolved over a single step:

In[2]:=
ResourceFunction["CombinatorToDAG"][ CombinatorK[x][y][CombinatorS[z][y][x]], 1, VertexLabels -> None]
Out[2]=

Show the same DAGs, but this time labeled to clarify how the evolution works. A light purple dotted edge indicates direct application of a transformation rule, whereas a dark purple dotted line indicates application of a transformation rule to a subexpression:

In[3]:=
ResourceFunction["CombinatorToDAG"][ CombinatorK[x][y][CombinatorS[z][y][x]], 1]
Out[3]=

Evolve a combinator expression over 2 steps using a specified rule:

In[4]:=
ResourceFunction["CombinatorToDAG"][{s[x_][y_][z_] :> x[z][y[z]]}, s[s[s]][s][k], 2]
Out[4]=

Options (3) 

Evolve a combinator expression over 2 steps using the default rules with specified glyphs for the S and K combinators:

In[5]:=
ResourceFunction["CombinatorToDAG"][s[s[s]][s][k], 2, "SKGlyphs" -> {s, k}]
Out[5]=

Display a causal graph of update events for a certain step of a combinator evolution (yellow nodes correspond to light purple arrows in the DAG representation, and gray nodes correspond to dark purple arrows):

In[6]:=
ResourceFunction["CombinatorToDAG"][s[s[s]][s][k], 2, "SKGlyphs" -> {s, k}, "ShowCausalGraph" -> True]
Out[6]=

When a combinator expression reaches its fixed point (such that transformation rules can no longer be applied), the causal graph will cease to change:

In[7]:=
fpevol = ResourceFunction["CombinatorFixedPointList"][s[s[s]][s][k], "SKGlyphs" -> {s, k}]
Out[7]=
In[8]:=
ResourceFunction["CombinatorToDAG"][s[s[s]][s][k], #, "SKGlyphs" -> {s, k}, "ShowCausalGraph" -> True] & /@ Range[0, Length[fpevol]]
Out[8]=

Version History

  • 1.0.0 – 10 February 2021

Related Resources

License Information