From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 4BE4E7EE7D for ; Mon, 1 Jun 2015 14:02:01 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of jon@ffconsultancy.com) identity=pra; client-ip=212.159.14.18; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="jon@ffconsultancy.com"; x-sender="jon@ffconsultancy.com"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of jon@ffconsultancy.com) identity=mailfrom; client-ip=212.159.14.18; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="jon@ffconsultancy.com"; x-sender="jon@ffconsultancy.com"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@avasout06.plus.net) identity=helo; client-ip=212.159.14.18; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="jon@ffconsultancy.com"; x-sender="postmaster@avasout06.plus.net"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0AvAQDaSGxVnBIOn9RcDoNWXoMerFeQPAqFdwKBLDwQAQEBAQEBAREBAQEBAQYNCQkhLoQiAQEBBAgCGQVGCwwBAwIJEQQBAQECAgkaAwICGQgbCQEJCAIEARILBQKIBgMWCbJKhlSXWgMKhHYBAQEBAQEEAQEBAQEBARuBIYoigk2BUGkHBoInOxKBMwWFSgqNNnmDPIJSgjKDAj6DM4J/iBWHBINdP26CRwEBAQ X-IPAS-Result: A0AvAQDaSGxVnBIOn9RcDoNWXoMerFeQPAqFdwKBLDwQAQEBAQEBAREBAQEBAQYNCQkhLoQiAQEBBAgCGQVGCwwBAwIJEQQBAQECAgkaAwICGQgbCQEJCAIEARILBQKIBgMWCbJKhlSXWgMKhHYBAQEBAQEEAQEBAQEBARuBIYoigk2BUGkHBoInOxKBMwWFSgqNNnmDPIJSgjKDAj6DM4J/iBWHBINdP26CRwEBAQ X-IronPort-AV: E=Sophos;i="5.13,532,1427752800"; d="scan'208";a="161229227" Received: from avasout06.plus.net ([212.159.14.18]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES128-SHA; 01 Jun 2015 14:02:00 +0200 Received: from XPS ([87.113.219.165]) by avasout06 with smtp id b01y1q0033aiWZz0101zV6; Mon, 01 Jun 2015 13:01:59 +0100 X-CM-Score: 0.00 X-CNFS-Analysis: v=2.1 cv=foEhHwMf c=1 sm=1 tr=0 a=CPAVYl+5h9ILULwPD0AF8A==:117 a=CPAVYl+5h9ILULwPD0AF8A==:17 a=0Bzu9jTXAAAA:8 a=IkcTkHD0fZMA:10 a=r2vSxAw-AAAA:8 a=4Wf4a91pAAAA:8 a=pGLkceISAAAA:8 a=ZOzjf2MOAAAA:8 a=CjxXgO3LAAAA:8 a=AdGb2G78CWkEvSBhD34A:9 a=QEXdDO2ut3YA:10 X-AUTH: jdh302@:2500 Reply-To: From: "Jon Harrop" To: "'Stephen Dolan'" , "'Gabriel Scherer'" Cc: "'Pierre Chambart'" , "'Goswin von Brederlow'" , "'caml users'" References: <20140929120817.GB20628@frosties> <54296663.8080902@laposte.net> In-Reply-To: Date: Mon, 1 Jun 2015 13:02:01 +0100 Organization: Flying Frog Consultancy Ltd. Message-ID: <00fb01d09c62$c5da4ad0$518ee070$@ffconsultancy.com> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-Mailer: Microsoft Outlook 14.0 Thread-Index: AQFuqN4yOtYSXluCVGIPP+VMQzGLkgE4D/JrAmTfKHkBp1AvAQHgYQHOArI/0/CeDLxnIA== Content-Language: en-gb Subject: RE: [Caml-list] Why List.map does not be implemented tail-recursively? What happens when the first allocation in the creation of a cyclic immutabl= e structure incurs a minor collection? let rec xs =3D 0::ys and ys =3D 1::xs -----Original Message----- From: stedolan@stedolan.net [mailto:stedolan@stedolan.net] On Behalf Of Ste= phen Dolan Sent: 02 October 2014 11:10 To: Gabriel Scherer Cc: Pierre Chambart; Goswin von Brederlow; caml users Subject: Re: [Caml-list] Why List.map does not be implemented tail-recursiv= ely? On Mon, Sep 29, 2014 at 10:00 PM, Gabriel Scherer wrote: >> Please, don't do that hack ! The compiler assumes immutable data are=20 >> not mutated and optimise knowing that. > > My understanding was that it is unsafe to Obj.magic an immutable data=20 > structure into a mutable one (one mental model is that immutable data=20= =20 > might be allocated in read-only memory, although that's not what the=20 > current implementation does), but that on the contrary it is safe to=20 > Obj.magic a mutable data-structure into an immutable one. The=20 > Obj.magic-using code for List.map, implemented in Extlib and inherited=20 > by Batteries, is careful to use an unsafe cast in exactly the second=20 > situation. This is a feature that other languages (eg. Mezzo) safely prov= ide. This trick is unsound in our implementation of multicore OCaml: the system = assumes that immutable objects only point to older objects, and thus that a= shared immutable object cannot point to a private immutable object. This c= an be hacked around (we have a similar hack for recursive immutable objects= ), but the point is that such tricks are fragile and depend on very impleme= ntation-specific behaviour. Even in single-threaded OCaml, this trick is broken by quite reasonable com= piler optimisations (although not ones that OCaml does today). For instance= , if ocamlopt were to perform alias analysis and optimise based on the resu= lts, the first thing the alias analyser would do is conclude that reference= s to immutable and mutable fields do not alias. This would allow it to swap= the order of references to the immutable and mutable fields, and after inl= ining would mean that the cons cell is read before it is initialised. Stephen -- Caml-list mailing list. Subscription management and archives: https://sympa.inria.fr/sympa/arc/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs