src/HOL/IMP/Compiler.thy
changeset 13675 01fc1fc61384
parent 13630 a013a9dd370f
child 14738 83f1a514dcb4
equal deleted inserted replaced
13674:f4c64597fb02 13675:01fc1fc61384
     9 subsection "The compiler"
     9 subsection "The compiler"
    10 
    10 
    11 consts compile :: "com \<Rightarrow> instr list"
    11 consts compile :: "com \<Rightarrow> instr list"
    12 primrec
    12 primrec
    13 "compile \<SKIP> = []"
    13 "compile \<SKIP> = []"
    14 "compile (x:==a) = [ASIN x a]"
    14 "compile (x:==a) = [SET x a]"
    15 "compile (c1;c2) = compile c1 @ compile c2"
    15 "compile (c1;c2) = compile c1 @ compile c2"
    16 "compile (\<IF> b \<THEN> c1 \<ELSE> c2) =
    16 "compile (\<IF> b \<THEN> c1 \<ELSE> c2) =
    17  [JMPF b (length(compile c1) + 1)] @ compile c1 @
    17  [JMPF b (length(compile c1) + 1)] @ compile c1 @
    18  [JMPF (%x. False) (length(compile c2))] @ compile c2"
    18  [JMPF (\<lambda>x. False) (length(compile c2))] @ compile c2"
    19 "compile (\<WHILE> b \<DO> c) = [JMPF b (length(compile c) + 1)] @ compile c @
    19 "compile (\<WHILE> b \<DO> c) = [JMPF b (length(compile c) + 1)] @ compile c @
    20  [JMPB (length(compile c)+1)]"
    20  [JMPB (length(compile c)+1)]"
    21 
    21 
    22 subsection "Compiler correctness"
    22 subsection "Compiler correctness"
    23 
    23 
    66 by(simp add: rtrancl_is_UN_rel_pow)
    66 by(simp add: rtrancl_is_UN_rel_pow)
    67 
    67 
    68 constdefs
    68 constdefs
    69  forws :: "instr \<Rightarrow> nat set"
    69  forws :: "instr \<Rightarrow> nat set"
    70 "forws instr == case instr of
    70 "forws instr == case instr of
    71  ASIN x a \<Rightarrow> {0} |
    71  SET x a \<Rightarrow> {0} |
    72  JMPF b n \<Rightarrow> {0,n} |
    72  JMPF b n \<Rightarrow> {0,n} |
    73  JMPB n \<Rightarrow> {}"
    73  JMPB n \<Rightarrow> {}"
    74  backws :: "instr \<Rightarrow> nat set"
    74  backws :: "instr \<Rightarrow> nat set"
    75 "backws instr == case instr of
    75 "backws instr == case instr of
    76  ASIN x a \<Rightarrow> {} |
    76  SET x a \<Rightarrow> {} |
    77  JMPF b n \<Rightarrow> {} |
    77  JMPF b n \<Rightarrow> {} |
    78  JMPB n \<Rightarrow> {n}"
    78  JMPB n \<Rightarrow> {n}"
    79 
    79 
    80 consts closed :: "nat \<Rightarrow> nat \<Rightarrow> instr list \<Rightarrow> bool"
    80 consts closed :: "nat \<Rightarrow> nat \<Rightarrow> instr list \<Rightarrow> bool"
    81 primrec
    81 primrec
   261       assume H: "\<langle>?W,[],s\<rangle> -n\<rightarrow> \<langle>[],rev ?W,t\<rangle>"
   261       assume H: "\<langle>?W,[],s\<rangle> -n\<rightarrow> \<langle>[],rev ?W,t\<rangle>"
   262       show "\<langle>?w,s\<rangle> \<longrightarrow>\<^sub>c t"
   262       show "\<langle>?w,s\<rangle> \<longrightarrow>\<^sub>c t"
   263       proof cases
   263       proof cases
   264 	assume b: "b s"
   264 	assume b: "b s"
   265 	then obtain m where m: "n = Suc m"
   265 	then obtain m where m: "n = Suc m"
   266           and 1: "\<langle>?C @ [?j2],[?j1],s\<rangle> -m\<rightarrow> \<langle>[],rev ?W,t\<rangle>"
   266           and "\<langle>?C @ [?j2],[?j1],s\<rangle> -m\<rightarrow> \<langle>[],rev ?W,t\<rangle>"
   267 	  using H by fastsimp
   267 	  using H by fastsimp
   268 	then obtain r n1 n2 where n1: "\<langle>?C,[],s\<rangle> -n1\<rightarrow> \<langle>[],rev ?C,r\<rangle>"
   268 	then obtain r n1 n2 where n1: "\<langle>?C,[],s\<rangle> -n1\<rightarrow> \<langle>[],rev ?C,r\<rangle>"
   269           and n2: "\<langle>[?j2],rev ?C @ [?j1],r\<rangle> -n2\<rightarrow> \<langle>[],rev ?W,t\<rangle>"
   269           and n2: "\<langle>[?j2],rev ?C @ [?j1],r\<rangle> -n2\<rightarrow> \<langle>[],rev ?W,t\<rangle>"
   270           and n12: "m = n1+n2"
   270           and n12: "m = n1+n2"
   271 	  using execn_decomp[of _ "[?j2]"]
   271 	  using execn_decomp[of _ "[?j2]"]