SKI combinators

The SKI calculus is a tiny programming language with three built-in symbols — S, K, and I — and a single operation: function application. It is equivalent in power to the untyped lambda calculus, but has no variables. Anything you can compute with lambdas can also be expressed by combining S, K, and I.

The three rules are:

• I x reduces to x.
• K x y reduces to x (drop the second argument).
• S f g x reduces to (f x) (g x) (apply both f and g to x, then apply the first result to the second).

That is the entire semantics. There is no notion of binding, scope, or substitution beyond textual rewriting.

Minimal example

The identity combinator does what it says — given anything, return it unchanged. Press step to apply rules one at a time:

ski reduction

resetsteprun to normal form

1. 0I x

next rule: I x → x

K selects the first argument and discards the rest. Watch the second argument disappear:

ski reduction

resetsteprun to normal form

1. 0K a b

next rule: K x y → x

A less obvious reduction

A classic identity in SKI: S K K x reduces to x. In other words, S K K is the identity combinator, expressed without using I.

ski reduction

resetsteprun to normal form

1. 0S K K x

next rule: S f g x → (f x) (g x)

The first step rewrites the root with the S rule. The next step applies K to the leftmost subterm. Walk through it carefully — every step is purely mechanical, no insight required.

Practical example

Compose two functions, written here as opaque variables f and g. The SKI encoding of "compose" is S (K S) K. Applying it to f, g, and an argument x should reduce to f (g x):

ski reduction

resetsteprun to normal form

1. 0S (K S) K f g x

next rule: S f g x → (f x) (g x)

Press run to normal form. The result f (g x) is exactly function composition — no lambdas, no environment, no names.

Why this matters

• The SKI calculus shows that variables are not fundamental — they are convenient sugar over a smaller core.
• Combinatory logic is the bridge from lambda calculus to point-free style in real languages (Haskell's (.) and flip, Clojure's comp and juxt).
• It is also the simplest setting in which to see what "reduction" really means: rewrite a redex by the rule for its head, repeat until no rules apply.

Try it in Clojure — SKI as combinators

Encode S, K, I as plain Clojure functions and watch the reductions happen by themselves at runtime.

comp, partial, juxt, and complement in clojure.core are spiritually combinators in this exact sense — short, named, variable-free function-builders. SKI is the theoretical floor of that style.

Real-world: where combinator thinking ships

The takeaway: every time you write (comp f g) instead of (fn [x] (f (g x))), you're moving one step closer to the SKI worldview — code as a tree of operators rather than a tree of named bindings.

Exercise

Define T = S (K (S I)) K. Try reducing T a b and observe what it computes. Hint: it is also a well-known combinator.

ski reduction

resetsteprun to normal form

1. 0S (K (S I)) K a b

next rule: S f g x → (f x) (g x)