src/CTT/CTT.ML
author wenzelm
Fri Dec 19 10:13:47 1997 +0100 (1997-12-19)
changeset 4440 9ed4098074bc
parent 3929 3553fcfa2c7e
child 9249 c71db8c28727
permissions -rw-r--r--
adapted to new sort function;
clasohm@1459
     1
(*  Title:      CTT/ctt.ML
clasohm@0
     2
    ID:         $Id$
clasohm@1459
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
clasohm@0
     4
    Copyright   1991  University of Cambridge
clasohm@0
     5
clasohm@0
     6
Tactics and lemmas for ctt.thy (Constructive Type Theory)
clasohm@0
     7
*)
clasohm@0
     8
clasohm@0
     9
open CTT;
clasohm@0
    10
clasohm@0
    11
(*Formation rules*)
clasohm@0
    12
val form_rls = [NF, ProdF, SumF, PlusF, EqF, FF, TF]
clasohm@0
    13
and formL_rls = [ProdFL, SumFL, PlusFL, EqFL];
clasohm@0
    14
clasohm@0
    15
 
clasohm@0
    16
(*Introduction rules
clasohm@0
    17
  OMITTED: EqI, because its premise is an eqelem, not an elem*)
clasohm@0
    18
val intr_rls = [NI0, NI_succ, ProdI, SumI, PlusI_inl, PlusI_inr, TI]
clasohm@0
    19
and intrL_rls = [NI_succL, ProdIL, SumIL, PlusI_inlL, PlusI_inrL];
clasohm@0
    20
clasohm@0
    21
clasohm@0
    22
(*Elimination rules
clasohm@0
    23
  OMITTED: EqE, because its conclusion is an eqelem,  not an elem
clasohm@0
    24
           TE, because it does not involve a constructor *)
clasohm@0
    25
val elim_rls = [NE, ProdE, SumE, PlusE, FE]
clasohm@0
    26
and elimL_rls = [NEL, ProdEL, SumEL, PlusEL, FEL];
clasohm@0
    27
clasohm@0
    28
(*OMITTED: eqC are TC because they make rewriting loop: p = un = un = ... *)
clasohm@0
    29
val comp_rls = [NC0, NC_succ, ProdC, SumC, PlusC_inl, PlusC_inr];
clasohm@0
    30
clasohm@0
    31
(*rules with conclusion a:A, an elem judgement*)
clasohm@0
    32
val element_rls = intr_rls @ elim_rls;
clasohm@0
    33
clasohm@0
    34
(*Definitions are (meta)equality axioms*)
clasohm@0
    35
val basic_defs = [fst_def,snd_def];
clasohm@0
    36
clasohm@0
    37
(*Compare with standard version: B is applied to UNSIMPLIFIED expression! *)
clasohm@1294
    38
qed_goal "SumIL2" CTT.thy
clasohm@0
    39
    "[| c=a : A;  d=b : B(a) |] ==> <c,d> = <a,b> : Sum(A,B)"
clasohm@0
    40
 (fn prems=>
clasohm@1459
    41
  [ (rtac sym_elem 1),
clasohm@1459
    42
    (rtac SumIL 1),
clasohm@1459
    43
    (ALLGOALS (rtac sym_elem )),
clasohm@0
    44
    (ALLGOALS (resolve_tac prems)) ]);
clasohm@0
    45
clasohm@0
    46
val intrL2_rls = [NI_succL, ProdIL, SumIL2, PlusI_inlL, PlusI_inrL];
clasohm@0
    47
clasohm@0
    48
(*Exploit p:Prod(A,B) to create the assumption z:B(a).  
clasohm@0
    49
  A more natural form of product elimination. *)
clasohm@1294
    50
qed_goal "subst_prodE" CTT.thy
clasohm@0
    51
    "[| p: Prod(A,B);  a: A;  !!z. z: B(a) ==> c(z): C(z) \
clasohm@0
    52
\    |] ==> c(p`a): C(p`a)"
clasohm@0
    53
 (fn prems=>
clasohm@0
    54
  [ (REPEAT (resolve_tac (prems@[ProdE]) 1)) ]);
clasohm@0
    55
clasohm@0
    56
(** Tactics for type checking **)
clasohm@0
    57
wenzelm@3929
    58
fun is_rigid_elem (Const("CTT.Elem",_) $ a $ _) = not (is_Var (head_of a))
clasohm@0
    59
  | is_rigid_elem _ = false;
clasohm@0
    60
clasohm@0
    61
(*Try solving a:A by assumption provided a is rigid!*) 
clasohm@0
    62
