helm/ocaml/cic_notation/cicNotationEnv.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 CicNotationPt
  27
  28 exception Value_not_found of string
  29
  30 type value =
  31   | TermValue of term
  32   | StringValue of string
  33   | NumValue of string
  34   | OptValue of value option
  35   | ListValue of value list
  36
  37 type value_type =
  38   | TermType
  39   | StringType
  40   | NumType
  41   | OptType of value_type
  42   | ListType of value_type
  43
  44 type declaration = string * value_type
  45 type binding = string * (value_type * value)
  46 type env_type = (string * (value_type * value)) list
  47
  48 let lookup_value ~env name =
  49   try
  50     snd (List.assoc name env)
  51   with Not_found -> raise (Value_not_found name)
  52
  53 let lookup_term ~env name =
  54   match lookup_value ~env name with
  55   | TermValue x -> x
  56   | _ -> raise (Value_not_found name)
  57
  58 let lookup_num ~env name =
  59   match lookup_value ~env name with
  60   | NumValue x -> x
  61   | _ -> raise (Value_not_found name)
  62
  63 let lookup_string ~env name =
  64   match lookup_value ~env name with
  65   | StringValue x -> x
  66   | _ -> raise (Value_not_found name)
  67
  68 let unopt_names names env =
  69   let rec aux acc = function
  70     | (name, (ty, v)) :: tl when List.mem name names ->
  71         (match ty, v with
  72         | OptType ty, OptValue (Some v) -> aux ((name, (ty, v)) :: acc) tl
  73         | _ -> assert false)
  74     | _ :: tl -> aux acc tl
  75       (* some pattern may contain only meta names, thus we trash all others *)
  76     | [] -> acc
  77   in
  78   aux [] env
  79
  80 let head_names names env =
  81   let rec aux acc = function
  82     | (name, (ty, v)) :: tl when List.mem name names ->
  83         (match ty, v with
  84         | ListType ty, ListValue (v :: _) -> aux ((name, (ty, v)) :: acc) tl
  85         | _ -> assert false)
  86     | _ :: tl -> aux acc tl
  87       (* base pattern may contain only meta names, thus we trash all others *)
  88     | [] -> acc
  89   in
  90   aux [] env
  91
  92 let tail_names names env =
  93   let rec aux acc = function
  94     | (name, (ty, v)) :: tl when List.mem name names ->
  95         (match ty, v with
  96         | ListType ty, ListValue (_ :: vtl) ->
  97             aux ((name, (ListType ty, ListValue vtl)) :: acc) tl
  98         | _ -> assert false)
  99     | binding :: tl -> aux (binding :: acc) tl
 100     | [] -> acc
 101   in
 102   aux [] env
 103
 104 let opt_binding_some (n, (ty, v)) = (n, (OptType ty, OptValue (Some v)))
 105 let opt_binding_none (n, (ty, v)) = (n, (OptType ty, OptValue None))
 106 let opt_binding_of_name (n, ty) = (n, (OptType ty, OptValue None))
 107 let list_binding_of_name (n, ty) = (n, (ListType ty, ListValue []))
 108 let opt_declaration (n, ty) = (n, OptType ty)
 109 let list_declaration (n, ty) = (n, ListType ty)
 110
 111   (* TODO ensure that names generated by fresh_var do not clash with user's *)
 112 let fresh_var =
 113   let index = ref ~-1 in
 114   fun () ->
 115     incr index;
 116     "fresh" ^ string_of_int !index
 117
 118 let meta_names_of term =
 119   let rec names = ref [] in
 120   let add_name n =
 121     if List.mem n !names then ()
 122     else names := n :: !names
 123   in
 124   let rec aux = function
 125     | AttributedTerm (_, term) -> aux term
 126     | Appl terms -> List.iter aux terms
 127     | Binder (_, _, body) -> aux body
 128     | Case (term, indty, outty_opt, patterns) ->
 129         aux term ;
 130         aux_opt outty_opt ;
 131         List.iter aux_branch patterns
 132     | LetIn (_, t1, t2) ->
 133         aux t1 ;
 134         aux t2
 135     | LetRec (_, definitions, body) ->
 136         List.iter aux_definition definitions ;
 137         aux body
 138     | Uri (_, Some substs) -> aux_substs substs
 139     | Ident (_, Some substs) -> aux_substs substs
 140     | Meta (_, substs) -> aux_meta_substs substs
 141
 142     | Implicit
 143     | Ident _
 144     | Num _
 145     | Sort _
 146     | Symbol _
 147     | Uri _
 148     | UserInput -> ()
 149
 150     | Magic magic -> aux_magic magic
 151     | Variable var -> aux_variable var
 152
 153     | _ -> assert false
 154   and aux_opt = function
 155     | Some term -> aux term
 156     | None -> ()
 157   and aux_capture_var (_, ty_opt) = aux_opt ty_opt
 158   and aux_branch (pattern, term) =
 159     aux_pattern pattern ;
 160     aux term
 161   and aux_pattern (head, vars) =
 162     List.iter aux_capture_var vars
 163   and aux_definition (var, term, i) =
 164     aux_capture_var var ;
 165     aux term
 166   and aux_substs substs = List.iter (fun (_, term) -> aux term) substs
 167   and aux_meta_substs meta_substs = List.iter aux_opt meta_substs
 168   and aux_variable = function
 169     | NumVar name -> add_name name
 170     | IdentVar name -> add_name name
 171     | TermVar name -> add_name name
 172     | FreshVar _ -> ()
 173     | Ascription _ -> assert false
 174   and aux_magic = function
 175     | Default (t1, t2)
 176     | Fold (_, t1, _, t2) ->
 177         aux t1 ;
 178         aux t2
 179     | _ -> assert false
 180   in
 181   aux term ;
 182   !names
 183
 184 let pp_term = ref (fun (t:CicNotationPt.term)  -> assert false; "")
 185 let set_pp_term f = pp_term := f
 186
 187 let instantiate ~env term =
 188   let fresh_env = ref [] in
 189   let lookup_fresh_name n =
 190     try
 191       List.assoc n !fresh_env
 192     with Not_found ->
 193       let new_name = fresh_var () in
 194       fresh_env := (n, new_name) :: !fresh_env;
 195       new_name
 196   in
 197   let rec aux env term =
 198     match term with
 199     | AttributedTerm (_, term) -> aux env term
 200     | Appl terms -> Appl (List.map (aux env) terms)
 201     | Binder (binder, var, body) ->
 202         Binder (binder, aux_capture_var env var, aux env body)
 203     | Case (term, indty, outty_opt, patterns) ->
 204         Case (aux env term, indty, aux_opt env outty_opt,
 205           List.map (aux_branch env) patterns)
 206     | LetIn (var, t1, t2) ->
 207         LetIn (aux_capture_var env var, aux env t1, aux env t2)
 208     | LetRec (kind, definitions, body) ->
 209         LetRec (kind, List.map (aux_definition env) definitions, aux env body)
 210     | Uri (name, None) -> Uri (name, None)
 211     | Uri (name, Some substs) -> Uri (name, Some (aux_substs env substs))
 212     | Ident (name, Some substs) -> Ident (name, Some (aux_substs env substs))
 213     | Meta (index, substs) -> Meta (index, aux_meta_substs env substs)
 214
 215     | Implicit
 216     | Ident _
 217     | Num _
 218     | Sort _
 219     | Symbol _
 220     | UserInput -> term
 221
 222     | Magic magic -> aux_magic env magic
 223     | Variable var -> aux_variable env var
 224
 225     | _ -> assert false
 226   and aux_opt env = function
 227     | Some term -> Some (aux env term)
 228     | None -> None
 229   and aux_capture_var env (name, ty_opt) = (aux env name, aux_opt env ty_opt)
 230   and aux_branch env (pattern, term) =
 231     (aux_pattern env pattern, aux env term)
 232   and aux_pattern env (head, vars) =
 233     (head, List.map (aux_capture_var env) vars)
 234   and aux_definition env (var, term, i) =
 235     (aux_capture_var env var, aux env term, i)
 236   and aux_substs env substs =
 237     List.map (fun (name, term) -> (name, aux env term)) substs
 238   and aux_meta_substs env meta_substs = List.map (aux_opt env) meta_substs
 239   and aux_variable env = function
 240     | NumVar name -> Num (lookup_num ~env name, 0)
 241     | IdentVar name -> Ident (lookup_string ~env name, None)
 242     | TermVar name -> lookup_term ~env name
 243     | FreshVar name -> Ident (lookup_fresh_name name, None)
 244     | Ascription (term, name) -> assert false
 245   and aux_magic env = function
 246     | Default (some_pattern, none_pattern) ->
 247         (match meta_names_of some_pattern with
 248         | [] -> assert false (* some pattern must contain at least 1 name *)
 249         | (name :: _) as names ->
 250             (match lookup_value ~env name with
 251             | OptValue (Some _) ->
 252                 (* assumption: if "name" above is bound to Some _, then all
 253                  * names returned by "meta_names_of" are bound to Some _ as well
 254                  *)
 255                 aux (unopt_names names env) some_pattern
 256             | OptValue None -> aux env none_pattern
 257             | _ -> assert false))
 258     | Fold (`Left, base_pattern, names, rec_pattern) ->
 259         let acc_name = List.hd names in (* names can't be empty, cfr. parser *)
 260         let meta_names =
 261           List.filter ((<>) acc_name) (meta_names_of rec_pattern)
 262         in
 263         (match meta_names with
 264         | [] -> assert false (* as above *)
 265         | (name :: _) as names ->
 266             let rec instantiate_fold_left acc env' =
 267               prerr_endline "instantiate_fold_left";
 268               match lookup_value ~env:env' name with
 269               | ListValue (_ :: _) ->
 270                   instantiate_fold_left
 271                     (let acc_binding = acc_name, (TermType, TermValue acc) in
 272                      aux (acc_binding :: head_names names env') rec_pattern)
 273                     (tail_names names env')
 274               | ListValue [] -> acc
 275               | _ -> assert false
 276             in
 277             instantiate_fold_left (aux env base_pattern) env)
 278     | Fold (`Right, base_pattern, names, rec_pattern) ->
 279         let acc_name = List.hd names in (* names can't be empty, cfr. parser *)
 280         let meta_names =
 281           List.filter ((<>) acc_name) (meta_names_of rec_pattern)
 282         in
 283         (match meta_names with
 284         | [] -> assert false (* as above *)
 285         | (name :: _) as names ->
 286             let rec instantiate_fold_right env' =
 287               prerr_endline "instantiate_fold_right";
 288               match lookup_value ~env:env' name with
 289               | ListValue (_ :: _) ->
 290                   let acc = instantiate_fold_right (tail_names names env') in
 291                   let acc_binding = acc_name, (TermType, TermValue acc) in
 292                   aux (acc_binding :: head_names names env') rec_pattern
 293               | ListValue [] -> aux env base_pattern
 294               | _ -> assert false
 295             in
 296             instantiate_fold_right env)
 297     | _ -> assert false
 298   in
 299   aux env term
 300