A combinator is a LambdaCalculus expression that satisfies the following two conditions:

CategoryFunctionalProgramming See also FunctionalProgramming, LambdaCalculus

- No variable name occurs free in it.
- No Lambda abstraction may occur inside a function application, i.e. something like
*(\x.x) f*is not allowed.

Y f x = x (f x)i.e. the right-hand side contains only function application and arguments that have been bound in the left-hand side. It is possible to transform every LambdaCalculus expression (that contains no free variables) into a set of combinator definitions C_1 ... C_n and a single expression containing only applications of C_1 ... C_n. The SKI calculus, as described in EssAndKayCombinators, is an existential proof: just take C_1 = S, C_2 = I and C_3 = K. But for practical implementation of a FunctionalProgramming language, a better idea is not to try to get around with a minimal set of combinators, but to find a (possibly large) set of combinators that naturally matches the lambda expression you are trying to evaluate. Such combinators can become a lot bigger than the small S, K and I combinators, therefore they are called SuperCombinators. SuperCombinators can rather easily be translated into C or assembly language. In this way, a FunctionalProgramming language can be implemented efficiently. See also very terse overview http://www.ccs.neu.edu/home/matthias/369-s04/Transcripts/abstract-machines-for-graph-reduction-transcript.html Introduced by Turner (1979) and generalized by Hughes (1982): D. A. Turner. A new implementation technique for applicative languages. Software - Practice and Experience, 9:31--49, 1979. Hughes, J. M. (1982), Super-combinators: A new implementation method for applicative languages, in `1982 ACM Symposium on LISP and Functional Programming', Pittsburgh, Pensylvania, pp. 1--10.

CategoryFunctionalProgramming See also FunctionalProgramming, LambdaCalculus

EditText of this page (last edited February 4, 2010) or FindPage with title or text search