A combinator is a LambdaCalculus
expression that satisfies the following two conditions:
- 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.
The functions S, K and I as mentioned in EssAndKayCombinators
, are combinators.
Combinators can always be written in a form that looks like this:
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
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.
See also FunctionalProgramming