helm/ocaml/tactics/inversion.ml

   1 (* Copyright (C) 2002, 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://cs.unibo.it/helm/.
  24  *)
  25
  26 (* $Id$ *)
  27
  28 exception TheTypeOfTheCurrentGoalIsAMetaICannotChooseTheRightElimiantionPrinciple
  29 exception NotAnInductiveTypeToEliminate
  30
  31 let debug = false;;
  32 let debug_print =
  33  fun msg -> if debug then prerr_endline (Lazy.force msg) else ()
  34
  35 let inside_obj = function
  36     | Cic.InductiveDefinition (l,params, nleft, _) ->
  37       (l,params,nleft)
  38     | _ -> raise (Invalid_argument "Errore in inside_obj")
  39
  40 let term_to_list = function
  41         | Cic.Appl l -> l
  42         | _ -> raise (Invalid_argument "Errore in term_to_list")
  43
  44
  45 let rec baseuri_of_term = function
  46   | Cic.Appl l -> baseuri_of_term (List.hd l)
  47   | Cic.MutInd (baseuri, tyno, []) -> baseuri
  48   | _ -> raise (Invalid_argument "baseuri_of_term")
  49
  50
  51 (*prende il numero dei parametri sinistri, la lista dei parametri, la lista dei tipi dei parametri,
  52 il tipo del GOAL e costruisce il termine per la cut ossia DX1 = DX1 -> ... DXn=DXn -> GOALTY *)
  53 let rec foo_cut nleft l param_ty_l body uri_of_eq =
  54
  55         if nleft >0 then foo_cut (nleft-1) (List.tl l)  (List.tl param_ty_l) body uri_of_eq
  56          else   match l with
  57                 | hd::tl -> Cic.Prod (Cic.Anonymous,
  58                                 Cic.Appl[Cic.MutInd (uri_of_eq  ,0,[]);
  59                                         (List.hd param_ty_l) ;
  60                                         hd;
  61                                         hd],
  62                                 foo_cut nleft (List.map (CicSubstitution.lift 1) tl) (List.tl param_ty_l) (CicSubstitution.lift 1 body) uri_of_eq
  63                         )
  64                 | [] -> body
  65  ;;
  66
  67 (* da una catena di prod costruisce una lista dei termini che lo compongono.*)
  68 let rec list_of_prod term =
  69 match term with
  70  | Cic.Prod (Cic.Anonymous,src,tgt) -> [src] @ (list_of_prod tgt)
  71  | _ -> [term]
  72
  73 ;;
  74
  75
  76 let rec cut_first n l =
  77  if n>0 then
  78   match l with
  79   | hd::tl -> cut_first (n-1) tl
  80   | [] -> []
  81   else l
  82 ;;
  83
  84
  85 let rec cut_last l =
  86 match l with
  87  | hd::tl when tl != [] -> hd:: (cut_last tl)
  88  | _ -> []
  89 ;;
  90
  91
  92 let foo_appl nleft nright_consno term uri =
  93  let l = [] in
  94  let a = ref l in
  95
  96  for n = 1 to nleft do
  97         a := !a @ [(Cic.Implicit None)]
  98
  99  done;
 100  a:= !a @ [term];
 101
 102  for n = 1 to nright_consno do
 103         a := !a @ [(Cic.Implicit None)]
 104  done;
 105  Cic.Appl ([Cic.Const(uri,[])] @ !a @ [Cic.Rel 1]) (*L'ipotesi e' sempre Rel 1. (?)  *)
 106 ;;
 107
 108
 109
 110 let rec foo_prod nright param_ty_l l l2 base_rel body uri_of_eq nleft termty isSetType term =
 111  match param_ty_l with
 112         | hd::tl -> Cic.Prod (Cic.Anonymous,
 113                         Cic.Appl[Cic.MutInd(uri_of_eq,0,[]);
 114                                 hd;
 115                                 (List.hd l);
 116                                 Cic.Rel base_rel
 117                         ],
 118                         foo_prod (nright-1) tl (List.map (CicSubstitution.lift 1) (List.tl l))
 119                                 (List.map (CicSubstitution.lift 1) l2)
 120                                 base_rel
 121                                 (CicSubstitution.lift 1 body)
 122                                 uri_of_eq nleft
 123                                 (CicSubstitution.lift 1 termty)
 124                                 isSetType
 125                                 (CicSubstitution.lift 1 term))
 126
 127
 128         | [] ->  ProofEngineReduction.replace_lifting ~equality:(ProofEngineReduction.alpha_equivalence)
 129                                                         ~what: (if isSetType then ((cut_first (1+nleft) (term_to_list termty) ) @ [term] )
 130                                                                 else (cut_first (1+nleft) (term_to_list termty) ) )
 131                                                         ~with_what: (List.map (CicSubstitution.lift (-1)) l2)
 132                                                         ~where:body
 133                                                         (*TODO lo stesso sottotermine di body puo' essere sia sx che dx!*)
 134 ;;
 135
 136
 137 let rec foo_lambda nright param_ty_l nright_ param_ty_l_ l l2 base_rel body uri_of_eq nleft termty isSetType ty_indty term =
 138  (*assert nright >0 *)
 139   match param_ty_l with
 140         | hd::tl ->Cic.Lambda ((Cic.Name ("lambda" ^ (string_of_int nright))),
 141                                 hd, (* typ *)
 142                                 foo_lambda      (nright-1) tl
 143                                                 nright_ param_ty_l_
 144                                                 (List.map (CicSubstitution.lift 1) l)
 145                                                 (List.map (CicSubstitution.lift 1) (l2 @ [Cic.Rel 1]))
 146                                                 base_rel
 147                                                 (CicSubstitution.lift 1 body)
 148                                                 uri_of_eq nleft
 149                                                 (CicSubstitution.lift 1 termty)
 150                                                 isSetType ty_indty
 151                                                 (CicSubstitution.lift 1 term))
 152         | [] when isSetType -> Cic.Lambda (
 153                                         (Cic.Name ("lambda" ^ (string_of_int nright))),
 154                                         (ProofEngineReduction.replace_lifting   ~equality:(ProofEngineReduction.alpha_equivalence)
 155                                                                                  ~what: (cut_first (1+nleft) (term_to_list termty) )
 156                                                                                  ~with_what: (List.map (CicSubstitution.lift (-1)) l2)
 157                                                                                  ~where:termty), (* tipo di H con i parametri destri sostituiti *)
 158                                         foo_prod nright_ param_ty_l_
 159                                                 (List.map (CicSubstitution.lift 1) l)
 160                                                 (List.map (CicSubstitution.lift 1) (l2 @ [Cic.Rel 1]))
 161                                                 (base_rel+1) (CicSubstitution.lift 1 body)
 162                                                 uri_of_eq nleft
 163                                                 (CicSubstitution.lift 1 termty) isSetType
 164                                                 (CicSubstitution.lift 1 term))
 165         | [] -> foo_prod nright_ param_ty_l_ l l2
 166                         base_rel body uri_of_eq
 167                         nleft termty isSetType term
 168 ;;
 169
 170
 171
 172 let inversion_tac ~term =
 173  let module T = CicTypeChecker in
 174  let module R = CicReduction in
 175  let module C = Cic in
 176  let module P = PrimitiveTactics in
 177  let module PET = ProofEngineTypes in
 178  let inversion_tac ~term (proof, goal) =
 179  let (_,metasenv,_,_) = proof in
 180  let metano,context,ty = CicUtil.lookup_meta goal metasenv in
 181  let (newproof, metasenv') = ProofEngineHelpers.subst_meta_in_proof proof metano term [] in
 182  let uri_of_eq = HelmLibraryObjects.Logic.eq_URI in
 183
 184 (* dall'indice che indentifica il goal nel metasenv, ritorna il suo tipo, che e' la terza componente
 185 della relativa congettura *)
 186 let (_,_,body) = CicUtil.lookup_meta goal metasenv in
 187
 188 (* estrae il tipo del termine oggetto di inversion, di solito un Cic.Appl list, ma..*)
 189
 190  let termty,_ = CicTypeChecker.type_of_aux' metasenv context term CicUniv.empty_ugraph in
 191  let uri = baseuri_of_term termty in
 192  let o,_ = CicEnvironment.get_obj CicUniv.empty_ugraph uri in
 193  let l,params,nleft = inside_obj o in
 194  let (_,_,typeno,_) =
 195        match termty with
 196                C.MutInd (uri,typeno,exp_named_subst) -> (uri,exp_named_subst,typeno,[])
 197                | C.Appl ((C.MutInd (uri,typeno,exp_named_subst))::args) ->
 198                                (uri,exp_named_subst,typeno,args)
 199                | _ -> raise NotAnInductiveTypeToEliminate
 200  in
 201
 202  let eliminator_uri =
 203
 204         let buri = UriManager.buri_of_uri uri in
 205         let name =
 206                 match o with
 207                         C.InductiveDefinition (tys,_,_,_) ->
 208                                 let (name,_,_,_) = List.nth tys typeno in
 209                                 name
 210                         |_ -> assert false
 211         in
 212
 213
 214 (*      let ty_ty,_ = T.type_of_aux' metasenv context termty CicUniv.empty_ugraph in
 215         let ext =
 216                 match ty_ty with
 217                         C.Sort C.Prop -> "_ind"
 218                         | C.Sort C.Set  -> "_rec"
 219                         | C.Sort C.CProp -> "_rec"
 220                         | C.Sort (C.Type _)-> "_rect"
 221                         | C.Meta (_,_) -> raise TheTypeOfTheCurrentGoalIsAMetaICannotChooseTheRightElimiantionPrinciple
 222                         | _ -> assert false
 223         in
 224 *)
 225
 226         let ext = "_ind" in
 227         UriManager.uri_of_string (buri ^ "/" ^ name ^ ext ^ ".con")
 228 in
 229
 230  (* il tipo del tipo induttivo oggetto di inversione *)
 231
 232  let (_,_,ty_indty,cons_list) = (List.hd l) in
 233  (*la lista ricavata dal tipo del tipo induttivo. *)
 234  let param_ty_l = list_of_prod ty_indty in
 235  let consno = List.length cons_list in
 236  let nright= (List.length param_ty_l)- (nleft+1) in
 237
 238  let isSetType = ((Pervasives.compare
 239                         (List.nth param_ty_l ((List.length param_ty_l)-1))
 240                         (Cic.Sort Cic.Prop)
 241                         ) != 0) in
 242
 243
 244
 245
 246 (* eliminiamo la testa di termty, in quanto e' il nome del predicato e non un parametro.*)
 247 let cut_term = foo_cut nleft (List.tl (term_to_list termty)) (list_of_prod ty_indty)  body uri_of_eq in
 248
 249
 250
 251 (* cut DXn=DXn \to GOAL *)
 252 let proof1,gl1 = PET.apply_tactic (P.cut_tac cut_term) (proof,goal) in
 253
 254 (* apply Hcut ; reflexivity (su tutti i goals aperti da apply_tac) *)
 255 let proof2, gl2 =       PET.apply_tactic
 256                                         (Tacticals.then_
 257                                                 ~start: (P.apply_tac (C.Rel 1)
 258                                                 ) (* apply Hcut *)
 259                                                 ~continuation: (EqualityTactics.reflexivity_tac
 260                                                 )
 261                                         )
 262                                         (proof1, (List.hd gl1))
 263
 264  in
 265
 266
 267
 268 (* apply (ledx_ind( lambda x. lambda y, ...)) *)
 269
 270 let (t1,metasenv,t3,t4) = proof2 in
 271 let goal2 = List.hd (List.tl gl1) in
 272 let (metano,context,_) = CicUtil.lookup_meta goal2 metasenv in
 273
 274 let cut_param_ty_l = (cut_first nleft (cut_last param_ty_l)) in
 275
 276 (* la lista dei soli parametri destri *)
 277 let l= cut_first (1+nleft) (term_to_list termty) in
 278
 279 let lambda_t = foo_lambda nright cut_param_ty_l nright cut_param_ty_l l [] nright body uri_of_eq nleft termty isSetType ty_indty term in
 280 let t = foo_appl nleft (nright+consno) lambda_t eliminator_uri  in
 281
 282 debug_print (lazy ("Lambda_t: " ^ (CicPp.ppterm t)));
 283 prerr_endline ("Term: " ^ (CicPp.ppterm termty));
 284 prerr_endline ("Body: " ^ (CicPp.ppterm body));
 285 prerr_endline ("Right param: " ^ (CicPp.ppterm (Cic.Appl l)));
 286
 287
 288
 289
 290
 291
 292 let (ref_t,_,metasenv'',_) = CicRefine.type_of_aux' metasenv context t CicUniv.empty_ugraph in
 293
 294 let proof2 = (t1,metasenv'',t3,t4) in
 295
 296 let proof3,gl3 = PET.apply_tactic       (P.apply_tac ref_t)
 297                                         (proof2, goal2) in
 298
 299 let new_goals =
 300             ProofEngineHelpers.compare_metasenvs
 301              ~oldmetasenv:metasenv ~newmetasenv:metasenv''
 302            in
 303
 304 let patched_new_goals =
 305               let (_,metasenv''',_,_) = proof3 in
 306                List.filter
 307                 (function i -> List.exists (function (j,_,_) -> j=i) metasenv'''
 308                 ) new_goals @ gl3
 309              in
 310
 311
 312
 313
 314 (*prerr_endline ("METASENV: " ^ CicMetaSubst.ppmetasenv metasenv []); DEBUG*)
 315
 316
 317 (proof3, patched_new_goals)
 318
 319 in
 320
 321 ProofEngineTypes.mk_tactic (inversion_tac ~term)
 322 ;;