A fixed point combinator (or fixedpoint operator) is a higherorder function that computes a fixed point of other functions. A fixed point of a function f is a value x such that f(x) = x. For example, 0 and 1 are fixed points of the function f(x) = x^{2}, because 0^{2} = 0 and 1^{2} = 1. Whereas a fixedpoint of a firstorder function (a function on "simple" values such as integers) is a firstorder value, a fixed point of a higherorder function f is another function p such that f(p) = p. A fixed point combinator, then, is a function g which produces such a fixed point p for any function f:
or, alternately:
Because fixedpoint combinators are higherorder functions, their history is intimately related to the development of lambda calculus. One wellknown fixed point combinator in the untyped lambda calculus is Haskell Curry's Y = λf·(λx·f (x x)) (λx·f (x x)). The name of this combinator is incorrectly used sometimes to refer to any fixed point combinator. The untyped lambda calculus however, contains an infinity of fixed point combinators. Fixed point combinators do not necessarily exist in more restrictive models of computation. For instance, they do not exist in simply typed lambda calculus.
In programming languages that support function literals, fixed point combinators allow the definition and use of anonymous recursive functions, i.e. without having to bind such functions to identifiers. In this setting, the use of fixed point combinators is sometimes called anonymous recursion.^{[1]}^{[2]}
Contents
How it works
Ignoring for now the question whether fixed point combinators even exist (to be addressed in the next section), we illustrate how a function satisfying the fixed point combinator equation works. To easily trace the computation steps, we choose untyped lambda calculus as our programming language. The (computational) equality from the equation that defines a fixed point combinator corresponds to beta reduction in lambda calculus.
Full article ▸
