From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <bluestorm.dylc@gmail.com>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: *
X-Spam-Status: No, score=1.4 required=5.0 tests=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 D9F07BC6B
	for <caml-list@yquem.inria.fr>; Wed, 23 Jan 2008 21:00:16 +0100 (CET)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AgAAABcsl0dA6bjvlmdsb2JhbACLWYRFAQEBAQcEBgcbB5ZGhyqBFQ
X-IronPort-AV: E=Sophos;i="4.25,240,1199660400"; 
   d="scan'208";a="21695827"
Received: from wr-out-0506.google.com ([64.233.184.239])
  by mail4-smtp-sop.national.inria.fr with ESMTP; 23 Jan 2008 21:00:02 +0100
Received: by wr-out-0506.google.com with SMTP id c49so1336432wra.21
        for <caml-list@yquem.inria.fr>; Wed, 23 Jan 2008 12:00:01 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        h=domainkey-signature:received:received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition;
        bh=UvJ+vCzwGmKr0XOyvQooMHgL8EE/5euEWT7rk80hg+E=;
        b=Sk7e6IX68u1JxXEZh0oAzGHgpQ+j1h+lK1AIRjPvlxlNHGsllWqOWkwS2oMThlgwykORI+O5Qg/ghkj4B/HzW7cl8ud59t3i94P/dHNn9ndFv6FLz8Ftm5tydno9pbQWHc6t853dT+g1Cqux613Fmyae0JxveWyNJoVV8Gi0+vw=
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition;
        b=ghm7x8vuDsf82+g8ugVQ3FxZpZ3xozlIt1kOlWdEMfztma1ItMrhAL+0o317/fSlydOSJOhQ6LZmH2Rcp1RfC6RraZBbUNUhIrcGH6opffirW23xm0AnOEnQcGm3q8HB11tg93UPjH/MASrKynz3EqB6aX9M3NAaanj18CHDjIE=
Received: by 10.142.158.17 with SMTP id g17mr5229793wfe.106.1201118399899;
        Wed, 23 Jan 2008 11:59:59 -0800 (PST)
Received: by 10.142.139.13 with HTTP; Wed, 23 Jan 2008 11:59:59 -0800 (PST)
Message-ID: <527cf6bc0801231159o7c001a73lddd74e5b3cb30061@mail.gmail.com>
Date: Wed, 23 Jan 2008 20:59:59 +0100
From: "blue storm" <bluestorm.dylc@gmail.com>
To: caml-list@yquem.inria.fr
Subject: small Camlp4 code : get a free name
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
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 storm:98 abstract:01 rec:01 

>> 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.