Re: [Caml-list] camlp4

[Christian Sternagel <Christian.Sternagel@uibk.ac.at>]

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.

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