# 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`.

# 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.

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]`.