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
  36 let inside_obj = function
  37     | Cic.InductiveDefinition (l,params, nleft, _) ->
  38       (l,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
  52 (* prende il numero dei parametri sinistri, la lista dei parametri, la lista
  53 dei tipi dei parametri, il tipo del GOAL e costruisce il termine per la cut
  54 ossia DX1 = DX1 -> ... DXn=DXn -> GOALTY *)
  55
  56 let rec foo_cut nleft l param_ty_l body uri_of_eq =
  57  if nleft > 0 then foo_cut (nleft-1) (List.tl l)  (List.tl param_ty_l) body
  58   uri_of_eq
  59  else   match l with
  60   | hd::tl -> Cic.Prod (Cic.Anonymous, Cic.Appl[Cic.MutInd (uri_of_eq  ,0,[]);
  61   (List.hd param_ty_l) ; hd; hd], foo_cut nleft
  62   (List.map (CicSubstitution.lift 1) tl) (List.tl param_ty_l)
  63   (CicSubstitution.lift 1 body) uri_of_eq )
  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 let rec cut_first n l =
  76  if n>0 then
  77   match l with
  78   | hd::tl -> cut_first (n-1) tl
  79   | [] -> []
  80   else l
  81 ;;
  82
  83
  84 let rec cut_last l =
  85 match l with
  86  | hd::tl when tl != [] -> hd:: (cut_last tl)
  87  | _ -> []
  88 ;;
  89
  90
  91 let foo_appl nleft nright_consno term uri =
  92  let l = [] in
  93  let a = ref l in
  94  for n = 1 to nleft do
  95         a := !a @ [(Cic.Implicit None)]
  96  done;
  97  a:= !a @ [term];
  98  for n = 1 to nright_consno do
  99         a := !a @ [(Cic.Implicit None)]
 100  done;
 101  Cic.Appl ([Cic.Const(uri,[])] @ !a @ [Cic.Rel 1]) (*L'ipotesi e' sempre Rel 1. (?)  *)
 102 ;;
 103
 104
 105 let rec foo_prod nright param_ty_l l l2 base_rel body uri_of_eq nleft termty
 106  isSetType term =
 107   match param_ty_l with
 108    | hd::tl -> Cic.Prod (
 109     Cic.Anonymous,
 110     Cic.Appl[Cic.MutInd(uri_of_eq,0,[]); hd; (List.hd l); Cic.Rel base_rel],
 111     foo_prod (nright-1) tl (List.map (CicSubstitution.lift 1) (List.tl l))
 112      (List.map (CicSubstitution.lift 1) l2)
 113      base_rel (CicSubstitution.lift 1 body)
 114      uri_of_eq nleft (CicSubstitution.lift 1 termty)
 115      isSetType (CicSubstitution.lift 1 term))
 116    | [] -> ProofEngineReduction.replace_lifting
 117     ~equality:(ProofEngineReduction.alpha_equivalence)
 118     ~what: (if isSetType
 119      then ((cut_first (1+nleft) (term_to_list termty) ) @ [term] )
 120      else (cut_first (1+nleft) (term_to_list termty) ) )
 121     ~with_what: (List.map (CicSubstitution.lift (-1)) l2)
 122     ~where:body
 123 (*TODO lo stesso sottotermine di body puo' essere sia sx che dx!*)
 124 ;;
 125
 126 let rec foo_lambda nright param_ty_l nright_ param_ty_l_ l l2 base_rel body
 127  uri_of_eq nleft termty isSetType ty_indty term =
 128  (*assert nright >0 *)
 129   match param_ty_l with
 130    | hd::tl ->Cic.Lambda (
 131     (Cic.Name ("lambda" ^ (string_of_int nright))),
 132     hd, (* typ *)
 133     foo_lambda (nright-1) tl nright_ param_ty_l_
 134      (List.map (CicSubstitution.lift 1) l)
 135      (List.map (CicSubstitution.lift 1) (l2 @ [Cic.Rel 1]))
 136      base_rel (CicSubstitution.lift 1 body)
 137      uri_of_eq nleft
 138      (CicSubstitution.lift 1 termty)
 139      isSetType ty_indty
 140      (CicSubstitution.lift 1 term))
 141    | [] when isSetType -> Cic.Lambda (
 142     (Cic.Name ("lambda" ^ (string_of_int nright))),
 143     (ProofEngineReduction.replace_lifting
 144      ~equality:(ProofEngineReduction.alpha_equivalence)
 145      ~what: (cut_first (1+nleft) (term_to_list termty) )
 146      ~with_what: (List.map (CicSubstitution.lift (-1)) l2)
 147      ~where:termty), (* tipo di H con i parametri destri sostituiti *)
 148     foo_prod nright_ param_ty_l_ (List.map (CicSubstitution.lift 1) l)
 149      (List.map (CicSubstitution.lift 1) (l2 @ [Cic.Rel 1]))
 150      (base_rel+1) (CicSubstitution.lift 1 body)
 151      uri_of_eq nleft
 152      (CicSubstitution.lift 1 termty) isSetType
 153      (CicSubstitution.lift 1 term))
 154    | [] -> foo_prod nright_ param_ty_l_ l l2 base_rel body uri_of_eq nleft
 155     termty isSetType term
 156 ;;
 157
 158 let inversion_tac ~term =
 159  let module T = CicTypeChecker in
 160  let module R = CicReduction in
 161  let module C = Cic in
 162  let module P = PrimitiveTactics in
 163  let module PET = ProofEngineTypes in
 164  let module PEH = ProofEngineHelpers in
 165  let inversion_tac ~term (proof, goal) =
 166  let (_,metasenv,_,_) = proof in
 167  let metano,context,ty = CicUtil.lookup_meta goal metasenv in
 168  let (newproof, metasenv') = PEH.subst_meta_in_proof proof metano term [] in
 169  let uri_of_eq = HelmLibraryObjects.Logic.eq_URI in
 170
 171  (* dall'indice che indentifica il goal nel metasenv, ritorna il suo tipo, che
 172  e' la terza componente della relativa congettura *)
 173  let (_,_,body) = CicUtil.lookup_meta goal metasenv in
 174  (* estrae il tipo del termine(ipotesi) oggetto di inversion,
 175  di solito un Cic.Appl *)
 176  let termty,_ = T.type_of_aux' metasenv context term CicUniv.empty_ugraph in
 177  let uri = baseuri_of_term termty in
 178  let o,_ = CicEnvironment.get_obj CicUniv.empty_ugraph uri in
 179  let l,params,nleft = inside_obj o in
 180  let (_,_,typeno,_) =
 181   match termty with
 182    C.MutInd (uri,typeno,exp_named_subst) -> (uri,exp_named_subst,typeno,[])
 183    | C.Appl ((C.MutInd (uri,typeno,exp_named_subst))::args) ->
 184     (uri,exp_named_subst,typeno,args)
 185    | _ -> raise NotAnInductiveTypeToEliminate
 186  in
 187  let eliminator_uri =
 188   let buri = UriManager.buri_of_uri uri in
 189   let name =
 190    match o with
 191     C.InductiveDefinition (tys,_,_,_) ->
 192      let (name,_,_,_) = List.nth tys typeno in
 193      name
 194     |_ -> assert false
 195   in
 196   let ext = "_ind" in
 197   UriManager.uri_of_string (buri ^ "/" ^ name ^ ext ^ ".con")
 198  in
 199  (* il tipo del tipo induttivo da cui viene l'ipotesi oggetto di inversione *)
 200  let (_,_,ty_indty,cons_list) = (List.hd l) in
 201  (*la lista di Cic.term ricavata dal tipo del tipo induttivo. *)
 202  let param_ty_l = list_of_prod ty_indty in
 203  let consno = List.length cons_list in
 204  let nright= (List.length param_ty_l)- (nleft+1) in
 205  let isSetType = ((Pervasives.compare
 206   (List.nth param_ty_l ((List.length param_ty_l)-1))
 207   (Cic.Sort Cic.Prop)) != 0)
 208  in
 209  (* eliminiamo la testa di termty, in quanto e' il nome del predicato e non un parametro.*)
 210  let cut_term = foo_cut nleft (List.tl (term_to_list termty))
 211   (list_of_prod ty_indty)  body uri_of_eq in
 212  (* cut DXn=DXn \to GOAL *)
 213  let proof1,gl1 = PET.apply_tactic (P.cut_tac cut_term) (proof,goal) in
 214  (* apply Hcut ; reflexivity (su tutti i goals aperti da apply_tac) *)
 215  let proof2, gl2 = PET.apply_tactic
 216   (Tacticals.then_
 217    ~start: (P.apply_tac (C.Rel 1)) (* apply Hcut *)
 218    ~continuation: (EqualityTactics.reflexivity_tac)
 219   ) (proof1, (List.hd gl1))
 220  in
 221  (* apply (ledx_ind( lambda x. lambda y, ...)) *)
 222  let (t1,metasenv,t3,t4) = proof2 in
 223  let goal2 = List.hd (List.tl gl1) in
 224  let (metano,context,_) = CicUtil.lookup_meta goal2 metasenv in
 225  let cut_param_ty_l = (cut_first nleft (cut_last param_ty_l)) in
 226  (* la lista dei soli parametri destri *)
 227  let l= cut_first (1+nleft) (term_to_list termty) in
 228  let lambda_t = foo_lambda nright cut_param_ty_l nright cut_param_ty_l l []
 229   nright body uri_of_eq nleft termty isSetType ty_indty term in
 230  let t = foo_appl nleft (nright+consno) lambda_t eliminator_uri  in
 231  debug_print (lazy ("Lambda_t: " ^ (CicPp.ppterm t)));
 232  debug_print (lazy ("Term: " ^ (CicPp.ppterm termty)));
 233  debug_print (lazy ("Body: " ^ (CicPp.ppterm body)));
 234  debug_print (lazy ("Right param: " ^ (CicPp.ppterm (Cic.Appl l))));
 235
 236  let (ref_t,_,metasenv'',_) = CicRefine.type_of_aux' metasenv context t
 237   CicUniv.empty_ugraph
 238  in
 239  let proof2 = (t1,metasenv'',t3,t4) in
 240  let proof3,gl3 = PET.apply_tactic (P.apply_tac ref_t) (proof2, goal2) in
 241  let new_goals = ProofEngineHelpers.compare_metasenvs
 242   ~oldmetasenv:metasenv ~newmetasenv:metasenv''
 243  in
 244  let patched_new_goals =
 245   let (_,metasenv''',_,_) = proof3 in
 246   List.filter (function i -> List.exists (function (j,_,_) -> j=i) metasenv''')
 247    new_goals @ gl3
 248  in
 249  (*prerr_endline ("METASENV: " ^ CicMetaSubst.ppmetasenv metasenv []); DEBUG*)
 250  (proof3, patched_new_goals)
 251 in
 252 ProofEngineTypes.mk_tactic (inversion_tac ~term)
 253 ;;