Previous Home Contents Next

Chapter 21: First notes by T. Daly

21.1 Overview

21.2 A trivial Aldor program

21.3 Building an Aldor type

21.4 A new type: Term - a first representation

21.5 A new Type: Polynomial

21.6 Operations in the Type "Polynomial"

21.7 Parameterized types

21.8 Summary



21.1 : Overview

There are several sections in this tutorial, which is written to introduce concepts in Aldor programming, using a step-by-step development style and mimicking the development of a novice Aldor programmer.

Section 21.2 uses a simple Aldor program to introduce the ideas necessary to understand how to use the compiler, how to use simple types and how to do simple output. We also discuss some differences between Aldor and the C and C++ programming languages.

Section 21.3 introduces building an Aldor Type. This section introduces the ideas of a Type, signatures and export/import issues. It also introduces the split between exports and implementation.

Section 21.4 constructs a new Type, which we call "Term". This section introduces the ideas of representation within types and ``standard'' export lists ("new", "dispose!", "access", "print"). It also introduces commenting styles and testing issues.

Section 21.5 constructs another new type, which we call "Polynomial". This section introduces the ideas of building Types over other Types. It explains printing and uses this function to introduce the question of ``the right place'' to implement certain operations. It introduces the concept of local functions. It also introduces the concept of a Category.

Section 21.6 introduces operations in the Type "Polynomial", rather than operations over another type. Here we introduce the polynomial arithmetic operations of "+", "-" and "*".

Section 21.7 introduces parameterized Types. We build a new "Term" type which is more general than the previous version of Term.

We are not trying to teach programming. The reader is assumed familiar with basic programming concepts and with elementary polynomial operations, such as addition and multiplication. The reader can ignore the comparisons with C and C++ if he doesn't know these languages.

As this is a tutorial, the reader should be aware that we are making design choices motivated by simplicity or clarity rather than issues of efficiency or generality.



21.2 : A trivial Aldor program

21.2.1 Some discussion of the Aldor language for the programmer

21.2.2 Signum - a first function

21.2.3 What is a Type?

We will develop a simple polynomial manipulation program and illustrate the various features of the language. By the end of this tutorial you should be able to write your own Aldor programs.


21.2.1 : Some discussion of the Aldor language for the programmer

These initial comments are intended to give those who are skilled in C and C++ an idea of the Aldor language, based on analogy. Those who are not C programmers should ignore this section.

Aldor is a block structured language that is strongly typed. It follows a syntactic style similar to C. It has the following simple characteristics:


21.2.2 : Signum - a first function

