Wolfram Research

Combinator Birds

Source Notebook

Information about 50 combinator functions

Details

The data is imported from this table of Combinator Birds, which in turn is taken from "To Mock a Mockingbird" by Raymond Smullyan.
The default content is a Dataset containing the following properties for each named combinator:
"Symbol" the symbol used to represent the combinator in the "Rule" property
"Rule" the operation of the combinator expressed via a transformation Rule
"Arguments" the number of arguments expected for the combinator to apply
"SK Basis Form" the combinator written as an expression in the SK combinator basis

Examples

Basic Examples

Get the rules corresponding to each combinator bird:

In[1]:=
ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)][[All, "Rule"]]
Out[1]=

Select combinators from the Dataset by their symbols:

In[2]:=
ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)][Select[MemberQ[{bla, owl, kon}, #Symbol] &]]
Out[2]=

Scope & Additional Elements

Use combinator rules to transform a combinator expression to its fixed point, at which it can no longer evolve:

In[3]:=
dov[dou][a][b][c] //. {ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Dove", "Rule"], ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Double Mockingbird", "Rule"]}
Out[3]=

Use combinator rules to evolve a combinator expression for a certain number of steps with a given traversal scheme:

In[4]:=
ResourceFunction["CombinatorEvolveList"][{ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Bald Eagle", "Rule"], ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Mockingbird", "Rule"], ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Thrush", "Rule"]}, bal[moc][b][c][d][thr][f][g], 3, {"Leftmost", "Outermost", 1}] // Column
Out[4]=
In[5]:=
ResourceFunction["CombinatorEvolveList"][{ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Bald Eagle", "Rule"], ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Mockingbird", "Rule"], ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Thrush", "Rule"]}, bal[moc][b][c][d][thr][f][g], 3, {"Rightmost", "Outermost", 1}] // Column
Out[5]=

Use the SK basis form of a combinator in its rule:

In[6]:=
ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Kite (False)", "Rule"] /. {ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Kite (False)", "Symbol"] -> ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Kite (False)", "SK Basis Form"]}
Out[6]=

Visualizations

Visualize the possible updates at each step in the evolution of a combinator given certain rules:

In[7]:=
ResourceFunction["CombinatorEvolutionPlot"][
 ResourceFunction["CombinatorPlot"][#, "FramedMatches", "CombinatorRules" -> {ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Dove", "Rule"], ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Double Mockingbird", "Rule"]}, "CombinatorStyles" -> <|
      dov -> <|"Highlight" -> Purple, "Background" -> LightPurple, "MatchText" -> Bold|> , dou -> <|"Highlight" -> Pink, "Background" -> LightPink, "MatchText" -> Bold|>|>] & /@ ResourceFunction["CombinatorFixedPointList"][{ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Dove", "Rule"], ResourceData[\!\(\*
TagBox["\"\<Combinator Birds\>\"",
#& ,
BoxID -> "ResourceTag-Combinator Birds-Input",
AutoDelete->True]\)]["Double Mockingbird", "Rule"]}, dov[dou][a][b][c], {"Leftmost", "Outermost"}], "StatesDisplay"]
Out[7]=

Wolfram Research, "Combinator Birds" from the Wolfram Data Repository (2021) 

Data Resource History

Source Metadata

See Also

Publisher Information