(Copy-pasting Wikipedia) A fixed-point combinator (or fixpoint combinator), is a higher-order function that returns some fixed point (a value that is mapped to itself) of its argument function, if one exists.

It has the following type(given in Haskell)

fix :: (a -> a) -> a

We'll assume it's defined somewhere already and move on for now.

Now, a classic example for showing it's usage is a factorial function(or any recursive function would work).

Generally it would be written recursively like this:

fact:: Integer -> Integer
fact n = if n == 0 then 1 else n * (fact (n - 1))

But, let's assume we don't have recursion in our language. So, let's try to write it a bit differently.

fact':: (Integer -> Integer) -> Integer -> Integer
fact' f n = if n == 0 then 1 else n * (f (n - 1))

Now, using fix, we could define our fact to be something like this

-- fact:: Integer -> Integer
-- fix:: (a -> a) -> a
-- fact' :: (Integer -> Integer) -> Integer -> Integer
-- which can be rewritten as
-- fact' :: (Integer -> Integer) -> (Integer -> Integer)
--
-- in fix fact', a is substituted to be (Integer -> Integer)
-- so fix fact:: Integer -> Integer
fact n = fix fact'

But fix has been a blackbox for us till now. Let's see how we can define it.

fix:: (a -> a) -> a
fix f = <t>

Now what could go in for t expression there? If we think purely in terms of types, we have a function as parameter f: a-> a and we need result to be of type a. So, it's probably going to be achieved by applying f.

Now, what is something of type a we can apply to f: a -> a. We really only know of one thing whose result is type a i.e fix. So, it's just going to be

fix f = f (fix f)

andd, that's the definition of fix, the fixed-point combinator.

NOTE: Since, fix is defined recursively, it has to be a primitive provided by host language(language in which the interpreter is written), since we mentioned before we didn't support recursion.

NOTE: Also this definition of fix works in a call by name language(lazy language) like Haskell, but will overflow the stack in something like OCaml.

Let's try defining it in OCaml

Why do we need to do it differently in OCaml?

Issue arises due to strictness. If you translate the program to OCaml, it'll be like this:

let rec fix f = f (fix f)

The issue with this is, the moment you call fix with some f, it'll first try to evaluate the fix f in RHS, which just keeps on going forever. Haskell doesn't suffer from the issue because it only actually evaluates it when it's needed.

ghci> fix f = f (fix f)
ghci> x y = 1:y
ghci> infinite1s = fix x
ghci> take 10 infinite1s
[1,1,1,1,1,1,1,1,1,1]

Using fix, we can define x=1:x like above. We basically took x::[Integer] -> [Integer] and converted it to [Integer] with fix.

You can't do this in OCaml directly. This is of the form a -> a where a=[Integer]. This form of fix with the signature (a -> a) -> a is possible in Haskell because a whatever it is, is lazily evaluated. It's actually a thunk which evaluates to a. In OCaml, a is always an evaluated value, so you will end up needing some thunking mechanism to define fix.

We need to get laziness to do this in OCaml. So, we'll use partially evaluated functions to get a definition of fix. We define it as follows:

val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b
let rec fix f x = f (fix f) x

(if you think about it, is sort of similar to (a -> a)-> a in Haskell, but a maps to 'a -> 'b here.)

This doesn't blow up because the usage of fix in RHS is also partial, it doesn't get fully evaluated until we actually use it. We end up creating lazy semantics of our own here.

utop # let rec fix f x = f (fix f) x;;
val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
─( 16:05:30 )─< command 7 >──────────────────────────────────────────────────────────────────────────────────────────────{ counter: 0 }─
utop # let fact f n = if n=0 then 1 else n * (f (n - 1));;
val fact : (int -> int) -> int -> int = <fun>
─( 16:05:34 )─< command 8 >──────────────────────────────────────────────────────────────────────────────────────────────{ counter: 0 }─
utop # (fix fact) 10;;
- : int = 3628800

That's pretty much it.

This sort of clicked properly for me when I was watching this excellent lecture by Robert Harper, so I thought I'd write it out as a small blog