combinator

combinator

   <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)