src/HOL/Tools/refute.ML
changeset 26939 1035c89b4c02
parent 26931 aa226d8405a8
child 26957 e3f04fdd994d
equal deleted inserted replaced
26938:64e850c3da9e 26939:1035c89b4c02
   217 
   217 
   218   fun interpret thy model args t =
   218   fun interpret thy model args t =
   219     case get_first (fn (_, f) => f thy model args t)
   219     case get_first (fn (_, f) => f thy model args t)
   220       (#interpreters (RefuteData.get thy)) of
   220       (#interpreters (RefuteData.get thy)) of
   221       NONE   => raise REFUTE ("interpret",
   221       NONE   => raise REFUTE ("interpret",
   222         "no interpreter for term " ^ quote (Sign.string_of_term thy t))
   222         "no interpreter for term " ^ quote (Syntax.string_of_term_global thy t))
   223     | SOME x => x;
   223     | SOME x => x;
   224 
   224 
   225 (* ------------------------------------------------------------------------- *)
   225 (* ------------------------------------------------------------------------- *)
   226 (* print: converts the interpretation 'intr', which must denote a term of    *)
   226 (* print: converts the interpretation 'intr', which must denote a term of    *)
   227 (*        type 'T', into a term using a suitable printer                     *)
   227 (*        type 'T', into a term using a suitable printer                     *)
   232 
   232 
   233   fun print thy model T intr assignment =
   233   fun print thy model T intr assignment =
   234     case get_first (fn (_, f) => f thy model T intr assignment)
   234     case get_first (fn (_, f) => f thy model T intr assignment)
   235       (#printers (RefuteData.get thy)) of
   235       (#printers (RefuteData.get thy)) of
   236       NONE   => raise REFUTE ("print",
   236       NONE   => raise REFUTE ("print",
   237         "no printer for type " ^ quote (Sign.string_of_typ thy T))
   237         "no printer for type " ^ quote (Syntax.string_of_typ_global thy T))
   238     | SOME x => x;
   238     | SOME x => x;
   239 
   239 
   240 (* ------------------------------------------------------------------------- *)
   240 (* ------------------------------------------------------------------------- *)
   241 (* print_model: turns the model into a string, using a fixed interpretation  *)
   241 (* print_model: turns the model into a string, using a fixed interpretation  *)
   242 (*              (given by an assignment for Boolean variables) and suitable  *)
   242 (*              (given by an assignment for Boolean variables) and suitable  *)
   251     val typs_msg =
   251     val typs_msg =
   252       if null typs then
   252       if null typs then
   253         "empty universe (no type variables in term)\n"
   253         "empty universe (no type variables in term)\n"
   254       else
   254       else
   255         "Size of types: " ^ commas (map (fn (T, i) =>
   255         "Size of types: " ^ commas (map (fn (T, i) =>
   256           Sign.string_of_typ thy T ^ ": " ^ string_of_int i) typs) ^ "\n"
   256           Syntax.string_of_typ_global thy T ^ ": " ^ string_of_int i) typs) ^ "\n"
   257     val show_consts_msg =
   257     val show_consts_msg =
   258       if not (!show_consts) andalso Library.exists (is_Const o fst) terms then
   258       if not (!show_consts) andalso Library.exists (is_Const o fst) terms then
   259         "set \"show_consts\" to show the interpretation of constants\n"
   259         "set \"show_consts\" to show the interpretation of constants\n"
   260       else
   260       else
   261         ""
   261         ""
   264         "empty interpretation (no free variables in term)\n"
   264         "empty interpretation (no free variables in term)\n"
   265       else
   265       else
   266         cat_lines (List.mapPartial (fn (t, intr) =>
   266         cat_lines (List.mapPartial (fn (t, intr) =>
   267           (* print constants only if 'show_consts' is true *)
   267           (* print constants only if 'show_consts' is true *)
   268           if (!show_consts) orelse not (is_Const t) then
   268           if (!show_consts) orelse not (is_Const t) then
   269             SOME (Sign.string_of_term thy t ^ ": " ^
   269             SOME (Syntax.string_of_term_global thy t ^ ": " ^
   270               Sign.string_of_term thy
   270               Syntax.string_of_term_global thy
   271                 (print thy model (Term.type_of t) intr assignment))
   271                 (print thy model (Term.type_of t) intr assignment))
   272           else
   272           else
   273             NONE) terms) ^ "\n"
   273             NONE) terms) ^ "\n"
   274   in
   274   in
   275     typs_msg ^ show_consts_msg ^ terms_msg
   275     typs_msg ^ show_consts_msg ^ terms_msg
   454         case Type.lookup typeSubs v of
   454         case Type.lookup typeSubs v of
   455           NONE =>
   455           NONE =>
   456           (* schematic type variable not instantiated *)
   456           (* schematic type variable not instantiated *)
   457           raise REFUTE ("monomorphic_term",
   457           raise REFUTE ("monomorphic_term",
   458             "no substitution for type variable " ^ fst (fst v) ^
   458             "no substitution for type variable " ^ fst (fst v) ^
   459             " in term " ^ Sign.string_of_term CPure.thy t)
   459             " in term " ^ Syntax.string_of_term_global CPure.thy t)
   460         | SOME typ =>
   460         | SOME typ =>
   461           typ)) t;
   461           typ)) t;
   462 
   462 
   463 (* ------------------------------------------------------------------------- *)
   463 (* ------------------------------------------------------------------------- *)
   464 (* specialize_type: given a constant 's' of type 'T', which is a subterm of  *)
   464 (* specialize_type: given a constant 's' of type 'T', which is a subterm of  *)
   785       (* string list *)
   785       (* string list *)
   786       val sort = (case T of
   786       val sort = (case T of
   787           TFree (_, sort) => sort
   787           TFree (_, sort) => sort
   788         | TVar (_, sort)  => sort
   788         | TVar (_, sort)  => sort
   789         | _               => raise REFUTE ("collect_axioms", "type " ^
   789         | _               => raise REFUTE ("collect_axioms", "type " ^
   790           Sign.string_of_typ thy T ^ " is not a variable"))
   790           Syntax.string_of_typ_global thy T ^ " is not a variable"))
   791       (* obtain axioms for all superclasses *)
   791       (* obtain axioms for all superclasses *)
   792       val superclasses = sort @ (maps (Sign.super_classes thy) sort)
   792       val superclasses = sort @ (maps (Sign.super_classes thy) sort)
   793       (* merely an optimization, because 'collect_this_axiom' disallows *)
   793       (* merely an optimization, because 'collect_this_axiom' disallows *)
   794       (* duplicate axioms anyway:                                       *)
   794       (* duplicate axioms anyway:                                       *)
   795       val superclasses = distinct (op =) superclasses
   795       val superclasses = distinct (op =) superclasses
   805           (axname, ax)
   805           (axname, ax)
   806         | [(idx, S)] =>
   806         | [(idx, S)] =>
   807           (axname, monomorphic_term (Vartab.make [(idx, (S, T))]) ax)
   807           (axname, monomorphic_term (Vartab.make [(idx, (S, T))]) ax)
   808         | _ =>
   808         | _ =>
   809           raise REFUTE ("collect_axioms", "class axiom " ^ axname ^ " (" ^
   809           raise REFUTE ("collect_axioms", "class axiom " ^ axname ^ " (" ^
   810             Sign.string_of_term thy ax ^
   810             Syntax.string_of_term_global thy ax ^
   811             ") contains more than one type variable")))
   811             ") contains more than one type variable")))
   812         class_axioms
   812         class_axioms
   813     in
   813     in
   814       fold collect_this_axiom monomorphic_class_axioms axs
   814       fold collect_this_axiom monomorphic_class_axioms axs
   815     end
   815     end
   910               val class   = Logic.class_of_const s
   910               val class   = Logic.class_of_const s
   911               val inclass = Logic.mk_inclass (TVar (("'a", 0), [class]), class)
   911               val inclass = Logic.mk_inclass (TVar (("'a", 0), [class]), class)
   912               val ax_in   = SOME (specialize_type thy (s, T) inclass)
   912               val ax_in   = SOME (specialize_type thy (s, T) inclass)
   913                 (* type match may fail due to sort constraints *)
   913                 (* type match may fail due to sort constraints *)
   914                 handle Type.TYPE_MATCH => NONE
   914                 handle Type.TYPE_MATCH => NONE
   915               val ax_1 = Option.map (fn ax => (Sign.string_of_term thy ax, ax))
   915               val ax_1 = Option.map (fn ax => (Syntax.string_of_term_global thy ax, ax))
   916                 ax_in
   916                 ax_in
   917               val ax_2 = Option.map (apsnd (specialize_type thy (s, T)))
   917               val ax_2 = Option.map (apsnd (specialize_type thy (s, T)))
   918                 (get_classdef thy class)
   918                 (get_classdef thy class)
   919             in
   919             in
   920               collect_type_axioms (fold collect_this_axiom
   920               collect_type_axioms (fold collect_this_axiom
   973             (* sanity check: every element in 'dtyps' must be a *)
   973             (* sanity check: every element in 'dtyps' must be a *)
   974             (* 'DtTFree'                                        *)
   974             (* 'DtTFree'                                        *)
   975             val _ = if Library.exists (fn d =>
   975             val _ = if Library.exists (fn d =>
   976               case d of DatatypeAux.DtTFree _ => false | _ => true) typs then
   976               case d of DatatypeAux.DtTFree _ => false | _ => true) typs then
   977               raise REFUTE ("ground_types", "datatype argument (for type "
   977               raise REFUTE ("ground_types", "datatype argument (for type "
   978                 ^ Sign.string_of_typ thy T ^ ") is not a variable")
   978                 ^ Syntax.string_of_typ_global thy T ^ ") is not a variable")
   979             else ()
   979             else ()
   980             (* required for mutually recursive datatypes; those need to   *)
   980             (* required for mutually recursive datatypes; those need to   *)
   981             (* be added even if they are an instance of an otherwise non- *)
   981             (* be added even if they are an instance of an otherwise non- *)
   982             (* recursive datatype                                         *)
   982             (* recursive datatype                                         *)
   983             fun collect_dtyp (d, acc) =
   983             fun collect_dtyp (d, acc) =
  1158   let
  1158   let
  1159     (* unit -> unit *)
  1159     (* unit -> unit *)
  1160     fun wrapper () =
  1160     fun wrapper () =
  1161     let
  1161     let
  1162       val u      = unfold_defs thy t
  1162       val u      = unfold_defs thy t
  1163       val _      = writeln ("Unfolded term: " ^ Sign.string_of_term thy u)
  1163       val _      = writeln ("Unfolded term: " ^ Syntax.string_of_term_global thy u)
  1164       val axioms = collect_axioms thy u
  1164       val axioms = collect_axioms thy u
  1165       (* Term.typ list *)
  1165       (* Term.typ list *)
  1166       val types = Library.foldl (fn (acc, t') =>
  1166       val types = Library.foldl (fn (acc, t') =>
  1167         acc union (ground_types thy t')) ([], u :: axioms)
  1167         acc union (ground_types thy t')) ([], u :: axioms)
  1168       val _     = writeln ("Ground types: "
  1168       val _     = writeln ("Ground types: "
  1169         ^ (if null types then "none."
  1169         ^ (if null types then "none."
  1170            else commas (map (Sign.string_of_typ thy) types)))
  1170            else commas (map (Syntax.string_of_typ_global thy) types)))
  1171       (* we can only consider fragments of recursive IDTs, so we issue a  *)
  1171       (* we can only consider fragments of recursive IDTs, so we issue a  *)
  1172       (* warning if the formula contains a recursive IDT                  *)
  1172       (* warning if the formula contains a recursive IDT                  *)
  1173       (* TODO: no warning needed for /positive/ occurrences of IDTs       *)
  1173       (* TODO: no warning needed for /positive/ occurrences of IDTs       *)
  1174       val _ = if Library.exists (fn
  1174       val _ = if Library.exists (fn
  1175           Type (s, _) =>
  1175           Type (s, _) =>
  1254       maxtime>=0 orelse
  1254       maxtime>=0 orelse
  1255         error ("\"maxtime\" is " ^ string_of_int maxtime ^ ", must be at least 0");
  1255         error ("\"maxtime\" is " ^ string_of_int maxtime ^ ", must be at least 0");
  1256       (* enter loop with or without time limit *)
  1256       (* enter loop with or without time limit *)
  1257       writeln ("Trying to find a model that "
  1257       writeln ("Trying to find a model that "
  1258         ^ (if negate then "refutes" else "satisfies") ^ ": "
  1258         ^ (if negate then "refutes" else "satisfies") ^ ": "
  1259         ^ Sign.string_of_term thy t);
  1259         ^ Syntax.string_of_term_global thy t);
  1260       if maxtime>0 then (
  1260       if maxtime>0 then (
  1261         TimeLimit.timeLimit (Time.fromSeconds maxtime)
  1261         TimeLimit.timeLimit (Time.fromSeconds maxtime)
  1262           wrapper ()
  1262           wrapper ()
  1263         handle TimeLimit.TimeOut =>
  1263         handle TimeLimit.TimeOut =>
  1264           writeln ("\nSearch terminated, time limit (" ^ string_of_int maxtime
  1264           writeln ("\nSearch terminated, time limit (" ^ string_of_int maxtime
  2039               val _ = if Library.exists (fn d =>
  2039               val _ = if Library.exists (fn d =>
  2040                   case d of DatatypeAux.DtTFree _ => false | _ => true) dtyps
  2040                   case d of DatatypeAux.DtTFree _ => false | _ => true) dtyps
  2041                 then
  2041                 then
  2042                   raise REFUTE ("IDT_interpreter",
  2042                   raise REFUTE ("IDT_interpreter",
  2043                     "datatype argument (for type "
  2043                     "datatype argument (for type "
  2044                     ^ Sign.string_of_typ thy (Type (s, Ts))
  2044                     ^ Syntax.string_of_typ_global thy (Type (s, Ts))
  2045                     ^ ") is not a variable")
  2045                     ^ ") is not a variable")
  2046                 else ()
  2046                 else ()
  2047               (* if the model specifies a depth for the current type, *)
  2047               (* if the model specifies a depth for the current type, *)
  2048               (* decrement it to avoid infinite recursion             *)
  2048               (* decrement it to avoid infinite recursion             *)
  2049               val typs'    = case depth of NONE => typs | SOME n =>
  2049               val typs'    = case depth of NONE => typs | SOME n =>
  2163               val _ = if Library.exists (fn d =>
  2163               val _ = if Library.exists (fn d =>
  2164                   case d of DatatypeAux.DtTFree _ => false | _ => true) dtyps
  2164                   case d of DatatypeAux.DtTFree _ => false | _ => true) dtyps
  2165                 then
  2165                 then
  2166                   raise REFUTE ("IDT_constructor_interpreter",
  2166                   raise REFUTE ("IDT_constructor_interpreter",
  2167                     "datatype argument (for type "
  2167                     "datatype argument (for type "
  2168                     ^ Sign.string_of_typ thy T
  2168                     ^ Syntax.string_of_typ_global thy T
  2169                     ^ ") is not a variable")
  2169                     ^ ") is not a variable")
  2170                 else ()
  2170                 else ()
  2171               (* decrement depth for the IDT 'T' *)
  2171               (* decrement depth for the IDT 'T' *)
  2172               val typs' = (case AList.lookup (op =) typs T of NONE => typs
  2172               val typs' = (case AList.lookup (op =) typs T of NONE => typs
  2173                 | SOME n => AList.update (op =) (T, n-1) typs)
  2173                 | SOME n => AList.update (op =) (T, n-1) typs)
  2223               val _ = if Library.exists (fn d =>
  2223               val _ = if Library.exists (fn d =>
  2224                   case d of DatatypeAux.DtTFree _ => false | _ => true) dtyps
  2224                   case d of DatatypeAux.DtTFree _ => false | _ => true) dtyps
  2225                 then
  2225                 then
  2226                   raise REFUTE ("IDT_constructor_interpreter",
  2226                   raise REFUTE ("IDT_constructor_interpreter",
  2227                     "datatype argument (for type "
  2227                     "datatype argument (for type "
  2228                     ^ Sign.string_of_typ thy (Type (s', Ts'))
  2228                     ^ Syntax.string_of_typ_global thy (Type (s', Ts'))
  2229                     ^ ") is not a variable")
  2229                     ^ ") is not a variable")
  2230                 else ()
  2230                 else ()
  2231               (* split the constructors into those occuring before/after *)
  2231               (* split the constructors into those occuring before/after *)
  2232               (* 'Const (s, T)'                                          *)
  2232               (* 'Const (s, T)'                                          *)
  2233               val (constrs1, constrs2) = take_prefix (fn (cname, ctypes) =>
  2233               val (constrs1, constrs2) = take_prefix (fn (cname, ctypes) =>
  3280           (* sanity check: every element in 'dtyps' must be a 'DtTFree' *)
  3280           (* sanity check: every element in 'dtyps' must be a 'DtTFree' *)
  3281           val _ = if Library.exists (fn d =>
  3281           val _ = if Library.exists (fn d =>
  3282               case d of DatatypeAux.DtTFree _ => false | _ => true) dtyps
  3282               case d of DatatypeAux.DtTFree _ => false | _ => true) dtyps
  3283             then
  3283             then
  3284               raise REFUTE ("IDT_printer", "datatype argument (for type " ^
  3284               raise REFUTE ("IDT_printer", "datatype argument (for type " ^
  3285                 Sign.string_of_typ thy (Type (s, Ts)) ^ ") is not a variable")
  3285                 Syntax.string_of_typ_global thy (Type (s, Ts)) ^ ") is not a variable")
  3286             else ()
  3286             else ()
  3287           (* the index of the element in the datatype *)
  3287           (* the index of the element in the datatype *)
  3288           val element = (case intr of
  3288           val element = (case intr of
  3289               Leaf xs => find_index (PropLogic.eval assignment) xs
  3289               Leaf xs => find_index (PropLogic.eval assignment) xs
  3290             | Node _  => raise REFUTE ("IDT_printer",
  3290             | Node _  => raise REFUTE ("IDT_printer",