helm/software/components/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
  36 let inside_obj = function
  37  | Cic.InductiveDefinition (type_list,params, nleft, _) ->
  38   (type_list,params,nleft)
  39  | _ -> raise (Invalid_argument "Errore in inside_obj")
  40
  41 let term_to_list = function
  42  | Cic.Appl l -> l
  43  | _ -> raise (Invalid_argument "Errore in term_to_list")
  44
  45
  46 let rec baseuri_of_term = function
  47  | Cic.Appl l -> baseuri_of_term (List.hd l)
  48  | Cic.MutInd (baseuri, tyno, []) -> baseuri
  49  | _ -> raise (Invalid_argument "baseuri_of_term")
  50
  51 (* returns DX1 = DX1 -> ... DXn=DXn -> GOALTY *)
  52 let rec foo_cut nleft parameters parameters_ty body uri_of_eq =
  53  if nleft > 0
  54  then
  55   foo_cut (nleft-1) (List.tl parameters)  (List.tl parameters_ty) body
  56    uri_of_eq
  57  else
  58   match parameters with
  59    | hd::tl ->
  60     Cic.Prod (
  61      Cic.Anonymous,
  62      Cic.Appl[Cic.MutInd (uri_of_eq  ,0,[]);
  63       (List.hd parameters_ty) ; hd; hd],
  64      foo_cut nleft (List.map (CicSubstitution.lift 1) tl)
  65       (List.map (CicSubstitution.lift 1) (List.tl parameters_ty))
  66       (CicSubstitution.lift 1 body) uri_of_eq )
  67    | [] -> body
  68 ;;
  69
  70 (* from a complex Cic.Prod term, return the list of its components *)
  71 let rec get_sort_type term =
  72  match term with
  73   | Cic.Prod (_,src,tgt) -> (get_sort_type tgt)
  74   | _ -> term
  75 ;;
  76
  77
  78 let rec cut_first n l =
  79  if n>0 then
  80   match l with
  81    | hd::tl -> cut_first (n-1) tl
  82    | [] -> []
  83  else l
  84 ;;
  85
  86
  87 let rec cut_last l =
  88  match l with
  89   | hd::tl when tl != [] -> hd:: (cut_last tl)
  90   | _ -> []
  91 ;;
  92
  93 (* returns the term to apply*)
  94 let foo_appl nleft nright_consno term uri =
  95  let l = [] in
  96  let a = ref l in
  97  for n = 1 to nleft do
  98         a := !a @ [(Cic.Implicit None)]
  99  done;
 100  a:= !a @ [term];
 101  for n = 1 to nright_consno do
 102         a := !a @ [(Cic.Implicit None)]
 103  done;
 104  (*  apply     i_ind           ? ... ?    H *)
 105  Cic.Appl ([Cic.Const(uri,[])] @ !a @ [Cic.Rel 1])
 106 ;;
 107
 108
 109 let rec foo_prod nright right_param_tys rightparameters l2 base_rel goalty
 110  uri_of_eq rightparameters_ termty isSetType term =
 111   match right_param_tys with
 112    | hd::tl -> Cic.Prod (
 113     Cic.Anonymous,
 114     Cic.Appl
 115      [Cic.MutInd(uri_of_eq,0,[]); hd; (List.hd rightparameters);
 116      Cic.Rel base_rel],
 117     foo_prod (nright-1)
 118      (List.map (CicSubstitution.lift 1) tl)
 119      (List.map (CicSubstitution.lift 1) (List.tl rightparameters))
 120      (List.map (CicSubstitution.lift 1) l2)
 121      base_rel (CicSubstitution.lift 1 goalty) uri_of_eq
 122      (List.map (CicSubstitution.lift 1) rightparameters_)
 123      (CicSubstitution.lift 1 termty)
 124      isSetType (CicSubstitution.lift 1 term))
 125    | [] -> ProofEngineReduction.replace_lifting
 126     ~equality:(fun _ -> CicUtil.alpha_equivalence)
 127     ~context:[]
 128     ~what: (if isSetType
 129      then (rightparameters_ @ [term] )
 130      else (rightparameters_ ) )
 131     ~with_what: (List.map (CicSubstitution.lift (-1)) l2)
 132     ~where:goalty
 133 (* the same subterm of goalty could be simultaneously sx and dx!*)
 134 ;;
 135
 136 let rec foo_lambda nright right_param_tys nright_ right_param_tys_
 137  rightparameters created_vars base_rel goalty uri_of_eq rightparameters_
 138  termty isSetType term =
 139   match right_param_tys with
 140    | hd::tl -> Cic.Lambda (
 141     (Cic.Name ("lambda" ^ (string_of_int nright))),
 142     hd, (* type *)
 143     foo_lambda (nright-1)
 144      (List.map (CicSubstitution.lift 1) tl) nright_
 145      (List.map (CicSubstitution.lift 1) right_param_tys_)
 146      (List.map (CicSubstitution.lift 1) rightparameters)
 147      (List.map (CicSubstitution.lift 1) (created_vars @ [Cic.Rel 1]))
 148      base_rel (CicSubstitution.lift 1 goalty) uri_of_eq
 149      (List.map (CicSubstitution.lift 1) rightparameters_)
 150      (CicSubstitution.lift 1 termty) isSetType
 151      (CicSubstitution.lift 1 term))
 152    | [] when isSetType -> Cic.Lambda (
 153     (Cic.Name ("lambda" ^ (string_of_int nright))),
 154     (ProofEngineReduction.replace_lifting
 155      ~equality:(fun _ -> CicUtil.alpha_equivalence)
 156      ~context:[]
 157      ~what: (rightparameters_ )
 158      ~with_what: (List.map (CicSubstitution.lift (-1)) created_vars)
 159      ~where:termty), (* type of H with replaced right parameters *)
 160     foo_prod nright_ (List.map (CicSubstitution.lift 1) right_param_tys_)
 161      (List.map (CicSubstitution.lift 1) rightparameters)
 162      (List.map (CicSubstitution.lift 1) (created_vars @ [Cic.Rel 1]))
 163      (base_rel+1) (CicSubstitution.lift 1 goalty) uri_of_eq
 164      (List.map (CicSubstitution.lift 1) rightparameters_)
 165      (CicSubstitution.lift 1 termty) isSetType
 166      (CicSubstitution.lift 1 term))
 167    | [] -> foo_prod nright_ right_param_tys_ rightparameters created_vars
 168    base_rel goalty uri_of_eq rightparameters_
 169     termty isSetType term
 170 ;;
 171
 172 let isSetType paramty = ((Pervasives.compare
 173   (get_sort_type paramty)
 174   (Cic.Sort Cic.Prop)) != 0)
 175
 176 exception EqualityNotDefinedYet
 177 let private_inversion_tac ~term =
 178  let module T = CicTypeChecker in
 179  let module R = CicReduction in
 180  let module C = Cic in
 181  let module P = PrimitiveTactics in
 182  let module PET = ProofEngineTypes in
 183  let private_inversion_tac ~term (proof, goal) =
 184
 185  (*DEBUG*) debug_print (lazy  ("private inversion begins"));
 186  let _,metasenv,_subst,_,_, _ = proof in
 187  let uri_of_eq =
 188   match LibraryObjects.eq_URI () with
 189      None -> raise EqualityNotDefinedYet
 190   | Some uri -> uri
 191  in
 192  let (_,context,goalty) = CicUtil.lookup_meta goal metasenv in
 193  let termty,_ = T.type_of_aux' metasenv context term CicUniv.empty_ugraph in
 194  let uri = baseuri_of_term termty in
 195  let o,_ = CicEnvironment.get_obj CicUniv.empty_ugraph uri in
 196  let (_,_,typeno,_) =
 197   match termty with
 198    C.MutInd (uri,typeno,exp_named_subst) -> (uri,exp_named_subst,typeno,[])
 199    | C.Appl ((C.MutInd (uri,typeno,exp_named_subst))::args) ->
 200     (uri,exp_named_subst,typeno,args)
 201    | _ -> raise NotAnInductiveTypeToEliminate
 202  in
 203  let buri = UriManager.buri_of_uri uri in
 204  let name,nleft,paramty,cons_list =
 205   match o with
 206    C.InductiveDefinition (tys,_,nleft,_) ->
 207     let (name,_,paramty,cons_list) = List.nth tys typeno in
 208     (name,nleft,paramty,cons_list)
 209    |_ -> assert false
 210  in
 211  let eliminator_uri =
 212   UriManager.uri_of_string (buri ^ "/" ^ name ^ "_ind" ^ ".con")
 213  in
 214  let parameters = (List.tl (term_to_list termty)) in
 215  let parameters_tys =
 216   (List.map
 217    (fun t -> (
 218     match (T.type_of_aux' metasenv context t CicUniv.empty_ugraph) with
 219      (term,graph) -> term))
 220    parameters)
 221  in
 222  let consno = List.length cons_list in
 223  let nright= ((List.length parameters)- nleft) in
 224  let isSetType = isSetType paramty in
 225  let cut_term = foo_cut nleft parameters
 226   parameters_tys goalty uri_of_eq in
 227  (*DEBUG*)  debug_print (lazy ("cut term " ^ CicPp.ppterm cut_term));
 228   debug_print (lazy ("CONTEXT before apply HCUT: " ^
 229    (CicMetaSubst.ppcontext ~metasenv [] context )));
 230   debug_print (lazy ("termty " ^ CicPp.ppterm termty));
 231  (* cut DXn=DXn \to GOAL *)
 232  let proof1,gl1 = PET.apply_tactic (P.cut_tac cut_term) (proof,goal) in
 233  (* apply Hcut ; reflexivity  *)
 234  let proof2, gl2 = PET.apply_tactic
 235   (Tacticals.then_
 236    ~start: (P.apply_tac (C.Rel 1)) (* apply Hcut *)
 237    ~continuation: (EqualityTactics.reflexivity_tac)
 238   ) (proof1, (List.hd gl1))
 239  in
 240  (*DEBUG*) debug_print (lazy  ("after apply HCUT;reflexivity
 241   in private inversion"));
 242  (* apply (ledx_ind( lambda x. lambda y, ...)) *)
 243  let t1,metasenv,_subst,t3,t4, attrs = proof2 in
 244  let goal2 = List.hd (List.tl gl1) in
 245  let (_,context,_) = CicUtil.lookup_meta goal2 metasenv in
 246  (* rightparameters type list *)
 247  let rightparam_ty_l = (cut_first nleft parameters_tys) in
 248  (* rightparameters list *)
 249  let rightparameters= cut_first nleft parameters in
 250  let lambda_t = foo_lambda nright rightparam_ty_l nright rightparam_ty_l
 251  rightparameters [] nright goalty uri_of_eq rightparameters termty isSetType
 252  term in
 253  let t = foo_appl nleft (nright+consno) lambda_t eliminator_uri in
 254  debug_print (lazy ("Lambda_t: " ^ (CicPp.ppterm t)));
 255  debug_print (lazy ("Term: " ^ (CicPp.ppterm termty)));
 256  debug_print (lazy ("Body: " ^ (CicPp.ppterm goalty)));
 257  debug_print
 258   (lazy ("Right param: " ^ (CicPp.ppterm (Cic.Appl rightparameters))));
 259  debug_print (lazy ("CONTEXT before refinement: " ^
 260   (CicMetaSubst.ppcontext ~metasenv [] context )));
 261   (*DEBUG*) debug_print (lazy  ("private inversion: term before refinement: " ^
 262    CicPp.ppterm t));
 263  let (ref_t,_,metasenv'',_) = CicRefine.type_of_aux' metasenv context t
 264   CicUniv.empty_ugraph
 265  in
 266  (*DEBUG*) debug_print (lazy  ("private inversion: termine after refinement: "
 267   ^ CicPp.ppterm ref_t));
 268  let proof2 = (t1,metasenv'',_subst,t3,t4, attrs) in
 269  let my_apply_tac =
 270   let my_apply_tac status =
 271    let proof,goals =
 272     ProofEngineTypes.apply_tactic (P.apply_tac ref_t) status in
 273    let patched_new_goals =
 274     let (_,metasenv''',_subst,_,_, _) = proof in
 275     let new_goals = ProofEngineHelpers.compare_metasenvs
 276      ~oldmetasenv:metasenv ~newmetasenv:metasenv''
 277     in
 278     List.filter (function i -> List.exists (function (j,_,_) -> j=i)
 279      metasenv''') new_goals @ goals
 280    in
 281    proof,patched_new_goals
 282   in
 283  ProofEngineTypes.mk_tactic my_apply_tac
 284  in
 285  let proof3,gl3 =
 286  PET.apply_tactic
 287   (Tacticals.then_
 288    ~start:my_apply_tac
 289    ~continuation:
 290     (ReductionTactics.simpl_tac (ProofEngineTypes.conclusion_pattern(None))))
 291     (proof2,goal2)
 292  in
 293
 294  (proof3, gl3)
 295 in
 296 ProofEngineTypes.mk_tactic (private_inversion_tac ~term)
 297 ;;
 298
 299
 300 let inversion_tac ~term =
 301  let module T = CicTypeChecker in
 302  let module R = CicReduction in
 303  let module C = Cic in
 304  let module P = PrimitiveTactics in
 305  let module PET = ProofEngineTypes in
 306  let inversion_tac ~term (proof, goal) =
 307  (*DEBUG*) debug_print (lazy ("inversion begins"));
 308   let _,metasenv,_subst,_,_, _ = proof in
 309   let (_,context,goalty) = CicUtil.lookup_meta goal metasenv in
 310   let termty,_ = T.type_of_aux' metasenv context term CicUniv.empty_ugraph in
 311   let uri, typeno =
 312     match termty with
 313       | Cic.MutInd (uri,typeno,_)
 314       | Cic.Appl(Cic.MutInd (uri,typeno,_)::_) -> uri,typeno
 315       | _ -> assert false
 316   in
 317   (* let uri = baseuri_of_term termty in *)
 318   let obj,_ = CicEnvironment.get_obj CicUniv.empty_ugraph uri in
 319   let name,nleft,arity,cons_list =
 320    match obj with
 321     Cic.InductiveDefinition (tys,_,nleft,_) ->
 322      let (name,_,arity,cons_list) = List.nth tys typeno in
 323         (name,nleft,arity,cons_list)
 324    |_ -> assert false
 325   in
 326   let buri = UriManager.buri_of_uri uri in
 327   let inversor_uri =
 328    UriManager.uri_of_string (buri ^ "/" ^ name ^ "_inv" ^ ".con") in
 329   (* arity length = number  of parameters plus 1 *)
 330   let arity_length = (List.length (term_to_list termty)) in
 331   (* Check the existence of any right parameter. *)
 332   assert (arity_length > (nleft + 1));
 333   let appl_term arity_consno uri =
 334    let l = [] in
 335    let a = ref l in
 336    for n = 1 to arity_consno do
 337     a := (Cic.Implicit None)::(!a)
 338    done;
 339    (* apply    i_inv             ? ...?      H).     *)
 340    Cic.Appl ([Cic.Const(uri,[])] @ !a @ [term])
 341   in
 342   let t = appl_term (arity_length + (List.length cons_list)) inversor_uri in
 343   let (t1,metasenv,_subst,t3,t4, attrs) = proof in
 344   let (ref_t,_,metasenv'',_) = CicRefine.type_of_aux' metasenv context t
 345   CicUniv.empty_ugraph
 346   in
 347   let proof = (t1,metasenv'',_subst,t3,t4, attrs) in
 348   let proof3,gl3 =
 349      ProofEngineTypes.apply_tactic (P.apply_tac ref_t) (proof,goal) in
 350   let patched_new_goals =
 351      let (_,metasenv''',_subst,_,_, _) = proof3 in
 352      let new_goals = ProofEngineHelpers.compare_metasenvs
 353       ~oldmetasenv:metasenv ~newmetasenv:metasenv''
 354      in
 355      List.filter (function i -> List.exists (function (j,_,_) -> j=i)
 356       metasenv''') new_goals @ gl3
 357     in
 358   (proof3, patched_new_goals)
 359  in
 360 ProofEngineTypes.mk_tactic (inversion_tac ~term)
 361 ;;