SKI Combinator Calculus

• I x → x

  • Identity function

• K x y → x

  • Constant functions

• S x y z → (x z) (y z)

  • Generalized function application

• Loop

  • (S I I) (S I I)
  • (S I I) (S I I) → (I (S I I)) (I (S I I)) →(S I I) (I (S I I)) → (S I I) (S I I)

• Recursion

  • x = S (K f) (S I I)
  • S I I x → * x x = S (K f) (S I I) x → ((K f) x) ((S I I) x) → * f (x x) → * f (f (x x))

• Consider a function equation of one variable: $fx=E$

  • If we apply function $f$ to argument $x$, the result is $E$

• We want a combinator $A(E,x)$ that implements $f$

  • Therefore $A(E,x)x=E$
  • And $A(E,x)$ doesn’t use $x$
  • We say we abstract $E$ with respect to $x$
  • $A(x,x)=I$
  • $A(E,x)=KE$ if $x$ does not appear in $E$
  • $A(E_1{E}_2,x)=SA(E_1,x)A(E_2,x)$

• Note $A(...)$ is not a combinator

  • It is a (recursively defined) mapping from expressions with variables to combinators