ex/Term.ML
changeset 48 21291189b51e
parent 0 7949f97df77a
child 114 b7f57e0ab47c
equal deleted inserted replaced
47:69d815b0e1eb 48:21291189b51e
    38 
    38 
    39 (*Induction for the set Term(A) *)
    39 (*Induction for the set Term(A) *)
    40 val [major,minor] = goal Term.thy 
    40 val [major,minor] = goal Term.thy 
    41     "[| M: Term(A);  \
    41     "[| M: Term(A);  \
    42 \       !!x zs. [| x: A;  zs: List(Term(A));  zs: List({x.R(x)}) \
    42 \       !!x zs. [| x: A;  zs: List(Term(A));  zs: List({x.R(x)}) \
    43 \               |] ==> R(x.zs)  \
    43 \               |] ==> R(x$zs)  \
    44 \    |] ==> R(M)";
    44 \    |] ==> R(M)";
    45 by (rtac (major RS (Term_def RS def_induct)) 1);
    45 by (rtac (major RS (Term_def RS def_induct)) 1);
    46 by (rtac Term_fun_mono 1);
    46 by (rtac Term_fun_mono 1);
    47 by (REPEAT (eresolve_tac ([uprodE, ssubst, minor] @
    47 by (REPEAT (eresolve_tac ([uprodE, ssubst, minor] @
    48  		([Int_lower1,Int_lower2] RL [List_mono RS subsetD])) 1));
    48  		([Int_lower1,Int_lower2] RL [List_mono RS subsetD])) 1));
    49 val Term_induct = result();
    49 val Term_induct = result();
    50 
    50 
    51 (*Induction on Term(A) followed by induction on List *)
    51 (*Induction on Term(A) followed by induction on List *)
    52 val major::prems = goal Term.thy
    52 val major::prems = goal Term.thy
    53     "[| M: Term(A);  \
    53     "[| M: Term(A);  \
    54 \       !!x.      [| x: A |] ==> R(x.NIL);  \
    54 \       !!x.      [| x: A |] ==> R(x$NIL);  \
    55 \       !!x z zs. [| x: A;  z: Term(A);  zs: List(Term(A));  R(x.zs)  \
    55 \       !!x z zs. [| x: A;  z: Term(A);  zs: List(Term(A));  R(x$zs)  \
    56 \                 |] ==> R(x . CONS(z,zs))  \
    56 \                 |] ==> R(x $ CONS(z,zs))  \
    57 \    |] ==> R(M)";
    57 \    |] ==> R(M)";
    58 by (rtac (major RS Term_induct) 1);
    58 by (rtac (major RS Term_induct) 1);
    59 by (etac List_induct 1);
    59 by (etac List_induct 1);
    60 by (REPEAT (ares_tac prems 1));
    60 by (REPEAT (ares_tac prems 1));
    61 val Term_induct2 = result();
    61 val Term_induct2 = result();
    95 val term_induct = result();
    95 val term_induct = result();
    96 
    96 
    97 (*Induction for the abstract type 'a term*)
    97 (*Induction for the abstract type 'a term*)
    98 val prems = goal Term.thy 
    98 val prems = goal Term.thy 
    99     "[| !!x. R(App(x,Nil));  \
    99     "[| !!x. R(App(x,Nil));  \
   100 \       !!x t ts. R(App(x,ts)) ==> R(App(x, Cons(t,ts)))  \
   100 \       !!x t ts. R(App(x,ts)) ==> R(App(x, t#ts))  \
   101 \    |] ==> R(t)";
   101 \    |] ==> R(t)";
   102 by (rtac term_induct 1);  (*types force good instantiation*)
   102 by (rtac term_induct 1);  (*types force good instantiation*)
   103 by (etac rev_mp 1);
   103 by (etac rev_mp 1);
   104 by (rtac list_induct 1);  (*types force good instantiation*)
   104 by (rtac list_induct 1);  (*types force good instantiation*)
   105 by (ALLGOALS (asm_simp_tac (list_all_ss addsimps prems)));
   105 by (ALLGOALS (asm_simp_tac (list_all_ss addsimps prems)));
   115 
   115 
   116 (* c : A <*> List(Term(A)) ==> c : Term(A) *)
   116 (* c : A <*> List(Term(A)) ==> c : Term(A) *)
   117 val TermI = standard (Term_unfold RS equalityD2 RS subsetD);
   117 val TermI = standard (Term_unfold RS equalityD2 RS subsetD);
   118 
   118 
   119 (*The constant APP is not declared; it is simply . *)
   119 (*The constant APP is not declared; it is simply . *)
   120 val prems = goal Term.thy "[| M: A;  N : List(Term(A)) |] ==> M.N : Term(A)";
   120 val prems = goal Term.thy "[| M: A;  N : List(Term(A)) |] ==> M$N : Term(A)";
   121 by (REPEAT (resolve_tac (prems@[TermI, ListI, uprodI]) 1));
   121 by (REPEAT (resolve_tac (prems@[TermI, ListI, uprodI]) 1));
   122 val APP_I = result();
   122 val APP_I = result();
   123 
   123 
   124 
   124 
   125 (*** Term_rec -- by wf recursion on pred_Sexp ***)
   125 (*** Term_rec -- by wf recursion on pred_Sexp ***)
   141 by (asm_simp_tac (list_all_ss addsimps [trancl_pred_SexpD1, cut_apply]) 1);
   141 by (asm_simp_tac (list_all_ss addsimps [trancl_pred_SexpD1, cut_apply]) 1);
   142 val Abs_map_lemma = result();
   142 val Abs_map_lemma = result();
   143 
   143 
   144 val [prem1,prem2,A_subset_Sexp] = goal Term.thy
   144 val [prem1,prem2,A_subset_Sexp] = goal Term.thy
   145     "[| M: Sexp;  N: List(Term(A));  A<=Sexp |] ==> \
   145     "[| M: Sexp;  N: List(Term(A));  A<=Sexp |] ==> \
   146 \    Term_rec(M.N, d) = d(M, N, Abs_map(%Z. Term_rec(Z,d), N))";
   146 \    Term_rec(M$N, d) = d(M, N, Abs_map(%Z. Term_rec(Z,d), N))";
   147 by (rtac (Term_rec_unfold RS trans) 1);
   147 by (rtac (Term_rec_unfold RS trans) 1);
   148 by (rtac (Split RS trans) 1);
   148 by (rtac (Split RS trans) 1);
   149 by (simp_tac (HOL_ss addsimps
   149 by (simp_tac (HOL_ss addsimps
   150       [prem2 RS Abs_map_lemma RS spec RS mp, pred_SexpI2 RS r_into_trancl,
   150       [prem2 RS Abs_map_lemma RS spec RS mp, pred_SexpI2 RS r_into_trancl,
   151        prem1, prem2 RS rev_subsetD, List_subset_Sexp,
   151        prem1, prem2 RS rev_subsetD, List_subset_Sexp,