% 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}{10}}{} % Chapter 11


%
%
\newcommand{\ugPackagesTitle}{Packages}
\newcommand{\ugPackagesNumber}{11.}
%
% =====================================================================
\begin{page}{ugPackagesPage}{11. Packages}
% =====================================================================
\beginscroll

Packages provide the bulk of
%-% \HDindex{package}{ugPackagesPage}{11.}{Packages}
\Language{}'s algorithmic library, from numeric packages for computing
special functions to symbolic facilities for
%-% \HDindex{constructor!package}{ugPackagesPage}{11.}{Packages}
differential equations, symbolic integration, and limits.
%-% \HDindex{package!constructor}{ugPackagesPage}{11.}{Packages}

In \downlink{``\ugIntProgTitle''}{ugIntProgPage} in Chapter \ugIntProgNumber\ignore{ugIntProg}, we developed several useful functions for drawing
vector fields and complex functions.
We now show you how you can add these functions to the
\Language{} library to make them available for general use.

The way we created the functions in \downlink{``\ugIntProgTitle''}{ugIntProgPage} in Chapter \ugIntProgNumber\ignore{ugIntProg} is typical of how
you, as an advanced \Language{} user, may interact with \Language{}.
You have an application.
You go to your editor and create an input file defining some
functions for the application.
Then you run the file and try the functions.
Once you get them all to work, you will often want to extend them,
add new features, perhaps write additional functions.

Eventually, when you have a useful set of functions for your application,
you may want to add them to your local \Language{} library.
To do this, you embed these function definitions in a package and add
that package to the library.

To introduce new packages, categories, and domains into the system,
you need to use the \Language{} compiler to convert the constructors
into executable machine code.
An existing compiler in \Language{} is available on an ``as-is''
basis.
A new, faster compiler will be available in version 2.0
of \Language{}.

\beginImportant
  
