[Caml-list] Cyclic data structures: internal representation

[Jean-Baptiste Jeannin <jeannin@cs.cornell.edu>]

Good morning,

One can create cyclic data structures in OCaml, using the keyword let rec. For example:

  # let rec l0 = 1 :: 2 :: l0;;
  var l0 : int list =
    [1; 2; 1; 2; 1; 2; 1; 2; 1; 2; 1; 2; 1; 2; 1; 2; 1; 2; ...]

I am wondering what the internal representation (in the AST) of such a data structure is. It could be a cyclic data structure on the AST itself, but I doubt it because it would make it difficult to manipulate. Another solution I see is keeping a data structure with free variables inside (or references, for that matter) and binding these free variables in some other place. l0 would then bounded directly to  [1 ; 2 ; l0 ] in the AST. Any idea what the internals of OCaml do?

Related questions:
- is there any easy way to check if a list is cyclic or not? The only way I see is to go down the list, checking at every step if this particular sublist has already been seen. But it's rather heavy.
- the documentation on the = sign (http://caml.inria.fr/pub/docs/manual-ocaml/libref/Pervasives.html) mentions that "Equality between cyclic data structures may not terminate." It seems to terminate if one or the other of the data structures is not cyclic. Does it ever terminate when both data sstructures are cyclic, or does it always loop?
  # let l1 = [1; 2] in l0 = l1;;
  - : bool = false
  # l0 = l0;;
  (* doesn't finish *)

Thank you,
Jean-Baptiste Jeannin