Encyclopedia > Combinator

  Article Content

Combinator

In mathematics, a combinator is a function with no free variables.

In computer science, combinators have been used as a basis for the semantics of functional programming languages.

A term of a combinator is either a constant, a variable, or an application of the form (A B), denoting the application of term A (a function of one argument) to term B. Application associates to the left in the absence of parentheses. All combinators can be defined as a composition of 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 the lambda-calculus. However, combinatorial expressions are much larger than their lambda-calculus equivalents.

A combinator of particular interest is the Y combinator, which is a fixed point combinator and can be used to implement recursion.

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)

Some special-purpose computers have been built to perform combinator calculations by graph reduction[?]. Examples include the SKIM[?] ("S-K-I machine") computer, built at Cambridge University, and the multiprocessor GRIP[?] ("Graph Reduction In Parallel") computer, built at UCL.

See also:


The original version of article was based on materical from FOLDOC, used with permission.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Bellefonte, Pennsylvania

... none of the area is covered with water. Demographics As of the census of 2000, there are 6,395 people, 2,796 households, and 1,602 families residing in the borough. ...