Function Repository Resource:

CombinatorFixedPoint

Evolve a combinator expression to its fixed point based on defined rules and evaluation scheme

Contributed by: Wolfram Research

ResourceFunction["CombinatorFixedPoint"][cmb]

evolves combinator expression cmb to its fixed point using S and K combinator transformation rules and single leftmost outermost updating order.

ResourceFunction["CombinatorFixedPoint"][cmb,scheme]

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

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

evolves 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.

The combinator transformations of interest should be given as a list of Rule or RuleDelayed elements in rules.

ResourceFunction["CombinatorFixedPoint"] takes the following options:

MaxSteps

Infinity

maximum steps to take in evolving cmb

"MaxSize"

Infinity

maximum leaf count allowed for evolution of cmb

"SKGlyphs"

{CombinatorS,CombinatorK}

symbols used to specify default transformation rules

Examples

Basic Examples (2)

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

In[1]:=

Out[1]=

Specify the update scheme and only use the K combinator transformation rule to evolve the combinator expression to its fixed point:

In[2]:=

$ResourceFunction["CombinatorFixedPoint"][{k[x_][y_] -> x}, s[s[s][s][s[s][k[k][s]][s]]][s[k[s][k]][k][s]], {"Innermost", "Rightmost", 1}, "SKGlyphs" -> {s, k}]$

Out[2]=

Properties and Relations (2)

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

In[3]:=

Out[3]=

One can replicate this result with the use of ReplaceAll in FixedPoint:

In[4]:=

$FixedPoint[ ReplaceAll[#, {s[x_][y_][z_] :> x[z][y[z]], k[x_][y_] :> x}] &, s[s[s][s][s[s][k[k][s]][s]]][s[k[s][k]][k][s]]]$

Out[4]=

Possible Issues (1)

The "MaxSize" and "MaxSteps" options can be useful for avoiding excessively long combinator evolutions, but will throw failures if their values are surpassed:

In[5]:=