# combinator

Computing Dictionary

### combinator definition

theory
A function with no free variables. A term is either a constant, a variable or of the form A B denoting the application of term A (a function of one argument) to term B. Juxtaposition associates to the left in the absence of parentheses. All combinators can be defined from two basic combinators - S and K. These two and a third, I, are defined thus:
S f g x = f x (g x) K x y = x I x = x = S K K x
There is a simple translation between combinatory logic and lambda-calculus. The size of equivalent expressions in the two languages are of the same order.
Other combinators were added by David Turner in 1979 when he used combinators to implement SASL:
B f g x = f (g x) C f g x = f x g S' c f g x = c (f x) (g x) B* c f g x = c (f (g x)) C' c f g x = c (f x) g
See fixed point combinator, curried function, supercombinators.
(2002-11-03)

The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
Explore Dictionary.com
Previous Definition: combinative
Next Definition: combinatorial
Words Near: combinator
More from Thesaurus.com
Synonyms and Antonyms for combinator
More from Reference.com
Search for articles containing combinator
More from Dictionary.com Translator
Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Related Searches