helm/ocaml/cic_notation/cicNotationFwd.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 Printf
  27
  28 open CicNotationEnv
  29 open CicNotationPt
  30
  31 (* XXX ZACK: switched to CicNotationUtil.names_of_term, commented code below to
  32  * be removes as soon as we believe implementation are equivalent *)
  33 (* let meta_names_of term =
  34   let rec names = ref [] in
  35   let add_name n =
  36     if List.mem n !names then ()
  37     else names := n :: !names
  38   in
  39   let rec aux = function
  40     | AttributedTerm (_, term) -> aux term
  41     | Appl terms -> List.iter aux terms
  42     | Binder (_, _, body) -> aux body
  43     | Case (term, indty, outty_opt, patterns) ->
  44         aux term ;
  45         aux_opt outty_opt ;
  46         List.iter aux_branch patterns
  47     | LetIn (_, t1, t2) ->
  48         aux t1 ;
  49         aux t2
  50     | LetRec (_, definitions, body) ->
  51         List.iter aux_definition definitions ;
  52         aux body
  53     | Uri (_, Some substs) -> aux_substs substs
  54     | Ident (_, Some substs) -> aux_substs substs
  55     | Meta (_, substs) -> aux_meta_substs substs
  56
  57     | Implicit
  58     | Ident _
  59     | Num _
  60     | Sort _
  61     | Symbol _
  62     | Uri _
  63     | UserInput -> ()
  64
  65     | Magic magic -> aux_magic magic
  66     | Variable var -> aux_variable var
  67
  68     | _ -> assert false
  69   and aux_opt = function
  70     | Some term -> aux term
  71     | None -> ()
  72   and aux_capture_var (_, ty_opt) = aux_opt ty_opt
  73   and aux_branch (pattern, term) =
  74     aux_pattern pattern ;
  75     aux term
  76   and aux_pattern (head, vars) =
  77     List.iter aux_capture_var vars
  78   and aux_definition (var, term, i) =
  79     aux_capture_var var ;
  80     aux term
  81   and aux_substs substs = List.iter (fun (_, term) -> aux term) substs
  82   and aux_meta_substs meta_substs = List.iter aux_opt meta_substs
  83   and aux_variable = function
  84     | NumVar name -> add_name name
  85     | IdentVar name -> add_name name
  86     | TermVar name -> add_name name
  87     | FreshVar _ -> ()
  88     | Ascription _ -> assert false
  89   and aux_magic = function
  90     | Default (t1, t2)
  91     | Fold (_, t1, _, t2) ->
  92         aux t1 ;
  93         aux t2
  94     | _ -> assert false
  95   in
  96   aux term ;
  97   !names *)
  98
  99 let unopt_names names env =
 100   let rec aux acc = function
 101     | (name, (ty, v)) :: tl when List.mem name names ->
 102         (match ty, v with
 103         | OptType ty, OptValue (Some v) -> aux ((name, (ty, v)) :: acc) tl
 104         | _ -> assert false)
 105     | _ :: tl -> aux acc tl
 106       (* some pattern may contain only meta names, thus we trash all others *)
 107     | [] -> acc
 108   in
 109   aux [] env
 110
 111 let head_names names env =
 112   let rec aux acc = function
 113     | (name, (ty, v)) :: tl when List.mem name names ->
 114         (match ty, v with
 115         | ListType ty, ListValue (v :: _) -> aux ((name, (ty, v)) :: acc) tl
 116         | _ -> assert false)
 117     | _ :: tl -> aux acc tl
 118       (* base pattern may contain only meta names, thus we trash all others *)
 119     | [] -> acc
 120   in
 121   aux [] env
 122
 123 let tail_names names env =
 124   let rec aux acc = function
 125     | (name, (ty, v)) :: tl when List.mem name names ->
 126         (match ty, v with
 127         | ListType ty, ListValue (_ :: vtl) ->
 128             aux ((name, (ListType ty, ListValue vtl)) :: acc) tl
 129         | _ -> assert false)
 130     | binding :: tl -> aux (binding :: acc) tl
 131     | [] -> acc
 132   in
 133   aux [] env
 134
 135 let instantiate_level2 env term =
 136   let fresh_env = ref [] in
 137   let lookup_fresh_name n =
 138     try
 139       List.assoc n !fresh_env
 140     with Not_found ->
 141       let new_name = CicNotationUtil.fresh_name () in
 142       fresh_env := (n, new_name) :: !fresh_env;
 143       new_name
 144   in
 145   let rec aux env term =
 146     match term with
 147     | AttributedTerm (_, term) -> aux env term
 148     | Appl terms -> Appl (List.map (aux env) terms)
 149     | Binder (binder, var, body) ->
 150         Binder (binder, aux_capture_var env var, aux env body)
 151     | Case (term, indty, outty_opt, patterns) ->
 152         Case (aux env term, indty, aux_opt env outty_opt,
 153           List.map (aux_branch env) patterns)
 154     | LetIn (var, t1, t2) ->
 155         LetIn (aux_capture_var env var, aux env t1, aux env t2)
 156     | LetRec (kind, definitions, body) ->
 157         LetRec (kind, List.map (aux_definition env) definitions, aux env body)
 158     | Uri (name, None) -> Uri (name, None)
 159     | Uri (name, Some substs) -> Uri (name, Some (aux_substs env substs))
 160     | Ident (name, Some substs) -> Ident (name, Some (aux_substs env substs))
 161     | Meta (index, substs) -> Meta (index, aux_meta_substs env substs)
 162
 163     | Implicit
 164     | Ident _
 165     | Num _
 166     | Sort _
 167     | Symbol _
 168     | UserInput -> term
 169
 170     | Magic magic -> aux_magic env magic
 171     | Variable var -> aux_variable env var
 172
 173     | _ -> assert false
 174   and aux_opt env = function
 175     | Some term -> Some (aux env term)
 176     | None -> None
 177   and aux_capture_var env (name, ty_opt) = (aux env name, aux_opt env ty_opt)
 178   and aux_branch env (pattern, term) =
 179     (aux_pattern env pattern, aux env term)
 180   and aux_pattern env (head, vars) =
 181     (head, List.map (aux_capture_var env) vars)
 182   and aux_definition env (var, term, i) =
 183     (aux_capture_var env var, aux env term, i)
 184   and aux_substs env substs =
 185     List.map (fun (name, term) -> (name, aux env term)) substs
 186   and aux_meta_substs env meta_substs = List.map (aux_opt env) meta_substs
 187   and aux_variable env = function
 188     | NumVar name -> Num (lookup_num env name, 0)
 189     | IdentVar name -> Ident (lookup_string env name, None)
 190     | TermVar name -> lookup_term env name
 191     | FreshVar name -> Ident (lookup_fresh_name name, None)
 192     | Ascription (term, name) -> assert false
 193   and aux_magic env = function
 194     | Default (some_pattern, none_pattern) ->
 195         (match CicNotationUtil.names_of_term some_pattern with
 196         | [] -> assert false (* some pattern must contain at least 1 name *)
 197         | (name :: _) as names ->
 198             (match lookup_value env name with
 199             | OptValue (Some _) ->
 200                 (* assumption: if "name" above is bound to Some _, then all
 201                  * names returned by "meta_names_of" are bound to Some _ as well
 202                  *)
 203                 aux (unopt_names names env) some_pattern
 204             | OptValue None -> aux env none_pattern
 205             | _ -> assert false))
 206     | Fold (`Left, base_pattern, names, rec_pattern) ->
 207         let acc_name = List.hd names in (* names can't be empty, cfr. parser *)
 208         let meta_names =
 209           List.filter ((<>) acc_name)
 210             (CicNotationUtil.names_of_term rec_pattern)
 211         in
 212         (match meta_names with
 213         | [] -> assert false (* as above *)
 214         | (name :: _) as names ->
 215             let rec instantiate_fold_left acc env' =
 216               match lookup_value env' name with
 217               | ListValue (_ :: _) ->
 218                   instantiate_fold_left
 219                     (let acc_binding = acc_name, (TermType, TermValue acc) in
 220                      aux (acc_binding :: head_names names env') rec_pattern)
 221                     (tail_names names env')
 222               | ListValue [] -> acc
 223               | _ -> assert false
 224             in
 225             instantiate_fold_left (aux env base_pattern) env)
 226     | Fold (`Right, base_pattern, names, rec_pattern) ->
 227         let acc_name = List.hd names in (* names can't be empty, cfr. parser *)
 228         let meta_names =
 229           List.filter ((<>) acc_name)
 230             (CicNotationUtil.names_of_term rec_pattern)
 231         in
 232         (match meta_names with
 233         | [] -> assert false (* as above *)
 234         | (name :: _) as names ->
 235             let rec instantiate_fold_right env' =
 236               match lookup_value env' name with
 237               | ListValue (_ :: _) ->
 238                   let acc = instantiate_fold_right (tail_names names env') in
 239                   let acc_binding = acc_name, (TermType, TermValue acc) in
 240                   aux (acc_binding :: head_names names env') rec_pattern
 241               | ListValue [] -> aux env base_pattern
 242               | _ -> assert false
 243             in
 244             instantiate_fold_right env)
 245     | If (_, p_true, p_false) as t -> aux env (CicNotationUtil.find_branch (Magic t))
 246     | Fail -> assert false
 247     | _ -> assert false
 248   in
 249   aux env term
 250
 251 let instantiate_appl_pattern env appl_pattern =
 252   let lookup name =
 253     try List.assoc name env
 254     with Not_found ->
 255       prerr_endline (sprintf "Name %s not found" name);
 256       assert false
 257   in
 258   let rec aux = function
 259     | UriPattern uri -> CicUtil.term_of_uri uri
 260     | ImplicitPattern -> Cic.Implicit None
 261     | VarPattern name -> lookup name
 262     | ApplPattern terms -> Cic.Appl (List.map aux terms)
 263   in
 264   aux appl_pattern
 265