src/HOL/Statespace/distinct_tree_prover.ML
author wenzelm
Wed, 23 Jul 2025 14:53:21 +0200
changeset 82898 89da4dcd1fa8
parent 80709 e6f026505c5b
permissions -rw-r--r--
clarified colors, following d6a14ed060fb;
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
29269
5c25a2012975 moved term order operations to structure TermOrd (cf. Pure/term_ord.ML);
wenzelm
parents: 29064
diff changeset
     1
(*  Title:      HOL/Statespace/distinct_tree_prover.ML
74588
3cc363e8bfb2 cleanup; add Apple reference
Norbert Schirmer <nschirmer@apple.com>
parents: 74587
diff changeset
     2
    Author:     Norbert Schirmer, TU Muenchen, 2007
3cc363e8bfb2 cleanup; add Apple reference
Norbert Schirmer <nschirmer@apple.com>
parents: 74587
diff changeset
     3
    Author:     Norbert Schirmer, Apple, 2021
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
     4
*)
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
     5
25408
156f6f7082b8 added signatures;
schirmer
parents: 25171
diff changeset
     6
signature DISTINCT_TREE_PROVER =
156f6f7082b8 added signatures;
schirmer
parents: 25171
diff changeset
     7
sig
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
     8
  datatype direction = Left | Right
