Combinatory logic/Analysis of combinators

From Esolang
Jump to navigation Jump to search

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.

  1. 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.
  2. 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
Retrieved from "https://esolangs.org/w/index.php?title=Combinatory_logic/Analysis_of_combinators&oldid=109108"