From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <puech@cs.unibo.it>
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82])
	by yquem.inria.fr (Postfix) with ESMTP id 5B8BEBBAF
	for <caml-list@yquem.inria.fr>; Wed, 10 Mar 2010 10:45:41 +0100 (CET)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AtEAAHP4lkuCiAFml2dsb2JhbACbBxUBAQEBAQgVBzWudwiNSIJiCIIPBA
X-IronPort-AV: E=Sophos;i="4.49,613,1262559600"; 
   d="scan'208";a="54337087"
Received: from leb.cs.unibo.it ([130.136.1.102])
  by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/ADH-AES256-SHA; 10 Mar 2010 10:45:41 +0100
Received: from ssl.cs.unibo.it (ssl.cs.unibo.it [127.0.0.1]) (Authenticated sender: hidden)
	by leb.cs.unibo.it (Postfix) with ESMTPSA id 76B172359 
	for <caml-list@inria.fr>; Wed, 10 Mar 2010 10:45:40 +0100 (CET)
Message-ID: <4B976A44.9040807@cs.unibo.it>
Date: Wed, 10 Mar 2010 10:45:40 +0100
From: Matthias Puech <puech@cs.unibo.it>
User-Agent: Thunderbird 2.0.0.19 (X11/20090105)
MIME-Version: 1.0
To: caml-list@inria.fr
Subject: Resources on OCaml's sharing
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Spam: no; 0.00; unibo:01 ocaml's:01 ocaml's:01 compiler:01 hash-consing:01 ml's:01 folklore:98 rec:01 heap:01 algorithm:01 caml:02 match:02 matthias:02 maximal:03 let:03 

Dear Camlists,

Does anyone know of a description of the sharing mechanism inside
Ocaml's heap (I guess)? I'm interested in any kind material, from a
formal account in a paper (even not directly related to Caml), to an
informal description and tips of usage, anything that could fill in my
shameful ignorance on that matter. Particularly, I'm trying to understand:
- where architecturally it takes place in the compiler,
- how it is an approximation from the perfect case of maximal sharing
(hash-consing I guess), i.e. what's the algorithm
- when can I safely state that a = b implies a == b.
- how is it that the function below is "smarter" than List.map? What do
we gain, what do we loose?

I understand sharing is part of ML's folklore and I didn't find any
resource on it, but maybe I missed something...

Thank you all in advance,
	-m

<<

let rec list_smartmap f l = match l with
    [] -> l
  | h::tl ->
      let h' = f h and tl' = list_smartmap f tl in
	if h'==h && tl'==tl then l
	else h'::tl'

>>