small Camlp4 code : get a free name

small Camlp4 code : get a free name

[blue storm]

>> I deduce that there is no standard way of introducing
>> `fresh' (w.r.t. the abstract syntax tree) variables
>> within a camlp4 syntax extension? Wouldn't that be nice? =)

>> Has anybody every implemented a solution to that problem?

> That  would be nice, but doing it cleanly would require a large amount of work
> and user visible changes.

I'm not sure it's a "clean" way of doing it, but i think this may works :
you can fold the AST to get every bound variable names, and then look
for conflicts.

I tried to do that. See my camlp4 code at the end of the message.

The folder is very simple : it collects every identifier name, even
not-really-bounded ones (eg. in patterns). I don't think it's a
problem : the important thing is to get no false positive.

Is there a problem with this method ?
Do you have any comment or advice ?

------------------
open Camlp4;

module Make (Syntax : Sig.Camlp4Syntax) = struct
  open Syntax;

  value get_bound_vars =
    let folder = object (self)
      inherit Ast.fold as super;

      value binds = [];
      method binds = binds;

      method ident = fun
        [ <:ident< $lid:id$ >> | <:ident< $uid:id$ >> ->
          {< binds = [id::binds] >}
        | other -> super#ident other ];
    end in
    fun expr -> (folder#expr expr)#binds;

  value get_free_var suffix binds =
    let rec generate var =
      if List.mem var binds
      then generate ("_" ^ var ^ "_")
      else var
    in generate suffix;
end;
------------------


You can test it with this example code (for example) :
------------------
open Camlp4
open PreCast

module FV = Freevars.Make(Syntax)

let _loc = Loc.ghost
let expr = <:expr< match foo with bar -> foo2 | _ -> 1 + 2 >>

let binds = FV.get_bound_vars expr
let fv = FV.get_free_var "foo" binds
(* fv is "_foo_" *)
------------------

Thanks for your comments.

Re: [Caml-list] small Camlp4 code : get a free name

[Martin Jambon]

On Wed, 23 Jan 2008, blue storm wrote:

>>> I deduce that there is no standard way of introducing
>>> `fresh' (w.r.t. the abstract syntax tree) variables
>>> within a camlp4 syntax extension? Wouldn't that be nice? =)
>
>>> Has anybody every implemented a solution to that problem?
>
>> That  would be nice, but doing it cleanly would require a large amount of work
>> and user visible changes.
>
> I'm not sure it's a "clean" way of doing it, but i think this may works :
> you can fold the AST to get every bound variable names, and then look
> for conflicts.
>
> I tried to do that. See my camlp4 code at the end of the message.
>
> The folder is very simple : it collects every identifier name, even
> not-really-bounded ones (eg. in patterns). I don't think it's a
> problem : the important thing is to get no false positive.
>
> Is there a problem with this method ?
> Do you have any comment or advice ?

Nice, but in theory, it may create identifiers that are bound to an 
incorrect value when the programmer forgot to define such a value.

For example, module A should provide A.x to module B (= another .ml file).
If the programmer forgets to define A.x, the compiler should report the 
error at the time of compiling b.ml. But if some camlp4 extension 
operating over a.ml introduces a variable A.x and by chance it has the 
same type as the expected A.x, then the compiler will remain silent and B 
will use the wrong value for A.x.


Martin

