equal
deleted
inserted
replaced
1 % |
1 % |
2 \begin{isabellebody}% |
2 \begin{isabellebody}% |
3 \def\isabellecontext{simp}% |
3 \def\isabellecontext{simp}% |
4 % |
4 % |
5 \isamarkupsubsubsection{Simplification rules} |
5 \isamarkupsubsubsection{Simplification rules% |
|
6 } |
6 % |
7 % |
7 \begin{isamarkuptext}% |
8 \begin{isamarkuptext}% |
8 \indexbold{simplification rule} |
9 \indexbold{simplification rule} |
9 To facilitate simplification, theorems can be declared to be simplification |
10 To facilitate simplification, theorems can be declared to be simplification |
10 rules (with the help of the attribute \isa{{\isacharbrackleft}simp{\isacharbrackright}}\index{*simp |
11 rules (with the help of the attribute \isa{{\isacharbrackleft}simp{\isacharbrackright}}\index{*simp |
37 to include simplification rules that can lead to nontermination, either on |
38 to include simplification rules that can lead to nontermination, either on |
38 their own or in combination with other simplification rules. |
39 their own or in combination with other simplification rules. |
39 \end{warn}% |
40 \end{warn}% |
40 \end{isamarkuptext}% |
41 \end{isamarkuptext}% |
41 % |
42 % |
42 \isamarkupsubsubsection{The simplification method} |
43 \isamarkupsubsubsection{The simplification method% |
|
44 } |
43 % |
45 % |
44 \begin{isamarkuptext}% |
46 \begin{isamarkuptext}% |
45 \index{*simp (method)|bold} |
47 \index{*simp (method)|bold} |
46 The general format of the simplification method is |
48 The general format of the simplification method is |
47 \begin{quote} |
49 \begin{quote} |
53 only the first subgoal and may thus need to be repeated---use |
55 only the first subgoal and may thus need to be repeated---use |
54 \isaindex{simp_all} to simplify all subgoals. |
56 \isaindex{simp_all} to simplify all subgoals. |
55 Note that \isa{simp} fails if nothing changes.% |
57 Note that \isa{simp} fails if nothing changes.% |
56 \end{isamarkuptext}% |
58 \end{isamarkuptext}% |
57 % |
59 % |
58 \isamarkupsubsubsection{Adding and deleting simplification rules} |
60 \isamarkupsubsubsection{Adding and deleting simplification rules% |
|
61 } |
59 % |
62 % |
60 \begin{isamarkuptext}% |
63 \begin{isamarkuptext}% |
61 If a certain theorem is merely needed in a few proofs by simplification, |
64 If a certain theorem is merely needed in a few proofs by simplification, |
62 we do not need to make it a global simplification rule. Instead we can modify |
65 we do not need to make it a global simplification rule. Instead we can modify |
63 the set of simplification rules used in a simplification step by adding rules |
66 the set of simplification rules used in a simplification step by adding rules |
71 \begin{quote} |
74 \begin{quote} |
72 \isa{only{\isacharcolon}} \textit{list of theorem names} |
75 \isa{only{\isacharcolon}} \textit{list of theorem names} |
73 \end{quote}% |
76 \end{quote}% |
74 \end{isamarkuptext}% |
77 \end{isamarkuptext}% |
75 % |
78 % |
76 \isamarkupsubsubsection{Assumptions} |
79 \isamarkupsubsubsection{Assumptions% |
|
80 } |
77 % |
81 % |
78 \begin{isamarkuptext}% |
82 \begin{isamarkuptext}% |
79 \index{simplification!with/of assumptions} |
83 \index{simplification!with/of assumptions} |
80 By default, assumptions are part of the simplification process: they are used |
84 By default, assumptions are part of the simplification process: they are used |
81 as simplification rules and are simplified themselves. For example:% |
85 as simplification rules and are simplified themselves. For example:% |
121 |
125 |
122 Note that only one of the above options is allowed, and it must precede all |
126 Note that only one of the above options is allowed, and it must precede all |
123 other arguments.% |
127 other arguments.% |
124 \end{isamarkuptext}% |
128 \end{isamarkuptext}% |
125 % |
129 % |
126 \isamarkupsubsubsection{Rewriting with definitions} |
130 \isamarkupsubsubsection{Rewriting with definitions% |
|
131 } |
127 % |
132 % |
128 \begin{isamarkuptext}% |
133 \begin{isamarkuptext}% |
129 \index{simplification!with definitions} |
134 \index{simplification!with definitions} |
130 Constant definitions (\S\ref{sec:ConstDefinitions}) can |
135 Constant definitions (\S\ref{sec:ConstDefinitions}) can |
131 be used as simplification rules, but by default they are not. Hence the |
136 be used as simplification rules, but by default they are not. Hence the |
169 occurrences of $f$ with at least two arguments. Thus it is safer to define |
174 occurrences of $f$ with at least two arguments. Thus it is safer to define |
170 $f$~\isasymequiv~\isasymlambda$x\,y.\;t$. |
175 $f$~\isasymequiv~\isasymlambda$x\,y.\;t$. |
171 \end{warn}% |
176 \end{warn}% |
172 \end{isamarkuptext}% |
177 \end{isamarkuptext}% |
173 % |
178 % |
174 \isamarkupsubsubsection{Simplifying let-expressions} |
179 \isamarkupsubsubsection{Simplifying let-expressions% |
|
180 } |
175 % |
181 % |
176 \begin{isamarkuptext}% |
182 \begin{isamarkuptext}% |
177 \index{simplification!of let-expressions} |
183 \index{simplification!of let-expressions} |
178 Proving a goal containing \isaindex{let}-expressions almost invariably |
184 Proving a goal containing \isaindex{let}-expressions almost invariably |
179 requires the \isa{let}-con\-structs to be expanded at some point. Since |
185 requires the \isa{let}-con\-structs to be expanded at some point. Since |
188 If, in a particular context, there is no danger of a combinatorial explosion |
194 If, in a particular context, there is no danger of a combinatorial explosion |
189 of nested \isa{let}s one could even simlify with \isa{Let{\isacharunderscore}def} by |
195 of nested \isa{let}s one could even simlify with \isa{Let{\isacharunderscore}def} by |
190 default:% |
196 default:% |
191 \end{isamarkuptext}% |
197 \end{isamarkuptext}% |
192 \isacommand{declare}\ Let{\isacharunderscore}def\ {\isacharbrackleft}simp{\isacharbrackright}% |
198 \isacommand{declare}\ Let{\isacharunderscore}def\ {\isacharbrackleft}simp{\isacharbrackright}% |
193 \isamarkupsubsubsection{Conditional equations} |
199 \isamarkupsubsubsection{Conditional equations% |
|
200 } |
194 % |
201 % |
195 \begin{isamarkuptext}% |
202 \begin{isamarkuptext}% |
196 So far all examples of rewrite rules were equations. The simplifier also |
203 So far all examples of rewrite rules were equations. The simplifier also |
197 accepts \emph{conditional} equations, for example% |
204 accepts \emph{conditional} equations, for example% |
198 \end{isamarkuptext}% |
205 \end{isamarkuptext}% |
215 because the corresponding precondition \isa{rev\ xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}} |
222 because the corresponding precondition \isa{rev\ xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}} |
216 simplifies to \isa{xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}}, which is exactly the local |
223 simplifies to \isa{xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}}, which is exactly the local |
217 assumption of the subgoal.% |
224 assumption of the subgoal.% |
218 \end{isamarkuptext}% |
225 \end{isamarkuptext}% |
219 % |
226 % |
220 \isamarkupsubsubsection{Automatic case splits} |
227 \isamarkupsubsubsection{Automatic case splits% |
|
228 } |
221 % |
229 % |
222 \begin{isamarkuptext}% |
230 \begin{isamarkuptext}% |
223 \indexbold{case splits}\index{*split|(} |
231 \indexbold{case splits}\index{*split|(} |
224 Goals containing \isa{if}-expressions are usually proved by case |
232 Goals containing \isa{if}-expressions are usually proved by case |
225 distinction on the condition of the \isa{if}. For example the goal% |
233 distinction on the condition of the \isa{if}. For example the goal% |
308 \end{warn} |
316 \end{warn} |
309 |
317 |
310 \index{*split|)}% |
318 \index{*split|)}% |
311 \end{isamarkuptxt}% |
319 \end{isamarkuptxt}% |
312 % |
320 % |
313 \isamarkupsubsubsection{Arithmetic} |
321 \isamarkupsubsubsection{Arithmetic% |
|
322 } |
314 % |
323 % |
315 \begin{isamarkuptext}% |
324 \begin{isamarkuptext}% |
316 \index{arithmetic} |
325 \index{arithmetic} |
317 The simplifier routinely solves a small class of linear arithmetic formulae |
326 The simplifier routinely solves a small class of linear arithmetic formulae |
318 (over type \isa{nat} and other numeric types): it only takes into account |
327 (over type \isa{nat} and other numeric types): it only takes into account |
328 \begin{isamarkuptext}% |
337 \begin{isamarkuptext}% |
329 \noindent |
338 \noindent |
330 is not proved by simplification and requires \isa{arith}.% |
339 is not proved by simplification and requires \isa{arith}.% |
331 \end{isamarkuptext}% |
340 \end{isamarkuptext}% |
332 % |
341 % |
333 \isamarkupsubsubsection{Tracing} |
342 \isamarkupsubsubsection{Tracing% |
|
343 } |
334 % |
344 % |
335 \begin{isamarkuptext}% |
345 \begin{isamarkuptext}% |
336 \indexbold{tracing the simplifier} |
346 \indexbold{tracing the simplifier} |
337 Using the simplifier effectively may take a bit of experimentation. Set the |
347 Using the simplifier effectively may take a bit of experimentation. Set the |
338 \isaindexbold{trace_simp} \rmindex{flag} to get a better idea of what is going |
348 \isaindexbold{trace_simp} \rmindex{flag} to get a better idea of what is going |