Function Repository Resource:

CombinatorFixedPointList

Source Notebook

Show the evolution of a combinator expression to its fixed point based on defined rules and an evaluation scheme

Contributed by: Wolfram Research

ResourceFunction["CombinatorFixedPointList"][cmb]

shows the evolution of the combinator expression cmb to its fixed point using S and K combinator transformation rules and single leftmost-outermost updating order.

ResourceFunction["CombinatorFixedPointList"][cmb]

shows the evolution of the combinator expression cmb to its fixed point using S and K combinator transformation rules and single leftmost-outermost updating order.

ResourceFunction["CombinatorFixedPointList"][cmb,scheme]

shows the evolution of cmb to its fixed point using S and K combinator transformation rules in matches found by scheme at each step.

ResourceFunction["CombinatorFixedPointList"][rules, cmb,scheme]

shows evolution cmb to its fixed point using rules in matches found by scheme at each step.

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.
CombinatorFixedPoint takes the following options:
MaxStepsInfinitymaximum steps to take in evolving cmb
"MaxSize"Infinitymaximum leaf count allowed for evolution of cmb
"SKGlyphs"{CombinatorS,CombinatorK}symbols used to specify default transformation rules

Examples

Basic Examples (2) 

Show steps of the fixed point evolution of a combinator expression using the default single leftmost-outermost update with S and K combinator transformation rules:

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

Specify the update scheme and only use the K combinator transformation rule to show the fixed-point evolution of the combinator expression:

In[2]:=
ResourceFunction["CombinatorFixedPointList"][{k[x_][y_] -> x}, s[s[s][s][s[s][k[k][s]][s]]][s[k[s][k]][k][s]], {"Innermost", "Rightmost", 1}]
Out[2]=

Scope (1) 

Calculate the leaf count of each expression generated during an evolution:

In[3]:=
LeafCount /@ ResourceFunction["CombinatorFixedPointList"][
  s[s][s][s[s]][s][s], {"Rightmost", "Innermost"}, "SKGlyphs" -> {s, k}, "MaxSize" -> 100]
Out[3]=

Properties and Relations (2) 

Show the steps of the fixed-point evolution of a combinator expression using the default single leftmost-outermost update with S and K combinator transformation rules:

In[4]:=
cmb = s[s[s][s][s[s][k[k][s]][s]]][s[k[s][k]][k][s]];
In[5]:=
ResourceFunction["CombinatorFixedPointList"][cmb, "SKGlyphs" -> {s, k}]
Out[5]=

One can show a similar fixed-point evolution using ReplaceAll in FixedPointList, which performs all non-overlapping updates in leftmost-outermost order:

In[6]:=
FixedPointList[
 ReplaceAll[#, {s[x_][y_][z_] :> x[z][y[z]], k[x_][y_] :> x}] &, cmb]
Out[6]=

Possible Issues (1) 

If the option values for "MaxSize" or "MaxSteps" are surpassed, the returned evolution ends before reaching a fixed point:

In[7]:=
ResourceFunction["CombinatorMatches"][#, {"Leftmost", "Outermost"}, "SKGlyphs" -> {s, k}] &[
 Last[ResourceFunction["CombinatorFixedPointList"][
   s[s][s][s[s]][s][s], "MaxSize" -> 100, "SKGlyphs" -> {s, k}]]]
Out[7]=
In[8]:=
ResourceFunction["CombinatorMatches"][#, {"Leftmost", "Outermost"}, "SKGlyphs" -> {s, k}] &[
 Last[ResourceFunction["CombinatorFixedPointList"][
   s[s][s][s[s]][s][s], "MaxSteps" -> 30, "SKGlyphs" -> {s, k}]]]
Out[8]=

Version History

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

Related Resources

License Information