helm/ocaml/cic_notation/cicNotationSubst.ml

   1 (* Copyright (C) 2004-2005, HELM Team.
   2  *
   3  * This file is part of HELM, an Hypertextual, Electronic
   4  * Library of Mathematics, developed at the Computer Science
   5  * Department, University of Bologna, Italy.
   6  *
   7  * HELM is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation; either version 2
  10  * of the License, or (at your option) any later version.
  11  *
  12  * HELM is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with HELM; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  20  * MA  02111-1307, USA.
  21  *
  22  * For details, see the HELM World-Wide-Web page,
  23  * http://helm.cs.unibo.it/
  24  *)
  25
  26 open CicNotationEnv
  27 open CicNotationPt
  28
  29   (* TODO ensure that names generated by fresh_var do not clash with user's *)
  30 let fresh_var =
  31   let index = ref ~-1 in
  32   fun () ->
  33     incr index;
  34     "fresh" ^ string_of_int !index
  35
  36 let meta_names_of term =
  37   let rec names = ref [] in
  38   let add_name n =
  39     if List.mem n !names then ()
  40     else names := n :: !names
  41   in
  42   let rec aux = function
  43     | AttributedTerm (_, term) -> aux term
  44     | Appl terms -> List.iter aux terms
  45     | Binder (_, _, body) -> aux body
  46     | Case (term, indty, outty_opt, patterns) ->
  47         aux term ;
  48         aux_opt outty_opt ;
  49         List.iter aux_branch patterns
  50     | LetIn (_, t1, t2) ->
  51         aux t1 ;
  52         aux t2
  53     | LetRec (_, definitions, body) ->
  54         List.iter aux_definition definitions ;
  55         aux body
  56     | Uri (_, Some substs) -> aux_substs substs
  57     | Ident (_, Some substs) -> aux_substs substs
  58     | Meta (_, substs) -> aux_meta_substs substs
  59
  60     | Implicit
  61     | Ident _
  62     | Num _
  63     | Sort _
  64     | Symbol _
  65     | Uri _
  66     | UserInput -> ()
  67
  68     | Magic magic -> aux_magic magic
  69     | Variable var -> aux_variable var
  70
  71     | _ -> assert false
  72   and aux_opt = function
  73     | Some term -> aux term
  74     | None -> ()
  75   and aux_capture_var (_, ty_opt) = aux_opt ty_opt
  76   and aux_branch (pattern, term) =
  77     aux_pattern pattern ;
  78     aux term
  79   and aux_pattern (head, vars) =
  80     List.iter aux_capture_var vars
  81   and aux_definition (var, term, i) =
  82     aux_capture_var var ;
  83     aux term
  84   and aux_substs substs = List.iter (fun (_, term) -> aux term) substs
  85   and aux_meta_substs meta_substs = List.iter aux_opt meta_substs
  86   and aux_variable = function
  87     | NumVar name -> add_name name
  88     | IdentVar name -> add_name name
  89     | TermVar name -> add_name name
  90     | FreshVar _ -> ()
  91     | Ascription _ -> assert false
  92   and aux_magic = function
  93     | Default (t1, t2)
  94     | Fold (_, t1, _, t2) ->
  95         aux t1 ;
  96         aux t2
  97     | _ -> assert false
  98   in
  99   aux term ;
 100   !names
 101
 102 let unopt_names names env =
 103   let rec aux acc = function
 104     | (name, (ty, v)) :: tl when List.mem name names ->
 105         (match ty, v with
 106         | OptType ty, OptValue (Some v) -> aux ((name, (ty, v)) :: acc) tl
 107         | _ -> assert false)
 108     | _ :: tl -> aux acc tl
 109       (* some pattern may contain only meta names, thus we trash all others *)
 110     | [] -> acc
 111   in
 112   aux [] env
 113
 114 let head_names names env =
 115   let rec aux acc = function
 116     | (name, (ty, v)) :: tl when List.mem name names ->
 117         (match ty, v with
 118         | ListType ty, ListValue (v :: _) -> aux ((name, (ty, v)) :: acc) tl
 119         | _ -> assert false)
 120     | _ :: tl -> aux acc tl
 121       (* base pattern may contain only meta names, thus we trash all others *)
 122     | [] -> acc
 123   in
 124   aux [] env
 125
 126 let tail_names names env =
 127   let rec aux acc = function
 128     | (name, (ty, v)) :: tl when List.mem name names ->
 129         (match ty, v with
 130         | ListType ty, ListValue (_ :: vtl) ->
 131             aux ((name, (ListType ty, ListValue vtl)) :: acc) tl
 132         | _ -> assert false)
 133     | binding :: tl -> aux (binding :: acc) tl
 134     | [] -> acc
 135   in
 136   aux [] env
 137
 138 let instantiate_level2 env term =
 139   let fresh_env = ref [] in
 140   let lookup_fresh_name n =
 141     try
 142       List.assoc n !fresh_env
 143     with Not_found ->
 144       let new_name = fresh_var () in
 145       fresh_env := (n, new_name) :: !fresh_env;
 146       new_name
 147   in
 148   let rec aux env term =
 149     match term with
 150     | AttributedTerm (_, term) -> aux env term
 151     | Appl terms -> Appl (List.map (aux env) terms)
 152     | Binder (binder, var, body) ->
 153         Binder (binder, aux_capture_var env var, aux env body)
 154     | Case (term, indty, outty_opt, patterns) ->
 155         Case (aux env term, indty, aux_opt env outty_opt,
 156           List.map (aux_branch env) patterns)
 157     | LetIn (var, t1, t2) ->
 158         LetIn (aux_capture_var env var, aux env t1, aux env t2)
 159     | LetRec (kind, definitions, body) ->
 160         LetRec (kind, List.map (aux_definition env) definitions, aux env body)
 161     | Uri (name, None) -> Uri (name, None)
 162     | Uri (name, Some substs) -> Uri (name, Some (aux_substs env substs))
 163     | Ident (name, Some substs) -> Ident (name, Some (aux_substs env substs))
 164     | Meta (index, substs) -> Meta (index, aux_meta_substs env substs)
 165
 166     | Implicit
 167     | Ident _
 168     | Num _
 169     | Sort _
 170     | Symbol _
 171     | UserInput -> term
 172
 173     | Magic magic -> aux_magic env magic
 174     | Variable var -> aux_variable env var
 175
 176     | _ -> assert false
 177   and aux_opt env = function
 178     | Some term -> Some (aux env term)
 179     | None -> None
 180   and aux_capture_var env (name, ty_opt) = (aux env name, aux_opt env ty_opt)
 181   and aux_branch env (pattern, term) =
 182     (aux_pattern env pattern, aux env term)
 183   and aux_pattern env (head, vars) =
 184     (head, List.map (aux_capture_var env) vars)
 185   and aux_definition env (var, term, i) =
 186     (aux_capture_var env var, aux env term, i)
 187   and aux_substs env substs =
 188     List.map (fun (name, term) -> (name, aux env term)) substs
 189   and aux_meta_substs env meta_substs = List.map (aux_opt env) meta_substs
 190   and aux_variable env = function
 191     | NumVar name -> Num (lookup_num env name, 0)
 192     | IdentVar name -> Ident (lookup_string env name, None)
 193     | TermVar name -> lookup_term env name
 194     | FreshVar name -> Ident (lookup_fresh_name name, None)
 195     | Ascription (term, name) -> assert false
 196   and aux_magic env = function
 197     | Default (some_pattern, none_pattern) ->
 198         (match meta_names_of some_pattern with
 199         | [] -> assert false (* some pattern must contain at least 1 name *)
 200         | (name :: _) as names ->
 201             (match lookup_value env name with
 202             | OptValue (Some _) ->
 203                 (* assumption: if "name" above is bound to Some _, then all
 204                  * names returned by "meta_names_of" are bound to Some _ as well
 205                  *)
 206                 aux (unopt_names names env) some_pattern
 207             | OptValue None -> aux env none_pattern
 208             | _ -> assert false))
 209     | Fold (`Left, base_pattern, names, rec_pattern) ->
 210         let acc_name = List.hd names in (* names can't be empty, cfr. parser *)
 211         let meta_names =
 212           List.filter ((<>) acc_name) (meta_names_of rec_pattern)
 213         in
 214         (match meta_names with
 215         | [] -> assert false (* as above *)
 216         | (name :: _) as names ->
 217             let rec instantiate_fold_left acc env' =
 218               prerr_endline "instantiate_fold_left";
 219               match lookup_value env' name with
 220               | ListValue (_ :: _) ->
 221                   instantiate_fold_left
 222                     (let acc_binding = acc_name, (TermType, TermValue acc) in
 223                      aux (acc_binding :: head_names names env') rec_pattern)
 224                     (tail_names names env')
 225               | ListValue [] -> acc
 226               | _ -> assert false
 227             in
 228             instantiate_fold_left (aux env base_pattern) env)
 229     | Fold (`Right, base_pattern, names, rec_pattern) ->
 230         let acc_name = List.hd names in (* names can't be empty, cfr. parser *)
 231         let meta_names =
 232           List.filter ((<>) acc_name) (meta_names_of rec_pattern)
 233         in
 234         (match meta_names with
 235         | [] -> assert false (* as above *)
 236         | (name :: _) as names ->
 237             let rec instantiate_fold_right env' =
 238               prerr_endline "instantiate_fold_right";
 239               match lookup_value env' name with
 240               | ListValue (_ :: _) ->
 241                   let acc = instantiate_fold_right (tail_names names env') in
 242                   let acc_binding = acc_name, (TermType, TermValue acc) in
 243                   aux (acc_binding :: head_names names env') rec_pattern
 244               | ListValue [] -> aux env base_pattern
 245               | _ -> assert false
 246             in
 247             instantiate_fold_right env)
 248     | _ -> assert false
 249   in
 250   aux env term
 251