Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 SKCombinatorLeftmostOutermostFinalExpression

Source Notebook

Compute the final state of the leftmost-outermost evolution of an SK combinator expression

Contributed by: Wolfram Research

ResourceFunction["SKCombinatorLeftmostOutermostFinalExpression"][cmb, t]

returns the final state of the leftmost-outermost evolution of the combinator expression cmb over t steps.

ResourceFunction["SKCombinatorLeftmostOutermostFinalExpression"][cmb, t, max]

returns the final state of the evolution of cmb if the leaf count of the final state is less than max.

Details and Options

The argument cmb should be given as a combinator expression in nested bracket form.
The arguments t and max should be given as integers.
ResourceFunction["SKCombinatorLeftmostOutermostFinalExpression"] has the option "SKGlyphs":
"SKGlyphs"{CombinatorS,CombinatorK}symbols used to specify S,K combinator transformation rules

Examples

Basic Examples (2) 

Find the state of an SK combinator evolution at a certain time step:

In[1]:=
ResourceFunction["SKCombinatorLeftmostOutermostFinalExpression"][ CombinatorS[CombinatorS][CombinatorS][ CombinatorK[CombinatorS][CombinatorK]][CombinatorS][ CombinatorS], 3]
Out[1]=

Compare the previous result with the last expression found by explicitly evolving the combinator expression:

In[2]:=
ResourceFunction["CombinatorEvolve"][ CombinatorS[CombinatorS][CombinatorS][ CombinatorK[CombinatorS][CombinatorK]][CombinatorS][ CombinatorS], 3]
Out[2]=

Use the third argument to constrain the maximum leaf count for the final expression:

In[3]:=
LeafCount[ ResourceFunction["SKCombinatorLeftmostOutermostFinalExpression"][ CombinatorS[CombinatorS][CombinatorS][CombinatorS[CombinatorS]][ CombinatorS][CombinatorS], 5]]
Out[3]=
In[4]:=
ResourceFunction["SKCombinatorLeftmostOutermostFinalExpression"][ CombinatorS[CombinatorS][CombinatorS][CombinatorS[CombinatorS]][ CombinatorS][CombinatorS], 5, 10]
Out[4]=

Options (1) 

SKGlyphs (1) 

Specify the symbols used to represent the S, K combinators in cmb:

In[5]:=
ResourceFunction["SKCombinatorLeftmostOutermostFinalExpression"][ s[s][s][k[k][k]][s][s], 3, "SKGlyphs" -> {s, k}]
Out[5]=

Properties and Relations (1) 

Compare the time efficiency of SKCombinatorLeftmostOutermostFinalExpression to that of taking the last state from the explicit evolution generated by the resource function CombinatorEvolve:

In[6]:=
First[Timing[ ResourceFunction["CombinatorEvolve"][ CombinatorS[CombinatorS][CombinatorS][CombinatorS[CombinatorS]][ CombinatorS][CombinatorS], 150]]]
Out[6]=
In[7]:=
First[Timing[ ResourceFunction["SKCombinatorLeftmostOutermostFinalExpression"][ CombinatorS[CombinatorS][CombinatorS][CombinatorS[CombinatorS]][ CombinatorS][CombinatorS], 150]]]
Out[7]=

Version History

  • 1.0.0 – 08 March 2021

Related Resources

License Information