Combinatory logic/Analysis of combinators

This article serves as a place for me to analyze the behavior of the To Mock a Mockingbird combinators, as seen on the page Combinatory logic.
== Definitions ==
For anything said in this page to be properly sciency, some terminology must be defined. This section covers that.
* S-reduction means evaluating the S combinator into its evaluated form (e.g. S-reducing Sxyz converts to xz(yz)
* K-reduction means converting a K combinator expression to a yielder. (e.g. Kxy = <yields(x)>y = x)
* π-reduction means replacing a series of combinators in a combinator expression with a combinator with the same effect for ease of reading (e.g. S(SKK)Kx = SIKx)
* A yielder is the product of application of K to a combinator. They are written as <yields([value])> (e.g. Kx = <yielder(x)>)
* Argument-giving means putting a variable name after a combinator which does not have all its arguments. These are written as lowercase letters and represent any combinator, and are used simply so that we can tell what's going on by assigning concrete names to abstract variables. Names are not reused in a combinator analysis. (e.g. giving SKK its arguments is written as SKKx)
=== Primitives ===
The S and K combinators are primitives, and must also be defined for this page to be meaningful. The S combinator, or self-application combinator, behaves like this:
 Sabc = ac(bc)
This means that it takes three arguments (via Currying) and applies the application of the first to the third to the application of the second to the third.
The K combinator, or Constant-making combinator, works like this:
 Kab = a
This can be interpreted in one of two ways. 
# The first way, the naive way (which is still accurate, but not correct), is to interpret it as taking two arguments and returning the first.
# The second way, the more correct way, is more complicated: K takes one argument (x). It returns a new (unnamed, or can be called <yields(x)> for ease of understanding) combinator that, regardless of what it's applied to, returns x. This process is called "Currying".
== I combinator ==
The I combinator is defined as such:
 I = SKK
Note that S is applied to only two arguments, when it is defined as accepting three. This means that it can be defined alternatively as such:
 Ia = SKKa
Now we have it accepting three arguments. Remember that S is defined as Sxyz = xz(yz). This means that SKKx is equivalent to:
 Ka(Ka)
Where the two Ks shown above are the arguments x and y of S.
This means that, following the above-mentioned convention, this is equivalent to:
 <yields(a)> <yields(a)>
The application of a combinator that always yields x to itself. But wait! It always yields a! This means that it is equal to a! Which is what we expect Ia to equal!
== B combinator ==
B is defined as:
 B = S (KS) K
Again, we have S taking two arguments, so we can give it x to even things out:
 S (KS) K a
By reducing S, we can show that this is equal to:
 (KS)a (K a)
By eliminating the Ks, we get
 <yields(S)>a <yields(a)>
Eliminating the first yielder (the second isn't yet applied to anything), we get:
 S <yields(a)>
So now, we have S again without all its arguments. It is missing two arguments this time.
 S <yields(a)> b c
This is, following S-reduction:
 <yields(a)>c (b c)
Which after K reduction is equal to:
 a(bc)
Thus:
 Babc = a(bc)
== B[1] combinator ==
 B[1] = BBB
 BBB
 (BB)B
 (B(Babc)de)Bfgh
 C = (a(bc)(de))f(gh)
== B[2] combinator ==
 B[2] = B(BBB)B
 B(BBB)B
 B(BBB)Ba
 (BBB)(Ba)
 (BBB)(Ba)bc
 (BBB)a(bc)
 (BBB)a(bc)d
 B(Ba)(bc)d
 Ba((bc)d)e
 a(((bc)d)e)
== B[3] combinator ==
 B[3] = B(BB)B
== C combinator ==
 C = S(BBS)(KK)
 S(BBS)(KK)
 S(BBS)(KK)a
 (BBS)a((KK)a)
 (BBS)a(<yields(K)>a)
 (BBSa)(K)
 (B(Sa))(K)
 B(Sa)Kb
 (Sa)(Kb)
 (Sa)(<yields(b)>)c
 ac(<yields(b)>c)
 acb
 C a b c = a c b
== D combinator ==
 D = BB
 (BB)
 BBabc
 Ba(bc)
 Ba(bc)d
 a((bc)d)
== D[1] combinator ==
 D[1] = B(BB)
 B(BB)
 B(BB)ab
 (BB)(ab)
 BB(ab)c
 B((ab)c)
 B((ab)c)de
 ((ab)c)(de)
== D[2] combinator ==
 D[2] = BB(BB)
== E combinator ==
 E = B(BBB)
 B(BBB)
 B(BBBa)
 B(B(Ba))
 B(B(Ba))
 B(B(Babc))
 B(B(a(bc)))
 B(B(a(bc))de)
 B(a(bc)(de))
 B(a(bc)(de))fg
 a(bc)(de)(fg)
== Ê combinator ==
 Ê = B(BBB)(B(BBB))
== F combinator ==
 F = ETTET
== G combinator ==
 G = BBC
 BBC
 BBCa
 B(Ca)
 B(Cabc)
 B(acb)
 B(acb)de
 (acb)(de)
 G a b c = (a c b) (d e)
== H combinator ==
 H = BW(BC)
== J combinator ==
 J = B(BC)(W(BC(B(BBB))))
== L combinator ==
 L = CBM
 CBM
 CBMa
 BaM
 BaMb
 a(Mb)
 a(bb)
 L a b = a (b b)
== M combinator ==
 M = SII
 SII
 SIIa
 Ia(Ia)
 a(a)
 aa
 M a = a a
== M[2] combinator ==
 M[2] = BM
 BM
 BMab
 M(ab)
 (ab)(ab)
 M[2] a b = (a b) (a b)
== O combinator ==
 O = SI
 SI
 SIab
 Ib(ab)
 b(ab)
 Oab = b(ab)
== Q combinator ==
 Q = CB
 CB
 CBab
 Bba
 Bbac
 b(ac)
 Qabc = b(ac)
== Q[1] combinator ==
 Q[1] = BCB
 BCB
 BCBa
 C(Ba)
 C(Ba)bc
 (Ba)cb
 (((Ba)c)b)
 (Bacb)
 a(cb)
 Q[1]abc = a(cb)
== Q[2] combinator ==
 Q[2] = C(BCB)
 C(BCB)
 C(BCB)ab
 (BCB)ba
 (BCBba)
 (BCBbac)
 BC(b(ac))
 BC(b(ac))
 BC(b(ac))de
 B(b(ac))ed
 b(ac)(ed)
== Q[3] combinator ==
 Q[3] = BT
 BT
 BTab
 T(ab)
 T(ab)c
 c(ab)
 T a b c = c (a b)
== Q[4] combinator ==
 Q[4] = F*B
== R combinator ==
 R = BTT
 BTT
 BTTa
 T(Ta)
 T(Ta)b
 T(Tab)
 T(ba)
 T(ba)c
 c(ba)
 R a b c = c (b a)
== T combinator ==
 T = CI
 CI
 CIab
 Iba
 ba
 T a b = b a
== U combinator ==
 U = LO
 LO
 LOa
 O(aa)
 O(aa)b
 b(aa)b
 U = b (a a) b
== V combinator ==
 V = BCT
== W[1] combinator ==
 W[1] = CW
 CW
 CWab
 Wba
 baa
 W[1] b a = b a a
== Y combinator ==
 Y = SLL
 SLL
 SLLa
 La(La)
 a(La)(La)
 a(La(La))
 a(a(La)(La))
 a(a(La(La)))
And so on...
== I* combinator ==
 I* = S(SK)
 S(SK)ab
 (SK)b(ab)
 SKb(ab)
 K(ab)(b(ab))
 <yields(ab)>(b(ab))
 ab
 I* a b = a b
== W* combinator ==
 W* = BW
 BW
 BWab
 W(ab)
 W(ab)c
 (ab)cc
 abcc
 W* a b c = a b c c
== C* combinator ==
 C* = BC
 BC
 BCab
 C(ab)
 (ab)cd
 (ab)dc
 abdc
 C* a b c d = a b d c
== R* combinator ==
 R* = C*C*
 C* C*
 C* C* a b c
 C* a c b
 C* a c b d
 a c d b
 R* a b c d = a c d b
== F* combinator ==
 F* = BC*R*
 B C* R*
 B C* R* a
 C* (R* a)
 C* (R* a) b c d
 C* (R*abcd)
 C*acdb
 acbd
 F* a b c d = a c b d
 
== W combinator ==
 W = S S (S K)
 S S (S K)
 S S (S K) a
 Sa((SK)a)
 Sa((SK)a)b
 ab(((SK)a)b)
 ab(SKab)
 ab(Kb(ab))
 ab(<yields(b)>(ab))
 ab(b)
 abb
 W a b = a b b
 ab(Kb(ab))
 ab(<yields(b)>(ab))
 ab(b)
 abb
 W a b = a b b
Category:Examples