Function Repository Resource:

CombinatorFixedPointList

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:

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)

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]:=

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]:=

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]:=

In[5]:=

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]$