src/HOL/Isar_examples/ExprCompiler.thy
author haftmann
Mon Jan 30 08:20:56 2006 +0100 (2006-01-30)
changeset 18851 9502ce541f01
parent 18193 54419506df9e
child 20503 503ac4c5ef91
permissions -rw-r--r--
adaptions to codegen_package
wenzelm@6444
     1
(*  Title:      HOL/Isar_examples/ExprCompiler.thy
wenzelm@6444
     2
    ID:         $Id$
wenzelm@6444
     3
    Author:     Markus Wenzel, TU Muenchen
wenzelm@6444
     4
wenzelm@6444
     5
Correctness of a simple expression/stack-machine compiler.
wenzelm@6444
     6
*)
wenzelm@6444
     7
wenzelm@10007
     8
header {* Correctness of a simple expression compiler *}
wenzelm@7748
     9
haftmann@16417
    10
theory ExprCompiler imports Main begin
wenzelm@6444
    11
wenzelm@7869
    12
text {*
wenzelm@7874
    13
 This is a (rather trivial) example of program verification.  We model
wenzelm@7874
    14
 a compiler for translating expressions to stack machine instructions,
wenzelm@7874
    15
 and prove its correctness wrt.\ some evaluation semantics.
wenzelm@10007
    16
*}
wenzelm@7869
    17
wenzelm@7869
    18
wenzelm@10007
    19
subsection {* Binary operations *}
wenzelm@6444
    20
wenzelm@6744
    21
text {*
wenzelm@7869
    22
 Binary operations are just functions over some type of values.  This
wenzelm@7982
    23
 is both for abstract syntax and semantics, i.e.\ we use a ``shallow
wenzelm@7874
    24
 embedding'' here.
wenzelm@10007
    25
*}
wenzelm@6444
    26
wenzelm@6444
    27
types
wenzelm@10007
    28
  'val binop = "'val => 'val => 'val"
wenzelm@6444
    29
wenzelm@6444
    30
wenzelm@10007
    31
subsection {* Expressions *}
wenzelm@7869
    32
wenzelm@7869
    33
text {*
wenzelm@7869
    34
 The language of expressions is defined as an inductive type,
wenzelm@7869
    35
 consisting of variables, constants, and binary operations on
wenzelm@7869
    36
 expressions.
wenzelm@10007
    37
*}
wenzelm@7869
    38
wenzelm@7869
    39
datatype ('adr, 'val) expr =
wenzelm@7869
    40
  Variable 'adr |
wenzelm@7869
    41
  Constant 'val |
wenzelm@10007
    42
  Binop "'val binop" "('adr, 'val) expr" "('adr, 'val) expr"
wenzelm@7869
    43
wenzelm@7869
    44
text {*
wenzelm@7874
    45
 Evaluation (wrt.\ some environment of variable assignments) is
wenzelm@7874
    46
 defined by primitive recursion over the structure of expressions.
wenzelm@10007
    47
*}
wenzelm@7869
    48
wenzelm@7869
    49
consts
wenzelm@10007
    50
  eval :: "('adr, 'val) expr => ('adr => 'val) => 'val"
wenzelm@7869
    51
wenzelm@7869
    52
primrec
wenzelm@7869
    53
  "eval (Variable x) env = env x"
wenzelm@7869
    54
  "eval (Constant c) env = c"
wenzelm@10007
    55
  "eval (Binop f e1 e2) env = f (eval e1 env) (eval e2 env)"
wenzelm@7869
    56
wenzelm@7869
    57
wenzelm@10007
    58
subsection {* Machine *}
wenzelm@6444
    59
wenzelm@6744
    60
text {*
wenzelm@6792
    61
 Next we model a simple stack machine, with three instructions.
wenzelm@10007
    62
*}
wenzelm@6444
    63
wenzelm@6444
    64
datatype ('adr, 'val) instr =
wenzelm@6444
    65
  Const 'val |
wenzelm@6444
    66
  Load 'adr |
wenzelm@10007
    67
  Apply "'val binop"
wenzelm@6444
    68
wenzelm@6744
    69
text {*
wenzelm@7869
    70
 Execution of a list of stack machine instructions is easily defined
wenzelm@7869
    71
 as follows.
wenzelm@10007
    72
*}
wenzelm@6444
    73
wenzelm@6444
    74
consts
wenzelm@7761
    75
  exec :: "(('adr, 'val) instr) list
wenzelm@10007
    76
    => 'val list => ('adr => 'val) => 'val list"
wenzelm@6444
    77
wenzelm@6444
    78
primrec
wenzelm@6444
    79
  "exec [] stack env = stack"
wenzelm@6444
    80
  "exec (instr # instrs) stack env =
