S and K
Context
Moses SchÃ¶nfinkel's inspiration came from the recently discovered result that all of the known operators in propositional logic (~a
, a && b
, a  b
, a => b
and a <=> b
) could be reduced to / derived from a single operator: nand
.
Notation
Notation: a tree (xy)
can be thought as a function x
applied to an argument y
. When evaluated, the tree returns a value. The function, argument or values are either combinators or binary trees.
S and K
K
The k
combinator is: k[x][y] = x
S
The s
and k
combinators: s[x][y][z] = x[z][y[z]]
and
Example
For example, let's say we start from s[k][s][k]
. This evaluates to k[k][s[k]]
by applying the s
rule with x = k
, y = s
and z = k
. This then evalutes to k
as we apply the k
rule with x = k
and y = s[k]
. Since there is no more rule to apply, it halts.
Boolean logic
We pick very specific definitions of true
and false
, such that we can construct an
ifthenelse structure: when true
follow the then
, when false
follow the else
.
And from that, we define other boolean combinators to perform the task that we want them to perform.
True
We define T[x][y]
= T = K
, which because K[x][y]
= x
, and,
False
We define F[x][y]
= F[x][y]
= S[K][x][y]
, which is K[y][x[y]]
= y
. With that, then,
NOT
We define NOT[x]
as S[S[I][K[F]]][K[T]][x]
, which leads to S[I][K[F]][x][K[T][x]]
= I[x][K[F][x]][T]
= x[F][T]
.
For example, NOT[T]
= T[F][T]
= F
, NOT[F]
= F[F][T]
= T
:
OR
OR[x][y]
= S[I][K[T]][x][y]
= I[x][K[T][x]][y]
= x[T][y]
For example: OR[T][T]
= T[T][T]
= T
, OR[T][F]
= T[T][F]
= T
, OR[F][T]
= F[T][T]
= T
and OR[F][F]
= F[F][F]
= F
.
AND
AND[x][y]
= S[S][K[K[F]]][x][y]
= S[x][K[K[F]][x]][y]
= x[y][K[K[F]][x][y]]
= x[y][K[F][y]]
= x[y][F]
, e.g. AND[T][T]
= T[T][F]
= T
, AND[T][F]
= T[F][F]
= F
, AND[F][T]
= F[T][F]
= F
and AND[F][F]
= F[F][F]
= F
.
NAND
You can combine combinators (duh) to form composite constructions, for example a NAND[x][y]
= NOT[AND[x][y]]
= AND[x][y][F][T]
= x[y][F][F][T]
.
For example, NAND[T][T]
= T[T][F][F][T]
= T[F][T]
= F
, NAND[F][T]
= F[T][F][F][T]
= F[F][T]
= T
, NAND[T][F]
= T[F][F][F][T]
= F[F][T]
= T
and NAND[F][F]
= F[F][F][F][T]
= F[F][T]
= T
.
Control
Identity
I[x]
: S[K][x][y]
always evaluates to y
in two steps (S[K][x][y]
= K[y][x[z]]
= y
). S[K][x][y]
and I[y]
are functionally equivalent because they always yield the same result when applied to any y
.
Second
N[x][y]
is defined as N = K[I]
and results in y
, since N[x][y]
= K[i][x][y]
= I[y]
= y
, which complements K
(which selects the first parameter, rather than the second).
Functions
Composition
B[f][g][x]
=f[g[x]]
performs a composition of functions (i.e.f * g (x)
=f(g(x))
), and is defined asB[f][g][x]
=S[K[S]][K][f][g][x]
=K[S][f][K[f]][g][x]
=S[K[f]][g][x]
=K[f][x][g[x]]
=f[g[x]]
.
Currying
C[f][g][x]
=f[x][g]
, defined asC[f][g][x]
=S[B[B][S]][K[K]][f][g][x]
=B[B][S][f][K[K][f]][g][x]
=B[S[f]][K[K][f]][g][x]
=S[f][K[K][f][g]][x]
=f[x][K[K][f][g][x]]
=f[x][K[g][x]]
=f[x][g]
W
W[x][f]
=f[x]
takes the second parameter and applies it to the first, which is constructed asW[x][f]
=C[I][x][f]
=I[f][x]
=f[x]
.
V
V[x][y][z]
= z[x][y]
takes the third argument, applies it to the first argument and then to the second. It is is defined as B[C][W][x][y][z]
= C[W[x]][y][z]
= W[x][z][y]
= z[x][y]
.
Data Structures
Pair
Suppose we want to describe ordered pairs, say (x, y)
, we can define a combinator Pair[x][y]
such that First[Pair[x][y]]
= x
and Second[Pair[x][y]]
= y
. If we define Pair[x][y][z]
= V[x][y][z]
= z[x][y]
and First
= W[T]
and Second
= W[F]
.
For example, First[Pair[x][y]]
= W[T][Pair[x][y]]
= Pair[x][y][T]
= T[x][y]
= x
and Second[Pair[x][y]]
= W[F][Pair[x][y]]
= Pair[x][y][F]
= F[x][y]
= y
.
Natural Numbers
Zero
We want to make the function Zero[x]
return T
when x
= 0
and F
otherwise, so we define Zero[x]
= First[x]
. Since we want Zero[0]
= First[0]
= W[T][0]
= 0[T]
. If we define 0
= I
, then Zero[0]
= 0[T]
= I[T]
= T
. So, we define 0
= I
.
1, 2, 3, ...
With the representation of 0
in place, we can define 1
as the pair Pair[F][0]
, 2
= Pair[F][1]
, 3
= Pair[F][2]
, and so on.
We can then define Next[n]
= Pair[false][n]
, which can give us our natural numbers 0
, Next[0]
, Next[Next[0]]
, Next[Next[Next[0]]]
, etc.
The Previous[n]
= Second[n]
, for example Previous[2]
= Second[2]
= Second[Pair[F][1]]
= 1
.
Recursion
Arithmetic
Apply
We'd like to derive a combinator that can compute the application of a function n
times, e.g. Apply[0][f][x]
= x
, Apply[1][f][x]
= f(x)
, Apply[2][f][x]
= f[f[x]]
, and so on.
Add
For example, adding two numbers, m
and n
is the same as applying the function Next
m
times to n
. That is, Add[m][n]
= Apply[m][Next][n]
= Next[Next[Next[...[Next[n]]]]]
(embeds m
times).
We define Apply[n][f][x]
as Zero[n][x][f[Apply[Previous[n]][f][x]]]
, which in practice can read as:
Apply(n, f, x) {
if (Zero(n) == T) {
return x;
} else {
return f(Apply(Previous(n), f, x));
}
}
Sub
Much like Add, we can define Sub as Sub[m][n] = Apply[m][Previous][n]
.
Fib
Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
NextPair[p] = Pair[Second[p]][Add[First[p]][Second[p]]]
. For example, NextPair[Pair[0][1]]
= Pair[Second[Pair[0][1]]][Add[First[Pair[0][1]]][Second[Pair[0][1]]]] = Pair[1][Add[0][1]]
= Pair[1][1]
.
Iota

