% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\texht{\setcounter{chapter}{11}}{} % Chapter 12

%
\newcommand{\ugCategoriesTitle}{Categories}
\newcommand{\ugCategoriesNumber}{12.}
%
% =====================================================================
\begin{page}{ugCategoriesPage}{12. Categories}
% =====================================================================
\beginscroll

This chapter unravels the mysteries of categories---what
%-% \HDindex{category}{ugCategoriesPage}{12.}{Categories}
they are, how they are related to domains and packages,
%-% \HDindex{category!constructor}{ugCategoriesPage}{12.}{Categories}
how they are defined in \Language{}, and how you can extend the
%-% \HDindex{constructor!category}{ugCategoriesPage}{12.}{Categories}
system to include new categories of your own.

We assume that you have read the introductory material on domains
and categories in \downlink{``\ugTypesBasicDomainConsTitle''}{ugTypesBasicDomainConsPage} in Section \ugTypesBasicDomainConsNumber\ignore{ugTypesBasicDomainCons}.
There you learned that the notion of packages covered in the
previous chapter are special cases of domains.
While this is in fact the case, it is useful here to regard domains
as distinct from packages.

Think of a domain as a datatype, a collection of objects (the
objects of the domain).
From your ``sneak preview'' in the previous chapter, you might
conclude that categories are simply named clusters of operations
exported by domains.
As it turns out, categories have a much deeper meaning.
Categories are fundamental to the design of \Language{}.
They control the interactions between domains and algorithmic
packages, and, in fact, between all the components of \Language{}.

Categories form hierarchies as shown on the inside cover pages of
this book.
The inside front-cover pages illustrate the basic
algebraic hierarchy of the \Language{} programming language.
The inside back-cover pages show the hierarchy for data
structures.

Think of the category structures of \Language{} as a foundation
for a city on which superstructures (domains) are built.
The algebraic hierarchy, for example, serves as a foundation for
constructive mathematical algorithms embedded in the domains of
\Language{}.
Once in place, domains can be constructed, either independently or
from one another.

Superstructures are built for quality---domains are compiled into
machine code for run-time efficiency.
You can extend the foundation in directions beyond the space
directly beneath the superstructures, then extend selected
superstructures to cover the space.
Because of the compilation strategy, changing components of the
foundation generally means that the existing superstructures
(domains) built on the changed parts of the foundation
(categories) have to be rebuilt---that is, recompiled.

Before delving into some of the interesting facts about categories, let's see
how you define them in \Language{}.

\beginmenu
    \menudownlink{{12.1. Definitions}}{ugCategoriesDefsPage}
    \menudownlink{{12.2. Exports}}{ugCategoriesExportsPage}
    \menudownlink{{12.3. Documentation}}{ugCategoriesDocPage}
    \menudownlink{{12.4. Hierarchies}}{ugCategoriesHierPage}
    \menudownlink{{12.5. Membership}}{ugCategoriesMembershipPage}
    \menudownlink{{12.6. Defaults}}{ugCategoriesDefaultsPage}
    \menudownlink{{12.7. Axioms}}{ugCategoriesAxiomsPage}
    \menudownlink{{12.8. Correctness}}{ugCategoriesCorrectnessPage}
    \menudownlink{{12.9. Attributes}}{ugCategoriesAttributesPage}
    \menudownlink{{12.10. Parameters}}{ugCategoriesParametersPage}
    \menudownlink{{12.11. Conditionals}}{ugCategoriesConditionalsPage}
    \menudownlink{{12.12. Anonymous Categories}}{ugCategoriesAndPackagesPage}
\endmenu
\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugCategoriesDefsTitle}{Definitions}
\newcommand{\ugCategoriesDefsNumber}{12.1.}
%
% =====================================================================
\begin{page}{ugCategoriesDefsPage}{12.1. Definitions}
% =====================================================================
\beginscroll

A category is defined by a function with exactly the same format as
%-% \HDindex{category!definition}{ugCategoriesDefsPage}{12.1.}{Definitions}
any other function in \Language{}.

\beginImportant
The definition of a category has the syntax:
\centerline{{{\it CategoryForm} : {\tt Category\quad{}==\quad{}} {\it Extensions} {\tt [ with} {\it Exports} {\tt ]}}}

The brackets {\tt [ ]} here indicate optionality.
\endImportant


The first example of a category definition is
\spadtype{SetCategory},
the most basic of the algebraic categories in \Language{}.
%-% \HDexptypeindex{SetCategory}{ugCategoriesDefsPage}{12.1.}{Definitions}

\beginImportant
  
\noindent
{\tt 1.\ \ \ SetCategory():\ Category\ ==}\newline
{\tt 2.\ \ \ \ \ \ Join(Type,CoercibleTo\ OutputForm)\ with}\newline
{\tt 3.\ \ \ \ \ \ \ \ \ "="\ :\ (\$,\ \$)\ ->\ Boolean}\newline
\endImportant

