2208
|
1 |
(* How to change the notation for \<lbrakk> \<rbrakk> meta-level implications? *)
|
2195
|
2 |
|
1975
b1281a0051ae
added stub for quotient paper; call with isabelle make qpaper
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
3 |
(*<*)
|
b1281a0051ae
added stub for quotient paper; call with isabelle make qpaper
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
4 |
theory Paper
|
2183
|
5 |
imports "Quotient"
|
1975
b1281a0051ae
added stub for quotient paper; call with isabelle make qpaper
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
6 |
"LaTeXsugar"
|
2186
|
7 |
"../Nominal/FSet"
|
1975
b1281a0051ae
added stub for quotient paper; call with isabelle make qpaper
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
8 |
begin
|
1994
|
9 |
|
|
10 |
notation (latex output)
|
2217
|
11 |
rel_conj ("_ OOO _" [53, 53] 52) and
|
|
12 |
"op -->" (infix "\<rightarrow>" 100) and
|
|
13 |
"==>" (infix "\<Rightarrow>" 100) and
|
2224
|
14 |
fun_map ("_ \<^raw:\mbox{\tt{---\textgreater}}> _" 51) and
|
|
15 |
fun_rel ("_ \<^raw:\mbox{\tt{===\textgreater}}> _" 51) and
|
2217
|
16 |
list_eq (infix "\<approx>" 50) and (* Not sure if we want this notation...? *)
|
2223
|
17 |
fempty ("\<emptyset>") and
|
|
18 |
funion ("_ \<union> _") and
|
|
19 |
finsert ("{_} \<union> _") and
|
2221
|
20 |
Cons ("_::_") and
|
|
21 |
concat ("flat") and
|
2223
|
22 |
fconcat ("\<Union>")
|
2220
|
23 |
|
2217
|
24 |
|
1994
|
25 |
|
2182
|
26 |
ML {*
|
|
27 |
fun nth_conj n (_, r) = nth (HOLogic.dest_conj r) n;
|
|
28 |
fun style_lhs_rhs proj = Scan.succeed (fn ctxt => fn t =>
|
|
29 |
let
|
|
30 |
val concl =
|
|
31 |
Object_Logic.drop_judgment (ProofContext.theory_of ctxt) (Logic.strip_imp_concl t)
|
|
32 |
in
|
|
33 |
case concl of (_ $ l $ r) => proj (l, r)
|
|
34 |
| _ => error ("Binary operator expected in term: " ^ Syntax.string_of_term ctxt concl)
|
|
35 |
end);
|
|
36 |
*}
|
|
37 |
setup {*
|
|
38 |
Term_Style.setup "rhs1" (style_lhs_rhs (nth_conj 0)) #>
|
|
39 |
Term_Style.setup "rhs2" (style_lhs_rhs (nth_conj 1)) #>
|
|
40 |
Term_Style.setup "rhs3" (style_lhs_rhs (nth_conj 2))
|
|
41 |
*}
|
1975
b1281a0051ae
added stub for quotient paper; call with isabelle make qpaper
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
42 |
(*>*)
|
b1281a0051ae
added stub for quotient paper; call with isabelle make qpaper
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
43 |
|
b1281a0051ae
added stub for quotient paper; call with isabelle make qpaper
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
44 |
section {* Introduction *}
|
b1281a0051ae
added stub for quotient paper; call with isabelle make qpaper
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
45 |
|
2102
200954544cae
added some of the quotient literature; a bit more to the qpaper
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
46 |
text {*
|
2205
|
47 |
\begin{flushright}
|
|
48 |
{\em ``Not using a [quotient] package has its advantages: we do not have to\\
|
|
49 |
collect all the theorems we shall ever want into one giant list;''}\\
|
2213
|
50 |
Larry Paulson \cite{Paulson06}
|
2205
|
51 |
\end{flushright}\smallskip
|
2103
|
52 |
|
|
53 |
\noindent
|
2220
|
54 |
Isabelle is a popular generic theorem prover in which many logics can be
|
2214
|
55 |
implemented. The most widely used one, however, is Higher-Order Logic
|
|
56 |
(HOL). This logic consists of a small number of axioms and inference rules
|
|
57 |
over a simply-typed term-language. Safe reasoning in HOL is ensured by two
|
|
58 |
very restricted mechanisms for extending the logic: one is the definition of
|
|
59 |
new constants in terms of existing ones; the other is the introduction of
|
|
60 |
new types by identifying non-empty subsets in existing types. It is well
|
2223
|
61 |
understood how to use both mechanisms for dealing with quotient
|
2220
|
62 |
constructions in HOL (see \cite{Homeier05,Paulson06}). For example the
|
|
63 |
integers in Isabelle/HOL are constructed by a quotient construction over the
|
|
64 |
type @{typ "nat \<times> nat"} and the equivalence relation
|
2102
200954544cae
added some of the quotient literature; a bit more to the qpaper
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
65 |
|
2225
|
66 |
@{text [display, indent=10] "(n\<^isub>1, n\<^isub>2) \<approx> (m\<^isub>1, m\<^isub>2) \<equiv> n\<^isub>1 + m\<^isub>2 = m\<^isub>1 + n\<^isub>2"}
|
2102
200954544cae
added some of the quotient literature; a bit more to the qpaper
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
67 |
|
200954544cae
added some of the quotient literature; a bit more to the qpaper
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
68 |
\noindent
|
2217
|
69 |
This constructions yields the new type @{typ int} and definitions for @{text
|
2220
|
70 |
"0"} and @{text "1"} of type @{typ int} can be given in terms of pairs of
|
|
71 |
natural numbers (namely @{text "(0, 0)"} and @{text "(1, 0)"}). Operations
|
|
72 |
such as @{text "add"} with type @{typ "int \<Rightarrow> int \<Rightarrow> int"} can be defined in
|
|
73 |
terms of operations on pairs of natural numbers (namely @{text
|
2224
|
74 |
"add_pair (n\<^isub>1, m\<^isub>1) (n\<^isub>2,
|
2222
|
75 |
m\<^isub>2) \<equiv> (n\<^isub>1 + n\<^isub>2, m\<^isub>1 + m\<^isub>2)"}).
|
|
76 |
Similarly one can construct the type of finite sets, written @{term "\<alpha> fset"},
|
2223
|
77 |
by quotienting the type @{text "\<alpha> list"} according to the equivalence relation
|
2103
|
78 |
|
2224
|
79 |
@{text [display, indent=10] "xs \<approx> ys \<equiv> (\<forall>x. memb x xs \<longleftrightarrow> memb x ys)"}
|
2103
|
80 |
|
|
81 |
\noindent
|
2224
|
82 |
which states that two lists are equivalent if every element in one list is
|
|
83 |
also member in the other. The empty finite set, written @{term "{||}"}, can
|
|
84 |
then be defined as the empty list and the union of two finite sets, written
|
|
85 |
@{text "\<union>"}, as list append.
|
2220
|
86 |
|
|
87 |
An area where quotients are ubiquitous is reasoning about programming language
|
|
88 |
calculi. A simple example is the lambda-calculus, whose ``raw'' terms are defined as
|
|
89 |
|
|
90 |
@{text [display, indent=10] "t ::= x | t t | \<lambda>x.t"}
|
2217
|
91 |
|
2220
|
92 |
\noindent
|
2222
|
93 |
The problem with this definition arises when one attempts to
|
|
94 |
prove formally, for example, the substitution lemma \cite{Barendregt81} by induction
|
|
95 |
over the structure of terms. This can be fiendishly complicated (see
|
2220
|
96 |
\cite[Pages 94--104]{CurryFeys58} for some ``rough'' sketches of a proof
|
|
97 |
about ``raw'' lambda-terms). In contrast, if we reason about
|
|
98 |
$\alpha$-equated lambda-terms, that means terms quotient according to
|
2223
|
99 |
$\alpha$-equivalence, then the reasoning infrastructure provided,
|
|
100 |
for example, by Nominal Isabelle \cite{UrbanKaliszyk11} makes the formal
|
2222
|
101 |
proof of the substitution lemma almost trivial.
|
2220
|
102 |
|
|
103 |
The difficulty is that in order to be able to reason about integers, finite
|
2221
|
104 |
sets or $\alpha$-equated lambda-terms one needs to establish a reasoning
|
2220
|
105 |
infrastructure by transferring, or \emph{lifting}, definitions and theorems
|
|
106 |
from the ``raw'' type @{typ "nat \<times> nat"} to the quotient type @{typ int}
|
|
107 |
(similarly for finite sets and $\alpha$-equated lambda-terms). This lifting
|
2222
|
108 |
usually requires a \emph{lot} of tedious reasoning effort \cite{Paulson06}.
|
2223
|
109 |
It is feasible to to this work manually, if one has only a few quotient
|
|
110 |
constructions at hand. But if they have to be done over and over again as in
|
2222
|
111 |
Nominal Isabelle, then manual reasoning is not an option.
|
2221
|
112 |
|
2223
|
113 |
The purpose of a \emph{quotient package} is to ease the lifting of theorems
|
|
114 |
and automate the definitions and reasoning as much as possible. In the
|
|
115 |
context of HOL, there have been a few quotient packages already
|
|
116 |
\cite{harrison-thesis,Slotosch97}. The most notable is the one by Homeier
|
|
117 |
\cite{Homeier05} implemented in HOL4. The fundamental construction these
|
|
118 |
quotient packages perform can be illustrated by the following picture:
|
2217
|
119 |
|
|
120 |
\begin{center}
|
2220
|
121 |
\mbox{}\hspace{20mm}\begin{tikzpicture}
|
|
122 |
%%\draw[step=2mm] (-4,-1) grid (4,1);
|
|
123 |
|
|
124 |
\draw[very thick] (0.7,0.3) circle (4.85mm);
|
|
125 |
\draw[rounded corners=1mm, very thick] ( 0.0,-0.9) rectangle ( 1.8, 0.9);
|
|
126 |
\draw[rounded corners=1mm, very thick] (-1.95,0.8) rectangle (-2.9,-0.195);
|
|
127 |
|
|
128 |
\draw (-2.0, 0.8) -- (0.7,0.8);
|
|
129 |
\draw (-2.0,-0.195) -- (0.7,-0.195);
|
2103
|
130 |
|
2220
|
131 |
\draw ( 0.7, 0.23) node {\begin{tabular}{@ {}c@ {}}equiv-\\[-1mm]clas.\end{tabular}};
|
|
132 |
\draw (-2.45, 0.35) node {\begin{tabular}{@ {}c@ {}}new\\[-1mm]type\end{tabular}};
|
|
133 |
\draw (1.8, 0.35) node[right=-0.1mm]
|
2224
|
134 |
{\begin{tabular}{@ {}l@ {}}existing\\[-1mm] type\\ (sets of raw elements)\end{tabular}};
|
2220
|
135 |
\draw (0.9, -0.55) node {\begin{tabular}{@ {}l@ {}}non-empty\\[-1mm]subset\end{tabular}};
|
|
136 |
|
|
137 |
\draw[->, very thick] (-1.8, 0.36) -- (-0.1,0.36);
|
|
138 |
\draw[<-, very thick] (-1.8, 0.16) -- (-0.1,0.16);
|
2221
|
139 |
\draw (-0.95, 0.26) node[above=0.4mm] {@{text Rep}};
|
|
140 |
\draw (-0.95, 0.26) node[below=0.4mm] {@{text Abs}};
|
2220
|
141 |
|
|
142 |
\end{tikzpicture}
|
|
143 |
\end{center}
|
2217
|
144 |
|
2221
|
145 |
\noindent
|
2223
|
146 |
The starting point is an existing type over which an equivalence relation
|
|
147 |
given by the user is defined. With this input the package introduces a new
|
2224
|
148 |
type that comes with associated \emph{abstraction} and \emph{representation}
|
2223
|
149 |
functions, written @{text Abs} and @{text Rep}. These functions relate
|
2224
|
150 |
elements in the existing type to ones in the new type and vice versa; they
|
|
151 |
can be uniquely identified by their type. For example for the integer
|
|
152 |
quotient construction the types of @{text Abs} and @{text Rep} are
|
|
153 |
|
|
154 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
|
155 |
@{text "Abs::nat \<times> nat \<Rightarrow> int"}\hspace{10mm}@{text "Rep::int \<Rightarrow> nat \<times> nat"}
|
|
156 |
\end{isabelle}
|
|
157 |
|
|
158 |
\noindent
|
|
159 |
However we often leave this typing information implicit for better
|
|
160 |
readability. Every abstraction and representation function represents an
|
|
161 |
isomorphism between the non-empty subset and elements in the new type. They
|
|
162 |
are necessary for making definitions involving the new type. For example
|
|
163 |
@{text "0"} and @{text "1"} of type @{typ int} can be defined as
|
|
164 |
|
2221
|
165 |
|
|
166 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
|
167 |
@{text "0 \<equiv> Abs (0, 0)"}\hspace{10mm}@{text "1 \<equiv> Abs (1, 0)"}
|
|
168 |
\end{isabelle}
|
|
169 |
|
|
170 |
\noindent
|
2224
|
171 |
Slightly more complicated is the definition of @{text "add"} having type
|
2222
|
172 |
@{typ "int \<Rightarrow> int \<Rightarrow> int"}. Its definition is as follows
|
2221
|
173 |
|
2224
|
174 |
@{text [display, indent=10] "add n m \<equiv> Abs (add_pair (Rep n) (Rep m))"}
|
2221
|
175 |
|
|
176 |
\noindent
|
2224
|
177 |
where we take the representation of the arguments @{text n} and @{text m},
|
|
178 |
add them according to @{text "add_pair"} and then take the
|
2221
|
179 |
abstraction of the result. This is all straightforward and the existing
|
|
180 |
quotient packages can deal with such definitions. But what is surprising
|
2223
|
181 |
that none of them can deal with slightly more complicated definitions involving
|
2221
|
182 |
\emph{compositions} of quotients. Such compositions are needed for example
|
2224
|
183 |
in case of quotienting lists and the operator that flattens lists of lists, defined
|
|
184 |
as follows
|
2102
200954544cae
added some of the quotient literature; a bit more to the qpaper
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
185 |
|
2220
|
186 |
@{thm [display, indent=10] concat.simps(1) concat.simps(2)[no_vars]}
|
2183
|
187 |
|
2103
|
188 |
\noindent
|
2221
|
189 |
We expect that the corresponding operator on finite sets, written @{term "fconcat"},
|
|
190 |
behaves as follows:
|
2188
|
191 |
|
2220
|
192 |
@{thm [display, indent=10] fconcat_empty[no_vars] fconcat_insert[no_vars]}
|
2102
200954544cae
added some of the quotient literature; a bit more to the qpaper
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
193 |
|
2103
|
194 |
\noindent
|
2223
|
195 |
The quotient package should provide us with a definition for @{text "\<Union>"} in
|
2224
|
196 |
terms of @{text flat}, @{text Rep} and @{text Abs} (the latter two having
|
|
197 |
the type @{text "\<alpha> fset \<Rightarrow> \<alpha> list"} and @{text "\<alpha> list \<Rightarrow> \<alpha> fset"},
|
|
198 |
respectively). The problem is that the method is used in the existing quotient
|
|
199 |
packages of just taking the representation of the arguments and then take
|
|
200 |
the abstraction of the result is \emph{not} enough. The reason is that case in case
|
|
201 |
of @{text "\<Union>"} we obtain the incorrect definition
|
|
202 |
|
|
203 |
@{text [display, indent=10] "\<Union> S \<equiv> Abs (flat (Rep S))"}
|
2221
|
204 |
|
2224
|
205 |
\noindent
|
|
206 |
where the right-hand side is not even typable! This problem can be remedied in the
|
|
207 |
existing quotient packages by introducing an intermediate step and reasoning
|
|
208 |
about faltening of lists of finite sets. However, this remedy is rather
|
|
209 |
cumbersome and inelegant in light of our work, which can deal with such
|
|
210 |
definitions directly. The solution is that we need to build aggregate
|
|
211 |
representation and abstraction functions, which in case of @{text "\<Union>"}
|
|
212 |
generate the following definition
|
|
213 |
|
|
214 |
@{text [display, indent=10] "\<Union> S \<equiv> Abs (flat ((map Rep \<circ> Rep) S))"}
|
2221
|
215 |
|
|
216 |
\noindent
|
2223
|
217 |
where @{term map} is the usual mapping function for lists. In this paper we
|
2224
|
218 |
will present a formal definition of our aggregate abstraction and
|
2223
|
219 |
representation functions (this definition was omitted in \cite{Homeier05}).
|
2224
|
220 |
They generate definitions, like the one above for @{text "\<Union>"},
|
2223
|
221 |
according to the type of the ``raw'' constant and the type
|
2224
|
222 |
of the quotient constant. This means we also have to extend the notions
|
|
223 |
of \emph{respectfulness} and \emph{preservation} from Homeier
|
|
224 |
\cite{Homeier05}.
|
2223
|
225 |
|
2224
|
226 |
We will also address the criticism by Paulson \cite{Paulson06} cited at the
|
|
227 |
beginning of this section about having to collect theorems that are lifted from the raw
|
|
228 |
level to the quotient level. Our quotient package is modular so that it
|
|
229 |
allows to lift single theorems separately. This has the advantage for the
|
|
230 |
user to develop a formal theory interactively an a natural progression. A
|
|
231 |
pleasing result of the modularity is also that we are able to clearly
|
|
232 |
specify what needs to be done in the lifting process (this was only hinted at in
|
|
233 |
\cite{Homeier05} and implemented as a ``rough recipe'' in ML-code).
|
|
234 |
|
|
235 |
The paper is organised as follows \ldots
|
2102
200954544cae
added some of the quotient literature; a bit more to the qpaper
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
236 |
*}
|
1975
b1281a0051ae
added stub for quotient paper; call with isabelle make qpaper
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
237 |
|
b1281a0051ae
added stub for quotient paper; call with isabelle make qpaper
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
238 |
|
1978
|
239 |
|
2224
|
240 |
section {* Preliminaries and General Quotient\label{sec:prelims} *}
|
1978
|
241 |
|
2182
|
242 |
|
|
243 |
|
1978
|
244 |
text {*
|
2182
|
245 |
In this section we present the definitions of a quotient that follow
|
|
246 |
those by Homeier, the proofs can be found there.
|
|
247 |
|
|
248 |
\begin{definition}[Quotient]
|
|
249 |
A relation $R$ with an abstraction function $Abs$
|
|
250 |
and a representation function $Rep$ is a \emph{quotient}
|
|
251 |
if and only if:
|
1978
|
252 |
|
2182
|
253 |
\begin{enumerate}
|
|
254 |
\item @{thm (rhs1) Quotient_def[of "R", no_vars]}
|
|
255 |
\item @{thm (rhs2) Quotient_def[of "R", no_vars]}
|
|
256 |
\item @{thm (rhs3) Quotient_def[of "R", no_vars]}
|
|
257 |
\end{enumerate}
|
|
258 |
|
|
259 |
\end{definition}
|
1978
|
260 |
|
2188
|
261 |
\begin{definition}[Relation map and function map]\\
|
2190
|
262 |
@{thm fun_rel_def[of "R1" "R2", no_vars]}\\
|
2182
|
263 |
@{thm fun_map_def[no_vars]}
|
|
264 |
\end{definition}
|
|
265 |
|
|
266 |
The main theorems for building higher order quotients is:
|
|
267 |
\begin{lemma}[Function Quotient]
|
|
268 |
If @{thm (prem 1) fun_quotient[no_vars]} and @{thm (prem 2) fun_quotient[no_vars]}
|
|
269 |
then @{thm (concl) fun_quotient[no_vars]}
|
|
270 |
\end{lemma}
|
|
271 |
|
1978
|
272 |
*}
|
|
273 |
|
2195
|
274 |
subsection {* Higher Order Logic *}
|
|
275 |
|
|
276 |
text {*
|
|
277 |
|
|
278 |
Types:
|
|
279 |
\begin{eqnarray}\nonumber
|
|
280 |
@{text "\<sigma> ::="} & @{text "\<alpha>"} & \textrm{(type variable)} \\ \nonumber
|
|
281 |
@{text "|"} & @{text "(\<sigma>,\<dots>,\<sigma>)\<kappa>"} & \textrm{(type construction)}
|
|
282 |
\end{eqnarray}
|
|
283 |
|
|
284 |
Terms:
|
|
285 |
\begin{eqnarray}\nonumber
|
|
286 |
@{text "t ::="} & @{text "x\<^isup>\<sigma>"} & \textrm{(variable)} \\ \nonumber
|
|
287 |
@{text "|"} & @{text "c\<^isup>\<sigma>"} & \textrm{(constant)} \\ \nonumber
|
|
288 |
@{text "|"} & @{text "t t"} & \textrm{(application)} \\ \nonumber
|
|
289 |
@{text "|"} & @{text "\<lambda>x\<^isup>\<sigma>. t"} & \textrm{(abstraction)} \\ \nonumber
|
|
290 |
\end{eqnarray}
|
|
291 |
|
|
292 |
*}
|
|
293 |
|
2224
|
294 |
section {* Lifting of Definitions *}
|
1978
|
295 |
|
2188
|
296 |
(* Say more about containers? *)
|
2182
|
297 |
|
1978
|
298 |
text {*
|
2182
|
299 |
|
2188
|
300 |
To define a constant on the lifted type, an aggregate abstraction
|
|
301 |
function is applied to the raw constant. Below we describe the operation
|
|
302 |
that generates
|
|
303 |
an aggregate @{term "Abs"} or @{term "Rep"} function given the
|
|
304 |
compound raw type and the compound quotient type.
|
|
305 |
This operation will also be used in translations of theorem statements
|
|
306 |
and in the lifting procedure.
|
|
307 |
|
|
308 |
The operation is additionally able to descend into types for which
|
|
309 |
maps are known. Such maps for most common types (list, pair, sum,
|
2195
|
310 |
option, \ldots) are described in Homeier, and we assume that @{text "map"}
|
|
311 |
is the function that returns a map for a given type. Then REP/ABS is defined
|
|
312 |
as follows:
|
2182
|
313 |
|
|
314 |
\begin{itemize}
|
2195
|
315 |
\item @{text "ABS(\<alpha>\<^isub>1, \<alpha>\<^isub>2)"} = @{text "id"}
|
|
316 |
\item @{text "REP(\<alpha>\<^isub>1, \<alpha>\<^isub>2)"} = @{text "id"}
|
|
317 |
\item @{text "ABS(\<sigma>, \<sigma>)"} = @{text "id"}
|
|
318 |
\item @{text "REP(\<sigma>, \<sigma>)"} = @{text "id"}
|
2208
|
319 |
\item @{text "ABS(\<sigma>\<^isub>1\<rightarrow>\<sigma>\<^isub>2,\<tau>\<^isub>1\<rightarrow>\<tau>\<^isub>2)"} = @{text "REP(\<sigma>\<^isub>1,\<tau>\<^isub>1) \<longrightarrow> ABS(\<sigma>\<^isub>2,\<tau>\<^isub>2)"}
|
|
320 |
\item @{text "REP(\<sigma>\<^isub>1\<rightarrow>\<sigma>\<^isub>2,\<tau>\<^isub>1\<rightarrow>\<tau>\<^isub>2)"} = @{text "ABS(\<sigma>\<^isub>1,\<tau>\<^isub>1) \<longrightarrow> REP(\<sigma>\<^isub>2,\<tau>\<^isub>2)"}
|
2195
|
321 |
\item @{text "ABS((\<sigma>\<^isub>1,\<dots>,\<sigma>\<^isub>n))\<kappa>, (\<tau>\<^isub>1,\<dots>,\<tau>\<^isub>n))\<kappa>)"} = @{text "(map \<kappa>) (ABS(\<sigma>\<^isub>1,\<tau>\<^isub>1)) \<dots> (ABS(\<sigma>\<^isub>n,\<tau>\<^isub>n))"}
|
|
322 |
\item @{text "REP((\<sigma>\<^isub>1,\<dots>,\<sigma>\<^isub>n))\<kappa>, (\<tau>\<^isub>1,\<dots>,\<tau>\<^isub>n))\<kappa>)"} = @{text "(map \<kappa>) (REP(\<sigma>\<^isub>1,\<tau>\<^isub>1)) \<dots> (REP(\<sigma>\<^isub>n,\<tau>\<^isub>n))"}
|
|
323 |
\item @{text "ABS((\<sigma>\<^isub>1,\<dots>,\<sigma>\<^isub>n))\<kappa>\<^isub>1, (\<tau>\<^isub>1,\<dots>,\<tau>\<^isub>m))\<kappa>\<^isub>2)"} = @{text "Abs_\<kappa>\<^isub>2 \<circ> (map \<kappa>\<^isub>1) (ABS(\<rho>\<^isub>1,\<nu>\<^isub>1) \<dots> (ABS(\<rho>\<^isub>p,\<nu>\<^isub>p)"} provided @{text "\<eta> \<kappa>\<^isub>2 = (\<alpha>\<^isub>1\<dots>\<alpha>\<^isub>p)\<kappa>\<^isub>1 \<and> \<exists>s. s(\<sigma>s\<kappa>\<^isub>1)=\<rho>s\<kappa>\<^isub>1 \<and> s(\<tau>s\<kappa>\<^isub>2)=\<nu>s\<kappa>\<^isub>2"}
|
|
324 |
\item @{text "REP((\<sigma>\<^isub>1,\<dots>,\<sigma>\<^isub>n))\<kappa>\<^isub>1, (\<tau>\<^isub>1,\<dots>,\<tau>\<^isub>m))\<kappa>\<^isub>2)"} = @{text "(map \<kappa>\<^isub>1) (REP(\<rho>\<^isub>1,\<nu>\<^isub>1) \<dots> (REP(\<rho>\<^isub>p,\<nu>\<^isub>p) \<circ> Rep_\<kappa>\<^isub>2"} provided @{text "\<eta> \<kappa>\<^isub>2 = (\<alpha>\<^isub>1\<dots>\<alpha>\<^isub>p)\<kappa>\<^isub>1 \<and> \<exists>s. s(\<sigma>s\<kappa>\<^isub>1)=\<rho>s\<kappa>\<^isub>1 \<and> s(\<tau>s\<kappa>\<^isub>2)=\<nu>s\<kappa>\<^isub>2"}
|
2182
|
325 |
\end{itemize}
|
|
326 |
|
2195
|
327 |
Apart from the last 2 points the definition is same as the one implemented in
|
2208
|
328 |
in Homeier's HOL package. Adding composition in last two cases is necessary
|
|
329 |
for compositional quotients. We ilustrate the different behaviour of the
|
|
330 |
definition by showing the derived definition of @{term fconcat}:
|
2182
|
331 |
|
2188
|
332 |
@{thm fconcat_def[no_vars]}
|
|
333 |
|
|
334 |
The aggregate @{term Abs} function takes a finite set of finite sets
|
|
335 |
and applies @{term "map rep_fset"} composed with @{term rep_fset} to
|
|
336 |
its input, obtaining a list of lists, passes the result to @{term concat}
|
|
337 |
obtaining a list and applies @{term abs_fset} obtaining the composed
|
|
338 |
finite set.
|
|
339 |
*}
|
|
340 |
|
|
341 |
subsection {* Respectfulness *}
|
|
342 |
|
|
343 |
text {*
|
|
344 |
|
|
345 |
A respectfulness lemma for a constant states that the equivalence
|
|
346 |
class returned by this constant depends only on the equivalence
|
2207
|
347 |
classes of the arguments applied to the constant. To automatically
|
|
348 |
lift a theorem that talks about a raw constant, to a theorem about
|
|
349 |
the quotient type a respectfulness theorem is required.
|
|
350 |
|
|
351 |
A respectfulness condition for a constant can be expressed in
|
|
352 |
terms of an aggregate relation between the constant and itself,
|
|
353 |
for example the respectfullness for @{term "append"}
|
2188
|
354 |
can be stated as:
|
|
355 |
|
2190
|
356 |
@{thm [display] append_rsp[no_vars]}
|
2182
|
357 |
|
2190
|
358 |
\noindent
|
2208
|
359 |
Which after unfolding @{term "op \<Longrightarrow>"} is equivalent to:
|
2188
|
360 |
|
2190
|
361 |
@{thm [display] append_rsp_unfolded[no_vars]}
|
2188
|
362 |
|
2207
|
363 |
An aggregate relation is defined in terms of relation composition,
|
|
364 |
so we define it first:
|
2188
|
365 |
|
|
366 |
\begin{definition}[Composition of Relations]
|
2190
|
367 |
@{abbrev "rel_conj R1 R2"} where @{text OO} is the predicate
|
|
368 |
composition @{thm pred_compI[no_vars]}
|
2188
|
369 |
\end{definition}
|
|
370 |
|
2207
|
371 |
The aggregate relation for an aggregate raw type and quotient type
|
|
372 |
is defined as:
|
2188
|
373 |
|
|
374 |
\begin{itemize}
|
2207
|
375 |
\item @{text "REL(\<alpha>\<^isub>1, \<alpha>\<^isub>2)"} = @{text "op ="}
|
|
376 |
\item @{text "REL(\<sigma>, \<sigma>)"} = @{text "op ="}
|
|
377 |
\item @{text "REL((\<sigma>\<^isub>1,\<dots>,\<sigma>\<^isub>n))\<kappa>, (\<tau>\<^isub>1,\<dots>,\<tau>\<^isub>n))\<kappa>)"} = @{text "(rel \<kappa>) (REL(\<sigma>\<^isub>1,\<tau>\<^isub>1)) \<dots> (REL(\<sigma>\<^isub>n,\<tau>\<^isub>n))"}
|
|
378 |
\item @{text "REL((\<sigma>\<^isub>1,\<dots>,\<sigma>\<^isub>n))\<kappa>\<^isub>1, (\<tau>\<^isub>1,\<dots>,\<tau>\<^isub>m))\<kappa>\<^isub>2)"} = @{text "(rel \<kappa>\<^isub>1) (REL(\<rho>\<^isub>1,\<nu>\<^isub>1) \<dots> (REL(\<rho>\<^isub>p,\<nu>\<^isub>p) OOO Eqv_\<kappa>\<^isub>2"} provided @{text "\<eta> \<kappa>\<^isub>2 = (\<alpha>\<^isub>1\<dots>\<alpha>\<^isub>p)\<kappa>\<^isub>1 \<and> \<exists>s. s(\<sigma>s\<kappa>\<^isub>1)=\<rho>s\<kappa>\<^isub>1 \<and> s(\<tau>s\<kappa>\<^isub>2)=\<nu>s\<kappa>\<^isub>2"}
|
2189
|
379 |
|
2188
|
380 |
\end{itemize}
|
|
381 |
|
2207
|
382 |
Again, the last case is novel, so lets look at the example of
|
|
383 |
respectfullness for @{term concat}. The statement according to
|
|
384 |
the definition above is:
|
2190
|
385 |
|
|
386 |
@{thm [display] concat_rsp[no_vars]}
|
2189
|
387 |
|
2190
|
388 |
\noindent
|
|
389 |
By unfolding the definition of relation composition and relation map
|
|
390 |
we can see the equivalent statement just using the primitive list
|
|
391 |
equivalence relation:
|
|
392 |
|
|
393 |
@{thm [display] concat_rsp_unfolded[of "a" "a'" "b'" "b", no_vars]}
|
2189
|
394 |
|
2190
|
395 |
The statement reads that, for any lists of lists @{term a} and @{term b}
|
|
396 |
if there exist intermediate lists of lists @{term "a'"} and @{term "b'"}
|
|
397 |
such that each element of @{term a} is in the relation with an appropriate
|
|
398 |
element of @{term a'}, @{term a'} is in relation with @{term b'} and each
|
|
399 |
element of @{term b'} is in relation with the appropriate element of
|
|
400 |
@{term b}.
|
2189
|
401 |
|
|
402 |
*}
|
|
403 |
|
|
404 |
subsection {* Preservation *}
|
|
405 |
|
2190
|
406 |
text {*
|
|
407 |
To be able to lift theorems that talk about constants that are not
|
|
408 |
lifted but whose type changes when lifting is performed additionally
|
|
409 |
preservation theorems are needed.
|
2196
|
410 |
|
|
411 |
To lift theorems that talk about insertion in lists of lifted types
|
|
412 |
we need to know that for any quotient type with the abstraction and
|
|
413 |
representation functions @{text "Abs"} and @{text Rep} we have:
|
|
414 |
|
|
415 |
@{thm [display] (concl) cons_prs[no_vars]}
|
|
416 |
|
|
417 |
This is not enough to lift theorems that talk about quotient compositions.
|
|
418 |
For some constants (for example empty list) it is possible to show a
|
|
419 |
general compositional theorem, but for @{term "op #"} it is necessary
|
|
420 |
to show that it respects the particular quotient type:
|
|
421 |
|
|
422 |
@{thm [display] insert_preserve2[no_vars]}
|
2190
|
423 |
*}
|
|
424 |
|
2191
|
425 |
subsection {* Composition of Quotient theorems *}
|
2189
|
426 |
|
2191
|
427 |
text {*
|
|
428 |
Given two quotients, one of which quotients a container, and the
|
|
429 |
other quotients the type in the container, we can write the
|
2193
|
430 |
composition of those quotients. To compose two quotient theorems
|
2207
|
431 |
we compose the relations with relation composition as defined above
|
|
432 |
and the abstraction and relation functions are the ones of the sub
|
|
433 |
quotients composed with the usual function composition.
|
|
434 |
The @{term "Rep"} and @{term "Abs"} functions that we obtain agree
|
|
435 |
with the definition of aggregate Abs/Rep functions and the
|
2193
|
436 |
relation is the same as the one given by aggregate relations.
|
|
437 |
This becomes especially interesting
|
2191
|
438 |
when we compose the quotient with itself, as there is no simple
|
|
439 |
intermediate step.
|
|
440 |
|
2193
|
441 |
Lets take again the example of @{term concat}. To be able to lift
|
2207
|
442 |
theorems that talk about it we provide the composition quotient
|
|
443 |
theorems, which then lets us perform the lifting procedure in an
|
|
444 |
unchanged way:
|
2188
|
445 |
|
2190
|
446 |
@{thm [display] quotient_compose_list[no_vars]}
|
2192
|
447 |
*}
|
|
448 |
|
2191
|
449 |
|
|
450 |
section {* Lifting Theorems *}
|
1978
|
451 |
|
2194
|
452 |
text {*
|
|
453 |
The core of the quotient package takes an original theorem that
|
|
454 |
talks about the raw types, and the statement of the theorem that
|
|
455 |
it is supposed to produce. This is different from other existing
|
2207
|
456 |
quotient packages, where only the raw theorems were necessary.
|
2194
|
457 |
We notice that in some cases only some occurrences of the raw
|
|
458 |
types need to be lifted. This is for example the case in the
|
|
459 |
new Nominal package, where a raw datatype that talks about
|
|
460 |
pairs of natural numbers or strings (being lists of characters)
|
|
461 |
should not be changed to a quotient datatype with constructors
|
|
462 |
taking integers or finite sets of characters. To simplify the
|
|
463 |
use of the quotient package we additionally provide an automated
|
|
464 |
statement translation mechanism that replaces occurrences of
|
|
465 |
types that match given quotients by appropriate lifted types.
|
|
466 |
|
|
467 |
Lifting the theorems is performed in three steps. In the following
|
|
468 |
we call these steps \emph{regularization}, \emph{injection} and
|
|
469 |
\emph{cleaning} following the names used in Homeier's HOL
|
2197
|
470 |
implementation.
|
2193
|
471 |
|
2197
|
472 |
We first define the statement of the regularized theorem based
|
|
473 |
on the original theorem and the goal theorem. Then we define
|
|
474 |
the statement of the injected theorem, based on the regularized
|
2208
|
475 |
theorem and the goal. We then show the 3 proofs, as all three
|
2197
|
476 |
can be performed independently from each other.
|
2193
|
477 |
|
2194
|
478 |
*}
|
1994
|
479 |
|
2197
|
480 |
subsection {* Regularization and Injection statements *}
|
1994
|
481 |
|
|
482 |
text {*
|
2197
|
483 |
|
2207
|
484 |
We first define the function @{text REG}, which takes the statements
|
|
485 |
of the raw theorem and the lifted theorem (both as terms) and
|
|
486 |
returns the statement of the regularized version. The intuition
|
|
487 |
behind this function is that it replaces quantifiers and
|
|
488 |
abstractions involving raw types by bounded ones, and equalities
|
|
489 |
involving raw types are replaced by appropriate aggregate
|
|
490 |
relations. It is defined as follows:
|
1994
|
491 |
|
2197
|
492 |
\begin{itemize}
|
2198
|
493 |
\item @{text "REG (\<lambda>x : \<sigma>. t, \<lambda>x : \<sigma>. s) = \<lambda>x : \<sigma>. REG (t, s)"}
|
|
494 |
\item @{text "REG (\<lambda>x : \<sigma>. t, \<lambda>x : \<tau>. s) = \<lambda>x : \<sigma> \<in> Res (REL (\<sigma>, \<tau>)). REG (t, s)"}
|
|
495 |
\item @{text "REG (\<forall>x : \<sigma>. t, \<forall>x : \<sigma>. s) = \<forall>x : \<sigma>. REG (t, s)"}
|
|
496 |
\item @{text "REG (\<forall>x : \<sigma>. t, \<forall>x : \<tau>. s) = \<forall>x : \<sigma> \<in> Res (REL (\<sigma>, \<tau>)). REG (t, s)"}
|
2197
|
497 |
\item @{text "REG ((op =) : \<sigma>, (op =) : \<sigma>) = (op =) : \<sigma>"}
|
|
498 |
\item @{text "REG ((op =) : \<sigma>, (op =) : \<tau>) = REL (\<sigma>, \<tau>) : \<sigma>"}
|
|
499 |
\item @{text "REG (t\<^isub>1 t\<^isub>2, s\<^isub>1 s\<^isub>2) = REG (t\<^isub>1, s\<^isub>1) REG (t\<^isub>2, s\<^isub>2)"}
|
2198
|
500 |
\item @{text "REG (v\<^isub>1, v\<^isub>2) = v\<^isub>1"}
|
|
501 |
\item @{text "REG (c\<^isub>1, c\<^isub>2) = c\<^isub>1"}
|
2197
|
502 |
\end{itemize}
|
1994
|
503 |
|
2207
|
504 |
In the above definition we ommited the cases for existential quantifiers
|
|
505 |
and unique existential quantifiers, as they are very similar to the cases
|
|
506 |
for the universal quantifier.
|
2197
|
507 |
|
2207
|
508 |
Next we define the function @{text INJ} which takes the statement of
|
|
509 |
the regularized theorems and the statement of the lifted theorem both as
|
|
510 |
terms and returns the statment of the injected theorem:
|
2198
|
511 |
|
|
512 |
\begin{itemize}
|
|
513 |
\item @{text "INJ ((\<lambda>x. t) : \<sigma>, (\<lambda>x. s) : \<sigma>) = \<lambda>x. (INJ (t, s)"}
|
|
514 |
\item @{text "INJ ((\<lambda>x. t) : \<sigma>, (\<lambda>x. s) : \<tau>) = REP(\<sigma>,\<tau>) (ABS (\<sigma>,\<tau>) (\<lambda>x. (INJ (t, s))))"}
|
|
515 |
\item @{text "INJ ((\<lambda>x \<in> R. t) : \<sigma>, (\<lambda>x. s) : \<tau>) = REP(\<sigma>,\<tau>) (ABS (\<sigma>,\<tau>) (\<lambda>x \<in> R. (INJ (t, s))))"}
|
|
516 |
\item @{text "INJ (\<forall> t, \<forall> s) = \<forall> (INJ (t, s)"}
|
|
517 |
\item @{text "INJ (\<forall> t \<in> R, \<forall> s) = \<forall> (INJ (t, s) \<in> R"}
|
|
518 |
\item @{text "INJ (t\<^isub>1 t\<^isub>2, s\<^isub>1 s\<^isub>2) = INJ (t\<^isub>1, s\<^isub>1) INJ (t\<^isub>2, s\<^isub>2)"}
|
|
519 |
\item @{text "INJ (v\<^isub>1 : \<sigma>, v\<^isub>2 : \<sigma>) = v\<^isub>1"}
|
|
520 |
\item @{text "INJ (v\<^isub>1 : \<sigma>, v\<^isub>2 : \<tau>) = REP(\<sigma>,\<tau>) (ABS (\<sigma>,\<tau>) (v\<^isub>1))"}
|
|
521 |
\item @{text "INJ (c\<^isub>1 : \<sigma>, c\<^isub>2 : \<sigma>) = c\<^isub>1"}
|
|
522 |
\item @{text "INJ (c\<^isub>1 : \<sigma>, c\<^isub>2 : \<tau>) = REP(\<sigma>,\<tau>) (ABS (\<sigma>,\<tau>) (c\<^isub>1))"}
|
|
523 |
\end{itemize}
|
|
524 |
|
|
525 |
For existential quantifiers and unique existential quantifiers it is
|
|
526 |
defined similarily to the universal one.
|
|
527 |
|
2197
|
528 |
*}
|
|
529 |
|
2208
|
530 |
subsection {* Proof procedure *}
|
|
531 |
|
|
532 |
(* In the below the type-guiding 'QuotTrue' assumption is removed; since we
|
|
533 |
present in a paper a version with typed-variables it is not necessary *)
|
2197
|
534 |
|
|
535 |
text {*
|
2208
|
536 |
|
|
537 |
With the above definitions of @{text "REG"} and @{text "INJ"} we can show
|
|
538 |
how the proof is performed. The first step is always the application of
|
|
539 |
of the following lemma:
|
|
540 |
|
|
541 |
@{term "[|A; A --> B; B = C; C = D|] ==> D"}
|
|
542 |
|
|
543 |
With @{text A} instantiated to the original raw theorem,
|
|
544 |
@{text B} instantiated to @{text "REG(A)"},
|
|
545 |
@{text C} instantiated to @{text "INJ(REG(A))"},
|
|
546 |
and @{text D} instantiated to the statement of the lifted theorem.
|
|
547 |
The first assumption can be immediately discharged using the original
|
|
548 |
theorem and the three left subgoals are exactly the subgoals of regularization,
|
|
549 |
injection and cleaning. The three can be proved independently by the
|
|
550 |
framework and in case there are non-solved subgoals they can be left
|
|
551 |
to the user.
|
|
552 |
|
|
553 |
The injection and cleaning subgoals are always solved if the appropriate
|
|
554 |
respectfulness and preservation theorems are given. It is not the case
|
|
555 |
with regularization; sometimes a theorem given by the user does not
|
|
556 |
imply a regularized version and a stronger one needs to be proved. This
|
|
557 |
is outside of the scope of the quotient package, so the user is then left
|
|
558 |
with such obligations. As an example lets see the simplest possible
|
|
559 |
non-liftable theorem for integers: When we want to prove @{term "0 \<noteq> 1"}
|
|
560 |
on integers the fact that @{term "\<not> (0, 0) = (1, 0)"} is not enough. It
|
|
561 |
only shows that particular items in the equivalence classes are not equal,
|
|
562 |
a more general statement saying that the classes are not equal is necessary.
|
|
563 |
*}
|
|
564 |
|
|
565 |
subsection {* Proving Regularization *}
|
|
566 |
|
|
567 |
text {*
|
1994
|
568 |
|
2209
|
569 |
Isabelle provides a set of \emph{mono} rules, that are used to split implications
|
|
570 |
of similar statements into simpler implication subgoals. These are enchanced
|
|
571 |
with special quotient theorem in the regularization goal. Below we only show
|
|
572 |
the versions for the universal quantifier. For the existential quantifier
|
|
573 |
and abstraction they are analoguous with some symmetry.
|
2199
|
574 |
|
2209
|
575 |
First, bounded universal quantifiers can be removed on the right:
|
2199
|
576 |
|
|
577 |
@{thm [display] ball_reg_right[no_vars]}
|
2206
|
578 |
|
2209
|
579 |
They can be removed anywhere if the relation is an equivalence relation:
|
|
580 |
|
|
581 |
@{thm [display] ball_reg_eqv[no_vars]}
|
|
582 |
|
|
583 |
And finally it can be removed anywhere if @{term R2} is an equivalence relation, then:
|
|
584 |
\[
|
|
585 |
@{thm (rhs) ball_reg_eqv_range[no_vars]} = @{thm (lhs) ball_reg_eqv_range[no_vars]}
|
|
586 |
\]
|
|
587 |
|
|
588 |
The last theorem is new in comparison with Homeier's package; it allows separating
|
|
589 |
regularization from injection.
|
|
590 |
|
2206
|
591 |
*}
|
|
592 |
|
|
593 |
(*
|
2209
|
594 |
@{thm (rhs) bex_reg_eqv_range[no_vars]} = @{thm (lhs) bex_reg_eqv_range[no_vars]}
|
2199
|
595 |
@{thm [display] bex_reg_left[no_vars]}
|
|
596 |
@{thm [display] bex1_bexeq_reg[no_vars]}
|
2206
|
597 |
@{thm [display] bex_reg_eqv[no_vars]}
|
2209
|
598 |
@{thm [display] babs_reg_eqv[no_vars]}
|
|
599 |
@{thm [display] babs_simp[no_vars]}
|
2206
|
600 |
*)
|
1994
|
601 |
|
|
602 |
subsection {* Injection *}
|
|
603 |
|
2199
|
604 |
text {*
|
2211
|
605 |
The injection proof starts with an equality between the regularized theorem
|
|
606 |
and the injected version. The proof again follows by the structure of the
|
|
607 |
two term, and is defined for a goal being a relation between the two terms.
|
2199
|
608 |
|
2211
|
609 |
\begin{itemize}
|
|
610 |
\item For two constants, an appropriate constant respectfullness assumption is used.
|
|
611 |
\item For two variables, the regularization assumptions state that they are related.
|
|
612 |
\item For two abstractions, they are eta-expanded and beta-reduced.
|
|
613 |
\end{itemize}
|
2199
|
614 |
|
2211
|
615 |
Otherwise the two terms are applications. There are two cases: If there is a REP/ABS
|
|
616 |
in the injected theorem we can use the theorem:
|
|
617 |
|
2199
|
618 |
@{thm [display] rep_abs_rsp[no_vars]}
|
|
619 |
|
2211
|
620 |
and continue the proof.
|
2199
|
621 |
|
2211
|
622 |
Otherwise we introduce an appropriate relation between the subterms and continue with
|
|
623 |
two subgoals using the lemma:
|
|
624 |
|
|
625 |
@{thm [display] apply_rsp[no_vars]}
|
2199
|
626 |
|
|
627 |
*}
|
|
628 |
|
1994
|
629 |
subsection {* Cleaning *}
|
|
630 |
|
2212
|
631 |
text {*
|
|
632 |
The @{text REG} and @{text INJ} functions have been defined in such a way
|
|
633 |
that establishing the goal theorem now consists only on rewriting the
|
|
634 |
injected theorem with the preservation theorems.
|
|
635 |
|
|
636 |
\begin{itemize}
|
|
637 |
\item First for lifted constants, their definitions are the preservation rules for
|
|
638 |
them.
|
|
639 |
\item For lambda abstractions lambda preservation establishes
|
|
640 |
the equality between the injected theorem and the goal. This allows both
|
|
641 |
abstraction and quantification over lifted types.
|
|
642 |
@{thm [display] lambda_prs[no_vars]}
|
|
643 |
\item Relations over lifted types are folded with:
|
|
644 |
@{thm [display] Quotient_rel_rep[no_vars]}
|
|
645 |
\item User given preservation theorems, that allow using higher level operations
|
|
646 |
and containers of types being lifted. An example may be
|
|
647 |
@{thm [display] map_prs(1)[no_vars]}
|
|
648 |
\end{itemize}
|
|
649 |
|
|
650 |
Preservation of relations and user given constant preservation lemmas *}
|
1994
|
651 |
|
|
652 |
section {* Examples *}
|
|
653 |
|
2210
|
654 |
(* Mention why equivalence *)
|
2206
|
655 |
|
2210
|
656 |
text {*
|
|
657 |
|
|
658 |
A user of our quotient package first needs to define an equivalence relation:
|
|
659 |
|
|
660 |
@{text "fun \<approx> where (x, y) \<approx> (u, v) = (x + v = u + y)"}
|
|
661 |
|
|
662 |
Then the user defines a quotient type:
|
|
663 |
|
|
664 |
@{text "quotient_type int = (nat \<times> nat) / \<approx>"}
|
|
665 |
|
|
666 |
Which leaves a proof obligation that the relation is an equivalence relation,
|
|
667 |
that can be solved with the automatic tactic with two definitions.
|
|
668 |
|
|
669 |
The user can then specify the constants on the quotient type:
|
|
670 |
|
|
671 |
@{text "quotient_definition 0 \<Colon> int is (0\<Colon>nat, 0\<Colon>nat)"}
|
|
672 |
@{text "fun plus_raw where plus_raw (x, y) (u, v) = (x + u, y + v)"}
|
|
673 |
@{text "quotient_definition (op +) \<Colon> (int \<Rightarrow> int \<Rightarrow> int) is plus_raw"}
|
|
674 |
|
|
675 |
Lets first take a simple theorem about addition on the raw level:
|
|
676 |
|
|
677 |
@{text "lemma plus_zero_raw: plus_raw (0, 0) i \<approx> i"}
|
|
678 |
|
|
679 |
When the user tries to lift a theorem about integer addition, the respectfulness
|
|
680 |
proof obligation is left, so let us prove it first:
|
|
681 |
|
|
682 |
@{text "lemma (op \<approx> \<Longrightarrow> op \<approx> \<Longrightarrow> op \<approx>) plus_raw plus_raw"}
|
|
683 |
|
|
684 |
Can be proved automatically by the system just by unfolding the definition
|
|
685 |
of @{term "op \<Longrightarrow>"}.
|
|
686 |
|
|
687 |
Now the user can either prove a lifted lemma explicitely:
|
|
688 |
|
|
689 |
@{text "lemma 0 + i = i by lifting plus_zero_raw"}
|
|
690 |
|
|
691 |
Or in this simple case use the automated translation mechanism:
|
|
692 |
|
|
693 |
@{text "thm plus_zero_raw[quot_lifted]"}
|
|
694 |
|
|
695 |
obtaining the same result.
|
|
696 |
*}
|
2206
|
697 |
|
1978
|
698 |
section {* Related Work *}
|
|
699 |
|
|
700 |
text {*
|
|
701 |
\begin{itemize}
|
|
702 |
|
2152
|
703 |
\item Peter Homeier's package~\cite{Homeier05} (and related work from there)
|
|
704 |
\item John Harrison's one~\cite{harrison-thesis} is the first one to lift theorems
|
|
705 |
but only first order.
|
1978
|
706 |
|
2152
|
707 |
\item PVS~\cite{PVS:Interpretations}
|
|
708 |
\item MetaPRL~\cite{Nogin02}
|
|
709 |
\item Manually defined quotients in Isabelle/HOL Library (Markus's Quotient\_Type,
|
|
710 |
Dixon's FSet, \ldots)
|
1978
|
711 |
|
|
712 |
\item Oscar Slotosch defines quotient-type automatically but no
|
2152
|
713 |
lifting~\cite{Slotosch97}.
|
1978
|
714 |
|
|
715 |
\item PER. And how to avoid it.
|
|
716 |
|
2152
|
717 |
\item Necessity of Hilbert Choice op and Larry's quotients~\cite{Paulson06}
|
1978
|
718 |
|
2152
|
719 |
\item Setoids in Coq and \cite{ChicliPS02}
|
1978
|
720 |
|
|
721 |
\end{itemize}
|
|
722 |
*}
|
1975
b1281a0051ae
added stub for quotient paper; call with isabelle make qpaper
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
723 |
|
2210
|
724 |
section {* Conclusion *}
|
|
725 |
|
2224
|
726 |
text {*
|
|
727 |
The package is part of the standard distribution of Isabelle.
|
|
728 |
*}
|
|
729 |
|
|
730 |
|
|
731 |
subsection {* Contributions *}
|
|
732 |
|
|
733 |
text {*
|
|
734 |
We present the detailed lifting procedure, which was not shown before.
|
|
735 |
|
|
736 |
The quotient package presented in this paper has the following
|
|
737 |
advantages over existing packages:
|
|
738 |
\begin{itemize}
|
|
739 |
|
|
740 |
\item We define quotient composition, function map composition and
|
|
741 |
relation map composition. This lets lifting polymorphic types with
|
|
742 |
subtypes quotiented as well. We extend the notions of
|
|
743 |
respectfulness and preservation to cope with quotient
|
|
744 |
composition.
|
|
745 |
|
|
746 |
\item We allow lifting only some occurrences of quotiented
|
|
747 |
types. Rsp/Prs extended. (used in nominal)
|
|
748 |
|
|
749 |
\item The quotient package is very modular. Definitions can be added
|
|
750 |
separately, rsp and prs can be proved separately, Quotients and maps
|
|
751 |
can be defined separately and theorems can
|
|
752 |
be lifted on a need basis. (useful with type-classes).
|
|
753 |
|
|
754 |
\item Can be used both manually (attribute, separate tactics,
|
|
755 |
rsp/prs databases) and programatically (automated definition of
|
|
756 |
lifted constants, the rsp proof obligations and theorem statement
|
|
757 |
translation according to given quotients).
|
|
758 |
|
|
759 |
\end{itemize}
|
|
760 |
*}
|
|
761 |
|
|
762 |
|
1975
b1281a0051ae
added stub for quotient paper; call with isabelle make qpaper
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
763 |
(*<*)
|
b1281a0051ae
added stub for quotient paper; call with isabelle make qpaper
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
764 |
end
|
1978
|
765 |
(*>*)
|