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.
Contents
- 1 Definitions
- 2 I combinator
- 3 B combinator
- 4 B[1] combinator
- 5 B[2] combinator
- 6 B[3] combinator
- 7 C combinator
- 8 D combinator
- 9 D[1] combinator
- 10 D[2] combinator
- 11 E combinator
- 12 Ê combinator
- 13 F combinator
- 14 G combinator
- 15 H combinator
- 16 J combinator
- 17 L combinator
- 18 M combinator
- 19 M[2] combinator
- 20 O combinator
- 21 Q combinator
- 22 Q[1] combinator
- 23 Q[2] combinator
- 24 Q[3] combinator
- 25 Q[4] combinator
- 26 R combinator
- 27 T combinator
- 28 U combinator
- 29 V combinator
- 30 W[1] combinator
- 31 Y combinator
- 32 I* combinator
- 33 W* combinator
- 34 C* combinator
- 35 R* combinator
- 36 F* combinator
- 37 W combinator
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 toxz(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 asSKKx
)
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