See Part One.
Here we continue discussing the S and K combinators. For a review, we summaraize the main results from Part One:
The S and K combinators are:
s[x][y][z] = x[z][y[z]]
k[x][y] = x
The I combinator, or "identity", reads:
i = s[k][k]
such that:
i[a] = a
One way to precalculate the set of integers is:
0 = s[k] [s][k]
1 = p[s[k]] [s][k]
2 = p[p[s[k]]] [s][k]
3 = p[p[p[s[k]]]] [s][k]
4 = p[p[p[p[s[k]]]]] [s][k]
5 = p[p[p[p[p[s[k]]]]]] [s][k]
...
... where p is the "increment" operator:
p = s[s[k[s]][k]]
Evaluating each of the above gives the simplified representation of each integer:
0 = k
1 = s[k]
2 = s[s[k]]
3 = s[s[s[k]]]
4 = s[s[s[s[k]]]]
5 = s[s[s[s[s[k]]]]]
...
Arithmetic expressions can be performed on integers using the following structure:
a {operator} b = [operator][pre a][pre b][s][k]
So far, we have stated three operators:
addition: s[k[s]][s[k[s[k[s]]]][s[k[k]]]]
multiplication: s[k[s]][k]
exponent: s[k[s[s[k][k]]]][k]
In case you've wondered if we can still use S and K combinators with fewer bracket symbols, you would be correct. Like training wheels, square brackets help the novice (and the computer parser) to read expressions without ambiguity. Once the eye is trained however, we can afford to use a more efficient notation. (The computer program we're using still needs all of the brackets). The streamlining amounts to ignoring the brackets when they aren't needed. For instance:
a[b] <--> ab
w[x][[y][z]] <--> wx(yz)
The combinators themselves now appear as:
sxkz = xz(yz)
kxy = x
We can now go back and rewrite everything in tighter notation. Skipping to the good stuff:
identity: skk = i
increment: s(s(ks)k)
addition: s(ks)(s(k(sks))i)
multiplication: s(ks)k
exponent: s(k(si))k
Given the object x, how do we calculate xx? (Remember we're using fancier notation now, so xx also means x[x].) The answer is the self-apply operator:
self-apply = sii
Testing this is rather trivial:
siix = ix(ix) = x(ix) = x(x) = xx
In the full square bracket notation, the above starts and finishes as (skipping the middle steps):
s[s[k][k]][s[k][k]][x] = x[x]
As with any programming tool, it's not that difficult to create an infinite loop. In the context of S and K combinators, an infinite loop could correspond to an expression that returns to itself after two or more steps. Following is such an expression:
infinite-loop = sii(sii)
Unrolling the expression, we see it repeats itself on the third step:
sii(sii) = i(sii)(i(sii)) = sii(i(sii)) = sii(sii)
In the full square bracket notation, the above goes as:
s[s[k][k]][s[k][k]][s[s[k][k]][s[k][k]]] --> (itself)
Given the compound object xy, how do we calculate yx? The answer is the swap operator:
swap = s(k(si))(s(kk)i)
Testing the above, we see it takes a few steps, but it does the job:
s(k(si))(s(kk)i)xy
k(si)x(s(kk)ix)y
si(kkx(ix))y
si(kx)y
iy(kxy)
yx
In the full square bracket notation, the above starts and finishes as (skipping the middle steps):
s[k[s[s[k][k]]]][s[k[k]][s[k][k]]][x][y] = y[x]
Consider the curious combination s(kx)(sii) for some unknown x. Let's allow this structure to act on y:
s(kx)(sii)y
kxy(siiy)
x(iy(iy))
x(yy)
In the full square bracket notation, the above starts and finishes as (skipping the middle steps):
s[k[x]][s[s[k][k]][s[k][k]]][y] = x[y[y]]
The above result is rather interesting - we get x applied to two copies of y. For definiteness, let us make the association r = s(kx)(sii). What happens, then, if we apply r to itself? Let's see:
r(r)
s(kx)(sii)(s(kx)(sii))
kx(s(kx)(sii))((sii)(s(kx)(sii)))
x((sii)(s(kx)(sii)))
x(sii(s(kx)(sii)))
x(i(s(kx)(sii))(i(s(kx)(sii))))
x(s(kx)(sii)(s(kx)(sii)))
x(r(r))
In the final step, you can see we're back at the first step with x applied on the left. This kickstarts a recursive endless loop as such, unless if x contains some way to terminate the loop. One way or the other, we've demonstrated that the SK calculus supports recursion.