val test_assume_tac = SUBGOAL(fn (prem,i) =>
clasohm@0
    63
    if is_rigid_elem (Logic.strip_assums_concl prem)
clasohm@0
    64
    then  assume_tac i  else  no_tac);
clasohm@0
    65
clasohm@0
    66
fun ASSUME tf i = test_assume_tac i  ORELSE  tf i;
clasohm@0
    67
clasohm@0
    68
clasohm@0
    69
(*For simplification: type formation and checking,
clasohm@0
    70
  but no equalities between terms*)
clasohm@0
    71
val routine_rls = form_rls @ formL_rls @ [refl_type] @ element_rls;
clasohm@0
    72
clasohm@0
    73
fun routine_tac rls prems = ASSUME (filt_resolve_tac (prems @ rls) 4);
clasohm@0
    74
clasohm@0
    75
clasohm@0
    76
(*Solve all subgoals "A type" using formation rules. *)
clasohm@0
    77
val form_tac = REPEAT_FIRST (filt_resolve_tac(form_rls) 1);
clasohm@0
    78
clasohm@0
    79
clasohm@0
    80
(*Type checking: solve a:A (a rigid, A flexible) by intro and elim rules. *)
clasohm@0
    81
fun typechk_tac thms =
clasohm@0
    82
  let val tac = filt_resolve_tac (thms @ form_rls @ element_rls) 3
clasohm@0
    83
  in  REPEAT_FIRST (ASSUME tac)  end;
clasohm@0
    84
clasohm@0
    85
clasohm@0
    86
(*Solve a:A (a flexible, A rigid) by introduction rules. 
clasohm@0
    87
  Cannot use stringtrees (filt_resolve_tac) since
clasohm@0
    88
  goals like ?a:SUM(A,B) have a trivial head-string *)
clasohm@0
    89
fun intr_tac thms =
clasohm@0
    90
  let val tac = filt_resolve_tac(thms@form_rls@intr_rls) 1
clasohm@0
    91
  in  REPEAT_FIRST (ASSUME tac)  end;
clasohm@0
    92
clasohm@0
    93
clasohm@0
    94
(*Equality proving: solve a=b:A (where a is rigid) by long rules. *)
clasohm@0
    95
fun equal_tac thms =
clasohm@0
    96
  let val rls = thms @ form_rls @ element_rls @ intrL_rls @
clasohm@0
    97
                elimL_rls @ [refl_elem]
clasohm@0
    98
  in  REPEAT_FIRST (ASSUME (filt_resolve_tac rls 3))  end;
clasohm@0
    99
clasohm@0
   100
(*** Simplification ***)
clasohm@0
   101
clasohm@0
   102
(*To simplify the type in a goal*)
clasohm@1294
   103
qed_goal "replace_type" CTT.thy
clasohm@0
   104
    "[| B = A;  a : A |] ==> a : B"
clasohm@0
   105
 (fn prems=>
clasohm@1459
   106
  [ (rtac equal_types 1),
clasohm@1459
   107
    (rtac sym_type 2),
clasohm@0
   108
    (ALLGOALS (resolve_tac prems)) ]);
clasohm@0
   109
clasohm@0
   110
(*Simplify the parameter of a unary type operator.*)
clasohm@1294
   111
qed_goal "subst_eqtyparg" CTT.thy
wenzelm@3837
   112
    "a=c : A ==> (!!z. z:A ==> B(z) type) ==> B(a)=B(c)"
clasohm@0
   113
 (fn prems=>
clasohm@1459
   114
  [ (rtac subst_typeL 1),
clasohm@1459
   115
    (rtac refl_type 2),
clasohm@0
   116
    (ALLGOALS (resolve_tac prems)),
clasohm@0
   117
    (assume_tac 1) ]);
clasohm@0
   118
clasohm@0
   119
(*Make a reduction rule for simplification.
clasohm@0
   120
  A goal a=c becomes b=c, by virtue of a=b *)
clasohm@0
   121
fun resolve_trans rl = rl RS trans_elem;
clasohm@0
   122
clasohm@0
   123
(*Simplification rules for Constructive Type Theory*)
clasohm@0
   124
val reduction_rls = map resolve_trans comp_rls;
clasohm@0
   125
clasohm@0
   126
(*Converts each goal "e : Eq(A,a,b)" into "a=b:A" for simplification.
clasohm@0
   127
  Uses other intro rules to avoid changing flexible goals.*)
clasohm@0
   128
val eqintr_tac = REPEAT_FIRST (ASSUME (filt_resolve_tac(EqI::intr_rls) 1));
clasohm@0
   129
