Quelle  Term.thy

(*  Title:      CCL/Term.thy
  Author: Martin Coen
  Copyright 1993 University of Cambridge
*)

section ‹Definitions of usual program constructs in CCL›

theory Term
imports CCL
begin

definition one :: "i"
  where "one == true"

definition "if" :: "[i,i,i]==>i"
    (‹(‹indent=3 notation=‹mixfix if then else›\›if _/ then _/ else _)› [0,0,60] 60)
  where "if b then t else u == case(b, t, u, λ x y. bot, λv. bot)"

definition inl :: "i==>i"
  where "inl(a) == "

definition inr :: "i==>i"
  where "inr(b) == "

definition split :: "[i,[i,i]==>i]==>i"
  where "split(t,f) == case(t, bot, bot, f, λu. bot)"

definition "when" :: "[i,i==>i,i==>i]==>i"
  where "when(t,f,g) == split(t, λb x. if b then f(x) else g(x))"

definition fst :: "i==>i"
  where "fst(t) == split(t, λx y. x)"

definition snd :: "i==>i"
  where "snd(t) == split(t, λx y. y)"

definition thd :: "i==>i"
  where "thd(t) == split(t, λx p. split(p, λy z. z))"

definition zero :: "i"
  where "zero == inl(one)"

definition succ :: "i==>i"
  where "succ(n) == inr(n)"

definition ncase :: "[i,i,i==>i]==>i"
  where "ncase(n,b,c) == when(n, λx. b, λy. c(y))"

definition "let1" :: "[i,i==>i]==>i"
  where let_def: "let1(t, f) == case(t,f(true),f(false), λx y. f(), λu. f(lam x. u(x)))"

syntax "_let1" :: "[idt,i,i]==>i"
  (‹(‹indent=3 notation=‹mixfix let be in›\›let _ be _/ in _)› [0,0,60] 60)
syntax_consts "_let1" == let1
translations "let x be a in e" == "CONST let1(a, λx. e)"

definition letrec :: "[[i,i==>i]==>i,(i==>i)==>i]==>i"
  where "letrec(h, b) == b(λx. fix(λf. lam x. h(x,λy. f`y))`x)"

definition letrec2 :: "[[i,i,i==>i==>i]==>i,(i==>i==>i)==>i]==>i"
  where "letrec2 (h, f) ==
    letrec (λp g'. split(p,λx y. h(x,y,λu v. g'())), λg'. f(λx y. g'()))"

definition letrec3 :: "[[i,i,i,i==>i==>i==>i]==>i,(i==>i==>i==>i)==>i]==>i"
  where "letrec3 (h, f) ==
    letrec (λp g'. split(p,λx xs. split(xs,λy z. h(x,y,z,λu v w. g'(>)))),
      λg'. f(λx y z. g'(>)))"

syntax
  "_letrec" :: "[idt,idt,i,i]==>i"
    (‹(‹indent=3 notation=‹mixfix letrec be in›\›letrec _ _ be _/ in _)› [0,0,0,60] 60)
  "_letrec2" :: "[idt,idt,idt,i,i]==>i"
    (‹(‹indent=3 notation=‹mixfix letrec be in›\›letrec _ _ _ be _/ in _)› [0,0,0,0,60] 60)
  "_letrec3" :: "[idt,idt,idt,idt,i,i]==>i"
    (‹(‹indent=3 notation=‹mixfix letrec be in›\›letrec _ _ _ _ be _/ in _)› [0,0,0,0,0,60] 60)
syntax_consts
  "_letrec" == letrec and
  "_letrec2" == letrec2 and
  "_letrec3" == letrec3
parse_translation ‹
  let
  fun abs_tr t u = Syntax_Trans.abs_tr [t, u];
  fun letrec_tr [f, x, a, b] =
  Syntax.const 🍋‹letrec› $ abs_tr x (abs_tr f a) $ abs_tr f b;
  fun letrec2_tr [f, x, y, a, b] =
  Syntax.const 🍋‹letrec2› $ abs_tr x (abs_tr y (abs_tr f a)) $ abs_tr f b;
  fun letrec3_tr [f, x, y, z, a, b] =
  Syntax.const 🍋‹letrec3› $ abs_tr x (abs_tr y (abs_tr z (abs_tr f a))) $ abs_tr f b;
  in
  [(🍋‹_letrec›, K letrec_tr),
  (🍋‹_letrec2›, K letrec2_tr),
  (🍋‹_letrec3›, K letrec3_tr)]
  end
 ›