> ------------------
> open Camlp4;
>
> module Make (Syntax : Sig.Camlp4Syntax) = struct
>  open Syntax;
>
>  value get_bound_vars =
>    let folder = object (self)
>      inherit Ast.fold as super;
>
>      value binds = [];
>      method binds = binds;
>
>      method ident = fun
>        [ <:ident< $lid:id$ >> | <:ident< $uid:id$ >> ->
>          {< binds = [id::binds] >}
>        | other -> super#ident other ];
>    end in
>    fun expr -> (folder#expr expr)#binds;
>
>  value get_free_var suffix binds =
>    let rec generate var =
>      if List.mem var binds
>      then generate ("_" ^ var ^ "_")
>      else var
>    in generate suffix;
> end;
> ------------------
>
>
> You can test it with this example code (for example) :
> ------------------
> open Camlp4
> open PreCast
>
> module FV = Freevars.Make(Syntax)
>
> let _loc = Loc.ghost
> let expr = <:expr< match foo with bar -> foo2 | _ -> 1 + 2 >>
>
> let binds = FV.get_bound_vars expr
> let fv = FV.get_free_var "foo" binds
> (* fv is "_foo_" *)
> ------------------
>
> Thanks for your comments.
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

--
http://wink.com/profile/mjambon
http://martin.jambon.free.fr

Re: [Caml-list] small Camlp4 code : get a free name

[Edgar Friendly]

Martin Jambon wrote:
 > Nice, but in theory, it may create identifiers that are bound to an
> incorrect value when the programmer forgot to define such a value.
> 
> For example, module A should provide A.x to module B (= another .ml file).
> If the programmer forgets to define A.x, the compiler should report the
> error at the time of compiling b.ml. But if some camlp4 extension
> operating over a.ml introduces a variable A.x and by chance it has the
> same type as the expected A.x, then the compiler will remain silent and
> B will use the wrong value for A.x.
> 
> 
> Martin
> 
It seems to me that the only way to satisfy this requirement involves a
distinct namespace for these variables.  Maybe
Camlp4.Unique_identifiers.<generated identifier>?

But this seems isomorphic to the simpler solution of claiming a portion
of the identifier space: __camlp4_unique_identifier_<generated identifier>.

E

Re: [Caml-list] small Camlp4 code : get a free name

[Nicolas Pouillard]

Excerpts from Edgar Friendly's message of Wed Jan 23 22:35:16 +0100 2008:
> Martin Jambon wrote:
>  > Nice, but in theory, it may create identifiers that are bound to an
> > incorrect value when the programmer forgot to define such a value.
> > 
> > For example, module A should provide A.x to module B (= another .ml file).
> > If the programmer forgets to define A.x, the compiler should report the
> > error at the time of compiling b.ml. But if some camlp4 extension
> > operating over a.ml introduces a variable A.x and by chance it has the
> > same type as the expected A.x, then the compiler will remain silent and
> > B will use the wrong value for A.x.
> > 
> > 
> > Martin
> > 
> It seems to me that the only way to satisfy this requirement involves a
> distinct namespace for these variables.  Maybe
> Camlp4.Unique_identifiers.<generated identifier>?

You    cannot    always   use   the   dot   notation.   For   instance   <<let
Camlp4.Unique_identifiers.x = e1 in e2 >> would be wrong.

> But this seems isomorphic to the simpler solution of claiming a portion
> of the identifier space: __camlp4_unique_identifier_<generated identifier>.

Yes that's the poor man fresh function.

Best regards,

-- 
Nicolas Pouillard aka Ertai

Re: [Caml-list] small Camlp4 code : get a free name

[Nicolas Pouillard]

Excerpts from bluestorm.dylc's message of Wed Jan 23 20:59:59 +0100 2008:
> >> I deduce that there is no standard way of introducing
> >> `fresh' (w.r.t. the abstract syntax tree) variables
> >> within a camlp4 syntax extension? Wouldn't that be nice? =)
> 
> >> Has anybody every implemented a solution to that problem?
> 
> > That  would be nice, but doing it cleanly would require a large amount of work
> > and user visible changes.
> 
> I'm not sure it's a "clean" way of doing it, but i think this may works :
> you can fold the AST to get every bound variable names, and then look
> for conflicts.
> 
> I tried to do that. See my camlp4 code at the end of the message.
> 
> The folder is very simple : it collects every identifier name, even
> not-really-bounded ones (eg. in patterns). I don't think it's a
> problem : the important thing is to get no false positive.
> 
> Is there a problem with this method ?
> Do you have any comment or advice ?

Apart  performance  issues  if used too naively, another problem could be that
we  need  to  find/have the roots of all the sources in order to get all bound
variable.

This  approach  is  very  nice because clear, simple and also commonly used in
formal developments.

However  if  someone  want  to  use  this method, it would be nice to define a
"fresh"  function  on top get_free_var that hold the set bound variables as an
internal state.

Best regards,

> ------------------
> open Camlp4;
> 
> module Make (Syntax : Sig.Camlp4Syntax) = struct
>   open Syntax;
> 
>   value get_bound_vars =
>     let folder = object (self)
>       inherit Ast.fold as super;
> 
>       value binds = [];
>       method binds = binds;
> 
>       method ident = fun
>         [ <:ident< $lid:id$ >> | <:ident< $uid:id$ >> ->
>           {< binds = [id::binds] >}
>         | other -> super#ident other ];
>     end in
>     fun expr -> (folder#expr expr)#binds;
> 
>   value get_free_var suffix binds =
>     let rec generate var =
>       if List.mem var binds
>       then generate ("_" ^ var ^ "_")
>       else var
>     in generate suffix;
> end;
> ------------------
> 
> 
> You can test it with this example code (for example) :
> ------------------
> open Camlp4
> open PreCast
> 
> module FV = Freevars.Make(Syntax)
> 
> let _loc = Loc.ghost
> let expr = <:expr< match foo with bar -> foo2 | _ -> 1 + 2 >>
> 
> let binds = FV.get_bound_vars expr
> let fv = FV.get_free_var "foo" binds
> (* fv is "_foo_" *)

-- 
Nicolas Pouillard aka Ertai