# combinatory logic

A combinator is simply a function with no free variables. A free variable is any variable referred to in a function that is not a parameter of that function. The operation of combination is then simply the application of a combinator to its parameters. Combination is specified by simple juxtaposition of two terms, and is left-associative. Parentheses may also be present to override associativity. For example

 $fgxy=(fg)xy=((fg)x)y$

All combinators in combinatory logic can be derived from two basic combinators, $S$ and $K$. They are defined as

 $\displaystyle Sfgx$ $\displaystyle=$ $\displaystyle fx(gx)$ $\displaystyle Kxy$ $\displaystyle=$ $\displaystyle x$

Reference is sometimes made to a third basic combinator, $I$, which can be defined in terms of $S$ and $K$.

 $Ix=SKKx=x$

Combinatory logic where $I$ is considered to be derived from $S$ and $K$ is sometimes known as pure combinatory logic.

For example, $Sfgx=fx(gx)$ in combinatory logic is equivalent to $S=(\lambda f(\lambda g(\lambda x((fx)(gx)))))$, and $Kxy=x$ is equivalent to $K=(\lambda x(\lambda yx))$.

 Title combinatory logic Canonical name CombinatoryLogic Date of creation 2013-03-22 12:32:29 Last modified on 2013-03-22 12:32:29 Owner Logan (6) Last modified by Logan (6) Numerical id 5 Author Logan (6) Entry type Definition Classification msc 03B40 Related topic LambdaCalculus Related topic Substitutability Defines combinator Defines combination Defines free variable Defines pure combinatory logic