From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: ** X-Spam-Status: No, score=2.2 required=5.0 tests=AWL,DNS_FROM_RFC_POST, SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id B43D9BBAF for ; Sun, 14 Dec 2008 15:29:19 +0100 (CET) X-IronPort-AV: E=Sophos;i="4.36,218,1228086000"; d="scan'208";a="20354670" Received: from concorde.inria.fr ([192.93.2.39]) by mail3-smtp-sop.national.inria.fr with ESMTP; 14 Dec 2008 15:29:19 +0100 Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id mBEETIbT018161 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Sun, 14 Dec 2008 15:29:19 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtIBAPumRElC+Vq0jmdsb2JhbACTFT4BAQEBBw0ICQ8FrVmBBIp2AQMBA4J7 X-IronPort-AV: E=Sophos;i="4.36,218,1228086000"; d="scan'208";a="20354669" Received: from ik-out-1112.google.com ([66.249.90.180]) by mail3-smtp-sop.national.inria.fr with ESMTP; 14 Dec 2008 15:29:18 +0100 Received: by ik-out-1112.google.com with SMTP id c28so817063ika.1 for ; Sun, 14 Dec 2008 06:29:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to :subject:cc:in-reply-to:mime-version:content-type :content-transfer-encoding:content-disposition:references; bh=MNJSJRJmUucxTy7SjPLkgbIETrUzPazMIsC1VxKC90E=; b=KqoiHEe5+gmtDOGkCpVenZVQ+F8bJkNWduW2Nb03DamZINZdt35G4hzOFrTeWYOywi fr8T7de5ZLOxgmD42TthF6E87DB5PWur9ipfsC+zojGovzOTEvavQOWo82ygSNpbh6JV wWjg1ARfaAz9L+0+QLCsrpf9MYq0rQHjegKig= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:cc:in-reply-to:mime-version :content-type:content-transfer-encoding:content-disposition :references; b=tBKqUSqXEMgXim5hSAO50qUo72Efs34ES6aU+NZEGKn4IatFpC4hpE8d9/eGsQBJOx Nr2JypvrTe2DXH5ogmMrmyeI3qI3+XEiWtObGnI14jWrEKLtJg5j1l4EzcPSV8eQ5RJW 5Ws8SMD4yvN/3rmmckGONXkURBz06OLgpHAv8= Received: by 10.210.54.17 with SMTP id c17mr6582806eba.74.1229264958014; Sun, 14 Dec 2008 06:29:18 -0800 (PST) Received: by 10.210.143.4 with HTTP; Sun, 14 Dec 2008 06:29:17 -0800 (PST) Message-ID: <527cf6bc0812140629h249f6c0wa5b0eaef9efc836b@mail.gmail.com> Date: Sun, 14 Dec 2008 15:29:17 +0100 From: "blue storm" To: Francois.Pottier@inria.fr Subject: Re: [Caml-list] Immutable cyclic data structures via a Cc: "Edgar Friendly" , caml-list@inria.fr, "Christopher L Conway" In-Reply-To: <20081214091045.GA2341@yquem.inria.fr> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <494465C2.2000807@gmail.com> <20081214091045.GA2341@yquem.inria.fr> X-Miltered: at concorde with ID 4945183E.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; mutable:01 compiler:01 mutable:01 storm:98 edgar:98 stays:98 wrote:01 wrote:01 caml-list:01 pottier:01 pottier:01 immutable:01 cyclic:01 immutable:01 data:02 On 12/14/08, Francois Pottier wrote: > On Sat, Dec 13, 2008 at 07:47:46PM -0600, Edgar Friendly wrote: >> ExtLib (and thus batteries) uses your unmute (called [inj]) for >> converting a mutable list into the normal immutable list. The definition: > > This is, in principle, unsound. The compiler could (if it were more > agressive) > assume that a value of type 'a list is unaffected by a function call, > whereas, > if the list is really mutable, it could actually be written to by the call. That could be an issue if an immutable list was mutated by the library. Extlib uses mutability to build new mutable lists, to have for example a cheap tail-recursive map (you can destructively cons new cells at the end of the mutable list). The new list is then converted in constant time to an usual unmutable list, wich is returned by the function. The reference to the original mutable list is lost, and pure lists are never converted back. The mutable list stays inside the function boundary and, assuming the function is correctly written, there is no observable mutability.