Re: [Caml-list] camlp4

["Nicolas Pouillard" <nicolas.pouillard@gmail.com>]

Excerpts from christian.sternagel's message of Sat Jan 19 16:09:01 +0100 2008:
> Quoting Nicolas Pouillard <nicolas.pouillard@gmail.com>:
> 
> > Excerpts from oandrieu's message of Fri Jan 18 20:30:59 +0100 2008:
> > > On Jan 18, 2008 6:08 PM, Christian Sternagel
> > > <Christian.Sternagel@uibk.ac.at> 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