The definition starts off with the name of the
category (\spadtype{SetCategory}); this is
always in column one in the source file.
%% maybe talk about naming conventions for source files? .spad or .ax?
All parts of a category definition are then indented with respect to this
%-% \HDindex{indentation}{ugCategoriesDefsPage}{12.1.}{Definitions}
first line.

In \downlink{``\ugTypesTitle''}{ugTypesPage} in Chapter \ugTypesNumber\ignore{ugTypes}, we talked about \spadtype{Ring} as denoting the
class of all domains that are rings, in short, the class of all
rings.
While this is the usual naming convention in \Language{}, it is also
common to use the word ``Category'' at the end of a category name for clarity.
The interpretation of the name \spadtype{SetCategory} is, then, ``the
category of all domains that are (mathematical) sets.''

The name \spadtype{SetCategory} is followed in the definition by its
formal parameters enclosed in parentheses \spadSyntax{()}.
Here there are no parameters.
As required, the type of the result of this category function is the
distinguished name {\sf Category}.

Then comes the \spadSyntax{==}.
As usual, what appears to the right of the \spadSyntax{==} is a
definition, here, a category definition.
A category definition always has two parts separated by the reserved word
\spadkey{with}
\spad{with}.
%\footnote{Debugging hint: it is very easy to forget
%the \spad{with}!}

The first part tells what categories the category extends.
Here, the category extends two categories: \spadtype{Type}, the
category of all domains, and
\spadtype{CoercibleTo(OutputForm)}.
%\footnote{\spadtype{CoercibleTo(OutputForm)}
%can also be written (and is written in the definition above) without
%parentheses.}
The operation \spad{Join} is a system-defined operation that
\spadkey{Join}
forms a single category from two or more other categories.

Every category other than \spadtype{Type} is an extension of some other
category.
If, for example, \spadtype{SetCategory} extended only the category
\spadtype{Type}, the definition here would read ``{\tt Type with
...}''.
In fact, the {\tt Type} is optional in this line; ``{\tt with
...}'' suffices.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugCategoriesExportsTitle}{Exports}
\newcommand{\ugCategoriesExportsNumber}{12.2.}
%
% =====================================================================
\begin{page}{ugCategoriesExportsPage}{12.2. Exports}
% =====================================================================
\beginscroll

To the right of the \spad{with} is a list of
\spadkey{with}
all the \spadglossSee{exports}{export} of the category.
Each exported operation has a name and a type expressed by a
\spadgloss{declaration} of the form
``{\frenchspacing\tt {\it name}: {\it type}}''.

Categories can export symbols, as well as
{\tt 0} and {\tt 1} which denote
domain constants.\footnote{The
numbers {\tt 0} and {\tt 1} are operation names in \Language{}.}
In the current implementation, all other exports are operations with
types expressed as \spadglossSee{mappings}{mapping} with the syntax
\centerline{{{\it}}
\centerline{{source\quad{\tt ->}\quad target}}
\centerline{{}}}

The category \spadtype{SetCategory} has a single export: the operation
\spadop{=} whose type is given by the mapping {\tt (\$, \$) -> Boolean}.
The \spadSyntax{\$} in a mapping type always means ``the domain.'' Thus
the operation \spadop{=} takes two arguments from the domain and
returns a value of type \spadtype{Boolean}.

The source part of the mapping here is given by a {\it tuple}
%-% \HDindex{tuple}{ugCategoriesExportsPage}{12.2.}{Exports}
consisting of two or more types separated by commas and enclosed in
parentheses.
If an operation takes only one argument, you can drop the parentheses
around the source type.
If the mapping has no arguments, the source part of the mapping is either
left blank or written as \spadSyntax{()}.
Here are examples of formats of various operations with some
contrived names.

\begin{verbatim}
someIntegerConstant  :    $
aZeroArgumentOperation:   () -> Integer
aOneArgumentOperation:    Integer -> $
aTwoArgumentOperation:    (Integer,$) -> Void
aThreeArgumentOperation:  ($,Integer,$) -> Fraction($)
\end{verbatim}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugCategoriesDocTitle}{Documentation}
\newcommand{\ugCategoriesDocNumber}{12.3.}
%
% =====================================================================
\begin{page}{ugCategoriesDocPage}{12.3. Documentation}
% =====================================================================
\beginscroll

The definition of \spadtype{SetCategory} above is  missing
an important component: its library documentation.
%-% \HDindex{documentation}{ugCategoriesDocPage}{12.3.}{Documentation}
Here is its definition, complete with documentation.

\beginImportant
  
