combinatory logic (original) (raw)

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

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

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

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

Combinatory logic and lambda calculus are equivalent. However, lambda calculus is more concise than combinatory logic; an expression of size 𝒪⁢(n) in lambda calculus is equivalent to an expression of size 𝒪⁢(n2) in combinatory logic.

For example, S⁢f⁢g⁢x=f⁢x⁢(g⁢x) in combinatory logic is equivalent toS=(λ⁢f⁢(λ⁢g⁢(λ⁢x⁢((f⁢x)⁢(g⁢x))))), and K⁢x⁢y=xis equivalent to K=(λ⁢x⁢(λ⁢y⁢x)).