XXIIVV
The Becekew Warbler
The Becekew Warbler16J13

A certain enchanted forest is inhabited by talking birds.

Combinatory Forests are inhabited by talking birds, which speak words represented here by shapes, or groups of shapes delimited by parentheses. Avian dialog demonstrates that even without anything as crude as digits and operators, arithmetic and computation can emerge. To find examples of combinatory logic used in practice, see rewriting programming.

A talking bird, given some words, yields a combination of those words, we always listen to the left-most bird first.

T()  C(WK)x(yz)

The Bekimet Forest

Within the Bekimet forest, we find the B, KI, M, and T birds. Each bird listens to a phrase, and answers with another. The first bird that we observe is the Mockingbird, which repeats the first word.

M   W(WK)x

The second bird that we observe is the Kite, which discards the first word.

KI   K(WK)xy

The third bird that we observe is the Thrush, which swaps the first and second words, notice how parenthesized words count as a single word.

T()  () C(WK)(xx)y

We can't quite make out the fourth bird, but we observe that it is the Bluebird, which is also found in the next forest, so let's continue.

Mockingbirdx x y zDuplicates the first word
Kitey zDiscards the first word
Thrushy x zSwaps the first and second words

The Becekew Forest

Within the Becekew forest, we find the B, C, K, and W birds. The first bird that we observe is the Warbler, which repeats the second word. This bird's song is similar to the Mockingbird, which repeats the first word.

W   Wxy

The second bird that we hear is the Kestrel, which discards the second word. This bird's song is similar to the Kite, which discards the first word. Here is the Kestrel, followed by the Warbler, notice how we always listen to birds in a sequence from the left-most bird first.

KW  W   KWxyz

The third bird that we hear is the Cardinal, which swaps the second and third words. This bird's song is similar to the Thrush, which swaps the first and second words. Here is the Cardinal, followed by the Kestrel, notice how the effect of these two birds could be done by the Kite.

CK  K   CKxyz

The elusive Bluebird takes three words, and parenthesizes the third word into the second word. It is used to "chain" words together, for example, something like "B (increment) (double) number", becomes "(increment (double number))".

B()()  (()) Bx(yy)(zz)
Warblerx y y zDuplicates the second word
Kestrelx zDiscards the second word
Cardinalx z ySwaps the second and third words
Bluebirdx (y z)Composition of x to y to z

The Sekei Forest

Within the Sekei forest, we find the S, K, and I birds. The simplest of these birds, appears to have no intelligence at all, and so it is called the Idiot bird since its response to hearing any word, is that same word.

I()  () (WK)(xy)

The Kestrel is also found in this forest, but we're already familiar with this one. Let's take a moment to see how words can be grouped by parentheses and transformed as if they were a single word. For instance, the Kestrel discards the second group of parenthesized words.

K()()  () Kx(yy)(zz)

The Starling applies the first and second words to the last, then applies the first result to the second result.

S  ()(()) B(B(BW)C)(BB)xyz
IdiotxxReturns its word
Starlingx y zx z (y z)Returns x(z) applied to y(z).

Conversion

Although these birds have been investigated somewhat over the past eighty years, they have for the most part been viewed as rather obscure and irrelevant creatures. It is a challenge to find any way to translate their behavior into something suitable for human perception.

Bekimet-BecekewBecekew-SekeiSekei-Becekew
KIK(WK)BS(KS)KSB(B(BW)C)(B B)
MW(WK)CS(S(K(S(KS)K))S)(KK)KK
TC(WK)KKIWK
WSS(SK)
And for that I turned to programs, and began to study just what programs in the wild might do.~

The Ornithomicon is the infamous grimoire of Avian Arithmetic.

Before progressing deeper into the enchanted forests, you should be familiar with the 9 birds of the Bekimet, Becekew and Sekei forests.

Avian Truths & Lies

The Kestrel takes two words and discards the second word. In other words, it always keeps the first one, this is the word for True:

K   Kxy

The Kite takes two words and discards the first word. In other words, it never keeps the first one, this is the word for False:

KI   KIxy

The Cardinal swaps the second and third words, it can turn a lie into a truth, and a truth into a lie, this is the word for Not:

C(KI)   C(KI)(K)(KI)xy

The Mockingbird takes 2 words that can be either True or False, and says True if at least one of them is True, this is the word for Or:

M(KI)(K)   W(WK)(KI)(K)xy

Two Starlings and a Kestrel can work together to say True, when both words are True, this is the word for And:

SSK(KI)(K)   SSK(KI)(K)xy

