Fixed point combinator
A
fixed point combinator is a function which computes
fixed points of other functions. A 'fixed point' of a function is a value left 'fixed' by that function; for example, 0 and 1 are fixed points of the squaring function.
In certain formalizations of mathematics, such as the lambda calculus and combinatorial calculus, every function has a fixed point. In these formalizations, it is possible to produce a function, often denoted Y, which computes a fixed point of any function it is given. Since a fixed point x of a function f is a value that has the property f(x) = x, a fixed point combinator Y is a function with the property that f(Y(f)) = Y(f) for all functions f.
One well-known fixed point combinator, discovered by Haskell B. Curry, is
- Y = λf.(λx.(f (x x)) λx.(f (x x)))
Another common fixed point combinator is the Turing fixed-point combinator (named for its discoverer
Alan Turing):
- Θ = (λx.λy.(y (x x y)) λx.λy.(y (x x y)))
This combinator is of interest because a variation of it can be used with applicative-order reduction:
- Θ_{v} = λh.(λx.(h λy.(y (x x y))) λx.(h λy.(y (x x y))))
Fixed point combinators are not especially rare. Here is one constructed by Jan Willem Klop:
- Y_{k} = (L L L L L L L L L L L L L L L L L L L L L L L L L L L L)
where
- L = λabcdefghijklmnopqstuvwxyzr.(r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))
See also:
combinator,
combinatory logic,
lambda calculus.