\noindent
{\tt 1.\ \ \ ++\ Description:}\newline
{\tt 2.\ \ \ ++\ \bs{}axiomType\{SetCategory\}\ is\ the\ basic\ category}\newline
{\tt 3.\ \ \ ++\ for\ describing\ a\ collection\ of\ elements\ with}\newline
{\tt 4.\ \ \ ++\ \bs{}axiomOp\{=\}\ (equality)\ and\ a\ \bs{}axiomFun\{coerce\}}\newline
{\tt 5.\ \ \ ++\ to\ \bs{}axiomType\{OutputForm\}.}\newline
{\tt 6.\ \ \ }\newline
{\tt 7.\ \ \ SetCategory():\ Category\ ==}\newline
{\tt 8.\ \ \ \ \ Join(Type,\ CoercibleTo\ OutputForm)\ with}\newline
{\tt 9.\ \ \ \ \ \ \ "=":\ (\$,\ \$)\ ->\ Boolean}\newline
{\tt 10.\ \ \ \ \ \ \ \ ++\ \bs{}axiom\{x\ =\ y\}\ tests\ if\ \bs{}axiom\{x\}\ and}\newline
{\tt 11.\ \ \ \ \ \ \ \ ++\ \bs{}axiom\{y\}\ are\ equal.}\newline
\endImportant

Documentary comments are an important part of constructor definitions.
Documentation is given both for the category itself and for
each export.
A description for the category precedes the code.
Each line of the description begins in column one with \axiomSyntax{++}.
The description starts with the word {\tt Description:}.\footnote{Other
information such as the author's name, date of creation, and so on,
can go in this
area as well but are currently ignored by \Language{}.}
All lines of the description following the initial line are
indented by the same amount.

{\texht{\sloppy}{}
Surround the name of any constructor (with or without parameters) with an
\texht{\verb+\axiomType{}+}{\\axiomType\{\}}.
Similarly, surround an
operator name with \texht{\verb+\axiomOp{}+}{\\axiomOp\{\}},
an \Language{} operation with \texht{\verb+\axiomFun{}+}{\\axiomFun\{\}}, and a
variable or \Language{} expression with
\texht{\verb+\axiom{}+}{\\axiom\{\}}.
Library documentation is given in a \TeX{}-like language so that
it can be used both for hard-copy and for \Browse{}.
These different wrappings cause operations and types to have
mouse-active buttons in \Browse{}.
For hard-copy output, wrapped expressions appear in a different font.
The above documentation appears in hard-copy as:

}
%
\texht{\begin{quotation}}{\indent{3}}
%
\axiomType{SetCategory} is the basic category
for describing a collection of elements with \axiomOp{=}
(equality) and a \spadfun{coerce} to \axiomType{OutputForm}.
%
\texht{\end{quotation}}{\indent{0}}
%
and
%
\texht{\begin{quotation}}{\indent{3}}
%
\axiom{x = y} tests if \axiom{x} and \axiom{y} are equal.
%
\texht{\end{quotation}}{\indent{0}}
%

For our purposes in this chapter, we omit the documentation from further
category descriptions.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugCategoriesHierTitle}{Hierarchies}
\newcommand{\ugCategoriesHierNumber}{12.4.}
%
% =====================================================================
\begin{page}{ugCategoriesHierPage}{12.4. Hierarchies}
% =====================================================================
\beginscroll

A second example of a category is
\spadtype{SemiGroup}, defined by:
%-% \HDexptypeindex{SemiGroup}{ugCategoriesHierPage}{12.4.}{Hierarchies}

\beginImportant
  
\noindent
{\tt 1.\ \ \ SemiGroup():\ Category\ ==\ SetCategory\ with}\newline
{\tt 2.\ \ \ \ \ \ \ \ \ "*":\ \ (\$,\$)\ ->\ \$}\newline
{\tt 3.\ \ \ \ \ \ \ \ \ "**":\ (\$,\ PositiveInteger)\ ->\ \$}\newline
\endImportant

This definition is as simple as that for \spadtype{SetCategory},
except that there are two exported operations.
Multiple exported operations are written as a \spadgloss{pile},
that is, they all begin in the same column.
Here you see that the category mentions another type,
\spadtype{PositiveInteger}, in a signature.
Any domain can be used in a signature.

Since categories extend one another, they form hierarchies.
Each category other than \spadtype{Type} has one or more parents given
by the one or more categories mentioned before the \spad{with} part of
the definition.
\spadtype{SemiGroup} extends \spadtype{SetCategory} and
\spadtype{SetCategory} extends both \spadtype{Type} and
\spadtype{CoercibleTo (OutputForm)}.
Since \spadtype{CoercibleTo (OutputForm)} also extends \spadtype{Type},
the mention of \spadtype{Type} in the definition is unnecessary but
included for emphasis.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugCategoriesMembershipTitle}{Membership}
\newcommand{\ugCategoriesMembershipNumber}{12.5.}
%
% =====================================================================
\begin{page}{ugCategoriesMembershipPage}{12.5. Membership}
% =====================================================================
\beginscroll