wenzelm@6444
    81
    (case instr of
wenzelm@6444
    82
      Const c => exec instrs (c # stack) env
wenzelm@6444
    83
    | Load x => exec instrs (env x # stack) env
wenzelm@7761
    84
    | Apply f => exec instrs (f (hd stack) (hd (tl stack))
wenzelm@10007
    85
                   # (tl (tl stack))) env)"
wenzelm@6444
    86
wenzelm@6444
    87
constdefs
wenzelm@6444
    88
  execute :: "(('adr, 'val) instr) list => ('adr => 'val) => 'val"
wenzelm@10007
    89
  "execute instrs env == hd (exec instrs [] env)"
wenzelm@6444
    90
wenzelm@6444
    91
wenzelm@10007
    92
subsection {* Compiler *}
wenzelm@6444
    93
wenzelm@6744
    94
text {*
wenzelm@7869
    95
 We are ready to define the compilation function of expressions to
wenzelm@6792
    96
 lists of stack machine instructions.
wenzelm@10007
    97
*}
wenzelm@6444
    98
wenzelm@6444
    99
consts
wenzelm@10007
   100
  compile :: "('adr, 'val) expr => (('adr, 'val) instr) list"
wenzelm@6444
   101
wenzelm@6444
   102
primrec
wenzelm@8031
   103
  "compile (Variable x) = [Load x]"
wenzelm@8031
   104
  "compile (Constant c) = [Const c]"
wenzelm@10007
   105
  "compile (Binop f e1 e2) = compile e2 @ compile e1 @ [Apply f]"
wenzelm@6444
   106
wenzelm@6444
   107
wenzelm@6744
   108
text {*
wenzelm@8051
   109
 The main result of this development is the correctness theorem for
wenzelm@8051
   110
 $\idt{compile}$.  We first establish a lemma about $\idt{exec}$ and
wenzelm@8051
   111
 list append.
wenzelm@10007
   112
*}
wenzelm@6444
   113
wenzelm@6444
   114
lemma exec_append:
wenzelm@18153
   115
  "exec (xs @ ys) stack env =
wenzelm@18153
   116
    exec ys (exec xs stack env) env"
wenzelm@18153
   117
proof (induct xs fixing: stack)
wenzelm@18153
   118
  case Nil
wenzelm@18153
   119
  show ?case by simp
wenzelm@11809
   120
next
wenzelm@18153
   121
  case (Cons x xs)
wenzelm@18153
   122
  show ?case
wenzelm@11809
   123
  proof (induct x)
wenzelm@18153
   124
    case Const show ?case by simp
wenzelm@18153
   125
  next
wenzelm@18153
   126
    case Load show ?case by simp
wenzelm@18153
   127
  next
wenzelm@18153
   128
    case Apply show ?case by simp
wenzelm@10007
   129
  qed
wenzelm@10007
   130
qed
wenzelm@6444
   131
wenzelm@10007
   132
theorem correctness: "execute (compile e) env = eval e env"
wenzelm@10007
   133
proof -
wenzelm@18193
   134
  have "\<And>stack. exec (compile e) stack env = eval e env # stack"
wenzelm@11809
   135
  proof (induct e)
wenzelm@18153
   136
    case Variable show ?case by simp
wenzelm@18153
   137
  next
wenzelm@18153
   138
    case Constant show ?case by simp
wenzelm@18153
   139
  next
wenzelm@18153
   140
    case Binop then show ?case by (simp add: exec_append)
wenzelm@10007
   141
  qed
wenzelm@10007
   142
  thus ?thesis by (simp add: execute_def)
wenzelm@10007
   143
qed
wenzelm@6444
   144
wenzelm@6444
   145
wenzelm@8051
   146
text {*
wenzelm@8051
   147
 \bigskip In the proofs above, the \name{simp} method does quite a lot
wenzelm@8051
   148
 of work behind the scenes (mostly ``functional program execution'').
wenzelm@8051
   149
 Subsequently, the same reasoning is elaborated in detail --- at most
wenzelm@8051
   150
 one recursive function definition is used at a time.  Thus we get a
wenzelm@8051
   151
 better idea of what is actually going on.
wenzelm@10007
   152
*}
wenzelm@8051
   153
wenzelm@13524
   154
lemma exec_append':
wenzelm@18153
   155
  "exec (xs @ ys) stack env = exec ys (exec xs stack env) env"
wenzelm@18153
   156
proof (induct xs fixing: stack)
wenzelm@18153
   157
  case (Nil s)
wenzelm@18153
   158
  have "exec ([] @ ys) s env = exec ys s env" by simp
wenzelm@18153
   159
  also have "... = exec ys (exec [] s env) env" by simp
wenzelm@18153
   160
  finally show ?case .
wenzelm@18153
   161
next
wenzelm@18153
   162
  case (Cons x xs s)
wenzelm@18153
   163
  show ?case
wenzelm@10007
   164
  proof (induct x)
wenzelm@18153
   165
    case (Const val)
wenzelm@18153
   166
    have "exec ((Const val # xs) @ ys) s env = exec (Const val # xs @ ys) s env"
wenzelm@18153
   167
      by simp
wenzelm@18153
   168
    also have "... = exec (xs @ ys) (val # s) env" by simp
wenzelm@18153
   169
    also from Cons have "... = exec ys (exec xs (val # s) env) env" .
wenzelm@18153
   170
    also have "... = exec ys (exec (Const val # xs) s env) env" by simp
wenzelm@18153
   171
    finally show ?case .
wenzelm@10007
   172
  next
wenzelm@18153
   173
    case (Load adr)
wenzelm@18153
   174
    from Cons show ?case by simp -- {* same as above *}
wenzelm@18153
   175
  next
wenzelm@18153
   176
    case (Apply fun)
wenzelm@18153
   177
    have "exec ((Apply fun # xs) @ ys) s env =
wenzelm@18153
   178
        exec (Apply fun # xs @ ys) s env" by simp
wenzelm@18153
   179
    also have "... =
wenzelm@18153
   180
        exec (xs @ ys) (fun (hd s) (hd (tl s)) # (tl (tl s))) env" by simp
wenzelm@18153
   181
    also from Cons have "... =
wenzelm@18153
   182
        exec ys (exec xs (fun (hd s) (hd (tl s)) # tl (tl s)) env) env" .
wenzelm@18153
   183
    also have "... = exec ys (exec (Apply fun # xs) s env) env" by simp
wenzelm@18153
   184
    finally show ?case .
wenzelm@10007
   185
  qed
wenzelm@10007
   186
qed
wenzelm@6444
   187
wenzelm@13537
   188
theorem correctness': "execute (compile e) env = eval e env"
wenzelm@10007
   189
proof -
wenzelm@18193
   190
  have exec_compile: "\<And>stack. exec (compile e) stack env = eval e env # stack"
wenzelm@10007
   191
  proof (induct e)
wenzelm@18153
   192
    case (Variable adr s)
wenzelm@18153
   193
    have "exec (compile (Variable adr)) s env = exec [Load adr] s env"
wenzelm@18153
   194
      by simp
wenzelm@18153
   195
    also have "... = env adr # s" by simp
wenzelm@18153
   196
    also have "env adr = eval (Variable adr) env" by simp
wenzelm@18153
   197
    finally show ?case .
wenzelm@10007
   198
  next
wenzelm@18153
   199
    case (Constant val s)
wenzelm@18153
   200
    show ?case by simp -- {* same as above *}
wenzelm@10007
   201
  next
wenzelm@18153
   202
    case (Binop fun e1 e2 s)
wenzelm@18153
   203
    have "exec (compile (Binop fun e1 e2)) s env =
wenzelm@18153
   204
        exec (compile e2 @ compile e1 @ [Apply fun]) s env" by simp
wenzelm@18153
   205
    also have "... = exec [Apply fun]
wenzelm@18153
   206
        (exec (compile e1) (exec (compile e2) s env) env) env"
wenzelm@18153
   207
      by (simp only: exec_append)
wenzelm@18153
   208
    also have "exec (compile e2) s env = eval e2 env # s" by fact
wenzelm@18153
   209
    also have "exec (compile e1) ... env = eval e1 env # ..." by fact
wenzelm@18153
   210
    also have "exec [Apply fun] ... env =
wenzelm@10007
   211
        fun (hd ...) (hd (tl ...)) # (tl (tl ...))" by simp
wenzelm@18153
   212
    also have "... = fun (eval e1 env) (eval e2 env) # s" by simp
wenzelm@18153
   213
    also have "fun (eval e1 env) (eval e2 env) =
wenzelm@18153
   214
        eval (Binop fun e1 e2) env"
wenzelm@18153
   215
      by simp
wenzelm@18153
   216
    finally show ?case .
wenzelm@10007
   217
  qed
wenzelm@8051
   218
wenzelm@10007
   219
  have "execute (compile e) env = hd (exec (compile e) [] env)"
wenzelm@10007
   220
    by (simp add: execute_def)
wenzelm@10007
   221
  also from exec_compile
wenzelm@18153
   222
    have "exec (compile e) [] env = [eval e env]" .
wenzelm@10007
   223
  also have "hd ... = eval e env" by simp
wenzelm@10007
   224
  finally show ?thesis .
wenzelm@10007
   225
qed
wenzelm@6444
   226
wenzelm@10007
   227
end