src/HOL/Tools/Nitpick/nitpick_kodkod.ML
changeset 39345 062c10ff848c
parent 39316 b6c4385ab400
child 39358 6bc2f7971df0
equal deleted inserted replaced
39344:9de74cdcd833 39345:062c10ff848c
    21   val kk_tuple : bool -> int -> int list -> Kodkod.tuple
    21   val kk_tuple : bool -> int -> int list -> Kodkod.tuple
    22   val tuple_set_from_atom_schema : (int * int) list -> Kodkod.tuple_set
    22   val tuple_set_from_atom_schema : (int * int) list -> Kodkod.tuple_set
    23   val sequential_int_bounds : int -> Kodkod.int_bound list
    23   val sequential_int_bounds : int -> Kodkod.int_bound list
    24   val pow_of_two_int_bounds : int -> int -> Kodkod.int_bound list
    24   val pow_of_two_int_bounds : int -> int -> Kodkod.int_bound list
    25   val bounds_and_axioms_for_built_in_rels_in_formulas :
    25   val bounds_and_axioms_for_built_in_rels_in_formulas :
    26     bool -> int Typtab.table -> int -> int -> int -> int -> Kodkod.formula list
    26     bool -> int -> int -> int -> int -> Kodkod.formula list
    27     -> Kodkod.bound list * Kodkod.formula list
    27     -> Kodkod.bound list * Kodkod.formula list
    28   val bound_for_plain_rel : Proof.context -> bool -> nut -> Kodkod.bound
    28   val bound_for_plain_rel : Proof.context -> bool -> nut -> Kodkod.bound
    29   val bound_for_sel_rel :
    29   val bound_for_sel_rel :
    30     Proof.context -> bool -> datatype_spec list -> nut -> Kodkod.bound
    30     Proof.context -> bool -> datatype_spec list -> nut -> Kodkod.bound
    31   val merge_bounds : Kodkod.bound list -> Kodkod.bound list
    31   val merge_bounds : Kodkod.bound list -> Kodkod.bound list
   128         aux (iter - 1) (2 * pow_of_two) (j + 1)
   128         aux (iter - 1) (2 * pow_of_two) (j + 1)
   129   in aux (bits + 1) 1 j0 end
   129   in aux (bits + 1) 1 j0 end
   130 
   130 
   131 fun built_in_rels_in_formulas formulas =
   131 fun built_in_rels_in_formulas formulas =
   132   let
   132   let
   133     fun rel_expr_func (KK.Rel (x as (n, j))) =
   133     fun rel_expr_func (KK.Rel (x as (_, j))) =
   134         (j < 0 andalso x <> unsigned_bit_word_sel_rel andalso
   134         (j < 0 andalso x <> unsigned_bit_word_sel_rel andalso
   135          x <> signed_bit_word_sel_rel)
   135          x <> signed_bit_word_sel_rel)
   136         ? insert (op =) x
   136         ? insert (op =) x
   137       | rel_expr_func _ = I
   137       | rel_expr_func _ = I
   138     val expr_F = {formula_func = K I, rel_expr_func = rel_expr_func,
   138     val expr_F = {formula_func = K I, rel_expr_func = rel_expr_func,
   202 fun isa_norm_frac (m, n) =
   202 fun isa_norm_frac (m, n) =
   203   if n < 0 then isa_norm_frac (~m, ~n)
   203   if n < 0 then isa_norm_frac (~m, ~n)
   204   else if m = 0 orelse n = 0 then (0, 1)
   204   else if m = 0 orelse n = 0 then (0, 1)
   205   else let val p = isa_zgcd (m, n) in (isa_div (m, p), isa_div (n, p)) end
   205   else let val p = isa_zgcd (m, n) in (isa_div (m, p), isa_div (n, p)) end
   206 
   206 
   207 fun tabulate_built_in_rel debug ofs univ_card nat_card int_card j0
   207 fun tabulate_built_in_rel debug univ_card nat_card int_card j0
   208                           (x as (n, _)) =
   208                           (x as (n, _)) =
   209   (check_arity "" univ_card n;
   209   (check_arity "" univ_card n;
   210    if x = not3_rel then
   210    if x = not3_rel then
   211      ("not3", tabulate_func1 debug univ_card (2, j0) (curry (op -) 1))
   211      ("not3", tabulate_func1 debug univ_card (2, j0) (curry (op -) 1))
   212    else if x = suc_rel then
   212    else if x = suc_rel then
   243      ("norm_frac", tabulate_int_op2_2 debug univ_card (int_card, j0)
   243      ("norm_frac", tabulate_int_op2_2 debug univ_card (int_card, j0)
   244                                       isa_norm_frac)
   244                                       isa_norm_frac)
   245    else
   245    else
   246      raise ARG ("Nitpick_Kodkod.tabulate_built_in_rel", "unknown relation"))
   246      raise ARG ("Nitpick_Kodkod.tabulate_built_in_rel", "unknown relation"))
   247 
   247 
   248 fun bound_for_built_in_rel debug ofs univ_card nat_card int_card main_j0
   248 fun bound_for_built_in_rel debug univ_card nat_card int_card main_j0
   249                            (x as (n, j)) =
   249                            (x as (n, j)) =
   250   if n = 2 andalso j <= suc_rels_base then
   250   if n = 2 andalso j <= suc_rels_base then
   251     let val (y as (k, j0), tabulate) = atom_seq_for_suc_rel x in
   251     let val (y as (k, j0), tabulate) = atom_seq_for_suc_rel x in
   252       ([(x, "suc")],
   252       ([(x, "suc")],
   253        if tabulate then
   253        if tabulate then
   256        else
   256        else
   257          [KK.TupleSet [], tuple_set_from_atom_schema [y, y]])
   257          [KK.TupleSet [], tuple_set_from_atom_schema [y, y]])
   258     end
   258     end
   259   else
   259   else
   260     let
   260     let
   261       val (nick, ts) = tabulate_built_in_rel debug ofs univ_card nat_card
   261       val (nick, ts) = tabulate_built_in_rel debug univ_card nat_card int_card
   262                                              int_card main_j0 x
   262                                              main_j0 x
   263     in ([(x, nick)], [KK.TupleSet ts]) end
   263     in ([(x, nick)], [KK.TupleSet ts]) end
   264 
   264 
   265 fun axiom_for_built_in_rel (x as (n, j)) =
   265 fun axiom_for_built_in_rel (x as (n, j)) =
   266   if n = 2 andalso j <= suc_rels_base then
   266   if n = 2 andalso j <= suc_rels_base then
   267     let val (y as (k, j0), tabulate) = atom_seq_for_suc_rel x in
   267     let val (y as (k, j0), tabulate) = atom_seq_for_suc_rel x in
   272       else
   272       else
   273         SOME (KK.TotalOrdering (x, KK.AtomSeq y, KK.Atom j0, KK.Atom (j0 + 1)))
   273         SOME (KK.TotalOrdering (x, KK.AtomSeq y, KK.Atom j0, KK.Atom (j0 + 1)))
   274     end
   274     end
   275   else
   275   else
   276     NONE
   276     NONE
   277 fun bounds_and_axioms_for_built_in_rels_in_formulas debug ofs univ_card nat_card
   277 fun bounds_and_axioms_for_built_in_rels_in_formulas debug univ_card nat_card
   278                                                     int_card main_j0 formulas =
   278                                                     int_card main_j0 formulas =
   279   let val rels = built_in_rels_in_formulas formulas in
   279   let val rels = built_in_rels_in_formulas formulas in
   280     (map (bound_for_built_in_rel debug ofs univ_card nat_card int_card main_j0)
   280     (map (bound_for_built_in_rel debug univ_card nat_card int_card main_j0)
   281          rels,
   281          rels,
   282      map_filter axiom_for_built_in_rel rels)
   282      map_filter axiom_for_built_in_rel rels)
   283   end
   283   end
   284 
   284 
   285 fun bound_comment ctxt debug nick T R =
   285 fun bound_comment ctxt debug nick T R =
   739   kk_no (kk_intersect
   739   kk_no (kk_intersect
   740              (loop_path_rel_expr kk nfa (pull start_T (map fst nfa)) start_T)
   740              (loop_path_rel_expr kk nfa (pull start_T (map fst nfa)) start_T)
   741              KK.Iden)
   741              KK.Iden)
   742 (* Cycle breaking in the bounds takes care of singly recursive datatypes, hence
   742 (* Cycle breaking in the bounds takes care of singly recursive datatypes, hence
   743    the first equation. *)
   743    the first equation. *)
   744 fun acyclicity_axioms_for_datatypes kk [_] = []
   744 fun acyclicity_axioms_for_datatypes _ [_] = []
   745   | acyclicity_axioms_for_datatypes kk nfas =
   745   | acyclicity_axioms_for_datatypes kk nfas =
   746     maps (fn nfa => map (acyclicity_axiom_for_datatype kk nfa o fst) nfa) nfas
   746     maps (fn nfa => map (acyclicity_axiom_for_datatype kk nfa o fst) nfa) nfas
   747 
   747 
   748 fun all_ge ({kk_join, kk_reflexive_closure, ...} : kodkod_constrs) z r =
   748 fun all_ge ({kk_join, kk_reflexive_closure, ...} : kodkod_constrs) z r =
   749   kk_join r (kk_reflexive_closure (KK.Rel (suc_rel_for_atom_seq z)))
   749   kk_join r (kk_reflexive_closure (KK.Rel (suc_rel_for_atom_seq z)))
   798        [{const = (_, T'), ...}] => T = T'
   798        [{const = (_, T'), ...}] => T = T'
   799      | _ => false)
   799      | _ => false)
   800   | NONE => false
   800   | NONE => false
   801 
   801 
   802 fun sym_break_axioms_for_constr_pair hol_ctxt binarize
   802 fun sym_break_axioms_for_constr_pair hol_ctxt binarize
   803        (kk as {kk_all, kk_or, kk_iff, kk_implies, kk_and, kk_some, kk_subset,
   803        (kk as {kk_all, kk_or, kk_implies, kk_and, kk_some, kk_intersect,
   804                kk_intersect, kk_join, kk_project, ...}) rel_table nfas dtypes
   804                kk_join, ...}) rel_table nfas dtypes
   805        (constr_ord,
   805        (constr_ord,
   806         ({const = const1 as (_, T1), delta = delta1, epsilon = epsilon1, ...},
   806         ({const = const1 as (_, T1), delta = delta1, epsilon = epsilon1, ...},
   807          {const = const2 as (_, T2), delta = delta2, epsilon = epsilon2, ...})
   807          {const = const2 as (_, _), delta = delta2, epsilon = epsilon2, ...})
   808         : constr_spec * constr_spec) =
   808         : constr_spec * constr_spec) =
   809   let
   809   let
   810     val dataT = body_type T1
   810     val dataT = body_type T1
   811     val nfa = nfas |> find_first (exists (curry (op =) dataT o fst)) |> these
   811     val nfa = nfas |> find_first (exists (curry (op =) dataT o fst)) |> these
   812     val rec_Ts = nfa |> map fst
   812     val rec_Ts = nfa |> map fst
  1416       | Op1 (SafeThe, _, R, u1) =>
  1416       | Op1 (SafeThe, _, R, u1) =>
  1417         if is_opt_rep R then
  1417         if is_opt_rep R then
  1418           kk_join (to_rep (Func (unopt_rep R, Opt bool_atom_R)) u1) true_atom
  1418           kk_join (to_rep (Func (unopt_rep R, Opt bool_atom_R)) u1) true_atom
  1419         else
  1419         else
  1420           to_rep (Func (R, Formula Neut)) u1
  1420           to_rep (Func (R, Formula Neut)) u1
  1421       | Op1 (First, T, R, u1) => to_nth_pair_sel 0 T R u1
  1421       | Op1 (First, _, R, u1) => to_nth_pair_sel 0 R u1
  1422       | Op1 (Second, T, R, u1) => to_nth_pair_sel 1 T R u1
  1422       | Op1 (Second, _, R, u1) => to_nth_pair_sel 1 R u1
  1423       | Op1 (Cast, _, R, u1) =>
  1423       | Op1 (Cast, _, R, u1) =>
  1424         ((case rep_of u1 of
  1424         ((case rep_of u1 of
  1425             Formula _ =>
  1425             Formula _ =>
  1426             (case unopt_rep R of
  1426             (case unopt_rep R of
  1427                Atom (2, j0) => atom_from_formula kk j0 (to_f u1)
  1427                Atom (2, j0) => atom_from_formula kk j0 (to_f u1)
  1683     and to_expr_assign (FormulaReg (j, _, _)) u =
  1683     and to_expr_assign (FormulaReg (j, _, _)) u =
  1684         KK.AssignFormulaReg (j, to_f u)
  1684         KK.AssignFormulaReg (j, to_f u)
  1685       | to_expr_assign (RelReg (j, _, R)) u =
  1685       | to_expr_assign (RelReg (j, _, R)) u =
  1686         KK.AssignRelReg ((arity_of_rep R, j), to_r u)
  1686         KK.AssignRelReg ((arity_of_rep R, j), to_r u)
  1687       | to_expr_assign u1 _ = raise NUT ("Nitpick_Kodkod.to_expr_assign", [u1])
  1687       | to_expr_assign u1 _ = raise NUT ("Nitpick_Kodkod.to_expr_assign", [u1])
  1688     and to_atom (x as (k, j0)) u =
  1688     and to_atom (x as (_, j0)) u =
  1689       case rep_of u of
  1689       case rep_of u of
  1690         Formula _ => atom_from_formula kk j0 (to_f u)
  1690         Formula _ => atom_from_formula kk j0 (to_f u)
  1691       | R => atom_from_rel_expr kk x R (to_r u)
  1691       | R => atom_from_rel_expr kk x R (to_r u)
  1692     and to_struct Rs u = struct_from_rel_expr kk Rs (rep_of u) (to_r u)
  1692     and to_struct Rs u = struct_from_rel_expr kk Rs (rep_of u) (to_r u)
  1693     and to_vect k R u = vect_from_rel_expr kk k R (rep_of u) (to_r u)
  1693     and to_vect k R u = vect_from_rel_expr kk k R (rep_of u) (to_r u)
  1725       end
  1725       end
  1726     and to_project new_R old_R r j0 =
  1726     and to_project new_R old_R r j0 =
  1727       rel_expr_from_rel_expr kk new_R old_R
  1727       rel_expr_from_rel_expr kk new_R old_R
  1728                              (kk_project_seq r j0 (arity_of_rep old_R))
  1728                              (kk_project_seq r j0 (arity_of_rep old_R))
  1729     and to_product Rs us = fold1 kk_product (map (uncurry to_opt) (Rs ~~ us))
  1729     and to_product Rs us = fold1 kk_product (map (uncurry to_opt) (Rs ~~ us))
  1730     and to_nth_pair_sel n res_T res_R u =
  1730     and to_nth_pair_sel n res_R u =
  1731       case u of
  1731       case u of
  1732         Tuple (_, _, us) => to_rep res_R (nth us n)
  1732         Tuple (_, _, us) => to_rep res_R (nth us n)
  1733       | _ => let
  1733       | _ => let
  1734                val R = rep_of u
  1734                val R = rep_of u
  1735                val (a_T, b_T) = HOLogic.dest_prodT (type_of u)
  1735                val (a_T, b_T) = HOLogic.dest_prodT (type_of u)
  1789                             NONE => []
  1789                             NONE => []
  1790                           | SOME oper =>
  1790                           | SOME oper =>
  1791                             [KK.IntEq (KK.IntReg 2,
  1791                             [KK.IntEq (KK.IntReg 2,
  1792                                        oper (KK.IntReg 0) (KK.IntReg 1))]))))
  1792                                        oper (KK.IntReg 0) (KK.IntReg 1))]))))
  1793       end
  1793       end
  1794     and to_apply (R as Formula _) func_u arg_u =
  1794     and to_apply (R as Formula _) _ _ =
  1795         raise REP ("Nitpick_Kodkod.to_apply", [R])
  1795         raise REP ("Nitpick_Kodkod.to_apply", [R])
  1796       | to_apply res_R func_u arg_u =
  1796       | to_apply res_R func_u arg_u =
  1797         case unopt_rep (rep_of func_u) of
  1797         case unopt_rep (rep_of func_u) of
  1798           Atom (1, j0) =>
  1798           Atom (1, j0) =>
  1799           to_guard [arg_u] res_R
  1799           to_guard [arg_u] res_R