src/HOL/IMP/Compiler0.thy
changeset 27363 6d93bbe5633e
parent 23746 a455e69c31cc
child 30952 7ab2716dd93b
equal deleted inserted replaced
27362:a6dc1769fdda 27363:6d93bbe5633e
    69   of instructions; only needed for the first proof.
    69   of instructions; only needed for the first proof.
    70 *}
    70 *}
    71 lemma app_right_1:
    71 lemma app_right_1:
    72   assumes "is1 \<turnstile> \<langle>s1,i1\<rangle> -1\<rightarrow> \<langle>s2,i2\<rangle>"
    72   assumes "is1 \<turnstile> \<langle>s1,i1\<rangle> -1\<rightarrow> \<langle>s2,i2\<rangle>"
    73   shows "is1 @ is2 \<turnstile> \<langle>s1,i1\<rangle> -1\<rightarrow> \<langle>s2,i2\<rangle>"
    73   shows "is1 @ is2 \<turnstile> \<langle>s1,i1\<rangle> -1\<rightarrow> \<langle>s2,i2\<rangle>"
    74   using prems
    74   using assms
    75   by induct auto
    75   by induct auto
    76 
    76 
    77 lemma app_left_1:
    77 lemma app_left_1:
    78   assumes "is2 \<turnstile> \<langle>s1,i1\<rangle> -1\<rightarrow> \<langle>s2,i2\<rangle>"
    78   assumes "is2 \<turnstile> \<langle>s1,i1\<rangle> -1\<rightarrow> \<langle>s2,i2\<rangle>"
    79   shows "is1 @ is2 \<turnstile> \<langle>s1,size is1+i1\<rangle> -1\<rightarrow> \<langle>s2,size is1+i2\<rangle>"
    79   shows "is1 @ is2 \<turnstile> \<langle>s1,size is1+i1\<rangle> -1\<rightarrow> \<langle>s2,size is1+i2\<rangle>"
    80   using prems
    80   using assms
    81   by induct auto
    81   by induct auto
    82 
    82 
    83 declare rtrancl_induct2 [induct set: rtrancl]
    83 declare rtrancl_induct2 [induct set: rtrancl]
    84 
    84 
    85 lemma app_right:
    85 lemma app_right:
    86   assumes "is1 \<turnstile> \<langle>s1,i1\<rangle> -*\<rightarrow> \<langle>s2,i2\<rangle>"
    86   assumes "is1 \<turnstile> \<langle>s1,i1\<rangle> -*\<rightarrow> \<langle>s2,i2\<rangle>"
    87   shows "is1 @ is2 \<turnstile> \<langle>s1,i1\<rangle> -*\<rightarrow> \<langle>s2,i2\<rangle>"
    87   shows "is1 @ is2 \<turnstile> \<langle>s1,i1\<rangle> -*\<rightarrow> \<langle>s2,i2\<rangle>"
    88   using prems
    88   using assms
    89 proof induct
    89 proof induct
    90   show "is1 @ is2 \<turnstile> \<langle>s1,i1\<rangle> -*\<rightarrow> \<langle>s1,i1\<rangle>" by simp
    90   show "is1 @ is2 \<turnstile> \<langle>s1,i1\<rangle> -*\<rightarrow> \<langle>s1,i1\<rangle>" by simp
    91 next
    91 next
    92   fix s1' i1' s2 i2
    92   fix s1' i1' s2 i2
    93   assume "is1 @ is2 \<turnstile> \<langle>s1,i1\<rangle> -*\<rightarrow> \<langle>s1',i1'\<rangle>"
    93   assume "is1 @ is2 \<turnstile> \<langle>s1,i1\<rangle> -*\<rightarrow> \<langle>s1',i1'\<rangle>"
    97 qed
    97 qed
    98 
    98 
    99 lemma app_left:
    99 lemma app_left:
   100   assumes "is2 \<turnstile> \<langle>s1,i1\<rangle> -*\<rightarrow> \<langle>s2,i2\<rangle>"
   100   assumes "is2 \<turnstile> \<langle>s1,i1\<rangle> -*\<rightarrow> \<langle>s2,i2\<rangle>"
   101   shows "is1 @ is2 \<turnstile> \<langle>s1,size is1+i1\<rangle> -*\<rightarrow> \<langle>s2,size is1+i2\<rangle>"
   101   shows "is1 @ is2 \<turnstile> \<langle>s1,size is1+i1\<rangle> -*\<rightarrow> \<langle>s2,size is1+i2\<rangle>"
   102 using prems
   102 using assms
   103 proof induct
   103 proof induct
   104   show "is1 @ is2 \<turnstile> \<langle>s1,length is1 + i1\<rangle> -*\<rightarrow> \<langle>s1,length is1 + i1\<rangle>" by simp
   104   show "is1 @ is2 \<turnstile> \<langle>s1,length is1 + i1\<rangle> -*\<rightarrow> \<langle>s1,length is1 + i1\<rangle>" by simp
   105 next
   105 next
   106   fix s1' i1' s2 i2
   106   fix s1' i1' s2 i2
   107   assume "is1 @ is2 \<turnstile> \<langle>s1,length is1 + i1\<rangle> -*\<rightarrow> \<langle>s1',length is1 + i1'\<rangle>"
   107   assume "is1 @ is2 \<turnstile> \<langle>s1,length is1 + i1\<rangle> -*\<rightarrow> \<langle>s1',length is1 + i1'\<rangle>"
   117 
   117 
   118 lemma app1_left:
   118 lemma app1_left:
   119   assumes "is \<turnstile> \<langle>s1,i1\<rangle> -*\<rightarrow> \<langle>s2,i2\<rangle>"
   119   assumes "is \<turnstile> \<langle>s1,i1\<rangle> -*\<rightarrow> \<langle>s2,i2\<rangle>"
   120   shows "instr # is \<turnstile> \<langle>s1,Suc i1\<rangle> -*\<rightarrow> \<langle>s2,Suc i2\<rangle>"
   120   shows "instr # is \<turnstile> \<langle>s1,Suc i1\<rangle> -*\<rightarrow> \<langle>s2,Suc i2\<rangle>"
   121 proof -
   121 proof -
   122   from app_left [OF prems, of "[instr]"]
   122   from app_left [OF assms, of "[instr]"]
   123   show ?thesis by simp
   123   show ?thesis by simp
   124 qed
   124 qed
   125 
   125 
   126 subsection "Compiler correctness"
   126 subsection "Compiler correctness"
   127 
   127 
   134   but application of induction hypothesis requires the above lifting lemmas
   134   but application of induction hypothesis requires the above lifting lemmas
   135 *}
   135 *}
   136 theorem
   136 theorem
   137   assumes "\<langle>c,s\<rangle> \<longrightarrow>\<^sub>c t"
   137   assumes "\<langle>c,s\<rangle> \<longrightarrow>\<^sub>c t"
   138   shows "compile c \<turnstile> \<langle>s,0\<rangle> -*\<rightarrow> \<langle>t,length(compile c)\<rangle>" (is "?P c s t")
   138   shows "compile c \<turnstile> \<langle>s,0\<rangle> -*\<rightarrow> \<langle>t,length(compile c)\<rangle>" (is "?P c s t")
   139   using prems
   139   using assms
   140 proof induct
   140 proof induct
   141   show "\<And>s. ?P \<SKIP> s s" by simp
   141   show "\<And>s. ?P \<SKIP> s s" by simp
   142 next
   142 next
   143   show "\<And>a s x. ?P (x :== a) s (s[x\<mapsto> a s])" by force
   143   show "\<And>a s x. ?P (x :== a) s (s[x\<mapsto> a s])" by force
   144 next
   144 next