What is <cycle> in data?

Question

(I use OCaml version 4.02.3)

I defined a type self

# type self = Self of self;;
type self = Self of self 

and its instance s

# let rec s = Self s;;
val s : self = Self <cycle>

Since OCaml is a strict language, I expected defining s will fall into infinite recursion. But the interpreter said s has a value and it is Self <cycle>.

I also applied a function to s.

# let f (s: self) = 1;;
val f : self -> int = <fun> 
# f s;;
- : int = 1 

It seems s is not evaluated before the function application (like in non-strict language).

How OCaml deal with cyclic data like s? Self <cycle> is a normal form?

Answer 1

OCaml is indeed an eager language, however s is a perfectly valid and fully evaluated term that happens to contain a cycle. For instance, this code yields the expected result:

let f (Self Self x) = x
f s == s;; 

More precisely, the memory representation of constructors with at n arguments are boxed and read like this:

⋅—————————————————————————————————————————————⋅
| header | field[0] | field[1] | ⋯ | fiekd[n] |
⋅—————————————————————————————————————————————⋅

The header contains metadata whereas field[k] is an OCaml value, i.e. either an integer or a pointer. In the case of s, Self has only one argument, and thus only one field field[0]. The value of field[0] is then simply a pointer towards the start of the block. The term s is thus perfectly representable in OCaml.

Moreover, the toplevel printer is able to detect this kind of cycles and print an <cycle> to avoid falling into an infinite recursion when printing the value of s. Here, <cycle>, like <abstr> or <fun>, represents just a kind of value that the toplevel printer cannot print.

Note, however, that cyclical value will trigger infinite recursion in many situations, for instance f s = s where (=) is the structural equality and not the physical one (i.e. (==)) triggers such recursion, another example would be

let rec ones = 1 :: ones;; (* prints [1;<cycle>] *)
let twos = List.map ((+) 1) ones;; (* falls in an infinite recursion *)