For the first example we will construct a trivial program to determine the sign of its argument (called the SPMquotsignum" function).

The entire function looks like:

Aldor is a strongly typed language but, initially, the compiler does not know anything about particular types (except for a very small number of built-in types). The compiler is shipped with a standard type library. We will have the line #include "aldor" at the top of each file to allow access to these types. The first line of our example program is:

which gives us access to the types SingleInteger and String, both of which are Types (with a capital T).


21.2.3 : What is a Type?

Types (with a capital T) are a way to create special kinds of new things in the world. Suppose we want a special kind of numbers,, such as Roman numerals (the kind you learned in school). We would need two parts to the definition of this new kinds of numbers: a way to store them in the program (called the representation) and a list of things we can do to them, such as add them, subtract them, print them etc. (called the operations). A Type is a kind of box that packages up three things: the operations, the representation and the programs to implement the operations.

Aldor programming usually consists of building new Types. So, when you see a new Type, the thing you need to know is, ``What can I do with this Type?'' or, equivalently, ``What operations are available for this Type?''

SingleInteger is a Type which reflects the underlying machine implementation of integers. That is, it has a defined range based on the size of the machine's word (its representation). There are several dozen operations that we can perform -- but it is sufficient to know that they act like integers for our purposes. That is, we can add, subtract, multiply and compare them, etc.

String is a second Type we will use. We really don't need to know how it is implemented. The only interesting operation on Strings, for our purposes, is printing. This operation is called ``<<''.

To build a Type we need to know the parts of the box (remember: Types are boxes with three interesting parts -- the exported functions, the representation and the implementation of the exported functions).

Our simple signum function is:

Let's look at the parts.

The first line of this form begins:

which is the function header (the rest of the definition is the function body). This header line reads as follows:

``We are defining a function called `signum', which takes one argument called `number', of Type `SingleInteger'. It returns a result of Type `String'.''

The == marks the start of a function body. The function body is surrounded by braces ({ }). Every exit from the function body must be of the correct return Type. In this case, every exit from the signum function must be of Type String (because we said that signumsignum" returns a String).

Within the function body we use the ``=>'' operator. This takes a test (something that is either true or false) on its left hand side and a value to return on its right hand side. If the test is true then we evaluate the right hand side and return its value as the value of the containing sequence. In this case the containing sequence is the program, so as soon as we find one of the tests is true we return the corresponding string as the result. The way in which ``=>'' is used here is similar to the switch construct in C.

Defining the function will not execute it. We call the function and print the resulting value. Printing is done by the ``<<'' operator. (Note that this is not the C++ leftshift operator). The ``<<'' operator has the function header:

This operator takes a TextWriter on its left hand side and an object to print on its right hand side. Its result is a TextWriter object. Since this is an infix operator (there are a few predefined infix operators in the syntax) we can cascade the ``<<'' operators. (Infix means that the function is written between its arguments like the + function rather than being written before the arguments like most functions.) Printing is thus done by:

This line is executed left to right as though it had been parenthesized:

An important thing to remember is that the compiler does not know anything about the particular Types in use, yet the meaning of each thing in our program is defined in a Type. In our case we are using the numbers 10, 0 and -10. The compiler does not know what these things are. We intend them to be SingleIntegers (because that's what our program takes) so we have to add the line:

in our program to tell the compiler that SingleInteger operations can be used. Since there isn't anything else around the 10 gets interpreted as a SingleInteger, which is what we want. It will often be the case in Aldor programs that we need to tell the compiler to import Types.

In our example we call the function signum with its argument (which must be a SingleInteger) and it returns a result of Type String. We call the function at the time we want to print the result. There are three lines in the example which test all possible cases. They look like:





21.3 : Building an Aldor type


22.3.1 Properties -- a first domain



21.3.1 : Properties -- a first domain

Aldor programs, like C++ programs, are normally developed as objects. The idea of an object in these languages is that there exist boxes (we call them domains, C++ calls them classes) that wrap the functions and the data representation together and hide all of the details. All we know about an object is given by the list of exports from its box, in other words the list of exports from the domain. For instance, we know we can add two SingleIntegers because the Type SingleInteger exports the function +.

We would like to define a new Type -- let's call it Properties -- with a list of functions to compute the properties of SingleIntegers. In fact, it will have only one function, the signum function.

So, how do we define a class (um, ... domain)? Each domain has the following (simplified) form:

Remember that we said there are three parts to a domain. The first part is the list of all of the functions we can call from that domain. This is the ``exported list of function signatures''. For our example they look like:

Properties is the name that we give to the domain. The with says that we are exporting a list of function signatures. This list is surrounded by braces. The signum line is slightly different from what we have seen before, and now reads:

The line is a ``function signature''. The signature line is read as:

``We are exporting a function called `SPMquotsignum"' that will take a thing of SPMquotType" `SPMquotSingleInteger"' and return a thing of SPMquotType" `SPMquotString"'.''
In order to define this function we use:

This line is the ``function header''. In the body of the domain we use function headers. The header line is read as:

``We are defining a function called `signum' that will take a particular SingleInteger called `number' and return a particular String.''

So, the exports list is a list of function signatures. Note also the ++ comment that follows the function signature. In export lists the so-called ``plus-plus comments'' are related to the function signature that preceeds them. This kind of comment differs from the - comment in that the ++ comment will show up in the documentation related to the function. Lines that contain a - are ignored starting from the - and ending with the newline. Similarly, lines that contain a ++ are ignored starting from the ++ and ending with the newline; however, the compiler does check the syntax of the ++ comment lines.

After the export list we find the ``add body'', which starts with the == add clause and is surrounded by braces. The SPMquotadd" body contains the representation and implementation information. The add body for our example looks like:

This is the same function definition we had earlier, except that it is now enclosed within a domain. Every exported function signature must have an associated implementation. However, the implementation is now ``hidden'' (encapsulated, if you like larger words) within a domain so it is not visible to the outside world. To make the function visible we need to perform three steps. We construct the signature, put it in the exports list of the domain and import the domain.

When we wish to use the functions exported from the domain Properties, we need to ``import'' from Properties. This ensures that the functions from Properties are in scope. Import allows control over which domains we wish to use. There might be many domains with the same signature and we wish to choose only one.



21.4 : A new type: Term - a first representation

22.4.1 Rep, the representation domain

22.4.2 Importing the Rep

22.4.3 Chosing our export list

22.4.4 New -- the consructor function

22.4.5 Dispose! -- destroying an instance

22.4.6 << -- printint the Type

22.4.7 New overloading

22.4.8 Accessing the representation

22.4.9 A word about testing

22.4.10 Listing

The signum domain does not create a new kind of object, so we didn't specify how objects from Properties were represented. It does not refer to itself. Domains with this structure are sometimes called ``packages'', to distinguish them from domains that refer to themselves in the export list.

Leaving the Properties domain for a while, we now will build a polynomial domain with simple exports and an internal representation.

Polynomials are relatively simple things, composed of terms that are added or subtracted to form the composite polynomial. Let's look at terms.

The terms are composed of products of coefficients and symbols (we are, of course, simplifying the issues but we'll come back to this later). So a term should look like:

We need a representation of a symbol. Usually a symbol is just a single letter and it is sufficient for our purposes to choose the set of ascii letters as our representation of symbols. Note that this will not allow us to write terms like:

This assumes that a term can contain more than one symbol (or, in general, could be composed of terms). We will revisit this design decision later.

We need a representation of coefficients. These are usually called the ring of coefficients over which we build polynomials. The ring has certain operations defined on it. We will ignore this for the moment and choose SingleIntegers (machine integers) as our coefficients. Note that this will not allow us to write the polynomial:

as (2/3) is not a SingleInteger. Thus we will need to revisit this design decision if we need to divide polynomials.


21.4.1 : Rep, the representation domain

Now that we have made those decisions we need a representation for terms. A Term can be stored as a record composed of a coefficient and a symbol. This is written in Aldor as:

This is a new construct for several reasons. The ``==>'' notation ==> defines a macro. Every occurrence of Rep will be replaced by the form on the right side of the arrow.

Records form a Type that is similar to C ``structs''. They have a list of fields (in this case, coef and var) and each field has its own TypeT (in this case, SingleInteger and Character). Records are a useful way of combining many different Types into one data structure.

By convention in Aldor, Rep is used to define the representation of a domain. Such a representation may be defined using either a macro definition, as shown, or a constant definition, with == instead of ==>. It is not essential to define a representation for a domain but it is generally useful, as there are two macros which work specifically on representations.

Contrast what a user sees as the representation of your Type with how the type is implemented: in this case, we have defined our representation (how a term will actually be stored) as a Record -- however, the user will see terms as Terms, that is, as a brand new Type in the world. We will, at times, need to move between the view of the data as a Term and the view of the data as a Record. The macro rep takes a Rep (in this case, a Record) and views it as a domain type (in this case, a Term). The macro per goes the other way: it takes a domain type (a Term) and views it as a Rep (a Record). So:

Sometimes we have a Record and we need a Term (such as when we return a result from a function) so the correct form is:

This will (hopefully) become clear as we progress with the example.


21.4.2 : Importing the Rep

Once we have chosen the representation we must tell the compiler to bring the functions related to that representation into the world (into ``scope''), so that we can use the functions from Record on our representation. The most common method of doing this is to follow the Rep macro definition with the line:

Since Rep is a macro that expands into

this line really reads (after macro expansion in the compiler):

This will import operations from the value of Rep, which allows access to the interior of the object.


21.4.3 : Choosing our export list

Another early step in developing a new domain is the choice of functions to export. These define the Type the user sees. How the Type is represented is much less important than what we can do with the Type, at least from the user's point of view. When you construct a new Type, the choice of representation is an important issue and will impact the efficiency of the resulting code.

You have complete freedom about what functions you export from your domain. What follows is a list that suggests useful exports for every domain. For various reasons you might decide not to implement these functions. We recommend these because users of your domain will expect to perform at least these operations.

It is reasonable that new domains have the following functions:

new
which constructs a new instance of the domain,
dispose!
which destroys an instance,
<<
which prints an instance,
accessors
which allow access to the parts of an instance.
In the description of the domain there is a special symbol, % which refers to ``the type being defined''.

Starting with these as the primitive functions we'll develop them one by one.


New -- the constructor function

The function new should take the parts of a domain representation and construct a new instance of the domain from those parts. For example, the instance 3 is a particular example of the type SingleInteger.

Since we are working with the domain Term we need a function, new, that takes a SingleInteger and a Character (the two things we need to stick into our Record(coef: SingleInteger, var: Character)) and returns an instance of the type Term. The signature of the new function is:

That is, the function new takes two arguments, a SingleInteger and a Character, and returns a new instance of this domain (in this case, the domain Term). Note that we are using % to mean ``this domain''. So, for example:

returns a new Term. Since we haven't decided how to print Terms yet we cannot show what the term looks like; however, this defines the term 3*x.

Now that we know the signature, let's look at the implementation. In the add body we have the following code:

This says that we are implementing the function new. It takes two arguments: number is a SingleInteger and variable is a Character. We return a % (the magic symbol again). That is, we return an instance of ``this domain'' (which is Term). So we have to write a function that takes a number and a variable and constructs a Record(coef: SingleInteger, var: Character). The [number,variable] will do this. However, the returned result is not supposed to be a Record (which is our Rep) but should be a Term (which is our Type). The magic macro that changes a Rep to a % is per. So the final result of per([number,variable]) is a Term.


Dispose! -- destroying an instance

The function dispose! frees up the storage taken up by instances of this domain. In this case, we will ignore the storage issues and return nothing, which is written as (). So the signature is:

Aldor, by default, includes a ``garbage collector'' which reclaims storage that you are no longer using. This strategy should be sufficient to handle storage needs for simple programs.

We will comment that for efficiency reasons it is probably a good idea to have dispose! add discarded items to a list and let new pick discarded items from this list instead of always allocating extra storage. The new and dispose! operations for the primitive array and record types in the basic Aldor library do this, so if you implement your operations in terms of these, this is what you will get. This is an excellent efficiency mechanism if used properly but can be dangerous if the storage is being pointed to by something else. Don't hold on to all the storage you ever use as the program will probably grow too large. The benefits of this technique outweigh the complexity. We're ignoring all of these issues for now.

If we look in the add body, we will find the code that implements the dispose! function. It looks like:

That is, it takes a % (in this case, a Term) as an argument and returns no result.


<< -- printing the Type

Above, we constructed an instance of term. It looked like:

Now we will walk through the steps of printing this term. To print this term we would make the call:

Printing is done using ``<<'', similar to the C++ convention. The signature of this is already defined for Records, SingleIntegers and Characters (the types we are using in our representation). However, it is not defined for instances of our type, Term. The ``<<'' function takes a TextWriter as its left argument (``<<'' is infix) and an instance of Term as its right argument and returns an instance of TextWriter as its result. The symbol print in the above call is a TextWriter.

So our signature is:

(Notice the %. This is a shorthand meaning ``the current domain''. In this case we are talking about the domain Term, so % means Term, similar to the usage of this in C++. However, you will see this symbol show up many times in Aldor code and it has a meaning based on what domain you are defining. It is important to know which % you are talking about. Be very careful about the meaning of this symbol.)

If we look in the add body for the implementation we find:

This says that we have a function ``<<'' that takes a TextWriter and a % (in this case, a Term") and returns a TextWriter.

The second line

We start out with our hands on a Term (in the variable called term1) which we want to print. First we use the form:

to view the term1 variable as our Rep (in this case, a Record"). Then we reach into the record to get the coef information with:

This is a SingleInteger (because that's what we said we would put into our Record). Now we call a function to print the SingleInteger:

This uses the ``<<'' function from SingleInteger which has the signature:

After all of this the first line of the program prints:



The third line

The third line of the program calls

and prints a * string. The printed line now looks like:



The fourth line

Again we need to use

to view the term1 variable as our Rep (in this case, a Record). Then we reach into the record to get the var information with:

This is a Character (because that's what we said we would put into our Record). Now we call a function to print the Character:

This uses the ``<<'' function from Character which has the signature:

After all of this the line now looks like:

Notice that we have not put a newline character in our printing routine. The polynomial domain will print many terms and they need to be strung out on a single line so we let someone else worry about how the line is formatted and concentrate on how a term should look on a line.

We will have much more to say about ``<<'' issues and printing later in this tutorial. For now it is enough to know that if we add the above signature to the export list and a ``<<'' function to our ``add body'' then we can control the way a Term is printed.


21.4.7 : Name overloading

Whew! That is harder to explain than it is to program. However, we are using many different ``<<'' functions and they all have the same name. This is called name overloading. In a different language that doesn't support name overloading we would have to have named the functions with different names like:

We could do that here but it is much more natural to use a single function name for the task we are trying to do rather than the type we are trying to print.

Most computer programming languages let you do this for a very small number of names, or have predefined overloaded operations, but do not allow the addition of new operations. For example, it is usually the case that you can write:

 y=3*4which uses *:(Integer,Integer) -> Integer;
andy=3.0*4.0which uses *:(Float, Float) -> Float;
andy=3*4.0which uses *:(Integer, Float) -> Float;

but you cannot overload most other function names in other languages.


Accessing the representation

Since we have a record of two fields, coef and var, we'd like the world to be able to look inside and access the fields without violating the encapsulation. There is no need for users to know that Terms are implemented as Records, only that there are two parts. The accessors need to reach inside a particular Term so each accessor takes a Term as its argument and return the part as its result.

In the ``add body'' we find the implementations:

that is, coef takes a Term (verb"term1"), pretends it is a Record, reaches into the record to get the coef field (which is a SingleInteger) and returns it;

var takes a Term (term1), pretends it is a Record, reaches into the record to get the var field (which is a Character) and returns it.


A word about testing

Every exported function should be tested. You will notice in the examples that follow we try to find boundary cases for all of the exported functions. It is a reasonable idea to leave the test cases in the original source file for later use. Changes to the source file can be tested easily by uncommenting the test cases. The commented test cases are useful documentation for the end user, who needs to know how to use various functions. The easiest method of adding test cases and commenting them out is to surround them with the compiler directive:

If you compile the file and use the compiler switch -DTEST you will compile all of the test cases. Running the file will run the test cases. Everything between the compiler directives (#if .. #endif) will be compiled.

If you compile the file without this compiler switch, you will compile the file without the test cases. Running the file will not run the tests. Everything between the compiler directives will be commented out.


Listing




21.5 : A new Type: Polynomial

22.5.1 Deciding on a representation

22.5.2 The type tower -- a closer look at Term

22.5.3 BasicType

22.5.4 Implementing equality (=) in Term

22.5.5 Implementing sample in Term

22.5.6 Fulfilling the contract

22.5.7 Polynomial -- the definition

22.5.8 Printing -- a digression

22.5.9 Polynomial -- a return from printing

22.5.10 Listing

For complete listing for this section see section 21.5.10.


21.5.1 : Deciding on a representation

We plan to construct our first polynomial. It will consist of Terms added together (we will ignore the signs of the terms for now). Since polynomials consist of a variable number of terms, we will need to mark each term with its respective power. We could do this in two ways...

Each term could have an explicit power attached. This is called a sparse representation because not all of the terms in a polynomial need to be present. We do not need to keep zero terms in a sparse representation.

An alternative is to represent each term by its position in a data structure. The position is the power of the term. This is called a dense representation. Dense representations need a term in every position of the representation even if the term is zero.

In general, a sparse representation is cheaper to store and harder to manipulate. Since this is a tutorial we will use a dense representation. This will certainly make it expensive to store x1000 -- but should simplify the code.

The representation will be an Array long enough to hold the terms. Array element 1 holds the constant term, array element 2 holds the x1 power term, etc. The array will be one longer than the highest power in the polynomial.

So we need the lines:


21.5.2 : The type tower -- a closer look at Term

Another important fact is that we've chosen Array(Term) as our representation. This assumes that the Type constructor Array will accept Term as a type it can use for elements of arrays. However, when we look at the definition of the Array (in array.as, in your Aldor samples/libaldor directory -- see chapter 29) we see the following domain definition:

This definition tells us that the argument to Array must be of type BasicType. We cannot use this definition of Array to build arrays of things that do not satisfy the definition of BasicType. When we try to do so, the compiler will see the definition:

and complain that Term is not of Type ``BasicType''.

So we have to change the domain header for Term to declare that Term is a BasicType. Our old domain header said:

and we change it to read:

which says that Term is a BasicType with some additional functions. Now when we try to compile it the compiler says:

Oh, bother (as Winnie the Pooh would say). The compiler is unable to accept that Term is a BasicType because Term does not provide all of the required functions.

To build up a data structure like Array(Term) (which we call a type tower in Aldor) each Type in the tower has to provide all of the functions expected by the next step in the tower. Why? Well, Array needs to be able to decide if two elements are equal. Everything that is a BasicType must have an = function so that Array knows that it has a way to decide if two array elements are equal without knowing anything about an array element. All it has to do is get the two array elements and call equal from their Type.

Term, as we have defined it so far, does not implement an = function.


21.5.3 : BasicType

Let's look at BasicType for a moment (in aldorcat.as in the Aldor samples/libaldor directory -- see chapter 29). BasicType has the following definition:

BasicType is a type called a Category, or metaclass. For something to be a BasicType it must implement the functions that are in the export list. Term does not implement the following functions: =, ~=, ``<<'', sample and hash. Without these, we cannot consider Term to be a BasicType.

Look carefully at this definition. There are three functions at the bottom that are marked as default. That means that, if the domain (in this case Term) does not implement these functions, the default definitions from the Category" will be used. So, we do not need to implement the functions ~=, hash and ``<<.'' (Well, almost....)

Notice also that there are two definitions of ``<<''. They have different signatures. That means that there are two different functions with the same name. This is not a problem -- in fact, it is a feature. Aldor will only consider a function call to match a function definition if the name, the type of each argument and the type of the result are the same. So, even if we have two functions with the same name, it is clear that the rest of the signature is different and so they are different.


21.5.4 : Implementing equality (=) in Term

Ultimately, we need to do several things: we need to implement the = function for the domain Term; we need to define sample; we need to export both functions from Term and we need to declare that Term is now fulfilling the contract of BasicType.

Let's do them one at a time. The signature that we need to export for the function = looks like:

We need to be able to compare two Term objects to decide whether they are equal. In this case, a working definition might be that two Term" objects are equal if and only if the coefficients are equal and the variables are equal. Notice that we use the definition of equality defined by the types we used to build Term. This is an important rule of composing and constructing domains.

This function implementation needs to be put in the add body of Term:

This says that we have an infix function = which takes two arguments: term1 of Type % (in this case, Term) and term2 of Type % (in this case, Term) and returns a Boolean.

The second line calls the function with signature:

because coef(term1) and coef(term2) both return SingleIntegers and the ``=>'' needs a Boolean result on its left hand side. If they are not equal then the terms cannot be equal and we return false.

The third line says call the function with signature:

because var(term1) and var(term2) both return Character and the ``=>'' needs a Boolean result on its left hand side. If they are not equal then the terms cannot be equal and we return false.

The fourth line (if we get to it) says that we have passed all of the tests so the terms must be equal and we return true.


21.5.5 : Implementing sample in Term

The second signature we need to implement is:

That is, we need to return a sample element of the domain. A reasonably harmless sample element would be one with a 0 coefficient since it would never show up in the printed representation. Alternatively, we could return an element with the 1 coefficient and the variable x. In general, the sample element should be the easiest (in some sense) to compute, because no user of the domain can rely on specialised properties of the sample, such as one-ness or emptyness. For now, let's return the 0 element. Since the variable doesn't matter, we'll use x.


21.5.6 : Fulfilling the contract

The next step would be to add both signatures to the export list of Term -- but it turns out that we don't have to do this. Look carefully at the definition of = and sample in BasicType. The signatures read:

Notice that they use %, not BasicType. Remember that % means ``the current domain''. So the signature that BasicType exports is automatically valid for Term when used in Term". We only need to implement these functions. Finally, as we have fulfilled the contract of being a BasicType, we declare that we are a BasicType. This allows Array(Term) to be constructed.

The new definition line and exports for the Term domain look like:

But we get all of the signatures exported from BasicType in addition so the real exports are those from BasicType and Term (that is, we can call all of these functions on Terms, even though it does not look as if they are exported from Term):

Notice that we also get ~=, hash and ``<<'' implementations for free from BasicType. We have the option of providing our own definition which will override the default definition, but we do not need to do this at the moment. That is, we can say:

(which is false, by our definition) but we don't have to implement this function in the add" body of Term. It is inherited from being a default in BasicType. That's why we said

We are saying that we want all of the signatures from BasicType and that we provide any implementations that we need to be a BasicType.

This type checking of export lists is a fundamental feature of the Aldor language. Since Term is a BasicType we know that it will have certain features and we can depend on this fact. In particular, we know that we can compare any two Terms for equality (because Term is a BasicType and all BasicTypes have a definition for equality).


21.5.7 : Polynomial -- the definition

As usual, we need the minimum functions for a domain:

new
which constructs a new instance of the domain,
dispose!
which destroys an instance,
<<
which prints an instance,
accessors
which allow access to the parts of an instance.

The new function takes a list of type Term", and returns an instance of a Polynomial. The signature is:

Notice that the % in this signature refers to the current domain,
Polynomial, not to the domain Term we were using above. Within a domain definition it always refers to the current domain.

The dispose! function does nothing interesting at this time and returns nothing.

The ``<<'' function has the same signature as the ``<<'' function from the Term domain but the % refers to Polynomial:




21.5.8 : Printing -- a digression

Printing polynomials is a mildly interesting issue. Let's do a step by step code development of the ``<<'' function.

We need to understand the requirements of the ``<<'' function a little better. The standard function header is:

which means that we expect a stream as our left hand argument (the ``<<'' operator is infix) and a poly object as our right hand object. Within the body of the function, printing is done by referring to the stream:

this will print the poly on the stream, followed by a newline. It is normal to return stream as the last thing in the body of the ``<<'' function.

A first cut is to just print each term of the polynomial (except the last) followed by a + sign, thus:

When we do this our polynomial will look something like:

which is correct but somewhat ugly.

First we simplify the printing of the zeroth order term. Since anything to the zero power is 1 that term should be printed as 1. The change we need to make is to just print the coef of the last term. Since poly.size is of type Term we can use the function coef from Term directly:

Next we note that the x^1 notation is unnecessary, so we change the index and print this term as x:

A third change is that we do not want to print terms of the form 0*x^n. That is, if the term has a zero coef we want to skip the printing. We could reach into the term by asking for the coef, but there is another way to do this. Asking if a term is zero is an interesting question of anything of type Term so we will change Term to export a zero? function. It is a trivial change but a better programming choice. So, the following signature gets added to Term:

and we can now use it in Polynomial's implementation of ``<<'' thus:

This will now skip printing terms whose coefficient is zero. However, it has a poor hack for handling the x^0 term. The problem is that we print trailing + signs after every term except the last. What happens if we decide not to print the last term (because it is zero)? Well, if we print nothing we have a dangling + sign. So, we cheat and print 0.

We can do better. The problem is with the program design. It prints a + without knowing that there will be a trailing term. It needs to check all trailing terms for nonzero to decide to print a +. This could be done but is inefficient. A better hack is to print a prefix + whenever we print a term (except the first, of course). So, another shot at it follows:

And now, another problem ... (these all fall under the universal law: ``There is no such thing as a simple job'') ... what happens if the whole polynomial contains nothing but zero coefficients? The code given above will print nothing, but should print a 0. We can get this situation if we subtract a polynomial from itself. Each term of the result will be zero and the whole list of terms will be zero.

We could hack the code in several ways. The simple fix is to check to see if the prefix string is still blank at the end of printing. If that is the case and the trailing term is zero then we didn't print anything so we can print a 0. Simple but ugly. The ugliness comes into play because this function knows what the zero polynomial looks like. Yes, it is part of the implementation of polynomial but there is no reason why we have to hard code the representation into the logic of the program so deeply. Besides, we are not the only ones who will want to know that this is a zero polynomial, so we should adopt the same approach we used with Term and export a zero? function. The signature looks like:

(Notice again that we have the same signature as the zero? from Term but the % now refers to Polynomial. It is vital that you know what % means at any given time. Indeed, the compiler spends a large amount of time deciding the same philosophical question.)

Oh, by the way, we have another design decision to make (remember the universal law). Our polynomial representation allows many representations for the zero polynomial. Any list of zero coefficient terms is a zero polynomial. We could write a function to check this condition but it would be better to decide on a single representation of zero. This is known in the literature as a canonical representation. We can get such a representation if we enforce the rule that no polynomial has a zero coefficient for the highest exponent. If we generate a polynomial that has a zero coefficient as the highest exponent we shorten the polynomial representation until this is no longer true. Following this rule the zero polynomial is represented as a list of length 0.

Canonical representations are important for deciding various questions such as equality or zero equivalence. Decisions about this issue and issues like sparse versus dense representations serve to distinguish one computer algebra system from another in fundamental ways. There are many tradeoffs but no one correct solution.

So, we add the zero? poly test early in the printing:

Still another problem. We print 1*x. Normal mathematical notation elides the 1 and would just print x. The best place to fix this is in Term. Printing a term which has a coef of 1 should just print the variable.

One more problem, while we are at it. What happens if the term has a negative coefficient? Well we print something like:

which is certainly correct but really ugly. Let's fix that with another pass. We need to be able to negate a term so that we can flip the sign of a negative term. So we add the signature:

to Term. This is unary negation. We also need predicates that tell whether a term is positive or negative:

We might as well add the ability to add and subtract terms while we are at it, since we will need them later when adding and subtracting polynomials. These signatures need to be added to Term's export list:

Now, back to printing the polynomial with negative terms. Let's make two local functions: prefix, which takes a term and returns the correct prefix string, and abs, which takes a term and returns a term with a positive sign. Local functions are in the implementation section of the code but their signature is not in the exports list. Since prefix and abs are not in the export list of Polynomial there is no way for anyone to know these functions exist. They are hidden in the Polynomial box. They aren't particularly general or interesting, but make the code (slightly) clearer.

Remember: There is no such thing as a simple job.


21.5.9 : Polynomial -- a return from printing

The accessor functions for a Polynomial fall into several cases. We would like to be able to access the leading term of the polynomial and each term of the polynomial. A single term is referred to as a monomial.

Notice that our representation of polynomials does not provide the exponent directly, so the user has to know what the exponent of a given term should be. In general, the i term from the polynomial will be x^i. However, the user needs to know the highest exponent of the polynomial (referred to as the degree):

This is good enough for a first try at a Polynomial type. The next example is an implementation of this type.


21.5.10 : Listing




21.6 : Operations in the Type ``Polynomial''

22.6.1 Listing

For complete listing for this section see section 21.6.1.

Polynomial"s are interesting objects and one can define several dozen interesting operations on objects of this Type". We introduce two just to give you the details of how to do it. The two operations are addition (+) and subtraction (-). These are infix operations. Their signatures look like:

That is, they take two objects, both of the current Type (in this case, Polynomial), and return an object of the same Type.

The implementations are fairly straightforward. Remember that each polynomial is just an array of terms and that the position in the array defines the exponent of the term. Since this is the case, in principle we only need to create an array of the right target length and loop over each element pair, adding or subtracting them. A slight complication is that the arrays may be of different lengths: we overcome this by choosing the greater length for the final array, and taking the sum or difference only for terms which exist in both polynomials.

This is not strictly correct, however, since the subtraction can generate terms which are zero at the highest powers of the polynomial. We should reduce the length of the polynomial to elide these terms.

Now we begin a series of tests for the various cases of creating and printing polynomials. First we need to bring the domains we will use into scope.

Since polynomials are lists of terms we create a few terms in the variable x, which we can use to construct polynomials.

We need to check the handling of leading negative signs:

We need to check that we print 1*x as x.

We need to check that 0*x is skipped properly:

We need to check that we print the zero polynomial properly:

We need to check that term arithmetic is properly implemented:




21.6.1 : Listing




21.7 : Parameterized types

22.7.1 Listing

The complete listing for this section is in section 21.7.1.

Types can be more general than we have seen so far. One generalization is to allow the types to take parameters. That is, we can construct a type which will change its behavior depending on some other type.

If we look at general polynomials, we find that there are several different types of coefficients. We could have polynomials of the form:

The first polynomial has integer coefficients. The second has real coefficients and the third has rational (ratios of integers) coefficients. The type of number allowed in the coefficient of a polynomial is determined by the ring of coefficients. Rings are simple mathematical objects that define operations like addition and subtraction. Since polynomials depend on the terms to define what it means to add or subtract something, we find that polynomials change their behavior depending on the ring of coefficients chosen.

We could implement this by defining ``integer'' polynomials, ``real'' polynomials and ``rational'' polynomials as separate types. However, most of the operations we want are common to all of these polynomial types. What we would like to be able to do is define Polynomials that take different kinds of Terms.

The same argument applies for Terms. Rather than having many different kinds of Terms, we can change Term to take a parameter that defines the kind of coefficients to use. Let's start this whole process by modifying Term to take a parameter which tells us the Type of a coefficient.

The previous Type definition line for Term was:

which has been changed to:

There is much to say about this change. The first and most notable difference is that Term is no longer a constant Type. It is now a function that takes an argument. We have given a name to the argument and, as in all of our function definitions, given the Type of the argument.

One question that arises is how and why we chose the type OrderedRing". When we build Type towers we depend on the things under us in the tower to supply certain operations. If we build on something that does not supply the needed operations then we have no meaning for our program (what would it mean to add two things of Type Display, for example).

A reasonable initial guess for a declaration line might be:

but this fails, because the code that follows assumes that we can compare the coefficient to the constant 1. However, things that are BasicTypes only have the operations: (=, ~=, ``<<, sample, hash) and are not required to have the constant 1. The guarantee that a Type has the constant 1 first appears in the (very primitive) type Monoid (see figure 25.1). So we could satisfy this requirement with the definition line:

Again we run into a problem: some of the operations we have implemented in Term (like positive?) require us to use the > operation to compare two coefficients. Being able to compare two things to decide if one is greater implies that there is an order. Pigments, for example, are not ordered. So we need to go further into the Type hierarchy to find something that is both a Monoid and has Order. The required Type is OrderedRing. So, in order (intentional pun) to guarantee that we will be able to compare coefficients for equality to 1 and compare two coefficients to decide which is larger, we have to give Term something that is at least an OrderedRing. This gives us the required function definition line:

We originally wrote the Rep so that it assumed that the coef field of the Record (which is how we store Terms internally) would be of Type SingleInteger. We must change this. The old Rep read:

and now it reads:

This tells us that we can store anything that satisfies our CoefType requirement in the internal representation.

The next change we need to make is in the signature lines of certain functions. The old signature for the function new was:

which has been changed to:

so that we used to require a SingleInteger" as the coefficient and now we can have any coefficient that is of type CoefType". This can be anything, as long as it is at least an OrderedRing".

Since we changed the function signature we must make the corresponding change in the function header line. It used to read:

and now it reads:

Similarly, we assumed that coef would return a SingleInteger":

and now it returns anything that is stored in the Term".

Since we changed the function signature we must make the corresponding change in the function header line. It used to read:

and now it reads:




21.7.1 : Listing

Many thanks to the reviewers: Peter Broadbery, Robert Corless, George Corliss, Tim Daly, Jr., Pietro Iglio, Phillip Santas, Jon Steinbach and Stephen Watt.


21.8 : Summary

At this point you know enough to write reasonably functional Aldor programs. We have introduced the concept of a domain as a means of structuring Aldor programs. We have shown examples of domains and explored the various parts, namely the export list, the representation and the implementation. We have shown how to connect the domain to the existing type hierarchy.


Previous Home Contents Next