]> matita.cs.unibo.it Git - helm.git/blob - helm/software/components/tactics/inversion.ml
Trick: the refiner always subst-expands the outtype, so that the beta-redex
[helm.git] / 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.oblivion_ugraph in
194  let uri = baseuri_of_term termty in  
195  let o,_ = CicEnvironment.get_obj CicUniv.oblivion_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.oblivion_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.oblivion_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.oblivion_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.oblivion_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.oblivion_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 ;;