helm/software/components/ng_tactics/nDestructTac.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: destructTactic.ml 9774 2009-05-15 19:37:08Z sacerdot $ *)
  27
  28 open NTacStatus
  29 open Continuationals.Stack
  30
  31 let debug = false
  32 let pp =
  33   if debug then (fun x -> prerr_endline (Lazy.force x)) else (fun _ -> ())
  34
  35 let fresh_name =
  36  let i = ref 0 in
  37  function () ->
  38   incr i;
  39   "z" ^ string_of_int !i
  40 ;;
  41
  42 let mk_id id =
  43  let id = if id = "_" then fresh_name () else id in
  44   CicNotationPt.Ident (id,None)
  45 ;;
  46
  47 let mk_appl =
  48  function
  49     [] -> assert false
  50   | [x] -> x
  51   | l -> CicNotationPt.Appl l
  52 ;;
  53
  54 let rec iter f n acc =
  55   if n < 0 then acc
  56   else iter f (n-1) (f n acc)
  57 ;;
  58
  59 let subst_metasenv_and_fix_names status =
  60   let u,h,metasenv, subst,o = status#obj in
  61   let o =
  62     NCicUntrusted.map_obj_kind ~skip_body:true
  63      (NCicUntrusted.apply_subst subst []) o
  64   in
  65    status#set_obj(u,h,NCicUntrusted.apply_subst_metasenv subst metasenv,subst,o)
  66 ;;
  67
  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 =
  71   prerr_endline "C";
  72   let lctx, rctx = HExtlib.split_nth (iname - 1) ctx in
  73   let lctx = List.rev lctx in
  74   let rec rm_last = function
  75       [] | [_] -> []
  76     | hd::tl -> hd::(rm_last tl)
  77   in
  78
  79   let indices,_ = List.fold_left
  80        (fun (acc,context) item ->
  81          prerr_endline "C2";
  82           match item with
  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))
  89        ([1], rctx) lctx in
  90     prerr_endline "C3:";
  91     List.iter (fun n -> prerr_endline (string_of_int n)) indices;
  92     let indices = match rm_last indices with
  93       | [] -> []
  94       | _::tl -> tl in
  95     let res = List.map (fun n -> let s,_ = List.nth ctx (n-1) in s) indices in
  96     prerr_endline "C4:";
  97     List.iter (fun n -> prerr_endline n) res;
  98     prerr_endline (NCicPp.ppcontext ~metasenv:[] ~subst ctx);
  99     res, indices
 100 ;;
 101
 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)
 106 ;;
 107
 108 let arg_list nleft t =
 109   let rec drop_prods n t =
 110     if n <= 0 then t
 111     else match t with
 112       | NCic.Prod (_,_,ta) -> drop_prods (n-1) ta
 113       | _ -> raise (Failure "drop_prods")
 114   in
 115   let rec aux = function
 116     | NCic.Prod (_,so,ta) -> so::aux ta
 117     | _ -> []
 118   in aux (drop_prods nleft t)
 119 ;;
 120
 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) ;;
 126
 127 let default_pattern = "",0,(None,[],Some CicNotationPt.UserInput);;
 128
 129 (* returns the discrimination = injection+contradiction principle *)
 130 (* FIXME: mi riservo di considerare tipi con parametri sx alla fine *)
 131
 132 let mk_discriminator it status =
 133   let nleft = 0 in
 134   let _,indname,_,cl = it in
 135
 136
 137   let mk_eq tys ts us es n =
 138     (* eqty = Tn u0 e0...un-1 en-1 *)
 139     let eqty = mk_appl
 140                  (List.nth tys n :: iter (fun i acc ->
 141                                            List.nth us i::
 142                                            List.nth es i:: acc)
 143                                      (n-1) []) in
 144
 145     (* params = [T0;t0;...;Tn;tn;u0;e0;un-1;en-1] *)
 146     let params = iter (fun i acc ->
 147                          List.nth tys i ::
 148                          List.nth ts i :: acc) n
 149                      (iter (fun i acc ->
 150                             List.nth us i::
 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);
 154                         List.nth us n]
 155   in
 156
 157   let kname it j =
 158     let _,_,_,cl = it in
 159     let _,name,_ = List.nth cl j in
 160     name
 161   in
 162
 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
 166     let tys = List.map
 167                 (fun x -> CicNotationPt.Implicit (`Tagged ("T" ^ (string_of_int x))))
 168                 (HExtlib.list_seq 0 nargs) in
 169     let tys = tys @
 170       [iter (fun i acc ->
 171         CicNotationPt.Binder (`Lambda, (mk_id ("x" ^ string_of_int i), None),
 172         CicNotationPt.Binder (`Lambda, (mk_id ("p" ^ string_of_int i), None),
 173         acc))) (nargs-1)
 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)])]
 179     in
 180     CicNotationPt.Binder (`Lambda, (mk_id "e",
 181       Some (mk_appl
 182         [mk_id "eq";
 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
 187     let refl2 = mk_appl
 188                   [mk_id "refl";
 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") )),
 193       if i = j then
 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))
 197               (nargs-1)
 198               (CicNotationPt.Binder (`Forall, (mk_id "_",
 199                 Some (mk_eq tys ts us es nargs)),
 200                 mk_id "P")))), mk_id "P")
 201       else mk_id "P"))
 202   in
 203
 204   let inner i ts = CicNotationPt.Case
 205               (mk_id "y",None,
 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 ))),
 212                   List.map
 213                   (fun j ->
 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
 217                      let nones =
 218                        iter (fun _ acc -> None::acc) (nargs_kty - 1) [] in
 219                      CicNotationPt.Pattern (kname it j,
 220                                             None,
 221                                             List.combine us nones),
 222                                 branch i j ts us)
 223                   (HExtlib.list_seq 0 (List.length cl)))
 224   in
 225   let outer = CicNotationPt.Case
 226                 (mk_id "x",None,
 227                  Some (CicNotationPt.Binder (`Lambda, (mk_id "_",None),
 228                  (*CicNotationPt.Sort (`NType "2")*) CicNotationPt.Implicit
 229                  `JustOne)) ,
 230                  List.map
 231                    (fun i ->
 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
 235                      let nones =
 236                        iter (fun _ acc -> None::acc) (nargs_kty - 1) [] in
 237                       CicNotationPt.Pattern (kname it i,
 238                                              None,
 239                                              List.combine ts nones),
 240                                 inner i ts)
 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))
 244   in
 245   pp (lazy ("discriminator = " ^ (CicNotationPp.pp_term principle)));
 246
 247   status, principle
 248 ;;
 249
 250 let hd_of_term = function
 251   | NCic.Appl (hd::_) -> hd
 252   | t -> t
 253 ;;
 254
 255 let name_of_rel ~context rel =
 256   let s, _ = List.nth context (rel-1) in s
 257 ;;
 258
 259 (* let lookup_in_ctx ~context n =
 260   List.nth context ((List.length context) - n - 1)
 261 ;;*)
 262
 263 let discriminate_tac ~context cur_eq status =
 264   pp (lazy (Printf.sprintf "discriminate: equation %s" (name_of_rel ~context cur_eq)));
 265
 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::
 272         params @ [
 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");
 277     ] in
 278   let dbranches it leftno =
 279     prerr_endline (Printf.sprintf "dbranches %d" leftno);
 280     let _,_,_,cl = it in
 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
 286       leftno m)))
 287       (nbranches-1) [] in
 288     if nbranches > 1 then
 289       (prerr_endline "sì branch";
 290          NTactics.branch_tac:: branches @ [NTactics.merge_tac])
 291     else
 292       (prerr_endline "no branch";
 293       branches)
 294   in
 295
 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
 314   in
 315
 316   NTactics.block_tac (
 317     [(fun status ->
 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";
 324                            mk_id "e"]))))
 325       status);
 326     NTactics.branch_tac;
 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 @
 334    [NTactics.shift_tac;
 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"];
 341     NTactics.merge_tac]
 342   ) status
 343 ;;
 344
 345 let subst_tac ~context ~dir cur_eq =
 346   fun status ->
 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
 356       | `LeftToRight -> l
 357       | `RightToLeft -> r in
 358     let var = match var with
 359       | NCic.Rel i -> i
 360       | _ -> assert false in
 361     let names_to_gen, _ =
 362       cascade_select_in_ctx ~subst:(get_subst status) context (var+cur_eq) in
 363     let gen_tac x =
 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
 374 ;;
 375
 376 let get_ctx st goal =
 377     ctx_of (get_goalty st goal)
 378 ;;
 379
 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)
 390             else
 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)
 396         | NCic.Rel j, _
 397             when NCicTypeChecker.does_not_occur ~subst ctx' (j-1) j r ->
 398               `Subst `LeftToRight
 399         | _, NCic.Rel j
 400             when NCicTypeChecker.does_not_occur ~subst ctx' (j-1) j l ->
 401               `Subst `RightToLeft
 402         | (NCic.Rel _, _ | _, NCic.Rel _ ) -> `Cycle
 403         | _ -> `Blob) in
 404   let rec aux i =
 405     try
 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)));
 413            match ty with
 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
 416                match kind with
 417                  | `Identity ->
 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
 421                         else aux (i+1)
 422                  | `Cycle | `Blob -> aux (i+1) (* XXX: skip cyclic/blob equations for now *)
 423                  | _ ->
 424                     if (List.for_all (fun x -> x <> n) acc) then
 425                       status, Some (List.length ctx - i), kind
 426                     else aux (i+1))
 427            | _ -> aux (i+1))
 428     with Failure _ | Invalid_argument _ -> status, None, `Blob
 429   in aux 0
 430 ;;
 431
 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
 439   in
 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
 443   | None, _ ->
 444     pp (lazy (Printf.sprintf "destruct: nprods is %d, no selection, context is %s" nprods (NCicPp.ppcontext ~metasenv:[] ~subst ctx)));
 445       if nprods > 0  then
 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)
 448       else
 449         status
 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)));
 469       assert false
 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)));
 472       assert false
 473 ;;
 474
 475 let destruct_tac s = NTactics.distribute_tac (destruct_tac0 0 []) s;;