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 mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id BA0C2BC6C for ; Sat, 19 Jan 2008 16:09:04 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAPCgkUeK6AGOk2dsb2JhbACQFwEBAQEHBAYJIJ06 X-IronPort-AV: E=Sophos;i="4.25,220,1199660400"; d="scan'208";a="21503114" Received: from lmr1.uibk.ac.at (HELO smtp.uibk.ac.at) ([138.232.1.142]) by mail4-smtp-sop.national.inria.fr with ESMTP; 19 Jan 2008 16:09:04 +0100 Received: from localhost (lwm2.uibk.ac.at [138.232.1.161] Christian.Sternagel@uibk.ac.at) by smtp.uibk.ac.at (8.13.8/8.13.8/F1) with ESMTP id m0JF910Y029284 for ; Sat, 19 Jan 2008 16:09:01 +0100 Received: from chello213047188176.tirol.surfer.at (chello213047188176.tirol.surfer.at [213.47.188.176]) by web-mail2.uibk.ac.at (IMP) with HTTP for ; Sat, 19 Jan 2008 16:09:01 +0100 Message-ID: <1200755341.4792128d5dad6@web-mail2.uibk.ac.at> Date: Sat, 19 Jan 2008 16:09:01 +0100 From: Christian Sternagel To: caml-list Subject: Re: [Caml-list] camlp4 References: <1200676132.4790dd24bfca9@web-mail2.uibk.ac.at> <95513600801181130u2f6584b8w505cd10e848bcc65@mail.gmail.com> <1200685853-sup-3987@ausone.local> In-Reply-To: <1200685853-sup-3987@ausone.local> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: Internet Messaging Program (IMP) 3.2.8 X-Originating-IP: 213.47.188.176 X-Forwarded-For: X-Scanned-By: MIMEDefang 2.61 at uibk.ac.at on 138.232.1.140 X-Spam: no; 0.00; camlp:01 camlp:01 flatten:01 appends:01 syntax:01 recursive:01 oandrieu:01 ocaml:01 wadler:01 expr:01 expr:01 cheers:01 wrote:01 rec:01 rec:01 Quoting Nicolas Pouillard : > Excerpts from oandrieu's message of Fri Jan 18 20:30:59 +0100 2008: > > On Jan 18, 2008 6:08 PM, Christian Sternagel > > wrote: > > > When using `camlp4o -parser Camlp4ListComprehension' as preprocessor, > > > is the resulting code the naive translation, like in, > > > > > > [(x, y) | x <- xs, even xs, y <- ys] > > > > > > => > > > > > > List.flatten ( > > > List.map (fun x -> List.map (fun y -> (x, y)) ys) (List.filter even xs) > > > ) > > > > > > or is there an optimization in order to avoid appends and minimize the > > > number of cons? > > > > > > FYI, my (old) syntax extension¹ for camlp4 <= 3.09 expands list > > comprehensions to a combination of folds: > > > > [+ (x, y) | x <- xs | when even x | y <- ys] > > > > => > > > > List.fold_right > > (fun x __acc__ -> > > if even x then > > List.fold_right (fun y __acc__ -> (x, y) :: __acc__) ys __acc__ > > else __acc__) > > xs [] > > > > Less cons operations, but it's not tail recursive. > > Hum... That's nice and I could accept patches in that direction. However > can > you do it without introducing variables, that's always dangerous to > add > variables because we should check that the user is not using the same. > > > [1] http://oandrieu.nerim.net/ocaml/#pa_compr > > -- > Nicolas Pouillard aka Ertai > > How about the transformation from Chapter 7 of [1] (by Philip Wadler)? It should be similar to the `pseudo code': type expr = ...;; type patt = ...;; type qualifier = Gen of patt * expr | Filt of expr;; type compr = (expr * qualifier list);; let rec expr = function | ... | (e, qs) -> transform [] (e, qs) | ... and transform l = function | (e, []) -> expr e :: expr l | (e, Filt f :: qs) -> if expr f then transform l (e, qs) else expr l | (e, Gen (p, l1) :: qs) -> let rec h = function | [] -> expr l | u :: us -> (function p -> transform (h us) (e, qs) | _ -> h us) u in h (expr l1) ;; (* where h, u, us are fresh variables not occurring in e, l1, l, or qs *) Sorry I'm not yet familiar with camlp4 grammar extensions, but of course above code would make use of them otherwise. It is stated in [1] that the resulting code is optimal in that it performs the minimum number of cons operations. I'm not sure whether this isn't equivalent to oandrieu's code. And I did ignore the hint that fresh variables make things complicated :). cheers christian [1] Simon P. Jones, 1987. The implementation of functional programming languages. Available online at: http://research.microsoft.com/~simonpj/papers/slpj-book-1987/index.htm