components/tactics/fwdSimplTactic.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 module PEH = ProofEngineHelpers
  29 module U  = CicUniv
  30 module TC = CicTypeChecker
  31 module PET = ProofEngineTypes
  32 module S = CicSubstitution
  33 module PT = PrimitiveTactics
  34 module T = Tacticals
  35 module FNG = FreshNamesGenerator
  36 module MI = CicMkImplicit
  37 module PESR = ProofEngineStructuralRules
  38
  39 let fail_msg0 = "unexported clearbody: invalid argument"
  40 let fail_msg2 = "fwd: no applicable simplification"
  41
  42 let error msg = raise (PET.Fail (lazy msg))
  43
  44 (* unexported tactics *******************************************************)
  45
  46 let id_tac =
  47    let id_tac (proof,goal) =
  48       try
  49          let _, metasenv, _, _ = proof in
  50          let _, _, _ = CicUtil.lookup_meta goal metasenv in
  51          (proof,[goal])
  52       with CicUtil.Meta_not_found _ -> (proof, [])
  53    in
  54    PET.mk_tactic id_tac
  55
  56 let clearbody ~index =
  57    let rec find_name index = function
  58       | Some (Cic.Name name, _) :: _ when index = 1 -> name
  59       | _ :: tail when index > 1 -> find_name (pred index) tail
  60       | _ -> error fail_msg0
  61    in
  62    let clearbody status =
  63       let (proof, goal) = status in
  64       let _, metasenv, _, _ = proof in
  65       let _, context, _ = CicUtil.lookup_meta goal metasenv in
  66       PET.apply_tactic (PESR.clearbody ~hyp:(find_name index context)) status
  67    in
  68    PET.mk_tactic clearbody
  69
  70 (* lapply *******************************************************************)
  71
  72 let strip_prods metasenv context ?how_many to_what term =
  73    let irl = MI.identity_relocation_list_for_metavariable context in
  74    let mk_meta metasenv its_type =
  75       let index = MI.new_meta metasenv [] in
  76       let metasenv = [index, context, its_type] @ metasenv in
  77       metasenv, Cic.Meta (index, irl), index
  78    in
  79    let update_counters = function
  80       | None, []                 -> None, false, id_tac, []
  81       | None, to_what :: tail    -> None, true, PT.apply_tac ~term:to_what, tail
  82       | Some hm, []              -> Some (pred hm), false, id_tac, []
  83       | Some hm, to_what :: tail -> Some (pred hm), true, PT.apply_tac ~term:to_what, tail
  84    in
  85    let rec aux metasenv metas conts tw = function
  86       | Some hm, _ when hm <= 0               -> metasenv, metas, conts
  87       | xhm, Cic.Prod (Cic.Name _, t1, t2)    ->
  88          let metasenv, meta, index = mk_meta metasenv t1 in
  89          aux metasenv (meta :: metas) (conts @ [id_tac, index]) tw (xhm, (S.subst meta t2))
  90       | xhm, Cic.Prod (Cic.Anonymous, t1, t2) ->
  91          let xhm, pos, tac, tw = update_counters (xhm, tw) in
  92          let metasenv, meta, index = mk_meta metasenv t1 in
  93          let conts = if pos then (tac, index) :: conts else conts @ [tac, index] in
  94          aux metasenv (meta :: metas) conts tw (xhm, (S.subst meta t2))
  95       | _, t                                  -> metasenv, metas, conts
  96    in
  97    aux metasenv [] [] to_what (how_many, term)
  98
  99 let get_clearables context terms =
 100    let aux = function
 101       | Cic.Rel i
 102       | Cic.Appl (Cic.Rel i :: _) -> PEH.get_name context i
 103       | _                         -> None
 104    in
 105    PEH.list_rev_map_filter aux terms
 106
 107 let lapply_tac_aux ?(mk_fresh_name_callback = FreshNamesGenerator.mk_fresh_name ~subst:[])
 108                (* ?(substs = []) *) ?how_many ?(to_what = []) what =
 109    let letin_tac term = PT.letin_tac ~mk_fresh_name_callback term in
 110    let lapply_tac (proof, goal) =
 111       let xuri, metasenv, u, t = proof in
 112       let _, context, _ = CicUtil.lookup_meta goal metasenv in
 113       let lemma, _ = TC.type_of_aux' metasenv context what U.empty_ugraph in
 114       let lemma = FNG.clean_dummy_dependent_types lemma in
 115       let metasenv, metas, conts = strip_prods metasenv context ?how_many to_what lemma in
 116       let conclusion =
 117          match metas with [] -> what | _ -> Cic.Appl (what :: List.rev metas)
 118       in
 119       let tac =
 120          T.then_ ~start:(letin_tac conclusion)
 121                  ~continuation:(clearbody ~index:1)
 122       in
 123       let proof = (xuri, metasenv, u, t) in
 124       let aux (proof, goals) (tac, goal) =
 125          let proof, new_goals = PET.apply_tactic tac (proof, goal) in
 126          proof, goals @ new_goals
 127       in
 128       List.fold_left aux (proof, []) ((tac, goal) :: conts)
 129    in
 130    PET.mk_tactic lapply_tac
 131
 132 let lapply_tac ?(mk_fresh_name_callback = FreshNamesGenerator.mk_fresh_name ~subst:[])
 133                (* ?(substs = []) *) ?(linear = false) ?how_many ?(to_what = []) what =
 134    let lapply_tac status =
 135       let proof, goal = status in
 136       let _, metasenv, _, _ = proof in
 137       let _, context, _ = CicUtil.lookup_meta goal metasenv in
 138       let lapply = lapply_tac_aux ~mk_fresh_name_callback ?how_many ~to_what what in
 139       let tac =
 140          if linear then
 141             let hyps = get_clearables context (what :: to_what) in
 142             T.then_ ~start:lapply
 143                     ~continuation:(PESR.clear ~hyps) (* T.try_tactic ~tactic: *)
 144          else
 145             lapply
 146          in
 147          PET.apply_tactic tac status
 148    in
 149    PET.mk_tactic lapply_tac
 150
 151 (* fwd **********************************************************************)
 152
 153 let fwd_simpl_tac
 154      ?(mk_fresh_name_callback = FNG.mk_fresh_name ~subst:[])
 155      ~dbd hyp =
 156    let lapply_tac to_what lemma =
 157       lapply_tac ~mk_fresh_name_callback ~how_many:1 ~to_what:[to_what] lemma
 158    in
 159    let fwd_simpl_tac status =
 160       let (proof, goal) = status in
 161       let _, metasenv, _, _ = proof in
 162       let _, context, ty = CicUtil.lookup_meta goal metasenv in
 163       let index, major = PEH.lookup_type metasenv context hyp in
 164       match FwdQueries.fwd_simpl ~dbd major with
 165          | []       -> error fail_msg2
 166          | uri :: _ ->
 167             Printf.eprintf "fwd: %s\n" (UriManager.string_of_uri uri); flush stderr;
 168             let start = lapply_tac (Cic.Rel index) (Cic.Const (uri, [])) in
 169             let tac = T.then_ ~start ~continuation:(PESR.clear ~hyps:[hyp]) in
 170             PET.apply_tactic tac status
 171    in
 172    PET.mk_tactic fwd_simpl_tac