We say a category designates a class of domains.
What class of domains?
%-% \HDindex{category!membership}{ugCategoriesMembershipPage}{12.5.}{Membership}
That is, how does \Language{} know what domains belong to what categories?
The simple answer to this basic question is key to the design of
\Language{}:

\beginImportant
\centerline{{{\bf Domains belong to categories by assertion.}}}
\endImportant

When a domain is defined, it is asserted to belong to one or more
categories.
Suppose, for example, that an author of domain \spadtype{String} wishes to
use the binary operator \spadop{*} to denote concatenation.
Thus \spad{"hello " * "there"} would produce the string
\spad{"hello there"}\footnote{Actually, concatenation of strings in
\Language{} is done by juxtaposition or by using the operation
\spadfunFrom{concat}{String}.
The expression \spad{"hello " "there"} produces the string
\spad{"hello there"}.}.
The author of \spadtype{String} could then assert that \spadtype{String}
is a member of \spadtype{SemiGroup}.
According to our definition of \spadtype{SemiGroup}, strings
would then also have the operation \spadop{**} defined automatically.
Then \spad{"--" ** 4} would produce a string of eight dashes
\spad{"--------"}.
Since \spadtype{String} is a member of \spadtype{SemiGroup}, it also is
a member of \spadtype{SetCategory} and thus has an operation
\spadop{=} for testing that two strings are equal.

\texht{Now turn to the algebraic category hierarchy inside the
front cover of this book.}{}
Any domain that is a member of a
category extending \spadtype{SemiGroup} is a member of
\spadtype{SemiGroup} (that is, it {\it is} a semigroup).
In particular, any domain asserted to be a \spadtype{Ring} is a
semigroup since \spadtype{Ring} extends \spadtype{Monoid}, that,
in turn, extends \spadtype{SemiGroup}.
The definition of \spadtype{Integer} in \Language{} asserts that
\spadtype{Integer} is a member of category
\spadtype{IntegerNumberSystem}, that, in turn, asserts that it is
a member of \spadtype{EuclideanDomain}.
Now \spadtype{EuclideanDomain} extends
\spadtype{PrincipalIdealDomain} and so on.
If you trace up the hierarchy, you see that
\spadtype{EuclideanDomain} extends \spadtype{Ring}, and,
therefore, \spadtype{SemiGroup}.
Thus \spadtype{Integer} is a semigroup and also exports the
operations \spadop{*} and \spadop{**}.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugCategoriesDefaultsTitle}{Defaults}
\newcommand{\ugCategoriesDefaultsNumber}{12.6.}
%
% =====================================================================
\begin{page}{ugCategoriesDefaultsPage}{12.6. Defaults}
% =====================================================================
\beginscroll

We actually omitted the last
%-% \HDindex{category!defaults}{ugCategoriesDefaultsPage}{12.6.}{Defaults}
part of the definition of
%-% \HDindex{default definitions}{ugCategoriesDefaultsPage}{12.6.}{Defaults}
\spadtype{SemiGroup} in
\downlink{``\ugCategoriesHierTitle''}{ugCategoriesHierPage} in Section \ugCategoriesHierNumber\ignore{ugCategoriesHier}.
Here now is its complete \Language{} definition.

\beginImportant
  
\noindent
{\tt 1.\ \ \ SemiGroup():\ Category\ ==\ SetCategory\ with}\newline
{\tt 2.\ \ \ \ \ \ \ \ \ "*":\ (\$,\ \$)\ ->\ \$}\newline
{\tt 3.\ \ \ \ \ \ \ \ \ "**":\ (\$,\ PositiveInteger)\ ->\ \$}\newline
{\tt 4.\ \ \ \ \ \ \ add}\newline
{\tt 5.\ \ \ \ \ \ \ \ \ import\ RepeatedSquaring(\$)}\newline
{\tt 6.\ \ \ \ \ \ \ \ \ x:\ \$\ **\ n:\ PositiveInteger\ ==\ expt(x,n)}\newline
\endImportant

The \spad{add} part at the end is used to give ``default definitions'' for
\spadkey{add}
exported operations.
Once you have a multiplication operation \spadop{*}, you can
define exponentiation
for positive integer exponents
using repeated multiplication:
\centerline{{\spad{x ** n = x * x * ... * x}   ( \spad{n} copies of \spad{x} )}}
This definition for \spadop{**} is called a {\it default} definition.
In general, a category can give default definitions for any
operation it exports.
Since \spadtype{SemiGroup} and all its category descendants in the hierarchy
export \spadop{**}, any descendant category may redefine \spadop{**} as well.

