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)" |