1 (* Copyright (C) 2002, HELM Team.
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.
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.
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.
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,
22 * For details, see the HELM World-Wide-Web page,
23 * http://cs.unibo.it/helm/.
28 exception TheTypeOfTheCurrentGoalIsAMetaICannotChooseTheRightElimiantionPrinciple
29 exception NotAnInductiveTypeToEliminate
33 fun msg -> if debug then prerr_endline (Lazy.force msg) else ()
35 let inside_obj = function
36 | Cic.InductiveDefinition (l,params, nleft, _) ->
38 | _ -> raise (Invalid_argument "Errore in inside_obj")
40 let term_to_list = function
42 | _ -> raise (Invalid_argument "Errore in term_to_list")
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")
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 =
55 if nleft >0 then foo_cut (nleft-1) (List.tl l) (List.tl param_ty_l) body uri_of_eq
57 | hd::tl -> Cic.Prod (Cic.Anonymous,
58 Cic.Appl[Cic.MutInd (uri_of_eq ,0,[]);
59 (List.hd param_ty_l) ;
62 foo_cut nleft (List.map (CicSubstitution.lift 1) tl) (List.tl param_ty_l) (CicSubstitution.lift 1 body) uri_of_eq
67 (* da una catena di prod costruisce una lista dei termini che lo compongono.*)
68 let rec list_of_prod term =
70 | Cic.Prod (Cic.Anonymous,src,tgt) -> [src] @ (list_of_prod tgt)
76 let rec cut_first n l =
79 | hd::tl -> cut_first (n-1) tl
87 | hd::tl when tl != [] -> hd:: (cut_last tl)
92 let foo_appl nleft nright_consno term uri =
97 a := !a @ [(Cic.Implicit None)]
102 for n = 1 to nright_consno do
103 a := !a @ [(Cic.Implicit None)]
105 Cic.Appl ([Cic.Const(uri,[])] @ !a @ [Cic.Rel 1]) (*L'ipotesi e' sempre Rel 1. (?) *)
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,[]);
118 foo_prod (nright-1) tl (List.map (CicSubstitution.lift 1) (List.tl l))
119 (List.map (CicSubstitution.lift 1) l2)
121 (CicSubstitution.lift 1 body)
123 (CicSubstitution.lift 1 termty)
125 (CicSubstitution.lift 1 term))
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)
133 (*TODO lo stesso sottotermine di body puo' essere sia sx che dx!*)
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))),
142 foo_lambda (nright-1) tl
144 (List.map (CicSubstitution.lift 1) l)
145 (List.map (CicSubstitution.lift 1) (l2 @ [Cic.Rel 1]))
147 (CicSubstitution.lift 1 body)
149 (CicSubstitution.lift 1 termty)
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)
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
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
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
188 (* estrae il tipo del termine oggetto di inversion, di solito un Cic.Appl list, ma..*)
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
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
204 let buri = UriManager.buri_of_uri uri in
207 C.InductiveDefinition (tys,_,_,_) ->
208 let (name,_,_,_) = List.nth tys typeno in
214 (* let ty_ty,_ = T.type_of_aux' metasenv context termty CicUniv.empty_ugraph in
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
227 UriManager.uri_of_string (buri ^ "/" ^ name ^ ext ^ ".con")
230 (* il tipo del tipo induttivo oggetto di inversione *)
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
238 let isSetType = ((Pervasives.compare
239 (List.nth param_ty_l ((List.length param_ty_l)-1))
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
251 (* cut DXn=DXn \to GOAL *)
252 let proof1,gl1 = PET.apply_tactic (P.cut_tac cut_term) (proof,goal) in
254 (* apply Hcut ; reflexivity (su tutti i goals aperti da apply_tac) *)
255 let proof2, gl2 = PET.apply_tactic
257 ~start: (P.apply_tac (C.Rel 1)
259 ~continuation: (EqualityTactics.reflexivity_tac
262 (proof1, (List.hd gl1))
268 (* apply (ledx_ind( lambda x. lambda y, ...)) *)
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
274 let cut_param_ty_l = (cut_first nleft (cut_last param_ty_l)) in
276 (* la lista dei soli parametri destri *)
277 let l= cut_first (1+nleft) (term_to_list termty) in
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
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)));
292 let (ref_t,_,metasenv'',_) = CicRefine.type_of_aux' metasenv context t CicUniv.empty_ugraph in
294 let proof2 = (t1,metasenv'',t3,t4) in
296 let proof3,gl3 = PET.apply_tactic (P.apply_tac ref_t)
300 ProofEngineHelpers.compare_metasenvs
301 ~oldmetasenv:metasenv ~newmetasenv:metasenv''
304 let patched_new_goals =
305 let (_,metasenv''',_,_) = proof3 in
307 (function i -> List.exists (function (j,_,_) -> j=i) metasenv'''
314 (*prerr_endline ("METASENV: " ^ CicMetaSubst.ppmetasenv metasenv []); DEBUG*)
317 (proof3, patched_new_goals)
321 ProofEngineTypes.mk_tactic (inversion_tac ~term)