| Ball DeBruijn Notation | Function Abstraction | Symbol | Bird | Combinator | SK Combinator |
|---|---|---|---|---|---|
| 3.3(21) | labc.a(bc) | B | Bluebird | S(KS)K | ((S(KS))K) |
| 4.4(321) | labcd.a(bcd) | B1 | Blackbird | BBB | ((S(K((S(KS))K)))((S(KS))K)) |
| 5.5(4321) | labcde.a(bcde) | B2 | Bunting | B(BBB)B | ((S(K((S(K((S(KS))K)))((S(KS))K))))((S(KS))K)) |
| 4.4(3(21)) | labcd.a(b(cd)) | B3 | Becard | B(BB)B | ((S(K((S(K((S(KS))K)))((S(KS))K))))((S(KS))K)) |
| 3.312 | labc.acb | C | Cardinal | S(BBS)(KK) | ((S((S(K((S(KS))K)))S))(KK)) |
| 4.43(21) | labcd.ab(cd) | D | Dove | BB | (S(K((S(KS))K))) |
| 5.543(21) | labcde.abc(de) | D1 | Dickcissel | B(BB) | (S(K(S(K((S(KS))K))))) |
| 5.5(43)(21) | labcde.a(bc)(de) | D2 | Dovekies | BB(BB) | ((S(K((S(KS))K)))(S(K((S(KS))K)))) |
| 5.54(321) | labcde.ab(cde) | E | Eagle | B(BBB) | (S(K((S(K((S(KS))K)))((S(KS))K)))) |
| 7.7(654)(321) | labcdefg.a(bcd)(efg) | Ê | Bald Eagle | B(BBB)(B(BBB)) | ((S(K((S(K((S(KS))K)))((S(KS))K))))(S(K((S(K((S(KS))K)))((S(KS))K))))) |
| 3.123 | labc.cba | F | Finch | ETTET | ((S(K((S((SK)K))(K((S(K(S((SK)K))))K)))))((S(K((S(K((S(KS))K)))((S(KS))K))))((S(K(S((SK)K))))K))) |
| 4.41(32) | labcd.ad(bc) | G | Goldfinch | BBC | ((S(K((S(KS))K)))((S((S(K((S(KS))K)))S))(KK))) |
| 3.3212 | labc.abcb | H | Hummingbird | BW(BC) | ((S(K((S(K(S((S(K((S((SK)K))((SK)K))))((S(K((S(KS))K)))((S(K(S((SK)K))))K))))))K)))(S(K((S((S(K((S(KS))K)))S))(KK))))) |
| 1.1 | la.a | I | Identity Bird (aka Idiot) | SKK | ((SK)K) |
| 4.43(412) | labcd.ab(adc) | J | Jay | B(BC)(W(BC(B(BBB)))) | ((S(K(S(K((S((S(K((S(KS))K)))S))(KK))))))((S((S(K((S((SK)K))((SK)K))))((S(K((S(KS))K)))((S(K(S((SK)K))))K))))(K((S(K((S((S(K((S(KS))K)))S))(KK))))(S(K((S(K((S(KS))K)))((S(KS))K)))))))) |
| 2.2 | lab.a | K | Kestrel (True) | K | K |
| 2.2(11) | lab.a(bb) | L | Lark | CBM | ((S((S(KS))K))(K((S((SK)K))((SK)K)))) |
| 1.11 | la.aa | M | Mockingbird | SII | ((S((SK)K))((SK)K)) |
| 2.21(21) | lab.ab(ab) | M2 | Double Mockingbird | BM | (S(K((S((SK)K))((SK)K)))) |
| 2.1(21) | lab.b(ab) | O | Owl | SI | (S((SK)K)) |
| 3.2(31) | labc.b(ac) | Q | Queer Bird | CB | ((S(K(S((S(KS))K))))K) |
| 3.3(12) | labc.a(cb) | Q1 | Quixotic Bird | BCB | ((S(K((S((S(K((S(KS))K)))S))(KK))))((S(KS))K)) |
| 3.2(13) | labc.b(ca) | Q2 | Quizzical Bird | C(BCB) | ((S(K(S((S(K((S((S(K((S(KS))K)))S))(KK))))((S(KS))K)))))K) |
| 3.1(32) | labc.c(ab) | Q3 | Quirky Bird | BT | (S(K((S(K(S((SK)K))))K))) |
| 3.1(23) | labc.c(ba) | Q4 | Quacky Bird | F*B | ((S(K((S((S(K((S(KS))K)))S))(KK))))((S(K(S((S(K((S((S(K((S(KS))K)))S))(KK))))((S(KS))K)))))K)) |
| 3.213 | labc.bca | R | Robin | BBT | ((S(K((S(KS))K)))((S(K(S((SK)K))))K)) |
| 3.31(21) | labc.ac(bc) | S | Starling | S | S |
| 2.12 | lab.ba | T | Thrush | CI | ((S(K(S((SK)K))))K) |
| 2.1(221) | lab.b(aab) | U | Turing | LO | ((S(K(S((SK)K))))((S((SK)K))((SK)K))) |
| 3.132 | labc.cab | V | Vireo (aka Pairing) | BCT | ((S(K((S((S(K((S(KS))K)))S))(KK))))((S(K(S((SK)K))))K)) |
| 2.211 | lab.abb | W | Warbler | C(BMR) | ((S(K(S((S(K((S((SK)K))((SK)K))))((S(K((S(KS))K)))((S(K(S((SK)K))))K))))))K) |
| 2.122 | lab.baa | W1 | Converse Warbler | CW | ((S(K(S((S(K(S((S(K((S((SK)K))((SK)K))))((S(K((S(KS))K)))((S(K(S((SK)K))))K))))))K))))K) |
| ??? | la.a(la) | Y | Why Bird (aka Sage Bird) | SLL | (((SS)K)((S(K((SS)(S((SS)K)))))K) |
| 2.21 | lab.ab | I* | Identity Bird Once Removed | S(SK) | (S(SK)) |
| 3.3211 | labc.abcc | W* | Warbler Once Removed | BW | (S(K((S(K(S((S(K((S((SK)K))((SK)K))))((S(K((S(KS))K)))((S(K(S((SK)K))))K))))))K))) |
| 4.4312 | labcd.abdc | C* | Cardinal Once Removed | BC | (S(K((S((S(K((S(KS))K)))S))(KK)))) |
| 4.4213 | labcd.acdb | R* | Robin Once Removed | CC | ((S(K((S((S(K((S(KS))K)))S))(KK))))(S(K((S((S(K((S(KS))K)))S))(KK))))) |
| 4.4123 | labcd.adcb | F* | Finch Once Removed | BCR | ((S(K(S(K((S((S(K((S(KS))K)))S))(KK))))))((S(K((S((S(K((S(KS))K)))S))(KK))))(S(K((S((S(K((S(KS))K)))S))(KK)))))) |
| 4.4231 | labcd.acbd | V* | Vireo Once Removed | CF | ((S(K((S((S(K((S(KS))K)))S))(KK))))((S(K(S(K((S((S(K((S(KS))K)))S))(KK))))))((S(K((S((S(K((S(KS))K)))S))(KK))))(S(K((S((S(K((S(KS))K)))S))(KK))))))) |
| 3.321 | labc.abc | I** | Identity Bird Twice Removed | ||
| 4.43211 | labcd.abcdd | W** | Warbler Twice Removed | B(BW) | S(K(S(K((S(K(S((S(K((S((SK)K))((SK)K))))((S(K((S(KS))K)))((S(K(S((SK)K))))K))))))K))))) |
| 5.54312 | labcde.abced | C** | Cardinal Twice Removed | BC* | S(K(S(K((S((S(K((S(KS))K)))S))(KK)))))) |
| 5.54213 | labcde.abdec | R** | Robin Twice Removed | BR* | (S(K((S(K((S((S(K((S(KS))K)))S))(KK))))(S(K((S((S(K((S(KS))K)))S))(KK))))))) |
| 5.54123 | labcde.abedc | F** | Finch Twice Removed | BF* | (S(K((S(K(S(K((S((S(K((S(KS))K)))S))(KK))))))((S(K((S((S(K((S(KS))K)))S))(KK))))(S(K((S((S(K((S(KS))K)))S))(KK)))))))) |
| 5.54132 | labcde.abecd | V** | Vireo Twice Removed | BV* | (S(K((S(K((S((S(K((S(KS))K)))S))(KK))))((S(K(S(K((S((S(K((S(KS))K)))S))(KK))))))((S(K((S((S(K((S(KS))K)))S))(KK))))(S(K((S((S(K((S(KS))K)))S))(KK))))))))) |
| 2.1 | lab.b | KI | Kite (False) | KI | (K((SK)K)) |
| ??? | l | W | Omega | MM | (((S((SK)K))((SK)K))((S((SK)K))((SK)K))) |
| 2.11 | lab.bb | KM | Konstant Mocker | KM | (K((S((SK)K))((SK)K))) |
| 2.22 | lab.aa | C(KM) | Crossed Konstant Mocker | C(KM) | ((S(K(S(K((S((SK)K))((SK)K))))))K) |
| ??? | l | Q | Theta | YO | ((((SS)K)((S(K((SS)(S((SS)K)))))K)(S((SK)K))) |
The combinatory birds were borrowed from To Mock A MockingBird, by Raymond Smullyan.
Some additional information about combinator birds can be found in To Dissect a Mockingbird by David C Keenan.
Some of the SK Combinatory terms were first reduced using the Combinatory Logic Tutorial by Chris Barker.
Chris Rathman / [email protected] source : http://www.angelfire.com/tx4/cus/combinator/birds.html
The term λx. λy. λz. x z (y z) (the S combinator), with de Bruijn indices, is λ λ λ 3 1 (2 1).