11 Packages
Packages provide the bulk of package Axiom's algorithmic library, from numeric packages for computing special functions to symbolic facilities for constructor:package differential equations, symbolic integration, and limits. package:constructor
In Chapter 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 Axiom library to make them available for general use.
The way we created the functions in Chapter ugIntProg is typical of how you, as an advanced Axiom user, may interact with Axiom. 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 Axiom 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 Axiom compiler to convert the constructors into executable machine code. An existing compiler in Axiom is available on an ``as-is'' basis. A new, faster compiler will be available in version 2.0 of Axiom.
C ==> Complex DoubleFloat All constructors used in a file
S ==> Segment DoubleFloat must be spelled out in full
INT ==> Integer unless abbreviated by macros
DFLOAT ==> DoubleFloat like these at the top of
VIEW3D ==> ThreeDimensionalViewport a file
CURVE ==> List List Point DFLOAT
)abbrev package DRAWCX DrawComplex Identify kinds and abbreviations
DrawComplex(): Exports == Implementation where Type definition begins here
Exports == with Export part begins
drawComplex: (C -> C,S,S,Boolean) -> VIEW3D Exported Operations
drawComplexVectorField: (C -> C,S,S) -> VIEW3D
setRealSteps: INT -> INT
setImagSteps: INT -> INT
setClipValue: DFLOAT-> DFLOAT
Implementation == add Implementation part begins
arrowScale : DFLOAT := (0.2)::DFLOAT --relative size Local variable 1
arrowAngle : DFLOAT := pi()-pi()/(20::DFLOAT) Local variable 2
realSteps : INT := 11 --# real steps Local variable 3
imagSteps : INT := 11 --# imaginary steps Local variable 4
clipValue : DFLOAT := 10::DFLOAT --maximum vector length
Local variable 5
setRealSteps(n) == realSteps := n Exported function definition 1
setImagSteps(n) == imagSteps := n Exported function definition 2
setClipValue(c) == clipValue := c Exported function definition 3
clipFun: DFLOAT -> DFLOAT --Clip large magnitudes.
clipFun(x) == min(max(x, -clipValue), clipValue)
Local function definition 1
makeArrow: (Point DFLOAT,Point DFLOAT,DFLOAT,DFLOAT) -> CURVE
makeArrow(p1, p2, len, arg) == ... Local function definition 2
drawComplex(f, realRange, imagRange, arrows?) == ...
Exported function definition 4
11.1 Names, Abbreviations, and File Structure
Each package has a name and an abbreviation. For a package of the complex draw functions from Chapter ugIntProg , we choose the name DrawComplex and abbreviation:constructor abbreviation DRAWCX.An abbreviation can be any string of constructor:abbreviation between two and seven capital letters and digits, beginning with a letter. See 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 )show for both the name and the abbreviation. show
Once you have named the package and its abbreviation, you can choose any new filename you like with extension `` .spad'' to hold the definition of your package. We choose the name drawpak.spad. If your application involves more than one package, you can put them all in the same file. Axiom assumes no relationship between the name of a library file, and the name or abbreviation of a package.
Near the top of the `` .spad'' file, list all the abbreviations for the packages using )abbrev, each command beginning in column one. Macros giving names to Axiom 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 DrawComplex in Figure fig-pak-cdraw . After the macro macro definition
S ==> Segment DoubleFloat
the name S can be used in the file as a shorthand for Segment DoubleFloat.The interpreter also allows macro for macro definitions. The abbreviation command for the package
)abbrev package DRAWCX DrawComplex
is given after the macros (although it could precede them).
11.2 Syntax
The definition of a package has the syntax:
PackageForm : Exports == Implementation
The syntax for defining a package constructor is the same as that syntax for defining any function in Axiom. 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 with followed by an explicit list of operations. A preferable way to write the definition of a package is with a where expression:
The definition of a package usually has the form:
PackageForm : Exports == Implementation where
optional type declarations
Exports == with
list of exported operations
Implementation == add
list of function definitions for exported operations
The DrawComplex package takes no parameters and exports five operations, each a separate item of a pile. Each operation is described as a declaration: a name, followed by a colon (:), followed by the type of the operation. All operations have types expressed as mappings with the syntax
source -> target
11.3 Abstract Datatypes
A constructor as defined in Axiom is called an abstract datatype in the computer science literature. Abstract datatypes separate ``specification'' (what operations are provided) from ``implementation'' (how the operations are implemented). The Exports (specification) part of a constructor is said to be ``public'' (it provides the user interface to the package) whereas the Implementation part is ``private'' (information here is effectively hidden---programs cannot take advantage of it).
The Exports part specifies what operations the package provides to users. As an author of a package, you must ensure that the Implementation part provides a function for each operation in the Exports part.The DrawComplex package enhances the facility described in Chapter 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 and . In interactive programming, you simply change the values of variables by 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 setRealSteps and setImagSteps for this purpose.
Another local variable is which can be changed using the exported operation setClipValue. This value is referenced by the internal function 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 (with the appropriate sign).
11.4 Capsules
The part to the right of add in the Implementation add part of the definition is called a capsule. The purpose of a capsule is:
- to define a function for each exported operation, and
- to define a local environment for these functions to run.
What is a local environment? First, what is an environment? environment Think of the capsule as an input file that Axiom reads from top to bottom. Think of the input file as having a )clear all at the top so that initially no variables or functions are defined. When this file is read, variables such as and in DrawComplex are set to initial values. Also, all the functions defined in the capsule are compiled. These include those that are exported (like ), and those that are not (like ). At the end, you get a set of name-value pairs: variable names (like and ) are paired with assigned values, while operation names (like and ) are paired with function values.
This set of name-value pairs is called an 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 local since any changes to the value of a variable in this environment can be seen 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 in your workspace, it does not affect what the 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 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.
11.5 Input Files vs. Packages
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. Axiom 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 Axiom as identifying the type for the argument parameter. Most of the time Axiom goes through the body of your function and figures out the target type that you have in mind. Axiom sometimes fails to get it right. Then---and only then---do you need a declaration to tell Axiom what type you want.
Input files are usually written to be read by Axiom---and by you. file:input:vs. package Without suitable documentation and declarations, your input files package:vs. input file 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 Axiom---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.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.
11.6 Compiling Packages
Once you have defined the package DrawComplex, you need to compile and test it. To compile the package, issue the system command )compile drawpak. Axiom reads the file drawpak.spad and compiles its contents into machine binary. If all goes well, the file DRAWCX.NRLIB is created in your local directory for the package. To test the package, you must load the package before trying an operation.
Compile the package.
Expose the package.
Use an odd step size to avoid a pole at the origin.
Define f to be the Gamma function.
Clip values of function with magnitude larger than 7.
Draw the Gamma function.
11.7 Parameters
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 Chapter 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 ugUserBlocks , we defined functions and to sort a list of integers. If you look at the code for these functions, you see that they may be used to sort any structure with the right properties. Also, the functions can be used to sort lists of any elements---not just integers. Let us now recall the code for .
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
What properties of ``lists of integers'' are assumed by the sorting algorithm? In the first line, the operation # computes the maximum index of the list. The first obvious property is that must have a finite number of elements. In Axiom, this is done by your telling Axiom that has the ``attribute'' finiteAggregate. An attribute is a property that a domain either has or does not have. As we show later in ugCategoriesAttributes , programs can query domains as to the presence or absence of an attribute.
The operation swap swaps elements of . Using Browse, you find that swap requires its elements to come from a domain of category IndexedAggregate with attribute shallowlyMutable. This attribute means that you can change the internal components of without changing its external structure. Shallowly-mutable data structures include lists, streams, one- and two-dimensional arrays, vectors, and matrices.
The category IndexedAggregate designates the class of aggregates whose elements can be accessed by the notation for suitable selectors . The category IndexedAggregate takes two arguments: , a domain of selectors for the aggregate, and , a domain of entries for the aggregate. Since the sort functions access elements by integers, we must choose Integer. The most general class of domains for which and are defined are those of category IndexedAggregate(Integer,Entry) with the two attributes shallowlyMutable and finiteAggregate.
Using Browse, you can also discover that Axiom has many kinds of domains with attribute shallowlyMutable. Those of class IndexedAggregate(Integer,Entry) include Bits, FlexibleArray, OneDimensionalArray, List, String, and Vector, and also HashTable and EqTable with integer keys. Although you may never want to sort all such structures, we nonetheless demonstrate Axiom's ability to do so.
Another requirement is that Entry has an operation <. One way to get this operation is to assume that Entry has category OrderedSet. By definition, will then export a < operation. A more general approach is to allow any comparison function 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 of objects of any type, and a domain , an aggregate of type IndexedAggregate(Integer, S) with the above two attributes. Here is its definition using what are close to the original definitions of and for sorting lists of integers. The symbol ! is added to the ends of the operation names. This uniform naming convention is used for Axiom operation names that destructively change one or more of their arguments.
SortPackage(S,A) : Exports == Implementation where
S: Object
A: IndexedAggregate(Integer,S)
with (finiteAggregate; shallowlyMutable)
Exports == with
bubbleSort!: (A,(S,S) -> Boolean) -> A
insertionSort!: (A, (S,S) -> Boolean) -> A
Implementation == add
bubbleSort!(m,f) ==
n := #m
for i in 1..(n-1) repeat
for j in n..(i+1) by -1 repeat
if f(m.j,m.(j-1)) then swap!(m,j,j-1)
m
insertionSort!(m,f) ==
for i in 2..#m repeat
j := i
while j > 1 and f(m.j,m.(j-1)) repeat
swap!(m,j,j-1)
j := (j - 1) pretend PositiveInteger
m
11.8 Conditionals
When packages have parameters, you can say that an operation is or is not conditional exported depending on the values of those parameters. When the domain of objects has an < operation, we can supply one-argument versions of and which use this operation for sorting. The presence of the operation < is guaranteed when is an ordered set.
Exports == with
bubbleSort!: (A,(S,S) -> Boolean) -> A
insertionSort!: (A, (S,S) -> Boolean) -> A
if S has OrderedSet then
bubbleSort!: A -> A
insertionSort!: A -> A
In addition to exporting the one-argument sort operations sort:bubble conditionally, we must provide conditional definitions for the sort:insertion operations in the Implementation part. This is easy: just have the one-argument functions call the corresponding two-argument functions with the operation < from .
Implementation == add
...
if S has OrderedSet then
bubbleSort!(m) == bubbleSort!(m,< $S)
insertionSort!(m) == insertionSort!(m,< $S)
In ugUserBlocks , we give an alternative definition of bubbleSort using firstfirstList and restrestList 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 setelt which allows us to destructively change the first and rest of a list. Using Browse, you find that these operations come from category UnaryRecursiveAggregate. Several aggregate types are unary recursive aggregates including those of List and AssociationList. We provide two different implementations for bubbleSort! and insertionSort!: one for list-like structures, another for array-like structures.
Implementation == add
...
if A has UnaryRecursiveAggregate(S) then
bubbleSort!(m,fn) ==
empty? m => m
l := m
while not empty? (r := l.rest) repeat
r := bubbleSort! r
x := l.first
if fn(r.first,x) then
l.first := r.first
r.first := x
l.rest := r
l := l.rest
m
insertionSort!(m,fn) ==
...
The ordering of definitions is important. The standard definitions come first and then the predicate
A has UnaryRecursiveAggregate(S)
is evaluated. If true, the special definitions cover up the standard ones.
Another equivalent way to write the capsule is to use an expression: if
if A has UnaryRecursiveAggregate(S) then
...
else
...
11.9 Testing
Once you have written the package, embed it in a file, for example, sortpak.spad. testing Be sure to include an )abbrev command at the top of the file:
)abbrev package SORTPAK SortPackage
Now compile the file (using )compile sortpak.spad).
Expose the constructor. You are then ready to begin testing.
Define a list.
Since the integers are an ordered set, a one-argument operation will do.
Re-sort it using ``greater than.''
Now sort it again using < on integers.
A string is an aggregate of characters so we can sort them as well.
Is < defined on booleans?
Good! Create a bit string representing ten consecutive boolean values true.
Set bits 3 through 5 to false, then display the result.
Now sort these booleans.
Create an ``eq-table'', a table having integers as keys and strings as values.
Give the table a first entry.
And a second.
What does the table look like?
Now sort it.
11.10 How Packages Work
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 bubbleSort!? Also, how is a single compiled function such as bubbleSort! able to sort data of different types?''
After the interpreter loads the package SortPackage, the four operations from the package become known to the interpreter. Each of these operations is expressed as a modemap in which the type modemap of the operation is written in terms of symbolic domains.
See the modemaps for bubbleSort!.
)display op bubbleSort!
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
What happens if you ask for bubbleSort!([1,-5,3])? There is a unique modemap for an operation named bubbleSort! with one argument. Since is a list of integers, the symbolic domain is defined as List(Integer). For some operation to apply, it must satisfy the predicate for some . What ? The third expression of the and requires D1 has IndexedAggregate(Integer, D2) with two attributes. So the interpreter searches for an IndexedAggregate among the ancestors of List (Integer) (see ugCategoriesHier ). It finds one: IndexedAggregate(Integer, Integer). The interpreter tries defining as Integer. After substituting for and , the predicate evaluates to true. An applicable operation has been found!
Now Axiom builds the package SortPackage(List(Integer), Integer). According to its definition, this package exports the required operation: bubbleSort!: 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, rest and swap) from the appropriate domains and then it returns a bubbleSort! to the interpreter together with the local environment for bubbleSort!. The interpreter applies the function to the argument . The bubbleSort! function is executed in its local environment and produces the result.