Function Repository Resource:

ChurchCombinator

Source Notebook

Evaluate the Church combinator

Contributed by: Wolfram Research

ResourceFunction["ChurchCombinator"][n]

gives a combinator corresponding to the n-th Church numeral where n is an integer.

ResourceFunction["ChurchCombinator"][op]

gives a combinator corresponding to the operator op.

Details and Options

In ResourceFunction["ChurchCombinator"][op], op can be any of the operators Increment, Plus, Times or Power.
ResourceFunction["ChurchCombinator"] can take the following option:
"SKGlyphs"{CombinatorS,CombinatorK}symbols used to specify combinators

Examples

Basic Examples (3) 

Generate a combinator corresponding to the seventh Church numeral:

In[1]:=
cm = ResourceFunction["ChurchCombinator"][7]
Out[1]=

Apply combinator transformation rules to see the numeral itself:

In[2]:=
cm[a][b] //. {CombinatorS[x_][y_][z_] -> x[z][y[z]], CombinatorK[x_][y_] -> x}
Out[2]=

Convert to an integer:

In[3]:=
Depth[%] - 1
Out[3]=

Scope (4) 

Combinator for the zeroth Church numeral:

In[4]:=
zero = ResourceFunction["ChurchCombinator"][0, "SKGlyphs" -> {s, k}]
Out[4]=

Apply combinator transformation rules to see the numeral itself:

In[5]:=
zero[a][b] //. {s[x_][y_][z_] -> x[z][y[z]], k[x_][y_] -> x}
Out[5]=
In[6]:=
Depth[%] - 1
Out[6]=

Increment a Church numeral combinator:

In[7]:=
inc = ResourceFunction["ChurchCombinator"][Increment, "SKGlyphs" -> {s, k}][
  ResourceFunction["ChurchCombinator"][1, "SKGlyphs" -> {s, k}]]
Out[7]=
In[8]:=
inc[a][b] //. {s[x_][y_][z_] -> x[z][y[z]], k[x_][y_] -> x}
Out[8]=
In[9]:=
Depth[%] - 1
Out[9]=

Add two Church numeral combinators:

In[10]:=
plus = ResourceFunction["ChurchCombinator"][Plus, "SKGlyphs" -> {s, k}][
   ResourceFunction["ChurchCombinator"][2, "SKGlyphs" -> {s, k}]][
  ResourceFunction["ChurchCombinator"][3, "SKGlyphs" -> {s, k}]]
Out[10]=
In[11]:=
plus[a][b] //. {s[x_][y_][z_] -> x[z][y[z]], k[x_][y_] -> x}
Out[11]=
In[12]:=
Depth[%] - 1
Out[12]=

Multiply two Church numeral combinators:

In[13]:=
times = ResourceFunction["ChurchCombinator"][Times][
   ResourceFunction["ChurchCombinator"][2]][
  ResourceFunction["ChurchCombinator"][3]]
Out[13]=
In[14]:=
times[a][b] //. {CombinatorS[x_][y_][z_] -> x[z][y[z]], CombinatorK[x_][y_] -> x}
Out[14]=
In[15]:=
Depth[%] - 1
Out[15]=

Raise a Church numeral combinator to the power of another Church numeral combinator:

In[16]:=
power = ResourceFunction["ChurchCombinator"][Power, "SKGlyphs" -> {s, k}][
   ResourceFunction["ChurchCombinator"][2, "SKGlyphs" -> {s, k}]][
  ResourceFunction["ChurchCombinator"][3, "SKGlyphs" -> {s, k}]]
Out[16]=
In[17]:=
power[a][b] //. {s[x_][y_][z_] -> x[z][y[z]], k[x_][y_] -> x}
Out[17]=
In[18]:=
Depth[%] - 1
Out[18]=

Possible Issues (2) 

ChurchCombinator is only defined for nonnegative integer n:

In[19]:=
ResourceFunction["ChurchCombinator"][-2, "SKGlyphs" -> {s, k}][a][
  b] //. {s[x_][y_][z_] -> x[z][y[z]], k[x_][y_] -> x}
Out[19]=

ChurchCombinator does not support all integer operations:

In[20]:=
ResourceFunction["ChurchCombinator"][Subtract, "SKGlyphs" -> {s, k}][
  ResourceFunction["ChurchCombinator"][3, "SKGlyphs" -> {s, k}]][
 ResourceFunction["ChurchCombinator"][2, "SKGlyphs" -> {s, k}]]
Out[20]=

Version History

  • 1.0.0 – 05 January 2021

Related Resources

License Information