From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 2D1457EFCD for ; Thu, 2 Oct 2014 12:09:35 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of stedolan@stedolan.net) identity=pra; client-ip=209.85.215.52; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="stedolan@stedolan.net"; x-sender="stedolan@stedolan.net"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of stedolan@stedolan.net) identity=mailfrom; client-ip=209.85.215.52; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="stedolan@stedolan.net"; x-sender="stedolan@stedolan.net"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-la0-f52.google.com) identity=helo; client-ip=209.85.215.52; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="stedolan@stedolan.net"; x-sender="postmaster@mail-la0-f52.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqsBAAIkLVTRVdc0m2dsb2JhbABghDoEgn7QNggWAREBAQEBAQYLCwkULIQEAQEEEhFWEAEKCw0CAiYCAiEBEgEFARwGEyKICAMRmlluizCOYA1XhlkKgSKMSoFIg2eBUwEEknOFdYI7ghCPJoRbGCmFFWuBSIECAQEB X-IPAS-Result: AqsBAAIkLVTRVdc0m2dsb2JhbABghDoEgn7QNggWAREBAQEBAQYLCwkULIQEAQEEEhFWEAEKCw0CAiYCAiEBEgEFARwGEyKICAMRmlluizCOYA1XhlkKgSKMSoFIg2eBUwEEknOFdYI7ghCPJoRbGCmFFWuBSIECAQEB X-IronPort-AV: E=Sophos;i="5.04,638,1406584800"; d="scan'208";a="99002855" Received: from mail-la0-f52.google.com ([209.85.215.52]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 02 Oct 2014 12:09:34 +0200 Received: by mail-la0-f52.google.com with SMTP id hz20so2054771lab.11 for ; Thu, 02 Oct 2014 03:09:33 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:sender:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=cmNkJ7KK0SSy9nAxV6CRnLVshpvXgt5LVkX0HGuP98o=; b=ZGrq2tAKfq6FcZDBE2zXv85z/F6dko/mLENmoKxMxIzIx+i+U/sJ2yrjKoa/ppo2zv OlKyGcch8L+7zpARJw62xdYqGgffbqDo4J4rYsESw45LXYexc46zz7Ki0CFbxA4i7BEF kvrcDuNv48oAdalwKafiBBBlEczqEnpC2uHhGWbTO2MXhA82ipo2L0suWOx+/Q20twP7 hV+JmD6uC3AxdkV6xsB0zFw7aB8Hf12X7dcomoA3pOlJlxcZISR+cYPflezWk+ioyGPM cnRwcNB2PxYTfY7mJbLDOljiSvJSJGkF5qeBqoa+CL5UHabdHspulqxK4395VN1hUfBU XfVQ== X-Gm-Message-State: ALoCoQmgQOGKwJosXiNsdOBA09o9V6lOj3ltTd7QNYJSiuI57S1QiSiFgpMuaKWnq9oP+0Pn0aXL MIME-Version: 1.0 X-Received: by 10.112.52.68 with SMTP id r4mr59019945lbo.31.1412244573824; Thu, 02 Oct 2014 03:09:33 -0700 (PDT) Sender: stedolan@stedolan.net Received: by 10.114.176.165 with HTTP; Thu, 2 Oct 2014 03:09:33 -0700 (PDT) X-Originating-IP: [128.232.9.157] In-Reply-To: References: <20140929120817.GB20628@frosties> <54296663.8080902@laposte.net> Date: Thu, 2 Oct 2014 11:09:33 +0100 X-Google-Sender-Auth: 8WTcojMaWPRIb9EynwsSjMOOMOM Message-ID: From: Stephen Dolan To: Gabriel Scherer Cc: Pierre Chambart , Goswin von Brederlow , caml users Content-Type: text/plain; charset=UTF-8 Subject: Re: [Caml-list] Why List.map does not be implemented tail-recursively? On Mon, Sep 29, 2014 at 10:00 PM, Gabriel Scherer wrote: >> Please, don't do that hack ! The compiler assumes immutable data are not >> mutated and optimise knowing that. > > My understanding was that it is unsafe to Obj.magic an immutable data > structure into a mutable one (one mental model is that immutable data might > be allocated in read-only memory, although that's not what the current > implementation does), but that on the contrary it is safe to Obj.magic a > mutable data-structure into an immutable one. The Obj.magic-using code for > List.map, implemented in Extlib and inherited by Batteries, is careful to > use an unsafe cast in exactly the second situation. This is a feature that > other languages (eg. Mezzo) safely provide. 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 can 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 implementation-specific behaviour. Even in single-threaded OCaml, this trick is broken by quite reasonable compiler optimisations (although not ones that OCaml does today). For instance, if ocamlopt were to perform alias analysis and optimise based on the results, the first thing the alias analyser would do is conclude that references 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 inlining would mean that the cons cell is read before it is initialised. Stephen