src/HOL/Tools/res_hol_clause.ML
changeset 24385 ab62948281a9
parent 24323 9aa7b5708eac
child 24937 340523598914
equal deleted inserted replaced
24384:0002537695df 24385:ab62948281a9
    14   val comb_I: thm
    14   val comb_I: thm
    15   val comb_K: thm
    15   val comb_K: thm
    16   val comb_B: thm
    16   val comb_B: thm
    17   val comb_C: thm
    17   val comb_C: thm
    18   val comb_S: thm
    18   val comb_S: thm
    19   datatype type_level = T_FULL | T_PARTIAL | T_CONST
    19   datatype type_level = T_FULL | T_CONST
    20   val typ_level: type_level ref
    20   val typ_level: type_level ref
    21   val minimize_applies: bool ref
    21   val minimize_applies: bool ref
    22   type axiom_name = string
    22   type axiom_name = string
    23   type polarity = bool
    23   type polarity = bool
    24   type clause_id = int
    24   type clause_id = int
    55 val fequal_imp_equal = thm "ATP_Linkup.fequal_imp_equal";
    55 val fequal_imp_equal = thm "ATP_Linkup.fequal_imp_equal";
    56 val equal_imp_fequal = thm "ATP_Linkup.equal_imp_fequal";
    56 val equal_imp_fequal = thm "ATP_Linkup.equal_imp_fequal";
    57 
    57 
    58 
    58 
    59 (*The different translations of types*)
    59 (*The different translations of types*)
    60 datatype type_level = T_FULL | T_PARTIAL | T_CONST;
    60 datatype type_level = T_FULL | T_CONST;
    61 
    61 
    62 val typ_level = ref T_CONST;
    62 val typ_level = ref T_CONST;
    63 
    63 
    64 fun full_types () = (typ_level:=T_FULL);
       
    65 fun partial_types () = (typ_level:=T_PARTIAL);
       
    66 fun const_types_only () = (typ_level:=T_CONST);
       
    67 
       
    68 (*If true, each function will be directly applied to as many arguments as possible, avoiding
    64 (*If true, each function will be directly applied to as many arguments as possible, avoiding
    69   use of the "apply" operator. Use of hBOOL is also minimized. It only works for the
    65   use of the "apply" operator. Use of hBOOL is also minimized.*)
    70   constant-typed translation, though it could be tried for the partially-typed one.*)
       
    71 val minimize_applies = ref true;
    66 val minimize_applies = ref true;
    72 
    67 
    73 val const_min_arity = ref (Symtab.empty : int Symtab.table);
    68 val const_min_arity = ref (Symtab.empty : int Symtab.table);
    74 
    69 
    75 val const_needs_hBOOL = ref (Symtab.empty : bool Symtab.table);
    70 val const_needs_hBOOL = ref (Symtab.empty : bool Symtab.table);
    76 
    71 
    77 fun min_arity_of c = getOpt (Symtab.lookup(!const_min_arity) c, 0);
    72 fun min_arity_of c = getOpt (Symtab.lookup(!const_min_arity) c, 0);
    78 
    73 
    79 (*True if the constant ever appears outside of the top-level position in literals.
    74 (*True if the constant ever appears outside of the top-level position in literals.
    80   If false, the constant always receives all of its arguments and is used as a predicate.*)
    75   If false, the constant always receives all of its arguments and is used as a predicate.*)
    81 fun needs_hBOOL c = not (!minimize_applies) orelse !typ_level=T_PARTIAL orelse
    76 fun needs_hBOOL c = not (!minimize_applies) orelse
    82                     getOpt (Symtab.lookup(!const_needs_hBOOL) c, false);
    77                     getOpt (Symtab.lookup(!const_needs_hBOOL) c, false);
    83 
       
    84 
       
    85 (**********************************************************************)
       
    86 (* convert a Term.term with lambdas into a Term.term with combinators *)
       
    87 (**********************************************************************)
       
    88 
       
    89 fun is_free (Bound(a)) n = (a = n)
       
    90   | is_free (Abs(x,_,b)) n = (is_free b (n+1))
       
    91   | is_free (P $ Q) n = ((is_free P n) orelse (is_free Q n))
       
    92   | is_free _ _ = false;
       
    93 
       
    94 fun compact_comb t bnds = t;
       
    95 
       
    96 fun lam2comb (Abs(x,tp,Bound 0)) _ = Const("ATP_Linkup.COMBI",tp-->tp)
       
    97   | lam2comb (Abs(x,tp,Bound n)) bnds =
       
    98       let val tb = List.nth(bnds,n-1)
       
    99       in  Const("ATP_Linkup.COMBK", [tb,tp] ---> tb) $ Bound (n-1)  end
       
   100   | lam2comb (Abs(x,t1,Const(c,t2))) _ = Const("ATP_Linkup.COMBK",[t2,t1] ---> t2) $ Const(c,t2)
       
   101   | lam2comb (Abs(x,t1,Free(v,t2))) _ = Const("ATP_Linkup.COMBK",[t2,t1] ---> t2) $ Free(v,t2)
       
   102   | lam2comb (Abs(x,t1,Var(ind,t2))) _ = Const("ATP_Linkup.COMBK", [t2,t1] ---> t2) $ Var(ind,t2)
       
   103   | lam2comb (t as (Abs(x,t1,P$(Bound 0)))) bnds =
       
   104       if is_free P 0 then
       
   105           let val tI = [t1] ---> t1
       
   106               val P' = lam2comb (Abs(x,t1,P)) bnds
       
   107               val tp' = Term.type_of1(bnds,P')
       
   108               val tS = [tp',tI] ---> Term.type_of1(t1::bnds,P)
       
   109           in
       
   110               compact_comb (Const("ATP_Linkup.COMBS",tS) $ P' $
       
   111                              Const("ATP_Linkup.COMBI",tI)) bnds
       
   112           end
       
   113       else incr_boundvars ~1 P
       
   114   | lam2comb (t as (Abs(x,t1,P$Q))) bnds =
       
   115       let val nfreeP = not(is_free P 0)
       
   116           and nfreeQ = not(is_free Q 0)
       
   117           val tpq = Term.type_of1(t1::bnds, P$Q)
       
   118       in
       
   119           if nfreeP andalso nfreeQ
       
   120           then
       
   121             let val tK = [tpq,t1] ---> tpq
       
   122             in  Const("ATP_Linkup.COMBK",tK) $ incr_boundvars ~1 (P $ Q)  end
       
   123           else if nfreeP then
       
   124             let val Q' = lam2comb (Abs(x,t1,Q)) bnds
       
   125                 val P' = incr_boundvars ~1 P
       
   126                 val tp = Term.type_of1(bnds,P')
       
   127                 val tq' = Term.type_of1(bnds, Q')
       
   128                 val tB = [tp,tq',t1] ---> tpq
       
   129             in  compact_comb (Const("ATP_Linkup.COMBB",tB) $ P' $ Q') bnds  end
       
   130           else if nfreeQ then
       
   131             let val P' = lam2comb (Abs(x,t1,P)) bnds
       
   132                 val Q' = incr_boundvars ~1 Q
       
   133                 val tq = Term.type_of1(bnds,Q')
       
   134                 val tp' = Term.type_of1(bnds, P')
       
   135                 val tC = [tp',tq,t1] ---> tpq
       
   136             in  compact_comb (Const("ATP_Linkup.COMBC",tC) $ P' $ Q') bnds  end
       
   137           else
       
   138             let val P' = lam2comb (Abs(x,t1,P)) bnds
       
   139                 val Q' = lam2comb (Abs(x,t1,Q)) bnds
       
   140                 val tp' = Term.type_of1(bnds,P')
       
   141                 val tq' = Term.type_of1(bnds,Q')
       
   142                 val tS = [tp',tq',t1] ---> tpq
       
   143             in  compact_comb (Const("ATP_Linkup.COMBS",tS) $ P' $ Q') bnds  end
       
   144       end
       
   145   | lam2comb (t as (Abs(x,t1,_))) _ = raise RC.CLAUSE("HOL CLAUSE",t);
       
   146 
       
   147 fun to_comb (Abs(x,tp,b)) bnds = lam2comb (Abs(x, tp, to_comb b (tp::bnds))) bnds
       
   148   | to_comb (P $ Q) bnds = (to_comb P bnds) $ (to_comb Q bnds)
       
   149   | to_comb t _ = t;
       
   150 
    78 
   151 
    79 
   152 (******************************************************)
    80 (******************************************************)
   153 (* data types for typed combinator expressions        *)
    81 (* data types for typed combinator expressions        *)
   154 (******************************************************)
    82 (******************************************************)
   224       in  (v',ts)  end
   152       in  (v',ts)  end
   225   | combterm_of thy (Var(v,t)) =
   153   | combterm_of thy (Var(v,t)) =
   226       let val (tp,ts) = type_of t
   154       let val (tp,ts) = type_of t
   227           val v' = CombVar(RC.make_schematic_var v,tp)
   155           val v' = CombVar(RC.make_schematic_var v,tp)
   228       in  (v',ts)  end
   156       in  (v',ts)  end
   229   | combterm_of thy (t as (P $ Q)) =
   157   | combterm_of thy (P $ Q) =
   230       let val (P',tsP) = combterm_of thy P
   158       let val (P',tsP) = combterm_of thy P
   231           val (Q',tsQ) = combterm_of thy Q
   159           val (Q',tsQ) = combterm_of thy Q
   232       in  (CombApp(P',Q'), tsP union tsQ)  end;
   160       in  (CombApp(P',Q'), tsP union tsQ)  end
       
   161   | combterm_of thy (t as Abs _) = raise RC.CLAUSE("HOL CLAUSE",t);
   233 
   162 
   234 fun predicate_of thy ((Const("Not",_) $ P), polarity) = predicate_of thy (P, not polarity)
   163 fun predicate_of thy ((Const("Not",_) $ P), polarity) = predicate_of thy (P, not polarity)
   235   | predicate_of thy (t,polarity) = (combterm_of thy t, polarity);
   164   | predicate_of thy (t,polarity) = (combterm_of thy t, polarity);
   236 
   165 
   237 fun literals_of_term1 thy args (Const("Trueprop",_) $ P) = literals_of_term1 thy args P
   166 fun literals_of_term1 thy args (Const("Trueprop",_) $ P) = literals_of_term1 thy args P
   245 
   174 
   246 fun literals_of_term thy P = literals_of_term1 thy ([],[]) P;
   175 fun literals_of_term thy P = literals_of_term1 thy ([],[]) P;
   247 
   176 
   248 (* making axiom and conjecture clauses *)
   177 (* making axiom and conjecture clauses *)
   249 fun make_clause thy (clause_id,axiom_name,kind,th) =
   178 fun make_clause thy (clause_id,axiom_name,kind,th) =
   250     let val (lits,ctypes_sorts) = literals_of_term thy (to_comb (prop_of th) [])
   179     let val (lits,ctypes_sorts) = literals_of_term thy (prop_of th)
   251         val (ctvar_lits,ctfree_lits) = RC.add_typs_aux ctypes_sorts
   180         val (ctvar_lits,ctfree_lits) = RC.add_typs_aux ctypes_sorts
   252     in
   181     in
   253         if forall isFalse lits
   182         if forall isFalse lits
   254         then error "Problem too trivial for resolution (empty clause)"
   183         then error "Problem too trivial for resolution (empty clause)"
   255         else
   184         else
   305   if !typ_level=T_FULL then
   234   if !typ_level=T_FULL then
   306       type_wrapper ^ RC.paren_pack [s, RC.string_of_fol_type tp]
   235       type_wrapper ^ RC.paren_pack [s, RC.string_of_fol_type tp]
   307   else s;
   236   else s;
   308 
   237 
   309 fun apply ss = "hAPP" ^ RC.paren_pack ss;
   238 fun apply ss = "hAPP" ^ RC.paren_pack ss;
   310 
       
   311 (*Full (non-optimized) and partial-typed transations*)
       
   312 fun string_of_combterm1 (CombConst(c,tp,_)) =
       
   313       let val c' = if c = "equal" then "c_fequal" else c
       
   314       in  wrap_type (c',tp)  end
       
   315   | string_of_combterm1 (CombVar(v,tp)) = wrap_type (v,tp)
       
   316   | string_of_combterm1 (CombApp(t1,t2)) =
       
   317       let val s1 = string_of_combterm1 t1
       
   318           and s2 = string_of_combterm1 t2
       
   319       in
       
   320           case !typ_level of
       
   321               T_FULL => wrap_type (apply [s1,s2], result_type (type_of_combterm t1))
       
   322             | T_PARTIAL => apply [s1,s2, RC.string_of_fol_type (type_of_combterm t1)]
       
   323             | T_CONST => raise ERROR "string_of_combterm1"
       
   324       end;
       
   325 
   239 
   326 fun rev_apply (v, []) = v
   240 fun rev_apply (v, []) = v
   327   | rev_apply (v, arg::args) = apply [rev_apply (v, args), arg];
   241   | rev_apply (v, arg::args) = apply [rev_apply (v, args), arg];
   328 
   242 
   329 fun string_apply (v, args) = rev_apply (v, rev args);
   243 fun string_apply (v, args) = rev_apply (v, rev args);
   346   | string_of_applic (CombVar(v,tp), args) = string_apply (v, args)
   260   | string_of_applic (CombVar(v,tp), args) = string_apply (v, args)
   347   | string_of_applic _ = raise ERROR "string_of_applic";
   261   | string_of_applic _ = raise ERROR "string_of_applic";
   348 
   262 
   349 fun wrap_type_if (head, s, tp) = if head_needs_hBOOL head then wrap_type (s, tp) else s;
   263 fun wrap_type_if (head, s, tp) = if head_needs_hBOOL head then wrap_type (s, tp) else s;
   350 
   264 
   351 (*Full (if optimized) and constant-typed transations*)
   265 fun string_of_combterm t =
   352 fun string_of_combterm2 t =
       
   353   let val (head, args) = strip_comb t
   266   let val (head, args) = strip_comb t
   354   in  wrap_type_if (head,
   267   in  wrap_type_if (head,
   355                     string_of_applic (head, map string_of_combterm2 args),
   268                     string_of_applic (head, map string_of_combterm args),
   356                     type_of_combterm t)
   269                     type_of_combterm t)
   357   end;
   270   end;
   358 
       
   359 fun string_of_combterm t =
       
   360     case (!typ_level,!minimize_applies) of
       
   361          (T_PARTIAL, _) => string_of_combterm1 t
       
   362        | (T_FULL, false) => string_of_combterm1 t
       
   363        | _ => string_of_combterm2 t;
       
   364 
   271 
   365 (*Boolean-valued terms are here converted to literals.*)
   272 (*Boolean-valued terms are here converted to literals.*)
   366 fun boolify t = "hBOOL" ^ RC.paren_pack [string_of_combterm t];
   273 fun boolify t = "hBOOL" ^ RC.paren_pack [string_of_combterm t];
   367 
   274 
   368 fun string_of_predicate t =
   275 fun string_of_predicate t =
   446 fun addtypes tvars tab = foldl RC.add_foltype_funcs tab tvars;
   353 fun addtypes tvars tab = foldl RC.add_foltype_funcs tab tvars;
   447 
   354 
   448 fun add_decls (CombConst(c,tp,tvars), (funcs,preds)) =
   355 fun add_decls (CombConst(c,tp,tvars), (funcs,preds)) =
   449       if c = "equal" then (addtypes tvars funcs, preds)
   356       if c = "equal" then (addtypes tvars funcs, preds)
   450       else
   357       else
   451         (case !typ_level of
   358 	let val arity = min_arity_of c
   452             T_PARTIAL => (RC.add_foltype_funcs (tp, Symtab.update(c,0) funcs), preds)
   359 	    val ntys = if !typ_level = T_CONST then length tvars else 0
   453           | _ =>
   360 	    val addit = Symtab.update(c, arity+ntys)
   454                let val arity = min_arity_of c
   361 	in
   455                    val ntys = if !typ_level = T_CONST then length tvars else 0
   362 	    if needs_hBOOL c then (addtypes tvars (addit funcs), preds)
   456                    val addit = Symtab.update(c, arity+ntys)
   363 	    else (addtypes tvars funcs, addit preds)
   457                in
   364 	end
   458                    if needs_hBOOL c then (addtypes tvars (addit funcs), preds)
       
   459                    else (addtypes tvars funcs, addit preds)
       
   460                end)
       
   461   | add_decls (CombVar(_,ctp), (funcs,preds)) =
   365   | add_decls (CombVar(_,ctp), (funcs,preds)) =
   462       (RC.add_foltype_funcs (ctp,funcs), preds)
   366       (RC.add_foltype_funcs (ctp,funcs), preds)
   463   | add_decls (CombApp(P,Q),decls) = add_decls(P,add_decls (Q,decls));
   367   | add_decls (CombApp(P,Q),decls) = add_decls(P,add_decls (Q,decls));
   464 
   368 
   465 fun add_literal_decls (Literal(_,c), decls) = add_decls (c,decls);
   369 fun add_literal_decls (Literal(_,c), decls) = add_decls (c,decls);
   467 fun add_clause_decls (Clause {literals, ...}, decls) =
   371 fun add_clause_decls (Clause {literals, ...}, decls) =
   468     foldl add_literal_decls decls literals
   372     foldl add_literal_decls decls literals
   469     handle Symtab.DUP a => raise ERROR ("function " ^ a ^ " has multiple arities")
   373     handle Symtab.DUP a => raise ERROR ("function " ^ a ^ " has multiple arities")
   470 
   374 
   471 fun decls_of_clauses clauses arity_clauses =
   375 fun decls_of_clauses clauses arity_clauses =
   472   let val happ_ar = case !typ_level of T_PARTIAL => 3 | _ => 2
   376   let val init_functab = Symtab.update (type_wrapper,2) (Symtab.update ("hAPP",2) RC.init_functab)
   473       val init_functab = Symtab.update (type_wrapper,2) (Symtab.update ("hAPP",happ_ar) RC.init_functab)
       
   474       val init_predtab = Symtab.update ("hBOOL",1) Symtab.empty
   377       val init_predtab = Symtab.update ("hBOOL",1) Symtab.empty
   475       val (functab,predtab) = (foldl add_clause_decls (init_functab, init_predtab) clauses)
   378       val (functab,predtab) = (foldl add_clause_decls (init_functab, init_predtab) clauses)
   476   in
   379   in
   477       (Symtab.dest (foldl RC.add_arityClause_funcs functab arity_clauses),
   380       (Symtab.dest (foldl RC.add_arityClause_funcs functab arity_clauses),
   478        Symtab.dest predtab)
   381        Symtab.dest predtab)
   490                       (foldl add_clause_preds Symtab.empty clauses)
   393                       (foldl add_clause_preds Symtab.empty clauses)
   491                       arity_clauses)
   394                       arity_clauses)
   492                clsrel_clauses)
   395                clsrel_clauses)
   493 
   396 
   494 
   397 
   495 
       
   496 (**********************************************************************)
   398 (**********************************************************************)
   497 (* write clauses to files                                             *)
   399 (* write clauses to files                                             *)
   498 (**********************************************************************)
   400 (**********************************************************************)
   499 
       
   500 
   401 
   501 val init_counters =
   402 val init_counters =
   502     Symtab.make [("c_COMBI", 0), ("c_COMBK", 0),
   403     Symtab.make [("c_COMBI", 0), ("c_COMBK", 0),
   503                  ("c_COMBB", 0), ("c_COMBC", 0),
   404                  ("c_COMBB", 0), ("c_COMBC", 0),
   504                  ("c_COMBS", 0), ("c_COMBB_e", 0),
   405                  ("c_COMBS", 0), ("c_COMBB_e", 0),
   572 fun display_arity (c,n) =
   473 fun display_arity (c,n) =
   573   Output.debug (fn () => "Constant: " ^ c ^ " arity:\t" ^ Int.toString n ^
   474   Output.debug (fn () => "Constant: " ^ c ^ " arity:\t" ^ Int.toString n ^
   574                 (if needs_hBOOL c then " needs hBOOL" else ""));
   475                 (if needs_hBOOL c then " needs hBOOL" else ""));
   575 
   476 
   576 fun count_constants (conjectures, axclauses, helper_clauses) =
   477 fun count_constants (conjectures, axclauses, helper_clauses) =
   577   if !minimize_applies andalso !typ_level<>T_PARTIAL then
   478   if !minimize_applies then
   578     (const_min_arity := Symtab.empty;
   479     (const_min_arity := Symtab.empty;
   579      const_needs_hBOOL := Symtab.empty;
   480      const_needs_hBOOL := Symtab.empty;
   580      List.app count_constants_clause conjectures;
   481      List.app count_constants_clause conjectures;
   581      List.app count_constants_clause axclauses;
   482      List.app count_constants_clause axclauses;
   582      List.app count_constants_clause helper_clauses;
   483      List.app count_constants_clause helper_clauses;