Hyper Dictionary

English Dictionary Computer Dictionary Video Dictionary Thesaurus Dream Dictionary Medical Dictionary

Search Dictionary:  


Matching Terms:  combinatorial, combinatory, combinatory logic

Computing Dictionary

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.