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/.
26 (* $Id: destructTactic.ml 9774 2009-05-15 19:37:08Z sacerdot $ *)
29 open Continuationals.Stack
33 if debug then (fun x -> prerr_endline (Lazy.force x)) else (fun _ -> ())
39 "z" ^ string_of_int !i
43 let id = if id = "_" then fresh_name () else id in
44 CicNotationPt.Ident (id,None)
51 | l -> CicNotationPt.Appl l
54 let rec iter f n acc =
56 else iter f (n-1) (f n acc)
59 let subst_metasenv_and_fix_names status =
60 let u,h,metasenv, subst,o = status#obj in
62 NCicUntrusted.map_obj_kind ~skip_body:true
63 (NCicUntrusted.apply_subst subst []) o
65 status#set_obj(u,h,NCicUntrusted.apply_subst_metasenv subst metasenv,subst,o)
68 (* input: nome della variabile riscritta
69 * output: lista dei nomi delle variabili il cui tipo dipende dall'input *)
70 let cascade_select_in_ctx ~subst ctx iname =
72 let lctx, rctx = HExtlib.split_nth (iname - 1) ctx in
73 let lctx = List.rev lctx in
74 let rec rm_last = function
76 | hd::tl -> hd::(rm_last tl)
79 let indices,_ = List.fold_left
80 (fun (acc,context) item ->
83 | n,(NCic.Decl s | NCic.Def (s,_))
84 when not (List.for_all (fun x -> NCicTypeChecker.does_not_occur ~subst context (x-1) x s) acc) ->
85 List.iter (fun m -> prerr_endline ("acc has " ^ (string_of_int m))) acc;
86 prerr_endline ("acc occurs in the type of " ^ n);
87 (1::List.map ((+) 1) acc, item::context)
88 | _ -> (List.map ((+) 1) acc, item::context))
91 List.iter (fun n -> prerr_endline (string_of_int n)) indices;
92 let indices = match rm_last indices with
95 let res = List.map (fun n -> let s,_ = List.nth ctx (n-1) in s) indices in
97 List.iter (fun n -> prerr_endline n) res;
98 prerr_endline (NCicPp.ppcontext ~metasenv:[] ~subst ctx);
102 let rec mk_fresh_name ctx firstch n =
103 let candidate = (String.make 1 firstch) ^ (string_of_int n) in
104 if (List.for_all (fun (s,_) -> s <> candidate) ctx) then candidate
105 else mk_fresh_name ctx firstch (n+1)
108 let arg_list nleft t =
109 let rec drop_prods n t =
112 | NCic.Prod (_,_,ta) -> drop_prods (n-1) ta
113 | _ -> raise (Failure "drop_prods")
115 let rec aux = function
116 | NCic.Prod (_,so,ta) -> so::aux ta
118 in aux (drop_prods nleft t)
121 let nargs it nleft consno =
122 prerr_endline (Printf.sprintf "nargs %d %d" nleft consno);
123 let _,indname,_,cl = it in
124 let _,_,t_k = List.nth cl consno in
125 List.length (arg_list nleft t_k) ;;
127 let default_pattern = "",0,(None,[],Some CicNotationPt.UserInput);;
129 (* returns the discrimination = injection+contradiction principle *)
130 (* FIXME: mi riservo di considerare tipi con parametri sx alla fine *)
132 let mk_discriminator it status =
134 let _,indname,_,cl = it in
137 let mk_eq tys ts us es n =
138 (* eqty = Tn u0 e0...un-1 en-1 *)
140 (List.nth tys n :: iter (fun i acc ->
145 (* params = [T0;t0;...;Tn;tn;u0;e0;un-1;en-1] *)
146 let params = iter (fun i acc ->
148 List.nth ts i :: acc) n
151 List.nth es i:: acc) (n-1) []) in
152 mk_appl [mk_id "eq"; eqty;
153 mk_appl (mk_id ("R" ^ string_of_int n) :: params);
159 let _,name,_ = List.nth cl j in
163 let branch i j ts us =
164 let nargs = nargs it nleft i in
165 let es = List.map (fun x -> mk_id ("e" ^ string_of_int x)) (HExtlib.list_seq 0 nargs) in
167 (fun x -> CicNotationPt.Implicit (`Tagged ("T" ^ (string_of_int x))))
168 (HExtlib.list_seq 0 nargs) in
171 CicNotationPt.Binder (`Lambda, (mk_id ("x" ^ string_of_int i), None),
172 CicNotationPt.Binder (`Lambda, (mk_id ("p" ^ string_of_int i), None),
174 (mk_appl [mk_id "eq"; CicNotationPt.Implicit `JustOne;
175 mk_appl (mk_id (kname it i)::
176 List.map (fun x -> mk_id ("x" ^string_of_int x))
177 (HExtlib.list_seq 0 (List.length ts)));
178 mk_appl (mk_id (kname it j)::us)])]
180 CicNotationPt.Binder (`Lambda, (mk_id "e",
183 CicNotationPt.Implicit `JustOne;
184 mk_appl (mk_id (kname it i)::ts);
185 mk_appl (mk_id (kname it j)::us)])),
186 let ts = ts @ [mk_id "e"] in
189 CicNotationPt.Implicit `JustOne;
190 mk_appl (mk_id (kname it j)::us)] in
191 let us = us @ [refl2] in
192 CicNotationPt.Binder (`Forall, (mk_id "P", Some (CicNotationPt.Sort (`NType "1") )),
194 CicNotationPt.Binder (`Forall, (mk_id "_",
195 Some (iter (fun i acc ->
196 CicNotationPt.Binder (`Forall, (List.nth es i, Some (mk_eq tys ts us es i)), acc))
198 (CicNotationPt.Binder (`Forall, (mk_id "_",
199 Some (mk_eq tys ts us es nargs)),
200 mk_id "P")))), mk_id "P")
204 let inner i ts = CicNotationPt.Case
206 Some (CicNotationPt.Binder (`Lambda, (mk_id "y",None),
207 CicNotationPt.Binder (`Forall, (mk_id "_", Some
208 (mk_appl [mk_id "eq";CicNotationPt.Implicit
209 `JustOne;(*CicNotationPt.Implicit `JustOne*)
210 mk_appl (mk_id (kname it i)::ts);mk_id "y"])),
211 CicNotationPt.Implicit `JustOne ))),
214 let nargs_kty = nargs it nleft j in
215 let us = iter (fun m acc -> mk_id ("u" ^ (string_of_int m))::acc)
216 (nargs_kty - 1) [] in
218 iter (fun _ acc -> None::acc) (nargs_kty - 1) [] in
219 CicNotationPt.Pattern (kname it j,
221 List.combine us nones),
223 (HExtlib.list_seq 0 (List.length cl)))
225 let outer = CicNotationPt.Case
227 Some (CicNotationPt.Binder (`Lambda, (mk_id "_",None),
228 (*CicNotationPt.Sort (`NType "2")*) CicNotationPt.Implicit
232 let nargs_kty = nargs it nleft i in
233 let ts = iter (fun m acc -> mk_id ("t" ^ (string_of_int m))::acc)
234 (nargs_kty - 1) [] in
236 iter (fun _ acc -> None::acc) (nargs_kty - 1) [] in
237 CicNotationPt.Pattern (kname it i,
239 List.combine ts nones),
241 (HExtlib.list_seq 0 (List.length cl))) in
242 let principle = CicNotationPt.Binder (`Lambda, (mk_id "x", Some (mk_id indname)),
243 CicNotationPt.Binder (`Lambda, (mk_id "y", Some (mk_id indname)), outer))
245 pp (lazy ("discriminator = " ^ (CicNotationPp.pp_term principle)));
250 let hd_of_term = function
251 | NCic.Appl (hd::_) -> hd
255 let name_of_rel ~context rel =
256 let s, _ = List.nth context (rel-1) in s
259 (* let lookup_in_ctx ~context n =
260 List.nth context ((List.length context) - n - 1)
263 let discriminate_tac ~context cur_eq status =
264 pp (lazy (Printf.sprintf "discriminate: equation %s" (name_of_rel ~context cur_eq)));
266 let dbranch it leftno consno =
267 prerr_endline (Printf.sprintf "dbranch %d %d" leftno consno);
268 let nlist = HExtlib.list_seq 0 (nargs it leftno consno) in
269 (* (\forall ...\forall P.\forall DH : ( ... = ... -> P). P) *)
270 let params = List.map (fun x -> prerr_endline (Printf.sprintf "dbranch param a%d" x); NTactics.intro_tac ("a" ^ string_of_int x)) nlist in
271 NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern::
273 NTactics.intro_tac "P";
274 NTactics.intro_tac "DH";
275 NTactics.apply_tac ("",0,mk_id "DH");
276 NTactics.apply_tac ("",0,mk_id "refl");
278 let dbranches it leftno =
279 prerr_endline (Printf.sprintf "dbranches %d" leftno);
281 let nbranches = List.length cl in
282 let branches = iter (fun n acc ->
283 let m = nbranches - n - 1 in
284 if m = 0 then (prerr_endline "no shift"; acc @ (dbranch it leftno m))
285 else (prerr_endline "sì shift"; acc @ NTactics.shift_tac :: (dbranch it
288 if nbranches > 1 then
289 (prerr_endline "sì branch";
290 NTactics.branch_tac:: branches @ [NTactics.merge_tac])
292 (prerr_endline "no branch";
296 let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
297 let _,ctx' = HExtlib.split_nth cur_eq context in
298 let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
299 let status, s = term_of_cic_term status s ctx' in
300 let status, leftno, it =
301 let it, t1, t2 = match s with
302 | NCic.Appl [_;it;t1;t2] -> it,t1,t2
303 | _ -> assert false in
304 (* XXX: serve? ho già fatto whd *)
305 let status, it = whd status ctx' (mk_cic_term ctx' it) in
306 let status, it = term_of_cic_term status it ctx' in
307 let _uri,indtyno,its = match it with
308 NCic.Const (NReference.Ref (uri, NReference.Ind (_,indtyno,_)) as r) ->
309 uri, indtyno, NCicEnvironment.get_checked_indtys r
310 | _ -> prerr_endline ("discriminate: indty =" ^ NCicPp.ppterm
311 ~metasenv:[] ~subst:[] ~context:[] it) ; assert false in
312 let _,leftno,its,_,_ = its in
313 status, leftno, List.nth its indtyno
318 let status, discr = mk_discriminator it status in
319 NTactics.cut_tac ("",0, CicNotationPt.Binder (`Forall, (mk_id "x", None),
320 CicNotationPt.Binder (`Forall, (mk_id "y", None),
321 CicNotationPt.Binder (`Forall, (mk_id "e",
322 Some (mk_appl [mk_id "eq";CicNotationPt.Implicit `JustOne; mk_id "x"; mk_id "y"])),
323 mk_appl [discr; mk_id "x"; mk_id "y";
327 NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern;
328 NTactics.intro_tac "x";
329 NTactics.intro_tac "y";
330 NTactics.intro_tac "Deq";
331 NTactics.rewrite_tac ~dir:`RightToLeft ~what:("",0,mk_id "Deq") ~where:default_pattern;
332 NTactics.cases_tac ~what:("",0,mk_id "x") ~where:default_pattern]
333 @ dbranches it leftno @
335 NTactics.intro_tac "#discriminate";
336 NTactics.apply_tac ("",0,mk_appl [mk_id "#discriminate";
337 CicNotationPt.Implicit `JustOne;
338 CicNotationPt.Implicit `JustOne; mk_id eq_name ]);
339 NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern;
340 NTactics.clear_tac ["#discriminate"];
345 let subst_tac ~context ~dir cur_eq =
347 let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
348 let _,ctx' = HExtlib.split_nth cur_eq context in
349 let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
350 let status, s = term_of_cic_term status s ctx' in
351 pp (lazy (Printf.sprintf "subst: equation %s" eq_name));
352 let l, r = match s with
353 | NCic.Appl [_;_;t1;t2] -> t1,t2
354 | _ -> assert false in
355 let var = match dir with
357 | `RightToLeft -> r in
358 let var = match var with
360 | _ -> assert false in
361 let names_to_gen, _ =
362 cascade_select_in_ctx ~subst:(get_subst status) context (var+cur_eq) in
364 NTactics.generalize_tac
365 ~where:("",0,(Some (mk_id x),[], Some CicNotationPt.UserInput)) in
366 NTactics.block_tac ((List.map gen_tac names_to_gen)@
367 [NTactics.clear_tac names_to_gen;
368 NTactics.rewrite_tac ~dir
369 ~what:("",0,mk_id eq_name) ~where:default_pattern;
370 NTactics.reduce_tac ~reduction:(`Normalize true)
371 ~where:default_pattern;
372 NTactics.clear_tac [eq_name]]@
373 (List.map NTactics.intro_tac (List.rev names_to_gen))) status
376 let get_ctx st goal =
377 ctx_of (get_goalty st goal)
380 (* = select + classify *)
381 let select_eq ctx acc status goal =
382 let classify ~subst ctx' l r =
383 (* FIXME: metasenv *)
384 if NCicReduction.are_convertible ~metasenv:[] ~subst ctx' l r
385 then status, `Identity
386 else status, (match hd_of_term l, hd_of_term r with
387 | NCic.Const (NReference.Ref (_,NReference.Con (_,ki,nleft)) as kref),
388 NCic.Const (NReference.Ref (_,NReference.Con (_,kj,_))) ->
389 if ki != kj then `Discriminate (0,true)
391 let rit = NReference.mk_indty true kref in
392 let _,_,its,_,itno = NCicEnvironment.get_checked_indtys rit in
393 let it = List.nth its itno in
394 let newprods = (nargs it nleft (ki-1)) + 1 in
395 `Discriminate (newprods, false)
397 when NCicTypeChecker.does_not_occur ~subst ctx' (j-1) j r ->
400 when NCicTypeChecker.does_not_occur ~subst ctx' (j-1) j l ->
402 | (NCic.Rel _, _ | _, NCic.Rel _ ) -> `Cycle
406 let index = List.length ctx - i in
407 match (List.nth ctx (index - 1)) with
408 | n, (NCic.Decl ty | NCic.Def (ty,_)) ->
409 (let _,ctx_ty = HExtlib.split_nth index ctx in
410 let status, ty = NTacStatus.whd status ctx_ty (mk_cic_term ctx_ty ty) in
411 let status, ty = term_of_cic_term status ty ctx_ty in
412 pp (lazy (Printf.sprintf "select_eq tries %s" (NCicPp.ppterm ~context:ctx_ty ~subst:[] ~metasenv:[] ty)));
414 | NCic.Appl [NCic.Const (NReference.Ref (u,_)) ;_;l;r] when NUri.name_of_uri u = "eq" ->
415 (let status, kind = classify ~subst:(get_subst status) ctx_ty l r in
418 let status, goalty = term_of_cic_term status (get_goalty status goal) ctx in
419 if NCicTypeChecker.does_not_occur ~subst:(get_subst status) ctx (index - 1) index goalty
420 then status, Some (List.length ctx - i), kind
422 | `Cycle | `Blob -> aux (i+1) (* XXX: skip cyclic/blob equations for now *)
424 if (List.for_all (fun x -> x <> n) acc) then
425 status, Some (List.length ctx - i), kind
428 with Failure _ | Invalid_argument _ -> status, None, `Blob
432 let rec destruct_tac0 nprods acc status goal =
433 let ctx = get_ctx status goal in
434 let subst = get_subst status in
435 let get_newgoal os ns ogoal =
436 let go, gc = NTactics.compare_statuses ~past:os ~present:ns in
437 let go' = ([ogoal] @- gc) @+ go in
438 match go' with [] -> assert false | g::_ -> g
440 let status, selection, kind = select_eq ctx acc status goal in
441 pp (lazy ("destruct: acc is " ^ String.concat "," acc ));
442 match selection, kind with
444 pp (lazy (Printf.sprintf "destruct: nprods is %d, no selection, context is %s" nprods (NCicPp.ppcontext ~metasenv:[] ~subst ctx)));
446 let status' = NTactics.exec (NTactics.intro_tac (mk_fresh_name ctx 'e' 0)) status goal in
447 destruct_tac0 (nprods-1) acc status' (get_newgoal status status' goal)
450 | Some cur_eq, `Discriminate (newprods,conflict) ->
451 pp (lazy (Printf.sprintf "destruct: discriminate - nprods is %d, selection is %d, context is %s" nprods cur_eq (NCicPp.ppcontext ~metasenv:[] ~subst ctx)));
452 let status' = NTactics.exec (discriminate_tac ~context:ctx cur_eq) status goal in
453 if conflict then status'
454 else destruct_tac0 (nprods+newprods)
455 (name_of_rel ~context:ctx cur_eq::acc) status' (get_newgoal status status' goal)
456 | Some cur_eq, `Subst dir ->
457 pp (lazy (Printf.sprintf "destruct: subst - nprods is %d, selection is %d, context is %s" nprods cur_eq (NCicPp.ppcontext ~metasenv:[] ~subst ctx)));
458 let status' = NTactics.exec (subst_tac ~context:ctx ~dir cur_eq) status goal in
459 pp (lazy (Printf.sprintf " ctx after subst = %s" (NCicPp.ppcontext ~metasenv:[] ~subst (get_ctx status' (get_newgoal status status' goal)))));
460 let eq_name,_ = List.nth ctx (cur_eq-1) in
461 destruct_tac0 nprods (List.filter (fun x -> x <> eq_name) acc) status' (get_newgoal status status' goal)
462 | Some cur_eq, `Identity ->
463 pp (lazy (Printf.sprintf "destruct: identity - nprods is %d, selection is %d, context is %s" nprods cur_eq (NCicPp.ppcontext ~metasenv:[] ~subst ctx)));
464 let eq_name,_ = List.nth ctx (cur_eq-1) in
465 let status' = NTactics.exec (NTactics.clear_tac [eq_name]) status goal in
466 destruct_tac0 nprods (List.filter (fun x -> x <> eq_name) acc) status' (get_newgoal status status' goal)
467 | Some cur_eq, `Cycle -> (* TODO, should never happen *)
468 pp (lazy (Printf.sprintf "destruct: cycle - nprods is %d, selection is %d, context is %s" nprods cur_eq (NCicPp.ppcontext ~metasenv:[] ~subst ctx)));
470 | Some cur_eq, `Blob ->
471 pp (lazy (Printf.sprintf "destruct: blob - nprods is %d, selection is %d, context is %s" nprods cur_eq (NCicPp.ppcontext ~metasenv:[] ~subst ctx)));
475 let destruct_tac s = NTactics.distribute_tac (destruct_tac0 0 []) s;;