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=1.2 required=5.0 tests=AWL,SPF_NEUTRAL 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 F0C82BC6B for ; Sun, 20 Jan 2008 16:24:34 +0100 (CET) X-IronPort-AV: E=Sophos;i="4.25,223,1199660400"; d="scan'208";a="21521352" Received: from peray.inria.fr (HELO ausone.inria.fr) ([128.93.8.98]) by mail4-relais-sop.national.inria.fr with SMTP; 20 Jan 2008 16:24:34 +0100 Received: by ausone.inria.fr (sSMTP sendmail emulation); Sun, _d Jan 2008 16:23:33 +0100 From: "Nicolas Pouillard" Content-Type: text/plain; charset=UTF-8 Cc: caml-list Subject: Re: [Caml-list] camlp4 To: christian.sternagel References: <1200676132.4790dd24bfca9@web-mail2.uibk.ac.at> <95513600801181130u2f6584b8w505cd10e848bcc65@mail.gmail.com> <1200685853-sup-3987@ausone.local> <1200755341.4792128d5dad6@web-mail2.uibk.ac.at> In-Reply-To: <1200755341.4792128d5dad6@web-mail2.uibk.ac.at> Date: Sun, 20 Jan 2008 16:23:33 +0100 Message-Id: <1200842484-sup-3237@ausone.local> User-Agent: Sup/git 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 wrote:01 rec:01 rec:01 preprocessor:01 Excerpts from christian.sternagel's message of Sat Jan 19 16:09:01 +0100 2008: > 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. Yes this approach can be integrated with a camlp4 extension. > It is stated in [1] that the resulting code is optimal in that it > performs the minimum number of cons operations. Nice. > And I did ignore the hint that fresh variables make things > complicated :). Yes it can... Best regards, -- Nicolas Pouillard aka Ertai