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"), |