# HG changeset patch # User wenzelm # Date 1124482799 -7200 # Node ID bb09ba3e5b2f5e3f6bf7e0609b6c5c396b44cfa5 # Parent 65e340b6a56f36a11379dc77cb2aa50ab0bcd0e7 updated; diff -r 65e340b6a56f -r bb09ba3e5b2f doc-src/AxClass/Nat/document/Group.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc-src/AxClass/Nat/document/Group.tex Fri Aug 19 22:19:59 2005 +0200 @@ -0,0 +1,511 @@ +% +\begin{isabellebody}% +\def\isabellecontext{Group}% +\isamarkuptrue% +% +\isamarkupheader{Basic group theory% +} +% +\isadelimtheory +% +\endisadelimtheory +% +\isatagtheory +\isamarkupfalse% +\isacommand{theory}\ Group\ \isakeyword{imports}\ Main\ \isakeyword{begin}% +\endisatagtheory +{\isafoldtheory}% +% +\isadelimtheory +% +\endisadelimtheory +\isamarkuptrue% +% +\begin{isamarkuptext}% +\medskip\noindent The meta-level type system of Isabelle supports + \emph{intersections} and \emph{inclusions} of type classes. These + directly correspond to intersections and inclusions of type + predicates in a purely set theoretic sense. This is sufficient as a + means to describe simple hierarchies of structures. As an + illustration, we use the well-known example of semigroups, monoids, + general groups and Abelian groups.% +\end{isamarkuptext}% +\isamarkuptrue% +% +\isamarkupsubsection{Monoids and Groups% +} +\isamarkuptrue% +% +\begin{isamarkuptext}% +First we declare some polymorphic constants required later for the + signature parts of our structures.% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{consts}\isanewline +\ \ times\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a{\isachardoublequote}\ \ \ \ {\isacharparenleft}\isakeyword{infixl}\ {\isachardoublequote}{\isasymodot}{\isachardoublequote}\ {\isadigit{7}}{\isadigit{0}}{\isacharparenright}\isanewline +\ \ invers\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a{\isachardoublequote}\ \ \ \ {\isacharparenleft}{\isachardoublequote}{\isacharparenleft}{\isacharunderscore}{\isasyminv}{\isacharparenright}{\isachardoublequote}\ {\isacharbrackleft}{\isadigit{1}}{\isadigit{0}}{\isadigit{0}}{\isadigit{0}}{\isacharbrackright}\ {\isadigit{9}}{\isadigit{9}}{\isadigit{9}}{\isacharparenright}\isanewline +\ \ one\ {\isacharcolon}{\isacharcolon}\ {\isacharprime}a\ \ \ \ {\isacharparenleft}{\isachardoublequote}{\isasymone}{\isachardoublequote}{\isacharparenright}\isamarkuptrue% +% +\begin{isamarkuptext}% +\noindent Next we define class \isa{monoid} of monoids with + operations \isa{{\isasymodot}} and \isa{{\isasymone}}. Note that multiple class + axioms are allowed for user convenience --- they simply represent + the conjunction of their respective universal closures.% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{axclass}\ monoid\ {\isasymsubseteq}\ type\isanewline +\ \ assoc{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}x\ {\isasymodot}\ y{\isacharparenright}\ {\isasymodot}\ z\ {\isacharequal}\ x\ {\isasymodot}\ {\isacharparenleft}y\ {\isasymodot}\ z{\isacharparenright}{\isachardoublequote}\isanewline +\ \ left{\isacharunderscore}unit{\isacharcolon}\ {\isachardoublequote}{\isasymone}\ {\isasymodot}\ x\ {\isacharequal}\ x{\isachardoublequote}\isanewline +\ \ right{\isacharunderscore}unit{\isacharcolon}\ {\isachardoublequote}x\ {\isasymodot}\ {\isasymone}\ {\isacharequal}\ x{\isachardoublequote}\isamarkuptrue% +% +\begin{isamarkuptext}% +\noindent So class \isa{monoid} contains exactly those types + \isa{{\isasymtau}} where \isa{{\isasymodot}\ {\isasymColon}\ {\isasymtau}\ {\isasymRightarrow}\ {\isasymtau}\ {\isasymRightarrow}\ {\isasymtau}} and \isa{{\isasymone}\ {\isasymColon}\ {\isasymtau}} + are specified appropriately, such that \isa{{\isasymodot}} is associative and + \isa{{\isasymone}} is a left and right unit element for the \isa{{\isasymodot}} + operation.% +\end{isamarkuptext}% +\isamarkuptrue% +% +\begin{isamarkuptext}% +\medskip Independently of \isa{monoid}, we now define a linear + hierarchy of semigroups, general groups and Abelian groups. Note + that the names of class axioms are automatically qualified with each + class name, so we may re-use common names such as \isa{assoc}.% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{axclass}\ semigroup\ {\isasymsubseteq}\ type\isanewline +\ \ assoc{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}x\ {\isasymodot}\ y{\isacharparenright}\ {\isasymodot}\ z\ {\isacharequal}\ x\ {\isasymodot}\ {\isacharparenleft}y\ {\isasymodot}\ z{\isacharparenright}{\isachardoublequote}\isanewline +\isanewline +\isamarkupfalse% +\isacommand{axclass}\ group\ {\isasymsubseteq}\ semigroup\isanewline +\ \ left{\isacharunderscore}unit{\isacharcolon}\ {\isachardoublequote}{\isasymone}\ {\isasymodot}\ x\ {\isacharequal}\ x{\isachardoublequote}\isanewline +\ \ left{\isacharunderscore}inverse{\isacharcolon}\ {\isachardoublequote}x{\isasyminv}\ {\isasymodot}\ x\ {\isacharequal}\ {\isasymone}{\isachardoublequote}\isanewline +\isanewline +\isamarkupfalse% +\isacommand{axclass}\ agroup\ {\isasymsubseteq}\ group\isanewline +\ \ commute{\isacharcolon}\ {\isachardoublequote}x\ {\isasymodot}\ y\ {\isacharequal}\ y\ {\isasymodot}\ x{\isachardoublequote}\isamarkuptrue% +% +\begin{isamarkuptext}% +\noindent Class \isa{group} inherits associativity of \isa{{\isasymodot}} + from \isa{semigroup} and adds two further group axioms. Similarly, + \isa{agroup} is defined as the subset of \isa{group} such that + for all of its elements \isa{{\isasymtau}}, the operation \isa{{\isasymodot}\ {\isasymColon}\ {\isasymtau}\ {\isasymRightarrow}\ {\isasymtau}\ {\isasymRightarrow}\ {\isasymtau}} is even commutative.% +\end{isamarkuptext}% +\isamarkuptrue% +% +\isamarkupsubsection{Abstract reasoning% +} +\isamarkuptrue% +% +\begin{isamarkuptext}% +In a sense, axiomatic type classes may be viewed as \emph{abstract + theories}. Above class definitions gives rise to abstract axioms + \isa{assoc}, \isa{left{\isacharunderscore}unit}, \isa{left{\isacharunderscore}inverse}, \isa{commute}, where any of these contain a type variable \isa{{\isacharprime}a\ {\isasymColon}\ c} that is restricted to types of the corresponding class \isa{c}. \emph{Sort constraints} like this express a logical + precondition for the whole formula. For example, \isa{assoc} + states that for all \isa{{\isasymtau}}, provided that \isa{{\isasymtau}\ {\isasymColon}\ semigroup}, the operation \isa{{\isasymodot}\ {\isasymColon}\ {\isasymtau}\ {\isasymRightarrow}\ {\isasymtau}\ {\isasymRightarrow}\ {\isasymtau}} is associative. + + \medskip From a technical point of view, abstract axioms are just + ordinary Isabelle theorems, which may be used in proofs without + special treatment. Such ``abstract proofs'' usually yield new + ``abstract theorems''. For example, we may now derive the following + well-known laws of general groups.% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{theorem}\ group{\isacharunderscore}right{\isacharunderscore}inverse{\isacharcolon}\ {\isachardoublequote}x\ {\isasymodot}\ x{\isasyminv}\ {\isacharequal}\ {\isacharparenleft}{\isasymone}{\isasymColon}{\isacharprime}a{\isasymColon}group{\isacharparenright}{\isachardoublequote}\isanewline +% +\isadelimproof +% +\endisadelimproof +% +\isatagproof +\isamarkupfalse% +\isacommand{proof}\ {\isacharminus}\isanewline +\ \ \isamarkupfalse% +\isacommand{have}\ {\isachardoublequote}x\ {\isasymodot}\ x{\isasyminv}\ {\isacharequal}\ {\isasymone}\ {\isasymodot}\ {\isacharparenleft}x\ {\isasymodot}\ x{\isasyminv}{\isacharparenright}{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}simp\ only{\isacharcolon}\ group{\isachardot}left{\isacharunderscore}unit{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{also}\ \isamarkupfalse% +\isacommand{have}\ {\isachardoublequote}{\isachardot}{\isachardot}{\isachardot}\ {\isacharequal}\ {\isasymone}\ {\isasymodot}\ x\ {\isasymodot}\ x{\isasyminv}{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}simp\ only{\isacharcolon}\ semigroup{\isachardot}assoc{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{also}\ \isamarkupfalse% +\isacommand{have}\ {\isachardoublequote}{\isachardot}{\isachardot}{\isachardot}\ {\isacharequal}\ {\isacharparenleft}x{\isasyminv}{\isacharparenright}{\isasyminv}\ {\isasymodot}\ x{\isasyminv}\ {\isasymodot}\ x\ {\isasymodot}\ x{\isasyminv}{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}simp\ only{\isacharcolon}\ group{\isachardot}left{\isacharunderscore}inverse{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{also}\ \isamarkupfalse% +\isacommand{have}\ {\isachardoublequote}{\isachardot}{\isachardot}{\isachardot}\ {\isacharequal}\ {\isacharparenleft}x{\isasyminv}{\isacharparenright}{\isasyminv}\ {\isasymodot}\ {\isacharparenleft}x{\isasyminv}\ {\isasymodot}\ x{\isacharparenright}\ {\isasymodot}\ x{\isasyminv}{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}simp\ only{\isacharcolon}\ semigroup{\isachardot}assoc{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{also}\ \isamarkupfalse% +\isacommand{have}\ {\isachardoublequote}{\isachardot}{\isachardot}{\isachardot}\ {\isacharequal}\ {\isacharparenleft}x{\isasyminv}{\isacharparenright}{\isasyminv}\ {\isasymodot}\ {\isasymone}\ {\isasymodot}\ x{\isasyminv}{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}simp\ only{\isacharcolon}\ group{\isachardot}left{\isacharunderscore}inverse{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{also}\ \isamarkupfalse% +\isacommand{have}\ {\isachardoublequote}{\isachardot}{\isachardot}{\isachardot}\ {\isacharequal}\ {\isacharparenleft}x{\isasyminv}{\isacharparenright}{\isasyminv}\ {\isasymodot}\ {\isacharparenleft}{\isasymone}\ {\isasymodot}\ x{\isasyminv}{\isacharparenright}{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}simp\ only{\isacharcolon}\ semigroup{\isachardot}assoc{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{also}\ \isamarkupfalse% +\isacommand{have}\ {\isachardoublequote}{\isachardot}{\isachardot}{\isachardot}\ {\isacharequal}\ {\isacharparenleft}x{\isasyminv}{\isacharparenright}{\isasyminv}\ {\isasymodot}\ x{\isasyminv}{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}simp\ only{\isacharcolon}\ group{\isachardot}left{\isacharunderscore}unit{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{also}\ \isamarkupfalse% +\isacommand{have}\ {\isachardoublequote}{\isachardot}{\isachardot}{\isachardot}\ {\isacharequal}\ {\isasymone}{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}simp\ only{\isacharcolon}\ group{\isachardot}left{\isacharunderscore}inverse{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{finally}\ \isamarkupfalse% +\isacommand{show}\ {\isacharquery}thesis\ \isamarkupfalse% +\isacommand{{\isachardot}}\isanewline +\isamarkupfalse% +\isacommand{qed}% +\endisatagproof +{\isafoldproof}% +% +\isadelimproof +% +\endisadelimproof +\isamarkuptrue% +% +\begin{isamarkuptext}% +\noindent With \isa{group{\isacharunderscore}right{\isacharunderscore}inverse} already available, \isa{group{\isacharunderscore}right{\isacharunderscore}unit}\label{thm:group-right-unit} is now established + much easier.% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{theorem}\ group{\isacharunderscore}right{\isacharunderscore}unit{\isacharcolon}\ {\isachardoublequote}x\ {\isasymodot}\ {\isasymone}\ {\isacharequal}\ {\isacharparenleft}x{\isasymColon}{\isacharprime}a{\isasymColon}group{\isacharparenright}{\isachardoublequote}\isanewline +% +\isadelimproof +% +\endisadelimproof +% +\isatagproof +\isamarkupfalse% +\isacommand{proof}\ {\isacharminus}\isanewline +\ \ \isamarkupfalse% +\isacommand{have}\ {\isachardoublequote}x\ {\isasymodot}\ {\isasymone}\ {\isacharequal}\ x\ {\isasymodot}\ {\isacharparenleft}x{\isasyminv}\ {\isasymodot}\ x{\isacharparenright}{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}simp\ only{\isacharcolon}\ group{\isachardot}left{\isacharunderscore}inverse{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{also}\ \isamarkupfalse% +\isacommand{have}\ {\isachardoublequote}{\isachardot}{\isachardot}{\isachardot}\ {\isacharequal}\ x\ {\isasymodot}\ x{\isasyminv}\ {\isasymodot}\ x{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}simp\ only{\isacharcolon}\ semigroup{\isachardot}assoc{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{also}\ \isamarkupfalse% +\isacommand{have}\ {\isachardoublequote}{\isachardot}{\isachardot}{\isachardot}\ {\isacharequal}\ {\isasymone}\ {\isasymodot}\ x{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}simp\ only{\isacharcolon}\ group{\isacharunderscore}right{\isacharunderscore}inverse{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{also}\ \isamarkupfalse% +\isacommand{have}\ {\isachardoublequote}{\isachardot}{\isachardot}{\isachardot}\ {\isacharequal}\ x{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}simp\ only{\isacharcolon}\ group{\isachardot}left{\isacharunderscore}unit{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{finally}\ \isamarkupfalse% +\isacommand{show}\ {\isacharquery}thesis\ \isamarkupfalse% +\isacommand{{\isachardot}}\isanewline +\isamarkupfalse% +\isacommand{qed}% +\endisatagproof +{\isafoldproof}% +% +\isadelimproof +% +\endisadelimproof +\isamarkuptrue% +% +\begin{isamarkuptext}% +\medskip Abstract theorems may be instantiated to only those types + \isa{{\isasymtau}} where the appropriate class membership \isa{{\isasymtau}\ {\isasymColon}\ c} is + known at Isabelle's type signature level. Since we have \isa{agroup\ {\isasymsubseteq}\ group\ {\isasymsubseteq}\ semigroup} by definition, all theorems of \isa{semigroup} and \isa{group} are automatically inherited by \isa{group} and \isa{agroup}.% +\end{isamarkuptext}% +\isamarkuptrue% +% +\isamarkupsubsection{Abstract instantiation% +} +\isamarkuptrue% +% +\begin{isamarkuptext}% +From the definition, the \isa{monoid} and \isa{group} classes + have been independent. Note that for monoids, \isa{right{\isacharunderscore}unit} + had to be included as an axiom, but for groups both \isa{right{\isacharunderscore}unit} and \isa{right{\isacharunderscore}inverse} are derivable from the other + axioms. With \isa{group{\isacharunderscore}right{\isacharunderscore}unit} derived as a theorem of group + theory (see page~\pageref{thm:group-right-unit}), we may now + instantiate \isa{monoid\ {\isasymsubseteq}\ semigroup} and \isa{group\ {\isasymsubseteq}\ monoid} properly as follows (cf.\ \figref{fig:monoid-group}). + + \begin{figure}[htbp] + \begin{center} + \small + \unitlength 0.6mm + \begin{picture}(65,90)(0,-10) + \put(15,10){\line(0,1){10}} \put(15,30){\line(0,1){10}} + \put(15,50){\line(1,1){10}} \put(35,60){\line(1,-1){10}} + \put(15,5){\makebox(0,0){\isa{agroup}}} + \put(15,25){\makebox(0,0){\isa{group}}} + \put(15,45){\makebox(0,0){\isa{semigroup}}} + \put(30,65){\makebox(0,0){\isa{type}}} \put(50,45){\makebox(0,0){\isa{monoid}}} + \end{picture} + \hspace{4em} + \begin{picture}(30,90)(0,0) + \put(15,10){\line(0,1){10}} \put(15,30){\line(0,1){10}} + \put(15,50){\line(0,1){10}} \put(15,70){\line(0,1){10}} + \put(15,5){\makebox(0,0){\isa{agroup}}} + \put(15,25){\makebox(0,0){\isa{group}}} + \put(15,45){\makebox(0,0){\isa{monoid}}} + \put(15,65){\makebox(0,0){\isa{semigroup}}} + \put(15,85){\makebox(0,0){\isa{type}}} + \end{picture} + \caption{Monoids and groups: according to definition, and by proof} + \label{fig:monoid-group} + \end{center} + \end{figure}% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{instance}\ monoid\ {\isasymsubseteq}\ semigroup\isanewline +% +\isadelimproof +% +\endisadelimproof +% +\isatagproof +\isamarkupfalse% +\isacommand{proof}\isanewline +\ \ \isamarkupfalse% +\isacommand{fix}\ x\ y\ z\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a{\isasymColon}monoid{\isachardoublequote}\isanewline +\ \ \isamarkupfalse% +\isacommand{show}\ {\isachardoublequote}x\ {\isasymodot}\ y\ {\isasymodot}\ z\ {\isacharequal}\ x\ {\isasymodot}\ {\isacharparenleft}y\ {\isasymodot}\ z{\isacharparenright}{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}rule\ monoid{\isachardot}assoc{\isacharparenright}\isanewline +\isamarkupfalse% +\isacommand{qed}% +\endisatagproof +{\isafoldproof}% +% +\isadelimproof +\isanewline +% +\endisadelimproof +\isanewline +\isamarkupfalse% +\isacommand{instance}\ group\ {\isasymsubseteq}\ monoid\isanewline +% +\isadelimproof +% +\endisadelimproof +% +\isatagproof +\isamarkupfalse% +\isacommand{proof}\isanewline +\ \ \isamarkupfalse% +\isacommand{fix}\ x\ y\ z\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a{\isasymColon}group{\isachardoublequote}\isanewline +\ \ \isamarkupfalse% +\isacommand{show}\ {\isachardoublequote}x\ {\isasymodot}\ y\ {\isasymodot}\ z\ {\isacharequal}\ x\ {\isasymodot}\ {\isacharparenleft}y\ {\isasymodot}\ z{\isacharparenright}{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}rule\ semigroup{\isachardot}assoc{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{show}\ {\isachardoublequote}{\isasymone}\ {\isasymodot}\ x\ {\isacharequal}\ x{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}rule\ group{\isachardot}left{\isacharunderscore}unit{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{show}\ {\isachardoublequote}x\ {\isasymodot}\ {\isasymone}\ {\isacharequal}\ x{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}rule\ group{\isacharunderscore}right{\isacharunderscore}unit{\isacharparenright}\isanewline +\isamarkupfalse% +\isacommand{qed}% +\endisatagproof +{\isafoldproof}% +% +\isadelimproof +% +\endisadelimproof +\isamarkuptrue% +% +\begin{isamarkuptext}% +\medskip The $\INSTANCE$ command sets up an appropriate goal that + represents the class inclusion (or type arity, see + \secref{sec:inst-arity}) to be proven (see also + \cite{isabelle-isar-ref}). The initial proof step causes + back-chaining of class membership statements wrt.\ the hierarchy of + any classes defined in the current theory; the effect is to reduce + to the initial statement to a number of goals that directly + correspond to any class axioms encountered on the path upwards + through the class hierarchy.% +\end{isamarkuptext}% +\isamarkuptrue% +% +\isamarkupsubsection{Concrete instantiation \label{sec:inst-arity}% +} +\isamarkuptrue% +% +\begin{isamarkuptext}% +So far we have covered the case of the form $\INSTANCE$~\isa{c\isactrlsub {\isadigit{1}}\ {\isasymsubseteq}\ c\isactrlsub {\isadigit{2}}}, namely \emph{abstract instantiation} --- + $c@1$ is more special than \isa{c\isactrlsub {\isadigit{1}}} and thus an instance + of \isa{c\isactrlsub {\isadigit{2}}}. Even more interesting for practical + applications are \emph{concrete instantiations} of axiomatic type + classes. That is, certain simple schemes \isa{{\isacharparenleft}{\isasymalpha}\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ {\isasymalpha}\isactrlsub n{\isacharparenright}\ t\ {\isasymColon}\ c} of class membership may be established at the + logical level and then transferred to Isabelle's type signature + level. + + \medskip As a typical example, we show that type \isa{bool} with + exclusive-or as \isa{{\isasymodot}} operation, identity as \isa{{\isasyminv}}, and + \isa{False} as \isa{{\isasymone}} forms an Abelian group.% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{defs}\ {\isacharparenleft}\isakeyword{overloaded}{\isacharparenright}\isanewline +\ \ times{\isacharunderscore}bool{\isacharunderscore}def{\isacharcolon}\ {\isachardoublequote}x\ {\isasymodot}\ y\ {\isasymequiv}\ x\ {\isasymnoteq}\ {\isacharparenleft}y{\isasymColon}bool{\isacharparenright}{\isachardoublequote}\isanewline +\ \ inverse{\isacharunderscore}bool{\isacharunderscore}def{\isacharcolon}\ {\isachardoublequote}x{\isasyminv}\ {\isasymequiv}\ x{\isasymColon}bool{\isachardoublequote}\isanewline +\ \ unit{\isacharunderscore}bool{\isacharunderscore}def{\isacharcolon}\ {\isachardoublequote}{\isasymone}\ {\isasymequiv}\ False{\isachardoublequote}\isamarkuptrue% +% +\begin{isamarkuptext}% +\medskip It is important to note that above $\DEFS$ are just + overloaded meta-level constant definitions, where type classes are + not yet involved at all. This form of constant definition with + overloading (and optional recursion over the syntactic structure of + simple types) are admissible as definitional extensions of plain HOL + \cite{Wenzel:1997:TPHOL}. The Haskell-style type system is not + required for overloading. Nevertheless, overloaded definitions are + best applied in the context of type classes. + + \medskip Since we have chosen above $\DEFS$ of the generic group + operations on type \isa{bool} appropriately, the class membership + \isa{bool\ {\isasymColon}\ agroup} may be now derived as follows.% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{instance}\ bool\ {\isacharcolon}{\isacharcolon}\ agroup\isanewline +% +\isadelimproof +% +\endisadelimproof +% +\isatagproof +\isamarkupfalse% +\isacommand{proof}\ {\isacharparenleft}intro{\isacharunderscore}classes{\isacharcomma}\isanewline +\ \ \ \ unfold\ times{\isacharunderscore}bool{\isacharunderscore}def\ inverse{\isacharunderscore}bool{\isacharunderscore}def\ unit{\isacharunderscore}bool{\isacharunderscore}def{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{fix}\ x\ y\ z\isanewline +\ \ \isamarkupfalse% +\isacommand{show}\ {\isachardoublequote}{\isacharparenleft}{\isacharparenleft}x\ {\isasymnoteq}\ y{\isacharparenright}\ {\isasymnoteq}\ z{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}x\ {\isasymnoteq}\ {\isacharparenleft}y\ {\isasymnoteq}\ z{\isacharparenright}{\isacharparenright}{\isachardoublequote}\ \isamarkupfalse% +\isacommand{by}\ blast\isanewline +\ \ \isamarkupfalse% +\isacommand{show}\ {\isachardoublequote}{\isacharparenleft}False\ {\isasymnoteq}\ x{\isacharparenright}\ {\isacharequal}\ x{\isachardoublequote}\ \isamarkupfalse% +\isacommand{by}\ blast\isanewline +\ \ \isamarkupfalse% +\isacommand{show}\ {\isachardoublequote}{\isacharparenleft}x\ {\isasymnoteq}\ x{\isacharparenright}\ {\isacharequal}\ False{\isachardoublequote}\ \isamarkupfalse% +\isacommand{by}\ blast\isanewline +\ \ \isamarkupfalse% +\isacommand{show}\ {\isachardoublequote}{\isacharparenleft}x\ {\isasymnoteq}\ y{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}y\ {\isasymnoteq}\ x{\isacharparenright}{\isachardoublequote}\ \isamarkupfalse% +\isacommand{by}\ blast\isanewline +\isamarkupfalse% +\isacommand{qed}% +\endisatagproof +{\isafoldproof}% +% +\isadelimproof +% +\endisadelimproof +\isamarkuptrue% +% +\begin{isamarkuptext}% +The result of an $\INSTANCE$ statement is both expressed as a + theorem of Isabelle's meta-logic, and as a type arity of the type + signature. The latter enables type-inference system to take care of + this new instance automatically. + + \medskip We could now also instantiate our group theory classes to + many other concrete types. For example, \isa{int\ {\isasymColon}\ agroup} + (e.g.\ by defining \isa{{\isasymodot}} as addition, \isa{{\isasyminv}} as negation + and \isa{{\isasymone}} as zero) or \isa{list\ {\isasymColon}\ {\isacharparenleft}type{\isacharparenright}\ semigroup} + (e.g.\ if \isa{{\isasymodot}} is defined as list append). Thus, the + characteristic constants \isa{{\isasymodot}}, \isa{{\isasyminv}}, \isa{{\isasymone}} + really become overloaded, i.e.\ have different meanings on different + types.% +\end{isamarkuptext}% +\isamarkuptrue% +% +\isamarkupsubsection{Lifting and Functors% +} +\isamarkuptrue% +% +\begin{isamarkuptext}% +As already mentioned above, overloading in the simply-typed HOL + systems may include recursion over the syntactic structure of types. + That is, definitional equations \isa{c\isactrlsup {\isasymtau}\ {\isasymequiv}\ t} may also + contain constants of name \isa{c} on the right-hand side --- if + these have types that are structurally simpler than \isa{{\isasymtau}}. + + This feature enables us to \emph{lift operations}, say to Cartesian + products, direct sums or function spaces. Subsequently we lift + \isa{{\isasymodot}} component-wise to binary products \isa{{\isacharprime}a\ {\isasymtimes}\ {\isacharprime}b}.% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{defs}\ {\isacharparenleft}\isakeyword{overloaded}{\isacharparenright}\isanewline +\ \ times{\isacharunderscore}prod{\isacharunderscore}def{\isacharcolon}\ {\isachardoublequote}p\ {\isasymodot}\ q\ {\isasymequiv}\ {\isacharparenleft}fst\ p\ {\isasymodot}\ fst\ q{\isacharcomma}\ snd\ p\ {\isasymodot}\ snd\ q{\isacharparenright}{\isachardoublequote}\isamarkuptrue% +% +\begin{isamarkuptext}% +It is very easy to see that associativity of \isa{{\isasymodot}} on \isa{{\isacharprime}a} + and \isa{{\isasymodot}} on \isa{{\isacharprime}b} transfers to \isa{{\isasymodot}} on \isa{{\isacharprime}a\ {\isasymtimes}\ {\isacharprime}b}. Hence the binary type constructor \isa{{\isasymodot}} maps semigroups + to semigroups. This may be established formally as follows.% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{instance}\ {\isacharasterisk}\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}semigroup{\isacharcomma}\ semigroup{\isacharparenright}\ semigroup\isanewline +% +\isadelimproof +% +\endisadelimproof +% +\isatagproof +\isamarkupfalse% +\isacommand{proof}\ {\isacharparenleft}intro{\isacharunderscore}classes{\isacharcomma}\ unfold\ times{\isacharunderscore}prod{\isacharunderscore}def{\isacharparenright}\isanewline +\ \ \isamarkupfalse% +\isacommand{fix}\ p\ q\ r\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a{\isasymColon}semigroup\ {\isasymtimes}\ {\isacharprime}b{\isasymColon}semigroup{\isachardoublequote}\isanewline +\ \ \isamarkupfalse% +\isacommand{show}\isanewline +\ \ \ \ {\isachardoublequote}{\isacharparenleft}fst\ {\isacharparenleft}fst\ p\ {\isasymodot}\ fst\ q{\isacharcomma}\ snd\ p\ {\isasymodot}\ snd\ q{\isacharparenright}\ {\isasymodot}\ fst\ r{\isacharcomma}\isanewline +\ \ \ \ \ \ snd\ {\isacharparenleft}fst\ p\ {\isasymodot}\ fst\ q{\isacharcomma}\ snd\ p\ {\isasymodot}\ snd\ q{\isacharparenright}\ {\isasymodot}\ snd\ r{\isacharparenright}\ {\isacharequal}\isanewline +\ \ \ \ \ \ \ {\isacharparenleft}fst\ p\ {\isasymodot}\ fst\ {\isacharparenleft}fst\ q\ {\isasymodot}\ fst\ r{\isacharcomma}\ snd\ q\ {\isasymodot}\ snd\ r{\isacharparenright}{\isacharcomma}\isanewline +\ \ \ \ \ \ \ \ snd\ p\ {\isasymodot}\ snd\ {\isacharparenleft}fst\ q\ {\isasymodot}\ fst\ r{\isacharcomma}\ snd\ q\ {\isasymodot}\ snd\ r{\isacharparenright}{\isacharparenright}{\isachardoublequote}\isanewline +\ \ \ \ \isamarkupfalse% +\isacommand{by}\ {\isacharparenleft}simp\ add{\isacharcolon}\ semigroup{\isachardot}assoc{\isacharparenright}\isanewline +\isamarkupfalse% +\isacommand{qed}% +\endisatagproof +{\isafoldproof}% +% +\isadelimproof +% +\endisadelimproof +\isamarkuptrue% +% +\begin{isamarkuptext}% +Thus, if we view class instances as ``structures'', then overloaded + constant definitions with recursion over types indirectly provide + some kind of ``functors'' --- i.e.\ mappings between abstract + theories.% +\end{isamarkuptext}% +% +\isadelimtheory +% +\endisadelimtheory +% +\isatagtheory +\isamarkupfalse% +\isacommand{end}% +\endisatagtheory +{\isafoldtheory}% +% +\isadelimtheory +% +\endisadelimtheory +\isanewline +\end{isabellebody}% +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "root" +%%% End: diff -r 65e340b6a56f -r bb09ba3e5b2f doc-src/AxClass/Nat/document/NatClass.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc-src/AxClass/Nat/document/NatClass.tex Fri Aug 19 22:19:59 2005 +0200 @@ -0,0 +1,96 @@ +% +\begin{isabellebody}% +\def\isabellecontext{NatClass}% +\isamarkuptrue% +% +\isamarkupheader{Defining natural numbers in FOL \label{sec:ex-natclass}% +} +% +\isadelimtheory +% +\endisadelimtheory +% +\isatagtheory +\isamarkupfalse% +\isacommand{theory}\ NatClass\ \isakeyword{imports}\ FOL\ \isakeyword{begin}% +\endisatagtheory +{\isafoldtheory}% +% +\isadelimtheory +% +\endisadelimtheory +\isamarkuptrue% +% +\begin{isamarkuptext}% +\medskip\noindent Axiomatic type classes abstract over exactly one + type argument. Thus, any \emph{axiomatic} theory extension where each + axiom refers to at most one type variable, may be trivially turned + into a \emph{definitional} one. + + We illustrate this with the natural numbers in + Isabelle/FOL.\footnote{See also + \url{http://isabelle.in.tum.de/library/FOL/ex/NatClass.html}}% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{consts}\isanewline +\ \ zero\ {\isacharcolon}{\isacharcolon}\ {\isacharprime}a\ \ \ \ {\isacharparenleft}{\isachardoublequote}{\isasymzero}{\isachardoublequote}{\isacharparenright}\isanewline +\ \ Suc\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a{\isachardoublequote}\isanewline +\ \ rec\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharparenleft}{\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a{\isacharparenright}\ {\isasymRightarrow}\ {\isacharprime}a{\isachardoublequote}\isanewline +\isanewline +\isamarkupfalse% +\isacommand{axclass}\ nat\ {\isasymsubseteq}\ {\isachardoublequote}term{\isachardoublequote}\isanewline +\ \ induct{\isacharcolon}\ {\isachardoublequote}P{\isacharparenleft}{\isasymzero}{\isacharparenright}\ {\isasymLongrightarrow}\ {\isacharparenleft}{\isasymAnd}x{\isachardot}\ P{\isacharparenleft}x{\isacharparenright}\ {\isasymLongrightarrow}\ P{\isacharparenleft}Suc{\isacharparenleft}x{\isacharparenright}{\isacharparenright}{\isacharparenright}\ {\isasymLongrightarrow}\ P{\isacharparenleft}n{\isacharparenright}{\isachardoublequote}\isanewline +\ \ Suc{\isacharunderscore}inject{\isacharcolon}\ {\isachardoublequote}Suc{\isacharparenleft}m{\isacharparenright}\ {\isacharequal}\ Suc{\isacharparenleft}n{\isacharparenright}\ {\isasymLongrightarrow}\ m\ {\isacharequal}\ n{\isachardoublequote}\isanewline +\ \ Suc{\isacharunderscore}neq{\isacharunderscore}{\isadigit{0}}{\isacharcolon}\ {\isachardoublequote}Suc{\isacharparenleft}m{\isacharparenright}\ {\isacharequal}\ {\isasymzero}\ {\isasymLongrightarrow}\ R{\isachardoublequote}\isanewline +\ \ rec{\isacharunderscore}{\isadigit{0}}{\isacharcolon}\ {\isachardoublequote}rec{\isacharparenleft}{\isasymzero}{\isacharcomma}\ a{\isacharcomma}\ f{\isacharparenright}\ {\isacharequal}\ a{\isachardoublequote}\isanewline +\ \ rec{\isacharunderscore}Suc{\isacharcolon}\ {\isachardoublequote}rec{\isacharparenleft}Suc{\isacharparenleft}m{\isacharparenright}{\isacharcomma}\ a{\isacharcomma}\ f{\isacharparenright}\ {\isacharequal}\ f{\isacharparenleft}m{\isacharcomma}\ rec{\isacharparenleft}m{\isacharcomma}\ a{\isacharcomma}\ f{\isacharparenright}{\isacharparenright}{\isachardoublequote}\isanewline +\isanewline +\isamarkupfalse% +\isacommand{constdefs}\isanewline +\ \ add\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a{\isacharcolon}{\isacharcolon}nat\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a{\isachardoublequote}\ \ \ \ {\isacharparenleft}\isakeyword{infixl}\ {\isachardoublequote}{\isacharplus}{\isachardoublequote}\ {\isadigit{6}}{\isadigit{0}}{\isacharparenright}\isanewline +\ \ {\isachardoublequote}m\ {\isacharplus}\ n\ {\isasymequiv}\ rec{\isacharparenleft}m{\isacharcomma}\ n{\isacharcomma}\ {\isasymlambda}x\ y{\isachardot}\ Suc{\isacharparenleft}y{\isacharparenright}{\isacharparenright}{\isachardoublequote}\isamarkuptrue% +% +\begin{isamarkuptext}% +This is an abstract version of the plain \isa{Nat} theory in + FOL.\footnote{See + \url{http://isabelle.in.tum.de/library/FOL/ex/Nat.html}} Basically, + we have just replaced all occurrences of type \isa{nat} by \isa{{\isacharprime}a} and used the natural number axioms to define class \isa{nat}. + There is only a minor snag, that the original recursion operator + \isa{rec} had to be made monomorphic. + + Thus class \isa{nat} contains exactly those types \isa{{\isasymtau}} that + are isomorphic to ``the'' natural numbers (with signature \isa{{\isasymzero}}, \isa{Suc}, \isa{rec}). + + \medskip What we have done here can be also viewed as \emph{type + specification}. Of course, it still remains open if there is some + type at all that meets the class axioms. Now a very nice property of + axiomatic type classes is that abstract reasoning is always possible + --- independent of satisfiability. The meta-logic won't break, even + if some classes (or general sorts) turns out to be empty later --- + ``inconsistent'' class definitions may be useless, but do not cause + any harm. + + Theorems of the abstract natural numbers may be derived in the same + way as for the concrete version. The original proof scripts may be + re-used with some trivial changes only (mostly adding some type + constraints).% +\end{isamarkuptext}% +% +\isadelimtheory +% +\endisadelimtheory +% +\isatagtheory +\isamarkupfalse% +\isacommand{end}% +\endisatagtheory +{\isafoldtheory}% +% +\isadelimtheory +% +\endisadelimtheory +\end{isabellebody}% +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "root" +%%% End: diff -r 65e340b6a56f -r bb09ba3e5b2f doc-src/AxClass/Nat/document/Product.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc-src/AxClass/Nat/document/Product.tex Fri Aug 19 22:19:59 2005 +0200 @@ -0,0 +1,132 @@ +% +\begin{isabellebody}% +\def\isabellecontext{Product}% +\isamarkuptrue% +% +\isamarkupheader{Syntactic classes% +} +% +\isadelimtheory +% +\endisadelimtheory +% +\isatagtheory +\isamarkupfalse% +\isacommand{theory}\ Product\ \isakeyword{imports}\ Main\ \isakeyword{begin}% +\endisatagtheory +{\isafoldtheory}% +% +\isadelimtheory +% +\endisadelimtheory +\isamarkuptrue% +% +\begin{isamarkuptext}% +\medskip\noindent There is still a feature of Isabelle's type system + left that we have not yet discussed. When declaring polymorphic + constants \isa{c\ {\isasymColon}\ {\isasymsigma}}, the type variables occurring in \isa{{\isasymsigma}} + may be constrained by type classes (or even general sorts) in an + arbitrary way. Note that by default, in Isabelle/HOL the + declaration \isa{{\isasymodot}\ {\isasymColon}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a} is actually an abbreviation + for \isa{{\isasymodot}\ {\isasymColon}\ {\isacharprime}a{\isasymColon}type\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a} Since class \isa{type} is the + universal class of HOL, this is not really a constraint at all. + + The \isa{product} class below provides a less degenerate example of + syntactic type classes.% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{axclass}\isanewline +\ \ product\ {\isasymsubseteq}\ type\isanewline +\isamarkupfalse% +\isacommand{consts}\isanewline +\ \ product\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a{\isasymColon}product\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a{\isachardoublequote}\ \ \ \ {\isacharparenleft}\isakeyword{infixl}\ {\isachardoublequote}{\isasymodot}{\isachardoublequote}\ {\isadigit{7}}{\isadigit{0}}{\isacharparenright}\isamarkuptrue% +% +\begin{isamarkuptext}% +Here class \isa{product} is defined as subclass of \isa{type} + without any additional axioms. This effects in logical equivalence + of \isa{product} and \isa{type}, as is reflected by the trivial + introduction rule generated for this definition. + + \medskip So what is the difference of declaring \isa{{\isasymodot}\ {\isasymColon}\ {\isacharprime}a{\isasymColon}product\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a} vs.\ declaring \isa{{\isasymodot}\ {\isasymColon}\ {\isacharprime}a{\isasymColon}type\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a} anyway? In this particular case where \isa{product\ {\isasymequiv}\ type}, it should be obvious that both declarations are the same + from the logic's point of view. It even makes the most sense to + remove sort constraints from constant declarations, as far as the + purely logical meaning is concerned \cite{Wenzel:1997:TPHOL}. + + On the other hand there are syntactic differences, of course. + Constants \isa{{\isasymodot}} on some type \isa{{\isasymtau}} are rejected by the + type-checker, unless the arity \isa{{\isasymtau}\ {\isasymColon}\ product} is part of the + type signature. In our example, this arity may be always added when + required by means of an $\INSTANCE$ with the default proof $\DDOT$. + + \medskip Thus, we may observe the following discipline of using + syntactic classes. Overloaded polymorphic constants have their type + arguments restricted to an associated (logically trivial) class + \isa{c}. Only immediately before \emph{specifying} these + constants on a certain type \isa{{\isasymtau}} do we instantiate \isa{{\isasymtau}\ {\isasymColon}\ c}. + + This is done for class \isa{product} and type \isa{bool} as + follows.% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{instance}\ bool\ {\isacharcolon}{\isacharcolon}\ product% +\isadelimproof +\ % +\endisadelimproof +% +\isatagproof +\isamarkupfalse% +\isacommand{{\isachardot}{\isachardot}}% +\endisatagproof +{\isafoldproof}% +% +\isadelimproof +% +\endisadelimproof +\isanewline +\isamarkupfalse% +\isacommand{defs}\ {\isacharparenleft}\isakeyword{overloaded}{\isacharparenright}\isanewline +\ \ product{\isacharunderscore}bool{\isacharunderscore}def{\isacharcolon}\ {\isachardoublequote}x\ {\isasymodot}\ y\ {\isasymequiv}\ x\ {\isasymand}\ y{\isachardoublequote}\isamarkuptrue% +% +\begin{isamarkuptext}% +The definition \isa{prod{\isacharunderscore}bool{\isacharunderscore}def} becomes syntactically + well-formed only after the arity \isa{bool\ {\isasymColon}\ product} is made + known to the type checker. + + \medskip It is very important to see that above $\DEFS$ are not + directly connected with $\INSTANCE$ at all! We were just following + our convention to specify \isa{{\isasymodot}} on \isa{bool} after having + instantiated \isa{bool\ {\isasymColon}\ product}. Isabelle does not require + these definitions, which is in contrast to programming languages like + Haskell \cite{haskell-report}. + + \medskip While Isabelle type classes and those of Haskell are almost + the same as far as type-checking and type inference are concerned, + there are important semantic differences. Haskell classes require + their instances to \emph{provide operations} of certain \emph{names}. + Therefore, its \texttt{instance} has a \texttt{where} part that tells + the system what these ``member functions'' should be. + + This style of \texttt{instance} would not make much sense in + Isabelle's meta-logic, because there is no internal notion of + ``providing operations'' or even ``names of functions''.% +\end{isamarkuptext}% +% +\isadelimtheory +% +\endisadelimtheory +% +\isatagtheory +\isamarkupfalse% +\isacommand{end}% +\endisatagtheory +{\isafoldtheory}% +% +\isadelimtheory +% +\endisadelimtheory +\isanewline +\end{isabellebody}% +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "root" +%%% End: diff -r 65e340b6a56f -r bb09ba3e5b2f doc-src/AxClass/Nat/document/Semigroups.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc-src/AxClass/Nat/document/Semigroups.tex Fri Aug 19 22:19:59 2005 +0200 @@ -0,0 +1,88 @@ +% +\begin{isabellebody}% +\def\isabellecontext{Semigroups}% +\isamarkuptrue% +% +\isamarkupheader{Semigroups% +} +% +\isadelimtheory +% +\endisadelimtheory +% +\isatagtheory +\isamarkupfalse% +\isacommand{theory}\ Semigroups\ \isakeyword{imports}\ Main\ \isakeyword{begin}% +\endisatagtheory +{\isafoldtheory}% +% +\isadelimtheory +% +\endisadelimtheory +\isamarkuptrue% +% +\begin{isamarkuptext}% +\medskip\noindent An axiomatic type class is simply a class of types + that all meet certain properties, which are also called \emph{class + axioms}. Thus, type classes may be also understood as type + predicates --- i.e.\ abstractions over a single type argument \isa{{\isacharprime}a}. Class axioms typically contain polymorphic constants that + depend on this type \isa{{\isacharprime}a}. These \emph{characteristic + constants} behave like operations associated with the ``carrier'' + type \isa{{\isacharprime}a}. + + We illustrate these basic concepts by the following formulation of + semigroups.% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{consts}\isanewline +\ \ times\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a{\isachardoublequote}\ \ \ \ {\isacharparenleft}\isakeyword{infixl}\ {\isachardoublequote}{\isasymodot}{\isachardoublequote}\ {\isadigit{7}}{\isadigit{0}}{\isacharparenright}\isanewline +\isamarkupfalse% +\isacommand{axclass}\ semigroup\ {\isasymsubseteq}\ type\isanewline +\ \ assoc{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}x\ {\isasymodot}\ y{\isacharparenright}\ {\isasymodot}\ z\ {\isacharequal}\ x\ {\isasymodot}\ {\isacharparenleft}y\ {\isasymodot}\ z{\isacharparenright}{\isachardoublequote}\isamarkuptrue% +% +\begin{isamarkuptext}% +\noindent Above we have first declared a polymorphic constant \isa{{\isasymodot}\ {\isasymColon}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a} and then defined the class \isa{semigroup} of + all types \isa{{\isasymtau}} such that \isa{{\isasymodot}\ {\isasymColon}\ {\isasymtau}\ {\isasymRightarrow}\ {\isasymtau}\ {\isasymRightarrow}\ {\isasymtau}} is indeed an + associative operator. The \isa{assoc} axiom contains exactly one + type variable, which is invisible in the above presentation, though. + Also note that free term variables (like \isa{x}, \isa{y}, + \isa{z}) are allowed for user convenience --- conceptually all of + these are bound by outermost universal quantifiers. + + \medskip In general, type classes may be used to describe + \emph{structures} with exactly one carrier \isa{{\isacharprime}a} and a fixed + \emph{signature}. Different signatures require different classes. + Below, class \isa{plus{\isacharunderscore}semigroup} represents semigroups \isa{{\isacharparenleft}{\isasymtau}{\isacharcomma}\ {\isasymoplus}\isactrlsup {\isasymtau}{\isacharparenright}}, while the original \isa{semigroup} would + correspond to semigroups of the form \isa{{\isacharparenleft}{\isasymtau}{\isacharcomma}\ {\isasymodot}\isactrlsup {\isasymtau}{\isacharparenright}}.% +\end{isamarkuptext}% +\isamarkupfalse% +\isacommand{consts}\isanewline +\ \ plus\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a{\isachardoublequote}\ \ \ \ {\isacharparenleft}\isakeyword{infixl}\ {\isachardoublequote}{\isasymoplus}{\isachardoublequote}\ {\isadigit{7}}{\isadigit{0}}{\isacharparenright}\isanewline +\isamarkupfalse% +\isacommand{axclass}\ plus{\isacharunderscore}semigroup\ {\isasymsubseteq}\ type\isanewline +\ \ assoc{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}x\ {\isasymoplus}\ y{\isacharparenright}\ {\isasymoplus}\ z\ {\isacharequal}\ x\ {\isasymoplus}\ {\isacharparenleft}y\ {\isasymoplus}\ z{\isacharparenright}{\isachardoublequote}\isamarkuptrue% +% +\begin{isamarkuptext}% +\noindent Even if classes \isa{plus{\isacharunderscore}semigroup} and \isa{semigroup} both represent semigroups in a sense, they are certainly + not quite the same.% +\end{isamarkuptext}% +% +\isadelimtheory +% +\endisadelimtheory +% +\isatagtheory +\isamarkupfalse% +\isacommand{end}% +\endisatagtheory +{\isafoldtheory}% +% +\isadelimtheory +% +\endisadelimtheory +\isanewline +\end{isabellebody}% +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "root" +%%% End: