src/HOL/Tools/res_hol_clause.ML
changeset 20016 9a005f7d95e6
parent 19964 73704ba4bed1
child 20022 b07a138b4e7d
equal deleted inserted replaced
20015:1ffcf4802802 20016:9a005f7d95e6
   218 fun get_clause_id (Clause cls) = #clause_id cls;
   218 fun get_clause_id (Clause cls) = #clause_id cls;
   219 
   219 
   220 fun get_literals (c as Clause(cls)) = #literals cls;
   220 fun get_literals (c as Clause(cls)) = #literals cls;
   221 
   221 
   222 
   222 
   223 
       
   224 exception TERM_ORD of string
       
   225 
       
   226 fun term_ord (CombVar(_,_),CombVar(_,_)) = EQUAL
       
   227   | term_ord (CombVar(_,_),_) = LESS
       
   228   | term_ord (CombFree(_,_),CombVar(_,_)) = GREATER
       
   229   | term_ord (CombFree(f1,tp1),CombFree(f2,tp2)) = 
       
   230     let val ord1 = string_ord(f1,f2)
       
   231     in
       
   232 	case ord1 of EQUAL => ResClause.types_ord ([tp1],[tp2])
       
   233 		   | _ => ord1
       
   234     end
       
   235   | term_ord (CombFree(_,_),_) = LESS
       
   236   | term_ord (CombConst(_,_,_),CombVar(_,_)) = GREATER
       
   237   | term_ord (CombConst(_,_,_),CombFree(_,_)) = GREATER
       
   238   | term_ord (CombConst(c1,tp1,_),CombConst(c2,tp2,_)) = 
       
   239     let val ord1 = string_ord (c1,c2)
       
   240     in
       
   241 	case ord1 of EQUAL => ResClause.types_ord ([tp1],[tp2])
       
   242 		   | _ => ord1
       
   243     end
       
   244   | term_ord (CombConst(_,_,_),_) = LESS
       
   245   | term_ord (CombApp(_,_,_),Bool(_)) = raise TERM_ORD("bool")
       
   246   | term_ord (CombApp(f1,arg1,tp1),CombApp(f2,arg2,tp2)) =
       
   247     let val ord1 = term_ord (f1,f2)
       
   248 	val ord2 = case ord1 of EQUAL => term_ord (arg1,arg2)
       
   249 			      | _ => ord1
       
   250     in
       
   251 	case ord2 of EQUAL => ResClause.types_ord ([tp1],[tp2])
       
   252 		   | _ => ord2
       
   253     end
       
   254   | term_ord (CombApp(_,_,_),_) = GREATER
       
   255   | term_ord (Bool(_),_) = raise TERM_ORD("bool");
       
   256 
       
   257 fun predicate_ord (Bool(t1),Bool(t2)) = term_ord (t1,t2)
       
   258 
       
   259 
       
   260 fun literal_ord (Literal(false,_),Literal(true,_)) = LESS
       
   261   | literal_ord (Literal(true,_),Literal(false,_)) = GREATER
       
   262   | literal_ord (Literal(_,pred1),Literal(_,pred2)) = predicate_ord(pred1,pred2);
       
   263 
       
   264 fun sort_lits lits = sort literal_ord lits;
       
   265 
       
   266 (*********************************************************************)
   223 (*********************************************************************)
   267 (* convert a clause with type Term.term to a clause with type clause *)
   224 (* convert a clause with type Term.term to a clause with type clause *)
   268 (*********************************************************************)
   225 (*********************************************************************)
   269 
   226 
   270 fun isFalse (Literal(pol,Bool(CombConst(c,_,_)))) =
   227 fun isFalse (Literal(pol,Bool(CombConst(c,_,_)))) =
   277       (pol andalso c = "c_True") orelse
   234       (pol andalso c = "c_True") orelse
   278       (not pol andalso c = "c_False")
   235       (not pol andalso c = "c_False")
   279   | isTrue _ = false;
   236   | isTrue _ = false;
   280   
   237   
   281 fun isTaut (Clause {literals,...}) = exists isTrue literals;  
   238 fun isTaut (Clause {literals,...}) = exists isTrue literals;  
   282 
       
   283 
       
   284 
       
   285 fun make_clause(clause_id,axiom_name,th,kind,literals,ctypes_sorts,ctvar_type_literals,ctfree_type_literals) =
       
   286     if forall isFalse literals
       
   287     then error "Problem too trivial for resolution (empty clause)"
       
   288     else
       
   289 	Clause {clause_id = clause_id, axiom_name = axiom_name, 
       
   290                 th = th, kind = kind, 
       
   291 		literals = literals, ctypes_sorts = ctypes_sorts, 
       
   292 		ctvar_type_literals = ctvar_type_literals,
       
   293 		ctfree_type_literals = ctfree_type_literals};
       
   294 
   239 
   295 fun type_of (Type (a, Ts)) =
   240 fun type_of (Type (a, Ts)) =
   296     let val (folTypes,ts) = types_of Ts
   241     let val (folTypes,ts) = types_of Ts
   297 	val t = ResClause.make_fixed_type_const a
   242 	val t = ResClause.make_fixed_type_const a
   298     in
   243     in
   464 
   409 
   465 fun literals_of_term P = literals_of_term1 ([],[]) P;
   410 fun literals_of_term P = literals_of_term1 ([],[]) P;
   466 
   411 
   467 
   412 
   468 (* making axiom and conjecture clauses *)
   413 (* making axiom and conjecture clauses *)
   469 fun make_axiom_clause thm (ax_name,cls_id) =
   414 fun make_clause(clause_id,axiom_name,kind,thm) =
   470     let val term = prop_of thm
   415     let val term = prop_of thm
   471 	val (lits,ctypes_sorts) = literals_of_term (comb_of term)
   416 	val term' = comb_of term
   472 	val lits' = sort_lits lits
   417 	val (lits,ctypes_sorts) = literals_of_term term'
   473 	val (ctvar_lits,ctfree_lits) = ResClause.add_typs_aux ctypes_sorts
   418 	val (ctvar_lits,ctfree_lits) = ResClause.add_typs_aux ctypes_sorts
   474     in
   419     in
   475 	make_clause(cls_id,ax_name,thm,Axiom,
   420 	if forall isFalse lits
   476 		    lits',ctypes_sorts,ctvar_lits,ctfree_lits)
   421 	then error "Problem too trivial for resolution (empty clause)"
   477     end;
   422 	else
   478 
   423 	    Clause {clause_id = clause_id, axiom_name = axiom_name, th = thm, kind = kind,
       
   424 		    literals = lits, ctypes_sorts = ctypes_sorts, 
       
   425 		    ctvar_type_literals = ctvar_lits,
       
   426 		    ctfree_type_literals = ctfree_lits}
       
   427     end;
       
   428 
       
   429 
       
   430 fun make_axiom_clause thm (ax_name,cls_id) = make_clause(cls_id,ax_name,Axiom,thm);
       
   431  
   479 fun make_axiom_clauses [] = []
   432 fun make_axiom_clauses [] = []
   480   | make_axiom_clauses ((thm,(name,id))::thms) =
   433   | make_axiom_clauses ((thm,(name,id))::thms) =
   481     let val cls = make_axiom_clause thm (name,id)
   434     let val cls = make_axiom_clause thm (name,id)
   482 	val clss = make_axiom_clauses thms
   435 	val clss = make_axiom_clauses thms
   483     in
   436     in
   484 	if isTaut cls then clss else (cls::clss)
   437 	if isTaut cls then clss else (cls::clss)
   485     end;
   438     end;
   486 
   439 
   487 
   440 
   488 fun make_conjecture_clause n thm =
   441 fun make_conjecture_clause n thm = make_clause(n,"Conjecture",Conjecture,thm);
   489     let val t = prop_of thm
   442  
   490 	val (lits,ctypes_sorts) = literals_of_term (comb_of t)
       
   491 	val (ctvar_lits,ctfree_lits) = ResClause.add_typs_aux ctypes_sorts
       
   492     in
       
   493 	make_clause(n,"conjecture",thm,Conjecture,lits,ctypes_sorts,ctvar_lits,ctfree_lits)
       
   494     end;
       
   495 
       
   496 
       
   497 
   443 
   498 fun make_conjecture_clauses_aux _ [] = []
   444 fun make_conjecture_clauses_aux _ [] = []
   499   | make_conjecture_clauses_aux n (t::ts) =
   445   | make_conjecture_clauses_aux n (t::ts) =
   500     make_conjecture_clause n t :: make_conjecture_clauses_aux (n+1) ts;
   446     make_conjecture_clause n t :: make_conjecture_clauses_aux (n+1) ts;
   501 
   447 
   753 	       (foldl ResClause.add_arityClause_preds
   699 	       (foldl ResClause.add_arityClause_preds
   754 		      (Symtab.update ("hBOOL",1) Symtab.empty)
   700 		      (Symtab.update ("hBOOL",1) Symtab.empty)
   755 		      arity_clauses)
   701 		      arity_clauses)
   756 	       clsrel_clauses)
   702 	       clsrel_clauses)
   757 
   703 
   758 
       
   759 (**********************************************************************)
       
   760 (* clause equalities and hashing functions                            *)
       
   761 (**********************************************************************)
       
   762 
       
   763 
       
   764 fun combterm_eq (CombConst(c1,tp1,tps1),CombConst(c2,tp2,tps2)) vtvars =
       
   765     let val (eq1,vtvars1) = if c1 = c2 then ResClause.types_eq (tps1,tps2) vtvars
       
   766 			    else (false,vtvars)
       
   767     in
       
   768 	(eq1,vtvars1)
       
   769     end
       
   770   | combterm_eq (CombConst(_,_,_),_) vtvars = (false,vtvars)
       
   771   | combterm_eq (CombFree(a1,tp1),CombFree(a2,tp2)) vtvars = 
       
   772     if a1 = a2 then ResClause.types_eq ([tp1],[tp2]) vtvars
       
   773     else (false,vtvars)
       
   774   | combterm_eq (CombFree(_,_),_) vtvars = (false,vtvars)
       
   775   | combterm_eq (CombVar(v1,tp1),CombVar(v2,tp2)) (vars,tvars) = 
       
   776     (case ResClause.check_var_pairs(v1,v2) vars of 0 => ResClause.types_eq ([tp1],[tp2]) ((v1,v2)::vars,tvars)
       
   777 						 | 1 => ResClause.types_eq ([tp1],[tp2]) (vars,tvars)
       
   778 						 | 2 => (false,(vars,tvars)))
       
   779   | combterm_eq (CombVar(_,_),_) vtvars = (false,vtvars)
       
   780   | combterm_eq (CombApp(f1,arg1,tp1),CombApp(f2,arg2,tp2)) vtvars =
       
   781     let val (eq1,vtvars1) = combterm_eq (f1,f2) vtvars
       
   782 	val (eq2,vtvars2) = if eq1 then combterm_eq (arg1,arg2) vtvars1
       
   783 			    else (eq1,vtvars1)
       
   784     in
       
   785 	if eq2 then ResClause.types_eq ([tp1],[tp2]) vtvars2
       
   786 	else (eq2,vtvars2)
       
   787     end
       
   788   | combterm_eq (CombApp(_,_,_),_) vtvars = (false,vtvars)
       
   789   | combterm_eq (Bool(t1),Bool(t2)) vtvars = combterm_eq (t1,t2) vtvars
       
   790   | combterm_eq (Bool(_),_) vtvars = (false,vtvars);
       
   791 
       
   792 fun lit_eq (Literal(pol1,pred1),Literal(pol2,pred2)) vtvars =
       
   793     if (pol1 = pol2) then combterm_eq (pred1,pred2) vtvars
       
   794     else (false,vtvars);
       
   795 
       
   796 fun lits_eq ([],[]) vtvars = (true,vtvars)
       
   797   | lits_eq (l1::ls1,l2::ls2) vtvars = 
       
   798     let val (eq1,vtvars1) = lit_eq (l1,l2) vtvars
       
   799     in
       
   800 	if eq1 then lits_eq (ls1,ls2) vtvars1
       
   801 	else (false,vtvars1)
       
   802     end;
       
   803 
       
   804 fun clause_eq (cls1,cls2) =
       
   805     let val lits1 = get_literals cls1
       
   806 	val lits2 = get_literals cls2
       
   807     in
       
   808 	length lits1 = length lits2 andalso #1 (lits_eq (lits1,lits2) ([],[]))
       
   809     end;
       
   810 
       
   811 val xor_words = List.foldl Word.xorb 0w0;
       
   812 
       
   813 fun hash_combterm (CombVar(_,_),w) = w
       
   814   | hash_combterm (CombFree(f,_),w) = Polyhash.hashw_string(f,w)
       
   815   | hash_combterm (CombConst(c,tp,tps),w) = Polyhash.hashw_string(c,w)
       
   816   | hash_combterm (CombApp(f,arg,tp),w) = hash_combterm (arg, hash_combterm (f,w))
       
   817   | hash_combterm (Bool(t),w) = hash_combterm (t,w);
       
   818 
       
   819 fun hash_literal (Literal(true,pred)) = hash_combterm(pred,0w0)
       
   820   | hash_literal (Literal(false,pred)) = Word.notb(hash_combterm(pred,0w0));
       
   821 
       
   822 fun hash_clause clause = xor_words (map hash_literal (get_literals clause));
       
   823 
   704 
   824 (**********************************************************************)
   705 (**********************************************************************)
   825 (* write clauses to files                                             *)
   706 (* write clauses to files                                             *)
   826 (**********************************************************************)
   707 (**********************************************************************)
   827 
   708