A domain of category \spadtype{SemiGroup}
(such as \spadtype{Integer}) may or may not choose to
define its own \spadop{**} operation.
If it does not, a default definition that is closest (in a ``tree-distance''
sense of the hierarchy) to the domain is chosen.

The part of the category definition following an \spadop{add} operation
is a \spadgloss{capsule}, as discussed in
\texht{the previous chapter.}{\downlink{``\ugPackagesTitle''}{ugPackagesPage} in Chapter \ugPackagesNumber\ignore{ugPackages}.}
The line
\begin{verbatim}
import RepeatedSquaring($)
\end{verbatim}
references the package
\spadtype{RepeatedSquaring(\$)}, that is, the package
\spadtype{RepeatedSquaring} that takes ``this domain'' as its
parameter.
For example, if the semigroup \spadtype{Polynomial (Integer)}
does not define its own exponentiation operation, the
definition used may come from the package
\spadtype{RepeatedSquaring (Polynomial (Integer))}.
The next line gives the definition in terms of \spadfun{expt} from that
package.

The default definitions are collected to form a ``default
package'' for the category.
The name of the package is the same as  the category but with an
ampersand (\spadSyntax{\&}) added at the end.
A default package always takes an additional argument relative to the
category.
Here is the definition of the default package \pspadtype{SemiGroup\&} as
automatically generated by \Language{} from the above definition of
\spadtype{SemiGroup}.

\beginImportant
  
\noindent
{\tt 1.\ \ \ SemiGroup\_\&(\$):\ Exports\ ==\ Implementation\ where}\newline
{\tt 2.\ \ \ \ \ \$:\ SemiGroup}\newline
{\tt 3.\ \ \ \ \ Exports\ ==\ with}\newline
{\tt 4.\ \ \ \ \ \ \ "**":\ (\$,\ PositiveInteger)\ ->\ \$}\newline
{\tt 5.\ \ \ \ \ Implementation\ ==\ add}\newline
{\tt 6.\ \ \ \ \ \ \ import\ RepeatedSquaring(\$)}\newline
{\tt 7.\ \ \ \ \ \ \ x:\$\ **\ n:PositiveInteger\ ==\ expt(x,n)}\newline
\endImportant

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugCategoriesAxiomsTitle}{Axioms}
\newcommand{\ugCategoriesAxiomsNumber}{12.7.}
%
% =====================================================================
\begin{page}{ugCategoriesAxiomsPage}{12.7. Axioms}
% =====================================================================
\beginscroll

In \texht{the previous section}{\downlink{``\ugCategoriesDefaultsTitle''}{ugCategoriesDefaultsPage} in Section \ugCategoriesDefaultsNumber\ignore{ugCategoriesDefaults}} you saw the
complete \Language{} program defining \index{axiom}
\spadtype{SemiGroup}.
According to this definition, semigroups (that is, are sets with
the operations \spadopFrom{*}{SemiGroup} and
\spadopFrom{**}{SemiGroup}.
%-% \HDexptypeindex{SemiGroup}{ugCategoriesAxiomsPage}{12.7.}{Axioms}

You might ask: ``Aside from the notion of default packages, isn't
a category just a \spadgloss{macro}, that is, a shorthand
equivalent to the two operations \spadop{*} and \spadop{**} with
their types?'' If a category were a macro, every time you saw the
word \spadtype{SemiGroup}, you would rewrite it by its list of
exported operations.
Furthermore, every time you saw the exported operations of
\spadtype{SemiGroup} among the exports of a constructor, you could
conclude that the constructor exported \spadtype{SemiGroup}.

A category is {\it not} a macro and here is why.
The definition for \spadtype{SemiGroup} has documentation that states:

\texht{\begin{quotation}}{\indent{3}}
    Category \spadtype{SemiGroup} denotes the class of all multiplicative
    semigroups, that is, a set with an associative operation \spadop{*}.

    \texht{\vskip .5\baselineskip}{}
    {Axioms:}

    {\small\tt associative("*" : (\$,\$)->\$) -- (x*y)*z = x*(y*z)}
\texht{\end{quotation}}{\indent{3}}

According to the author's remarks, the mere
exporting of an operation named \spadop{*} and \spadop{**} is not
enough to qualify the domain as a \spadtype{SemiGroup}.
In fact, a domain can be a semigroup only if it explicitly
exports a \spadop{**} and
a \spadop{*} satisfying the associativity axiom.

In general, a category name implies a set of axioms, even mathematical
theorems.
There are numerous axioms from \spadtype{Ring}, for example,
that are well-understood from the literature.
No attempt is made to list them all.
Nonetheless, all such mathematical facts are implicit by the use of the
name \spadtype{Ring}.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugCategoriesCorrectnessTitle}{Correctness}
\newcommand{\ugCategoriesCorrectnessNumber}{12.8.}
%
% =====================================================================
\begin{page}{ugCategoriesCorrectnessPage}{12.8. Correctness}
% =====================================================================
\beginscroll

