Fixed-point Combinator - Implementing Fixed-point Combinators

Implementing Fixed-point Combinators

In a language that supports lazy evaluation, like in Haskell, it is possible to define a fixed-point combinator using the defining equation of the fixed-point combinator. A programming language of this kind effectively solves the fixed-point combinator equation by means of its own (lazy) recursion mechanism. This implementation of a fixed-point combinator in Haskell is sometimes referred to as defining the Y combinator in Haskell. This is incorrect because the actual Y combinator is rejected by the Haskell type checker (but see the following section for a small modification of Y using a recursive type which works). The listing below shows the implementation of a fixed-point combinator in Haskell that exploits Haskell's ability to solve the fixed-point combinator equation. This fixed-point combinator is traditionally called fix in Haskell. Observe that fix is a polymorphic fixed-point combinator (c.f. the discussion in previous section on System F); its type is only shown for clarity—it can be inferred in Haskell. The definition is followed by some usage examples.

fix :: (a -> a) -> a fix f = f (fix f) fix (const 9) -- const is a function that returns its first parameter and ignores the second; -- this evaluates to 9 factabs fact 0 = 1 -- factabs is F from our lambda calculus example factabs fact x = x * fact (x-1) (fix factabs) 5 -- evaluates to 120

In the example above, the application of fix does not loop infinitely, because of lazy evaluation; e.g., in the expansion of fix (const 9) as (const 9)(fix f), the subexpression fix f is not evaluated. In contrast, the definition of fix from Haskell loops forever when applied in a strict programming language, because the argument to f is expanded beforehand, yielding an infinite call sequence f (f ... (fix f) ... )), which causes a stack overflow in most implementations.

In a strict language like OCaml, we can avoid the infinite recursion problem by forcing the use of a closure. The strict version of fix shall have the type ∀a.∀b.((a→b)→(a→b))→(a→b). In other words, it works only on a function which itself takes and returns a function. For example, the following OCaml code implements a strict version of fix:

let rec fix f x = f (fix f) x (* note the extra x *) let factabs fact = function (* factabs now has extra level of lambda abstraction *) 0 -> 1 | x -> x * fact (x-1) let _ = (fix factabs) 5 (* evaluates to "120" *)

The same idea can be used to implement a (monomorphic) fixed combinator in strict languages that support inner classes inside methods (called local inner classes in Java), which are used as 'poor man's closures' in this case. Even when such classes may be anonymous, as in the case of Java, the syntax is still cumbersome. Java code. Function objects, e.g. in C++, simplify the calling syntax, but they still have to be generated, preferably using a helper function such as boost::bind. C++ code.