src/Provers/Arith/cancel_sums.ML
author skalberg
Sun, 13 Feb 2005 17:15:14 +0100
changeset 15531 08c8dad8e399
parent 15027 d23887300b96
child 17613 072c21e31b42
permissions -rw-r--r--
Deleted Library.option type.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
4291
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
     1
(*  Title:      Provers/Arith/cancel_sums.ML
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
     2
    ID:         $Id$
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
     3
    Author:     Markus Wenzel and Stefan Berghofer, TU Muenchen
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
     4
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
     5
Cancel common summands of balanced expressions:
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
     6
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
     7
  A + x + B ~~ A' + x + B'  ==  A + B ~~ A' + B'
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
     8
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
     9
where + is AC0 and ~~ an appropriate balancing operation (e.g. =, <=, <, -).
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    10
*)
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    11
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    12
signature CANCEL_SUMS_DATA =
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    13
sig
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    14
  (*abstract syntax*)
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    15
  val mk_sum: term list -> term
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    16
  val dest_sum: term -> term list
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    17
  val mk_bal: term * term -> term
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    18
  val dest_bal: term -> term * term
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    19
  (*rules*)
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    20
  val prove_conv: tactic -> tactic -> Sign.sg -> term * term -> thm
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    21
  val norm_tac: tactic                   	(*AC0 etc.*)
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    22
  val uncancel_tac: cterm -> tactic      	(*apply A ~~ B  ==  x + A ~~ x + B*)
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    23
end;
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    24
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    25
signature CANCEL_SUMS =
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    26
sig
15027
d23887300b96 adapted type of simprocs;
wenzelm
parents: 4452
diff changeset
    27
  val proc: Sign.sg -> simpset -> term -> thm option
4291
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    28
end;
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    29
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    30
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    31
functor CancelSumsFun(Data: CANCEL_SUMS_DATA): CANCEL_SUMS =
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    32
struct
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    33
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    34
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    35
(* cancel *)
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    36
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    37
fun cons1 x (xs, y, z) = (x :: xs, y, z);
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    38
fun cons2 y (x, ys, z) = (x, y :: ys, z);
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    39
fun cons12 x y (xs, ys, z) = (x :: xs, y :: ys, z);
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    40
4346
15fab62268c3 adapted to new term order;
wenzelm
parents: 4291
diff changeset
    41
(*symmetric difference of multisets -- assumed to be sorted wrt. Logic.term_ord*)
4291
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    42
fun cancel ts [] vs = (ts, [], vs)
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    43
  | cancel [] us vs = ([], us, vs)
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    44
  | cancel (t :: ts) (u :: us) vs =
4452
b2ee34200dab adapted to new sort function;
wenzelm
parents: 4346
diff changeset
    45
      (case Term.term_ord (t, u) of
4346
15fab62268c3 adapted to new term order;
wenzelm
parents: 4291
diff changeset
    46
        EQUAL => cancel ts us (t :: vs)
4291
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    47
      | LESS => cons1 t (cancel ts (u :: us) vs)
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    48
      | GREATER => cons2 u (cancel (t :: ts) us vs));
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    49
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    50
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    51
(* uncancel *)
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    52
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    53
fun uncancel_sums_tac _ [] = all_tac
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    54
  | uncancel_sums_tac sg (t :: ts) =
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    55
      Data.uncancel_tac (Thm.cterm_of sg t) THEN
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    56
      uncancel_sums_tac sg ts;
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    57
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    58
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    59
(* the simplification procedure *)
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    60
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    61
fun proc sg _ t =
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    62
  (case try Data.dest_bal t of
15531
08c8dad8e399 Deleted Library.option type.
skalberg
parents: 15027
diff changeset
    63
    NONE => NONE
08c8dad8e399 Deleted Library.option type.
skalberg
parents: 15027
diff changeset
    64
  | SOME bal =>
4291
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    65
      let
4452
b2ee34200dab adapted to new sort function;
wenzelm
parents: 4346
diff changeset
    66
        val (ts, us) = pairself (sort Term.term_ord o Data.dest_sum) bal;
4291
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    67
        val (ts', us', vs) = cancel ts us [];
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    68
      in
15531
08c8dad8e399 Deleted Library.option type.
skalberg
parents: 15027
diff changeset
    69
        if null vs then NONE
08c8dad8e399 Deleted Library.option type.
skalberg
parents: 15027
diff changeset
    70
        else SOME
4291
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    71
          (Data.prove_conv (uncancel_sums_tac sg vs) Data.norm_tac sg
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    72
            (t, Data.mk_bal (Data.mk_sum ts', Data.mk_sum us')))
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    73
      end);
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    74
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    75
6e13b5427de0 Cancel common summands of balanced expressions.
wenzelm
parents:
diff changeset
    76
end;