src/Pure/proofterm.ML
changeset 64566 679710d324f1
parent 63857 0883c1cc655c
child 64568 a504a3dec35a
equal deleted inserted replaced
64565:5069ddebc937 64566:679710d324f1
   531       if i < plev then (is, js) else (insert (op =) (i-plev) is, js)
   531       if i < plev then (is, js) else (insert (op =) (i-plev) is, js)
   532   | prf_add_loose_bnos plev tlev (prf1 %% prf2) p =
   532   | prf_add_loose_bnos plev tlev (prf1 %% prf2) p =
   533       prf_add_loose_bnos plev tlev prf2
   533       prf_add_loose_bnos plev tlev prf2
   534         (prf_add_loose_bnos plev tlev prf1 p)
   534         (prf_add_loose_bnos plev tlev prf1 p)
   535   | prf_add_loose_bnos plev tlev (prf % opt) (is, js) =
   535   | prf_add_loose_bnos plev tlev (prf % opt) (is, js) =
   536       prf_add_loose_bnos plev tlev prf (case opt of
   536       prf_add_loose_bnos plev tlev prf
       
   537         (case opt of
   537           NONE => (is, insert (op =) ~1 js)
   538           NONE => (is, insert (op =) ~1 js)
   538         | SOME t => (is, add_loose_bnos (t, tlev, js)))
   539         | SOME t => (is, add_loose_bnos (t, tlev, js)))
   539   | prf_add_loose_bnos plev tlev (AbsP (_, opt, prf)) (is, js) =
   540   | prf_add_loose_bnos plev tlev (AbsP (_, opt, prf)) (is, js) =
   540       prf_add_loose_bnos (plev+1) tlev prf (case opt of
   541       prf_add_loose_bnos (plev+1) tlev prf
       
   542         (case opt of
   541           NONE => (is, insert (op =) ~1 js)
   543           NONE => (is, insert (op =) ~1 js)
   542         | SOME t => (is, add_loose_bnos (t, tlev, js)))
   544         | SOME t => (is, add_loose_bnos (t, tlev, js)))
   543   | prf_add_loose_bnos plev tlev (Abst (_, _, prf)) p =
   545   | prf_add_loose_bnos plev tlev (Abst (_, _, prf)) p =
   544       prf_add_loose_bnos plev (tlev+1) prf p
   546       prf_add_loose_bnos plev (tlev+1) prf p
   545   | prf_add_loose_bnos _ _ _ _ = ([], []);
   547   | prf_add_loose_bnos _ _ _ _ = ([], []);
   633           handle Same.SAME => prf %% subst lev prf')
   635           handle Same.SAME => prf %% subst lev prf')
   634       | subst lev (prf % t) = (subst lev prf % Option.map (substh' lev) t
   636       | subst lev (prf % t) = (subst lev prf % Option.map (substh' lev) t
   635           handle Same.SAME => prf % Same.map_option (subst' lev) t)
   637           handle Same.SAME => prf % Same.map_option (subst' lev) t)
   636       | subst _ _ = raise Same.SAME
   638       | subst _ _ = raise Same.SAME
   637     and substh lev prf = (subst lev prf handle Same.SAME => prf);
   639     and substh lev prf = (subst lev prf handle Same.SAME => prf);
   638   in case args of [] => prf | _ => substh 0 prf end;
   640   in (case args of [] => prf | _ => substh 0 prf) end;
   639 
   641 
   640 fun prf_subst_pbounds args prf =
   642 fun prf_subst_pbounds args prf =
   641   let
   643   let
   642     val n = length args;
   644     val n = length args;
   643     fun subst (PBound i) Plev tlev =
   645     fun subst (PBound i) Plev tlev =
   649       | subst (prf %% prf') Plev tlev = (subst prf Plev tlev %% substh prf' Plev tlev
   651       | subst (prf %% prf') Plev tlev = (subst prf Plev tlev %% substh prf' Plev tlev
   650           handle Same.SAME => prf %% subst prf' Plev tlev)
   652           handle Same.SAME => prf %% subst prf' Plev tlev)
   651       | subst (prf % t) Plev tlev = subst prf Plev tlev % t
   653       | subst (prf % t) Plev tlev = subst prf Plev tlev % t
   652       | subst  _ _ _ = raise Same.SAME
   654       | subst  _ _ _ = raise Same.SAME
   653     and substh prf Plev tlev = (subst prf Plev tlev handle Same.SAME => prf)
   655     and substh prf Plev tlev = (subst prf Plev tlev handle Same.SAME => prf)
   654   in case args of [] => prf | _ => substh prf 0 0 end;
   656   in (case args of [] => prf | _ => substh prf 0 0) end;
   655 
   657 
   656 
   658 
   657 (**** Freezing and thawing of variables in proof terms ****)
   659 (**** Freezing and thawing of variables in proof terms ****)
   658 
   660 
   659 local
   661 local
   990         (case head_of f of
   992         (case head_of f of
   991           Abs _ => SOME (remove_types t)
   993           Abs _ => SOME (remove_types t)
   992         | Var _ => SOME (remove_types t)
   994         | Var _ => SOME (remove_types t)
   993         | _ => NONE) %
   995         | _ => NONE) %
   994         (case head_of g of
   996         (case head_of g of
   995            Abs _ => SOME (remove_types u)
   997           Abs _ => SOME (remove_types u)
   996         | Var _ => SOME (remove_types u)
   998         | Var _ => SOME (remove_types u)
   997         | _ => NONE) %% prf1 %% prf2
   999         | _ => NONE) %% prf1 %% prf2
   998      | _ => prf % NONE % NONE %% prf1 %% prf2)
  1000      | _ => prf % NONE % NONE %% prf1 %% prf2)
   999   end;
  1001   end;
  1000 
  1002 
  1103       add_npvars q p Ts (add_npvars q (not p) Ts (vs, t), u)
  1105       add_npvars q p Ts (add_npvars q (not p) Ts (vs, t), u)
  1104   | add_npvars q p Ts (vs, Const ("Pure.all", Type (_, [Type (_, [T, _]), _])) $ t) =
  1106   | add_npvars q p Ts (vs, Const ("Pure.all", Type (_, [Type (_, [T, _]), _])) $ t) =
  1105       add_npvars q p Ts (vs, if p andalso q then betapply (t, Var (("",0), T)) else t)
  1107       add_npvars q p Ts (vs, if p andalso q then betapply (t, Var (("",0), T)) else t)
  1106   | add_npvars q p Ts (vs, Abs (_, T, t)) = add_npvars q p (T::Ts) (vs, t)
  1108   | add_npvars q p Ts (vs, Abs (_, T, t)) = add_npvars q p (T::Ts) (vs, t)
  1107   | add_npvars _ _ Ts (vs, t) = add_npvars' Ts (vs, t)
  1109   | add_npvars _ _ Ts (vs, t) = add_npvars' Ts (vs, t)
  1108 and add_npvars' Ts (vs, t) = (case strip_comb t of
  1110 and add_npvars' Ts (vs, t) =
       
  1111   (case strip_comb t of
  1109     (Var (ixn, _), ts) => if test_args [] ts then vs
  1112     (Var (ixn, _), ts) => if test_args [] ts then vs
  1110       else Library.foldl (add_npvars' Ts)
  1113       else Library.foldl (add_npvars' Ts)
  1111         (AList.update (op =) (ixn,
  1114         (AList.update (op =) (ixn,
  1112           Library.foldl (add_funvars Ts) ((these ooo AList.lookup) (op =) vs ixn, ts)) vs, ts)
  1115           Library.foldl (add_funvars Ts) ((these ooo AList.lookup) (op =) vs ixn, ts)) vs, ts)
  1113   | (Abs (_, T, u), ts) => Library.foldl (add_npvars' (T::Ts)) (vs, u :: ts)
  1116   | (Abs (_, T, u), ts) => Library.foldl (add_npvars' (T::Ts)) (vs, u :: ts)
  1114   | (_, ts) => Library.foldl (add_npvars' Ts) (vs, ts));
  1117   | (_, ts) => Library.foldl (add_npvars' Ts) (vs, ts));
  1115 
  1118 
  1116 fun prop_vars (Const ("Pure.imp", _) $ P $ Q) = union (op =) (prop_vars P) (prop_vars Q)
  1119 fun prop_vars (Const ("Pure.imp", _) $ P $ Q) = union (op =) (prop_vars P) (prop_vars Q)
  1117   | prop_vars (Const ("Pure.all", _) $ Abs (_, _, t)) = prop_vars t
  1120   | prop_vars (Const ("Pure.all", _) $ Abs (_, _, t)) = prop_vars t
  1118   | prop_vars t = (case strip_comb t of
  1121   | prop_vars t = (case strip_comb t of (Var (ixn, _), _) => [ixn] | _ => []);
  1119       (Var (ixn, _), _) => [ixn] | _ => []);
       
  1120 
  1122 
  1121 fun is_proj t =
  1123 fun is_proj t =
  1122   let
  1124   let
  1123     fun is_p i t = (case strip_comb t of
  1125     fun is_p i t =
       
  1126       (case strip_comb t of
  1124         (Bound _, []) => false
  1127         (Bound _, []) => false
  1125       | (Bound j, ts) => j >= i orelse exists (is_p i) ts
  1128       | (Bound j, ts) => j >= i orelse exists (is_p i) ts
  1126       | (Abs (_, _, u), _) => is_p (i+1) u
  1129       | (Abs (_, _, u), _) => is_p (i+1) u
  1127       | (_, ts) => exists (is_p i) ts)
  1130       | (_, ts) => exists (is_p i) ts)
  1128   in (case strip_abs_body t of
  1131   in
  1129         Bound _ => true
  1132     (case strip_abs_body t of
  1130       | t' => is_p 0 t')
  1133       Bound _ => true
       
  1134     | t' => is_p 0 t')
  1131   end;
  1135   end;
  1132 
  1136 
  1133 fun needed_vars prop =
  1137 fun needed_vars prop =
  1134   union (op =) (Library.foldl (uncurry (union (op =)))
  1138   union (op =) (Library.foldl (uncurry (union (op =)))
  1135     ([], map (uncurry (insert (op =))) (add_npvars true true [] ([], prop))))
  1139     ([], map (uncurry (insert (op =))) (add_npvars true true [] ([], prop))))
  1194               | _ => raise Fail "shrink: proof not in normal form");
  1198               | _ => raise Fail "shrink: proof not in normal form");
  1195             val vs = vars_of prop;
  1199             val vs = vars_of prop;
  1196             val (ts', ts'') = chop (length vs) ts;
  1200             val (ts', ts'') = chop (length vs) ts;
  1197             val insts = take (length ts') (map (fst o dest_Var) vs) ~~ ts';
  1201             val insts = take (length ts') (map (fst o dest_Var) vs) ~~ ts';
  1198             val nvs = Library.foldl (fn (ixns', (ixn, ixns)) =>
  1202             val nvs = Library.foldl (fn (ixns', (ixn, ixns)) =>
  1199               insert (op =) ixn (case AList.lookup (op =) insts ixn of
  1203               insert (op =) ixn
       
  1204                 (case AList.lookup (op =) insts ixn of
  1200                   SOME (SOME t) => if is_proj t then union (op =) ixns ixns' else ixns'
  1205                   SOME (SOME t) => if is_proj t then union (op =) ixns ixns' else ixns'
  1201                 | _ => union (op =) ixns ixns'))
  1206                 | _ => union (op =) ixns ixns'))
  1202                   (needed prop ts'' prfs, add_npvars false true [] ([], prop));
  1207                   (needed prop ts'' prfs, add_npvars false true [] ([], prop));
  1203             val insts' = map
  1208             val insts' = map
  1204               (fn (ixn, x as SOME _) => if member (op =) nvs ixn then (false, x) else (true, NONE)
  1209               (fn (ixn, x as SOME _) => if member (op =) nvs ixn then (false, x) else (true, NONE)
  1248       (pinst, (tymatch (tyinsts, K p), insts));
  1253       (pinst, (tymatch (tyinsts, K p), insts));
  1249     fun matchTs inst (Ts, Us) = Library.foldl (uncurry matchT) (inst, Ts ~~ Us);
  1254     fun matchTs inst (Ts, Us) = Library.foldl (uncurry matchT) (inst, Ts ~~ Us);
  1250 
  1255 
  1251     fun mtch Ts i j (pinst, tinst) (Hyp (Var (ixn, _)), prf) =
  1256     fun mtch Ts i j (pinst, tinst) (Hyp (Var (ixn, _)), prf) =
  1252           if i = 0 andalso j = 0 then ((ixn, prf) :: pinst, tinst)
  1257           if i = 0 andalso j = 0 then ((ixn, prf) :: pinst, tinst)
  1253           else (case apfst (flt i) (apsnd (flt j)
  1258           else
  1254                   (prf_add_loose_bnos 0 0 prf ([], []))) of
  1259             (case apfst (flt i) (apsnd (flt j) (prf_add_loose_bnos 0 0 prf ([], []))) of
  1255               ([], []) => ((ixn, incr_pboundvars (~i) (~j) prf) :: pinst, tinst)
  1260               ([], []) => ((ixn, incr_pboundvars (~i) (~j) prf) :: pinst, tinst)
  1256             | ([], _) => if j = 0 then
  1261             | ([], _) =>
  1257                    ((ixn, incr_pboundvars (~i) (~j) prf) :: pinst, tinst)
  1262                 if j = 0 then ((ixn, incr_pboundvars (~i) (~j) prf) :: pinst, tinst)
  1258                  else raise PMatch
  1263                 else raise PMatch
  1259             | _ => raise PMatch)
  1264             | _ => raise PMatch)
  1260       | mtch Ts i j inst (prf1 % opt1, prf2 % opt2) =
  1265       | mtch Ts i j inst (prf1 % opt1, prf2 % opt2) =
  1261           optmatch (matcht Ts j) (mtch Ts i j inst (prf1, prf2)) (opt1, opt2)
  1266           optmatch (matcht Ts j) (mtch Ts i j inst (prf1, prf2)) (opt1, opt2)
  1262       | mtch Ts i j inst (prf1 %% prf2, prf1' %% prf2') =
  1267       | mtch Ts i j inst (prf1 %% prf2, prf1' %% prf2') =
  1263           mtch Ts i j (mtch Ts i j inst (prf1, prf1')) (prf2, prf2')
  1268           mtch Ts i j (mtch Ts i j inst (prf1, prf1')) (prf2, prf2')
  1387             let val prf'' = incr_pboundvars 0 (~1) prf'
  1392             let val prf'' = incr_pboundvars 0 (~1) prf'
  1388             in SOME (the_default (prf'', no_skel) (rew Ts hs prf'')) end
  1393             in SOME (the_default (prf'', no_skel) (rew Ts hs prf'')) end
  1389       | rew0 Ts hs prf = rew Ts hs prf;
  1394       | rew0 Ts hs prf = rew Ts hs prf;
  1390 
  1395 
  1391     fun rew1 _ _ (Hyp (Var _)) _ = NONE
  1396     fun rew1 _ _ (Hyp (Var _)) _ = NONE
  1392       | rew1 Ts hs skel prf = (case rew2 Ts hs skel prf of
  1397       | rew1 Ts hs skel prf =
  1393           SOME prf1 => (case rew0 Ts hs prf1 of
  1398           (case rew2 Ts hs skel prf of
  1394               SOME (prf2, skel') => SOME (the_default prf2 (rew1 Ts hs skel' prf2))
  1399             SOME prf1 =>
  1395             | NONE => SOME prf1)
  1400               (case rew0 Ts hs prf1 of
  1396         | NONE => (case rew0 Ts hs prf of
  1401                 SOME (prf2, skel') => SOME (the_default prf2 (rew1 Ts hs skel' prf2))
  1397               SOME (prf1, skel') => SOME (the_default prf1 (rew1 Ts hs skel' prf1))
  1402               | NONE => SOME prf1)
  1398             | NONE => NONE))
  1403           | NONE =>
  1399 
  1404               (case rew0 Ts hs prf of
  1400     and rew2 Ts hs skel (prf % SOME t) = (case prf of
  1405                 SOME (prf1, skel') => SOME (the_default prf1 (rew1 Ts hs skel' prf1))
       
  1406               | NONE => NONE))
       
  1407 
       
  1408     and rew2 Ts hs skel (prf % SOME t) =
       
  1409           (case prf of
  1401             Abst (_, _, body) =>
  1410             Abst (_, _, body) =>
  1402               let val prf' = prf_subst_bounds [t] body
  1411               let val prf' = prf_subst_bounds [t] body
  1403               in SOME (the_default prf' (rew2 Ts hs no_skel prf')) end
  1412               in SOME (the_default prf' (rew2 Ts hs no_skel prf')) end
  1404           | _ => (case rew1 Ts hs (case skel of skel' % _ => skel' | _ => no_skel) prf of
  1413           | _ =>
  1405               SOME prf' => SOME (prf' % SOME t)
  1414               (case rew1 Ts hs (case skel of skel' % _ => skel' | _ => no_skel) prf of
  1406             | NONE => NONE))
  1415                 SOME prf' => SOME (prf' % SOME t)
       
  1416               | NONE => NONE))
  1407       | rew2 Ts hs skel (prf % NONE) = Option.map (fn prf' => prf' % NONE)
  1417       | rew2 Ts hs skel (prf % NONE) = Option.map (fn prf' => prf' % NONE)
  1408           (rew1 Ts hs (case skel of skel' % _ => skel' | _ => no_skel) prf)
  1418           (rew1 Ts hs (case skel of skel' % _ => skel' | _ => no_skel) prf)
  1409       | rew2 Ts hs skel (prf1 %% prf2) = (case prf1 of
  1419       | rew2 Ts hs skel (prf1 %% prf2) =
       
  1420           (case prf1 of
  1410             AbsP (_, _, body) =>
  1421             AbsP (_, _, body) =>
  1411               let val prf' = prf_subst_pbounds [prf2] body
  1422               let val prf' = prf_subst_pbounds [prf2] body
  1412               in SOME (the_default prf' (rew2 Ts hs no_skel prf')) end
  1423               in SOME (the_default prf' (rew2 Ts hs no_skel prf')) end
  1413           | _ =>
  1424           | _ =>
  1414             let val (skel1, skel2) = (case skel of
  1425             let
  1415                 skel1 %% skel2 => (skel1, skel2)
  1426               val (skel1, skel2) =
  1416               | _ => (no_skel, no_skel))
  1427                 (case skel of
  1417             in case rew1 Ts hs skel1 prf1 of
  1428                   skel1 %% skel2 => (skel1, skel2)
  1418                 SOME prf1' => (case rew1 Ts hs skel2 prf2 of
  1429                 | _ => (no_skel, no_skel))
       
  1430             in
       
  1431               (case rew1 Ts hs skel1 prf1 of
       
  1432                 SOME prf1' =>
       
  1433                   (case rew1 Ts hs skel2 prf2 of
  1419                     SOME prf2' => SOME (prf1' %% prf2')
  1434                     SOME prf2' => SOME (prf1' %% prf2')
  1420                   | NONE => SOME (prf1' %% prf2))
  1435                   | NONE => SOME (prf1' %% prf2))
  1421               | NONE => (case rew1 Ts hs skel2 prf2 of
  1436               | NONE =>
       
  1437                   (case rew1 Ts hs skel2 prf2 of
  1422                     SOME prf2' => SOME (prf1 %% prf2')
  1438                     SOME prf2' => SOME (prf1 %% prf2')
  1423                   | NONE => NONE)
  1439                   | NONE => NONE))
  1424             end)
  1440             end)
  1425       | rew2 Ts hs skel (Abst (s, T, prf)) = (case rew1 (the_default dummyT T :: Ts) hs
  1441       | rew2 Ts hs skel (Abst (s, T, prf)) =
       
  1442           (case rew1 (the_default dummyT T :: Ts) hs
  1426               (case skel of Abst (_, _, skel') => skel' | _ => no_skel) prf of
  1443               (case skel of Abst (_, _, skel') => skel' | _ => no_skel) prf of
  1427             SOME prf' => SOME (Abst (s, T, prf'))
  1444             SOME prf' => SOME (Abst (s, T, prf'))
  1428           | NONE => NONE)
  1445           | NONE => NONE)
  1429       | rew2 Ts hs skel (AbsP (s, t, prf)) = (case rew1 Ts (t :: hs)
  1446       | rew2 Ts hs skel (AbsP (s, t, prf)) =
  1430               (case skel of AbsP (_, _, skel') => skel' | _ => no_skel) prf of
  1447           (case rew1 Ts (t :: hs) (case skel of AbsP (_, _, skel') => skel' | _ => no_skel) prf of
  1431             SOME prf' => SOME (AbsP (s, t, prf'))
  1448             SOME prf' => SOME (AbsP (s, t, prf'))
  1432           | NONE => NONE)
  1449           | NONE => NONE)
  1433       | rew2 _ _ _ _ = NONE;
  1450       | rew2 _ _ _ _ = NONE;
  1434 
  1451 
  1435   in the_default prf (rew1 [] [] no_skel prf) end;
  1452   in the_default prf (rew1 [] [] no_skel prf) end;
  1578 fun thm_proof thy name shyps hyps concl promises body =
  1595 fun thm_proof thy name shyps hyps concl promises body =
  1579   let val (pthm, head, args, argsP, _) = prepare_thm_proof thy name shyps hyps concl promises body
  1596   let val (pthm, head, args, argsP, _) = prepare_thm_proof thy name shyps hyps concl promises body
  1580   in (pthm, proof_combP (proof_combt' (head, args), argsP)) end;
  1597   in (pthm, proof_combP (proof_combt' (head, args), argsP)) end;
  1581 
  1598 
  1582 fun unconstrain_thm_proof thy shyps concl promises body =
  1599 fun unconstrain_thm_proof thy shyps concl promises body =
  1583   let
  1600   let val (pthm, head, _, _, args) = prepare_thm_proof thy "" shyps [] concl promises body
  1584     val (pthm, head, _, _, args) = prepare_thm_proof thy "" shyps [] concl promises body
       
  1585   in (pthm, proof_combt' (head, args)) end;
  1601   in (pthm, proof_combt' (head, args)) end;
  1586 
  1602 
  1587 
  1603 
  1588 fun get_name shyps hyps prop prf =
  1604 fun get_name shyps hyps prop prf =
  1589   let val (_, prop) = Logic.unconstrainT shyps (Logic.list_implies (hyps, prop)) in
  1605   let val (_, prop) = Logic.unconstrainT shyps (Logic.list_implies (hyps, prop)) in