clasohm@0
   130
(** Tactics that instantiate CTT-rules.
clasohm@0
   131
    Vars in the given terms will be incremented! 
clasohm@1459
   132
    The (rtac EqE i) lets them apply to equality judgements. **)
clasohm@0
   133
clasohm@0
   134
fun NE_tac (sp: string) i = 
clasohm@1459
   135
  TRY (rtac EqE i) THEN res_inst_tac [ ("p",sp) ] NE i;
clasohm@0
   136
clasohm@0
   137
fun SumE_tac (sp: string) i = 
clasohm@1459
   138
  TRY (rtac EqE i) THEN res_inst_tac [ ("p",sp) ] SumE i;
clasohm@0
   139
clasohm@0
   140
fun PlusE_tac (sp: string) i = 
clasohm@1459
   141
  TRY (rtac EqE i) THEN res_inst_tac [ ("p",sp) ] PlusE i;
clasohm@0
   142
clasohm@0
   143
(** Predicate logic reasoning, WITH THINNING!!  Procedures adapted from NJ. **)
clasohm@0
   144
clasohm@0
   145
(*Finds f:Prod(A,B) and a:A in the assumptions, concludes there is z:B(a) *)
clasohm@0
   146
fun add_mp_tac i = 
clasohm@1459
   147
    rtac subst_prodE i  THEN  assume_tac i  THEN  assume_tac i;
clasohm@0
   148
clasohm@0
   149
(*Finds P-->Q and P in the assumptions, replaces implication by Q *)
clasohm@1459
   150
fun mp_tac i = etac subst_prodE i  THEN  assume_tac i;
clasohm@0
   151
clasohm@0
   152
(*"safe" when regarded as predicate calculus rules*)
wenzelm@4440
   153
val safe_brls = sort (make_ord lessb)
clasohm@0
   154
    [ (true,FE), (true,asm_rl), 
clasohm@0
   155
      (false,ProdI), (true,SumE), (true,PlusE) ];
clasohm@0
   156
clasohm@0
   157
val unsafe_brls =
clasohm@0
   158
    [ (false,PlusI_inl), (false,PlusI_inr), (false,SumI), 
clasohm@0
   159
      (true,subst_prodE) ];
clasohm@0
   160
clasohm@0
   161
(*0 subgoals vs 1 or more*)
clasohm@0
   162
val (safe0_brls, safep_brls) =
clasohm@0
   163
    partition (apl(0,op=) o subgoals_of_brl) safe_brls;
clasohm@0
   164
clasohm@0
   165
fun safestep_tac thms i =
clasohm@0
   166
    form_tac  ORELSE  
clasohm@0
   167
    resolve_tac thms i  ORELSE
clasohm@0
   168
    biresolve_tac safe0_brls i  ORELSE  mp_tac i  ORELSE
clasohm@0
   169
    DETERM (biresolve_tac safep_brls i);
clasohm@0
   170
clasohm@0
   171
fun safe_tac thms i = DEPTH_SOLVE_1 (safestep_tac thms i); 
clasohm@0
   172
clasohm@0
   173
fun step_tac thms = safestep_tac thms  ORELSE'  biresolve_tac unsafe_brls;
clasohm@0
   174
clasohm@0
   175
(*Fails unless it solves the goal!*)
clasohm@0
   176
fun pc_tac thms = DEPTH_SOLVE_1 o (step_tac thms);
clasohm@0
   177
clasohm@0
   178
(** The elimination rules for fst/snd **)
clasohm@0
   179
clasohm@1294
   180
qed_goalw "SumE_fst" CTT.thy basic_defs
clasohm@0
   181
    "p : Sum(A,B) ==> fst(p) : A"
lcp@361
   182
 (fn [major] =>
lcp@361
   183
  [ (rtac (major RS SumE) 1),
lcp@361
   184
    (assume_tac 1) ]);
clasohm@0
   185
clasohm@0
   186
(*The first premise must be p:Sum(A,B) !!*)
clasohm@1294
   187
qed_goalw "SumE_snd" CTT.thy basic_defs
clasohm@0
   188
    "[| p: Sum(A,B);  A type;  !!x. x:A ==> B(x) type \
clasohm@0
   189
\    |] ==> snd(p) : B(fst(p))"
lcp@361
   190
 (fn major::prems=>
lcp@361
   191
  [ (rtac (major RS SumE) 1),
lcp@361
   192
    (resolve_tac [SumC RS subst_eqtyparg RS replace_type] 1),
lcp@361
   193
    (typechk_tac prems) ]);