diff -r ed47044ee6a6 -r 2e48182cc82c src/HOL/Isar_Examples/Expr_Compiler.thy --- a/src/HOL/Isar_Examples/Expr_Compiler.thy Sat Dec 26 15:03:41 2015 +0100 +++ b/src/HOL/Isar_Examples/Expr_Compiler.thy Sat Dec 26 15:44:14 2015 +0100 @@ -1,5 +1,5 @@ (* Title: HOL/Isar_Examples/Expr_Compiler.thy - Author: Markus Wenzel, TU Muenchen + Author: Makarius Correctness of a simple expression/stack-machine compiler. *) @@ -10,32 +10,40 @@ imports Main begin -text \This is a (rather trivial) example of program verification. We model a +text \ + This is a (rather trivial) example of program verification. We model a compiler for translating expressions to stack machine instructions, and - prove its correctness wrt.\ some evaluation semantics.\ + prove its correctness wrt.\ some evaluation semantics. +\ subsection \Binary operations\ -text \Binary operations are just functions over some type of values. This is - both for abstract syntax and semantics, i.e.\ we use a ``shallow - embedding'' here.\ +text \ + Binary operations are just functions over some type of values. This is both + for abstract syntax and semantics, i.e.\ we use a ``shallow embedding'' + here. +\ type_synonym 'val binop = "'val \ 'val \ 'val" subsection \Expressions\ -text \The language of expressions is defined as an inductive type, - consisting of variables, constants, and binary operations on expressions.\ +text \ + The language of expressions is defined as an inductive type, consisting of + variables, constants, and binary operations on expressions. +\ datatype (dead 'adr, dead 'val) expr = Variable 'adr | Constant 'val | Binop "'val binop" "('adr, 'val) expr" "('adr, 'val) expr" -text \Evaluation (wrt.\ some environment of variable assignments) is defined - by primitive recursion over the structure of expressions.\ +text \ + Evaluation (wrt.\ some environment of variable assignments) is defined by + primitive recursion over the structure of expressions. +\ primrec eval :: "('adr, 'val) expr \ ('adr \ 'val) \ 'val" where @@ -46,15 +54,19 @@ subsection \Machine\ -text \Next we model a simple stack machine, with three instructions.\ +text \ + Next we model a simple stack machine, with three instructions. +\ datatype (dead 'adr, dead 'val) instr = Const 'val | Load 'adr | Apply "'val binop" -text \Execution of a list of stack machine instructions is easily defined as - follows.\ +text \ + Execution of a list of stack machine instructions is easily defined as + follows. +\ primrec exec :: "(('adr, 'val) instr) list \ 'val list \ ('adr \ 'val) \ 'val list" where @@ -72,8 +84,10 @@ subsection \Compiler\ -text \We are ready to define the compilation function of expressions to - lists of stack machine instructions.\ +text \ + We are ready to define the compilation function of expressions to lists of + stack machine instructions. +\ primrec compile :: "('adr, 'val) expr \ (('adr, 'val) instr) list" where @@ -82,8 +96,10 @@ | "compile (Binop f e1 e2) = compile e2 @ compile e1 @ [Apply f]" -text \The main result of this development is the correctness theorem for - \compile\. We first establish a lemma about \exec\ and list append.\ +text \ + The main result of this development is the correctness theorem for + \compile\. We first establish a lemma about \exec\ and list append. +\ lemma exec_append: "exec (xs @ ys) stack env = @@ -128,8 +144,8 @@ In the proofs above, the \simp\ method does quite a lot of work behind the scenes (mostly ``functional program execution''). Subsequently, the same reasoning is elaborated in detail --- at most one recursive function - definition is used at a time. Thus we get a better idea of what is - actually going on. + definition is used at a time. Thus we get a better idea of what is actually + going on. \ lemma exec_append':