68 |
68 |
69 (** Uncurrying **) |
69 (** Uncurrying **) |
70 |
70 |
71 fun add_to_uncurry_table ctxt t = |
71 fun add_to_uncurry_table ctxt t = |
72 let |
72 let |
73 val thy = Proof_Context.theory_of ctxt |
|
74 fun aux (t1 $ t2) args table = |
73 fun aux (t1 $ t2) args table = |
75 let val table = aux t2 [] table in aux t1 (t2 :: args) table end |
74 let val table = aux t2 [] table in aux t1 (t2 :: args) table end |
76 | aux (Abs (_, _, t')) _ table = aux t' [] table |
75 | aux (Abs (_, _, t')) _ table = aux t' [] table |
77 | aux (t as Const (x as (s, _))) args table = |
76 | aux (t as Const (x as (s, _))) args table = |
78 if is_built_in_const thy [(NONE, true)] x orelse |
77 if is_built_in_const x orelse is_constr_like ctxt x orelse |
79 is_constr_like ctxt x orelse |
|
80 is_sel s orelse s = @{const_name Sigma} then |
78 is_sel s orelse s = @{const_name Sigma} then |
81 table |
79 table |
82 else |
80 else |
83 Termtab.map_default (t, 65536) (Integer.min (length args)) table |
81 Termtab.map_default (t, 65536) (Integer.min (length args)) table |
84 | aux _ _ table = table |
82 | aux _ _ table = table |
124 | aux t args = s_betapplys [] (t, args) |
122 | aux t args = s_betapplys [] (t, args) |
125 in aux t [] end |
123 in aux t [] end |
126 |
124 |
127 (** Boxing **) |
125 (** Boxing **) |
128 |
126 |
129 fun box_fun_and_pair_in_term (hol_ctxt as {ctxt, thy, stds, ...}) def orig_t = |
127 fun box_fun_and_pair_in_term (hol_ctxt as {ctxt, ...}) def orig_t = |
130 let |
128 let |
131 fun box_relational_operator_type (Type (@{type_name fun}, Ts)) = |
129 fun box_relational_operator_type (Type (@{type_name fun}, Ts)) = |
132 Type (@{type_name fun}, map box_relational_operator_type Ts) |
130 Type (@{type_name fun}, map box_relational_operator_type Ts) |
133 | box_relational_operator_type (Type (@{type_name prod}, Ts)) = |
131 | box_relational_operator_type (Type (@{type_name prod}, Ts)) = |
134 Type (@{type_name prod}, map (box_type hol_ctxt InPair) Ts) |
132 Type (@{type_name prod}, map (box_type hol_ctxt InPair) Ts) |
227 box_relational_operator_type T |
225 box_relational_operator_type T |
228 else if String.isPrefix quot_normal_prefix s then |
226 else if String.isPrefix quot_normal_prefix s then |
229 let val T' = box_type hol_ctxt InFunLHS (domain_type T) in |
227 let val T' = box_type hol_ctxt InFunLHS (domain_type T) in |
230 T' --> T' |
228 T' --> T' |
231 end |
229 end |
232 else if is_built_in_const thy stds x orelse |
230 else if is_built_in_const x orelse |
233 s = @{const_name Sigma} then |
231 s = @{const_name Sigma} then |
234 T |
232 T |
235 else if is_constr_like ctxt x then |
233 else if is_constr_like ctxt x then |
236 box_type hol_ctxt InConstr T |
234 box_type hol_ctxt InConstr T |
237 else if is_sel s orelse is_rep_fun ctxt x then |
235 else if is_sel s orelse is_rep_fun ctxt x then |
249 val t2 = coerce_term hol_ctxt new_Ts (hd Ts1) T2 t2 |
247 val t2 = coerce_term hol_ctxt new_Ts (hd Ts1) T2 t2 |
250 in |
248 in |
251 s_betapply new_Ts (if s1 = @{type_name fun} then |
249 s_betapply new_Ts (if s1 = @{type_name fun} then |
252 t1 |
250 t1 |
253 else |
251 else |
254 select_nth_constr_arg ctxt stds |
252 select_nth_constr_arg ctxt |
255 (@{const_name FunBox}, |
253 (@{const_name FunBox}, |
256 Type (@{type_name fun}, Ts1) --> T1) t1 0 |
254 Type (@{type_name fun}, Ts1) --> T1) t1 0 |
257 (Type (@{type_name fun}, Ts1)), t2) |
255 (Type (@{type_name fun}, Ts1)), t2) |
258 end |
256 end |
259 | t1 $ t2 => |
257 | t1 $ t2 => |
266 val t2 = coerce_term hol_ctxt new_Ts (hd Ts1) T2 t2 |
264 val t2 = coerce_term hol_ctxt new_Ts (hd Ts1) T2 t2 |
267 in |
265 in |
268 s_betapply new_Ts (if s1 = @{type_name fun} then |
266 s_betapply new_Ts (if s1 = @{type_name fun} then |
269 t1 |
267 t1 |
270 else |
268 else |
271 select_nth_constr_arg ctxt stds |
269 select_nth_constr_arg ctxt |
272 (@{const_name FunBox}, |
270 (@{const_name FunBox}, |
273 Type (@{type_name fun}, Ts1) --> T1) t1 0 |
271 Type (@{type_name fun}, Ts1) --> T1) t1 0 |
274 (Type (@{type_name fun}, Ts1)), t2) |
272 (Type (@{type_name fun}, Ts1)), t2) |
275 end |
273 end |
276 | Free (s, T) => Free (s, box_type hol_ctxt InExpr T) |
274 | Free (s, T) => Free (s, box_type hol_ctxt InExpr T) |
304 fun aux [] = false |
302 fun aux [] = false |
305 | aux [T] = is_fun_or_set_type T orelse is_pair_type T |
303 | aux [T] = is_fun_or_set_type T orelse is_pair_type T |
306 | aux _ = true |
304 | aux _ = true |
307 in aux (map snd (Term.add_vars t []) @ map (nth Ts) (loose_bnos t)) end |
305 in aux (map snd (Term.add_vars t []) @ map (nth Ts) (loose_bnos t)) end |
308 |
306 |
309 fun pull_out_constr_comb ({ctxt, stds, ...} : hol_context) Ts relax k level t |
307 fun pull_out_constr_comb ({ctxt, ...} : hol_context) Ts relax k level t args |
310 args seen = |
308 seen = |
311 let val t_comb = list_comb (t, args) in |
309 let val t_comb = list_comb (t, args) in |
312 case t of |
310 case t of |
313 Const x => |
311 Const x => |
314 if not relax andalso is_constr ctxt stds x andalso |
312 if not relax andalso is_constr ctxt x andalso |
315 not (is_fun_or_set_type (fastype_of1 (Ts, t_comb))) andalso |
313 not (is_fun_or_set_type (fastype_of1 (Ts, t_comb))) andalso |
316 has_heavy_bounds_or_vars Ts t_comb andalso |
314 has_heavy_bounds_or_vars Ts t_comb andalso |
317 not (loose_bvar (t_comb, level)) then |
315 not (loose_bvar (t_comb, level)) then |
318 let |
316 let |
319 val (j, seen) = case find_index (curry (op =) t_comb) seen of |
317 val (j, seen) = case find_index (curry (op =) t_comb) seen of |
396 pull_out_constr_comb hol_ctxt Ts false k num_exists t args seen |
394 pull_out_constr_comb hol_ctxt Ts false k num_exists t args seen |
397 else |
395 else |
398 (list_comb (t, args), seen) |
396 (list_comb (t, args), seen) |
399 in aux [] 0 t [] [] |> fst end |
397 in aux [] 0 t [] [] |> fst end |
400 |
398 |
401 fun destroy_pulled_out_constrs (hol_ctxt as {ctxt, stds, ...}) axiom strong t = |
399 fun destroy_pulled_out_constrs (hol_ctxt as {ctxt, ...}) axiom strong t = |
402 let |
400 let |
403 val num_occs_of_var = |
401 val num_occs_of_var = |
404 fold_aterms (fn Var z => (fn f => fn z' => f z' |> z = z' ? Integer.add 1) |
402 fold_aterms (fn Var z => (fn f => fn z' => f z' |> z = z' ? Integer.add 1) |
405 | _ => I) t (K 0) |
403 | _ => I) t (K 0) |
406 fun aux Ts careful ((t0 as Const (@{const_name "=="}, _)) $ t1 $ t2) = |
404 fun aux Ts careful ((t0 as Const (@{const_name "=="}, _)) $ t1 $ t2) = |
432 let |
430 let |
433 val (arg_Ts, dataT) = strip_type T |
431 val (arg_Ts, dataT) = strip_type T |
434 val n = length arg_Ts |
432 val n = length arg_Ts |
435 in |
433 in |
436 if length args = n andalso |
434 if length args = n andalso |
437 (is_constr ctxt stds x orelse s = @{const_name Pair} orelse |
435 (is_constr ctxt x orelse s = @{const_name Pair} orelse |
438 x = (@{const_name Suc}, nat_T --> nat_T)) andalso |
436 x = (@{const_name Suc}, nat_T --> nat_T)) andalso |
439 (not careful orelse not (is_Var t1) orelse |
437 (not careful orelse not (is_Var t1) orelse |
440 String.isPrefix val_var_prefix (fst (fst (dest_Var t1)))) then |
438 String.isPrefix val_var_prefix (fst (fst (dest_Var t1)))) then |
441 s_let Ts "l" (n + 1) dataT bool_T |
439 s_let Ts "l" (n + 1) dataT bool_T |
442 (fn t1 => |
440 (fn t1 => |
449 | _ => raise SAME ()) |
447 | _ => raise SAME ()) |
450 |> body_type (type_of t0) = prop_T ? HOLogic.mk_Trueprop) |
448 |> body_type (type_of t0) = prop_T ? HOLogic.mk_Trueprop) |
451 handle SAME () => if pass1 then aux_eq Ts careful false t0 t2 t1 |
449 handle SAME () => if pass1 then aux_eq Ts careful false t0 t2 t1 |
452 else t0 $ aux Ts false t2 $ aux Ts false t1 |
450 else t0 $ aux Ts false t2 $ aux Ts false t1 |
453 and sel_eq Ts x t n nth_T nth_t = |
451 and sel_eq Ts x t n nth_T nth_t = |
454 HOLogic.eq_const nth_T $ nth_t |
452 HOLogic.eq_const nth_T $ nth_t $ select_nth_constr_arg ctxt x t n nth_T |
455 $ select_nth_constr_arg ctxt stds x t n nth_T |
|
456 |> aux Ts false |
453 |> aux Ts false |
457 in aux [] axiom t end |
454 in aux [] axiom t end |
458 |
455 |
459 (** Destruction of universal and existential equalities **) |
456 (** Destruction of universal and existential equalities **) |
460 |
457 |
485 aux prems zs (subst_free [(Var z, t')] t2) |
482 aux prems zs (subst_free [(Var z, t')] t2) |
486 else |
483 else |
487 aux (t1 :: prems) (Term.add_vars t1 zs) t2 |
484 aux (t1 :: prems) (Term.add_vars t1 zs) t2 |
488 in aux [] [] end |
485 in aux [] [] end |
489 |
486 |
490 fun find_bound_assign ctxt stds j = |
487 fun find_bound_assign ctxt j = |
491 let |
488 let |
492 fun do_term _ [] = NONE |
489 fun do_term _ [] = NONE |
493 | do_term seen (t :: ts) = |
490 | do_term seen (t :: ts) = |
494 let |
491 let |
495 fun do_eq pass1 t1 t2 = |
492 fun do_eq pass1 t1 t2 = |
498 else case t1 of |
495 else case t1 of |
499 Bound j' => if j' = j then SOME (t2, ts @ seen) else raise SAME () |
496 Bound j' => if j' = j then SOME (t2, ts @ seen) else raise SAME () |
500 | Const (s, Type (@{type_name fun}, [T1, T2])) $ Bound j' => |
497 | Const (s, Type (@{type_name fun}, [T1, T2])) $ Bound j' => |
501 if j' = j andalso |
498 if j' = j andalso |
502 s = nth_sel_name_for_constr_name @{const_name FunBox} 0 then |
499 s = nth_sel_name_for_constr_name @{const_name FunBox} 0 then |
503 SOME (construct_value ctxt stds |
500 SOME (construct_value ctxt |
504 (@{const_name FunBox}, T2 --> T1) [t2], |
501 (@{const_name FunBox}, T2 --> T1) [t2], |
505 ts @ seen) |
502 ts @ seen) |
506 else |
503 else |
507 raise SAME () |
504 raise SAME () |
508 | _ => raise SAME ()) |
505 | _ => raise SAME ()) |
525 (aux (f, lev) $ (aux (t, lev) handle SAME () => t) |
522 (aux (f, lev) $ (aux (t, lev) handle SAME () => t) |
526 handle SAME () => f $ aux (t, lev)) |
523 handle SAME () => f $ aux (t, lev)) |
527 | aux _ = raise SAME () |
524 | aux _ = raise SAME () |
528 in aux (t, j) handle SAME () => t end |
525 in aux (t, j) handle SAME () => t end |
529 |
526 |
530 fun destroy_existential_equalities ({ctxt, stds, ...} : hol_context) = |
527 fun destroy_existential_equalities ({ctxt, ...} : hol_context) = |
531 let |
528 let |
532 fun kill [] [] ts = foldr1 s_conj ts |
529 fun kill [] [] ts = foldr1 s_conj ts |
533 | kill (s :: ss) (T :: Ts) ts = |
530 | kill (s :: ss) (T :: Ts) ts = |
534 (case find_bound_assign ctxt stds (length ss) [] ts of |
531 (case find_bound_assign ctxt (length ss) [] ts of |
535 SOME (_, []) => @{const True} |
532 SOME (_, []) => @{const True} |
536 | SOME (arg_t, ts) => |
533 | SOME (arg_t, ts) => |
537 kill ss Ts (map (subst_one_bound (length ss) |
534 kill ss Ts (map (subst_one_bound (length ss) |
538 (incr_bv (~1, length ss + 1, arg_t))) ts) |
535 (incr_bv (~1, length ss + 1, arg_t))) ts) |
539 | NONE => |
536 | NONE => |
729 fun special_fun_aconv ((x1, js1, ts1), (x2, js2, ts2)) = |
726 fun special_fun_aconv ((x1, js1, ts1), (x2, js2, ts2)) = |
730 x1 = x2 andalso js1 = js2 andalso length ts1 = length ts2 andalso |
727 x1 = x2 andalso js1 = js2 andalso length ts1 = length ts2 andalso |
731 forall (op aconv) (ts1 ~~ ts2) |
728 forall (op aconv) (ts1 ~~ ts2) |
732 |
729 |
733 fun specialize_consts_in_term |
730 fun specialize_consts_in_term |
734 (hol_ctxt as {ctxt, thy, stds, specialize, def_tables, simp_table, |
731 (hol_ctxt as {ctxt, thy, specialize, def_tables, simp_table, |
735 special_funs, ...}) def depth t = |
732 special_funs, ...}) def depth t = |
736 if not specialize orelse depth > special_max_depth then |
733 if not specialize orelse depth > special_max_depth then |
737 t |
734 t |
738 else |
735 else |
739 let |
736 let |
740 val blacklist = |
737 val blacklist = |
741 if def then case term_under_def t of Const x => [x] | _ => [] else [] |
738 if def then case term_under_def t of Const x => [x] | _ => [] else [] |
742 fun aux args Ts (Const (x as (s, T))) = |
739 fun aux args Ts (Const (x as (s, T))) = |
743 ((if not (member (op =) blacklist x) andalso not (null args) andalso |
740 ((if not (member (op =) blacklist x) andalso not (null args) andalso |
744 not (String.isPrefix special_prefix s) andalso |
741 not (String.isPrefix special_prefix s) andalso |
745 not (is_built_in_const thy stds x) andalso |
742 not (is_built_in_const x) andalso |
746 (is_equational_fun_but_no_plain_def hol_ctxt x orelse |
743 (is_equational_fun_but_no_plain_def hol_ctxt x orelse |
747 (is_some (def_of_const thy def_tables x) andalso |
744 (is_some (def_of_const thy def_tables x) andalso |
748 not (is_of_class_const thy x) andalso |
745 not (is_of_class_const thy x) andalso |
749 not (is_constr ctxt stds x) andalso |
746 not (is_constr ctxt x) andalso |
750 not (is_choice_spec_fun hol_ctxt x))) then |
747 not (is_choice_spec_fun hol_ctxt x))) then |
751 let |
748 let |
752 val eligible_args = |
749 val eligible_args = |
753 filter (is_special_eligible_arg true Ts o snd) |
750 filter (is_special_eligible_arg true Ts o snd) |
754 (index_seq 0 (length args) ~~ args) |
751 (index_seq 0 (length args) ~~ args) |
893 |
890 |
894 (* Prevents divergence in case of cyclic or infinite axiom dependencies. *) |
891 (* Prevents divergence in case of cyclic or infinite axiom dependencies. *) |
895 val axioms_max_depth = 255 |
892 val axioms_max_depth = 255 |
896 |
893 |
897 fun axioms_for_term |
894 fun axioms_for_term |
898 (hol_ctxt as {thy, ctxt, max_bisim_depth, stds, user_axioms, |
895 (hol_ctxt as {thy, ctxt, max_bisim_depth, user_axioms, evals, |
899 evals, def_tables, nondef_table, choice_spec_table, |
896 def_tables, nondef_table, choice_spec_table, nondefs, |
900 nondefs, ...}) assm_ts neg_t = |
897 ...}) assm_ts neg_t = |
901 let |
898 let |
902 val (def_assm_ts, nondef_assm_ts) = |
899 val (def_assm_ts, nondef_assm_ts) = |
903 List.partition (assumption_exclusively_defines_free assm_ts) assm_ts |
900 List.partition (assumption_exclusively_defines_free assm_ts) assm_ts |
904 val def_assm_table = map (`(the o defined_free_by_assumption)) def_assm_ts |
901 val def_assm_table = map (`(the o defined_free_by_assumption)) def_assm_ts |
905 type accumulator = styp list * (term list * term list) |
902 type accumulator = styp list * (term list * term list) |
926 else add_nondef_axiom) depth t |
923 else add_nondef_axiom) depth t |
927 and add_axioms_for_term depth t (accum as (seen, axs)) = |
924 and add_axioms_for_term depth t (accum as (seen, axs)) = |
928 case t of |
925 case t of |
929 t1 $ t2 => accum |> fold (add_axioms_for_term depth) [t1, t2] |
926 t1 $ t2 => accum |> fold (add_axioms_for_term depth) [t1, t2] |
930 | Const (x as (s, T)) => |
927 | Const (x as (s, T)) => |
931 (if member (op aconv) seen t orelse is_built_in_const thy stds x then |
928 (if member (op aconv) seen t orelse is_built_in_const x then |
932 accum |
929 accum |
933 else |
930 else |
934 let val accum = (t :: seen, axs) in |
931 let val accum = (t :: seen, axs) in |
935 if depth > axioms_max_depth then |
932 if depth > axioms_max_depth then |
936 raise TOO_LARGE ("Nitpick_Preproc.axioms_for_term.\ |
933 raise TOO_LARGE ("Nitpick_Preproc.axioms_for_term.\ |
947 (get_class_def thy class) |
944 (get_class_def thy class) |
948 in |
945 in |
949 fold (add_maybe_def_axiom depth) (map_filter I [ax1, ax2]) |
946 fold (add_maybe_def_axiom depth) (map_filter I [ax1, ax2]) |
950 accum |
947 accum |
951 end |
948 end |
952 else if is_constr ctxt stds x then |
949 else if is_constr ctxt x then |
953 accum |
950 accum |
954 else if is_descr (original_name s) then |
951 else if is_descr (original_name s) then |
955 fold (add_nondef_axiom depth) (equational_fun_axioms hol_ctxt x) |
952 fold (add_nondef_axiom depth) (equational_fun_axioms hol_ctxt x) |
956 accum |
953 accum |
957 else if is_equational_fun_but_no_plain_def hol_ctxt x then |
954 else if is_equational_fun_but_no_plain_def hol_ctxt x then |
1015 | Type (z as (_, Ts)) => |
1012 | Type (z as (_, Ts)) => |
1016 fold (add_axioms_for_type depth) Ts |
1013 fold (add_axioms_for_type depth) Ts |
1017 #> (if is_pure_typedef ctxt T then |
1014 #> (if is_pure_typedef ctxt T then |
1018 fold (add_maybe_def_axiom depth) (optimized_typedef_axioms ctxt z) |
1015 fold (add_maybe_def_axiom depth) (optimized_typedef_axioms ctxt z) |
1019 else if is_quot_type ctxt T then |
1016 else if is_quot_type ctxt T then |
1020 fold (add_def_axiom depth) |
1017 fold (add_def_axiom depth) (optimized_quot_type_axioms ctxt z) |
1021 (optimized_quot_type_axioms ctxt stds z) |
|
1022 else if max_bisim_depth >= 0 andalso is_codatatype ctxt T then |
1018 else if max_bisim_depth >= 0 andalso is_codatatype ctxt T then |
1023 fold (add_maybe_def_axiom depth) |
1019 fold (add_maybe_def_axiom depth) |
1024 (codatatype_bisim_axioms hol_ctxt T) |
1020 (codatatype_bisim_axioms hol_ctxt T) |
1025 else |
1021 else |
1026 I) |
1022 I) |
1251 (** Preprocessor entry point **) |
1247 (** Preprocessor entry point **) |
1252 |
1248 |
1253 val max_skolem_depth = 3 |
1249 val max_skolem_depth = 3 |
1254 |
1250 |
1255 fun preprocess_formulas |
1251 fun preprocess_formulas |
1256 (hol_ctxt as {thy, ctxt, stds, binary_ints, destroy_constrs, boxes, |
1252 (hol_ctxt as {ctxt, binary_ints, destroy_constrs, boxes, needs, ...}) |
1257 needs, ...}) assm_ts neg_t = |
1253 assm_ts neg_t = |
1258 let |
1254 let |
1259 val (nondef_ts, def_ts, got_all_mono_user_axioms, no_poly_user_axioms) = |
1255 val (nondef_ts, def_ts, got_all_mono_user_axioms, no_poly_user_axioms) = |
1260 neg_t |> unfold_defs_in_term hol_ctxt |
1256 neg_t |> unfold_defs_in_term hol_ctxt |
1261 |> close_form |
1257 |> close_form |
1262 |> skolemize_term_and_more hol_ctxt max_skolem_depth |
1258 |> skolemize_term_and_more hol_ctxt max_skolem_depth |
1263 |> specialize_consts_in_term hol_ctxt false 0 |
1259 |> specialize_consts_in_term hol_ctxt false 0 |
1264 |> axioms_for_term hol_ctxt assm_ts |
1260 |> axioms_for_term hol_ctxt assm_ts |
1265 val binarize = |
1261 val binarize = |
1266 is_standard_datatype thy stds nat_T andalso |
|
1267 case binary_ints of |
1262 case binary_ints of |
1268 SOME false => false |
1263 SOME false => false |
1269 | _ => forall (may_use_binary_ints false) nondef_ts andalso |
1264 | _ => forall (may_use_binary_ints false) nondef_ts andalso |
1270 forall (may_use_binary_ints true) def_ts andalso |
1265 forall (may_use_binary_ints true) def_ts andalso |
1271 (binary_ints = SOME true orelse |
1266 (binary_ints = SOME true orelse |