src/HOL/Tools/Nitpick/nitpick_model.ML
changeset 33224 f93390060bbe
parent 33202 0183ab3ca7b4
child 33549 a2db56854b83
equal deleted inserted replaced
33223:1711610c5b7d 33224:f93390060bbe
     5 Model reconstruction for Nitpick.
     5 Model reconstruction for Nitpick.
     6 *)
     6 *)
     7 
     7 
     8 signature NITPICK_MODEL =
     8 signature NITPICK_MODEL =
     9 sig
     9 sig
    10   type scope = NitpickScope.scope
    10   type scope = Nitpick_Scope.scope
    11   type rep = NitpickRep.rep
    11   type rep = Nitpick_Rep.rep
    12   type nut = NitpickNut.nut
    12   type nut = Nitpick_Nut.nut
    13 
    13 
    14   type params = {
    14   type params = {
    15     show_skolems: bool,
    15     show_skolems: bool,
    16     show_datatypes: bool,
    16     show_datatypes: bool,
    17     show_consts: bool}
    17     show_consts: bool}
    27   val prove_hol_model :
    27   val prove_hol_model :
    28     scope -> Time.time option -> nut list -> nut list -> nut NameTable.table
    28     scope -> Time.time option -> nut list -> nut list -> nut NameTable.table
    29     -> Kodkod.raw_bound list -> term -> bool option
    29     -> Kodkod.raw_bound list -> term -> bool option
    30 end;
    30 end;
    31 
    31 
    32 structure NitpickModel : NITPICK_MODEL =
    32 structure Nitpick_Model : NITPICK_MODEL =
    33 struct
    33 struct
    34 
    34 
    35 open NitpickUtil
    35 open Nitpick_Util
    36 open NitpickHOL
    36 open Nitpick_HOL
    37 open NitpickScope
    37 open Nitpick_Scope
    38 open NitpickPeephole
    38 open Nitpick_Peephole
    39 open NitpickRep
    39 open Nitpick_Rep
    40 open NitpickNut
    40 open Nitpick_Nut
    41 
    41 
    42 type params = {
    42 type params = {
    43   show_skolems: bool,
    43   show_skolems: bool,
    44   show_datatypes: bool,
    44   show_datatypes: bool,
    45   show_consts: bool}
    45   show_consts: bool}
    55 (* string -> typ -> int -> string *)
    55 (* string -> typ -> int -> string *)
    56 fun atom_name prefix (T as Type (s, _)) j =
    56 fun atom_name prefix (T as Type (s, _)) j =
    57     prefix ^ substring (short_name s, 0, 1) ^ nat_subscript (j + 1)
    57     prefix ^ substring (short_name s, 0, 1) ^ nat_subscript (j + 1)
    58   | atom_name prefix (T as TFree (s, _)) j =
    58   | atom_name prefix (T as TFree (s, _)) j =
    59     prefix ^ perhaps (try (unprefix "'")) s ^ nat_subscript (j + 1)
    59     prefix ^ perhaps (try (unprefix "'")) s ^ nat_subscript (j + 1)
    60   | atom_name _ T _ = raise TYPE ("NitpickModel.atom_name", [T], [])
    60   | atom_name _ T _ = raise TYPE ("Nitpick_Model.atom_name", [T], [])
    61 (* bool -> typ -> int -> term *)
    61 (* bool -> typ -> int -> term *)
    62 fun atom for_auto T j =
    62 fun atom for_auto T j =
    63   if for_auto then
    63   if for_auto then
    64     Free (atom_name (hd (space_explode "." nitpick_prefix)) T j, T)
    64     Free (atom_name (hd (space_explode "." nitpick_prefix)) T j, T)
    65   else
    65   else
   128   let
   128   let
   129     (* term -> term list * term list *)
   129     (* term -> term list * term list *)
   130     fun aux (Const (s, _)) = (s <> non_opt_name, ([], []))
   130     fun aux (Const (s, _)) = (s <> non_opt_name, ([], []))
   131       | aux (Const (@{const_name fun_upd}, _) $ t0 $ t1 $ t2) =
   131       | aux (Const (@{const_name fun_upd}, _) $ t0 $ t1 $ t2) =
   132         let val (s, (ts1, ts2)) = aux t0 in (s, (t1 :: ts1, t2 :: ts2)) end
   132         let val (s, (ts1, ts2)) = aux t0 in (s, (t1 :: ts1, t2 :: ts2)) end
   133       | aux t = raise TERM ("NitpickModel.dest_plain_fun", [t])
   133       | aux t = raise TERM ("Nitpick_Model.dest_plain_fun", [t])
   134   in apsnd (pairself rev) o aux end
   134   in apsnd (pairself rev) o aux end
   135 
   135 
   136 (* typ -> term -> term list * term *)
   136 (* typ -> term -> term list * term *)
   137 fun break_in_two (Type ("*", [T1, T2]))
   137 fun break_in_two (Type ("*", [T1, T2]))
   138                  (Const (@{const_name Pair}, _) $ t1 $ t2) =
   138                  (Const (@{const_name Pair}, _) $ t1 $ t2) =
   139     break_in_two T2 t2 |>> cons t1
   139     break_in_two T2 t2 |>> cons t1
   140   | break_in_two _ (Const (@{const_name Pair}, _) $ t1 $ t2) = ([t1], t2)
   140   | break_in_two _ (Const (@{const_name Pair}, _) $ t1 $ t2) = ([t1], t2)
   141   | break_in_two _ t = raise TERM ("NitpickModel.break_in_two", [t])
   141   | break_in_two _ t = raise TERM ("Nitpick_Model.break_in_two", [t])
   142 (* typ -> term -> term -> term *)
   142 (* typ -> term -> term -> term *)
   143 fun pair_up (Type ("*", [T1', T2']))
   143 fun pair_up (Type ("*", [T1', T2']))
   144             (t1 as Const (@{const_name Pair},
   144             (t1 as Const (@{const_name Pair},
   145                           Type ("fun", [_, Type ("fun", [_, T1])])) $ t11 $ t12)
   145                           Type ("fun", [_, Type ("fun", [_, T1])])) $ t11 $ t12)
   146             t2 =
   146             t2 =
   178                    (Const (@{const_name fun_upd}, _) $ t0 $ t1 $ t2) =
   178                    (Const (@{const_name fun_upd}, _) $ t0 $ t1 $ t2) =
   179           Const (@{const_name fun_upd},
   179           Const (@{const_name fun_upd},
   180                  [T1' --> T2', T1', T2'] ---> T1' --> T2')
   180                  [T1' --> T2', T1', T2'] ---> T1' --> T2')
   181           $ do_arrow T1' T2' T1 T2 t0 $ do_term T1' T1 t1 $ do_term T2' T2 t2
   181           $ do_arrow T1' T2' T1 T2 t0 $ do_term T1' T1 t1 $ do_term T2' T2 t2
   182         | do_arrow _ _ _ _ t =
   182         | do_arrow _ _ _ _ t =
   183           raise TERM ("NitpickModel.typecast_fun.do_arrow", [t])
   183           raise TERM ("Nitpick_Model.typecast_fun.do_arrow", [t])
   184       and do_fun T1' T2' T1 T2 t =
   184       and do_fun T1' T2' T1 T2 t =
   185         case factor_out_types T1' T1 of
   185         case factor_out_types T1' T1 of
   186           ((_, NONE), (_, NONE)) => t |> do_arrow T1' T2' T1 T2
   186           ((_, NONE), (_, NONE)) => t |> do_arrow T1' T2' T1 T2
   187         | ((_, NONE), (T1a, SOME T1b)) =>
   187         | ((_, NONE), (T1a, SOME T1b)) =>
   188           t |> do_curry T1a T1b T2 |> do_arrow T1' T2' T1a (T1b --> T2)
   188           t |> do_curry T1a T1b T2 |> do_arrow T1' T2' T1a (T1b --> T2)
   189         | ((T1a', SOME T1b'), (_, NONE)) =>
   189         | ((T1a', SOME T1b'), (_, NONE)) =>
   190           t |> do_arrow T1a' (T1b' --> T2') T1 T2 |> do_uncurry T1' T2'
   190           t |> do_arrow T1a' (T1b' --> T2') T1 T2 |> do_uncurry T1' T2'
   191         | _ => raise TYPE ("NitpickModel.typecast_fun.do_fun", [T1, T1'], [])
   191         | _ => raise TYPE ("Nitpick_Model.typecast_fun.do_fun", [T1, T1'], [])
   192       (* typ -> typ -> term -> term *)
   192       (* typ -> typ -> term -> term *)
   193       and do_term (Type ("fun", [T1', T2'])) (Type ("fun", [T1, T2])) t =
   193       and do_term (Type ("fun", [T1', T2'])) (Type ("fun", [T1, T2])) t =
   194           do_fun T1' T2' T1 T2 t
   194           do_fun T1' T2' T1 T2 t
   195         | do_term (T' as Type ("*", Ts' as [T1', T2'])) (Type ("*", [T1, T2]))
   195         | do_term (T' as Type ("*", Ts' as [T1', T2'])) (Type ("*", [T1, T2]))
   196                   (Const (@{const_name Pair}, _) $ t1 $ t2) =
   196                   (Const (@{const_name Pair}, _) $ t1 $ t2) =
   197           Const (@{const_name Pair}, Ts' ---> T')
   197           Const (@{const_name Pair}, Ts' ---> T')
   198           $ do_term T1' T1 t1 $ do_term T2' T2 t2
   198           $ do_term T1' T1 t1 $ do_term T2' T2 t2
   199         | do_term T' T t =
   199         | do_term T' T t =
   200           if T = T' then t
   200           if T = T' then t
   201           else raise TYPE ("NitpickModel.typecast_fun.do_term", [T, T'], [])
   201           else raise TYPE ("Nitpick_Model.typecast_fun.do_term", [T, T'], [])
   202     in if T1' = T1 andalso T2' = T2 then t else do_fun T1' T2' T1 T2 t end
   202     in if T1' = T1 andalso T2' = T2 then t else do_fun T1' T2' T1 T2 t end
   203   | typecast_fun T' _ _ _ = raise TYPE ("NitpickModel.typecast_fun", [T'], [])
   203   | typecast_fun T' _ _ _ = raise TYPE ("Nitpick_Model.typecast_fun", [T'], [])
   204 
   204 
   205 (* term -> string *)
   205 (* term -> string *)
   206 fun truth_const_sort_key @{const True} = "0"
   206 fun truth_const_sort_key @{const True} = "0"
   207   | truth_const_sort_key @{const False} = "2"
   207   | truth_const_sort_key @{const False} = "2"
   208   | truth_const_sort_key _ = "1"
   208   | truth_const_sort_key _ = "1"
   300           val k2 = card_of_type card_assigns T2
   300           val k2 = card_of_type card_assigns T2
   301         in
   301         in
   302           term_for_rep seen T T' (Vect (k1, Atom (k2, 0)))
   302           term_for_rep seen T T' (Vect (k1, Atom (k2, 0)))
   303                        [nth_combination (replicate k1 (k2, 0)) j]
   303                        [nth_combination (replicate k1 (k2, 0)) j]
   304           handle General.Subscript =>
   304           handle General.Subscript =>
   305                  raise ARG ("NitpickModel.reconstruct_term.term_for_atom",
   305                  raise ARG ("Nitpick_Model.reconstruct_term.term_for_atom",
   306                             signed_string_of_int j ^ " for " ^
   306                             signed_string_of_int j ^ " for " ^
   307                             string_for_rep (Vect (k1, Atom (k2, 0))))
   307                             string_for_rep (Vect (k1, Atom (k2, 0))))
   308         end
   308         end
   309       | term_for_atom seen (Type ("*", [T1, T2])) _ j =
   309       | term_for_atom seen (Type ("*", [T1, T2])) _ j =
   310         let val k1 = card_of_type card_assigns T1 in
   310         let val k1 = card_of_type card_assigns T1 in
   348                              (index_seq 0 (length arg_Ts))
   348                              (index_seq 0 (length arg_Ts))
   349             val sel_Rs =
   349             val sel_Rs =
   350               map (fn x => get_first
   350               map (fn x => get_first
   351                                (fn ConstName (s', T', R) =>
   351                                (fn ConstName (s', T', R) =>
   352                                    if (s', T') = x then SOME R else NONE
   352                                    if (s', T') = x then SOME R else NONE
   353                                  | u => raise NUT ("NitpickModel.reconstruct_\
   353                                  | u => raise NUT ("Nitpick_Model.reconstruct_\
   354                                                    \term.term_for_atom", [u]))
   354                                                    \term.term_for_atom", [u]))
   355                                sel_names |> the) sel_xs
   355                                sel_names |> the) sel_xs
   356             val arg_Rs = map (snd o dest_Func) sel_Rs
   356             val arg_Rs = map (snd o dest_Func) sel_Rs
   357             val sel_jsss = map tuples_for_const sel_xs
   357             val sel_jsss = map tuples_for_const sel_xs
   358             val arg_jsss =
   358             val arg_jsss =
   387                          | n1 => case HOLogic.dest_number t2 |> snd of
   387                          | n1 => case HOLogic.dest_number t2 |> snd of
   388                                    1 => mk_num n1
   388                                    1 => mk_num n1
   389                                  | n2 => Const (@{const_name HOL.divide},
   389                                  | n2 => Const (@{const_name HOL.divide},
   390                                                 [num_T, num_T] ---> num_T)
   390                                                 [num_T, num_T] ---> num_T)
   391                                          $ mk_num n1 $ mk_num n2)
   391                                          $ mk_num n1 $ mk_num n2)
   392                       | _ => raise TERM ("NitpickModel.reconstruct_term.term_\
   392                       | _ => raise TERM ("Nitpick_Model.reconstruct_term.term_\
   393                                          \for_atom (Abs_Frac)", ts)
   393                                          \for_atom (Abs_Frac)", ts)
   394                     end
   394                     end
   395                   else if not for_auto andalso is_abs_fun thy constr_x then
   395                   else if not for_auto andalso is_abs_fun thy constr_x then
   396                     Const (abs_name, constr_T) $ the_single ts
   396                     Const (abs_name, constr_T) $ the_single ts
   397                   else
   397                   else
   419                     (batch_list (arity_of_rep R) js))
   419                     (batch_list (arity_of_rep R) js))
   420     (* (typ * int) list -> typ -> typ -> rep -> int list list -> term *)
   420     (* (typ * int) list -> typ -> typ -> rep -> int list list -> term *)
   421     and term_for_rep seen T T' Unit [[]] = term_for_atom seen T T' 0
   421     and term_for_rep seen T T' Unit [[]] = term_for_atom seen T T' 0
   422       | term_for_rep seen T T' (R as Atom (k, j0)) [[j]] =
   422       | term_for_rep seen T T' (R as Atom (k, j0)) [[j]] =
   423         if j >= j0 andalso j < j0 + k then term_for_atom seen T T' (j - j0)
   423         if j >= j0 andalso j < j0 + k then term_for_atom seen T T' (j - j0)
   424         else raise REP ("NitpickModel.reconstruct_term.term_for_rep", [R])
   424         else raise REP ("Nitpick_Model.reconstruct_term.term_for_rep", [R])
   425       | term_for_rep seen (Type ("*", [T1, T2])) _ (Struct [R1, R2]) [js] =
   425       | term_for_rep seen (Type ("*", [T1, T2])) _ (Struct [R1, R2]) [js] =
   426         let
   426         let
   427           val arity1 = arity_of_rep R1
   427           val arity1 = arity_of_rep R1
   428           val (js1, js2) = chop arity1 js
   428           val (js1, js2) = chop arity1 js
   429         in
   429         in
   452                          o AList.lookup (op =) grouped_jss2) jss1
   452                          o AList.lookup (op =) grouped_jss2) jss1
   453         in make_fun true T1 T2 T' ts1 ts2 end
   453         in make_fun true T1 T2 T' ts1 ts2 end
   454       | term_for_rep seen T T' (Opt R) jss =
   454       | term_for_rep seen T T' (Opt R) jss =
   455         if null jss then Const (unknown, T) else term_for_rep seen T T' R jss
   455         if null jss then Const (unknown, T) else term_for_rep seen T T' R jss
   456       | term_for_rep seen T _ R jss =
   456       | term_for_rep seen T _ R jss =
   457         raise ARG ("NitpickModel.reconstruct_term.term_for_rep",
   457         raise ARG ("Nitpick_Model.reconstruct_term.term_for_rep",
   458                    Refute.string_of_typ T ^ " " ^ string_for_rep R ^ " " ^
   458                    Refute.string_of_typ T ^ " " ^ string_for_rep R ^ " " ^
   459                    string_of_int (length jss))
   459                    string_of_int (length jss))
   460   in
   460   in
   461     (not for_auto ? setify_mapify_funs []) o unbox_term oooo term_for_rep []
   461     (not for_auto ? setify_mapify_funs []) o unbox_term oooo term_for_rep []
   462   end
   462   end
   574             end
   574             end
   575           | ConstName (s, T, _) =>
   575           | ConstName (s, T, _) =>
   576             (assign_operator_for_const (s, T),
   576             (assign_operator_for_const (s, T),
   577              user_friendly_const ext_ctxt (base_name, step_name) formats (s, T),
   577              user_friendly_const ext_ctxt (base_name, step_name) formats (s, T),
   578              T)
   578              T)
   579           | _ => raise NUT ("NitpickModel.reconstruct_hol_model.\
   579           | _ => raise NUT ("Nitpick_Model.reconstruct_hol_model.\
   580                             \pretty_for_assign", [name])
   580                             \pretty_for_assign", [name])
   581         val t2 = if rep_of name = Any then
   581         val t2 = if rep_of name = Any then
   582                    Const (@{const_name undefined}, T')
   582                    Const (@{const_name undefined}, T')
   583                  else
   583                  else
   584                    tuple_list_for_name rel_table bounds name
   584                    tuple_list_for_name rel_table bounds name
   599                 (if precise then [] else [Pretty.str unrep]))])
   599                 (if precise then [] else [Pretty.str unrep]))])
   600     (* typ -> dtype_spec list *)
   600     (* typ -> dtype_spec list *)
   601     fun integer_datatype T =
   601     fun integer_datatype T =
   602       [{typ = T, card = card_of_type card_assigns T, co = false,
   602       [{typ = T, card = card_of_type card_assigns T, co = false,
   603         precise = false, constrs = []}]
   603         precise = false, constrs = []}]
   604       handle TYPE ("NitpickHOL.card_of_type", _, _) => []
   604       handle TYPE ("Nitpick_HOL.card_of_type", _, _) => []
   605     val (codatatypes, datatypes) =
   605     val (codatatypes, datatypes) =
   606       List.partition #co datatypes
   606       List.partition #co datatypes
   607       ||> append (integer_datatype nat_T @ integer_datatype int_T)
   607       ||> append (integer_datatype nat_T @ integer_datatype int_T)
   608     val block_of_datatypes =
   608     val block_of_datatypes =
   609       if show_datatypes andalso not (null datatypes) then
   609       if show_datatypes andalso not (null datatypes) then
   635       map (fn x as (s, T) =>
   635       map (fn x as (s, T) =>
   636               case filter (equal x o nickname_of pairf (unbox_type o type_of))
   636               case filter (equal x o nickname_of pairf (unbox_type o type_of))
   637                           free_names of
   637                           free_names of
   638                 [name] => name
   638                 [name] => name
   639               | [] => FreeName (s, T, Any)
   639               | [] => FreeName (s, T, Any)
   640               | _ => raise TERM ("NitpickModel.reconstruct_hol_model",
   640               | _ => raise TERM ("Nitpick_Model.reconstruct_hol_model",
   641                                  [Const x])) all_frees
   641                                  [Const x])) all_frees
   642     val chunks = block_of_names true "Free variable" free_names @
   642     val chunks = block_of_names true "Free variable" free_names @
   643                  block_of_names show_skolems "Skolem constant" skolem_names @
   643                  block_of_names show_skolems "Skolem constant" skolem_names @
   644                  block_of_names true "Evaluated term" eval_names @
   644                  block_of_names true "Evaluated term" eval_names @
   645                  block_of_datatypes @ block_of_codatatypes @
   645                  block_of_datatypes @ block_of_codatatypes @