Home

combinatory

Combinatory, in a mathematical and logical context, refers to the study and use of combinators—abstract objects that represent patterns of function application. The term is most closely associated with combinatory logic, a formalism developed to eliminate the need for bound variables in mathematical expressions of computation. The development is traditionally attributed to Moses Schönfinkel and was later extended by Haskell Curry, whose name is often attached to the Curry–Howard correspondence in logic.

In combinatory logic, a combinator is a higher-order function with no free variables. Combinators can be applied

Combinatory logic is closely related to lambda calculus and is known to be expressively equivalent to it,

to
arguments,
and
complex
computations
are
built
entirely
from
the
interaction
of
a
small
set
of
primitive
combinators.
The
most
famous
are
the
K
and
S
combinators.
The
K
combinator
satisfies
K
x
y
=
x,
effectively
returning
the
first
argument.
The
S
combinator
satisfies
S
f
g
x
=
f
x
(g
x),
enabling
function
application
and
composition.
With
these
two,
and
sometimes
the
identity
combinator
I,
which
is
I
x
=
x
and
can
be
defined
as
SKK,
a
wide
range
of
computable
operations
can
be
constructed.
Other
commonly
used
combinators
include
B
(composition),
C
(the
flip),
and
W
(duplication).
offering
a
variable-free
alternative
form
of
computation.
It
has
influenced
the
design
of
functional
programming
languages
and
the
theory
of
program
semantics,
and
it
underpins
various
formal
systems
used
in
logic,
type
theory,
and
the
study
of
computation.