src/HOL/Tools/res_axioms.ML
changeset 22471 7c51f1a799f3
parent 22360 26ead7ed4f4b
child 22516 c986140356b8
equal deleted inserted replaced
22470:0d52e5157124 22471:7c51f1a799f3
   413        |> transform_elim |> zero_var_indexes |> freeze_thm
   413        |> transform_elim |> zero_var_indexes |> freeze_thm
   414        |> ObjectLogic.atomize_thm |> make_nnf |> strip_lambdas ~1;
   414        |> ObjectLogic.atomize_thm |> make_nnf |> strip_lambdas ~1;
   415 
   415 
   416 (*The cache prevents repeated clausification of a theorem,
   416 (*The cache prevents repeated clausification of a theorem,
   417   and also repeated declaration of Skolem functions*)
   417   and also repeated declaration of Skolem functions*)
   418   (* FIXME better use Termtab!? No, we MUST use theory data!!*)
   418   (* FIXME  use theory data!!*)
   419 val clause_cache = ref (Symtab.empty : (thm * thm list) Symtab.table)
   419 val clause_cache = ref (Thmtab.empty : thm list Thmtab.table)
   420 
   420 
   421 
   421 
   422 (*Generate Skolem functions for a theorem supplied in nnf*)
   422 (*Generate Skolem functions for a theorem supplied in nnf*)
   423 fun skolem_of_nnf th =
   423 fun skolem_of_nnf th =
   424   map (skolem_of_def o assume o (cterm_of (theory_of_thm th))) (assume_skofuns th);
   424   map (skolem_of_def o assume o (cterm_of (theory_of_thm th))) (assume_skofuns th);
   464 (*Keep the full complexity of the original name*)
   464 (*Keep the full complexity of the original name*)
   465 fun flatten_name s = space_implode "_X" (NameSpace.explode s);
   465 fun flatten_name s = space_implode "_X" (NameSpace.explode s);
   466 
   466 
   467 (*Declare Skolem functions for a theorem, supplied in nnf and with its name.
   467 (*Declare Skolem functions for a theorem, supplied in nnf and with its name.
   468   It returns a modified theory, unless skolemization fails.*)
   468   It returns a modified theory, unless skolemization fails.*)
   469 fun skolem thy (name,th) =
   469 fun skolem thy th =
   470   let val cname = (case name of "" => gensym "" | s => flatten_name s)
   470   let val cname = (case PureThy.get_name_hint th of "" => gensym "" | s => flatten_name s)
   471       val _ = Output.debug (fn () => "skolemizing " ^ name ^ ": ")
   471       val _ = Output.debug (fn () => "skolemizing " ^ cname ^ ": ")
   472   in Option.map
   472   in Option.map
   473         (fn nnfth =>
   473         (fn nnfth =>
   474           let val (thy',defs) = declare_skofuns cname nnfth thy
   474           let val (thy',defs) = declare_skofuns cname nnfth thy
   475               val cnfs = Meson.make_cnf (map skolem_of_def defs) nnfth
   475               val cnfs = Meson.make_cnf (map skolem_of_def defs) nnfth
   476               val (thy'',cnfs') = declare_abstract (thy',cnfs)
   476               val (thy'',cnfs') = declare_abstract (thy',cnfs)
   479       (SOME (to_nnf th)  handle THM _ => NONE)
   479       (SOME (to_nnf th)  handle THM _ => NONE)
   480   end;
   480   end;
   481 
   481 
   482 (*Populate the clause cache using the supplied theorem. Return the clausal form
   482 (*Populate the clause cache using the supplied theorem. Return the clausal form
   483   and modified theory.*)
   483   and modified theory.*)
   484 fun skolem_cache_thm (name,th) thy =
   484 fun skolem_cache_thm th thy =
   485   case Symtab.lookup (!clause_cache) name of
   485   case Thmtab.lookup (!clause_cache) th of
   486       NONE =>
   486       NONE =>
   487         (case skolem thy (name, Thm.transfer thy th) of
   487         (case skolem thy (Thm.transfer thy th) of
   488              NONE => ([th],thy)
   488              NONE => ([th],thy)
   489            | SOME (cls,thy') => 
   489            | SOME (cls,thy') => 
   490                  (if null cls then warning ("skolem_cache: empty clause set for " ^ name)
   490                  (if null cls 
       
   491                   then warning ("skolem_cache: empty clause set for " ^ string_of_thm th)
   491                   else ();
   492                   else ();
   492                   change clause_cache (Symtab.update (name, (th, cls))); 
   493                   change clause_cache (Thmtab.update (th, cls)); 
   493                   (cls,thy')))
   494                   (cls,thy')))
   494     | SOME (th',cls) =>
   495     | SOME cls => (cls,thy);
   495         if Thm.eq_thm(th,th') then (cls,thy)
       
   496         else (Output.debug (fn () => "skolem_cache: Ignoring variant of theorem " ^ name);
       
   497               Output.debug (fn () => string_of_thm th);
       
   498               Output.debug (fn () => string_of_thm th');
       
   499               getOpt (skolem thy (name, Thm.transfer thy th), ([th],thy)));
       
   500 
   496 
   501 (*Exported function to convert Isabelle theorems into axiom clauses*)
   497 (*Exported function to convert Isabelle theorems into axiom clauses*)
   502 fun cnf_axiom (name,th) =
   498 fun cnf_axiom th =
   503  (Output.debug (fn () => "cnf_axiom called, theorem name = " ^ name);
   499   case Thmtab.lookup (!clause_cache) th of
   504   case name of
   500       NONE => 
   505         "" => skolem_thm th (*no name, so can't cache*)
   501 	let val cls = map Goal.close_result (skolem_thm th)
   506       | s  => case Symtab.lookup (!clause_cache) s of
   502 	in Output.debug (fn () => "inserted into cache");
   507                 NONE => 
   503 	   change clause_cache (Thmtab.update (th, cls)); cls 
   508                   let val cls = map Goal.close_result (skolem_thm th)
   504 	end
   509                   in Output.debug (fn () => "inserted into cache");
   505     | SOME cls => cls;
   510                      change clause_cache (Symtab.update (s, (th, cls))); cls 
       
   511                   end
       
   512               | SOME(th',cls) =>
       
   513                   if Thm.eq_thm(th,th') then cls
       
   514                   else
       
   515                     (Output.debug (fn () => "cnf_axiom: duplicate or variant of theorem " ^ name);
       
   516                      Output.debug (fn () => string_of_thm th);
       
   517                      Output.debug (fn () => string_of_thm th');
       
   518                      skolem_thm th)
       
   519  );
       
   520 
   506 
   521 fun pairname th = (PureThy.get_name_hint th, th);
   507 fun pairname th = (PureThy.get_name_hint th, th);
   522 
       
   523 (*Principally for debugging*)
       
   524 fun cnf_name s = 
       
   525   let val th = thm s
       
   526   in cnf_axiom (PureThy.get_name_hint th, th) end;
       
   527 
   508 
   528 (**** Extract and Clausify theorems from a theory's claset and simpset ****)
   509 (**** Extract and Clausify theorems from a theory's claset and simpset ****)
   529 
   510 
   530 fun rules_of_claset cs =
   511 fun rules_of_claset cs =
   531   let val {safeIs,safeEs,hazIs,hazEs,...} = rep_cs cs
   512   let val {safeIs,safeEs,hazIs,hazEs,...} = rep_cs cs
   549 fun simpset_rules_of ctxt = rules_of_simpset (local_simpset_of ctxt);
   530 fun simpset_rules_of ctxt = rules_of_simpset (local_simpset_of ctxt);
   550 
   531 
   551 fun atpset_rules_of ctxt = map pairname (ResAtpset.get_atpset ctxt);
   532 fun atpset_rules_of ctxt = map pairname (ResAtpset.get_atpset ctxt);
   552 
   533 
   553 
   534 
   554 (**** Translate a set of classical/simplifier rules into CNF (still as type "thm")  ****)
   535 (**** Translate a set of theorems into CNF ****)
   555 
   536 
   556 (* classical rules: works for both FOL and HOL *)
   537 (* classical rules: works for both FOL and HOL *)
   557 fun cnf_rules [] err_list = ([],err_list)
   538 fun cnf_rules [] err_list = ([],err_list)
   558   | cnf_rules ((name,th) :: ths) err_list =
   539   | cnf_rules ((name,th) :: ths) err_list =
   559       let val (ts,es) = cnf_rules ths err_list
   540       let val (ts,es) = cnf_rules ths err_list
   560       in  (cnf_axiom (name,th) :: ts,es) handle  _ => (ts, (th::es))  end;
   541       in  (cnf_axiom th :: ts,es) handle  _ => (ts, (th::es))  end;
   561 
   542 
   562 fun pair_name_cls k (n, []) = []
   543 fun pair_name_cls k (n, []) = []
   563   | pair_name_cls k (n, cls::clss) = (cls, (n,k)) :: pair_name_cls (k+1) (n, clss)
   544   | pair_name_cls k (n, cls::clss) = (cls, (n,k)) :: pair_name_cls (k+1) (n, clss)
   564 
   545 
   565 fun cnf_rules_pairs_aux pairs [] = pairs
   546 fun cnf_rules_pairs_aux pairs [] = pairs
   566   | cnf_rules_pairs_aux pairs ((name,th)::ths) =
   547   | cnf_rules_pairs_aux pairs ((name,th)::ths) =
   567       let val pairs' = (pair_name_cls 0 (name, cnf_axiom(name,th))) @ pairs
   548       let val pairs' = (pair_name_cls 0 (name, cnf_axiom th)) @ pairs
   568                        handle THM _ => pairs | ResClause.CLAUSE _ => pairs
   549                        handle THM _ => pairs | ResClause.CLAUSE _ => pairs
   569       in  cnf_rules_pairs_aux pairs' ths  end;
   550       in  cnf_rules_pairs_aux pairs' ths  end;
   570 
   551 
   571 (*The combination of rev and tail recursion preserves the original order*)
   552 (*The combination of rev and tail recursion preserves the original order*)
   572 fun cnf_rules_pairs l = cnf_rules_pairs_aux [] (rev l);
   553 fun cnf_rules_pairs l = cnf_rules_pairs_aux [] (rev l);
   574 
   555 
   575 (**** Convert all theorems of a claset/simpset into clauses (ResClause.clause, or ResHolClause.clause) ****)
   556 (**** Convert all theorems of a claset/simpset into clauses (ResClause.clause, or ResHolClause.clause) ****)
   576 
   557 
   577 (*Setup function: takes a theory and installs ALL known theorems into the clause cache*)
   558 (*Setup function: takes a theory and installs ALL known theorems into the clause cache*)
   578 
   559 
   579 fun skolem_cache (name,th) thy =
   560 fun skolem_cache th thy =
   580   let val prop = Thm.prop_of th
   561   let val prop = Thm.prop_of th
   581   in
   562   in
   582       if lambda_free prop 
   563       if lambda_free prop 
   583          (*Monomorphic theorems can be Skolemized on demand,
   564          (*Monomorphic theorems can be Skolemized on demand,
   584            but there are problems with re-use of abstraction functions if we don't
   565            but there are problems with re-use of abstraction functions if we don't
   585            do them now, even for monomorphic theorems.*)
   566            do them now, even for monomorphic theorems.*)
   586       then thy  
   567       then thy  
   587       else #2 (skolem_cache_thm (name,th) thy)
   568       else #2 (skolem_cache_thm th thy)
   588   end;
   569   end;
   589 
   570 
   590 (*The cache can be kept smaller by augmenting the condition above with 
   571 (*The cache can be kept smaller by augmenting the condition above with 
   591     orelse (not abstract_lambdas andalso monomorphic prop).
   572     orelse (not abstract_lambdas andalso monomorphic prop).
   592   However, while this step does not reduce the time needed to build HOL, 
   573   However, while this step does not reduce the time needed to build HOL, 
   593   it doubles the time taken by the first call to the ATP link-up.*)
   574   it doubles the time taken by the first call to the ATP link-up.*)
   594 
   575 
   595 fun clause_cache_setup thy = fold skolem_cache (PureThy.all_thms_of thy) thy;
   576 fun clause_cache_setup thy = fold skolem_cache (map #2 (PureThy.all_thms_of thy)) thy;
   596 
   577 
   597 
   578 
   598 (*** meson proof methods ***)
   579 (*** meson proof methods ***)
   599 
   580 
   600 fun skolem_use_cache_thm th =
   581 fun skolem_use_cache_thm th =
   601   case Symtab.lookup (!clause_cache) (PureThy.get_name_hint th) of
   582   case Thmtab.lookup (!clause_cache) th of
   602       NONE => skolem_thm th
   583       NONE => skolem_thm th
   603     | SOME (th',cls) =>
   584     | SOME cls => cls;
   604         if Thm.eq_thm(th,th') then cls else skolem_thm th;
       
   605 
   585 
   606 fun cnf_rules_of_ths ths = List.concat (map skolem_use_cache_thm ths);
   586 fun cnf_rules_of_ths ths = List.concat (map skolem_use_cache_thm ths);
   607 
   587 
   608 val meson_method_setup = Method.add_methods
   588 val meson_method_setup = Method.add_methods
   609   [("meson", Method.thms_args (fn ths =>
   589   [("meson", Method.thms_args (fn ths =>
   610       Method.SIMPLE_METHOD' (CHANGED_PROP o Meson.meson_claset_tac (cnf_rules_of_ths ths) HOL_cs)),
   590       Method.SIMPLE_METHOD' (CHANGED_PROP o Meson.meson_claset_tac (cnf_rules_of_ths ths) HOL_cs)),
   611     "MESON resolution proof procedure")];
   591     "MESON resolution proof procedure")];
   612 
   592 
   613 (** Attribute for converting a theorem into clauses **)
   593 (** Attribute for converting a theorem into clauses **)
   614 
   594 
   615 fun meta_cnf_axiom th = map Meson.make_meta_clause (cnf_axiom (pairname th));
   595 fun meta_cnf_axiom th = map Meson.make_meta_clause (cnf_axiom th);
   616 
   596 
   617 fun clausify_rule (th,i) = List.nth (meta_cnf_axiom th, i)
   597 fun clausify_rule (th,i) = List.nth (meta_cnf_axiom th, i)
   618 
   598 
   619 val clausify = Attrib.syntax (Scan.lift Args.nat
   599 val clausify = Attrib.syntax (Scan.lift Args.nat
   620   >> (fn i => Thm.rule_attribute (fn _ => fn th => clausify_rule (th, i))));
   600   >> (fn i => Thm.rule_attribute (fn _ => fn th => clausify_rule (th, i))));
   621 
   601 
   622 
   602 
   623 (*** Converting a subgoal into negated conjecture clauses. ***)
   603 (*** Converting a subgoal into negated conjecture clauses. ***)
   624 
   604 
   625 val neg_skolemize_tac = EVERY' [rtac ccontr, ObjectLogic.atomize_tac, skolemize_tac];
   605 val neg_skolemize_tac = EVERY' [rtac ccontr, ObjectLogic.atomize_tac, skolemize_tac];
   626 val neg_clausify = Meson.finish_cnf o assume_abstract_list o make_clauses;
   606 
       
   607 (*finish_cnf removes tautologies and functional reflexivity axioms, but by calling Thm.varifyT
       
   608   it can introduce TVars, which we don't want in conjecture clauses.*)
       
   609 val neg_clausify = map Thm.freezeT o Meson.finish_cnf o assume_abstract_list o make_clauses;
   627 
   610 
   628 fun neg_conjecture_clauses st0 n =
   611 fun neg_conjecture_clauses st0 n =
   629   let val st = Seq.hd (neg_skolemize_tac n st0)
   612   let val st = Seq.hd (neg_skolemize_tac n st0)
   630       val (params,_,_) = strip_context (Logic.nth_prem (n, Thm.prop_of st))
   613       val (params,_,_) = strip_context (Logic.nth_prem (n, Thm.prop_of st))
   631   in (neg_clausify (Option.valOf (metahyps_thms n st)), params) end;
   614   in (neg_clausify (Option.valOf (metahyps_thms n st)), params) end;
   652 (*Conjoin a list of theorems to form a single theorem*)
   635 (*Conjoin a list of theorems to form a single theorem*)
   653 fun conj_rule []  = TrueI
   636 fun conj_rule []  = TrueI
   654   | conj_rule ths = foldr1 conj2_rule ths;
   637   | conj_rule ths = foldr1 conj2_rule ths;
   655 
   638 
   656 fun skolem_attr (Context.Theory thy, th) =
   639 fun skolem_attr (Context.Theory thy, th) =
   657       let val name = PureThy.get_name_hint th
   640       let val (cls, thy') = skolem_cache_thm th thy
   658           val (cls, thy') = skolem_cache_thm (name, th) thy
       
   659       in (Context.Theory thy', conj_rule cls) end
   641       in (Context.Theory thy', conj_rule cls) end
   660   | skolem_attr (context, th) = (context, conj_rule (skolem_use_cache_thm th));
   642   | skolem_attr (context, th) = (context, conj_rule (skolem_use_cache_thm th));
   661 
   643 
   662 val setup_attrs = Attrib.add_attributes
   644 val setup_attrs = Attrib.add_attributes
   663   [("skolem", Attrib.no_args skolem_attr, "skolemization of a theorem"),
   645   [("skolem", Attrib.no_args skolem_attr, "skolemization of a theorem"),