18537
|
1 |
%
|
|
2 |
\begin{isabellebody}%
|
|
3 |
\def\isabellecontext{proof}%
|
|
4 |
%
|
|
5 |
\isadelimtheory
|
|
6 |
\isanewline
|
|
7 |
\isanewline
|
|
8 |
\isanewline
|
|
9 |
%
|
|
10 |
\endisadelimtheory
|
|
11 |
%
|
|
12 |
\isatagtheory
|
|
13 |
\isacommand{theory}\isamarkupfalse%
|
|
14 |
\ {\isachardoublequoteopen}proof{\isachardoublequoteclose}\ \isakeyword{imports}\ base\ \isakeyword{begin}%
|
|
15 |
\endisatagtheory
|
|
16 |
{\isafoldtheory}%
|
|
17 |
%
|
|
18 |
\isadelimtheory
|
|
19 |
%
|
|
20 |
\endisadelimtheory
|
|
21 |
%
|
20451
|
22 |
\isamarkupchapter{Structured proofs%
|
18537
|
23 |
}
|
|
24 |
\isamarkuptrue%
|
|
25 |
%
|
20452
|
26 |
\isamarkupsection{Variables and schematic polymorphism%
|
20027
|
27 |
}
|
|
28 |
\isamarkuptrue%
|
|
29 |
%
|
20063
|
30 |
\begin{isamarkuptext}%
|
|
31 |
FIXME%
|
|
32 |
\end{isamarkuptext}%
|
|
33 |
\isamarkuptrue%
|
|
34 |
%
|
20027
|
35 |
\isadelimmlref
|
|
36 |
%
|
|
37 |
\endisadelimmlref
|
|
38 |
%
|
|
39 |
\isatagmlref
|
|
40 |
%
|
|
41 |
\begin{isamarkuptext}%
|
|
42 |
\begin{mldecls}
|
|
43 |
\indexml{Variable.declare-term}\verb|Variable.declare_term: term -> Proof.context -> Proof.context| \\
|
20063
|
44 |
\indexml{Variable.add-fixes}\verb|Variable.add_fixes: string list -> Proof.context -> string list * Proof.context| \\
|
20459
|
45 |
\indexml{Variable.import}\verb|Variable.import: bool ->|\isasep\isanewline%
|
|
46 |
\verb| thm list -> Proof.context -> ((ctyp list * cterm list) * thm list) * Proof.context| \\
|
20027
|
47 |
\indexml{Variable.export}\verb|Variable.export: Proof.context -> Proof.context -> thm list -> thm list| \\
|
|
48 |
\indexml{Variable.trade}\verb|Variable.trade: Proof.context -> (thm list -> thm list) -> thm list -> thm list| \\
|
|
49 |
\indexml{Variable.polymorphic}\verb|Variable.polymorphic: Proof.context -> term list -> term list| \\
|
|
50 |
\end{mldecls}
|
|
51 |
|
|
52 |
\begin{description}
|
|
53 |
|
20063
|
54 |
\item \verb|Variable.declare_term|~\isa{t\ ctxt} declares term
|
|
55 |
\isa{t} to belong to the context. This fixes free type
|
|
56 |
variables, but not term variables. Constraints for type and term
|
|
57 |
variables are declared uniformly.
|
|
58 |
|
|
59 |
\item \verb|Variable.add_fixes|~\isa{xs\ ctxt} fixes term
|
|
60 |
variables \isa{xs} and returns the internal names of the
|
|
61 |
resulting Skolem constants. Note that term fixes refer to
|
|
62 |
\emph{all} type instances that may occur in the future.
|
|
63 |
|
|
64 |
\item \verb|Variable.invent_fixes| is similar to \verb|Variable.add_fixes|, but the given names merely act as hints for
|
|
65 |
internal fixes produced here.
|
20027
|
66 |
|
20063
|
67 |
\item \verb|Variable.import|~\isa{open\ ths\ ctxt} augments the
|
|
68 |
context by new fixes for the schematic type and term variables
|
|
69 |
occurring in \isa{ths}. The \isa{open} flag indicates
|
|
70 |
whether the fixed names should be accessible to the user, otherwise
|
|
71 |
internal names are chosen.
|
20027
|
72 |
|
20063
|
73 |
\item \verb|Variable.export|~\isa{inner\ outer\ ths} generalizes
|
|
74 |
fixed type and term variables in \isa{ths} according to the
|
|
75 |
difference of the \isa{inner} and \isa{outer} context. Note
|
|
76 |
that type variables occurring in term variables are still fixed.
|
|
77 |
|
|
78 |
\verb|Variable.export| essentially reverses the effect of \verb|Variable.import| (up to renaming of schematic variables.
|
20043
|
79 |
|
|
80 |
\item \verb|Variable.trade| composes \verb|Variable.import| and \verb|Variable.export|, i.e.\ it provides a view on facts with all
|
|
81 |
variables being fixed in the current context.
|
20027
|
82 |
|
20063
|
83 |
\item \verb|Variable.polymorphic|~\isa{ctxt\ ts} generalizes type
|
|
84 |
variables in \isa{ts} as far as possible, even those occurring
|
|
85 |
in fixed term variables. This operation essentially reverses the
|
|
86 |
default policy of type-inference to introduce local polymorphism as
|
|
87 |
fixed types.
|
20027
|
88 |
|
|
89 |
\end{description}%
|
|
90 |
\end{isamarkuptext}%
|
|
91 |
\isamarkuptrue%
|
|
92 |
%
|
|
93 |
\endisatagmlref
|
|
94 |
{\isafoldmlref}%
|
|
95 |
%
|
|
96 |
\isadelimmlref
|
|
97 |
%
|
|
98 |
\endisadelimmlref
|
|
99 |
%
|
18537
|
100 |
\begin{isamarkuptext}%
|
|
101 |
FIXME%
|
|
102 |
\end{isamarkuptext}%
|
|
103 |
\isamarkuptrue%
|
|
104 |
%
|
20451
|
105 |
\isamarkupsection{Assumptions%
|
|
106 |
}
|
|
107 |
\isamarkuptrue%
|
|
108 |
%
|
|
109 |
\begin{isamarkuptext}%
|
20458
|
110 |
An \emph{assumption} is a proposition that it is postulated in the
|
|
111 |
current context. Local conclusions may use assumptions as
|
|
112 |
additional facts, but this imposes implicit hypotheses that weaken
|
|
113 |
the overall statement.
|
|
114 |
|
|
115 |
Assumptions are restricted to fixed non-schematic statements, all
|
|
116 |
generality needs to be expressed by explicit quantifiers.
|
|
117 |
Nevertheless, the result will be in HHF normal form with outermost
|
|
118 |
quantifiers stripped. For example, by assuming \isa{{\isasymAnd}x\ {\isacharcolon}{\isacharcolon}\ {\isasymalpha}{\isachardot}\ P\ x} we get \isa{{\isasymAnd}x\ {\isacharcolon}{\isacharcolon}\ {\isasymalpha}{\isachardot}\ P\ x\ {\isasymturnstile}\ P\ {\isacharquery}x} for arbitrary \isa{{\isacharquery}x}
|
|
119 |
of the fixed type \isa{{\isasymalpha}}. Local derivations accumulate more
|
|
120 |
and more explicit references to hypotheses: \isa{A\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ A\isactrlisub n\ {\isasymturnstile}\ B} where \isa{A\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ A\isactrlisub n} needs to
|
|
121 |
be covered by the assumptions of the current context.
|
|
122 |
|
20459
|
123 |
\medskip The \isa{add{\isacharunderscore}assms} operation augments the context by
|
|
124 |
local assumptions, which are parameterized by an arbitrary \isa{export} rule (see below).
|
20458
|
125 |
|
|
126 |
The \isa{export} operation moves facts from a (larger) inner
|
|
127 |
context into a (smaller) outer context, by discharging the
|
|
128 |
difference of the assumptions as specified by the associated export
|
|
129 |
rules. Note that the discharged portion is determined by the
|
20459
|
130 |
difference contexts, not the facts being exported! There is a
|
|
131 |
separate flag to indicate a goal context, where the result is meant
|
|
132 |
to refine an enclosing sub-goal of a structured proof state (cf.\
|
|
133 |
\secref{sec:isar-proof-state}).
|
20458
|
134 |
|
|
135 |
\medskip The most basic export rule discharges assumptions directly
|
|
136 |
by means of the \isa{{\isasymLongrightarrow}} introduction rule:
|
|
137 |
\[
|
|
138 |
\infer[(\isa{{\isasymLongrightarrow}{\isacharunderscore}intro})]{\isa{{\isasymGamma}\ {\isacharbackslash}\ A\ {\isasymturnstile}\ A\ {\isasymLongrightarrow}\ B}}{\isa{{\isasymGamma}\ {\isasymturnstile}\ B}}
|
|
139 |
\]
|
|
140 |
|
|
141 |
The variant for goal refinements marks the newly introduced
|
|
142 |
premises, which causes the builtin goal refinement scheme of Isar to
|
|
143 |
enforce unification with local premises within the goal:
|
|
144 |
\[
|
|
145 |
\infer[(\isa{{\isacharhash}{\isasymLongrightarrow}{\isacharunderscore}intro})]{\isa{{\isasymGamma}\ {\isacharbackslash}\ A\ {\isasymturnstile}\ {\isacharhash}A\ {\isasymLongrightarrow}\ B}}{\isa{{\isasymGamma}\ {\isasymturnstile}\ B}}
|
|
146 |
\]
|
|
147 |
|
20459
|
148 |
\medskip Alternative assumptions may perform arbitrary
|
|
149 |
transformations on export, as long as a particular portion of
|
|
150 |
hypotheses is removed from the given facts. For example, a local
|
|
151 |
definition works by fixing \isa{x} and assuming \isa{x\ {\isasymequiv}\ t},
|
|
152 |
with the following export rule to reverse the effect:
|
20458
|
153 |
\[
|
|
154 |
\infer{\isa{{\isasymGamma}\ {\isacharbackslash}\ x\ {\isasymequiv}\ t\ {\isasymturnstile}\ B\ t}}{\isa{{\isasymGamma}\ {\isasymturnstile}\ B\ x}}
|
|
155 |
\]
|
|
156 |
|
|
157 |
\medskip The general concept supports block-structured reasoning
|
|
158 |
nicely, with arbitrary mechanisms for introducing local assumptions.
|
|
159 |
The common reasoning pattern is as follows:
|
|
160 |
|
|
161 |
\medskip
|
|
162 |
\begin{tabular}{l}
|
20459
|
163 |
\isa{add{\isacharunderscore}assms\ e\isactrlisub {\isadigit{1}}\ A\isactrlisub {\isadigit{1}}} \\
|
20458
|
164 |
\isa{{\isasymdots}} \\
|
20459
|
165 |
\isa{add{\isacharunderscore}assms\ e\isactrlisub n\ A\isactrlisub n} \\
|
20458
|
166 |
\isa{export} \\
|
|
167 |
\end{tabular}
|
|
168 |
\medskip
|
|
169 |
|
|
170 |
\noindent The final \isa{export} will turn any fact \isa{A\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ A\isactrlisub n\ {\isasymturnstile}\ B} into some \isa{{\isasymturnstile}\ B{\isacharprime}}, by
|
|
171 |
applying the export rules \isa{e\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ e\isactrlisub n}
|
|
172 |
inside-out.%
|
20451
|
173 |
\end{isamarkuptext}%
|
|
174 |
\isamarkuptrue%
|
|
175 |
%
|
20458
|
176 |
\isadelimmlref
|
|
177 |
%
|
|
178 |
\endisadelimmlref
|
|
179 |
%
|
|
180 |
\isatagmlref
|
|
181 |
%
|
|
182 |
\begin{isamarkuptext}%
|
|
183 |
\begin{mldecls}
|
|
184 |
\indexmltype{Assumption.export}\verb|type Assumption.export| \\
|
|
185 |
\indexml{Assumption.assume}\verb|Assumption.assume: cterm -> thm| \\
|
20459
|
186 |
\indexml{Assumption.add-assms}\verb|Assumption.add_assms: Assumption.export ->|\isasep\isanewline%
|
|
187 |
\verb| cterm list -> Proof.context -> thm list * Proof.context| \\
|
|
188 |
\indexml{Assumption.add-assumes}\verb|Assumption.add_assumes: |\isasep\isanewline%
|
|
189 |
\verb| cterm list -> Proof.context -> thm list * Proof.context| \\
|
20458
|
190 |
\indexml{Assumption.export}\verb|Assumption.export: bool -> Proof.context -> Proof.context -> thm -> thm| \\
|
|
191 |
\end{mldecls}
|
|
192 |
|
|
193 |
\begin{description}
|
|
194 |
|
20459
|
195 |
\item \verb|Assumption.export| represents arbitrary export
|
|
196 |
rules, which is any function of type \verb|bool -> cterm list -> thm -> thm|,
|
|
197 |
where the \verb|bool| indicates goal mode, and the \verb|cterm list| the collection of assumptions to be discharged
|
|
198 |
simultaneously.
|
20458
|
199 |
|
20459
|
200 |
\item \verb|Assumption.assume|~\isa{A} turns proposition \isa{A} into a raw assumption \isa{A\ {\isasymturnstile}\ A{\isacharprime}}, where the conclusion
|
|
201 |
\isa{A{\isacharprime}} is in HHF normal form.
|
20458
|
202 |
|
|
203 |
\item \verb|Assumption.add_assms|~\isa{e\ As} augments the context
|
20459
|
204 |
by assumptions \isa{As} with export rule \isa{e}. The
|
|
205 |
resulting facts are hypothetical theorems as produced by \verb|Assumption.assume|.
|
|
206 |
|
|
207 |
\item \verb|Assumption.add_assumes|~\isa{As} is a special case of
|
|
208 |
\verb|Assumption.add_assms| where the export rule performs \isa{{\isasymLongrightarrow}{\isacharunderscore}intro} or \isa{{\isacharhash}{\isasymLongrightarrow}{\isacharunderscore}intro}, depending on goal mode.
|
20458
|
209 |
|
|
210 |
\item \verb|Assumption.export|~\isa{is{\isacharunderscore}goal\ inner\ outer\ th}
|
|
211 |
exports result \isa{th} from the the \isa{inner} context
|
20459
|
212 |
back into the \isa{outer} one; \isa{is{\isacharunderscore}goal\ {\isacharequal}\ true} means
|
|
213 |
this is a goal context. The result is in HHF normal form. Note
|
|
214 |
that \verb|ProofContext.export| combines \verb|Variable.export|
|
|
215 |
and \verb|Assumption.export| in the canonical way.
|
20458
|
216 |
|
|
217 |
\end{description}%
|
|
218 |
\end{isamarkuptext}%
|
|
219 |
\isamarkuptrue%
|
|
220 |
%
|
|
221 |
\endisatagmlref
|
|
222 |
{\isafoldmlref}%
|
|
223 |
%
|
|
224 |
\isadelimmlref
|
|
225 |
%
|
|
226 |
\endisadelimmlref
|
|
227 |
%
|
20451
|
228 |
\isamarkupsection{Conclusions%
|
|
229 |
}
|
|
230 |
\isamarkuptrue%
|
|
231 |
%
|
|
232 |
\begin{isamarkuptext}%
|
|
233 |
FIXME%
|
|
234 |
\end{isamarkuptext}%
|
|
235 |
\isamarkuptrue%
|
|
236 |
%
|
20452
|
237 |
\isamarkupsection{Proof states \label{sec:isar-proof-state}%
|
18537
|
238 |
}
|
|
239 |
\isamarkuptrue%
|
|
240 |
%
|
|
241 |
\begin{isamarkuptext}%
|
|
242 |
FIXME
|
|
243 |
|
|
244 |
\glossary{Proof state}{The whole configuration of a structured proof,
|
|
245 |
consisting of a \seeglossary{proof context} and an optional
|
|
246 |
\seeglossary{structured goal}. Internally, an Isar proof state is
|
|
247 |
organized as a stack to accomodate block structure of proof texts.
|
|
248 |
For historical reasons, a low-level \seeglossary{tactical goal} is
|
|
249 |
occasionally called ``proof state'' as well.}
|
|
250 |
|
|
251 |
\glossary{Structured goal}{FIXME}
|
|
252 |
|
|
253 |
\glossary{Goal}{See \seeglossary{tactical goal} or \seeglossary{structured goal}. \norefpage}%
|
|
254 |
\end{isamarkuptext}%
|
|
255 |
\isamarkuptrue%
|
|
256 |
%
|
20451
|
257 |
\isamarkupsection{Proof methods%
|
18537
|
258 |
}
|
|
259 |
\isamarkuptrue%
|
|
260 |
%
|
|
261 |
\begin{isamarkuptext}%
|
|
262 |
FIXME%
|
|
263 |
\end{isamarkuptext}%
|
|
264 |
\isamarkuptrue%
|
|
265 |
%
|
|
266 |
\isamarkupsection{Attributes%
|
|
267 |
}
|
|
268 |
\isamarkuptrue%
|
|
269 |
%
|
|
270 |
\begin{isamarkuptext}%
|
20451
|
271 |
FIXME ?!%
|
18537
|
272 |
\end{isamarkuptext}%
|
|
273 |
\isamarkuptrue%
|
|
274 |
%
|
|
275 |
\isadelimtheory
|
|
276 |
%
|
|
277 |
\endisadelimtheory
|
|
278 |
%
|
|
279 |
\isatagtheory
|
|
280 |
\isacommand{end}\isamarkupfalse%
|
|
281 |
%
|
|
282 |
\endisatagtheory
|
|
283 |
{\isafoldtheory}%
|
|
284 |
%
|
|
285 |
\isadelimtheory
|
|
286 |
%
|
|
287 |
\endisadelimtheory
|
|
288 |
\isanewline
|
|
289 |
\end{isabellebody}%
|
|
290 |
%%% Local Variables:
|
|
291 |
%%% mode: latex
|
|
292 |
%%% TeX-master: "root"
|
|
293 |
%%% End:
|