While such statements are only comments,
%-% \HDindex{correctness}{ugCategoriesCorrectnessPage}{12.8.}{Correctness}
\Language{} can enforce their intention simply by shifting the burden of
responsibility onto the author of a domain.
A domain belongs to category \spad{Ring} only if the
author asserts that the domain  belongs to \spadtype{Ring} or
to a category that extends \spadtype{Ring}.

This principle of assertion is important for large user-extendable
systems.
\Language{} has a large library of operations offering facilities in
many areas.
Names such as \spadfun{norm} and \spadfun{product}, for example, have
diverse meanings in diverse contexts.
An inescapable hindrance to users would be to force those who wish to
extend \Language{} to always invent new names for operations.
%>> I don't think disambiguate is really a word, though I like it
\Language{} allows you to reuse names, and then use context to disambiguate one
from another.

Here is another example of why this is important.
Some languages, such as {\bf APL},
%-% \HDindex{APL}{ugCategoriesCorrectnessPage}{12.8.}{Correctness}
denote the \spadtype{Boolean} constants \spad{true} and
\spad{false} by the integers \spad{1} and \spad{0}.
You may want to let infix operators \spadop{+} and \spadop{*} serve as the logical
operators \spadfun{or} and \spadfun{and}, respectively.
But note this: \spadtype{Boolean} is not a ring.
The {\it inverse axiom} for \spadtype{Ring} states:
%
\centerline{{Every element \spad{x} has an additive inverse \spad{y} such that}}
\centerline{{\spad{x + y = 0}.}}
%
\spadtype{Boolean} is not a ring since \spad{true} has
no inverse---there is no inverse element \spad{a} such that
\spad{1 + a = 0} (in terms of booleans, \spad{(true or a) = false}).
Nonetheless, \Language{} {\it could} easily and correctly implement
\spadtype{Boolean} this way.
\spadtype{Boolean} simply would not assert that it is of category
\spadtype{Ring}.
Thus the \spadop{+} for \spadtype{Boolean} values
is not confused with the one for \spadtype{Ring}.
Since the \spadtype{Polynomial} constructor requires its argument
to be a ring, \Language{} would then refuse to build the
domain \spadtype{Polynomial(Boolean)}. Also, \Language{} would refuse to
wrongfully apply algorithms to \spadtype{Boolean} elements that  presume that the
ring axioms for \spadop{+} hold.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugCategoriesAttributesTitle}{Attributes}
\newcommand{\ugCategoriesAttributesNumber}{12.9.}
%
% =====================================================================
\begin{page}{ugCategoriesAttributesPage}{12.9. Attributes}
% =====================================================================
\beginscroll

Most axioms are not computationally useful.
Those that are can be explicitly expressed by what \Language{} calls an
\spadgloss{attribute}.
The attribute \spadatt{commutative("*")}, for example, is used to assert
that a domain has commutative multiplication.
Its definition is given by its documentation:

\texht{\begingroup \parindent=1pc \narrower\noindent}{\indent{3}}%
    A domain \spad{R} has \spadatt{commutative("*")}
    if it has an operation "*": \spadsig{(R,R)}{R} such that \spad{x * y = y * x}.
\texht{\par\endgroup}{\indent{0}}

Just as you can test whether a domain has the category \spadtype{Ring}, you
can test that a domain has a given attribute.

\xtc{
Do polynomials over the integers
have commutative multiplication?
}{
\spadpaste{Polynomial Integer has commutative("*")}
}
\xtc{
Do matrices over the integers
have commutative multiplication?
}{
\spadpaste{Matrix Integer has commutative("*")}
}

Attributes are used to conditionally export and define
operations for a domain (see \downlink{``\ugDomainsAssertionsTitle''}{ugDomainsAssertionsPage} in Section \ugDomainsAssertionsNumber\ignore{ugDomainsAssertions}).
Attributes can also be asserted in a category definition.

After mentioning category \spadtype{Ring} many times in this book,
it is high time that we show you its definition:
%-% \HDexptypeindex{Ring}{ugCategoriesAttributesPage}{12.9.}{Attributes}

\beginImportant
  
\noindent
{\tt 1.\ \ \ Ring():\ Category\ ==}\newline
{\tt 2.\ \ \ \ \ Join(Rng,Monoid,LeftModule(\$:\ Rng))\ with}\newline
{\tt 3.\ \ \ \ \ \ \ \ \ characteristic:\ ->\ NonNegativeInteger}\newline
{\tt 4.\ \ \ \ \ \ \ \ \ coerce:\ Integer\ ->\ \$}\newline
{\tt 5.\ \ \ \ \ \ \ \ \ unitsKnown}\newline
{\tt 6.\ \ \ \ \ \ \ add}\newline
{\tt 7.\ \ \ \ \ \ \ \ \ n:Integer}\newline
{\tt 8.\ \ \ \ \ \ \ \ \ coerce(n)\ ==\ n\ *\ 1\$\$}\newline
\endImportant

