I published a paper a while back called “Patterns in Combinator Evolution.” In it, I showed that in a way, all size 4 and 5 combinators evaluate only according to a certain number of patterns that are built up on each other. I wrote that I generated all combinator patterns up to size 5, then less general rules were excluded in favor of more general rules (for instance, the more general S[K][y_][x_] :> x is included but not the more specific S[K][S][x_] :> x). Also, cases where applying a shorter combinator rule has the same effect as applying a larger combinator rule are not included. The rule S[S[K][y_][x_]] :> S[x] is not included, since the shorter rule S[K][y_][x_] :> x applied to S[S[K][y_][x_]] will also give S[x] in one step. Today I’m publishing the code I wrote to filter the combinators, and also showing how combinators of size 6 evaluate.
Code
Code
Outcome
Outcome
In[]:=
rulesTo4=lessContainingPatternsSorted[4]//Column
Out[]=
S K |
In[]:=
rulesTo5=lessContainingPatternsSorted[5]//Column
Out[]=
S S K |
S S K |
S S K |
K K |
K K |
K K |
S K |
S K |
S S |
S S |
S K |
In[]:=
rulesTo6=lessContainingPatternsSorted[6]//Column
Out[]=