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.1 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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id BB265BC6C for ; Sat, 9 Feb 2008 20:15:03 +0100 (CET) X-IronPort-AV: E=Sophos;i="4.25,327,1199660400"; d="scan'208";a="7128208" Received: from peray.inria.fr (HELO ausone.inria.fr) ([128.93.8.98]) by mail2-relais-roc.national.inria.fr with SMTP; 09 Feb 2008 20:15:02 +0100 Received: by ausone.inria.fr (sSMTP sendmail emulation); Sat, _d Feb 2008 20:13:56 +0100 From: "Nicolas Pouillard" Content-Type: text/plain; charset=UTF-8 Cc: caml-list Subject: Re: [Caml-list] small Camlp4 code : get a free name To: bluestorm.dylc References: <527cf6bc0801231159o7c001a73lddd74e5b3cb30061@mail.gmail.com> In-Reply-To: <527cf6bc0801231159o7c001a73lddd74e5b3cb30061@mail.gmail.com> Date: Sat, 09 Feb 2008 20:13:56 +0100 Message-Id: <1202583789-sup-4492@ausone.local> User-Agent: Sup/git X-Spam: no; 0.00; camlp:01 syntax:01 camlp:01 syntax:01 sig:01 struct:01 vars:01 expr:01 expr:01 foo:01 foo:01 vars:01 abstract:01 rec:01 caml-list:01 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