Function Repository Resource:

CombinatorEvolve

Source Notebook

Evolve a combinator expression for a certain number of steps based on defined rules and an evaluation scheme

Contributed by: Wolfram Research

ResourceFunction["CombinatorEvolve"][cmb,t]

evolves the combinator expression cmb across t steps using S and K combinator transformation rules and single leftmost-outermost updating order.

ResourceFunction["CombinatorEvolve"][cmb,t,scheme]

evolves cmb using S and K combinator transformation rules in matches found by scheme.

ResourceFunction["CombinatorEvolve"][rules,cmb,t,scheme]

evolves cmb using rules in matches found by scheme.

Details and Options

The input cmb must be given as a combinator expression in nested bracket form.
If scheme is specified, direction ("Leftmost", "Rightmost"), depth order ("Outermost", "Innermost") and number of matches (integer number or Infinity) must be specified in order of their priority as sorting criteria.
The combinator transformations of interest should be given as a list of Rule or RuleDelayed elements in rules.
The number of steps t should be an integer number.
ResourceFunction["CombinatorEvolve"] has the following options:
"MaxSize"Infinitymaximum leaf count allowed for evolution of cmb
"SKGlyphs"{CombinatorS,CombinatorK}symbols used to specify default transformation rules

Examples

Basic Examples (2) 

Evolve a combinator expression for five steps using the default S and K combinator transformation rules in the single-match leftmost-outermost updating scheme:

In[1]:=
ResourceFunction["CombinatorEvolve"][
 s[x][s[x][y][z]][y[k[x][y][k[x][y]]]], 5, "SKGlyphs" -> {s, k}]
Out[1]=

Evolve a combinator expression for five steps, specifying that only the S combinator rule should be used in an all-match rightmost-innermost updating scheme:

In[2]:=
ResourceFunction["CombinatorEvolve"][{s[x_][y_][z_] :> x[z][y[z]]}, s[x][s[x][y][z]][y[k[x][y][k[x][y]]]], 5, {"Innermost", "Rightmost", Infinity}]
Out[2]=

Possible Issues (2) 

The "MaxSize" option can be useful for avoiding excessively long combinator evolutions, but will throw a failure if its value is surpassed:

In[3]:=
ResourceFunction["CombinatorEvolve"][s[s][s][s[s]][s][s], 200, "MaxSize" -> 100, "SKGlyphs" -> {s, k}]
Out[3]=

CombinatorEvolve returns the fixed-point value if the expression has stopped evolving:

In[4]:=
ResourceFunction["CombinatorEvolve"][
 s[x][s[x][y][z]][y[k[x][y][k[x][y]]]], 6, "SKGlyphs" -> {s, k}]
Out[4]=
In[5]:=
ResourceFunction["CombinatorEvolve"][
 s[x][s[x][y][z]][y[k[x][y][k[x][y]]]], 20, "SKGlyphs" -> {s, k}]
Out[5]=

Version History

  • 1.0.3 – 05 December 2020
  • 1.0.2 – 05 December 2020
  • 1.0.1 – 05 December 2020
  • 1.0.0 – 04 December 2020

Related Resources

License Information