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 |