29302
eb782d1dc07c normalized some ML type/val aliases;
wenzelm
parents: 29269
diff changeset
     9
  val mk_tree : ('a -> term) -> typ -> 'a list -> term
eb782d1dc07c normalized some ML type/val aliases;
wenzelm
parents: 29269
diff changeset
    10
  val dest_tree : term -> term list
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    11
  val find_tree : term -> term -> direction list option
25408
156f6f7082b8 added signatures;
schirmer
parents: 25171
diff changeset
    12
74587
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
    13
  val in_set: Proof.context -> direction list -> cterm -> thm
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
    14
  val find_in_set: Proof.context -> term -> cterm -> thm
29302
eb782d1dc07c normalized some ML type/val aliases;
wenzelm
parents: 29269
diff changeset
    15
  val neq_to_eq_False : thm
60327
a3f565b8ba76 clarified context;
wenzelm
parents: 59621
diff changeset
    16
  val distinctTreeProver : Proof.context -> thm -> direction list -> direction list -> thm
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    17
  val neq_x_y : Proof.context -> term -> term -> string -> thm option
29302
eb782d1dc07c normalized some ML type/val aliases;
wenzelm
parents: 29269
diff changeset
    18
  val distinctFieldSolver : string list -> solver
42368
3b8498ac2314 proper subgoal addressing via SUBGOAL/CSUBGOAL -- assuming these tactics did not handle Subscript in any special way;
wenzelm
parents: 42361
diff changeset
    19
  val distinctTree_tac : string list -> Proof.context -> int -> tactic
60327
a3f565b8ba76 clarified context;
wenzelm
parents: 59621
diff changeset
    20
  val distinct_implProver : Proof.context -> thm -> cterm -> thm
a3f565b8ba76 clarified context;
wenzelm
parents: 59621
diff changeset
    21
  val subtractProver : Proof.context -> term -> cterm -> thm -> thm
29302
eb782d1dc07c normalized some ML type/val aliases;
wenzelm
parents: 29269
diff changeset
    22
  val distinct_simproc : string list -> simproc
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    23
60639
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
    24
  val discharge : Proof.context -> thm list -> thm -> thm
25408
156f6f7082b8 added signatures;
schirmer
parents: 25171
diff changeset
    25
end;
156f6f7082b8 added signatures;
schirmer
parents: 25171
diff changeset
    26
156f6f7082b8 added signatures;
schirmer
parents: 25171
diff changeset
    27
structure DistinctTreeProver : DISTINCT_TREE_PROVER =
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    28
struct
39159
0dec18004e75 more antiquotations;
wenzelm
parents: 38864
diff changeset
    29
45356
e79402612266 inlined antiquotations;
wenzelm
parents: 45355
diff changeset
    30
val neq_to_eq_False = @{thm neq_to_eq_False};
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    31
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    32
datatype direction = Left | Right;
25408
156f6f7082b8 added signatures;
schirmer
parents: 25171
diff changeset
    33
69597
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
    34
fun treeT T = Type (\<^type_name>\<open>tree\<close>, [T]);
45740
132a3e1c0fe5 more antiquotations;
wenzelm
parents: 45356
diff changeset
    35
69597
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
    36
fun mk_tree' e T n [] = Const (\<^const_name>\<open>Tip\<close>, treeT T)
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    37
  | mk_tree' e T n xs =
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    38
     let
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    39
       val m = (n - 1) div 2;
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    40
       val (xsl,x::xsr) = chop m xs;
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    41
       val l = mk_tree' e T m xsl;
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    42
       val r = mk_tree' e T (n-(m+1)) xsr;
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    43
     in
69597
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
    44
       Const (\<^const_name>\<open>Node\<close>, treeT T --> T --> HOLogic.boolT--> treeT T --> treeT T) $
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
    45
         l $ e x $ \<^term>\<open>False\<close> $ r
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    46
     end
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    47
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    48
fun mk_tree e T xs = mk_tree' e T (length xs) xs;
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    49
69597
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
    50
fun dest_tree (Const (\<^const_name>\<open>Tip\<close>, _)) = []
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
    51
  | dest_tree (Const (\<^const_name>\<open>Node\<close>, _) $ l $ e $ _ $ r) = dest_tree l @ e :: dest_tree r
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    52
  | dest_tree t = raise TERM ("dest_tree", [t]);
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    53
25408
156f6f7082b8 added signatures;
schirmer
parents: 25171
diff changeset
    54
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    55
69597
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
    56
fun lin_find_tree e (Const (\<^const_name>\<open>Tip\<close>, _)) = NONE
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
    57
  | lin_find_tree e (Const (\<^const_name>\<open>Node\<close>, _) $ l $ x $ _ $ r) =
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    58
      if e aconv x
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    59
      then SOME []
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    60
      else
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    61
        (case lin_find_tree e l of
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    62
          SOME path => SOME (Left :: path)
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    63
        | NONE =>
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    64
            (case lin_find_tree e r of
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    65
              SOME path => SOME (Right :: path)
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    66
            | NONE => NONE))
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    67
  | lin_find_tree e t = raise TERM ("find_tree: input not a tree", [t])
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    68
69597
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
    69
fun bin_find_tree order e (Const (\<^const_name>\<open>Tip\<close>, _)) = NONE
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
    70
  | bin_find_tree order e (Const (\<^const_name>\<open>Node\<close>, _) $ l $ x $ _ $ r) =
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    71
      (case order (e, x) of
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    72
        EQUAL => SOME []
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    73
      | LESS => Option.map (cons Left) (bin_find_tree order e l)
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    74
      | GREATER => Option.map (cons Right) (bin_find_tree order e r))
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    75
  | bin_find_tree order e t = raise TERM ("find_tree: input not a tree", [t])
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    76
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    77
fun find_tree e t =
35408
b48ab741683b modernized structure Term_Ord;
wenzelm
parents: 30289
diff changeset
    78
  (case bin_find_tree Term_Ord.fast_term_ord e t of
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    79
    NONE => lin_find_tree e t
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    80
  | x => x);
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    81
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    82
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    83
fun split_common_prefix xs [] = ([], xs, [])
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    84
  | split_common_prefix [] ys = ([], [], ys)
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    85
  | split_common_prefix (xs as (x :: xs')) (ys as (y :: ys')) =
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    86
      if x = y
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    87
      then let val (ps, xs'', ys'') = split_common_prefix xs' ys' in (x :: ps, xs'', ys'') end
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
    88
      else ([], xs, ys)
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    89
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    90
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    91
(* Wrapper around Thm.instantiate. The type instiations of instTs are applied to
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    92
 * the right hand sides of insts
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    93
 *)
60327
a3f565b8ba76 clarified context;
wenzelm
parents: 59621
diff changeset
    94
fun instantiate ctxt instTs insts =
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    95
  let
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 55972
diff changeset
    96
    val instTs' = map (fn (T, U) => (dest_TVar (Thm.typ_of T), Thm.typ_of U)) instTs;
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    97
    fun substT x = (case AList.lookup (op =) instTs' x of NONE => TVar x | SOME T' => T');
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
    98
    fun mapT_and_recertify ct =
60327
a3f565b8ba76 clarified context;
wenzelm
parents: 59621
diff changeset
    99
      (Thm.cterm_of ctxt (Term.map_types (Term.map_type_tvar substT) (Thm.term_of ct)));
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   100
    val insts' = map (apfst mapT_and_recertify) insts;
60642
48dd1cefb4ae simplified Thm.instantiate and derivatives: the LHS refers to non-certified variables -- this merely serves as index into already certified structures (or is ignored);
wenzelm
parents: 60639
diff changeset
   101
  in
48dd1cefb4ae simplified Thm.instantiate and derivatives: the LHS refers to non-certified variables -- this merely serves as index into already certified structures (or is ignored);
wenzelm
parents: 60639
diff changeset
   102
    Thm.instantiate
74282
c2ee8d993d6a clarified signature: more scalable operations;
wenzelm
parents: 69597
diff changeset
   103
     (TVars.make (map (apfst (dest_TVar o Thm.typ_of)) instTs),
c2ee8d993d6a clarified signature: more scalable operations;
wenzelm
parents: 69597
diff changeset
   104
      Vars.make (map (apfst (dest_Var o Thm.term_of)) insts'))
60642
48dd1cefb4ae simplified Thm.instantiate and derivatives: the LHS refers to non-certified variables -- this merely serves as index into already certified structures (or is ignored);
wenzelm
parents: 60639
diff changeset
   105
  end;
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   106
51701
1e29891759c4 tuned exceptions -- avoid composing error messages in low-level situations;
wenzelm
parents: 45740
diff changeset
   107
fun tvar_clash ixn S S' =
1e29891759c4 tuned exceptions -- avoid composing error messages in low-level situations;
wenzelm
parents: 45740
diff changeset
   108
  raise TYPE ("Type variable has two distinct sorts", [TVar (ixn, S), TVar (ixn, S')], []);
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   109
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   110
fun lookup (tye, (ixn, S)) =
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   111
  (case AList.lookup (op =) tye ixn of
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   112
    NONE => NONE
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   113
  | SOME (S', T) => if S = S' then SOME T else tvar_clash ixn S S');
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   114
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   115
val naive_typ_match =
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   116
  let
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   117
    fun match (TVar (v, S), T) subs =
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   118
          (case lookup (subs, (v, S)) of
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   119
            NONE => ((v, (S, T))::subs)
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   120
          | SOME _ => subs)
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   121
      | match (Type (a, Ts), Type (b, Us)) subs =
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   122
          if a <> b then raise Type.TYPE_MATCH
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   123
          else matches (Ts, Us) subs
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   124
      | match (TFree x, TFree y) subs =
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   125
          if x = y then subs else raise Type.TYPE_MATCH
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   126
      | match _ _ = raise Type.TYPE_MATCH
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   127
    and matches (T :: Ts, U :: Us) subs = matches (Ts, Us) (match (T, U) subs)
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   128
      | matches _ subs = subs;
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   129
  in match end;
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   130
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   131
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   132
(* expects that relevant type variables are already contained in
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   133
 * term variables. First instantiation of variables is returned without further
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   134
 * checking.
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   135
 *)
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   136
fun naive_cterm_first_order_match (t, ct) env =
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   137
  let
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   138
    fun mtch (env as (tyinsts, insts)) =
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   139
      fn (Var (ixn, T), ct) =>
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   140
          (case AList.lookup (op =) insts ixn of
59586
ddf6deaadfe8 clarified signature;
wenzelm
parents: 59582
diff changeset
   141
            NONE => (naive_typ_match (T, Thm.typ_of_cterm ct) tyinsts, (ixn, ct) :: insts)
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   142
          | SOME _ => env)
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   143
       | (f $ t, ct) =>
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   144
          let val (cf, ct') = Thm.dest_comb ct;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   145
          in mtch (mtch env (f, cf)) (t, ct') end
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   146
       | _ => env;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   147
  in mtch env (t, ct) end;
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   148
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   149
60639
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   150
fun discharge ctxt prems rule =
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   151
  let
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   152
    val (tyinsts,insts) =
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 55972
diff changeset
   153
      fold naive_cterm_first_order_match (Thm.prems_of rule ~~ map Thm.cprop_of prems) ([], []);
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   154
    val tyinsts' =
60642
48dd1cefb4ae simplified Thm.instantiate and derivatives: the LHS refers to non-certified variables -- this merely serves as index into already certified structures (or is ignored);
wenzelm
parents: 60639
diff changeset
   155
      map (fn (v, (S, U)) => ((v, S), Thm.ctyp_of ctxt U)) tyinsts;
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   156
    val insts' =
60642
48dd1cefb4ae simplified Thm.instantiate and derivatives: the LHS refers to non-certified variables -- this merely serves as index into already certified structures (or is ignored);
wenzelm
parents: 60639
diff changeset
   157
      map (fn (idxn, ct) => ((idxn, Thm.typ_of_cterm ct), ct)) insts;
74282
c2ee8d993d6a clarified signature: more scalable operations;
wenzelm
parents: 69597
diff changeset
   158
    val rule' = Thm.instantiate (TVars.make tyinsts', Vars.make insts') rule;
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   159
  in fold Thm.elim_implies prems rule' end;
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   160
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   161
local
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   162
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   163
val (l_in_set_root, x_in_set_root, r_in_set_root) =
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   164
  let
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   165
    val (Node_l_x_d, r) =
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 55972
diff changeset
   166
      Thm.cprop_of @{thm in_set_root}
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   167
      |> Thm.dest_comb |> #2
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   168
      |> Thm.dest_comb |> #2 |> Thm.dest_comb |> #2 |> Thm.dest_comb;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   169
    val (Node_l, x) = Node_l_x_d |> Thm.dest_comb |> #1 |> Thm.dest_comb;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   170
    val l = Node_l |> Thm.dest_comb |> #2;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   171
  in (l,x,r) end;
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   172
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   173
val (x_in_set_left, r_in_set_left) =
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   174
  let
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   175
    val (Node_l_x_d, r) =
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 55972
diff changeset
   176
      Thm.cprop_of @{thm in_set_left}
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   177
      |> Thm.dest_comb |> #2 |> Thm.dest_comb |> #2
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   178
      |> Thm.dest_comb |> #2 |> Thm.dest_comb |> #2 |> Thm.dest_comb;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   179
    val x = Node_l_x_d |> Thm.dest_comb |> #1 |> Thm.dest_comb |> #2;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   180
  in (x, r) end;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   181
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   182
val (x_in_set_right, l_in_set_right) =
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   183
  let
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   184
    val (Node_l, x) =
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 55972
diff changeset
   185
      Thm.cprop_of @{thm in_set_right}
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   186
      |> Thm.dest_comb |> #2 |> Thm.dest_comb |> #2
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   187
      |> Thm.dest_comb |> #2 |> Thm.dest_comb |> #2
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   188
      |> Thm.dest_comb |> #1 |> Thm.dest_comb |> #1
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   189
      |> Thm.dest_comb;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   190
    val l = Node_l |> Thm.dest_comb |> #2;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   191
  in (x, l) end;
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   192
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   193
in
74587
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   194
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   195
fun in_set ctxt ps tree =
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   196
  let
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   197
    val in_set = in_set ctxt
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   198
    val (_, [l, x, _, r]) = Drule.strip_comb tree;
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   199
    val xT = Thm.ctyp_of_cterm x;
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   200
  in
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   201
    (case ps of
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   202
      [] =>
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   203
        instantiate ctxt
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   204
          [(Thm.ctyp_of_cterm x_in_set_root, xT)]
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   205
          [(l_in_set_root, l), (x_in_set_root, x), (r_in_set_root, r)] @{thm in_set_root}
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   206
    | Left :: ps' =>
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   207
        let
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   208
          val in_set_l = in_set ps' l;
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   209
          val in_set_left' =
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   210
            instantiate ctxt
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   211
              [(Thm.ctyp_of_cterm x_in_set_left, xT)]
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   212
              [(x_in_set_left, x), (r_in_set_left, r)] @{thm in_set_left};
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   213
        in discharge ctxt [in_set_l] in_set_left' end
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   214
    | Right :: ps' =>
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   215
        let
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   216
          val in_set_r = in_set ps' r;
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   217
          val in_set_right' =
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   218
            instantiate ctxt
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   219
              [(Thm.ctyp_of_cterm x_in_set_right, xT)]
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   220
              [(x_in_set_right, x), (l_in_set_right, l)] @{thm in_set_right};
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   221
        in discharge ctxt [in_set_r] in_set_right' end)
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   222
  end;
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   223
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   224
fun find_in_set ctxt t ct =
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   225
  case find_tree t (Thm.term_of ct) of
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   226
    SOME ps => in_set ctxt ps ct
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   227
  | NONE => raise TERM ("find_in_set", [t, Thm.term_of ct])
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   228
 
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   229
(*
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   230
1. First get paths x_path y_path of x and y in the tree.
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   231
2. For the common prefix descend into the tree according to the path
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   232
   and lemmas all_distinct_left/right
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   233
3. If one restpath is empty use distinct_left/right,
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   234
   otherwise all_distinct_left_right
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   235
*)
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   236
60327
a3f565b8ba76 clarified context;
wenzelm
parents: 59621
diff changeset
   237
fun distinctTreeProver ctxt dist_thm x_path y_path =
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   238
  let
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   239
    fun dist_subtree [] thm = thm
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   240
      | dist_subtree (p :: ps) thm =
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   241
         let
45356
e79402612266 inlined antiquotations;
wenzelm
parents: 45355
diff changeset
   242
           val rule =
e79402612266 inlined antiquotations;
wenzelm
parents: 45355
diff changeset
   243
            (case p of Left => @{thm all_distinct_left} | Right => @{thm all_distinct_right})
60639
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   244
         in dist_subtree ps (discharge ctxt [thm] rule) end;
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   245
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   246
    val (ps, x_rest, y_rest) = split_common_prefix x_path y_path;
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   247
    val dist_subtree_thm = dist_subtree ps dist_thm;
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 55972
diff changeset
   248
    val subtree = Thm.cprop_of dist_subtree_thm |> Thm.dest_comb |> #2 |> Thm.dest_comb |> #2;
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   249
    val (_, [l, _, _, r]) = Drule.strip_comb subtree;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   250
74587
ebb0b15c66e1 refine interface
Norbert Schirmer <nschirmer@apple.com>
parents: 74282
diff changeset
   251
  val in_set = in_set ctxt
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   252
  fun in_set' [] = raise TERM ("distinctTreeProver", [])
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   253
    | in_set' (Left :: ps) = in_set ps l
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   254
    | in_set' (Right :: ps) = in_set ps r;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   255
60639
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   256
  fun distinct_lr node_in_set Left =
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   257
        discharge ctxt [dist_subtree_thm, node_in_set] @{thm distinct_left}
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   258
    | distinct_lr node_in_set Right =
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   259
        discharge ctxt [dist_subtree_thm, node_in_set] @{thm distinct_right}
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   260
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   261
  val (swap, neq) =
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   262
    (case x_rest of
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   263
      [] =>
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   264
        let val y_in_set = in_set' y_rest;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   265
        in (false, distinct_lr y_in_set (hd y_rest)) end
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   266
    | xr :: xrs =>
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   267
        (case y_rest of
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   268
          [] =>
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   269
            let val x_in_set = in_set' x_rest;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   270
            in (true, distinct_lr x_in_set (hd x_rest)) end
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   271
        | yr :: yrs =>
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   272
            let
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   273
              val x_in_set = in_set' x_rest;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   274
              val y_in_set = in_set' y_rest;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   275
            in
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   276
              (case xr of
45356
e79402612266 inlined antiquotations;
wenzelm
parents: 45355
diff changeset
   277
                Left =>
60639
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   278
                  (false,
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   279
                    discharge ctxt [dist_subtree_thm, x_in_set, y_in_set] @{thm distinct_left_right})
45356
e79402612266 inlined antiquotations;
wenzelm
parents: 45355
diff changeset
   280
              | Right =>
60639
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   281
                  (true,
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   282
                    discharge ctxt [dist_subtree_thm, y_in_set, x_in_set] @{thm distinct_left_right}))
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   283
           end));
60639
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   284
  in if swap then discharge ctxt [neq] @{thm swap_neq} else neq end;
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   285
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   286
60639
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   287
fun deleteProver _ dist_thm [] = @{thm delete_root} OF [dist_thm]
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   288
  | deleteProver ctxt dist_thm (p::ps) =
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   289
      let
45356
e79402612266 inlined antiquotations;
wenzelm
parents: 45355
diff changeset
   290
        val dist_rule =
e79402612266 inlined antiquotations;
wenzelm
parents: 45355
diff changeset
   291
          (case p of Left => @{thm all_distinct_left} | Right => @{thm all_distinct_right});
60639
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   292
        val dist_thm' = discharge ctxt [dist_thm] dist_rule;
45356
e79402612266 inlined antiquotations;
wenzelm
parents: 45355
diff changeset
   293
        val del_rule = (case p of Left => @{thm delete_left} | Right => @{thm delete_right});
60639
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   294
        val del = deleteProver ctxt dist_thm' ps;
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   295
      in discharge ctxt [dist_thm, del] del_rule end;
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   296
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   297
local
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   298
  val (alpha, v) =
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   299
    let
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   300
      val ct =
45356
e79402612266 inlined antiquotations;
wenzelm
parents: 45355
diff changeset
   301
        @{thm subtract_Tip} |> Thm.cprop_of |> Thm.dest_comb |> #2 |> Thm.dest_comb |> #2
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   302
        |> Thm.dest_comb |> #2;
59586
ddf6deaadfe8 clarified signature;
wenzelm
parents: 59582
diff changeset
   303
      val [alpha] = ct |> Thm.ctyp_of_cterm |> Thm.dest_ctyp;
60642
48dd1cefb4ae simplified Thm.instantiate and derivatives: the LHS refers to non-certified variables -- this merely serves as index into already certified structures (or is ignored);
wenzelm
parents: 60639
diff changeset
   304
    in (dest_TVar (Thm.typ_of alpha), #1 (dest_Var (Thm.term_of ct))) end;
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   305
in
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   306
69597
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
   307
fun subtractProver ctxt (Const (\<^const_name>\<open>Tip\<close>, T)) ct dist_thm =
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   308
      let
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   309
        val ct' = dist_thm |> Thm.cprop_of |> Thm.dest_comb |> #2 |> Thm.dest_comb |> #2;
80634
a90ab1ea6458 tuned: more explicit dest_Type_name and dest_Type_args;
wenzelm
parents: 78812
diff changeset
   310
        val [alphaI] = dest_Type_args T;
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   311
      in
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   312
        Thm.instantiate
77879
wenzelm
parents: 74588
diff changeset
   313
          (TVars.make1 (alpha, Thm.ctyp_of ctxt alphaI),
wenzelm
parents: 74588
diff changeset
   314
           Vars.make1 ((v, treeT alphaI), ct')) @{thm subtract_Tip}
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   315
      end
69597
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
   316
  | subtractProver ctxt (Const (\<^const_name>\<open>Node\<close>, nT) $ l $ x $ d $ r) ct dist_thm =
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   317
      let
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   318
        val ct' = dist_thm |> Thm.cprop_of |> Thm.dest_comb |> #2 |> Thm.dest_comb |> #2;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   319
        val (_, [cl, _, _, cr]) = Drule.strip_comb ct;
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 55972
diff changeset
   320
        val ps = the (find_tree x (Thm.term_of ct'));
60639
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   321
        val del_tree = deleteProver ctxt dist_thm ps;
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   322
        val dist_thm' = discharge ctxt [del_tree, dist_thm] @{thm delete_Some_all_distinct};
60327
a3f565b8ba76 clarified context;
wenzelm
parents: 59621
diff changeset
   323
        val sub_l = subtractProver ctxt (Thm.term_of cl) cl (dist_thm');
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   324
        val sub_r =
60327
a3f565b8ba76 clarified context;
wenzelm
parents: 59621
diff changeset
   325
          subtractProver ctxt (Thm.term_of cr) cr
60639
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   326
            (discharge ctxt [sub_l, dist_thm'] @{thm subtract_Some_all_distinct_res});
6686a410842a clarified context;
wenzelm
parents: 60327
diff changeset
   327
      in discharge ctxt [del_tree, sub_l, sub_r] @{thm subtract_Node} end;
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   328
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   329
end;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   330
60327
a3f565b8ba76 clarified context;
wenzelm
parents: 59621
diff changeset
   331
fun distinct_implProver ctxt dist_thm ct =
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   332
  let
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   333
    val ctree = ct |> Thm.dest_comb |> #2 |> Thm.dest_comb |> #2;
60327
a3f565b8ba76 clarified context;
wenzelm
parents: 59621
diff changeset
   334
    val sub = subtractProver ctxt (Thm.term_of ctree) ctree dist_thm;
45356
e79402612266 inlined antiquotations;
wenzelm
parents: 45355
diff changeset
   335
  in @{thm subtract_Some_all_distinct} OF [sub, dist_thm] end;
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   336
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   337
fun get_fst_success f [] = NONE
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   338
  | get_fst_success f (x :: xs) =
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   339
      (case f x of
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   340
        NONE => get_fst_success f xs
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   341
      | SOME v => SOME v);
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   342
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   343
fun neq_x_y ctxt x y name =
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   344
  (let
42361
23f352990944 modernized structure Proof_Context;
wenzelm
parents: 39159
diff changeset
   345
    val dist_thm = the (try (Proof_Context.get_thm ctxt) name);
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 55972
diff changeset
   346
    val ctree = Thm.cprop_of dist_thm |> Thm.dest_comb |> #2 |> Thm.dest_comb |> #2;
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 55972
diff changeset
   347
    val tree = Thm.term_of ctree;
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   348
    val x_path = the (find_tree x tree);
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   349
    val y_path = the (find_tree y tree);
60327
a3f565b8ba76 clarified context;
wenzelm
parents: 59621
diff changeset
   350
    val thm = distinctTreeProver ctxt dist_thm x_path y_path;
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   351
  in SOME thm
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   352
  end handle Option.Option => NONE);
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   353
42368
3b8498ac2314 proper subgoal addressing via SUBGOAL/CSUBGOAL -- assuming these tactics did not handle Subscript in any special way;
wenzelm
parents: 42361
diff changeset
   354
fun distinctTree_tac names ctxt = SUBGOAL (fn (goal, i) =>
3b8498ac2314 proper subgoal addressing via SUBGOAL/CSUBGOAL -- assuming these tactics did not handle Subscript in any special way;
wenzelm
parents: 42361
diff changeset
   355
    (case goal of
69597
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
   356
      Const (\<^const_name>\<open>Trueprop\<close>, _) $
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
   357
          (Const (\<^const_name>\<open>Not\<close>, _) $ (Const (\<^const_name>\<open>HOL.eq\<close>, _) $ x $ y)) =>
42368
3b8498ac2314 proper subgoal addressing via SUBGOAL/CSUBGOAL -- assuming these tactics did not handle Subscript in any special way;
wenzelm
parents: 42361
diff changeset
   358
        (case get_fst_success (neq_x_y ctxt x y) names of
60754
02924903a6fd prefer tactics with explicit context;
wenzelm
parents: 60642
diff changeset
   359
          SOME neq => resolve_tac ctxt [neq] i
42368
3b8498ac2314 proper subgoal addressing via SUBGOAL/CSUBGOAL -- assuming these tactics did not handle Subscript in any special way;
wenzelm
parents: 42361
diff changeset
   360
        | NONE => no_tac)
3b8498ac2314 proper subgoal addressing via SUBGOAL/CSUBGOAL -- assuming these tactics did not handle Subscript in any special way;
wenzelm
parents: 42361
diff changeset
   361
    | _ => no_tac))
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   362
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   363
fun distinctFieldSolver names =
51717
9e7d1c139569 simplifier uses proper Proof.context instead of historic type simpset;
wenzelm
parents: 51701
diff changeset
   364
  mk_solver "distinctFieldSolver" (distinctTree_tac names);
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   365
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   366
fun distinct_simproc names =
78812
d769a183d51d simprocs may be distinguished via 'identifier': only works for ML antiquotation (see also 13252110a6fe);
wenzelm
parents: 77879
diff changeset
   367
  Simplifier.make_simproc \<^context>
d769a183d51d simprocs may be distinguished via 'identifier': only works for ML antiquotation (see also 13252110a6fe);
wenzelm
parents: 77879
diff changeset
   368
   {name = "DistinctTreeProver.distinct_simproc",
80709
e6f026505c5b support for congprocs in the Simplifier, closely following Norbert Schirmer et-al, but with only one "simproc" name space and "simproc_setup" command / ML antiquotation;
wenzelm
parents: 80634
diff changeset
   369
    kind = Simproc,
78812
d769a183d51d simprocs may be distinguished via 'identifier': only works for ML antiquotation (see also 13252110a6fe);
wenzelm
parents: 77879
diff changeset
   370
    lhss = [\<^term>\<open>x = y\<close>],
61144
5e94dfead1c2 simplified simproc programming interfaces;
wenzelm
parents: 60754
diff changeset
   371
    proc = fn _ => fn ctxt => fn ct =>
5e94dfead1c2 simplified simproc programming interfaces;
wenzelm
parents: 60754
diff changeset
   372
      (case Thm.term_of ct of
69597
ff784d5a5bfb isabelle update -u control_cartouches;
wenzelm
parents: 62913
diff changeset
   373
        Const (\<^const_name>\<open>HOL.eq\<close>, _) $ x $ y =>
45356
e79402612266 inlined antiquotations;
wenzelm
parents: 45355
diff changeset
   374
          Option.map (fn neq => @{thm neq_to_eq_False} OF [neq])
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   375
            (get_fst_success (neq_x_y ctxt x y) names)
78812
d769a183d51d simprocs may be distinguished via 'identifier': only works for ML antiquotation (see also 13252110a6fe);
wenzelm
parents: 77879
diff changeset
   376
      | _ => NONE),
d769a183d51d simprocs may be distinguished via 'identifier': only works for ML antiquotation (see also 13252110a6fe);
wenzelm
parents: 77879
diff changeset
   377
    identifier = []};
25171
4a9c25bffc9b added Statespace library
schirmer
parents:
diff changeset
   378
45355
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   379
end;
c0704e988526 misc tuning and modernization;
wenzelm
parents: 43596
diff changeset
   380
62391
1658fc9b2618 more canonical names
nipkow
parents: 61144
diff changeset
   381
end;