Impressum Big_Step.thy

(* Author: Gerwin Klein, Tobias Nipkow *)

theory Big_Stepimports

subsection "Big-Step Semantics of Commands"

textopenc,s) ==> s'›.
The big-step semantics is a straightefinition<
with concrete syntax. Note that therameter
so the yntax(c,s) ==> s'›.
› s(x := aval

inductive
  big_step :: "com × state ==> state ==> bool" (infix ‹==>› 55)
where
Skip: "(SKIP,s) \<Rightarrow> s" |
Assign: "(x ::= a,s) \<Rightarrowrrow( al) 
Seq: "\<lbrakk> (c\<^sub>1,s\<^sub>1) \<Rightarrow>s\<^sub>2;  (c\<^sub>2,s\^>) \<Rightarrow> s\<^sub>3 \<rbrakk> \<Longrightarrow> (c\<^sub>1;;c\^sub2\^>) \<Rightarrow> s\<^sub>3" |
IfTrue: "\<lbrakk> bval b s;  (c\<^sub>1,s) \<Rightarrow<> \<Longrightarrow> (IF b THEN c\<^sub>1 ELSE <sub2, s) \<Rightarrow> t" |
se\<lbrakk> \<not>bval b s;  (c\<^sub>2,s) \<Rightarrow> t \<rbrakk> \<Longrightarrow> (IF b THEN c\<^sub>1 ELSE c\<^sub>2, s) \<Rightarrow> t" |
WhileFalse "not>bvalLongrightarrow> (WHILE b DO c,s) \<Rightarrow> s" |
WhileTrue:
"\<lbrakk> bval b s\<^sub>1;  (c,s\<^sub>1) \<Rightarrow> s\<^sub>2;  (WHILE b DO c, s\<^sub>2) \<Rightarrow> s\<^sub>3 \<rbrakk> 
\<Longrightarrow> (WHILE b DO c, sub1) \<Rightarrow> s\<^sub>3"

text\<open>We want to execute the big-step rules:\<close>

code_pred big_step .

text\<open>For inductive definitions we need command
       ttvalueses nstead textttluee.close>

values "{t. (SKIP, <lambda>_.0\Rightarrow t}"

text\<open>We need to translate the result state into a list
oay.close

values "{map t [''x'']  

values "{map topen side and from that construct a derivation tree for the other side\<close>

values "{map t [''x'',''y''] |t.
  (WHILE Less (V ''x'') (V ''y'') DO (''x'' ::s ') 
   <''x'' := 0, ''y'' := 13>) \<Rightarrow> "


text>?w, s) \<Rightarrow> t\<close> obtain s' where

text \<open>The introduction rules are good forautomaticallyally
construction small program executions. The cursives
may require backtracking, so we declare the set unsafe
introjava.lang.StringIndexOutOfBoundsException: Index 14 out of bounds for length 14
declare big_step.intros ntro

text\<open>The standard induction rule 
@{thm [display] big_step.induct [no_vars]}\<close>

thm big_step.induct

text\<open>
This induction schema is almost perfect for our purposes, but
our trick for reusing the tuple syntax means that the induction
schema has two parameters instead of the \<open>c\<close>, \<open>s\<close>,
and \<open>s'\<close> that we are likely to encounter. Splitting
the tuple parameter fixes this:
\<close>
lemmas big_step_induct = big_step.induct[split_format(complete)]
thm big_step_induct
text \<open>
@{thm [display] big_step_induct [no_vars]}
\<close>


subsection "Rule inversion"

text\<open>What can we deduce from @{prop "(SKIP,s) \<Rightarrow> t"} ?
That @{prop "s = t"}.  is how we can automatically prove it:\<closejava.lang.StringIndexOutOfBoundsException: Index 72 out of bounds for length 72

inductive_cases SkipE[elim!]: "(SKIP,s) \<Rightarrow> t"
thm SkipE

text\<open>This is an \emph{elimination rule}. The [elim] attribute tells auto,
blast and friends (but not simp!)   it; [elim!] means that
it isappliedrly

Similarly for the other commands:\<close>

inductive_cases AssignE[elim!]: "(x ::=java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
ssignE
inductive_cases SeqE[elim!]: "(c1;;c2,s1) \<Rightarrow> s3"
thm SeqE
inductive_cases IfE[elim!]: "(IF b THEN c1 ELSE c2,s) \<Rightarrow> t"
thm

inductive_cases WhileE[elim]: "(WHILE b DO c,s) \<Rightarrow> t"
thm WhileE
text\<open>Only [elim]: [elim!] would not terminate.\<close>

text<java.lang.StringIndexOutOfBoundsException: Index 8 out of bounds for length 8

lemma "(IF b THEN SKIP ELSE SKIP, s) \<Rightarrow> t \<Longrightarrow> t = s"
java.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 8

text\<open>Rule inversion by hand via the `sesthodjava.lang.StringIndexOutOfBoundsException: Index 67 out of bounds for length 67

lemma assumes "(IF b THEN SKIP ELSE SKIP, s) \<Rightarrow> t"
shows "t = s"
proof-
  from assms show ?thesis
  proof casesthus?thesisbyblast
    case java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
    thus ?thesisbyblast
  next
    case IfFalse thus ?thesis by blast
  qed
qed

(* Using rule inversion to prove simplification rules: *)
lemma
  "(x ::= a,s)\Rightarrow> s' ⟷:c2s <>s2" and
  by auto

text ‹An example combining rule inversion and derivations›
lemma Seq_assoc:
  "(c1;; c2;; c3, s) ==> s' ⟷ (c1;; (c2;; c3), s) ==> s'"
proof
  assume "(c1;; c2;; c3, s) ==> s'"
  then
    c1: "(c1, s) ==> s1" and
    c2: "(c2, s1)\Rightarrow s2" and
    c3: "(c3, s2) ==> s'" by auto
  from c2 c3
  have (1>s'" by (rule Seq)
  with c1
  show "(c1;; (c2 s'  (e)
next
  ―The other direction is analogous›
  assume "(c1;; (c2;; c3), s) ==>
  thus "(c1;; c2;; c3  <>s'" by auto
qed
 lehtpnlninqac

subsection "Command

text ‹
  We call two statements \<open>c\<close> and \<open>c'\<close> equivalent wrt.\ the
  big-step semantics when \emph{\<open>c\<close> started in \<open>s\<close> terminates
  in \<open>s'\<closeiff \<open>c'\<close> started in the same \<open>s\<close> also terminates
e<>s'\<close>}. Formally:
\<close>
abbreviation
  equiv_c :: "com \<Rightarrow> com \<Rightarrow> bool" (infix \<open>\<sim>\<close> 50) where
  "c \<sim> c' \<equiv> (\<forall>s t. (c,s) \<Rightarrow> t  =  (c'       \<open>bval b s<close>


text
Warning\open\<sim>\<close> is the symbol written \verb!\ < s i m >! (without spaces).

  (IF2EN(1THENc11ELSE2)ELSE(Fb1THENc12ELSE2)
  transformation on programs:
\close
lemma unfold_while:
  "(WHILE b DO c) \<sim> (IF  ENc;WHILE   KIP"s"w\sim ?w")
proof -
  \<comment> \<open>to show the equivalenceeclose>
  \<comment> \<open>each side and from that construct a derivation tree for the other side<>
  { fix s t assume \open>This of  omaticclosejava.lang.StringIndexOutOfBoundsException: Index 44 out of bounds for length 44
    \<comment> \<open>as a first thing we note that, if @{text b} is @{text False} in state @{text s},\<close>
   \<comment><>then othstatementstementsonothing<close>
    { assume "\<not>bval b s"
      hence t="using<open>(?ws <ightarrow t\<close> by blast
      hence "(?iw, s) \<Rightarrow> t" using \<open>\<not>bval b s\<close> by blast
    }
    moreover
 >\<open>on the other hand, if @{text b} is @{text True} in state @{text s},\<close>
    \<comment> \<open>then only the       w WHILE O,^sub>1') \<Rightarrow> t'"
    { assume"bvals
      with \<open>(?w, s) \<Rightarrow> t\<close> obtain s' where
        "(c, s) \<Rightarrow> s'" and "(?w, s') \<Rightarrow> t" by auto
      \<comment> \<open>now we can build a derivation tree for the @{text IF}\<close>
      \<comment> \<open>first, the body of the True-branch:\<close>
      hence "(c;; ?w, s) \<Rightarrow> t" by (rule Seq)
      \<comment> \<open>then the whole @{text IF}\<close>
      with \<open>bval b s\<close> have "(?iw, s) \<Rightarrow> t" by (rule IfTrue)
    }
    ultimately
    \<comment> \<open>both cases together give us what we want:\<close>
    have "(?iw, s) \<Rightarrow> t" by blast
  }
  
  \<comment> \<open>now the other direction:\<close>
  { fix s t assume "(?iw, s) \<Rightarrow> t"
    \<comment> \<open>again, if @{text b} is @{text False} in state @{text s}, then the False-branch\<close>
    \<comment> \<open>of the @{text IF} is executed, and both statements do nothing:\<close>
    { assume "\<not>bval b s"
      hence "s = t" using \<open>(?iw, s) \<Rightarrow> t\<close> by blast
      hence "(?w, s) \<Rightarrow> t" using \<open>\<not>bval b s\<close> by blast
    }
    moreover
    \<comment> \<open>on the other hand, f@{xtb is{trueinstate{xt}<lose
    \<comment> \<open>then this time only the @{text IfTrue} rule can have be used\<close>
    { assume "bval b s"
      with \<open>(?iw, Rightarrow t\<close> have "(c;; ?w,s< t" by auto
    <>\<open>and for this, only the Seq-rule is applicable:\<close>
      then obtain s' where
        "(c, s) \<Rightarrow> s'" and "(?w, s') \<Rightarrow>       open(?iw, s) \<Rightarrow> t\<close> have "(c;; ?w, s) \<Rightarrow> t" by auto
      \<comment><> this information, we can build a derivation tree for the @{text WHILE}\<close>
      with \<open>bval b s\<close
      have ?> tbyrulele rue
 
    ultimately
    \< m_sym<>c') = (c' \<sim> c)" by auto
    have "(?w, s) \<Rightarrow> t" by blast
java.lang.StringIndexOutOfBoundsException: Index 3 out of bounds for length 3
  ultimately
  show ?thesis by blast
qed

text \<open>Luckily, such lengthy proofs are seldom .Isabelle
prove many such facts automatically.\<close>

lemma while_unfold:
  "(WHILE b DO c) \<sim> (IF b THEN c;; WHILE b DO c ELSE SKIP)"
by blast

lemma triv_if:
  "(IF b THEN c ELSE c) \<sim> c"
by blast

lemma commute_if:
  "(IF b1 THEN (IF b2 THEN c11 ELSE c12) ELSE c2) 
   \<sim> 
   (IF b2 THEN (IF b1 THEN c11 ELSE c2) ELSE (IF b1 THEN c12 ELSE c2))"
by blast

lemma sim_while_cong_aux:
  "(WHILE b DO c,s) \<Rightarrow> t  \<Longrightarrow> c \<sim> c' \<Longrightarrow>  (WHILE b DO c',s) \<Rightarrow> t"
apply(induction "WHILE b DO c" s t arbitrary: b c rule: big_step_induct)
 apply blast
apply blast
done

lemma sim_while_cong: "c \<sim> c' \<Longrightarrow> WHILE b DO c \<sim> WHILE b DO c'"
by (metis sim_while_cong_aux)

text \<open>Command equivalence is an equivalence relation, i.e.\ it is
reflexive, symmetric, and transitive. Because we used an abbreviation
above, Isabelle derives this automatically.\<close>

lemma sim_refl:  "c \<sim> c" by simp
lemma sim_sym:   "(c \<sim> c') = (c' \<sim> c)" by auto
lemma sim_trans: "c \<sim> c' \<Longrightarrow> c' \<sim> c'' \<Longrightarrow> c \<sim> c''" by auto

subsection "Execution is deterministic"

text \<open>This proof is automatic.\<close>

theorem big_step_determ: "\<lbrakk> (c,s) \<Rightarrow> t; (c,s) \<Rightarrow> u \<rbrakk> \<Longrightarrow> u = t"
  by (induction arbitrary: u rule: big_step.induct) blast+

text \<open>
  This is the proof as you might present it in a lecture. The remaining
  cases are simple enough to be proved automatically:
\<close>

theorem
  "(c,s) \<Rightarrow> t  \<Longrightarrow>  (c,s) \<Rightarrow> t'  \<Longrightarrow>  t' = t"
proof (induction arbitrary: t' rule: big_step.induct)
  \<comment> \<open>the only interesting case, @{text WhileTrue}:\<close>
  fix b c s s\<^sub>1 t t'
  \<comment> \<open>The assumptions of the rule:\<close>
  assume "bval b s" and "(c,s) \<Rightarrow> s\<^sub>1" and "(WHILE b DO c,s\<^sub>1) \<Rightarrow> t"
  \<comment> \<open>Ind.Hyp; note the @{text"\<And>"} because of arbitrary:\<close>
  assume IHc: "\<And>t'. (c,s) \<Rightarrow> t' \<Longrightarrow> t' = s\<^sub>1"
  assume IHw: "\<And>t'. (WHILE b DO c,s\<^sub>1) \<Rightarrow> t' \<Longrightarrow> t' = t"
  \<comment> \<open>Premise of implication:\<close>
  assume "(WHILE b DO c,s) \<Rightarrow> t'"
  with \<open>bval b s\<close> obtain s\<^sub>1' where
      c: "(c,s) \<Rightarrow> s\<^sub>1'" and
      w: "(WHILE b DO c,s\<^sub>1') \<Rightarrow> t'"
    by auto
  from c IHc have "s\<^sub>1' = s\<^sub>1" by blast
  with w IHw show "t' = t" by blast
qed blast+ \<comment> \<open>prove the rest automatically\<close>

end