i[x]
=x[S][K]

I[x]
=i[i][x]
=i[S][K][x]
=S[S][K][K][x]
=S[K][K[K]][x]
=K[x][K[K][x]]
=x
. 
K[x][y]
=i[i[I]][x][y]
=i[i[i[i]]][x][y]
=i[i[i[S][K]]][x][y]
=i[i[S][S][K][K]]][x][y]
=i[S[S][K][S][K][K]][x][y]
=S[S][K][S][K][K][S][K][x][y]
=S[S][K[S]][K][K][S][K][x][y]
=S[K][K[S][K]][S][K][x][y]
=S[K][S][S][K][x][y]
=K[S][S[S]][K][x][y]
=S[K][S[S][K]][x][y]
=K[x][S[S][K][y]]
=x
. 
S[x][y][z]
=i[K][x][y][z]
=K[S][K][x][y][z]
=S[x][y][z]
=x[z][y[z]]

i[x] => x[[a][b][c] => a[c][b[c]]]][[d][e] => d]

i[i][x] => i[[a][b][c] => a[c][b[c]]]][[d][e] => d][x]
=([a][b][c] => a[c][b[c]])[[a][b][c] => a[c][b[c]]]][[d][e] => d]][[d][e] => d][x]
=([a][b][c] => a[c][b[c]])[[d][e] => d][([d][e] => d)[[d][e] => d]][x]
=([d][e] => d)[x][([d][e] => d)[[d][e] => d][x]]
=x
.
Alternatively, j
would also work:
j[x] = x[K][S]
S
=j[j][j]
=j[K][S][j]
=K[K][S][S][j]
=K[S][j]
=S
K
=j[j[j][j][j][j]]
=j[S[j][j]]
=S[j][j][K][S]
=j[K][j[K]][S]
=K[K][S][j[K]][S]
=K[j[K]][S]
=j[K]
=K[K][S]
=K
;
Another option is W[x] = x[K][S][K]
with K = W[W][W]
and S = W[W[W]]
.
K
=W[W][W]
=W[K][S][K][W]
=K[K][S][K][S][K][W]
=K[K][S][K][W]
=K[K][W]
=K
S
=W[W[W]]
=W[W[K][S][K]]
=W[K[K][S][K][S][K]]
=K[K][S][K][S][K][K][S][K]
=K[K][S][K][K][S][K]
=K[K][K][S][K]
=K[S][K]
=S
.
If we define m
as:

m[x][y][z]
=x[z][y[K[z]]]

K = m[m[m]][ m[m[m]][m][m] [m][m][m]]
=m[m[m]][ m[m][m][m[K[m]]] [m][m][m]]
=m[m[m]][ m[m[K[m]]][m[K[m[K[m]]]]] [m][m][m]]

S = m (m (m m (m m (m m))(m (m (m m (m m)))))) m m
Unused?
Self Application
M[x]
(sometimes also called u
, e.g. here) is a combinator that takes an argument and applies that argument to itself: M[x]
= S[I][I][x]
= I[x][I[x]]
= x[x]
An interesting property of the M
combinator is that its selfapplication is irreducible: u[u]
= s[i][i][s[i][i]]
= i[s[i][i]][i[s[i][i]]]
= s[i][i][s[i][i]]
= u[u]
.
Reversal
R[x][y]
= y[x]
can be constructed as R[x][y]
= S[K[S[I]]][K][x][y]
= K[S[I]][x][K[x]][y]
= S[I][K[x]][y]
= I[y][K[x][y]]
= y[K[x][y]]
= y[x]
.
References
 Combinatory Fibonacci
 TODO: look at Iota and Jot which can derive S and K
 SKI Calculus
 Moses SchÃ¶nfinkel
 Combinators and the History of Computation
 Combinators: A 100Year Celebration