There are only two new things here.
First, look at the \spadSyntax{\$\$} on the last line.
This is not a typographic error!
The first \spadSyntax{\$} says that the \spad{1} is to come from some
domain.
The second \spadSyntax{\$} says that the domain is ``this domain.''
If \spadSyntax{\$} is \spadtype{Fraction(Integer)}, this line reads {\tt
coerce(n) == n * 1\$Fraction(Integer)}.

The second new thing is the presence of attribute ``\spad{unitsKnown}''.
\Language{} can always distinguish an attribute from an operation.
An operation has a name and a type. An attribute has no type.
The attribute \spadatt{unitsKnown} asserts a rather subtle mathematical
fact that is normally taken for granted when working with
rings.\footnote{With this axiom, the units of a domain are the set of
elements \spad{x} that each have a multiplicative
inverse \spad{y} in the domain.
Thus \spad{1} and \spad{-1} are units in domain \spadtype{Integer}.
Also, for \spadtype{Fraction Integer}, the domain of rational numbers,
all non-zero elements are units.}
Because programs can test for this attribute, \Language{} can
correctly handle rather more complicated mathematical structures (ones
that are similar to rings but do not have this attribute).

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugCategoriesParametersTitle}{Parameters}
\newcommand{\ugCategoriesParametersNumber}{12.10.}
%
% =====================================================================
\begin{page}{ugCategoriesParametersPage}{12.10. Parameters}
% =====================================================================
\beginscroll

Like domain constructors, category constructors can also have
parameters.
For example, category \spadtype{MatrixCategory} is a parameterized
category for defining matrices over a ring \spad{R} so that the
matrix domains can have
different representations and indexing schemes.
Its definition has the form:

\beginImportant
  
\noindent
{\tt 1.\ \ \ MatrixCategory(R,Row,Col):\ Category\ ==}\newline
{\tt 2.\ \ \ \ \ \ \ TwoDimensionalArrayCategory(R,Row,Col)\ with\ ...}\newline
\endImportant

The category extends \spadtype{TwoDimensionalArrayCategory} with
the same arguments.
You cannot find \spadtype{TwoDimensionalArrayCategory} in the
algebraic hierarchy listing.
Rather, it is a member of the data structure hierarchy,
given inside the back cover of this book.
In particular, \spadtype{TwoDimensionalArrayCategory} is an extension of
\spadtype{HomogeneousAggregate} since its elements are all one type.

The domain \spadtype{Matrix(R)}, the class of matrices with coefficients
from domain \spad{R}, asserts that it is a member of category
\spadtype{MatrixCategory(R, Vector(R), Vector(R))}.
The parameters of a category must also have types.
The first parameter to \spadtype{MatrixCategory}
\spad{R} is required to be a ring.
The second and third are required to be domains of category
\spadtype{FiniteLinearAggregate(R)}.\footnote{%
This is another extension of
\spadtype{HomogeneousAggregate} that you can see in
the data structure hierarchy.}
In practice, examples of categories having parameters other than
domains are rare.

Adding the declarations for parameters to the definition for
\spadtype{MatrixCategory}, we have:

\beginImportant
  
\noindent
{\tt 1.\ \ \ R:\ Ring}\newline
{\tt 2.\ \ \ (Row,\ Col):\ FiniteLinearAggregate(R)}\newline
{\tt 3.\ \ \ }\newline
{\tt 4.\ \ \ MatrixCategory(R,\ Row,\ Col):\ Category\ ==}\newline
{\tt 5.\ \ \ \ \ \ \ TwoDimensionalArrayCategory(R,\ Row,\ Col)\ with\ ...}\newline
\endImportant

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugCategoriesConditionalsTitle}{Conditionals}
\newcommand{\ugCategoriesConditionalsNumber}{12.11.}
%
% =====================================================================
\begin{page}{ugCategoriesConditionalsPage}{12.11. Conditionals}
% =====================================================================
\beginscroll

As categories have parameters, the actual operations exported by a
%-% \HDindex{conditional}{ugCategoriesConditionalsPage}{12.11.}{Conditionals}
category can depend on these parameters.
As an example, the operation \spadfunFrom{determinant}{MatrixCategory}
from category \spadtype{MatrixCategory} is only exported when the
underlying domain \spad{R} has commutative multiplication:

\begin{verbatim}
if R has commutative("*") then
   determinant: $ -> R
\end{verbatim}

