1 % |
1 % |
2 \begin{isabellebody}% |
2 \begin{isabellebody}% |
3 \def\isabellecontext{Overloading{\isadigit{1}}}% |
3 \def\isabellecontext{Overloading{\isadigit{1}}}% |
|
4 \isamarkupfalse% |
4 % |
5 % |
5 \isamarkupsubsubsection{Controlled Overloading with Type Classes% |
6 \isamarkupsubsubsection{Controlled Overloading with Type Classes% |
6 } |
7 } |
|
8 \isamarkuptrue% |
7 % |
9 % |
8 \begin{isamarkuptext}% |
10 \begin{isamarkuptext}% |
9 We now start with the theory of ordering relations, which we shall phrase |
11 We now start with the theory of ordering relations, which we shall phrase |
10 in terms of the two binary symbols \isa{{\isacharless}{\isacharless}} and \isa{{\isacharless}{\isacharless}{\isacharequal}} |
12 in terms of the two binary symbols \isa{{\isacharless}{\isacharless}} and \isa{{\isacharless}{\isacharless}{\isacharequal}} |
11 to avoid clashes with \isa{{\isacharless}} and \isa{{\isasymle}} in theory \isa{Main}. To restrict the application of \isa{{\isacharless}{\isacharless}} and \isa{{\isacharless}{\isacharless}{\isacharequal}} we |
13 to avoid clashes with \isa{{\isacharless}} and \isa{{\isasymle}} in theory \isa{Main}. To restrict the application of \isa{{\isacharless}{\isacharless}} and \isa{{\isacharless}{\isacharless}{\isacharequal}} we |
12 introduce the class \isa{ordrel}:% |
14 introduce the class \isa{ordrel}:% |
13 \end{isamarkuptext}% |
15 \end{isamarkuptext}% |
14 \isacommand{axclass}\ ordrel\ {\isacharless}\ {\isachardoublequote}term{\isachardoublequote}% |
16 \isamarkuptrue% |
|
17 \isacommand{axclass}\ ordrel\ {\isacharless}\ {\isachardoublequote}term{\isachardoublequote}\isamarkupfalse% |
|
18 % |
15 \begin{isamarkuptext}% |
19 \begin{isamarkuptext}% |
16 \noindent |
20 \noindent |
17 This introduces a new class \isa{ordrel} and makes it a subclass of |
21 This introduces a new class \isa{ordrel} and makes it a subclass of |
18 the predefined class \isa{term}, which |
22 the predefined class \isa{term}, which |
19 is the class of all HOL types.\footnote{The quotes around \isa{term} |
23 is the class of all HOL types.\footnote{The quotes around \isa{term} |
20 simply avoid the clash with the command \isacommand{term}.} |
24 simply avoid the clash with the command \isacommand{term}.} |
21 This is a degenerate form of axiomatic type class without any axioms. |
25 This is a degenerate form of axiomatic type class without any axioms. |
22 Its sole purpose is to restrict the use of overloaded constants to meaningful |
26 Its sole purpose is to restrict the use of overloaded constants to meaningful |
23 instances:% |
27 instances:% |
24 \end{isamarkuptext}% |
28 \end{isamarkuptext}% |
|
29 \isamarkuptrue% |
25 \isacommand{consts}\ less\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}{\isacharprime}a{\isacharcolon}{\isacharcolon}ordrel{\isacharparenright}\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ bool{\isachardoublequote}\ \ \ \ \ {\isacharparenleft}\isakeyword{infixl}\ {\isachardoublequote}{\isacharless}{\isacharless}{\isachardoublequote}\ \ {\isadigit{5}}{\isadigit{0}}{\isacharparenright}\isanewline |
30 \isacommand{consts}\ less\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}{\isacharprime}a{\isacharcolon}{\isacharcolon}ordrel{\isacharparenright}\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ bool{\isachardoublequote}\ \ \ \ \ {\isacharparenleft}\isakeyword{infixl}\ {\isachardoublequote}{\isacharless}{\isacharless}{\isachardoublequote}\ \ {\isadigit{5}}{\isadigit{0}}{\isacharparenright}\isanewline |
26 \ \ \ \ \ \ \ le\ \ \ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}{\isacharprime}a{\isacharcolon}{\isacharcolon}ordrel{\isacharparenright}\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ bool{\isachardoublequote}\ \ \ \ \ {\isacharparenleft}\isakeyword{infixl}\ {\isachardoublequote}{\isacharless}{\isacharless}{\isacharequal}{\isachardoublequote}\ {\isadigit{5}}{\isadigit{0}}{\isacharparenright}% |
31 \ \ \ \ \ \ \ le\ \ \ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}{\isacharprime}a{\isacharcolon}{\isacharcolon}ordrel{\isacharparenright}\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ bool{\isachardoublequote}\ \ \ \ \ {\isacharparenleft}\isakeyword{infixl}\ {\isachardoublequote}{\isacharless}{\isacharless}{\isacharequal}{\isachardoublequote}\ {\isadigit{5}}{\isadigit{0}}{\isacharparenright}\isamarkupfalse% |
|
32 % |
27 \begin{isamarkuptext}% |
33 \begin{isamarkuptext}% |
28 \noindent |
34 \noindent |
29 Note that only one occurrence of a type variable in a type needs to be |
35 Note that only one occurrence of a type variable in a type needs to be |
30 constrained with a class; the constraint is propagated to the other |
36 constrained with a class; the constraint is propagated to the other |
31 occurrences automatically. |
37 occurrences automatically. |
32 |
38 |
33 So far there are no types of class \isa{ordrel}. To breathe life |
39 So far there are no types of class \isa{ordrel}. To breathe life |
34 into \isa{ordrel} we need to declare a type to be an \bfindex{instance} of |
40 into \isa{ordrel} we need to declare a type to be an \bfindex{instance} of |
35 \isa{ordrel}:% |
41 \isa{ordrel}:% |
36 \end{isamarkuptext}% |
42 \end{isamarkuptext}% |
37 \isacommand{instance}\ bool\ {\isacharcolon}{\isacharcolon}\ ordrel% |
43 \isamarkuptrue% |
|
44 \isacommand{instance}\ bool\ {\isacharcolon}{\isacharcolon}\ ordrel\isamarkupfalse% |
|
45 % |
38 \begin{isamarkuptxt}% |
46 \begin{isamarkuptxt}% |
39 \noindent |
47 \noindent |
40 Command \isacommand{instance} actually starts a proof, namely that |
48 Command \isacommand{instance} actually starts a proof, namely that |
41 \isa{bool} satisfies all axioms of \isa{ordrel}. |
49 \isa{bool} satisfies all axioms of \isa{ordrel}. |
42 There are none, but we still need to finish that proof, which we do |
50 There are none, but we still need to finish that proof, which we do |
43 by invoking the \methdx{intro_classes} method:% |
51 by invoking the \methdx{intro_classes} method:% |
44 \end{isamarkuptxt}% |
52 \end{isamarkuptxt}% |
45 \isacommand{by}\ intro{\isacharunderscore}classes% |
53 \isamarkuptrue% |
|
54 \isacommand{by}\ intro{\isacharunderscore}classes\isamarkupfalse% |
|
55 % |
46 \begin{isamarkuptext}% |
56 \begin{isamarkuptext}% |
47 \noindent |
57 \noindent |
48 More interesting \isacommand{instance} proofs will arise below |
58 More interesting \isacommand{instance} proofs will arise below |
49 in the context of proper axiomatic type classes. |
59 in the context of proper axiomatic type classes. |
50 |
60 |
51 Although terms like \isa{False\ {\isacharless}{\isacharless}{\isacharequal}\ P} are now legal, we still need to say |
61 Although terms like \isa{False\ {\isacharless}{\isacharless}{\isacharequal}\ P} are now legal, we still need to say |
52 what the relation symbols actually mean at type \isa{bool}:% |
62 what the relation symbols actually mean at type \isa{bool}:% |
53 \end{isamarkuptext}% |
63 \end{isamarkuptext}% |
|
64 \isamarkuptrue% |
54 \isacommand{defs}\ {\isacharparenleft}\isakeyword{overloaded}{\isacharparenright}\isanewline |
65 \isacommand{defs}\ {\isacharparenleft}\isakeyword{overloaded}{\isacharparenright}\isanewline |
55 le{\isacharunderscore}bool{\isacharunderscore}def{\isacharcolon}\ \ {\isachardoublequote}P\ {\isacharless}{\isacharless}{\isacharequal}\ Q\ {\isasymequiv}\ P\ {\isasymlongrightarrow}\ Q{\isachardoublequote}\isanewline |
66 le{\isacharunderscore}bool{\isacharunderscore}def{\isacharcolon}\ \ {\isachardoublequote}P\ {\isacharless}{\isacharless}{\isacharequal}\ Q\ {\isasymequiv}\ P\ {\isasymlongrightarrow}\ Q{\isachardoublequote}\isanewline |
56 less{\isacharunderscore}bool{\isacharunderscore}def{\isacharcolon}\ {\isachardoublequote}P\ {\isacharless}{\isacharless}\ Q\ {\isasymequiv}\ {\isasymnot}P\ {\isasymand}\ Q{\isachardoublequote}% |
67 less{\isacharunderscore}bool{\isacharunderscore}def{\isacharcolon}\ {\isachardoublequote}P\ {\isacharless}{\isacharless}\ Q\ {\isasymequiv}\ {\isasymnot}P\ {\isasymand}\ Q{\isachardoublequote}\isamarkupfalse% |
|
68 % |
57 \begin{isamarkuptext}% |
69 \begin{isamarkuptext}% |
58 \noindent |
70 \noindent |
59 Now \isa{False\ {\isacharless}{\isacharless}{\isacharequal}\ P} is provable:% |
71 Now \isa{False\ {\isacharless}{\isacharless}{\isacharequal}\ P} is provable:% |
60 \end{isamarkuptext}% |
72 \end{isamarkuptext}% |
|
73 \isamarkuptrue% |
61 \isacommand{lemma}\ {\isachardoublequote}False\ {\isacharless}{\isacharless}{\isacharequal}\ P{\isachardoublequote}\isanewline |
74 \isacommand{lemma}\ {\isachardoublequote}False\ {\isacharless}{\isacharless}{\isacharequal}\ P{\isachardoublequote}\isanewline |
62 \isacommand{by}{\isacharparenleft}simp\ add{\isacharcolon}\ le{\isacharunderscore}bool{\isacharunderscore}def{\isacharparenright}% |
75 \isamarkupfalse% |
|
76 \isacommand{by}{\isacharparenleft}simp\ add{\isacharcolon}\ le{\isacharunderscore}bool{\isacharunderscore}def{\isacharparenright}\isamarkupfalse% |
|
77 % |
63 \begin{isamarkuptext}% |
78 \begin{isamarkuptext}% |
64 \noindent |
79 \noindent |
65 At this point, \isa{{\isacharbrackleft}{\isacharbrackright}\ {\isacharless}{\isacharless}{\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}} is not even well-typed. |
80 At this point, \isa{{\isacharbrackleft}{\isacharbrackright}\ {\isacharless}{\isacharless}{\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}} is not even well-typed. |
66 To make it well-typed, |
81 To make it well-typed, |
67 we need to make lists a type of class \isa{ordrel}:% |
82 we need to make lists a type of class \isa{ordrel}:% |
68 \end{isamarkuptext}% |
83 \end{isamarkuptext}% |
|
84 \isamarkuptrue% |
|
85 \isamarkupfalse% |
69 \end{isabellebody}% |
86 \end{isabellebody}% |
70 %%% Local Variables: |
87 %%% Local Variables: |
71 %%% mode: latex |
88 %%% mode: latex |
72 %%% TeX-master: "root" |
89 %%% TeX-master: "root" |
73 %%% End: |
90 %%% End: |