76 |
76 |
77 \medskip\noindent\hspace*{2ex}\isa{class\ ord\ extends\ eq\ where} \\ |
77 \medskip\noindent\hspace*{2ex}\isa{class\ ord\ extends\ eq\ where} \\ |
78 \hspace*{4ex}\isa{less{\isacharunderscore}eq\ {\isasymColon}\ {\isasymalpha}\ {\isasymRightarrow}\ {\isasymalpha}\ {\isasymRightarrow}\ bool} \\ |
78 \hspace*{4ex}\isa{less{\isacharunderscore}eq\ {\isasymColon}\ {\isasymalpha}\ {\isasymRightarrow}\ {\isasymalpha}\ {\isasymRightarrow}\ bool} \\ |
79 \hspace*{4ex}\isa{less\ {\isasymColon}\ {\isasymalpha}\ {\isasymRightarrow}\ {\isasymalpha}\ {\isasymRightarrow}\ bool} |
79 \hspace*{4ex}\isa{less\ {\isasymColon}\ {\isasymalpha}\ {\isasymRightarrow}\ {\isasymalpha}\ {\isasymRightarrow}\ bool} |
80 |
80 |
81 \medskip\noindent Type variables are annotated with (finitly many) classes; |
81 \medskip\noindent Type variables are annotated with (finitely many) classes; |
82 these annotations are assertions that a particular polymorphic type |
82 these annotations are assertions that a particular polymorphic type |
83 provides definitions for overloaded functions. |
83 provides definitions for overloaded functions. |
84 |
84 |
85 Indeed, type classes not only allow for simple overloading |
85 Indeed, type classes not only allow for simple overloading |
86 but form a generic calculus, an instance of order-sorted |
86 but form a generic calculus, an instance of order-sorted |
87 algebra \cite{Nipkow-Prehofer:1993,nipkow-sorts93,Wenzel:1997:TPHOL}. |
87 algebra \cite{Nipkow-Prehofer:1993,nipkow-sorts93,Wenzel:1997:TPHOL}. |
88 |
88 |
89 From a software enigineering point of view, type classes |
89 From a software engineering point of view, type classes |
90 correspond to interfaces in object-oriented languages like Java; |
90 correspond to interfaces in object-oriented languages like Java; |
91 so, it is naturally desirable that type classes do not only |
91 so, it is naturally desirable that type classes do not only |
92 provide functions (class parameters) but also state specifications |
92 provide functions (class parameters) but also state specifications |
93 implementations must obey. For example, the \isa{class\ eq} |
93 implementations must obey. For example, the \isa{class\ eq} |
94 above could be given the following specification, demanding that |
94 above could be given the following specification, demanding that |
100 \hspace*{2ex}\isa{satisfying} \\ |
100 \hspace*{2ex}\isa{satisfying} \\ |
101 \hspace*{4ex}\isa{refl{\isacharcolon}\ eq\ x\ x} \\ |
101 \hspace*{4ex}\isa{refl{\isacharcolon}\ eq\ x\ x} \\ |
102 \hspace*{4ex}\isa{sym{\isacharcolon}\ eq\ x\ y\ {\isasymlongleftrightarrow}\ eq\ x\ y} \\ |
102 \hspace*{4ex}\isa{sym{\isacharcolon}\ eq\ x\ y\ {\isasymlongleftrightarrow}\ eq\ x\ y} \\ |
103 \hspace*{4ex}\isa{trans{\isacharcolon}\ eq\ x\ y\ {\isasymand}\ eq\ y\ z\ {\isasymlongrightarrow}\ eq\ x\ z} |
103 \hspace*{4ex}\isa{trans{\isacharcolon}\ eq\ x\ y\ {\isasymand}\ eq\ y\ z\ {\isasymlongrightarrow}\ eq\ x\ z} |
104 |
104 |
105 \medskip\noindent From a theoretic point of view, type classes are leightweight |
105 \medskip\noindent From a theoretic point of view, type classes are lightweight |
106 modules; Haskell type classes may be emulated by |
106 modules; Haskell type classes may be emulated by |
107 SML functors \cite{classes_modules}. |
107 SML functors \cite{classes_modules}. |
108 Isabelle/Isar offers a discipline of type classes which brings |
108 Isabelle/Isar offers a discipline of type classes which brings |
109 all those aspects together: |
109 all those aspects together: |
110 |
110 |
322 % |
322 % |
323 \begin{isamarkuptext}% |
323 \begin{isamarkuptext}% |
324 \noindent Associativity from product semigroups is |
324 \noindent Associativity from product semigroups is |
325 established using |
325 established using |
326 the definition of \isa{{\isasymotimes}} on products and the hypothetical |
326 the definition of \isa{{\isasymotimes}} on products and the hypothetical |
327 associativety of the type components; these hypothesis |
327 associativity of the type components; these hypotheses |
328 are facts due to the \isa{semigroup} constraints imposed |
328 are facts due to the \isa{semigroup} constraints imposed |
329 on the type components by the \isa{instance} proposition. |
329 on the type components by the \isa{instance} proposition. |
330 Indeed, this pattern often occurs with parametric types |
330 Indeed, this pattern often occurs with parametric types |
331 and type classes.% |
331 and type classes.% |
332 \end{isamarkuptext}% |
332 \end{isamarkuptext}% |
348 \ \ \ \ \ \ \isakeyword{fixes}\ neutral\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequoteopen}{\isasymalpha}{\isachardoublequoteclose}\ {\isacharparenleft}{\isachardoublequoteopen}{\isasymone}{\isachardoublequoteclose}{\isacharparenright}\isanewline |
348 \ \ \ \ \ \ \isakeyword{fixes}\ neutral\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequoteopen}{\isasymalpha}{\isachardoublequoteclose}\ {\isacharparenleft}{\isachardoublequoteopen}{\isasymone}{\isachardoublequoteclose}{\isacharparenright}\isanewline |
349 \ \ \ \ \ \ \isakeyword{assumes}\ neutl{\isacharcolon}\ {\isachardoublequoteopen}{\isasymone}\ {\isasymotimes}\ x\ {\isacharequal}\ x{\isachardoublequoteclose}% |
349 \ \ \ \ \ \ \isakeyword{assumes}\ neutl{\isacharcolon}\ {\isachardoublequoteopen}{\isasymone}\ {\isasymotimes}\ x\ {\isacharequal}\ x{\isachardoublequoteclose}% |
350 \begin{isamarkuptext}% |
350 \begin{isamarkuptext}% |
351 \noindent Again, we prove some instances, by |
351 \noindent Again, we prove some instances, by |
352 providing suitable parameter definitions and proofs for the |
352 providing suitable parameter definitions and proofs for the |
353 additional specifications. Obverve that instantiations |
353 additional specifications. Observe that instantiations |
354 for types with the same arity may be simultaneous:% |
354 for types with the same arity may be simultaneous:% |
355 \end{isamarkuptext}% |
355 \end{isamarkuptext}% |
356 \isamarkuptrue% |
356 \isamarkuptrue% |
357 \ \ \ \ \isacommand{instantiation}\isamarkupfalse% |
357 \ \ \ \ \isacommand{instantiation}\isamarkupfalse% |
358 \ nat\ \isakeyword{and}\ int\ {\isacharcolon}{\isacharcolon}\ monoidl\isanewline |
358 \ nat\ \isakeyword{and}\ int\ {\isacharcolon}{\isacharcolon}\ monoidl\isanewline |
773 a canonical interpretation as type classes. |
773 a canonical interpretation as type classes. |
774 Anyway, there is also the possibility of other interpretations. |
774 Anyway, there is also the possibility of other interpretations. |
775 For example, also \isa{list}s form a monoid with |
775 For example, also \isa{list}s form a monoid with |
776 \isa{op\ {\isacharat}} and \isa{{\isacharbrackleft}{\isacharbrackright}} as operations, but it |
776 \isa{op\ {\isacharat}} and \isa{{\isacharbrackleft}{\isacharbrackright}} as operations, but it |
777 seems inappropriate to apply to lists |
777 seems inappropriate to apply to lists |
778 the same operations as for genuinly algebraic types. |
778 the same operations as for genuinely algebraic types. |
779 In such a case, we simply can do a particular interpretation |
779 In such a case, we simply can do a particular interpretation |
780 of monoids for lists:% |
780 of monoids for lists:% |
781 \end{isamarkuptext}% |
781 \end{isamarkuptext}% |
782 \isamarkuptrue% |
782 \isamarkuptrue% |
783 \ \ \ \ \isacommand{interpretation}\isamarkupfalse% |
783 \ \ \ \ \isacommand{interpretation}\isamarkupfalse% |
943 } |
943 } |
944 \isamarkuptrue% |
944 \isamarkuptrue% |
945 % |
945 % |
946 \begin{isamarkuptext}% |
946 \begin{isamarkuptext}% |
947 As a commodity, class context syntax allows to refer |
947 As a commodity, class context syntax allows to refer |
948 to local class operations and their global conuterparts |
948 to local class operations and their global counterparts |
949 uniformly; type inference resolves ambiguities. For example:% |
949 uniformly; type inference resolves ambiguities. For example:% |
950 \end{isamarkuptext}% |
950 \end{isamarkuptext}% |
951 \isamarkuptrue% |
951 \isamarkuptrue% |
952 \isacommand{context}\isamarkupfalse% |
952 \isacommand{context}\isamarkupfalse% |
953 \ semigroup\isanewline |
953 \ semigroup\isanewline |