5 section {* Introduction *}
8 Type classes were introduced by Wadler and Blott \cite{wadler89how}
9 into the Haskell language to allow for a reasonable implementation
10 of overloading\footnote{throughout this tutorial, we are referring
11 to classical Haskell 1.0 type classes, not considering
12 later additions in expressiveness}.
13 As a canonical example, a polymorphic equality function
14 @{text "eq \<Colon> \<alpha> \<Rightarrow> \<alpha> \<Rightarrow> bool"} which is overloaded on different
15 types for @{text "\<alpha>"}, which is achieved by splitting introduction
16 of the @{text eq} function from its overloaded definitions by means
17 of @{text class} and @{text instance} declarations:
18 \footnote{syntax here is a kind of isabellized Haskell}
22 \noindent@{text "class eq where"} \\
23 \hspace*{2ex}@{text "eq \<Colon> \<alpha> \<Rightarrow> \<alpha> \<Rightarrow> bool"}
25 \medskip\noindent@{text "instance nat \<Colon> eq where"} \\
26 \hspace*{2ex}@{text "eq 0 0 = True"} \\
27 \hspace*{2ex}@{text "eq 0 _ = False"} \\
28 \hspace*{2ex}@{text "eq _ 0 = False"} \\
29 \hspace*{2ex}@{text "eq (Suc n) (Suc m) = eq n m"}
31 \medskip\noindent@{text "instance (\<alpha>\<Colon>eq, \<beta>\<Colon>eq) pair \<Colon> eq where"} \\
32 \hspace*{2ex}@{text "eq (x1, y1) (x2, y2) = eq x1 x2 \<and> eq y1 y2"}
34 \medskip\noindent@{text "class ord extends eq where"} \\
35 \hspace*{2ex}@{text "less_eq \<Colon> \<alpha> \<Rightarrow> \<alpha> \<Rightarrow> bool"} \\
36 \hspace*{2ex}@{text "less \<Colon> \<alpha> \<Rightarrow> \<alpha> \<Rightarrow> bool"}
40 \noindent Type variables are annotated with (finitely many) classes;
41 these annotations are assertions that a particular polymorphic type
42 provides definitions for overloaded functions.
44 Indeed, type classes not only allow for simple overloading
45 but form a generic calculus, an instance of order-sorted
46 algebra \cite{nipkow-sorts93,Nipkow-Prehofer:1993,Wenzel:1997:TPHOL}.
48 From a software engineering point of view, type classes
49 roughly correspond to interfaces in object-oriented languages like Java;
50 so, it is naturally desirable that type classes do not only
51 provide functions (class parameters) but also state specifications
52 implementations must obey. For example, the @{text "class eq"}
53 above could be given the following specification, demanding that
54 @{text "class eq"} is an equivalence relation obeying reflexivity,
55 symmetry and transitivity:
59 \noindent@{text "class eq where"} \\
60 \hspace*{2ex}@{text "eq \<Colon> \<alpha> \<Rightarrow> \<alpha> \<Rightarrow> bool"} \\
61 @{text "satisfying"} \\
62 \hspace*{2ex}@{text "refl: eq x x"} \\
63 \hspace*{2ex}@{text "sym: eq x y \<longleftrightarrow> eq x y"} \\
64 \hspace*{2ex}@{text "trans: eq x y \<and> eq y z \<longrightarrow> eq x z"}
68 \noindent From a theoretical point of view, type classes are lightweight
69 modules; Haskell type classes may be emulated by
70 SML functors \cite{classes_modules}.
71 Isabelle/Isar offers a discipline of type classes which brings
72 all those aspects together:
75 \item specifying abstract parameters together with
76 corresponding specifications,
77 \item instantiating those abstract parameters by a particular
79 \item in connection with a ``less ad-hoc'' approach to overloading,
80 \item with a direct link to the Isabelle module system:
81 locales \cite{kammueller-locales}.
84 \noindent Isar type classes also directly support code generation
85 in a Haskell like fashion. Internally, they are mapped to more primitive
86 Isabelle concepts \cite{Haftmann-Wenzel:2006:classes}.
88 This tutorial demonstrates common elements of structured specifications
89 and abstract reasoning with type classes by the algebraic hierarchy of
90 semigroups, monoids and groups. Our background theory is that of
91 Isabelle/HOL \cite{isa-tutorial}, for which some
92 familiarity is assumed.
95 section {* A simple algebra example \label{sec:example} *}
97 subsection {* Class definition *}
100 Depending on an arbitrary type @{text "\<alpha>"}, class @{text
101 "semigroup"} introduces a binary operator @{text "(\<otimes>)"} that is
102 assumed to be associative:
105 class %quote semigroup =
106 fixes mult :: "\<alpha> \<Rightarrow> \<alpha> \<Rightarrow> \<alpha>" (infixl "\<otimes>" 70)
107 assumes assoc: "(x \<otimes> y) \<otimes> z = x \<otimes> (y \<otimes> z)"
110 \noindent This @{command class} specification consists of two
111 parts: the \qn{operational} part names the class parameter
112 (@{element "fixes"}), the \qn{logical} part specifies properties on them
113 (@{element "assumes"}). The local @{element "fixes"} and
114 @{element "assumes"} are lifted to the theory toplevel,
116 parameter @{term [source] "mult \<Colon> \<alpha>\<Colon>semigroup \<Rightarrow> \<alpha> \<Rightarrow> \<alpha>"} and the
117 global theorem @{fact "semigroup.assoc:"}~@{prop [source] "\<And>x y
118 z \<Colon> \<alpha>\<Colon>semigroup. (x \<otimes> y) \<otimes> z = x \<otimes> (y \<otimes> z)"}.
122 subsection {* Class instantiation \label{sec:class_inst} *}
125 The concrete type @{typ int} is made a @{class semigroup}
126 instance by providing a suitable definition for the class parameter
127 @{text "(\<otimes>)"} and a proof for the specification of @{fact assoc}.
128 This is accomplished by the @{command instantiation} target:
131 instantiation %quote int :: semigroup
135 mult_int_def: "i \<otimes> j = i + (j\<Colon>int)"
137 instance %quote proof
138 fix i j k :: int have "(i + j) + k = i + (j + k)" by simp
139 then show "(i \<otimes> j) \<otimes> k = i \<otimes> (j \<otimes> k)"
140 unfolding mult_int_def .
146 \noindent @{command instantiation} defines class parameters
147 at a particular instance using common specification tools (here,
148 @{command definition}). The concluding @{command instance}
149 opens a proof that the given parameters actually conform
150 to the class specification. Note that the first proof step
151 is the @{method default} method,
152 which for such instance proofs maps to the @{method intro_classes} method.
153 This reduces an instance judgement to the relevant primitive
154 proof goals; typically it is the first method applied
155 in an instantiation proof.
157 From now on, the type-checker will consider @{typ int}
158 as a @{class semigroup} automatically, i.e.\ any general results
159 are immediately available on concrete instances.
161 \medskip Another instance of @{class semigroup} yields the natural numbers:
164 instantiation %quote nat :: semigroup
167 primrec %quote mult_nat where
168 "(0\<Colon>nat) \<otimes> n = n"
169 | "Suc m \<otimes> n = Suc (m \<otimes> n)"
171 instance %quote proof
173 show "m \<otimes> n \<otimes> q = m \<otimes> (n \<otimes> q)"
180 \noindent Note the occurence of the name @{text mult_nat}
181 in the primrec declaration; by default, the local name of
182 a class operation @{text f} to be instantiated on type constructor
183 @{text \<kappa>} is mangled as @{text f_\<kappa>}. In case of uncertainty,
184 these names may be inspected using the @{command "print_context"} command
185 or the corresponding ProofGeneral button.
188 subsection {* Lifting and parametric types *}
191 Overloaded definitions given at a class instantiation
192 may include recursion over the syntactic structure of types.
193 As a canonical example, we model product semigroups
194 using our simple algebra:
197 instantiation %quote * :: (semigroup, semigroup) semigroup
201 mult_prod_def: "p\<^isub>1 \<otimes> p\<^isub>2 = (fst p\<^isub>1 \<otimes> fst p\<^isub>2, snd p\<^isub>1 \<otimes> snd p\<^isub>2)"
203 instance %quote proof
204 fix p\<^isub>1 p\<^isub>2 p\<^isub>3 :: "\<alpha>\<Colon>semigroup \<times> \<beta>\<Colon>semigroup"
205 show "p\<^isub>1 \<otimes> p\<^isub>2 \<otimes> p\<^isub>3 = p\<^isub>1 \<otimes> (p\<^isub>2 \<otimes> p\<^isub>3)"
206 unfolding mult_prod_def by (simp add: assoc)
212 \noindent Associativity of product semigroups is established using
213 the definition of @{text "(\<otimes>)"} on products and the hypothetical
214 associativity of the type components; these hypotheses
215 are legitimate due to the @{class semigroup} constraints imposed
216 on the type components by the @{command instance} proposition.
217 Indeed, this pattern often occurs with parametric types
222 subsection {* Subclassing *}
225 We define a subclass @{text monoidl} (a semigroup with a left-hand neutral)
226 by extending @{class semigroup}
227 with one additional parameter @{text neutral} together
228 with its characteristic property:
231 class %quote monoidl = semigroup +
232 fixes neutral :: "\<alpha>" ("\<one>")
233 assumes neutl: "\<one> \<otimes> x = x"
236 \noindent Again, we prove some instances, by
237 providing suitable parameter definitions and proofs for the
238 additional specifications. Observe that instantiations
239 for types with the same arity may be simultaneous:
242 instantiation %quote nat and int :: monoidl
246 neutral_nat_def: "\<one> = (0\<Colon>nat)"
249 neutral_int_def: "\<one> = (0\<Colon>int)"
251 instance %quote proof
253 show "\<one> \<otimes> n = n"
254 unfolding neutral_nat_def by simp
257 show "\<one> \<otimes> k = k"
258 unfolding neutral_int_def mult_int_def by simp
263 instantiation %quote * :: (monoidl, monoidl) monoidl
267 neutral_prod_def: "\<one> = (\<one>, \<one>)"
269 instance %quote proof
270 fix p :: "\<alpha>\<Colon>monoidl \<times> \<beta>\<Colon>monoidl"
271 show "\<one> \<otimes> p = p"
272 unfolding neutral_prod_def mult_prod_def by (simp add: neutl)
278 \noindent Fully-fledged monoids are modelled by another subclass,
279 which does not add new parameters but tightens the specification:
282 class %quote monoid = monoidl +
283 assumes neutr: "x \<otimes> \<one> = x"
285 instantiation %quote nat and int :: monoid
288 instance %quote proof
290 show "n \<otimes> \<one> = n"
291 unfolding neutral_nat_def by (induct n) simp_all
294 show "k \<otimes> \<one> = k"
295 unfolding neutral_int_def mult_int_def by simp
300 instantiation %quote * :: (monoid, monoid) monoid
303 instance %quote proof
304 fix p :: "\<alpha>\<Colon>monoid \<times> \<beta>\<Colon>monoid"
305 show "p \<otimes> \<one> = p"
306 unfolding neutral_prod_def mult_prod_def by (simp add: neutr)
312 \noindent To finish our small algebra example, we add a @{text group} class
313 with a corresponding instance:
316 class %quote group = monoidl +
317 fixes inverse :: "\<alpha> \<Rightarrow> \<alpha>" ("(_\<div>)" [1000] 999)
318 assumes invl: "x\<div> \<otimes> x = \<one>"
320 instantiation %quote int :: group
324 inverse_int_def: "i\<div> = - (i\<Colon>int)"
326 instance %quote proof
328 have "-i + i = 0" by simp
329 then show "i\<div> \<otimes> i = \<one>"
330 unfolding mult_int_def neutral_int_def inverse_int_def .
336 section {* Type classes as locales *}
338 subsection {* A look behind the scenes *}
341 The example above gives an impression how Isar type classes work
342 in practice. As stated in the introduction, classes also provide
343 a link to Isar's locale system. Indeed, the logical core of a class
344 is nothing other than a locale:
348 fixes f :: "\<alpha> \<Rightarrow> \<alpha>"
349 assumes idem: "f (f x) = f x"
352 \noindent essentially introduces the locale
353 *} (*<*)setup %invisible {* Sign.add_path "foo" *}
356 fixes f :: "\<alpha> \<Rightarrow> \<alpha>"
357 assumes idem: "f (f x) = f x"
359 text {* \noindent together with corresponding constant(s): *}
361 consts %quote f :: "\<alpha> \<Rightarrow> \<alpha>"
364 \noindent The connection to the type system is done by means
365 of a primitive type class
366 *} (*<*)setup %invisible {* Sign.add_path "foo" *}
368 classes %quote idem < type
369 (*<*)axiomatization where idem: "f (f (x::\<alpha>\<Colon>idem)) = f x"
370 setup %invisible {* Sign.parent_path *}(*>*)
372 text {* \noindent together with a corresponding interpretation: *}
374 interpretation %quote idem_class:
375 idem "f \<Colon> (\<alpha>\<Colon>idem) \<Rightarrow> \<alpha>"
376 (*<*)proof qed (rule idem)(*>*)
379 \noindent This gives you the full power of the Isabelle module system;
380 conclusions in locale @{text idem} are implicitly propagated
381 to class @{text idem}.
382 *} (*<*)setup %invisible {* Sign.parent_path *}
384 subsection {* Abstract reasoning *}
387 Isabelle locales enable reasoning at a general level, while results
388 are implicitly transferred to all instances. For example, we can
389 now establish the @{text "left_cancel"} lemma for groups, which
390 states that the function @{text "(x \<otimes>)"} is injective:
393 lemma %quote (in group) left_cancel: "x \<otimes> y = x \<otimes> z \<longleftrightarrow> y = z"
395 assume "x \<otimes> y = x \<otimes> z"
396 then have "x\<div> \<otimes> (x \<otimes> y) = x\<div> \<otimes> (x \<otimes> z)" by simp
397 then have "(x\<div> \<otimes> x) \<otimes> y = (x\<div> \<otimes> x) \<otimes> z" using assoc by simp
398 then show "y = z" using neutl and invl by simp
401 then show "x \<otimes> y = x \<otimes> z" by simp
405 \noindent Here the \qt{@{keyword "in"} @{class group}} target specification
406 indicates that the result is recorded within that context for later
407 use. This local theorem is also lifted to the global one @{fact
408 "group.left_cancel:"} @{prop [source] "\<And>x y z \<Colon> \<alpha>\<Colon>group. x \<otimes> y = x \<otimes>
409 z \<longleftrightarrow> y = z"}. Since type @{text "int"} has been made an instance of
410 @{text "group"} before, we may refer to that fact as well: @{prop
411 [source] "\<And>x y z \<Colon> int. x \<otimes> y = x \<otimes> z \<longleftrightarrow> y = z"}.
415 subsection {* Derived definitions *}
418 Isabelle locales are targets which support local definitions:
421 primrec %quote (in monoid) pow_nat :: "nat \<Rightarrow> \<alpha> \<Rightarrow> \<alpha>" where
422 "pow_nat 0 x = \<one>"
423 | "pow_nat (Suc n) x = x \<otimes> pow_nat n x"
426 \noindent If the locale @{text group} is also a class, this local
427 definition is propagated onto a global definition of
428 @{term [source] "pow_nat \<Colon> nat \<Rightarrow> \<alpha>\<Colon>monoid \<Rightarrow> \<alpha>\<Colon>monoid"}
429 with corresponding theorems
431 @{thm pow_nat.simps [no_vars]}.
433 \noindent As you can see from this example, for local
434 definitions you may use any specification tool
435 which works together with locales, such as Krauss's recursive function package
440 subsection {* A functor analogy *}
443 We introduced Isar classes by analogy to type classes in
444 functional programming; if we reconsider this in the
445 context of what has been said about type classes and locales,
446 we can drive this analogy further by stating that type
447 classes essentially correspond to functors that have
448 a canonical interpretation as type classes.
449 There is also the possibility of other interpretations.
450 For example, @{text list}s also form a monoid with
451 @{text append} and @{term "[]"} as operations, but it
452 seems inappropriate to apply to lists
453 the same operations as for genuinely algebraic types.
454 In such a case, we can simply make a particular interpretation
455 of monoids for lists:
458 interpretation %quote list_monoid: monoid append "[]"
462 \noindent This enables us to apply facts on monoids
463 to lists, e.g. @{thm list_monoid.neutl [no_vars]}.
465 When using this interpretation pattern, it may also
466 be appropriate to map derived definitions accordingly:
469 primrec %quote replicate :: "nat \<Rightarrow> \<alpha> list \<Rightarrow> \<alpha> list" where
471 | "replicate (Suc n) xs = xs @ replicate n xs"
473 interpretation %quote list_monoid: monoid append "[]" where
474 "monoid.pow_nat append [] = replicate"
476 interpret monoid append "[]" ..
477 show "monoid.pow_nat append [] = replicate"
480 show "monoid.pow_nat append [] n = replicate n"
486 \noindent This pattern is also helpful to reuse abstract
487 specifications on the \emph{same} type. For example, think of a
488 class @{text preorder}; for type @{typ nat}, there are at least two
489 possible instances: the natural order or the order induced by the
490 divides relation. But only one of these instances can be used for
491 @{command instantiation}; using the locale behind the class @{text
492 preorder}, it is still possible to utilise the same abstract
493 specification again using @{command interpretation}.
496 subsection {* Additional subclass relations *}
499 Any @{text "group"} is also a @{text "monoid"}; this can be made
500 explicit by claiming an additional subclass relation, together with
501 a proof of the logical difference:
504 subclass %quote (in group) monoid
507 from invl have "x\<div> \<otimes> x = \<one>" by simp
508 with assoc [symmetric] neutl invl have "x\<div> \<otimes> (x \<otimes> \<one>) = x\<div> \<otimes> x" by simp
509 with left_cancel show "x \<otimes> \<one> = x" by simp
513 The logical proof is carried out on the locale level.
514 Afterwards it is propagated
515 to the type system, making @{text group} an instance of
516 @{text monoid} by adding an additional edge
517 to the graph of subclass relations
518 (\figref{fig:subclass}).
524 \begin{picture}(40,60)(0,0)
525 \put(20,60){\makebox(0,0){@{text semigroup}}}
526 \put(20,40){\makebox(0,0){@{text monoidl}}}
527 \put(00,20){\makebox(0,0){@{text monoid}}}
528 \put(40,00){\makebox(0,0){@{text group}}}
529 \put(20,55){\vector(0,-1){10}}
530 \put(15,35){\vector(-1,-1){10}}
531 \put(25,35){\vector(1,-3){10}}
534 \begin{picture}(40,60)(0,0)
535 \put(20,60){\makebox(0,0){@{text semigroup}}}
536 \put(20,40){\makebox(0,0){@{text monoidl}}}
537 \put(00,20){\makebox(0,0){@{text monoid}}}
538 \put(40,00){\makebox(0,0){@{text group}}}
539 \put(20,55){\vector(0,-1){10}}
540 \put(15,35){\vector(-1,-1){10}}
541 \put(05,15){\vector(3,-1){30}}
543 \caption{Subclass relationship of monoids and groups:
544 before and after establishing the relationship
545 @{text "group \<subseteq> monoid"}; transitive edges are left out.}
550 For illustration, a derived definition
551 in @{text group} using @{text pow_nat}
554 definition %quote (in group) pow_int :: "int \<Rightarrow> \<alpha> \<Rightarrow> \<alpha>" where
555 "pow_int k x = (if k >= 0
556 then pow_nat (nat k) x
557 else (pow_nat (nat (- k)) x)\<div>)"
560 \noindent yields the global definition of
561 @{term [source] "pow_int \<Colon> int \<Rightarrow> \<alpha>\<Colon>group \<Rightarrow> \<alpha>\<Colon>group"}
562 with the corresponding theorem @{thm pow_int_def [no_vars]}.
565 subsection {* A note on syntax *}
568 As a convenience, class context syntax allows references
569 to local class operations and their global counterparts
570 uniformly; type inference resolves ambiguities. For example:
573 context %quote semigroup
576 term %quote "x \<otimes> y" -- {* example 1 *}
577 term %quote "(x\<Colon>nat) \<otimes> y" -- {* example 2 *}
581 term %quote "x \<otimes> y" -- {* example 3 *}
584 \noindent Here in example 1, the term refers to the local class operation
585 @{text "mult [\<alpha>]"}, whereas in example 2 the type constraint
586 enforces the global class operation @{text "mult [nat]"}.
587 In the global context in example 3, the reference is
588 to the polymorphic global class operation @{text "mult [?\<alpha> \<Colon> semigroup]"}.
591 section {* Further issues *}
593 subsection {* Type classes and code generation *}
596 Turning back to the first motivation for type classes,
597 namely overloading, it is obvious that overloading
598 stemming from @{command class} statements and
599 @{command instantiation}
600 targets naturally maps to Haskell type classes.
601 The code generator framework \cite{isabelle-codegen}
602 takes this into account. If the target language (e.g.~SML)
603 lacks type classes, then they
604 are implemented by an explicit dictionary construction.
605 As example, let's go back to the power function:
608 definition %quote example :: int where
609 "example = pow_int 10 (-2)"
612 \noindent This maps to Haskell as follows:
615 text %quote {*@{code_stmts example (Haskell)}*}
618 \noindent The code in SML has explicit dictionary passing:
621 text %quote {*@{code_stmts example (SML)}*}
623 subsection {* Inspecting the type class universe *}
626 To facilitate orientation in complex subclass structures,
627 two diagnostics commands are provided:
631 \item[@{command "print_classes"}] print a list of all classes
632 together with associated operations etc.
634 \item[@{command "class_deps"}] visualizes the subclass relation
635 between all classes as a Hasse diagram.