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 B45187FACD for ; Mon, 29 Sep 2014 23:01:04 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of gabriel.scherer@gmail.com) identity=pra; client-ip=209.85.214.172; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of gabriel.scherer@gmail.com designates 209.85.214.172 as permitted sender) identity=mailfrom; client-ip=209.85.214.172; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-ob0-f172.google.com) identity=helo; client-ip=209.85.214.172; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="postmaster@mail-ob0-f172.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtsBAN/HKVTRVdasm2dsb2JhbABgg2FXBIJ9thOPHYFth04CgQ0IFgERAQEBAQEGCwsJFCyEAwEBAQMBEhEdARsSCwEDAQsGAwIEBw0NHQICIgERAQUBChIGExIQiAcBAwkIDYxlkC5uizCBcoMQiQcKGScDCgZhhjcBEQEFDo8oEVMEB4J4gVMFhRQFjVGDNYcJgWKSCRgphRY7L4EHgUMBAQE X-IPAS-Result: AtsBAN/HKVTRVdasm2dsb2JhbABgg2FXBIJ9thOPHYFth04CgQ0IFgERAQEBAQEGCwsJFCyEAwEBAQMBEhEdARsSCwEDAQsGAwIEBw0NHQICIgERAQUBChIGExIQiAcBAwkIDYxlkC5uizCBcoMQiQcKGScDCgZhhjcBEQEFDo8oEVMEB4J4gVMFhRQFjVGDNYcJgWKSCRgphRY7L4EHgUMBAQE X-IronPort-AV: E=Sophos;i="5.04,622,1406584800"; d="scan'208";a="98499463" Received: from mail-ob0-f172.google.com ([209.85.214.172]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 29 Sep 2014 23:01:03 +0200 Received: by mail-ob0-f172.google.com with SMTP id wp18so4622024obc.17 for ; Mon, 29 Sep 2014 14:01:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=U7W18S5a+YB2888yF9pubNW5eEoH5RTZS83rS8pa4W4=; b=BpHxzF9aKtX5fg3Jt9EZjKS1X+sRe5/YlZhuczZaRjmDmCRROitCfW1oqDv/UFhGvU BsBc70tZjzyzzKKYw4s1dPBklmEMbU6GimQh7meKm/v4BHkSX184bF+SGcSIWVeF66nd bv/QQiJ0+kDKjUBn8rtsUOd2Y6nfZxJFMzvbpWsruL9KeADl5BfvuW8aPVymOi2YHWMx KIa6ZECkDVMDifS15wW00uu9cxmamgDd/26R9H7CaL7IVglsbgolamQViAEXshcIAg2P UL3OUwPUuU5QfpbVDiC9YSfKOjYw2HY0UTEJkQsp58cuOAT4mv0r/1UV3dKzNgxNLOBV xx9A== X-Received: by 10.60.74.39 with SMTP id q7mr5920873oev.72.1412024462933; Mon, 29 Sep 2014 14:01:02 -0700 (PDT) MIME-Version: 1.0 Received: by 10.76.105.196 with HTTP; Mon, 29 Sep 2014 14:00:21 -0700 (PDT) In-Reply-To: <54296663.8080902@laposte.net> References: <20140929120817.GB20628@frosties> <54296663.8080902@laposte.net> From: Gabriel Scherer Date: Mon, 29 Sep 2014 23:00:21 +0200 Message-ID: To: Pierre Chambart Cc: Goswin von Brederlow , caml users Content-Type: multipart/alternative; boundary=001a11348eee87051905043a9013 Subject: Re: [Caml-list] Why List.map does not be implemented tail-recursively? --001a11348eee87051905043a9013 Content-Type: text/plain; charset=UTF-8 > > 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. If this last technique became invalid because of compiler optimization in the future, that would need to be clearly exposed and justified. Could you confirm that this is not the case today? (I think this is also the way immutable recursive value work, with a tying-the-knot mutation followed by a conceptual "freeze" of the resulting structure.) On Mon, Sep 29, 2014 at 4:02 PM, Pierre Chambart < pierre.chambart@laposte.net> wrote: > On 29/09/2014 14:08, Goswin von Brederlow wrote: > > And I'll will do the same, reply anyway. > > > > You can't write List.map tail recursive unless: > > > > 1) You use List.rev (List.rev_map fn list). > > > > or > > > > 2) Use hacks to create a mutable list so you can grow it head to tail > > instead of tail to head. > > > > The fastest code seems to be when you do List.map recursively up to > > some limit (say 1000 items) and return the remainder. Repeat and glue > > the lists together into one large list using hacks. > > > > MfG > > Mrvn > > > Please, don't do that hack ! The compiler assumes immutable data are not > mutated and optimise knowing that. > -- > Pierre > > > -- > 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 > --001a11348eee87051905043a9013 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Please, = don't do that hack ! The compiler assumes immutable data are not
mutated and optimise knowing that.

My u= nderstanding was that it is unsafe to Obj.magic an immutable data structure= into a mutable one (one mental model is that immutable data=C2=A0 might be= allocated in read-only memory, although that's not what the current im= plementation does), but that on the contrary it is safe to Obj.magic a muta= ble 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 a= n unsafe cast in exactly the second situation. This is a feature that other= languages (eg. Mezzo) safely provide.

If this last techn= ique became invalid because of compiler optimization in the future, that wo= uld need to be clearly exposed and justified. Could you confirm that this i= s not the case today?

(I think this is also the way immut= able recursive value work, with a tying-the-knot mutation followed by a con= ceptual "freeze" of the resulting structure.)

On Mon, Sep 29, 2014 at 4:0= 2 PM, Pierre Chambart <pierre.chambart@laposte.net> wrote:
On 29/09/2014 14:08, Goswin von Brederlow wrote:
> And I'll will do the same, reply anyway.
>
> You can't write List.map tail recursive unless:
>
> 1) You use List.rev (List.rev_map fn list).
>
> or
>
> 2) Use hacks to create a mutable list so you can grow it head to tail<= br> > instead of tail to head.
>
> The fastest code seems to be when you do List.map recursively up to
> some limit (say 1000 items) and return the remainder. Repeat and glue<= br> > the lists together into one large list using hacks.
>
> MfG
>=C2=A0 =C2=A0 =C2=A0 =C2=A0Mrvn
>
Please, don't do that hack ! The compiler assumes immutable data= are not
mutated and optimise knowing that.
--
Pierre


--
Caml-list mailing list.=C2=A0 Subscription management and archives:
ht= tps://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

--001a11348eee87051905043a9013--