\noindent
\label{pak-cdraw}
{\tt 1.\ \ \ C\ \ \ \ \ \ ==>\ Complex\ DoubleFloat}\newline
{\tt 2.\ \ \ S\ \ \ \ \ \ ==>\ Segment\ DoubleFloat}\newline
{\tt 3.\ \ \ INT\ \ \ \ ==>\ Integer}\newline
{\tt 4.\ \ \ DFLOAT\ ==>\ DoubleFloat}\newline
{\tt 5.\ \ \ VIEW3D\ ==>\ ThreeDimensionalViewport}\newline
{\tt 6.\ \ \ CURVE\ \ ==>\ List\ List\ Point\ DFLOAT}\newline
{\tt 7.\ \ \ }\newline
{\tt 8.\ \ \ )abbrev\ package\ DRAWCX\ DrawComplex}\newline
{\tt 9.\ \ \ DrawComplex():\ Exports\ ==\ Implementation\ where}\newline
{\tt 10.\ \ }\newline
{\tt 11.\ \ \ \ Exports\ ==\ with}\newline
{\tt 12.\ \ \ \ \ \ drawComplex:\ (C\ ->\ C,S,S,Boolean)\ ->\ VIEW3D}\newline
{\tt 13.\ \ \ \ \ \ drawComplexVectorField:\ (C\ ->\ C,S,S)\ ->\ VIEW3D}\newline
{\tt 14.\ \ \ \ \ \ setRealSteps:\ INT\ ->\ INT}\newline
{\tt 15.\ \ \ \ \ \ setImagSteps:\ INT\ ->\ INT}\newline
{\tt 16.\ \ \ \ \ \ setClipValue:\ DFLOAT->\ DFLOAT}\newline
{\tt 17.\ \ }\newline
{\tt 18.\ \ \ \ Implementation\ ==\ add}\newline
{\tt 19.\ \ \ \ \ \ arrowScale\ :\ DFLOAT\ :=\ (0.2)::DFLOAT\ --relative\ size}\newline
{\tt 20.\ \ \ \ \ \ arrowAngle\ :\ DFLOAT\ :=\ pi()-pi()/(20::DFLOAT)}\newline
{\tt 21.\ \ \ \ \ \ realSteps\ \ :\ INT\ :=\ 11\ --\#\ real\ steps}\newline
{\tt 22.\ \ \ \ \ \ imagSteps\ \ :\ INT\ :=\ 11\ --\#\ imaginary\ steps}\newline
{\tt 23.\ \ \ \ \ \ clipValue\ \ :\ DFLOAT\ \ :=\ 10::DFLOAT\ --maximum\ vector\ length}\newline
{\tt 24.\ \ }\newline
{\tt 25.\ \ \ \ \ \ setRealSteps(n)\ ==\ realSteps\ :=\ n}\newline
{\tt 26.\ \ \ \ \ \ setImagSteps(n)\ ==\ imagSteps\ :=\ n}\newline
{\tt 27.\ \ \ \ \ \ setClipValue(c)\ ==\ clipValue\ :=\ c}\newline
{\tt 28.\ \ }\newline
{\tt 29.\ \ \ \ \ \ clipFun:\ DFLOAT\ ->\ DFLOAT\ --Clip\ large\ magnitudes.}\newline
{\tt 30.\ \ \ \ \ \ clipFun(x)\ ==\ min(max(x,\ -clipValue),\ clipValue)}\newline
{\tt 31.\ \ }\newline
{\tt 32.\ \ \ \ \ \ makeArrow:\ (Point\ DFLOAT,Point\ DFLOAT,DFLOAT,DFLOAT)\ ->\ CURVE}\newline
{\tt 33.\ \ \ \ \ \ makeArrow(p1,\ p2,\ len,\ arg)\ ==\ ...}\newline
{\tt 34.\ \ }\newline
{\tt 35.\ \ \ \ \ \ drawComplex(f,\ realRange,\ imagRange,\ arrows?)\ ==\ ...}\newline
\caption{The DrawComplex package.}\label{fig-pak-cdraw}
\endImportant

\beginmenu
    \menudownlink{{11.1. Names, Abbreviations, and File Structure}}{ugPackagesNamesPage}
    \menudownlink{{11.2. Syntax}}{ugPackagesSyntaxPage}
    \menudownlink{{11.3. Abstract Datatypes}}{ugPackagesAbstractPage}
    \menudownlink{{11.4. Capsules}}{ugPackagesCapsulesPage}
    \menudownlink{{11.5. Input Files vs. Packages}}{ugPackagesInputFilesPage}
    \menudownlink{{11.6. Compiling Packages}}{ugPackagesPackagesPage}
    \menudownlink{{11.7. Parameters}}{ugPackagesParametersPage}
    \menudownlink{{11.8. Conditionals}}{ugPackagesCondsPage}
    \menudownlink{{11.9. Testing}}{ugPackagesCompilingPage}
    \menudownlink{{11.10. How Packages Work}}{ugPackagesHowPage}
\endmenu
\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugPackagesNamesTitle}{Names, Abbreviations, and File Structure}
\newcommand{\ugPackagesNamesNumber}{11.1.}
%
% =====================================================================
\begin{page}{ugPackagesNamesPage}{11.1. Names, Abbreviations, and File Structure}
% =====================================================================
\beginscroll
%
Each package has a name and an abbreviation.
For a package of the complex draw functions from \downlink{``\ugIntProgTitle''}{ugIntProgPage} in Chapter \ugIntProgNumber\ignore{ugIntProg},
we choose the name \nonLibAxiomType{DrawComplex}
and
%-% \HDindex{abbreviation!constructor}{ugPackagesNamesPage}{11.1.}{Names, Abbreviations, and File Structure}
abbreviation \nonLibAxiomType{DRAWCX}.\footnote{An abbreviation can be any string
of
%-% \HDindex{constructor!abbreviation}{ugPackagesNamesPage}{11.1.}{Names, Abbreviations, and File Structure}
between two and seven capital letters and digits, beginning with a letter.
See \downlink{``\ugTypesWritingAbbrTitle''}{ugTypesWritingAbbrPage} in Section \ugTypesWritingAbbrNumber\ignore{ugTypesWritingAbbr} for more information.}
To be sure that you have not chosen a name or abbreviation already used by
the system, issue the system command \spadcmd{)show} for both the name and
the abbreviation.
%-% \HDsyscmdindex{show}{ugPackagesNamesPage}{11.1.}{Names, Abbreviations, and File Structure}

Once you have named the package and its abbreviation, you can choose any new
filename you like with extension ``{\bf \spadFileExt{}}'' to hold the
definition of your package.
We choose the name {\bf
drawpak\spadFileExt{}}.
If your application involves more than one package, you
can put them all in the same file.
\Language{} assumes no relationship between the name of a library file, and
the name or abbreviation of a package.

Near the top of the ``{\bf \spadFileExt{}}'' file, list all the
abbreviations for the packages
using \spadcmd{)abbrev}, each command beginning in column one.
Macros giving names to \Language{} expressions can also be placed near the
top of the file.
The macros are only usable from their point of definition until the
end of the file.

Consider the definition of
\nonLibAxiomType{DrawComplex} in Figure \ref{fig-pak-cdraw}.
After the macro
%-% \HDindex{macro}{ugPackagesNamesPage}{11.1.}{Names, Abbreviations, and File Structure}
definition
\begin{verbatim}
S      ==> Segment DoubleFloat
\end{verbatim}
the name
{\tt S} can be used in the file as a
shorthand for \axiomType{Segment DoubleFloat}.\footnote{The interpreter also allows
{\tt macro} for macro definitions.}
The abbreviation command for the package
\begin{verbatim}
)abbrev package DRAWCX DrawComplex
\end{verbatim}
is given after the macros (although it could precede them).

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugPackagesSyntaxTitle}{Syntax}
\newcommand{\ugPackagesSyntaxNumber}{11.2.}
%
% =====================================================================
\begin{page}{ugPackagesSyntaxPage}{11.2. Syntax}
% =====================================================================
\beginscroll
%
The definition of a package has the syntax:
\centerline{{\frenchspacing{\it PackageForm {\tt :} Exports\quad{\tt ==}\quad Implementation}}}
The syntax for defining a package constructor is the same as that
%-% \HDindex{syntax}{ugPackagesSyntaxPage}{11.2.}{Syntax}
for defining any function in \Language{}.
In practice, the definition extends over many lines so that this syntax is
not practical.
Also, the type of a package is expressed by the operator \axiom{with}
\spadkey{with}
followed by an explicit list of operations.
A preferable way to write the definition of a package is with a \axiom{where}
\spadkey{where}
expression:

