I have an OCaml function for finding fixed points:
>> let rec fix f x =
let x' = f x in
if x = x' then x else fix f x';;
(system message) val fix : ('a -> 'a) -> 'a -> 'a = <fun>
The question is, I don't understand how it works when I type:
>> let cubed x = x*x*x;;
(system message) val cubed : int -> int = <fun>
>> fix cubed 2;;
(system message) - : int = 0
In my understanding, fix cubed 2 will go into an infinite loop of fix cubed 2*2*2, fix cubed (2*2*2)*(2*2*2)*(2*2*2) and so on. How does this function correctly finds the fixed point 0?
More or less by accident.
What is happening is that you are using cubed on a power of two, which results in a larger power of two. After a few rounds of this the result will be large enough to overflow and be truncated - and large powers of two will truncate to zero, which happens to be a fixpoint of this function.
To be completely clear, OCaml will not do any kind of sophisticated search or trickery, fix is just a loop which happens to terminate with a useful answer in this case.
You can use #trace in the toplevel to see it happening:
# #trace cubed;;
cubed is now traced.
# fix cubed 2
;;
cubed <-- 2
cubed --> 8
cubed <-- 8
cubed --> 512
cubed <-- 512
cubed --> 134217728
cubed <-- 134217728
cubed --> 0
cubed <-- 0
cubed --> 0
- : int = 0