browse words by letter
a b c d e f g h i j k l m n o p q r s t u v w x y z
combinator


combinator


  1  definition  found 
 
  From  The  Free  On-line  Dictionary  of  Computing  (13  Mar  01)  [foldoc]: 
 
  combinator 
 
  A  function  with  no  {free  variable}s.  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 
 
  {Combinatory  logic}  is  equivalent  to  the  {lambda-calculus}  but 
  a  lambda  expression  of  size  O(n)  is  equivalent  to  a 
  combinatorial  expression  of  size  O(n^2). 
 
  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}, 
  {supercombinator}s. 
 
  (1994-12-06)