src/Tools/eqsubst.ML
changeset 52236 fb82b42eb498
parent 52235 6aff6b8bec13
child 52237 ab3ba550cbe7
equal deleted inserted replaced
52235:6aff6b8bec13 52236:fb82b42eb498
   237 (* search only for 'valid' unifiers (non abs subterms and non vars) *)
   237 (* search only for 'valid' unifiers (non abs subterms and non vars) *)
   238 val searchf_lr_unify_valid = searchf_unify_gen (search_lr_valid valid_match_start);
   238 val searchf_lr_unify_valid = searchf_unify_gen (search_lr_valid valid_match_start);
   239 
   239 
   240 val searchf_bt_unify_valid = searchf_unify_gen (search_bt_valid valid_match_start);
   240 val searchf_bt_unify_valid = searchf_unify_gen (search_bt_valid valid_match_start);
   241 
   241 
   242 (* apply a substitution in the conclusion of the theorem th *)
   242 (* apply a substitution in the conclusion of the theorem *)
   243 (* cfvs are certified free var placeholders for goal params *)
   243 (* cfvs are certified free var placeholders for goal params *)
   244 (* conclthm is a theorem of for just the conclusion *)
   244 (* conclthm is a theorem of for just the conclusion *)
   245 (* m is instantiation/match information *)
   245 (* m is instantiation/match information *)
   246 (* rule is the equation for substitution *)
   246 (* rule is the equation for substitution *)
   247 fun apply_subst_in_concl ctxt i th (cfvs, conclthm) rule m =
   247 fun apply_subst_in_concl ctxt i st (cfvs, conclthm) rule m =
   248   RWInst.rw ctxt m rule conclthm
   248   RWInst.rw ctxt m rule conclthm
   249   |> IsaND.unfix_frees cfvs
   249   |> IsaND.unfix_frees cfvs
   250   |> RWInst.beta_eta_contract
   250   |> RWInst.beta_eta_contract
   251   |> (fn r => Tactic.rtac r i th);
   251   |> (fn r => Tactic.rtac r i st);
   252 
   252 
   253 (* substitute within the conclusion of goal i of gth, using a meta
   253 (* substitute within the conclusion of goal i of gth, using a meta
   254 equation rule. Note that we assume rule has var indicies zero'd *)
   254 equation rule. Note that we assume rule has var indicies zero'd *)
   255 fun prep_concl_subst ctxt i gth =
   255 fun prep_concl_subst ctxt i gth =
   256   let
   256   let
   274   in
   274   in
   275     ((cfvs, conclthm), (thy, maxidx, ft))
   275     ((cfvs, conclthm), (thy, maxidx, ft))
   276   end;
   276   end;
   277 
   277 
   278 (* substitute using an object or meta level equality *)
   278 (* substitute using an object or meta level equality *)
   279 fun eqsubst_tac' ctxt searchf instepthm i th =
   279 fun eqsubst_tac' ctxt searchf instepthm i st =
   280   let
   280   let
   281     val (cvfsconclthm, searchinfo) = prep_concl_subst ctxt i th;
   281     val (cvfsconclthm, searchinfo) = prep_concl_subst ctxt i st;
   282     val stepthms = Seq.of_list (prep_meta_eq ctxt instepthm);
   282     val stepthms = Seq.of_list (prep_meta_eq ctxt instepthm);
   283     fun rewrite_with_thm r =
   283     fun rewrite_with_thm r =
   284       let val (lhs,_) = Logic.dest_equals (Thm.concl_of r) in
   284       let val (lhs,_) = Logic.dest_equals (Thm.concl_of r) in
   285         searchf searchinfo lhs
   285         searchf searchinfo lhs
   286         |> Seq.maps (apply_subst_in_concl ctxt i th cvfsconclthm r)
   286         |> Seq.maps (apply_subst_in_concl ctxt i st cvfsconclthm r)
   287       end;
   287       end;
   288   in stepthms |> Seq.maps rewrite_with_thm end;
   288   in stepthms |> Seq.maps rewrite_with_thm end;
   289 
   289 
   290 
   290 
   291 (* distinct subgoals *)
       
   292 fun distinct_subgoals th = the_default th (SINGLE distinct_subgoals_tac th);
       
   293 
       
   294 
       
   295 (* General substitution of multiple occurances using one of
   291 (* General substitution of multiple occurances using one of
   296    the given theorems *)
   292    the given theorems *)
   297 
   293 
   298 fun skip_first_occs_search occ srchf sinfo lhs =
   294 fun skip_first_occs_search occ srchf sinfo lhs =
   299   (case (skipto_skipseq occ (srchf sinfo lhs)) of
   295   (case skipto_skipseq occ (srchf sinfo lhs) of
   300     SkipMore _ => Seq.empty
   296     SkipMore _ => Seq.empty
   301   | SkipSeq ss => Seq.flat ss);
   297   | SkipSeq ss => Seq.flat ss);
   302 
   298 
   303 (* The occL is a list of integers indicating which occurence
   299 (* The occL is a list of integers indicating which occurence
   304 w.r.t. the search order, to rewrite. Backtracking will also find later
   300 w.r.t. the search order, to rewrite. Backtracking will also find later
   305 occurences, but all earlier ones are skipped. Thus you can use [0] to
   301 occurences, but all earlier ones are skipped. Thus you can use [0] to
   306 just find all rewrites. *)
   302 just find all rewrites. *)
   307 
   303 
   308 fun eqsubst_tac ctxt occL thms i th =
   304 fun eqsubst_tac ctxt occL thms i st =
   309   let val nprems = Thm.nprems_of th in
   305   let val nprems = Thm.nprems_of st in
   310     if nprems < i then Seq.empty else
   306     if nprems < i then Seq.empty else
   311     let
   307     let
   312       val thmseq = (Seq.of_list thms);
   308       val thmseq = Seq.of_list thms;
   313       fun apply_occ occ th =
   309       fun apply_occ occ st =
   314         thmseq |> Seq.maps (fn r =>
   310         thmseq |> Seq.maps (fn r =>
   315           eqsubst_tac' ctxt
   311           eqsubst_tac' ctxt
   316             (skip_first_occs_search occ searchf_lr_unify_valid) r
   312             (skip_first_occs_search occ searchf_lr_unify_valid) r
   317             (i + (Thm.nprems_of th - nprems)) th);
   313             (i + (Thm.nprems_of st - nprems)) st);
   318       val sortedoccL = Library.sort (rev_order o int_ord) occL;
   314       val sortedoccL = Library.sort (rev_order o int_ord) occL;
   319     in
   315     in
   320       Seq.map distinct_subgoals (Seq.EVERY (map apply_occ sortedoccL) th)
   316       Seq.maps distinct_subgoals_tac (Seq.EVERY (map apply_occ sortedoccL) st)
   321     end
   317     end
   322   end;
   318   end;
   323 
   319 
   324 
   320 
   325 (* inthms are the given arguments in Isar, and treated as eqstep with
   321 (* inthms are the given arguments in Isar, and treated as eqstep with
   326    the first one, then the second etc *)
   322    the first one, then the second etc *)
   327 fun eqsubst_meth ctxt occL inthms = SIMPLE_METHOD' (eqsubst_tac ctxt occL inthms);
   323 fun eqsubst_meth ctxt occL inthms = SIMPLE_METHOD' (eqsubst_tac ctxt occL inthms);
   328 
   324 
   329 (* apply a substitution inside assumption j, keeps asm in the same place *)
   325 (* apply a substitution inside assumption j, keeps asm in the same place *)
   330 fun apply_subst_in_asm ctxt i th rule ((cfvs, j, _, pth),m) =
   326 fun apply_subst_in_asm ctxt i st rule ((cfvs, j, _, pth),m) =
   331   let
   327   let
   332     val th2 = Thm.rotate_rule (j - 1) i th; (* put premice first *)
   328     val st2 = Thm.rotate_rule (j - 1) i st; (* put premice first *)
   333     val preelimrule =
   329     val preelimrule =
   334       RWInst.rw ctxt m rule pth
   330       RWInst.rw ctxt m rule pth
   335       |> (Seq.hd o prune_params_tac)
   331       |> (Seq.hd o prune_params_tac)
   336       |> Thm.permute_prems 0 ~1 (* put old asm first *)
   332       |> Thm.permute_prems 0 ~1 (* put old asm first *)
   337       |> IsaND.unfix_frees cfvs (* unfix any global params *)
   333       |> IsaND.unfix_frees cfvs (* unfix any global params *)
   338       |> RWInst.beta_eta_contract; (* normal form *)
   334       |> RWInst.beta_eta_contract; (* normal form *)
   339   in
   335   in
   340     (* ~j because new asm starts at back, thus we subtract 1 *)
   336     (* ~j because new asm starts at back, thus we subtract 1 *)
   341     Seq.map (Thm.rotate_rule (~ j) (Thm.nprems_of rule + i))
   337     Seq.map (Thm.rotate_rule (~ j) (Thm.nprems_of rule + i))
   342       (Tactic.dtac preelimrule i th2)
   338       (Tactic.dtac preelimrule i st2)
   343   end;
   339   end;
   344 
   340 
   345 
   341 
   346 (* prepare to substitute within the j'th premise of subgoal i of gth,
   342 (* prepare to substitute within the j'th premise of subgoal i of gth,
   347 using a meta-level equation. Note that we assume rule has var indicies
   343 using a meta-level equation. Note that we assume rule has var indicies
   378     ((fn l => Library.upto (1, length l))
   374     ((fn l => Library.upto (1, length l))
   379       (Logic.prems_of_goal (Thm.prop_of gth) i));
   375       (Logic.prems_of_goal (Thm.prop_of gth) i));
   380 
   376 
   381 
   377 
   382 (* substitute in an assumption using an object or meta level equality *)
   378 (* substitute in an assumption using an object or meta level equality *)
   383 fun eqsubst_asm_tac' ctxt searchf skipocc instepthm i th =
   379 fun eqsubst_asm_tac' ctxt searchf skipocc instepthm i st =
   384   let
   380   let
   385     val asmpreps = prep_subst_in_asms ctxt i th;
   381     val asmpreps = prep_subst_in_asms ctxt i st;
   386     val stepthms = Seq.of_list (prep_meta_eq ctxt instepthm);
   382     val stepthms = Seq.of_list (prep_meta_eq ctxt instepthm);
   387     fun rewrite_with_thm r =
   383     fun rewrite_with_thm r =
   388       let
   384       let
   389         val (lhs,_) = Logic.dest_equals (Thm.concl_of r);
   385         val (lhs,_) = Logic.dest_equals (Thm.concl_of r);
   390         fun occ_search occ [] = Seq.empty
   386         fun occ_search occ [] = Seq.empty
   393                 SkipMore i => occ_search i moreasms
   389                 SkipMore i => occ_search i moreasms
   394               | SkipSeq ss =>
   390               | SkipSeq ss =>
   395                   Seq.append (Seq.map (Library.pair asminfo) (Seq.flat ss))
   391                   Seq.append (Seq.map (Library.pair asminfo) (Seq.flat ss))
   396                     (occ_search 1 moreasms)) (* find later substs also *)
   392                     (occ_search 1 moreasms)) (* find later substs also *)
   397       in
   393       in
   398         occ_search skipocc asmpreps |> Seq.maps (apply_subst_in_asm ctxt i th r)
   394         occ_search skipocc asmpreps |> Seq.maps (apply_subst_in_asm ctxt i st r)
   399       end;
   395       end;
   400   in stepthms |> Seq.maps rewrite_with_thm end;
   396   in stepthms |> Seq.maps rewrite_with_thm end;
   401 
   397 
   402 
   398 
   403 fun skip_first_asm_occs_search searchf sinfo occ lhs =
   399 fun skip_first_asm_occs_search searchf sinfo occ lhs =
   404   skipto_skipseq occ (searchf sinfo lhs);
   400   skipto_skipseq occ (searchf sinfo lhs);
   405 
   401 
   406 fun eqsubst_asm_tac ctxt occL thms i th =
   402 fun eqsubst_asm_tac ctxt occL thms i st =
   407   let val nprems = Thm.nprems_of th in
   403   let val nprems = Thm.nprems_of st in
   408     if nprems < i then Seq.empty
   404     if nprems < i then Seq.empty
   409     else
   405     else
   410       let
   406       let
   411         val thmseq = Seq.of_list thms;
   407         val thmseq = Seq.of_list thms;
   412         fun apply_occ occK th =
   408         fun apply_occ occK st =
   413           thmseq |> Seq.maps (fn r =>
   409           thmseq |> Seq.maps (fn r =>
   414             eqsubst_asm_tac' ctxt
   410             eqsubst_asm_tac' ctxt
   415               (skip_first_asm_occs_search searchf_lr_unify_valid) occK r
   411               (skip_first_asm_occs_search searchf_lr_unify_valid) occK r
   416               (i + (Thm.nprems_of th - nprems)) th);
   412               (i + (Thm.nprems_of st - nprems)) st);
   417         val sortedoccs = Library.sort (rev_order o int_ord) occL;
   413         val sortedoccs = Library.sort (rev_order o int_ord) occL;
   418       in
   414       in
   419         Seq.map distinct_subgoals (Seq.EVERY (map apply_occ sortedoccs) th)
   415         Seq.maps distinct_subgoals_tac (Seq.EVERY (map apply_occ sortedoccs) st)
   420       end
   416       end
   421   end;
   417   end;
   422 
   418 
   423 (* inthms are the given arguments in Isar, and treated as eqstep with
   419 (* inthms are the given arguments in Isar, and treated as eqstep with
   424    the first one, then the second etc *)
   420    the first one, then the second etc *)