1. combinator 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.
combinator | combinatory logic |