Since the word for True keeps the first of 2 words, and False selects the second, we need a way to pass the second and third words to the first one. The Idiotbird is the equivalent to IfThenElse:

I(KI)   I(KI)xy

Avian Numerals

Avian numerals are somewhat odd, the value of a number is equal to how many times a word applies itself on another. Considering that numbers are times a word is applied onto another, applying "2 sqr" to a number "3" would give "sqr (sqr 3)", or 81.

0KIfxx4SB(SB(WB))fxf(f(f(fx)))
1Ifxfx5SB(SB(SB(WB)))fxf(f(f(f(fx))))
2WBfxf(fx)6SB(SB(SB(SB(WB))))fxf(f(f(f(f(fx)))))
3SB(WB)fxf(f(fx))7SB(SB(SB(SB(SB(WB)))))fxf(f(f(f(f(f(fx))))))

It looks like a Starling and Bluebird always give us the succeeding number, since "SB2" is 3 and "SB3" is 4.

SB5  6 SB(SB(SB(SB(WB))))fx

Among its many talents, the Bluebird can also Multiply numbers, as "2(3f)" is the same as "6f", thus, "B(2)(3)" is the same as "6".

B23  6 B(2)(3)fx

Our old friend the Thrush is capable of calculating the Power of two numbers. The following example is essentially applying the word three (which itself applies a word 3 times) four times.

T34  81 C(WK)(3)(4)fx

As we travel deeper into the forest, we encounter the Nightingale, which applies a word to the result of the second and the fourth, and to the result of the third and the fourth:

N  ()() B(BS)Bfxyz

The Nightingale allows us to apply the first number onto the second, or effectively Add numbers together:

NB23  5 B(BS)BB(2)(3)fx

The Ornithodex is the reference manual of common combinator birds.

Color-coded for the Bekimet, Becekew and Sekei forests.

AbstractionSymbolBirdCombinator
λabc.a(bc)BBluebirdS(KS)K
λabcd.a(bcd)B1BlackbirdBBB
λabcde.a(bcde)B2BuntingB(BBB)B
λabcd.a(b(cd))B3BecardB(BB)B
λabc.acbCCardinalS(BBS)(KK)
λabcd.ab(cd)DDoveBB
λabcde.abc(de)D1DickcisselB(BB)
λabcde.a(bc)(de)D2DovekiesBB(BB)
λabcde.ab(cde)EEagleB(BBB)
λabcdefg.a(bcd)(efg)ÊBald EagleB(BBB)(B(BBB))
λabc.cbaFFinchETTET
λabcd.ad(bc)GGoldfinchBBC
λabc.abcbHHummingbirdBW(BC)
λa.aIIdiot(Identity)SKK
λabcd.ab(adc)JJayB(BC)(W(BC(B(BBB))))
λab.aKKestrel (True)
λab.bKIKite (False)KI
λab.a(bb)LLarkCBM
λabcd.a(bd)(cd)NNightingaleB(BS)B
λa.aaMMockingbirdSII
λab.ab(ab)M2Double MockingbirdBM
λab.b(ab)OOwlSI
λabc.b(ac)QQueer BirdCB
λabc.a(cb)Q1Quixotic BirdBCB
λabc.b(ca)Q2Quizzical BirdC(BCB)
λabc.c(ab)Q3Quirky BirdBT
λabc.c(ba)Q4Quacky BirdF*B
λabc.bcaRRobinBBT
λabc.ac(bc)SStarlingS
λab.baTThrushCI
λab.b(aab)UTuringLO
λabc.cabVVireo (aka Pairing)BCT
λab.abbWWarblerC(BMR)
λab.baaW1Converse WarblerCW
λa.a(λa)YWhy Bird (aka Sage Bird)SLL
λab.abI*Identity Bird Once RemovedS(SK)
λabc.abccW*Warbler Once RemovedBW
λabcd.abdcC*Cardinal Once RemovedBC
λabcd.acdbR*Robin Once RemovedC*C*
λabcd.adcbF*Finch Once RemovedBC*R*
λabcd.acbdV*Vireo Once RemovedC*F*
λabcd.abcddW**Warbler Twice RemovedB(BW)
λabcde.abcedC**Cardinal Twice RemovedBC*
λabcde.abdecR**Robin Twice RemovedBR*
λabcde.abedcF**Finch Twice RemovedBF*
λabcde.abecdV**Vireo Twice RemovedBV*
λab.bbKMKonstant MockerKM
λab.aaC(KM)Crossed Konstant MockerC(KM)

incoming reversible computing programming languages fractran interaction nets thuesday