Conditionals can also define conditional extensions of a category.
Here is a portion of the definition of \spadtype{QuotientFieldCategory}:
%-% \HDexptypeindex{QuotientFieldCategory}{ugCategoriesConditionalsPage}{12.11.}{Conditionals}

\beginImportant
  
\noindent
{\tt 1.\ \ \ QuotientFieldCategory(R)\ :\ Category\ ==\ ...\ with\ ...}\newline
{\tt 2.\ \ \ \ \ \ \ \ if\ R\ has\ OrderedSet\ then\ OrderedSet}\newline
{\tt 3.\ \ \ \ \ \ \ \ if\ R\ has\ IntegerNumberSystem\ then}\newline
{\tt 4.\ \ \ \ \ \ \ \ \ \ ceiling:\ \$\ ->\ R}\newline
{\tt 5.\ \ \ \ \ \ \ \ \ \ \ \ ...}\newline
\endImportant

Think of category \spadtype{QuotientFieldCategory(R)} as
denoting the domain \spadtype{Fraction(R)}, the
class of all fractions of the form \smath{a/b} for elements of \spad{R}.
The first conditional means in English:
``If the elements of \spad{R} are totally ordered (\spad{R}
is an \spadtype{OrderedSet}), then so are the fractions \smath{a/b}''.
%-% \HDexptypeindex{Fraction}{ugCategoriesConditionalsPage}{12.11.}{Conditionals}

The second conditional is used to conditionally export an
operation \spadfun{ceiling} which returns the smallest integer
greater than or equal to its argument.
Clearly, ``ceiling'' makes sense for integers but not for
polynomials and other algebraic structures.
Because of this conditional,
the domain \spadtype{Fraction(Integer)} exports
an operation
\spadfun{ceiling}: \spadsig{Fraction Integer}{Integer}, but
\spadtype{Fraction Polynomial Integer} does not.

Conditionals can also appear in the default definitions for the
operations of a category.
For example, a default definition for \spadfunFrom{ceiling}{Field}
within the part following the \spadop{add} reads:

\begin{verbatim}
if R has IntegerNumberSystem then
    ceiling x == ...
\end{verbatim}

Here the predicate used is identical to the predicate
in the {\tt Exports} part.
This need not be the case.
See \downlink{``\ugPackagesCondsTitle''}{ugPackagesCondsPage} in Section \ugPackagesCondsNumber\ignore{ugPackagesConds} for a more complicated example.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugCategoriesAndPackagesTitle}{Anonymous Categories}
\newcommand{\ugCategoriesAndPackagesNumber}{12.12.}
%
% =====================================================================
\begin{page}{ugCategoriesAndPackagesPage}{12.12. Anonymous Categories}
% =====================================================================
\beginscroll

The part of a category to the right of a {\tt with} is also
regarded as a category---an ``anonymous category.''
Thus you have already seen a   category definition
%-% \HDindex{category!anonymous}  in \chapref{ugPackages}.{ugCategoriesAndPackagesPage}{12.12.}{Anonymous Categories}
The {\tt Exports} part of the package \pspadtype{DrawComplex}
(\downlink{``\ugPackagesAbstractTitle''}{ugPackagesAbstractPage} in Section \ugPackagesAbstractNumber\ignore{ugPackagesAbstract}) is an anonymous category.
This is not necessary.
We could, instead, give this category a name:

%
\beginImportant
  
\noindent
{\tt 1.\ \ \ DrawComplexCategory():\ Category\ ==\ with}\newline
{\tt 2.\ \ \ \ \ \ drawComplex:\ (C\ ->\ C,S,S,Boolean)\ ->\ VIEW3D}\newline
{\tt 3.\ \ \ \ \ \ drawComplexVectorField:\ (C\ ->\ C,S,S)\ ->\ VIEW3D}\newline
{\tt 4.\ \ \ \ \ \ setRealSteps:\ INT\ ->\ INT}\newline
{\tt 5.\ \ \ \ \ \ setImagSteps:\ INT\ ->\ INT}\newline
{\tt 6.\ \ \ \ \ \ setClipValue:\ DFLOAT->\ DFLOAT}\newline
\endImportant
%
and then define \spadtype{DrawComplex} by:
%
\beginImportant
  
\noindent
{\tt 1.\ \ \ DrawComplex():\ DrawComplexCategory\ ==\ Implementation}\newline
{\tt 2.\ \ \ \ \ \ where}\newline
{\tt 3.\ \ \ \ \ \ \ \ \ ...}\newline
\endImportant
%

There is no reason, however, to give this list of exports a name
since no other domain or package exports it.
In fact, it is rare for a package to export a named category.
As you will see in the next chapter, however, it is very common
for the definition of domains to mention one or more category
before the {\tt with}.
\spadkey{with}
\endscroll
\autobuttons
\end{page}
%