src/Doc/Tutorial/CodeGen/CodeGen.thy
changeset 69505 cc2d676d5395
parent 67406 23307fd33906
child 69597 ff784d5a5bfb
equal deleted inserted replaced
69504:bda7527ccf05 69505:cc2d676d5395
    35 
    35 
    36 text\<open>
    36 text\<open>
    37 The stack machine has three instructions: load a constant value onto the
    37 The stack machine has three instructions: load a constant value onto the
    38 stack, load the contents of an address onto the stack, and apply a
    38 stack, load the contents of an address onto the stack, and apply a
    39 binary operation to the two topmost elements of the stack, replacing them by
    39 binary operation to the two topmost elements of the stack, replacing them by
    40 the result. As for @{text"expr"}, addresses and values are type parameters:
    40 the result. As for \<open>expr\<close>, addresses and values are type parameters:
    41 \<close>
    41 \<close>
    42 
    42 
    43 datatype (dead 'a, 'v) instr = Const 'v
    43 datatype (dead 'a, 'v) instr = Const 'v
    44                        | Load 'a
    44                        | Load 'a
    45                        | Apply "'v binop"
    45                        | Apply "'v binop"
    46 
    46 
    47 text\<open>
    47 text\<open>
    48 The execution of the stack machine is modelled by a function
    48 The execution of the stack machine is modelled by a function
    49 @{text"exec"} that takes a list of instructions, a store (modelled as a
    49 \<open>exec\<close> that takes a list of instructions, a store (modelled as a
    50 function from addresses to values, just like the environment for
    50 function from addresses to values, just like the environment for
    51 evaluating expressions), and a stack (modelled as a list) of values,
    51 evaluating expressions), and a stack (modelled as a list) of values,
    52 and returns the stack at the end of the execution --- the store remains
    52 and returns the stack at the end of the execution --- the store remains
    53 unchanged:
    53 unchanged:
    54 \<close>
    54 \<close>
   101   "\<forall>vs. exec (xs@ys) s vs = exec ys s (exec xs s vs)" 
   101   "\<forall>vs. exec (xs@ys) s vs = exec ys s (exec xs s vs)" 
   102 
   102 
   103 txt\<open>\noindent
   103 txt\<open>\noindent
   104 This requires induction on @{term"xs"} and ordinary simplification for the
   104 This requires induction on @{term"xs"} and ordinary simplification for the
   105 base cases. In the induction step, simplification leaves us with a formula
   105 base cases. In the induction step, simplification leaves us with a formula
   106 that contains two @{text"case"}-expressions over instructions. Thus we add
   106 that contains two \<open>case\<close>-expressions over instructions. Thus we add
   107 automatic case splitting, which finishes the proof:
   107 automatic case splitting, which finishes the proof:
   108 \<close>
   108 \<close>
   109 apply(induct_tac xs, simp, simp split: instr.split)
   109 apply(induct_tac xs, simp, simp split: instr.split)
   110 (*<*)done(*>*)
   110 (*<*)done(*>*)
   111 text\<open>\noindent
   111 text\<open>\noindent
   112 Note that because both \methdx{simp_all} and \methdx{auto} perform simplification, they can
   112 Note that because both \methdx{simp_all} and \methdx{auto} perform simplification, they can
   113 be modified in the same way as @{text simp}.  Thus the proof can be
   113 be modified in the same way as \<open>simp\<close>.  Thus the proof can be
   114 rewritten as
   114 rewritten as
   115 \<close>
   115 \<close>
   116 (*<*)
   116 (*<*)
   117 declare exec_app[simp del]
   117 declare exec_app[simp del]
   118 lemma [simp]: "\<forall>vs. exec (xs@ys) s vs = exec ys s (exec xs s vs)" 
   118 lemma [simp]: "\<forall>vs. exec (xs@ys) s vs = exec ys s (exec xs s vs)"