\beginImportant
The definition of a package usually has the form: \newline
{\tt%
{\it PackageForm} : Exports  ==  Implementation where \newline
\texht{\hspace*{.75pc}}{\tab{3}} {\it optional type declarations}\newline
\texht{\hspace*{.75pc}}{\tab{3}} Exports  ==   with \newline
\texht{\hspace*{2.0pc}}{\tab{6}}   {\it list of exported operations}\newline
\texht{\hspace*{.75pc}}{\tab{3}} Implementation == add \newline
\texht{\hspace*{2.0pc}}{\tab{6}}   {\it list of function definitions for exported operations}
}
\endImportant

The \axiomType{DrawComplex} package takes no parameters and exports five
operations, each a separate item of a \spadgloss{pile}.
Each operation is described as a \spadgloss{declaration}: a name, followed
by a colon (\axiomSyntax{:}), followed by the type of the operation.
All operations have types expressed as \spadglossSee{mappings}{mapping} with
the syntax
\centerline{{{\it}}
\centerline{{source\quad{\tt ->}\quad target}}
\centerline{{}}}

%e *********************************************************************
\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugPackagesAbstractTitle}{Abstract Datatypes}
\newcommand{\ugPackagesAbstractNumber}{11.3.}
%
% =====================================================================
\begin{page}{ugPackagesAbstractPage}{11.3. Abstract Datatypes}
% =====================================================================
\beginscroll

A constructor as defined in \Language{} is called an \spadgloss{abstract
datatype} in the computer science literature.
Abstract datatypes separate ``specification'' (what operations are
provided) from ``implementation'' (how the operations are implemented).
The {\tt Exports} (specification) part of a constructor is said to be ``public'' (it
provides the user interface to the package) whereas the {\tt Implementation}
part is ``private'' (information here is effectively hidden---programs
cannot take advantage of it).

The {\tt Exports} part specifies what operations the package provides to users.
As an author of a package, you must ensure that
the {\tt Implementation} part provides a function for each
operation in the {\tt Exports} part.\footnote{The \spadtype{DrawComplex}
package enhances the facility
described in  \downlink{``\ugIntProgCompFunsTitle''}{ugIntProgCompFunsPage} in Chapter \ugIntProgCompFunsNumber\ignore{ugIntProgCompFuns} by allowing a
complex function to have
arrows emanating from the surface to indicate the direction of the
complex argument.}

An important difference between interactive programming and the
use of packages is in the handling of global variables such as
\axiom{realSteps} and \axiom{imagSteps}.
In interactive programming, you simply change the values of
variables by \spadgloss{assignment}.
With packages, such variables are local to the package---their
values can only be set using functions exported by the package.
In our example package, we provide two functions
\fakeAxiomFun{setRealSteps} and \fakeAxiomFun{setImagSteps} for
this purpose.

Another local variable is \axiom{clipValue} which can be changed using
the exported operation \fakeAxiomFun{setClipValue}.
This value is referenced by the internal function \fakeAxiomFun{clipFun} that
decides whether to use the computed value of the function at a point or,
if the magnitude of that value is too large, the
value assigned to \axiom{clipValue} (with the
appropriate sign).

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugPackagesCapsulesTitle}{Capsules}
\newcommand{\ugPackagesCapsulesNumber}{11.4.}
%
% =====================================================================
\begin{page}{ugPackagesCapsulesPage}{11.4. Capsules}
% =====================================================================
\beginscroll
%
The part to the right of {\tt add} in the {\tt Implementation}
\spadkey{add}
part of the definition is called a \spadgloss{capsule}.
The purpose of a capsule is:
\indent{4}
\beginitems
\item[-] to define a function for each exported operation, and
\item[-] to define a \spadgloss{local environment} for these functions to run.
\enditems
\indent{0}

What is a local environment?
First, what is an environment?
%-% \HDindex{environment}{ugPackagesCapsulesPage}{11.4.}{Capsules}
Think of the capsule as an input file that \Language{} reads from top to
bottom.
Think of the input file as having a \axiom{)clear all} at the top
so that initially no variables or functions are defined.
When this file is read, variables such as \axiom{realSteps} and
\axiom{arrowSize} in \nonLibAxiomType{DrawComplex} are set to initial values.
Also, all the functions defined in the capsule are compiled.
These include those that are exported (like \axiom{drawComplex}), and
those that are not (like \axiom{makeArrow}).
At the end, you get a set of name-value pairs:
variable names (like \axiom{realSteps} and \axiom{arrowSize})
are paired with assigned values, while
operation names (like \axiom{drawComplex} and \axiom{makeArrow})
are paired with function values.

