1 header "Arithmetic and Boolean Expressions"
3 theory AExp imports Main begin
5 subsection "Arithmetic Expressions"
7 type_synonym vname = string
9 type_synonym state = "vname \<Rightarrow> val"
11 text_raw{*\snip{AExpaexpdef}{2}{1}{% *}
12 datatype aexp = N int | V vname | Plus aexp aexp
15 text_raw{*\snip{AExpavaldef}{1}{2}{% *}
16 fun aval :: "aexp \<Rightarrow> state \<Rightarrow> val" where
18 "aval (V x) s = s x" |
19 "aval (Plus a\<^sub>1 a\<^sub>2) s = aval a\<^sub>1 s + aval a\<^sub>2 s"
23 value "aval (Plus (V ''x'') (N 5)) (\<lambda>x. if x = ''x'' then 7 else 0)"
25 text {* The same state more concisely: *}
26 value "aval (Plus (V ''x'') (N 5)) ((\<lambda>x. 0) (''x'':= 7))"
28 text {* A little syntax magic to write larger states compactly: *}
30 definition null_state ("<>") where
31 "null_state \<equiv> \<lambda>x. 0"
33 "_State" :: "updbinds => 'a" ("<_>")
35 "_State ms" == "_Update <> ms"
38 We can now write a series of updates to the function @{text "\<lambda>x. 0"} compactly:
40 lemma "<a := 1, b := 2> = (<> (a := 1)) (b := (2::int))"
43 value "aval (Plus (V ''x'') (N 5)) <''x'' := 7>"
46 text {* In the @{term[source] "<a := b>"} syntax, variables that are not mentioned are 0 by default:
48 value "aval (Plus (V ''x'') (N 5)) <''y'' := 7>"
50 text{* Note that this @{text"<\<dots>>"} syntax works for any function space
51 @{text"\<tau>\<^sub>1 \<Rightarrow> \<tau>\<^sub>2"} where @{text "\<tau>\<^sub>2"} has a @{text 0}. *}
54 subsection "Constant Folding"
56 text{* Evaluate constant subsexpressions: *}
58 text_raw{*\snip{AExpasimpconstdef}{0}{2}{% *}
59 fun asimp_const :: "aexp \<Rightarrow> aexp" where
60 "asimp_const (N n) = N n" |
61 "asimp_const (V x) = V x" |
62 "asimp_const (Plus a\<^sub>1 a\<^sub>2) =
63 (case (asimp_const a\<^sub>1, asimp_const a\<^sub>2) of
64 (N n\<^sub>1, N n\<^sub>2) \<Rightarrow> N(n\<^sub>1+n\<^sub>2) |
65 (b\<^sub>1,b\<^sub>2) \<Rightarrow> Plus b\<^sub>1 b\<^sub>2)"
68 theorem aval_asimp_const:
69 "aval (asimp_const a) s = aval a s"
71 apply (auto split: aexp.split)
74 text{* Now we also eliminate all occurrences 0 in additions. The standard
75 method: optimized versions of the constructors: *}
77 text_raw{*\snip{AExpplusdef}{0}{2}{% *}
78 fun plus :: "aexp \<Rightarrow> aexp \<Rightarrow> aexp" where
79 "plus (N i\<^sub>1) (N i\<^sub>2) = N(i\<^sub>1+i\<^sub>2)" |
80 "plus (N i) a = (if i=0 then a else Plus (N i) a)" |
81 "plus a (N i) = (if i=0 then a else Plus a (N i))" |
82 "plus a\<^sub>1 a\<^sub>2 = Plus a\<^sub>1 a\<^sub>2"
85 lemma aval_plus[simp]:
86 "aval (plus a1 a2) s = aval a1 s + aval a2 s"
87 apply(induction a1 a2 rule: plus.induct)
88 apply simp_all (* just for a change from auto *)
91 text_raw{*\snip{AExpasimpdef}{2}{0}{% *}
92 fun asimp :: "aexp \<Rightarrow> aexp" where
95 "asimp (Plus a\<^sub>1 a\<^sub>2) = plus (asimp a\<^sub>1) (asimp a\<^sub>2)"
98 text{* Note that in @{const asimp_const} the optimized constructor was
99 inlined. Making it a separate function @{const plus} improves modularity of
100 the code and the proofs. *}
102 value "asimp (Plus (Plus (N 0) (N 0)) (Plus (V ''x'') (N 0)))"
104 theorem aval_asimp[simp]:
105 "aval (asimp a) s = aval a s"