print_translation ‹
  let
  val bound = Syntax_Trans.mark_bound_abs;
 
  fun letrec_tr' [Abs(x,T,Abs(f,S,a)),Abs(ff,SS,b)] =
  let
  val (f',b') = Syntax_Trans.print_abs(ff,SS,b)
  val (_,a'') = Syntax_Trans.print_abs(f,S,a)
  val (x',a') = Syntax_Trans.print_abs(x,T,a'')
  in
  Syntax.const 🍋‹_letrec› $ bound(f',SS) $ bound(x',T) $ a' $ b'
  end;
 
  fun letrec2_tr' [Abs(x,T,Abs(y,U,Abs(f,S,a))),Abs(ff,SS,b)] =
  let
  val (f',b') = Syntax_Trans.print_abs(ff,SS,b)
  val ( _,a1) = Syntax_Trans.print_abs(f,S,a)
  val (y',a2) = Syntax_Trans.print_abs(y,U,a1)
  val (x',a') = Syntax_Trans.print_abs(x,T,a2)
  in
  Syntax.const 🍋‹_letrec2› $ bound(f',SS) $ bound(x',T) $ bound(y',U) $ a' $ b'
  end;
 
  fun letrec3_tr' [Abs(x,T,Abs(y,U,Abs(z,V,Abs(f,S,a)))),Abs(ff,SS,b)] =
  let
  val (f',b') = Syntax_Trans.print_abs(ff,SS,b)
  val ( _,a1) = Syntax_Trans.print_abs(f,S,a)
  val (z',a2) = Syntax_Trans.print_abs(z,V,a1)
  val (y',a3) = Syntax_Trans.print_abs(y,U,a2)
  val (x',a') = Syntax_Trans.print_abs(x,T,a3)
  in
  Syntax.const 🍋‹_letrec3› $
  bound(f',SS) $ bound(x',T) $ bound(y',U) $ bound(z',V) $ a' $ b'
  end;
  in
  [(🍋‹letrec›, K letrec_tr'),
  (🍋‹letrec2›, K letrec2_tr'),
  (🍋‹letrec3›, K letrec3_tr')]
  end
 ›

definition nrec :: "[i,i,[i,i]==>i]==>i"
  where "nrec(n,b,c) == letrec g x be ncase(x, b, λy. c(y,g(y))) in g(n)"

definition nil :: "i"  (‹[]›)
  where "[] == inl(one)"

definition cons :: "[i,i]==>i"  (infixr ‹$› 80)
  where "h$t == inr()"

definition lcase :: "[i,i,[i,i]==>i]==>i"
  where "lcase(l,b,c) == when(l, λx. b, λy. split(y,c))"

definition lrec :: "[i,i,[i,i,i]==>i]==>i"
  where "lrec(l,b,c) == letrec g x be lcase(x, b, λh t. c(h,t,g(t))) in g(l)"

definition napply :: "[i==>i,i,i]==>i"  (‹(‹notation=‹mixfix napply›\›_ ^ _ ` _)› [56,56,56] 56)
  where "f ^n` a == nrec(n,a,λx g. f(g))"

lemmas simp_can_defs = one_def inl_def inr_def
  and simp_ncan_defs = if_def when_def split_def fst_def snd_def thd_def
lemmas simp_defs = simp_can_defs simp_ncan_defs

lemmas ind_can_defs = zero_def succ_def nil_def cons_def
  and ind_ncan_defs = ncase_def nrec_def lcase_def lrec_def
lemmas ind_defs = ind_can_defs ind_ncan_defs

lemmas data_defs = simp_defs ind_defs napply_def
  and genrec_defs = letrec_def letrec2_def letrec3_def


subsection ‹Beta Rules, including strictness›

lemma letB: "¬ t=bot ==> let x be t in f(x) = f(t)"
  apply (unfold let_def)
  apply (erule rev_mp)
  apply (rule_tac t = "t" in term_case)
      apply simp_all
  done

lemma letBabot: "let x be bot in f(x) = bot"
  unfolding let_def by (rule caseBbot)

lemma letBbbot: "let x be t in bot = bot"
  apply (unfold let_def)
  apply (rule_tac t = t in term_case)
      apply (rule caseBbot)
     apply simp_all
  done

lemma applyB: "(lam x. b(x)) ` a = b(a)"
  by (simp add: apply_def)

lemma applyBbot: "bot ` a = bot"
  unfolding apply_def by (rule caseBbot)

lemma fixB: "fix(f) = f(fix(f))"
  apply (unfold fix_def)
  apply (rule applyB [THEN ssubst], rule refl)
  done

lemma letrecB: "letrec g x be h(x,g) in g(a) = h(a,λy. letrec g x be h(x,g) in g(y))"
  apply (unfold letrec_def)
  apply (rule fixB [THEN ssubst], rule applyB [THEN ssubst], rule refl)
  done

lemmas rawBs = caseBs applyB applyBbot

method_setup beta_rl = ‹
  Scan.succeed (fn ctxt =>
  let
  val ctxt' = ctxt
  |> Context_Position.set_visible false
  |> Simplifier.add_simps @{thms rawBs}
  |> Simplifier.set_loop (fn _ => stac ctxt @{thm letrecB});
  in SIMPLE_METHOD' (CHANGED o simp_tac ctxt') end)
 ›

lemma ifBtrue: "if true then t else u = t"
  and ifBfalse: "if false then t else u = u"
  and ifBbot: "if bot then t else u = bot"
  unfolding data_defs by beta_rl+

lemma whenBinl: "when(inl(a),t,u) = t(a)"
  and whenBinr: "when(inr(a),t,u) = u(a)"
  and whenBbot: "when(bot,t,u) = bot"
  unfolding data_defs by beta_rl+

lemma splitB: "split(,h) = h(a,b)"
  and splitBbot: "split(bot,h) = bot"
  unfolding data_defs by beta_rl+

lemma fstB: "fst() = a"
  and fstBbot: "fst(bot) = bot"
  unfolding data_defs by beta_rl+

lemma sndB: "snd() = b"
  and sndBbot: "snd(bot) = bot"
  unfolding data_defs by beta_rl+

lemma thdB: "thd(>) = c"
  and thdBbot: "thd(bot) = bot"
  unfolding data_defs by beta_rl+

lemma ncaseBzero: "ncase(zero,t,u) = t"
  and ncaseBsucc: "ncase(succ(n),t,u) = u(n)"
  and ncaseBbot: "ncase(bot,t,u) = bot"
  unfolding data_defs by beta_rl+

lemma nrecBzero: "nrec(zero,t,u) = t"
  and nrecBsucc: "nrec(succ(n),t,u) = u(n,nrec(n,t,u))"
  and nrecBbot: "nrec(bot,t,u) = bot"
  unfolding data_defs by beta_rl+

lemma lcaseBnil: "lcase([],t,u) = t"
  and lcaseBcons: "lcase(x$xs,t,u) = u(x,xs)"
  and lcaseBbot: "lcase(bot,t,u) = bot"
  unfolding data_defs by beta_rl+

lemma lrecBnil: "lrec([],t,u) = t"
  and lrecBcons: "lrec(x$xs,t,u) = u(x,xs,lrec(xs,t,u))"
  and lrecBbot: "lrec(bot,t,u) = bot"
  unfolding data_defs by beta_rl+

lemma letrec2B:
  "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))"
  unfolding data_defs letrec2_def by beta_rl+

lemma letrec3B:
  "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))"
  unfolding data_defs letrec3_def by beta_rl+

lemma napplyBzero: "f^zero`a = a"
  and napplyBsucc: "f^succ(n)`a = f(f^n`a)"
  unfolding data_defs by beta_rl+

lemmas 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


subsection ‹Constructors are injective›

lemma term_injs:
  "(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')"
  by (inj_rl applyB splitB whenBinl whenBinr ncaseBsucc lcaseBcons)


subsection ‹Constructors are distinct›

ML ‹
 ML_Thms.bind_thms ("term_dstncts",
  mkall_dstnct_thms 🍋 @{thms data_defs} (@{thms ccl_injs} @ @{thms term_injs})
  [["bot","inl","inr"], ["bot","zero","succ"], ["bot","nil","cons"]]);
 ›


subsection ‹Rules for pre-order ‹[=›\›

lemma term_porews:
  "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'"
  by (simp_all add: data_defs ccl_porews)


subsection ‹Rewriting and Proving›

ML ‹
  ML_Thms.bind_thms ("term_injDs", XH_to_Ds @{thms term_injs});
 ›

lemmas term_rews = termBs term_injs term_dstncts ccl_porews term_porews

lemmas [simp] = term_rews
lemmas [elim!] = term_dstncts [THEN notE]
lemmas [dest!] = term_injDs

end