This set of name-value pairs is called an \spadgloss{environment}.
Actually, we call this environment the ``initial environment'' of a package:
it is the environment that exists immediately after the package is
first built.
Afterwards, functions of this capsule can
access or reset a variable in the environment.
The environment is called {\it local} since any changes to the value of a
variable in this environment can be seen {\it only} by these functions.

Only the functions from the package can change the variables in the local
environment.
When two functions are called successively from a package,
any changes caused by the first function called
are seen by the second.

Since the environment is local to the package, its names
don't get mixed
up with others in the system or your workspace.
If you happen to have a variable called \axiom{realSteps} in your
workspace, it does not affect what the
\nonLibAxiomType{DrawComplex} functions do in any way.

The functions in a package are compiled into machine code.
Unlike function definitions in input files that may be compiled repeatedly
as you use them with varying argument types,
functions in packages have a unique type (generally parameterized by
the argument parameters of a package) and a unique compilation residing on disk.

The capsule itself is turned into a compiled function.
This so-called {\it capsule function} is what builds the initial environment
spoken of above.
If the package has arguments (see below), then each call to the package
constructor with a distinct pair of arguments
builds a distinct package, each with its own local environment.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugPackagesInputFilesTitle}{Input Files vs. Packages}
\newcommand{\ugPackagesInputFilesNumber}{11.5.}
%
% =====================================================================
\begin{page}{ugPackagesInputFilesPage}{11.5. Input Files vs. Packages}
% =====================================================================
\beginscroll
%
A good question at this point would be ``Is writing a package more difficult than
writing an input file?''

The programs in input files are designed for flexibility and ease-of-use.
\Language{} can usually work out all of your types as it reads your program
and does the computations you request.
Let's say that you define a one-argument function without giving its type.
When you first apply the function to a value, this
value is understood by \Language{} as identifying the type for the
argument parameter.
Most of the time \Language{} goes through the body of your function and
figures out the target type that you have in mind.
\Language{} sometimes fails to get it right.
Then---and only then---do you need a declaration to tell \Language{} what
type you want.

Input files are usually written to be read by \Language{}---and by you.
%-% \HDindex{file!input!vs. package}{ugPackagesInputFilesPage}{11.5.}{Input Files vs. Packages}
Without suitable documentation and declarations, your input files
%-% \HDindex{package!vs. input file}{ugPackagesInputFilesPage}{11.5.}{Input Files vs. Packages}
are likely incomprehensible to a colleague---and to you some
months later!

Packages are designed for legibility, as well as
run-time efficiency.
There are few new concepts you need to learn to write
packages. Rather, you just have to be explicit about types
and type conversions.
The types of all functions are pre-declared so that \Language{}---and the reader---
knows precisely what types of arguments can be passed to and from
the functions (certainly you don't want a colleague to guess or to
have to work this out from context!).
The types of local variables are also declared.
Type conversions are explicit, never automatic.\footnote{There
is one exception to this rule: conversions from a subdomain to a
domain are automatic.
After all, the objects both have the domain as a common type.}

In summary, packages are more tedious to write than input files.
When writing input files, you can casually go ahead, giving some
facts now, leaving others for later.
Writing packages requires forethought, care and discipline.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugPackagesPackagesTitle}{Compiling Packages}
\newcommand{\ugPackagesPackagesNumber}{11.6.}
%
% =====================================================================
\begin{page}{ugPackagesPackagesPage}{11.6. Compiling Packages}
% =====================================================================
\beginscroll
%

Once you have defined the package \nonLibAxiomType{DrawComplex},
you need to compile and test it.
To compile the package, issue the system command \spadcmd{)compile drawpak}.
\Language{} reads the file {\bf drawpak\spadFileExt{}}
and compiles its contents into machine binary.
If all goes well, the file {\bf DRAWCX.NRLIB} is created in your
local directory for the package.
To test the package, you must load the package before trying an
operation.

\nullXtc{
Compile the package.
}{
\spadpaste{)compile drawpak}
}
\xtc{
Expose the package.
}{
\spadpaste{)expose DRAWCX \bound{dp}}
}
\xtc{
Use an odd step size to avoid
a pole at the origin.
}{
\spadpaste{setRealSteps 51 \free{dp}\bound{srs}}
}
\xtc{
}{
\spadpaste{setImagSteps 51 \free{dp}\bound{scs}}
}
\xtc{
Define \userfun{f} to be the Gamma function.
}{
\spadpaste{f(z) == Gamma(z) \bound{f}}
}
\xtc{
Clip values of function with magnitude larger than 7.
}{
\spadpaste{setClipValue 7}
}
\psXtc{
Draw the \spadfun{Gamma} function.
}{
\graphpaste{drawComplex(f,-\%pi..\%pi,-\%pi..\%pi, false) \free{srs scs f}}
}{
\epsffile[0 0 300 300]{../ps/3Dgamma11.ps}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugPackagesParametersTitle}{Parameters}
\newcommand{\ugPackagesParametersNumber}{11.7.}
%
% =====================================================================
\begin{page}{ugPackagesParametersPage}{11.7. Parameters}
% =====================================================================
\beginscroll
%
The power of packages becomes evident when packages have parameters.
Usually these parameters are domains and the exported operations have types
involving these parameters.

