# File Term.ML

    (*  Title:      CCL/Term.ML
        ID:         $Id: Term.ML,v 1.11 2005/09/17 15:35:28 wenzelm Exp $
        Author:     Martin Coen, Cambridge University Computer Laboratory
        Copyright   1993  University of Cambridge
    *)

    val simp_can_defs = [one_def,inl_def,inr_def];
    val simp_ncan_defs = [if_def,when_def,split_def,fst_def,snd_def,thd_def];
    val simp_defs = simp_can_defs @ simp_ncan_defs;

    val ind_can_defs = [zero_def,succ_def,nil_def,cons_def];
    val ind_ncan_defs = [ncase_def,nrec_def,lcase_def,lrec_def];
    val ind_defs = ind_can_defs @ ind_ncan_defs;

    val data_defs = simp_defs @ ind_defs @ [napply_def];
    val genrec_defs = [letrec_def,letrec2_def,letrec3_def];

    (*** Beta Rules, including strictness ***)

    Goalw [let_def] "~ t=bot--> let x be t in f(x) = f(t)";
    by (res_inst_tac [("t","t")] term_case 1);
    by (ALLGOALS(simp_tac(CCL_ss addsimps [caseBtrue,caseBfalse,caseBpair,caseBlam])));
    bind_thm("letB", result() RS mp);

    Goalw [let_def] "let x be bot in f(x) = bot";
    by (rtac caseBbot 1);
    qed "letBabot";

    Goalw [let_def] "let x be t in bot = bot";
    by (resolve_tac ([caseBbot] RL [term_case]) 1);
    by (ALLGOALS(simp_tac(CCL_ss addsimps [caseBtrue,caseBfalse,caseBpair,caseBlam])));
    qed "letBbbot";

    Goalw [apply_def] "(lam x. b(x)) ` a = b(a)";
    by (ALLGOALS(simp_tac(CCL_ss addsimps [caseBtrue,caseBfalse,caseBpair,caseBlam])));
    qed "applyB";

    Goalw [apply_def] "bot ` a = bot";
    by (rtac caseBbot 1);
    qed "applyBbot";

    Goalw [fix_def] "fix(f) = f(fix(f))";
    by (resolve_tac [applyB RS ssubst] 1 THEN rtac refl 1);
    qed "fixB";

    Goalw [letrec_def]
          "letrec g x be h(x,g) in g(a) = h(a,%y. letrec g x be h(x,g) in g(y))";
    by (resolve_tac [fixB RS ssubst] 1 THEN
        resolve_tac [applyB RS ssubst] 1 THEN rtac refl 1);
    qed "letrecB";

    val rawBs = caseBs @ [applyB,applyBbot];

    fun raw_mk_beta_rl defs s = prove_goalw (the_context ()) defs s
               (fn _ => [stac letrecB 1,
                         simp_tac (CCL_ss addsimps rawBs) 1]);
    fun mk_beta_rl s = raw_mk_beta_rl data_defs s;

    fun raw_mk_beta_rl defs s = prove_goalw (the_context ()) defs s
               (fn _ => [simp_tac (CCL_ss addsimps rawBs
                                   setloop (stac letrecB)) 1]);
    fun mk_beta_rl s = raw_mk_beta_rl data_defs s;

    val ifBtrue    = mk_beta_rl "if true then t else u = t";
    val ifBfalse   = mk_beta_rl "if false then t else u = u";
    val ifBbot     = mk_beta_rl "if bot then t else u = bot";

    val whenBinl   = mk_beta_rl "when(inl(a),t,u) = t(a)";
    val whenBinr   = mk_beta_rl "when(inr(a),t,u) = u(a)";
    val whenBbot   = mk_beta_rl "when(bot,t,u) = bot";

    val splitB     = mk_beta_rl "split(<a,b>,h) = h(a,b)";
    val splitBbot  = mk_beta_rl "split(bot,h) = bot";
    val fstB       = mk_beta_rl "fst(<a,b>) = a";
    val fstBbot    = mk_beta_rl "fst(bot) = bot";
    val sndB       = mk_beta_rl "snd(<a,b>) = b";
    val sndBbot    = mk_beta_rl "snd(bot) = bot";
    val thdB       = mk_beta_rl "thd(<a,<b,c>>) = c";
    val thdBbot    = mk_beta_rl "thd(bot) = bot";

    val ncaseBzero = mk_beta_rl "ncase(zero,t,u) = t";
    val ncaseBsucc = mk_beta_rl "ncase(succ(n),t,u) = u(n)";
    val ncaseBbot  = mk_beta_rl "ncase(bot,t,u) = bot";
    val nrecBzero  = mk_beta_rl "nrec(zero,t,u) = t";
    val nrecBsucc  = mk_beta_rl "nrec(succ(n),t,u) = u(n,nrec(n,t,u))";
    val nrecBbot   = mk_beta_rl "nrec(bot,t,u) = bot";

    val lcaseBnil  = mk_beta_rl "lcase([],t,u) = t";
    val lcaseBcons = mk_beta_rl "lcase(x$xs,t,u) = u(x,xs)";
    val lcaseBbot  = mk_beta_rl "lcase(bot,t,u) = bot";
    val lrecBnil   = mk_beta_rl "lrec([],t,u) = t";
    val lrecBcons  = mk_beta_rl "lrec(x$xs,t,u) = u(x,xs,lrec(xs,t,u))";
    val lrecBbot   = mk_beta_rl "lrec(bot,t,u) = bot";

    val letrec2B = raw_mk_beta_rl (data_defs @ [letrec2_def])
           "letrec g x y be h(x,y,g) in g(p,q) = \
    \                     h(p,q,%u v. letrec g x y be h(x,y,g) in g(u,v))";
    val letrec3B = raw_mk_beta_rl (data_defs @ [letrec3_def])
           "letrec g x y z be h(x,y,z,g) in g(p,q,r) = \
    \                     h(p,q,r,%u v w. letrec g x y z be h(x,y,z,g) in g(u,v,w))";

    val napplyBzero   = mk_beta_rl "f^zero`a = a";
    val napplyBsucc   = mk_beta_rl "f^succ(n)`a = f(f^n`a)";

    val termBs = [letB,applyB,applyBbot,splitB,splitBbot,
                  fstB,fstBbot,sndB,sndBbot,thdB,thdBbot,
                  ifBtrue,ifBfalse,ifBbot,whenBinl,whenBinr,whenBbot,
                  ncaseBzero,ncaseBsucc,ncaseBbot,nrecBzero,nrecBsucc,nrecBbot,
                  lcaseBnil,lcaseBcons,lcaseBbot,lrecBnil,lrecBcons,lrecBbot,
                  napplyBzero,napplyBsucc];

    (*** Constructors are injective ***)

    val term_injs = map (mk_inj_rl (the_context ())
                         [applyB,splitB,whenBinl,whenBinr,ncaseBsucc,lcaseBcons])
                   ["(inl(a) = inl(a')) <-> (a=a')",
                    "(inr(a) = inr(a')) <-> (a=a')",
                    "(succ(a) = succ(a')) <-> (a=a')",
                    "(a$b = a'$b') <-> (a=a' & b=b')"];

    (*** Constructors are distinct ***)

    val term_dstncts = mkall_dstnct_thms (the_context ()) data_defs (ccl_injs @ term_injs)
                        [["bot","inl","inr"],["bot","zero","succ"],["bot","nil","op $"]];

    (*** Rules for pre-order [= ***)

    local
      fun mk_thm s = prove_goalw (the_context ()) data_defs s (fn _ =>
                      [simp_tac (ccl_ss addsimps (ccl_porews)) 1]);
    in
      val term_porews = map mk_thm ["inl(a) [= inl(a') <-> a [= a'",
                                    "inr(b) [= inr(b') <-> b [= b'",
                                    "succ(n) [= succ(n') <-> n [= n'",
                                    "x$xs [= x'$xs' <-> x [= x'  & xs [= xs'"];
    end;

    (*** Rewriting and Proving ***)

    val term_rews = termBs @ term_injs @ term_dstncts @ ccl_porews @ term_porews;
    val term_ss = ccl_ss addsimps term_rews;

    val term_cs = ccl_cs addSEs (term_dstncts RL [notE])
                         addSDs (XH_to_Ds term_injs);