# One-point bases for λ-calculus

## The Iota combinator and some alternatives

I first read about the Iota combinator years ago and was intrigued by its existence. Recently I wondered what some alternative one-point bases look like and whether Iota is the smallest such combinator. Here is what I found online, in papers, and from writing a small tool that searches for such bases.

Indeed, the tool *found some that are smaller than Iota*. I’m sure they have been found before, but it seems this information could be more discoverable. So here is a buffet of one-point bases; after a quick, informal recap/definition of what a (one-point) basis is.

**Disclaimer:** This is *not *a tutorial or introduction to λ-calculus or combinatory logic. Yet, maybe this still sparks the curiosity of less experienced readers, so further reading is linked throughout!

# Basis

A *basis *for λ-calculus or combinatory logic is a set of terms that, when combined using nothing but function application, can generate (terms equal to) any arbitrary λ-term or combinator.

**Example:** Basis {S, K, I} where

I = λx -> x

K = λx -> λy -> x

S = λx -> λy -> λz -> x z (y z)or equivalentlyI x = x

K x y = x

S x y z = x z (y z)

For instance, the λ-term `λf -> λx -> f (f x)`

(a Church encoded number 2) is equivalent to `S (S (K S) K) I`

, which one can confirm with pen and paper.

Alternatively, the combinator C with behavior `C x y z = x z y`

can be reconstructed as `S (S (K (S (K S) K)) S) (K K)`

.

It is worth noting that even {S, K} is a basis: One can reconstruct `I = S K K`

. The second `K`

can in fact be any arbitrary term for this to work.

**Counter-example:** Set {K, I} with K and I defined as above. The two terms lack the ability to *duplicate *terms (like combinator S does via argument z). Thus, λ-term `λx -> x x`

(also known as the M combinator) cannot be reconstructed using any combination of Ks and Is.

# One-point bases

A *one-point basis* is a basis with just one element. There exist infinitely many. In the following we consider a basis {X}, but for various definitions of X.

## The Iota combinator

Consider the Iota combinator `X = λx -> x "S" "K"`

with S and K as defined above. Note that if {X} is our basis, S and K should be defined in terms of X, instead of the other way around! “S” and “K” above are hence meant as compact notation for the full definition:

`X = λx -> x (λx -> λy -> λz -> x z (y z)) (λx -> λy -> x)`

-------------S--------------- -------K-------

{X} is a basis since {S, K, I} is and we can reconstruct `I = X X`

, `K = X (X I)`

and `S = X K`

.

## Similar alternatives

While Iota is rather well-known and quite elegant, there are several similar combinators that form one-point bases like

`X = λx -> x "K" "S"`

, since`S = X X X`

and`K = X (S X X)`

`X = λx -> x "K" "S" "K"`

, since`K = X X X`

and`S = X (X X)`

## More compact alternatives

The above one-point bases are quite lengthy λ-terms (when fully expanded), so I wrote a tool to search for shorter alternatives and found:

`X = λx -> λy -> λz -> x (λx -> λy -> x) z (y z)`

-------------S-ish-- --------

------K------

As indicated, note how this is similar to the S combinator, but with an additional K in the body. Not sure if/where this was mentioned in literature before, but I am inclined to call this combinator “Ioter” since “Iota” already means “small amount”, and this combinator is small*er.*

Anyways, while Ioter is small, it unfortunately requires rather lengthy terms to reconstruct well-known combinators:

`I = X (X (X (X (X X X)))) X`

K = X (X (X (X X X))) X

S = X (K (K X)) K

The construction for S is likely not the shortest (after expanding the Ks, it uses 23 Xs), but I believe no definition using less than 15 Xs exists.

EDIT: Indeed, John Tromp found S = (X(X(X X(X(X(X X)))))) (X(X(X X) X) X) X of size 16. Thank you!

A very similar, slightly longer (but still shorter than Iota) alternative is:

`X = λx -> λy -> λz -> x (λx -> λy -> λz -> y) z (y z)`

-------------S-ish-- --------

--------K K--------

One can restore S, K and I from this basis slightly faster:

`I = X X`

K = X I I

S = X (K (K X)) K

# Conclusion

As mentioned at the beginning, the point of this post is mainly to have a quick overview with examples in one spot. I show the Iota combinator as well as similar and smaller alternatives that I was previously unaware of. They have drawbacks in restoring SKI combinators, but I’m still intrigued; anyways, this is not supposed to be a ranking and purely for reference (see title image) or entertainment.