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=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 8F5B2BBAF for ; Wed, 11 Jun 2008 00:32:57 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmgAADmeTkjYi40Iomdsb2JhbACSEQEBAQEBAQcFBgkRnyM X-IronPort-AV: E=Sophos;i="4.27,619,1204498800"; d="scan'208";a="11861073" Received: from mail-out8.nyct.net (HELO mail.nyct.net) ([216.139.141.8]) by mail2-smtp-roc.national.inria.fr with ESMTP; 11 Jun 2008 00:32:57 +0200 Received: from [192.168.42.2] (pool-96-250-28-38.nycmny.east.verizon.net [96.250.28.38]) (authenticated bits=0) by mail.nyct.net (8.14.2/8.14.1) with ESMTP id m5AMWqGi045182 (version=TLSv1/SSLv3 cipher=DHE-DSS-AES256-SHA bits=256 verify=NO); Tue, 10 Jun 2008 18:32:54 -0400 (EDT) (envelope-from bhurt@spnz.org) Date: Tue, 10 Jun 2008 19:07:47 -0400 (EDT) From: Brian Hurt X-X-Sender: bhurt@localhost To: Charles Hymans Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] optimization of sequence of List.map and inlining In-Reply-To: <676aba050806101201x526f03b1lf1fdbed665ee2e3f@mail.gmail.com> Message-ID: References: <676aba050806101201x526f03b1lf1fdbed665ee2e3f@mail.gmail.com> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Spam: no; 0.00; inlining:01 compiler:01 foo:01 foo:01 wrote:01 caml-list:01 exceptions:01 short:01 optimization:03 element:03 let:03 let:03 applied:05 brian:05 brian:05 On Tue, 10 Jun 2008, Charles Hymans wrote: > Let's say, I have the following code: > > let f l = List.map succ l > > .... > > let l = f l in > let l = List.map succ l in > do_something_with l > > > Is there a way to tell the compiler to optimize it so that it runs as fast > as this code: > let l = List.map (fun x -> succ (succ x)) l in > l > In the first case, there are two passes where succ is applied to > each elements of the list. In the second case, there is only one pass > that applies succ twice to each element of the list. > The short answer is no- due to the possibility of side effects, it's hard (read: in the general case equivelent to the halting problem) to determine if that code transformation produces the same result. Even ignoring exceptions and i/o! As an example of what I mean, consider the code: let r : ref 1;; let foo x = r := !r + x; !r;; let bar x = foo (foo x);; So now, if we set r to 1, and call List.map foo (List.map foo [1;2;3]), we get the return list [9; 13; 20], while List.map bar [1;2;3] returns [4; 12; 30]. So it's not always the case that you can replace List.map f (List.map g lst) with List.map (f . g) lst, and get the same result back. Brian