sgo.to

S and K

Sam Goto

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 if-then-else 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 as B[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 as C[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 as W[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 self-application 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