In \downlink{``\ugTypesTitle''}{ugTypesPage} in Chapter \ugTypesNumber\ignore{ugTypes}, you learned that categories denote classes of
domains.
Although we cover this notion in detail in the next
chapter, we now give you a sneak preview of its usefulness.

In \downlink{``\ugUserBlocksTitle''}{ugUserBlocksPage} in Section \ugUserBlocksNumber\ignore{ugUserBlocks}, we defined functions \axiom{bubbleSort(m)} and
\axiom{insertionSort(m)} to sort a list of integers.
If you look at the code for these functions, you see that they may be
used to sort {\it any} structure \axiom{m} with the right properties.
Also, the functions can be used to sort lists of {\it any} elements---not
just integers.
Let us now recall the code for \axiom{bubbleSort}.

\begin{verbatim}
bubbleSort(m) ==
  n := #m
  for i in 1..(n-1) repeat
    for j in n..(i+1) by -1 repeat
      if m.j < m.(j-1) then swap!(m,j,j-1)
  m
\end{verbatim}

What properties of ``lists of integers'' are assumed by the sorting
algorithm?
In the first line, the operation \spadfun{\#} computes the maximum index of
the list.
The first obvious property is that \axiom{m} must have a finite number of
elements.
In \Language{}, this is done
by your telling \Language{} that \axiom{m} has
the ``attribute'' \spadatt{finiteAggregate}.
An \spadgloss{attribute} is a property
that a domain either has or does not have.
As we show later in \downlink{``\ugCategoriesAttributesTitle''}{ugCategoriesAttributesPage} in Section \ugCategoriesAttributesNumber\ignore{ugCategoriesAttributes},
programs can query domains as to the presence or absence of an attribute.

The operation \spadfunX{swap} swaps elements of \axiom{m}.
Using \Browse{}, you find that \spadfunX{swap} requires its
elements to come from a domain of category
\axiomType{IndexedAggregate} with attribute
\spadatt{shallowlyMutable}.
This attribute means that you can change the internal components
of \axiom{m} without changing its external structure.
Shallowly-mutable data structures include lists, streams, one- and
two-dimensional arrays, vectors, and matrices.

The category \axiomType{IndexedAggregate} designates the class of
aggregates whose elements can be accessed by the notation
\axiom{m.s} for suitable selectors \axiom{s}.
The category \axiomType{IndexedAggregate} takes two arguments:
\axiom{Index}, a domain of selectors for the aggregate, and
\axiom{Entry}, a domain of entries for the aggregate.
Since the sort functions access elements by integers, we must
choose \axiom{Index = }\axiomType{Integer}.
The most general class of domains for which \axiom{bubbleSort} and
\axiom{insertionSort} are defined are those of
category \spadtype{IndexedAggregate(Integer,Entry)} with the two
attributes \spadatt{shallowlyMutable} and
\spadatt{finiteAggregate}.

Using \Browse{}, you can also discover that \Language{} has many kinds of domains
with attribute \spadatt{shallowlyMutable}.
Those of class \axiomType{IndexedAggregate(Integer,Entry)} include
\axiomType{Bits}, \axiomType{FlexibleArray}, \axiomType{OneDimensionalArray},
\axiomType{List}, \axiomType{String}, and \axiomType{Vector}, and also
\axiomType{HashTable} and \axiomType{EqTable} with integer keys.
Although you may never want to sort all such structures, we
nonetheless demonstrate \Language{}'s
ability to do so.

Another requirement is that \nonLibAxiomType{Entry} has an
operation \axiomOp{<}.
One way to get this operation is to assume that
\nonLibAxiomType{Entry} has category \axiomType{OrderedSet}.
By definition, will then export a \axiomOp{<} operation.
A more general approach is to allow any comparison function
\axiom{f} to be used for sorting.
This function will be passed as an argument to the sorting
functions.

Our sorting package then takes two arguments: a domain \axiom{S}
of objects of {\it any} type, and a domain \axiom{A}, an aggregate
of type \axiomType{IndexedAggregate(Integer, S)} with the above
two attributes.
Here is its definition using what are close to the original
definitions of \axiom{bubbleSort} and \axiom{insertionSort} for
sorting lists of integers.
The symbol \axiomSyntax{!} is added to the ends of the operation
names.
This uniform naming convention is used for \Language{} operation
names that destructively change one or more of their arguments.

\beginImportant
  
\noindent
{\tt 1.\ \ \ SortPackage(S,A)\ :\ Exports\ ==\ Implementation\ where}\newline
{\tt 2.\ \ \ \ \ S:\ Object}\newline
{\tt 3.\ \ \ \ \ A:\ IndexedAggregate(Integer,S)}\newline
{\tt 4.\ \ \ \ \ \ \ with\ (finiteAggregate;\ shallowlyMutable)}\newline
{\tt 5.\ \ \ }\newline
{\tt 6.\ \ \ \ \ Exports\ ==\ with}\newline
{\tt 7.\ \ \ \ \ \ \ bubbleSort!:\ (A,(S,S)\ ->\ Boolean)\ ->\ A}\newline
{\tt 8.\ \ \ \ \ \ \ insertionSort!:\ (A,\ (S,S)\ ->\ Boolean)\ ->\ A}\newline
{\tt 9.\ \ \ }\newline
{\tt 10.\ \ \ \ Implementation\ ==\ add}\newline
{\tt 11.\ \ \ \ \ \ bubbleSort!(m,f)\ ==}\newline
{\tt 12.\ \ \ \ \ \ \ \ n\ :=\ \#m}\newline
{\tt 13.\ \ \ \ \ \ \ \ for\ i\ in\ 1..(n-1)\ repeat}\newline
{\tt 14.\ \ \ \ \ \ \ \ \ \ for\ j\ in\ n..(i+1)\ by\ -1\ repeat}\newline
{\tt 15.\ \ \ \ \ \ \ \ \ \ \ \ if\ f(m.j,m.(j-1))\ then\ swap!(m,j,j-1)}\newline
{\tt 16.\ \ \ \ \ \ \ \ m}\newline
{\tt 17.\ \ \ \ \ \ insertionSort!(m,f)\ ==}\newline
{\tt 18.\ \ \ \ \ \ \ \ for\ i\ in\ 2..\#m\ repeat}\newline
{\tt 19.\ \ \ \ \ \ \ \ \ \ j\ :=\ i}\newline
{\tt 20.\ \ \ \ \ \ \ \ \ \ while\ j\ >\ 1\ and\ f(m.j,m.(j-1))\ repeat}\newline
{\tt 21.\ \ \ \ \ \ \ \ \ \ \ \ swap!(m,j,j-1)}\newline
{\tt 22.\ \ \ \ \ \ \ \ \ \ \ \ j\ :=\ (j\ -\ 1)\ pretend\ PositiveInteger}\newline
{\tt 23.\ \ \ \ \ \ \ \ m}\newline
\endImportant

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugPackagesCondsTitle}{Conditionals}
\newcommand{\ugPackagesCondsNumber}{11.8.}
%
% =====================================================================
\begin{page}{ugPackagesCondsPage}{11.8. Conditionals}
% =====================================================================
\beginscroll
%
When packages have parameters, you can say that an operation is or is not
%-% \HDindex{conditional}{ugPackagesCondsPage}{11.8.}{Conditionals}
exported depending on the values of those parameters.
When the domain of objects \axiom{S} has an \axiomOp{<}
operation, we can supply one-argument versions of
\axiom{bubbleSort} and \axiom{insertionSort} which use this operation
for sorting.
The presence of the
operation \axiomOp{<} is guaranteed when \axiom{S} is an ordered set.

\beginImportant
  
\noindent
{\tt 1.\ \ \ Exports\ ==\ with}\newline
{\tt 2.\ \ \ \ \ \ \ bubbleSort!:\ (A,(S,S)\ ->\ Boolean)\ ->\ A}\newline
{\tt 3.\ \ \ \ \ \ \ insertionSort!:\ (A,\ (S,S)\ ->\ Boolean)\ ->\ A}\newline
{\tt 4.\ \ \ }\newline
{\tt 5.\ \ \ \ \ \ \ if\ S\ has\ OrderedSet\ then}\newline
{\tt 6.\ \ \ \ \ \ \ \ \ bubbleSort!:\ A\ ->\ A}\newline
{\tt 7.\ \ \ \ \ \ \ \ \ insertionSort!:\ A\ ->\ A}\newline
\endImportant

In addition to exporting the one-argument sort operations
%-% \HDindex{sort!bubble}{ugPackagesCondsPage}{11.8.}{Conditionals}
conditionally, we must provide conditional definitions for the
%-% \HDindex{sort!insertion}{ugPackagesCondsPage}{11.8.}{Conditionals}
operations in the {\tt Implementation} part.
This is easy: just have the one-argument functions call the
corresponding two-argument functions with the operation
\axiomOp{<} from \axiom{S}.

\beginImportant
  
\noindent
{\tt 1.\ \ \ \ \ Implementation\ ==\ add}\newline
{\tt 2.\ \ \ \ \ \ \ \ \ \ ...}\newline
{\tt 3.\ \ \ \ \ \ \ if\ S\ has\ OrderedSet\ then}\newline
{\tt 4.\ \ \ \ \ \ \ \ \ bubbleSort!(m)\ ==\ bubbleSort!(m,<\$S)}\newline
{\tt 5.\ \ \ \ \ \ \ \ \ insertionSort!(m)\ ==\ insertionSort!(m,<\$S)}\newline
\endImportant

In \downlink{``\ugUserBlocksTitle''}{ugUserBlocksPage} in Section \ugUserBlocksNumber\ignore{ugUserBlocks}, we give an alternative definition of
\fakeAxiomFun{bubbleSort} using \spadfunFrom{first}{List} and
\spadfunFrom{rest}{List} that is more efficient for a list (for
which access to any element requires traversing the list from its
first node).
To implement a more efficient algorithm for lists, we need the
operation \spadfun{setelt} which allows us to destructively change
the \spadfun{first} and \spadfun{rest} of a list.
Using \Browse{}, you find that these operations come from category
\axiomType{UnaryRecursiveAggregate}.
Several aggregate types are unary recursive aggregates including
those of \axiomType{List} and \axiomType{AssociationList}.
We provide two different implementations for
\fakeAxiomFun{bubbleSort!} and \fakeAxiomFun{insertionSort!}: one
for list-like structures, another for array-like structures.

\beginImportant
  
\noindent
{\tt 1.\ \ \ Implementation\ ==\ add}\newline
{\tt 2.\ \ \ \ \ \ \ \ \ \ \ ...}\newline
{\tt 3.\ \ \ \ \ \ \ if\ A\ has\ UnaryRecursiveAggregate(S)\ then}\newline
{\tt 4.\ \ \ \ \ \ \ \ \ bubbleSort!(m,fn)\ ==}\newline
{\tt 5.\ \ \ \ \ \ \ \ \ \ \ empty?\ m\ =>\ m}\newline
{\tt 6.\ \ \ \ \ \ \ \ \ \ \ l\ :=\ m}\newline
{\tt 7.\ \ \ \ \ \ \ \ \ \ \ while\ not\ empty?\ (r\ :=\ l.rest)\ repeat}\newline
{\tt 8.\ \ \ \ \ \ \ \ \ \ \ \ \ \ r\ :=\ bubbleSort!\ r}\newline
{\tt 9.\ \ \ \ \ \ \ \ \ \ \ \ \ \ x\ :=\ l.first}\newline
{\tt 10.\ \ \ \ \ \ \ \ \ \ \ \ \ if\ fn(r.first,x)\ then}\newline
{\tt 11.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ l.first\ :=\ r.first}\newline
{\tt 12.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ r.first\ :=\ x}\newline
{\tt 13.\ \ \ \ \ \ \ \ \ \ \ \ \ l.rest\ :=\ r}\newline
{\tt 14.\ \ \ \ \ \ \ \ \ \ \ \ \ l\ :=\ l.rest}\newline
{\tt 15.\ \ \ \ \ \ \ \ \ \ \ m}\newline
{\tt 16.\ \ \ \ \ \ \ \ \ insertionSort!(m,fn)\ ==}\newline
{\tt 17.\ \ \ \ \ \ \ \ \ \ \ \ ...}\newline
\endImportant

The ordering of definitions is important.
The standard definitions come first and
then the predicate
\begin{verbatim}
A has UnaryRecursiveAggregate(S)
\end{verbatim}
is evaluated.
If {\tt true}, the special definitions cover up the standard ones.

Another equivalent way to write the capsule is to use an
\axiom{if-then-else} expression:
\spadkey{if}

\beginImportant
  
\noindent
{\tt 1.\ \ \ \ \ \ \ \ if\ A\ has\ UnaryRecursiveAggregate(S)\ then}\newline
{\tt 2.\ \ \ \ \ \ \ \ \ \ \ ...}\newline
{\tt 3.\ \ \ \ \ \ \ \ else}\newline
{\tt 4.\ \ \ \ \ \ \ \ \ \ \ ...}\newline
\endImportant

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugPackagesCompilingTitle}{Testing}
\newcommand{\ugPackagesCompilingNumber}{11.9.}
%
% =====================================================================
\begin{page}{ugPackagesCompilingPage}{11.9. Testing}
% =====================================================================
\beginscroll
%
Once you have written the package, embed it in a file, for example, {\bf
sortpak\spadFileExt{}}.
%-% \HDindex{testing}{ugPackagesCompilingPage}{11.9.}{Testing}
Be sure to include an \axiom{)abbrev} command at the top of the file:
\begin{verbatim}
)abbrev package SORTPAK SortPackage
\end{verbatim}
Now compile the file (using \spadcmd{)compile sortpak\spadFileExt{}}).
\xtc{
Expose the constructor.
You are then ready to begin testing.
}{
\spadpaste{)expose SORTPAK}
}
\xtc{
Define a list.
}{
\spadpaste{l := [1,7,4,2,11,-7,3,2]}
}
\xtc{
Since the integers are an ordered set,
a one-argument operation will do.
}{
\spadpaste{bubbleSort!(l)}
}
\xtc{
Re-sort it using ``greater than.''
}{
\spadpaste{bubbleSort!(l,(x,y) +-> x > y)}
}
\xtc{
Now sort it again using \axiomOp{<} on integers.
}{
\spadpaste{bubbleSort!(l, <\$Integer)}
}
\xtc{
A string is an aggregate of characters so we can sort them as well.
}{
\spadpaste{bubbleSort! "Mathematical Sciences"}
}
\xtc{
Is \axiomOp{<} defined on booleans?
}{
\spadpaste{false < true}
}
\xtc{
Good! Create a bit string representing ten consecutive
boolean values \axiom{true}.
}{
\spadpaste{u : Bits := new(10,true)}
}
\xtc{
Set bits 3 through 5 to \axiom{false}, then display the result.
}{
\spadpaste{u(3..5) := false; u}
}
\xtc{
Now sort these booleans.
}{
\spadpaste{bubbleSort! u}
}
\xtc{
Create an ``eq-table'' (see \downlink{`EqTable'}{EqTableXmpPage}\ignore{EqTable}), a
table having integers as keys
and strings as values.
}{
\spadpaste{t : EqTable(Integer,String) := table()}
}
\xtc{
Give the table a first entry.
}{
\spadpaste{t.1 := "robert"}
}
\xtc{
And a second.
}{
\spadpaste{t.2 := "richard"}
}
\xtc{
What does the table look like?
}{
\spadpaste{t}
}
\xtc{
Now sort it.
}{
\spadpaste{bubbleSort! t}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugPackagesHowTitle}{How Packages Work}
\newcommand{\ugPackagesHowNumber}{11.10.}
%
% =====================================================================
\begin{page}{ugPackagesHowPage}{11.10. How Packages Work}
% =====================================================================
\beginscroll
%
Recall that packages as abstract datatypes are compiled independently
and put into the library.
The curious reader may ask: ``How is the interpreter able to find an
operation such as \fakeAxiomFun{bubbleSort!}?
Also, how is a single compiled function such as \fakeAxiomFun{bubbleSort!} able
to sort data of different types?''

After the interpreter loads the package \nonLibAxiomType{SortPackage}, the four
operations from the package become known to the interpreter.
Each of these operations is expressed as a {\it modemap} in which the type
%-% \HDindex{modemap}{ugPackagesHowPage}{11.10.}{How Packages Work}
of the operation is written in terms of symbolic domains.
\nullXtc{
See the modemaps for \fakeAxiomFun{bubbleSort!}.
}{
\spadpaste{)display op bubbleSort!}
}
\begin{verbatim}
There are 2 exposed functions called bubbleSort! :

   [1] D1 -> D1 from SortPackage(D2,D1)
         if D2 has ORDSET and D2 has OBJECT and D1 has
         IndexedAggregate(Integer, D2) with
              finiteAggregate
              shallowlyMutable

   [2] (D1,((D3,D3) -> Boolean)) -> D1 from SortPackage(D3,D1)
         if D3 has OBJECT and D1 has
         IndexedAggregate(Integer,D3) with
              finiteAggregate
              shallowlyMutable
\end{verbatim}

What happens if you ask for \axiom{bubbleSort!([1,-5,3])}?
There is a unique modemap for an operation named
\fakeAxiomFun{bubbleSort!} with one argument.
Since \axiom{[1,-5,3]} is a list of integers, the symbolic domain
\axiom{D1} is defined as \axiomType{List(Integer)}.
For some operation to apply, it must satisfy the predicate for
some \axiom{D2}.
What \axiom{D2}?
The third expression of the \axiom{and} requires {\tt D1 has
IndexedAggregate(Integer, D2) with} two attributes.
So the interpreter searches for an \axiomType{IndexedAggregate}
among the ancestors of \axiomType{List (Integer)} (see
\downlink{``\ugCategoriesHierTitle''}{ugCategoriesHierPage} in Section \ugCategoriesHierNumber\ignore{ugCategoriesHier}).
It finds one: \axiomType{IndexedAggregate(Integer, Integer)}.
The interpreter tries defining \axiom{D2} as \axiomType{Integer}.
After substituting for \axiom{D1} and \axiom{D2}, the predicate
evaluates to \axiom{true}.
An applicable operation has been found!

Now \Language{} builds the package
\axiomType{SortPackage(List(Integer), Integer)}.
According to its definition, this package exports the required
operation: \fakeAxiomFun{bubbleSort!}: \spadsig{List Integer}{List
Integer}.
The interpreter then asks the package for a function implementing
this operation.
The package gets all the functions it needs (for example,
\axiomFun{rest} and \axiomFunX{swap}) from the appropriate
domains and then it
returns a \fakeAxiomFun{bubbleSort!} to the interpreter together with
the local environment for \fakeAxiomFun{bubbleSort!}.
The interpreter applies the function to the argument \axiom{[1,-5,3]}.
The \fakeAxiomFun{bubbleSort!} function is executed in its local
environment and produces the result.
\endscroll
\autobuttons
\end{page}
%