From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 5E2B2BBAF for ; Wed, 10 Mar 2010 18:36:48 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArYCAMxnl0vRVaC2kWdsb2JhbACOaoN/h2IIFQEBAQEJCQwHESSuQ0eEUyKIVQEBAwWCSYIrBIMXiQo X-IronPort-AV: E=Sophos;i="4.49,615,1262559600"; d="scan'208";a="54370407" Received: from mail-gy0-f182.google.com ([209.85.160.182]) by mail1-smtp-roc.national.inria.fr with ESMTP; 10 Mar 2010 18:36:47 +0100 Received: by gyf2 with SMTP id 2so72272gyf.27 for ; Wed, 10 Mar 2010 09:36:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:sender:received:in-reply-to :references:date:x-google-sender-auth:message-id:subject:from:to:cc :content-type:content-transfer-encoding; bh=vKjYXCs/XY554bYqxmSqpGvEHtfuLTvhvitfcWEAwyM=; b=LLsfpjO5e9yO6en677TgwA5g04QR0kkslv8Y/+lX5XPg4As8ZJ2aX3T+juz5FFG7mK /Zy11qxyvKY6VCbH+CLkEjEALPXhYlUUij4X9esRGmuIKtRQXP/EselhqoQHhEp7uGZJ Wq/kIdR2g0PkaFqIzWY4Q7v4SL5SGjavCbhv8= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type :content-transfer-encoding; b=juGRnEMXFTyBoyKgtN3oPUloRWyWLQA91AyQgWKi0JCvPH+qonBLB3S1EPUWKNPEIj f0RJ+pmWwOeNxhwdmYmngSPfmKUqU3nPIvyRSt3NDyC43u1aVfceGlStoHMgxRGpthe2 dl/9TjmWjoJ8PuQ8GMyq9yzkzgqJe1PjXE+rQ= MIME-Version: 1.0 Sender: peter.hawkins@gmail.com Received: by 10.100.86.8 with SMTP id j8mr2330199anb.89.1268242606983; Wed, 10 Mar 2010 09:36:46 -0800 (PST) In-Reply-To: <4B976A44.9040807@cs.unibo.it> References: <4B976A44.9040807@cs.unibo.it> Date: Wed, 10 Mar 2010 09:36:46 -0800 X-Google-Sender-Auth: 2852c30b040acdd9 Message-ID: Subject: Re: [Caml-list] Resources on OCaml's sharing From: Peter Hawkins To: Matthias Puech Cc: caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Spam: no; 0.00; ocaml's:01 ml-like:01 ocaml:01 unibo:01 compiler:01 compiler:01 mutable:01 semantics:01 ocaml:01 val:01 pointer:01 val:01 bool:01 bool:01 semantically:01 Hi... Here are some comments for ML-like languages in general, not specific to OC= aml. On Wed, Mar 10, 2010 at 1:45 AM, Matthias Puech wrote: > shameful ignorance on that matter. Particularly, I'm trying to understand= : > - where architecturally it takes place in the compiler, It doesn't. The compiler doesn't have any support for recognizing and exploiting sharing. If a program creates sharing, then that's all well and good, but the compiler doesn't try to find sharing that wasn't already present. Indeed in the presence of mutable state as in ML, it's difficult for a compiler to introduce sharing without changing the semantics of the program. How do we ever create sharing as a programmer? Consider the following OCaml session: # let x =3D [1;2;3];; val x : int list =3D [1; 2; 3] This code introduces sharing, by creating two lists "y" and "z" with a pointer to a common shared tail "x": # let y =3D 7::x;; val y : int list =3D [7; 1; 2; 3] # let z =3D 42::x;; val z : int list =3D [42; 1; 2; 3] # List.tl y =3D=3D x;; - : bool =3D true # List.tl z =3D=3D x;; - : bool =3D true On the other hand, this code creates two distinct yet semantically equal tail lists: # let y' =3D 7::[1;2;3];; val y' : int list =3D [7; 1; 2; 3] # let z' =3D 42::[1;2;3];; val z' : int list =3D [42; 1; 2; 3] # List.tl y' =3D=3D x;; - : bool =3D false # List.tl z' =3D=3D x;; - : bool =3D false # List.tl y' =3D=3D List.tl z';; - : bool =3D false We have semantic equality, but not reference equality: # y =3D y';; - : bool =3D true # z =3D z';; - : bool =3D true # y =3D=3D y';; - : bool =3D false # z =3D=3D z';; - : bool =3D false You might want to google for "purely functional data structures" or "persistent data structures", e.g.: http://en.wikipedia.org/wiki/Purely_functional Chris Okasaki's writing is the standard reference, I believe. > - how it is an approximation from the perfect case of maximal sharing > (hash-consing I guess), i.e. what's the algorithm See above. The only sharing is that explicitly created by the programmer. > - when can I safely state that a =3D b implies a =3D=3D b. Pretty much never. The only way you can know "a =3D=3D b" if you know that variable "b" is a copy of variable "a", or vice versa. > - how is it that the function below is "smarter" than List.map? What do > we gain, what do we loose? > << > > let rec list_smartmap f l =3D match l with > =A0 =A0[] -> l > =A0| h::tl -> > =A0 =A0 =A0let h' =3D f h and tl' =3D list_smartmap f tl in > =A0 =A0 =A0 =A0if h'=3D=3Dh && tl'=3D=3Dtl then l > =A0 =A0 =A0 =A0else h'::tl' > Gain: If "f" is the identity function for some suffix of the list, you save some space and return the original instance of that suffix, rather than a copy. Loss: You spend time doing some pointer comparisons on every iteration that probably almost never succeed, assuming f is not the identity function. Peter