1 2% Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. 3% All rights reserved. 4% 5% Redistribution and use in source and binary forms, with or without 6% modification, are permitted provided that the following conditions are 7% met: 8% 9% - Redistributions of source code must retain the above copyright 10% notice, this list of conditions and the following disclaimer. 11% 12% - Redistributions in binary form must reproduce the above copyright 13% notice, this list of conditions and the following disclaimer in 14% the documentation and/or other materials provided with the 15% distribution. 16% 17% - Neither the name of The Numerical ALgorithms Group Ltd. nor the 18% names of its contributors may be used to endorse or promote products 19% derived from this software without specific prior written permission. 20% 21% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 22% IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 23% TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 24% PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 25% OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 26% EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 27% PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES-- LOSS OF USE, DATA, OR 28% PROFITS-- OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 29% LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 30% NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 31% SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 33 34% ********************************************************************* 35\head{chapter}{Categories}{ugCategories} 36% ********************************************************************* 37 38This chapter unravels the mysteries of categories---what 39\index{category} 40they are, how they are related to domains and packages, 41\index{category!constructor} 42how they are defined in \Language{}, and how you can extend the 43\index{constructor!category} 44system to include new categories of your own. 45 46We assume that you have read the introductory material on domains 47and categories in \spadref{ugTypesBasicDomainCons}. 48There you learned that the notion of packages covered in the 49previous chapter are special cases of domains. 50While this is in fact the case, it is useful here to regard domains 51as distinct from packages. 52 53Think of a domain as a datatype, a collection of objects (the 54objects of the domain). 55From your ``sneak preview'' in the previous chapter, you might 56conclude that categories are simply named clusters of operations 57exported by domains. 58As it turns out, categories have a much deeper meaning. 59Categories are fundamental to the design of \Language{}. 60They control the interactions between domains and algorithmic 61packages, and, in fact, between all the components of \Language{}. 62 63Categories form hierarchies as shown on the inside cover pages of 64this book. 65The inside front-cover pages illustrate the basic 66algebraic hierarchy of the \Language{} programming language. 67The inside back-cover pages show the hierarchy for data 68structures. 69 70Think of the category structures of \Language{} as a foundation 71for a city on which superstructures (domains) are built. 72The algebraic hierarchy, for example, serves as a foundation for 73constructive mathematical algorithms embedded in the domains of 74\Language{}. 75Once in place, domains can be constructed, either independently or 76from one another. 77 78Superstructures are built for quality---domains are compiled into 79machine code for run-time efficiency. 80You can extend the foundation in directions beyond the space 81directly beneath the superstructures, then extend selected 82superstructures to cover the space. 83Because of the compilation strategy, changing components of the 84foundation generally means that the existing superstructures 85(domains) built on the changed parts of the foundation 86(categories) have to be rebuilt---that is, recompiled. 87 88Before delving into some of the interesting facts about categories, let's see 89how you define them in \Language{}. 90 91% ********************************************************************* 92\head{section}{Definitions}{ugCategoriesDefs} 93% ********************************************************************* 94 95A category is defined by a function with exactly the same format as 96\index{category!definition} 97any other function in \Language{}. 98 99% ---------------------------------------------------------------------- 100\beginImportant 101The definition of a category has the syntax: 102\begin{center} 103{\it CategoryForm} : {\tt Category\quad{}==\quad{}} {\it Extensions} {\tt [ with} {\it Exports} {\tt ]} 104\end{center} 105 106The brackets {\tt [ ]} here indicate optionality. 107\endImportant 108% ---------------------------------------------------------------------- 109 110 111The first example of a category definition is 112\spadtype{SetCategory}, 113the most basic of the algebraic categories in \Language{}. 114\exptypeindex{SetCategory} 115 116\begin{xmpLines} 117SetCategory(): Category == 118 Join(Type,CoercibleTo OutputForm) with 119 "=" : (%, %) -> Boolean 120\end{xmpLines} 121 122The definition starts off with the name of the 123category (\spadtype{SetCategory}); this is 124always in column one in the source file. 125%% maybe talk about naming conventions for source files? .spad or .ax? 126All parts of a category definition are then indented with respect to this 127\index{indentation} 128first line. 129 130In \chapref{ugTypes}, we talked about \spadtype{Ring} as denoting the 131class of all domains that are rings, in short, the class of all 132rings. 133While this is the usual naming convention in \Language{}, it is also 134common to use the word ``Category'' at the end of a category name for clarity. 135The interpretation of the name \spadtype{SetCategory} is, then, ``the 136category of all domains that are (mathematical) sets.'' 137 138The name \spadtype{SetCategory} is followed in the definition by its 139formal parameters enclosed in parentheses \spadSyntax{()}. 140Here there are no parameters. 141As required, the type of the result of this category function is the 142distinguished name {\sf Category}. 143 144Then comes the \spadSyntax{==}. 145As usual, what appears to the right of the \spadSyntax{==} is a 146definition, here, a category definition. 147A category definition always has two parts separated by the reserved word 148\spadkey{with} 149\spad{with}. 150%\footnote{Debugging hint: it is very easy to forget 151%the \spad{with}!} 152 153The first part tells what categories the category extends. 154Here, the category extends two categories: \spadtype{Type}, the 155category of all domains, and 156\spadtype{CoercibleTo(OutputForm)}. 157%\footnote{\spadtype{CoercibleTo(OutputForm)} 158%can also be written (and is written in the definition above) without 159%parentheses.} 160The operation \spadtype{Join} is a system-defined operation that 161\spadkey{Join} 162forms a single category from two or more other categories. 163 164Every category other than \spadtype{Type} is an extension of some other 165category. 166If, for example, \spadtype{SetCategory} extended only the category 167\spadtype{Type}, the definition here would read ``{\tt Type with 168...}''. 169In fact, the {\tt Type} is optional in this line; ``{\tt with 170...}'' suffices. 171 172% ********************************************************************* 173\head{section}{Exports}{ugCategoriesExports} 174% ********************************************************************* 175 176To the right of the \spad{with} is a list of 177\spadkey{with} 178all the \spadglossSee{exports}{export} of the category. 179Each exported operation has a name and a type expressed by a 180\spadgloss{declaration} of the form 181``{\frenchspacing\tt {\it name}: {\it type}}''. 182 183Categories can export symbols, as well as 184{\tt 0} and {\tt 1} which denote 185domain constants.\footnote{The 186numbers {\tt 0} and {\tt 1} are operation names in \Language{}.} 187In the current implementation, all other exports are operations with 188types expressed as \spadglossSee{mappings}{mapping} with the syntax 189\begin{center} 190{\it 191source\quad\spad{->}\quad target 192} 193\end{center} 194 195The category \spadtype{SetCategory} has a single export: the operation 196\spadop{=} whose type is given by the mapping \spad{(%, %) -> Boolean}. 197The \spadSyntax{%} in a mapping type always means ``the domain.'' Thus 198the operation \spadop{=} takes two arguments from the domain and 199returns a value of type \spadtype{Boolean}. 200 201The source part of the mapping here is given by a {\it tuple} 202\index{tuple} 203consisting of two or more types separated by commas and enclosed in 204parentheses. 205If an operation takes only one argument, you can drop the parentheses 206around the source type. 207If the mapping has no arguments, the source part of the mapping is either 208left blank or written as \spadSyntax{()}. 209Here are examples of formats of various operations with some 210contrived names. 211 212\begin{verbatim} 213someIntegerConstant : % 214aZeroArgumentOperation: () -> Integer 215aOneArgumentOperation: Integer -> % 216aTwoArgumentOperation: (Integer,%) -> Void 217aThreeArgumentOperation: (%,Integer,%) -> Fraction(%) 218\end{verbatim} 219 220% ********************************************************************* 221\head{section}{Documentation}{ugCategoriesDoc} 222% ********************************************************************* 223 224The definition of \spadtype{SetCategory} above is missing 225an important component: its library documentation. 226\index{documentation} 227Here is its definition, complete with documentation. 228 229\begin{xmpLines} 230++ Description: 231++ \spadtype{SetCategory} is the basic category 232++ for describing a collection of elements with 233++ \spadop{=} (equality) and a \spadfun{coerce} 234++ to \spadtype{OutputForm}. 235 236SetCategory(): Category == 237 Join(Type, CoercibleTo OutputForm) with 238 "=": (%, %) -> Boolean 239 ++ \spad{x = y} tests if \spad{x} and 240 ++ \spad{y} are equal. 241\end{xmpLines} 242 243Documentary comments are an important part of constructor definitions. 244Documentation is given both for the category itself and for 245each export. 246A description for the category precedes the code. 247Each line of the description begins in column one with \spadSyntax{++}. 248The description starts with the word {\tt Description:}.\footnote{Other 249information such as the author's name, date of creation, and so on, 250can go in this 251area as well but are currently ignored by \Language{}.} 252All lines of the description following the initial line are 253indented by the same amount. 254 255{\texht{\sloppy}{} 256Mark the name of any constructor (with or without parameters) with 257\cs{spadtype} like this 258\begin{verbatim} 259\spadtype{Polynomial(Integer)} 260\end{verbatim} 261Similarly, mark an 262operator name with \cs{spadop}, 263a \Language{} operation (function) with \cs{spadfun}, and a 264variable or \Language{} expression with 265\cs{spad}. 266Library documentation is given in a \TeX{}-like language so that 267it can be used both for hard-copy and for \Browse{}. 268These different wrappings cause operations and types to have 269mouse-active buttons in \Browse{}. 270For hard-copy output, wrapped expressions appear in a different font. 271The above documentation appears in hard-copy as: 272 273} 274% 275\texht{\begin{quotation}}{\indent{3}} 276% 277\spadtype{SetCategory} is the basic category 278for describing a collection of elements with \spadop{=} 279(equality) and a \spadfun{coerce} to \spadtype{OutputForm}. 280% 281\texht{\end{quotation}}{\indent{0}} 282% 283and 284% 285\texht{\begin{quotation}}{\indent{3}} 286% 287\spad{x = y} tests if \spad{x} and \spad{y} are equal. 288% 289\texht{\end{quotation}}{\indent{0}} 290% 291 292For our purposes in this chapter, we omit the documentation from further 293category descriptions. 294 295% ********************************************************************* 296\head{section}{Hierarchies}{ugCategoriesHier} 297% ********************************************************************* 298 299A second example of a category is 300\spadtype{SemiGroup}, defined by: 301\exptypeindex{SemiGroup} 302 303\begin{xmpLines} 304SemiGroup(): Category == SetCategory with 305 "*": (%,%) -> % 306 "^": (%, PositiveInteger) -> % 307\end{xmpLines} 308 309This definition is as simple as that for \spadtype{SetCategory}, 310except that there are two exported operations. 311Multiple exported operations are written as a \spadgloss{pile}, 312that is, they all begin in the same column. 313Here you see that the category mentions another type, 314\spadtype{PositiveInteger}, in a signature. 315Any domain can be used in a signature. 316 317Since categories extend one another, they form hierarchies. 318Each category other than \spadtype{Type} has one or more parents given 319by the one or more categories mentioned before the \spad{with} part of 320the definition. 321\spadtype{SemiGroup} extends \spadtype{SetCategory} and 322\spadtype{SetCategory} extends both \spadtype{Type} and 323\spadtype{CoercibleTo (OutputForm)}. 324Since \spadtype{CoercibleTo (OutputForm)} also extends \spadtype{Type}, 325the mention of \spadtype{Type} in the definition is unnecessary but 326included for emphasis. 327 328% ********************************************************************* 329\head{section}{Membership}{ugCategoriesMembership} 330% ********************************************************************* 331 332We say a category designates a class of domains. 333What class of domains? 334\index{category!membership} 335That is, how does \Language{} know what domains belong to what categories? 336The simple answer to this basic question is key to the design of 337\Language{}: 338 339\beginImportant 340\begin{center} 341{\bf Domains belong to categories by assertion.} 342\end{center} 343\endImportant 344 345When a domain is defined, it is asserted to belong to one or more 346categories. 347Suppose, for example, that an author of domain \spadtype{String} wishes to 348use the binary operator \spadop{*} to denote concatenation. 349Thus \spad{"hello " * "there"} would produce the string 350\spad{"hello there"}\footnote{Actually, concatenation of strings in 351\Language{} is done by juxtaposition or by using the operation 352\spadfunFrom{concat}{String}. 353The expression \spad{"hello " "there"} produces the string 354\spad{"hello there"}.}. 355The author of \spadtype{String} could then assert that \spadtype{String} 356is a member of \spadtype{SemiGroup}. 357According to our definition of \spadtype{SemiGroup}, strings 358would then also have the operation \spadop{^} defined automatically. 359Then \spad{"--" ^ 4} would produce a string of eight dashes 360\spad{"--------"}. 361Since \spadtype{String} is a member of \spadtype{SemiGroup}, it also is 362a member of \spadtype{SetCategory} and thus has an operation 363\spadop{=} for testing that two strings are equal. 364 365\begin{texonly} 366 Now turn to the algebraic category hierarchy inside the front cover 367 of this book. 368\end{texonly} 369Any domain that is a member of a 370category extending \spadtype{SemiGroup} is a member of 371\spadtype{SemiGroup} (that is, it {\it is} a semigroup). 372In particular, any domain asserted to be a \spadtype{Ring} is a 373semigroup since \spadtype{Ring} extends \spadtype{Monoid}, that, 374in turn, extends \spadtype{SemiGroup}. 375The definition of \spadtype{Integer} in \Language{} asserts that 376\spadtype{Integer} is a member of category 377\spadtype{IntegerNumberSystem}, that, in turn, asserts that it is 378a member of \spadtype{EuclideanDomain}. 379Now \spadtype{EuclideanDomain} extends 380\spadtype{PrincipalIdealDomain} and so on. 381If you trace up the hierarchy, you see that 382\spadtype{EuclideanDomain} extends \spadtype{Ring}, and, 383therefore, \spadtype{SemiGroup}. 384Thus \spadtype{Integer} is a semigroup and also exports the 385operations \spadop{*} and \spadop{^}. 386 387% ********************************************************************* 388\head{section}{Defaults}{ugCategoriesDefaults} 389% ********************************************************************* 390 391We actually omitted the last 392\index{category!defaults} 393part of the definition of 394\index{default definitions} 395\spadtype{SemiGroup} in 396\spadref{ugCategoriesHier}. 397Here now is its complete \Language{} definition. 398 399\begin{xmpLines} 400SemiGroup(): Category == SetCategory with 401 "*": (%, %) -> % 402 "^": (%, PositiveInteger) -> % 403 add 404 import RepeatedSquaring(%) 405 x: % ^ n: PositiveInteger == expt(x,n) 406\end{xmpLines} 407 408The \spad{add} part at the end is used to give ``default definitions'' for 409\spadkey{add} 410exported operations. 411Once you have a multiplication operation \spadop{*}, you can 412define exponentiation 413for positive integer exponents 414using repeated multiplication: 415\begin{texonly} 416\begin{displaymath} 417x^n = {\underbrace{x \, x \, x \, \cdots \, x}_{\displaystyle n \hbox{\ times}}} 418\end{displaymath} 419\end{texonly}% 420\begin{htonly} 421\begin{center} 422\spad{x ^ n = x * x * ... * x} ( \spad{n} copies of \spad{x} ) 423\end{center} 424\end{htonly} 425This definition for \spadop{^} is called a {\it default} definition. 426In general, a category can give default definitions for any 427operation it exports. 428Since \spadtype{SemiGroup} and all its category descendants in the hierarchy 429export \spadop{^}, any descendant category may redefine \spadop{^} as well. 430 431A domain of category \spadtype{SemiGroup} 432(such as \spadtype{Integer}) may or may not choose to 433define its own \spadop{^} operation. 434If it does not, a default definition that is closest (in a ``tree-distance'' 435sense of the hierarchy) to the domain is chosen. 436 437The part of the category definition following an \spadSyntax{add} operation 438is a \spadgloss{capsule}, as discussed in 439\texht{the previous chapter.}{\chapref{ugPackages}.} 440The line 441\begin{verbatim} 442import RepeatedSquaring(%) 443\end{verbatim} 444references the package 445\spadtype{RepeatedSquaring(%)}, that is, the package 446\spadtype{RepeatedSquaring} that takes ``this domain'' as its 447parameter. 448For example, if the semigroup \spadtype{Polynomial (Integer)} 449does not define its own exponentiation operation, the 450definition used may come from the package 451\spadtype{RepeatedSquaring (Polynomial (Integer))}. 452The next line gives the definition in terms of \spadfun{expt} from that 453package. 454 455The default definitions are collected to form a ``default 456package'' for the category. 457The name of the package is the same as the category but with an 458ampersand (\spadSyntax{&}) added at the end. 459A default package always takes an additional argument relative to the 460category. 461Here is the definition of the default package \pspadtype{SemiGroup&} as 462automatically generated by \Language{} from the above definition of 463\spadtype{SemiGroup}. 464 465\begin{xmpLines} 466SemiGroup_&(%): Exports == Implementation where 467 %: SemiGroup 468 Exports == with 469 "^": (%, PositiveInteger) -> % 470 Implementation == add 471 import RepeatedSquaring(%) 472 x:% ^ n:PositiveInteger == expt(x,n) 473\end{xmpLines} 474 475% ********************************************************************* 476\head{section}{Axioms}{ugCategoriesAxioms} 477% ********************************************************************* 478 479In \texht{the previous section}{\spadref{ugCategoriesDefaults}} you saw the 480complete \Language{} program defining \index{axiom} 481\spadtype{SemiGroup}. 482According to this definition, semigroups (that is, are sets with 483the operations \spadopFrom{*}{SemiGroup} and 484\spadopFrom{^}{SemiGroup}. 485\exptypeindex{SemiGroup} 486 487You might ask: ``Aside from the notion of default packages, isn't 488a category just a \spadgloss{macro}, that is, a shorthand 489equivalent to the two operations \spadop{*} and \spadop{^} with 490their types?'' If a category were a macro, every time you saw the 491word \spadtype{SemiGroup}, you would rewrite it by its list of 492exported operations. 493Furthermore, every time you saw the exported operations of 494\spadtype{SemiGroup} among the exports of a constructor, you could 495conclude that the constructor exported \spadtype{SemiGroup}. 496 497A category is {\it not} a macro and here is why. 498The definition for \spadtype{SemiGroup} has documentation that states: 499 500\texht{\begin{quotation}}{\indent{3}} 501 Category \spadtype{SemiGroup} denotes the class of all multiplicative 502 semigroups, that is, a set with an associative operation \spadop{*}. 503 504 \texht{\vskip .5\baselineskip}{} 505 {Axioms:} 506 507 {\small\spad{associative("*" : (%,%)->%)} \quad\quad\quad \spad{(x*y)*z = x*(y*z)}} 508\texht{\end{quotation}}{\indent{3}} 509 510According to the author's remarks, the mere 511exporting of an operation named \spadop{*} and \spadop{^} is not 512enough to qualify the domain as a \spadtype{SemiGroup}. 513In fact, a domain can be a semigroup only if it explicitly 514exports a \spadop{^} and 515a \spadop{*} satisfying the associativity axiom. 516 517In general, a category name implies a set of axioms, even mathematical 518theorems. 519There are numerous axioms from \spadtype{Ring}, for example, 520that are well-understood from the literature. 521No attempt is made to list them all. 522Nonetheless, all such mathematical facts are implicit by the use of the 523name \spadtype{Ring}. 524 525% ********************************************************************* 526\head{section}{Correctness}{ugCategoriesCorrectness} 527% ********************************************************************* 528 529While such statements are only comments, 530\index{correctness} 531\Language{} can enforce their intention simply by shifting the burden of 532responsibility onto the author of a domain. 533A domain belongs to category \spadtype{Ring} only if the 534author asserts that the domain belongs to \spadtype{Ring} or 535to a category that extends \spadtype{Ring}. 536 537This principle of assertion is important for large user-extendable 538systems. 539\Language{} has a large library of operations offering facilities in 540many areas. 541Names such as \spadfun{norm} and \spadfun{product}, for example, have 542diverse meanings in diverse contexts. 543An inescapable hindrance to users would be to force those who wish to 544extend \Language{} to always invent new names for operations. 545%>> I don't think disambiguate is really a word, though I like it 546\Language{} allows you to reuse names, and then use context to disambiguate one 547from another. 548 549Here is another example of why this is important. 550Some languages, such as {\bf APL}, 551\index{APL} 552denote the \spadtype{Boolean} constants \spad{true} and 553\spad{false} by the integers \spad{1} and \spad{0}. 554You may want to let infix operators \spadop{+} and \spadop{*} serve as the logical 555operators \spadfun{or} and \spadfun{and}, respectively. 556But note this: \spadtype{Boolean} is not a ring. 557The {\it inverse axiom} for \spadtype{Ring} states: 558% 559\begin{center} 560Every element \spad{x} has an additive inverse \spad{y} such that 561\spad{x + y = 0}. 562\end{center} 563% 564\spadtype{Boolean} is not a ring since \spad{true} has 565no inverse---there is no inverse element \spad{a} such that 566\spad{1 + a = 0} (in terms of booleans, \spad{(true or a) = false}). 567Nonetheless, \Language{} {\it could} easily and correctly implement 568\spadtype{Boolean} this way. 569\spadtype{Boolean} simply would not assert that it is of category 570\spadtype{Ring}. 571Thus the \spadop{+} for \spadtype{Boolean} values 572is not confused with the one for \spadtype{Ring}. 573Since the \spadtype{Polynomial} constructor requires its argument 574to be a ring, \Language{} would then refuse to build the 575domain \spadtype{Polynomial(Boolean)}. Also, \Language{} would refuse to 576wrongfully apply algorithms to \spadtype{Boolean} elements that presume that the 577ring axioms for \spadop{+} hold. 578 579% ********************************************************************* 580\head{section}{Categories as attributes}{ugCategoriesAttributes} 581% ********************************************************************* 582 583Most axioms are not computationally useful. 584Those that are can be explicitly expressed by using special 585categories that export no operations. 586Note: in the past, instead of categories, \Language{} used a 587special construct called \spad{attribute}. 588 589The category \spadtype{CommutativeStar}, for example, is used to assert 590that a domain has commutative multiplication. 591Its definition is given by its documentation: 592 593\texht{\begingroup \parindent=1pc \narrower\noindent}{\indent{3}}% 594 A domain \spad{R} has \spadtype{CommutativeStar} 595 if it has an operation "*": \spad{(R,R)->R} such that \spad{x * y = y * x}. 596\texht{\par\endgroup}{\indent{0}} 597 598% Just as you can test whether a domain has the category \spadtype{Ring}, you 599% can test that a domain has a given attribute. 600So, to test that a domain is known to satisfy an axiom, we just 601test if it has corresponding category, like \spadtype{CommutativeStar} 602above. 603 604\xtc{ 605Do polynomials over the integers 606have commutative multiplication? 607}{ 608\spadcommand{Polynomial Integer has CommutativeStar} 609} 610\xtc{ 611Do matrices over the integers 612have commutative multiplication? 613}{ 614\spadcommand{Matrix Integer has CommutativeStar} 615} 616 617Using categories to assert axioms and category conditions 618to test if axioms are satisfied, 619we can conditionally export and define 620operations for a domain depending on axioms 621(see \spadref{ugDomainsAssertions}). 622Of course categories can also be asserted in a category definition. 623 624After mentioning category \spadtype{Ring} many times in this book, 625it is high time that we show you its definition: 626\exptypeindex{Ring} 627 628\begin{xmpLines} 629Ring() : Category == Join(Rng, SemiRing, NonAssociativeRing, 630 unitsKnown) 631\end{xmpLines} 632 633As you can see \spadtype{Ring} just combines properties of 634other categories. 635So let us see \spadtype{NonAssociativeRing}: 636 637\begin{xmpLines} 638NonAssociativeRing() : Category == Join(NonAssociativeRng, 639 NonAssociativeSemiRing) with 640 --operations 641 characteristic : -> NonNegativeInteger 642 ++ characteristic() returns the characteristic of the ring. 643 --we can not make this a constant, since some domains are mutable 644 coerce : Integer -> % 645 ++ coerce(n) coerces the integer n to an element of the ring. 646 add 647 n : Integer 648 coerce(n) == n * 1$% 649\end{xmpLines} 650 651There is one new thing here. 652Look at the \spadSyntax{$%} on the last line. 653This is not a typographic error! 654The \spadSyntax{$} says that the \spad{1} is to come from some 655domain. 656The \spadSyntax{%} says that the domain is ``this domain.'' 657If \spadSyntax{%} is \spadtype{Fraction(Integer)}, this line reads 658\spad{coerce(n) == n * 1$Fraction(Integer)}. 659 660Let us comment on category \spadtype{unitsKnown} appearing 661in definition of \spadtype{Ring} above. 662The category \spadtype{unitsKnown} asserts a rather subtle mathematical 663fact that is normally taken for granted when working with 664rings.\footnote{With this axiom, the units of a domain are the set of 665elements \spad{x} that each have a multiplicative 666inverse \spad{y} in the domain. 667Thus \spad{1} and \spad{-1} are units in domain \spadtype{Integer}. 668Also, for \spadtype{Fraction Integer}, the domain of rational numbers, 669all non-zero elements are units.} 670Because programs can test for this category, \Language{} can 671correctly handle rather more complicated mathematical structures (ones 672that are similar to rings but do not have this category). 673 674% ********************************************************************* 675\head{section}{Parameters}{ugCategoriesParameters} 676% ********************************************************************* 677 678Like domain constructors, category constructors can also have 679parameters. 680For example, category \spadtype{MatrixCategory} is a parameterized 681category for defining matrices over a ring \spad{R} so that the 682matrix domains can have 683different representations and indexing schemes. 684Its definition has the form: 685 686\begin{xmpLines} 687MatrixCategory(R,Row,Col): Category == 688 TwoDimensionalArrayCategory(R,Row,Col) with ... 689\end{xmpLines} 690 691The category extends \spadtype{TwoDimensionalArrayCategory} with 692the same arguments. 693You cannot find \spadtype{TwoDimensionalArrayCategory} in the 694algebraic hierarchy listing. 695Rather, it is a member of the data structure hierarchy, 696given inside the back cover of this book. 697In particular, \spadtype{TwoDimensionalArrayCategory} is an extension of 698\spadtype{HomogeneousAggregate} since its elements are all one type. 699 700The domain \spadtype{Matrix(R)}, the class of matrices with coefficients 701from domain \spad{R}, asserts that it is a member of category 702\spadtype{MatrixCategory(R, Vector(R), Vector(R))}. 703The parameters of a category must also have types. 704The first parameter to \spadtype{MatrixCategory} 705\spad{R} is required to be a ring. 706The second and third are required to be domains of category 707\spadtype{FiniteLinearAggregate(R)}.\footnote{% 708This is another extension of 709\spadtype{HomogeneousAggregate} that you can see in 710the data structure hierarchy.} 711In practice, examples of categories having parameters other than 712domains are rare. 713 714Adding the declarations for parameters to the definition for 715\spadtype{MatrixCategory}, we have: 716 717\begin{xmpLines} 718R: Ring 719(Row, Col): FiniteLinearAggregate(R) 720 721MatrixCategory(R, Row, Col): Category == 722 TwoDimensionalArrayCategory(R, Row, Col) with ... 723\end{xmpLines} 724 725% ********************************************************************* 726\head{section}{Conditionals}{ugCategoriesConditionals} 727% ********************************************************************* 728 729As categories have parameters, the actual operations exported by a 730\index{conditional} 731category can depend on these parameters. 732As an example, the operation \spadfunFrom{determinant}{MatrixCategory} 733from category \spadtype{MatrixCategory} is only exported when the 734underlying domain \spad{R} has commutative multiplication: 735 736\begin{verbatim} 737if R has CommutativeRing then 738 determinant: % -> R 739\end{verbatim} 740 741Conditionals can also define conditional extensions of a category. 742Here is a portion of the definition of \spadtype{QuotientFieldCategory}: 743\exptypeindex{QuotientFieldCategory} 744 745\begin{xmpLines} 746QuotientFieldCategory(R) : Category == ... with ... 747 if R has OrderedSet then OrderedSet 748 if R has IntegerNumberSystem then 749 ceiling: % -> R 750 ... 751\end{xmpLines} 752 753Think of category \spadtype{QuotientFieldCategory(R)} as 754denoting the domain \spadtype{Fraction(R)}, the 755class of all fractions of the form \smath{a/b} for elements of \spad{R}. 756The first conditional means in English: 757``If the elements of \spad{R} are totally ordered (\spad{R} 758is an \spadtype{OrderedSet}), then so are the fractions \smath{a/b}''. 759\exptypeindex{Fraction} 760 761The second conditional is used to conditionally export an 762operation \spadfun{ceiling} which returns the smallest integer 763greater than or equal to its argument. 764Clearly, ``ceiling'' makes sense for integers but not for 765polynomials and other algebraic structures. 766Because of this conditional, 767the domain \spadtype{Fraction(Integer)} exports 768an operation 769\spadfun{ceiling}: \spadtype{Fraction Integer}\spad{->}\spadtype{Integer}, but 770\spadtype{Fraction Polynomial Integer} does not. 771 772Conditionals can also appear in the default definitions for the 773operations of a category. 774For example, a default definition for \spadfunFrom{ceiling}{Field} 775within the part following the \spadSyntax{add} reads: 776 777\begin{verbatim} 778if R has IntegerNumberSystem then 779 ceiling x == ... 780\end{verbatim} 781 782Here the predicate used is identical to the predicate 783in the {\tt Exports} part. 784This need not be the case. 785See \spadref{ugPackagesConds} for a more complicated example. 786 787% ********************************************************************* 788\head{section}{Anonymous Categories}{ugCategoriesAndPackages} 789% ********************************************************************* 790 791The part of a category to the right of a {\tt with} is also 792regarded as a category---an ``anonymous category.'' 793Thus you have already seen a category definition 794\index{category!anonymous} in \chapref{ugPackages}. 795The {\tt Exports} part of the package \pspadtype{DrawComplex} 796(\spadref{ugPackagesAbstract}) is an anonymous category. 797This is not necessary. 798We could, instead, give this category a name: 799 800% 801\begin{xmpLines} 802DrawComplexCategory(): Category == with 803 drawComplex: (C -> C,S,S,Boolean) -> VIEW3D 804 drawComplexVectorField: (C -> C,S,S) -> VIEW3D 805 setRealSteps: INT -> INT 806 setImagSteps: INT -> INT 807 setClipValue: DFLOAT-> DFLOAT 808\end{xmpLines} 809% 810and then define \spadtype{DrawComplex} by: 811% 812\begin{xmpLines} 813DrawComplex(): DrawComplexCategory == Implementation 814 where 815 ... 816\end{xmpLines} 817% 818 819There is no reason, however, to give this list of exports a name 820since no other domain or package exports it. 821In fact, it is rare for a package to export a named category. 822As you will see in the next chapter, however, it is very common 823for the definition of domains to mention one or more category 824before the {\tt with}. 825\spadkey{with} 826