Chapter 21: First notes by T. Daly

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.

21.2 : A trivial Aldor program

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:

• Printing is done using the ``<<'' operator. For example:
  print << "this is a number: " << 3 << newline;

• Assignment uses :=. For example:
  a := 3;

• The conditional statement has the form:
  if condition then statement else statement;
  For example:
  if a > 0 then print << "+" else print << "-";

  Note that you must use = instead of == for equality and that the if then else construct is an expression producing a value, as in:
  x := if a = 0 then 1 else 2

  This is the equivalent of the C/C++ expression:
  x = (a == 0 ? 1 : 2)

• Iteration may be performed with the repeat statement. For
  example:
  for i in 1..10 repeat print << i;

  In Aldor you can iterate over structures in a more elegant and abstract fashion than in C, where you normally need to write loops which directly access the representation of data structures, or C++, where you need to define friend iterator classes. In Aldor every domain can provide a generator abstracting the traversal of its elements. So, for instance, you can write:

  import from List SingleInteger;
  ls := [1,2,3,4,5];
  for elem in ls repeat print << elem << newline;
  

• Sequences of statements may be surrounded by braces. For example:

  {
    a := 3; 
    if a > 0 then
            print << "positive" 
    else 
            print << "negative"
  }
  

  In C/C++ the ; is a terminator, while in Aldor it is a separator. This means that the ; is not necessary after the last statement inside braces. However, the compiler will not complain if one is used.

• There is no main (unless you want one). Programs are compiled as files. Top level forms (such as print) that occur in the file are executed when the (compiled) file is run. The executable version of a file which contains:

  #include "aldor"
  print << "hello, world" << newline;
  

  will print
  hello, world
  when it is run. This is similar to a ``compiled interpretation language'' like several new versions of Basic.

• Integers, strings and floating point numbers are not built into the language, but need to be explicitly imported. See the language description for details.

• domains and categories are similar to the C++ concept of classes and abstract classes. However, functions match both on the types of their arguments and the on types of the results. C++ ignores result types when trying to match function signatures.

• In contrast to C and C++, which are never indentation sensitive, the Aldor compiler can optionally take account of indentation. Using the #pile directive at the top of a file instructs Aldor to consider sequences of statements at the same indentation level as belonging to the same block, when braces are omitted.

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:

#include "aldor"

signum(number: SingleInteger): String == {
        number > 0 => "Positive"; 
        number = 0 => "Zero";
        "Negative"
}

import from SingleInteger;
print << signum 10 << newline;
print << signum 0  << newline;
print << signum(-10) << newline;

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:

  #include "aldor"

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:

signum(number: SingleInteger): String == {
        number > 0 => "Positive"; 
        number = 0 => "Zero";
        "Negative"
}

The first line of this form begins:

 
        signum(number: SingleInteger): String ==

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:

(stream: TextWriter) << (thing: String): TextWriter ==

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:

 print << "first thing" << "second thing" << ... << newline;

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

 ((((print << "first thing") << "second thing") << ...) << newline);

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:

 import from SingleInteger;

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:

print << signum(10) << newline;
print << signum(0) << newline;
print << signum(-10) << newline;

21.3 : Building an Aldor type

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 +.

#include "aldor"

Properties: with {
        signum: SingleInteger -> String;
                ++ signum will return the sign of a number as a String
 }
== add {
        signum(number: SingleInteger): String == {
                number > 0 => "Positive";
                number = 0 => "Zero";
                "Negative"
        }
 }

import from SingleInteger;
import from Properties;
print << signum(10) << newline;
print << signum(0) << newline;
print << signum(-10) << newline;

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:

DomainName: with {
        exported list of function signatures
}
== add {
        representation
        implementations of exported functions
}

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: with {
        signum: SingleInteger -> String;
                ++ signum will return the sign of a number as a String
}

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:

signum: SingleInteger -> String;

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"'.''

signum(number: SingleInteger): String ==

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:

== add {
        signum(number: SingleInteger): String == {
                number > 0 => "Positive";
                number = 0 => "Zero";
                "Negative"
        }
}

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

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:

Rep ==> Record(coef:SingleInteger, var:Character);

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:

per: Record(coef: SingleInteger, var: Character) -> Term;
rep: Term -> Record(coef: SingleInteger, var: Character);

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:

rep(termobject)

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:

import from Rep;

Since Rep is a macro that expands into

Record(coef: SingleInteger, var: Character)

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

import from Record(coef: SingleInteger, var: Character);

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.

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:

new: (SingleInteger, Character) -> %;

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:

new(10, char "x")

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:

new(number: SingleInteger, variable: Character): % ==
        per([number, variable]);

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:

dispose!: % -> ();

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:

dispose!(ignore: %): () == {}

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:

new(10, char "x")

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

print << new(10, char "x")

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:

<<: (TextWriter, %) -> TextWriter;

(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:

(port: TextWriter) << (term1: %): TextWriter == {
         port << rep(term1).coef;
         port << "*";
         port << rep(term1).var
 }

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:

rep(term1)

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:

rep(term1).coef

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:

port << rep(term1).coef;

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

<<: (TextWriter, SingleInteger) -> TextWriter

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

10

The third line of the program calls

<<: (TextWriter, String) -> TextWriter

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

10*

Again we need to use

rep(term1)

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:

rep(term1).var

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:

port << rep(term1).var;

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

<<: (TextWriter, Character) -> TextWriter

After all of this the line now looks like:

10*x

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:

printTerm
printSingleInteger
printCharacter
printString

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*4	which uses	*:(Integer,Integer) -> Integer;
and	y=3.0*4.0	which uses	*:(Float, Float) -> Float;
and	y=3*4.0	which 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.

coef: Term -> SingleInteger;
var:  Term -> Character;

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

coef(term1: %): SingleInteger == rep(term1).coef;

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(term1: %): Character == rep(term1).var;

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 TEST
        testcase1
        testcase2
        ...
#endif

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

#include "aldor"

Term: with {
        new: (SingleInteger, Character) -> %;
        dispose!: % -> ();
        <<: (TextWriter, %) -> TextWriter;
        coef: % -> SingleInteger;
        var:  % -> Character;
 }
== add {
        Rep ==> Record(coef: SingleInteger, var: Character);
        import from Rep;

        new(number: SingleInteger, variable: Character): % == 
                 per([number, variable]);

        dispose!(ignore: %):() == {}

        (port: TextWriter) << (term1: %): TextWriter == {
                port << rep(term1).coef;
                port << "*";
                port << rep(term1).var
        }

        coef(term: %): SingleInteger == rep(term).coef;

        var(term: %): Character == rep(term).var;
 }

import from SingleInteger;
import from Character;
import from Term;
term1 := new(3, char "x");
print << term1 << newline;
print << coef term1 << newline;
print << var term1 << newline;
dispose! term1;

21.5 : A new Type: Polynomial

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 x¹⁰⁰⁰ -- 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 x¹ power term, etc. The array will be one longer than the highest power in the polynomial.

So we need the lines:

Rep ==> Array Term;
import from Rep;

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

21.5.3 : BasicType

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:

=: (%, %) -> Boolean;

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:

(term1: %) = (term2: %): Boolean == {
        coef term1 ~= coef term2 => false;
        var  term1 ~= var term2  => false;
        true
}

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:

~=: (SingleInteger, SingleInteger) -> Boolean

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:

~=: (Character, Character) -> Boolean

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:

sample: %;

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:

=: (%, %) -> Boolean;
sample: %;

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:

Term: BasicType with {
        new: (SingleInteger, Character) -> %;
        dispose!: % -> ();
        <<: (TextWriter, %) -> TextWriter;
        coef: % -> SingleInteger;
        var:  % -> Character;
 }

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):

=:      (%, %) -> Boolean;      ++ Equality test.
~=:     (%, %) -> Boolean;      ++ Inequality test.
<<:     (TextWriter, %) -> TextWriter;  ++ Basic output.
<<:     % -> TextWriter -> TextWriter;  ++ Basic output.
sample: %;      ++ Example element.
hash:   % -> SingleInteger;     ++ Hashing function.
new:    (SingleInteger, Character) -> %;
dispose!: % -> ();
<<:     (TextWriter, %) -> TextWriter;
coef:   % -> SingleInteger;
var:    % -> Character;

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:

new(10, char "x") ~= new(10, char "x")

(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

Term: BasicType with {

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:

new: List(Term) -> %;

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.

dispose!: % -> ();

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

<<: (TextWriter, %) -> TextWriter;

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:

(stream: TextWriter) << (poly: %): TextWriter

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:

stream << poly << newline;

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:

(stream: TextWriter) << (poly: %): TextWriter == {
        size: SingleInteger := #(rep(poly));
        for i in 1..(size-1) repeat 
                stream << poly.i << "^" << (size - i) << " + ";
        stream << poly.size
}

When we do this our polynomial will look something like:

3*x^2 + 2*x^1 + 1*x^0

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:

(stream: TextWriter) << (poly: %): TextWriter == {
        size: SingleInteger := #(rep(poly));
        for i in 1..(size-1) repeat
                stream << poly.i << "^" << (size - i) << " + ";
        stream << coef(poly.size)
}

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

(stream: TextWriter) << (poly: %): TextWriter == {
        size: SingleInteger := #(rep(poly));
        for i in 1..(size-2) repeat 
                stream << poly.i << "^" << (size-i) << " + ";
        stream << poly.(size-1) << " + "
        stream << coef(poly.size)
}

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:

zero? % -> Boolean;

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

(stream: TextWriter) << (poly: %): TextWriter == {
        size: SingleInteger := #(rep(poly));

        for i in 1..(size-2) repeat 
              if not zero?(poly.i) then 
                      stream << poly.i << "^" << (size - i) << " + ";

        if not zero?(poly.(size-1)) then 
              stream << poly.(size-1) << " + ";
        if zero?(poly.size) then
              stream << 0
        else
              stream << coef(poly.size)
}

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:

(stream: TextWriter) << (poly: %): TextWriter == {
        size: SingleInteger := #(rep(poly));
        prefix: String := "";
        for i in 1..(size-2) repeat
              if not zero?(poly.i) then {
                      stream << prefix << poly.i << "^" << (size - i);
                      prefix := " + "
              }
        if not zero?(poly.(size-1)) then {
                stream << prefix << poly.(size-1);
                prefix := " + "
        }
        if not zero?(poly.size) then 
                stream << prefix << coef(poly.size);
       stream
}

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:

zero?: % -> Boolean;

(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:

(stream: TextWriter) << (poly: %): TextWriter == {
        zero? poly => stream << 0;

        size: SingleInteger := #(rep(poly));
        prefix: String := "";

        for i in 1..(size-2) repeat
                if not zero?(poly.i) then {
                       stream << prefix << poly.i << "^" << (size-i);
                       prefix := " + "
                }
        if not zero?(poly.(size-1)) then {
                stream << prefix << poly.(size-1);
                prefix := " + "
        }
        if not zero?(poly.size) then 
                stream << prefix << coef(poly.size);
        stream
}

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:

-3*x^2 + -2*x + -1

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:

-: % -> %;

positive? % -> Boolean;
negative? % -> Boolean;

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.

prefix(term: Term): String ==
        if negative? term then " - " else " + ";

abs(term: Term): Term ==
        if negative? term then -term else term;

(stream: TextWriter) << (poly: %): TextWriter == {
        zero? poly => stream << 0;

        size: SingleInteger := #(rep(poly));
        prefix: String := if negative?(poly.1) then " - " else "";

        for i in 1..(size-2) repeat
                if not zero?(poly.i) then {
                        stream << prefix << abs(poly.i);
                        stream << "^" << (size - i);
                        prefix := prefix(poly.(i+1))
                }
        if not zero?(poly.(size-1)) then {
                stream << prefix << abs(poly.(size-1));
                prefix := prefix(poly.size)
        }
        if not zero?(poly.size) then 
                stream << prefix << abs(coef(poly.size));
        stream
}

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.

leadingMonomial: % -> Term;
apply: (%, SingleInteger) -> Term;

degree: % -> SingleInteger;

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

#include "aldor"

Term: BasicType with {
        new: (SingleInteger, Character) -> %;
        dispose!: % -> ();
        <<: (TextWriter, %) -> TextWriter;
        coef: % -> SingleInteger;
        var:  % -> Character;
        zero?: % -> Boolean;
        positive?: % -> Boolean;
        negative?: % -> Boolean;
        -: % -> %;
        -:(%,%) -> %;
        +:(%,%) -> %;
}
== add {
        Rep ==> Record(coef: SingleInteger, var: Character);
        import from Rep;

        new(number: SingleInteger, variable: Character): % == 
                per [number, variable];

        dispose!(ignore: %):() == {}

        (stream: TextWriter) << (term: %): TextWriter ==
                if rep(term).coef = 1 then
                         stream << rep(term).var
                else {
                         stream << rep(term).coef;
                         stream << "*" << rep(term).var
                }

        coef(term: %): SingleInteger == rep(term).coef;

        var(term: %): Character == rep(term).var;

        (term1: %) = (term2: %): Boolean == {
                coef term1 ~= coef term2 => false;
                var  term1 ~= var term2  => false;
                true
        }

        sample: % == per [0, char "x"];

        zero?(term: %): Boolean     == coef(term) = 0;

        positive?(term: %): Boolean == coef(term) > 0;

        negative?(term: %): Boolean == coef(term) < 0;

        -(term: %): % == per [-coef(term), var term];

        (term1: %) - (term2: %): % == {
                var term1 ~= var term2 => 
                       error "Subtracting terms with incompatible vars";
                per [coef(term1) - coef(term2), var term1]
        }

        (term1: %) + (term2: %): % == {
                var term1 ~= var term2 => 
                       error "Adding terms with incompatible vars";
                per [coef(term1) + coef(term2), var term1]
        }
}

Polynomial: with {
        new: List(Term) -> %;
        dispose!: % -> ();
        <<: (TextWriter, %) -> TextWriter;
        leadingMonomial: % -> Term;
        apply: (%, SingleInteger) -> Term;
        degree: % -> SingleInteger;
        zero?: % -> Boolean;
}
== add {
        import from List Term;
        import from SingleInteger;
        Rep ==> Array Term;
        import from Rep;

        new(terms: List Term): % == {

                size: SingleInteger := #terms;
                result: Rep := new(size, sample@Term);

                for i in 1..size repeat
                        result.i:=terms.i;

                per result
        }

        dispose!(ignore: %):() == {}

        prefix(term: Term): String == 
                if negative? term then " - " else " + ";

        abs(term: Term): Term == 
                if negative? term then -term else term;

        (stream: TextWriter) << (poly: %): TextWriter == {
                zero? poly => stream << 0;

                size: SingleInteger := #(rep(poly));
                sign: String := if negative?(poly.1) then " - " else "";

                for i in 1..(size-2) repeat
                        if not zero?(poly.i) then {
                                stream << sign << abs(poly.i);
                                stream << "^" << (size - i);
                                sign := prefix(poly.(i + 1))
                        }

               if not zero?(poly.(size - 1)) then {
                       stream << sign << abs(poly.(size-1));
                       sign := prefix(poly.size)
               }
               if not zero?(poly.size) then 
                       stream << sign << abs(coef(poly.size));
               stream
        }              

        leadingMonomial(poly: %): Term == 
                rep(poly).(#(rep(poly)));

        apply(poly: %, exponent: SingleInteger): Term == 
                rep(poly).exponent;

        degree(poly: %): SingleInteger == #(rep(poly));

        zero?(poly: %): Boolean == #(rep(poly)) = 0;
 }

#if TEST

import from Character;
import from SingleInteger;
import from List Term;
import from Polynomial;
var: Character := char "x";
term1 := new(3, var);
term2 := new(2, var);
term3 := new(1, var);
term4 := new(0, var);
term5 := new(-3, var);
--  term6 := -term5;
print << new(list(term5,term5,term5)) << newline; -- negative signs
print << new(list(term3,term2,term1)) << newline; -- 1 elision
print << new(list(term1,term2,term3)) << newline;
print << new(list(term4,term2,term3)) << newline;
print << new(list(term1,term4,term3)) << newline;
print << new(list(term4,term4,term3)) << newline;
print << new(list(term1,term2,term4)) << newline; -- bad leading term
print << new(list(term4,term2,term4)) << newline; -- bad leading term
print << new(list(term1,term4,term4)) << newline; -- bad leading term
print << new(list(term4,term4,term4)) << newline; -- bad leading term
print << new(list())@Polynomial << newline; -- true zero polynomial

#endif -- TEST

21.6 : Operations in the Type ``Polynomial''

21.6.1 : Listing

#include "aldor"

Term: BasicType with {
        new: (SingleInteger, Character) -> %;
        dispose!: % -> ();
        <<: (TextWriter, %) -> TextWriter;
        coef: % -> SingleInteger;
        var:  % -> Character;
        zero?: % -> Boolean;
        positive?: % -> Boolean;
        negative?: % -> Boolean;
        -: % -> %;
        -:(%,%) -> %;
        +:(%,%) -> %;
}
== add {
        Rep ==> Record(coef: SingleInteger, var: Character);
        import from Rep;

        new(number: SingleInteger, variable: Character): % == 
                per [number, variable];

        dispose!(ignore: %):() == {}

        (stream: TextWriter) << (term: %): TextWriter == 
                if rep(term).coef = 1 then
                         stream << rep(term).var
                else {
                         stream << rep(term).coef;
                         stream << "*" << rep(term).var
                }

        coef(term: %): SingleInteger == rep(term).coef;

        var(term: %): Character == rep(term).var;

        (term1: %) = (term2: %): Boolean == {
                coef term1 ~= coef term2  => false;
                var term1  ~= var term2   => false;
                true
        }

        sample: % == per [0, char "x"];

        zero?(term: %): Boolean      == coef(term) = 0;

        positive?(term: %): Boolean == coef(term) > 0;

        negative?(term: %): Boolean == coef(term) < 0;

        -(term: %): % == per [-coef(term), var term];

        (term1: %) - (term2: %): % == {
                var term1 ~= var term2 => 
                        error "Term: Variables do not match";
                per [coef term1 - coef term2, var term1]
        }

        (term1): % + (term2: %): % == {
                var term1 ~= var term2 => 
                        error "Term: Variables do not match";
                per [coef term1 + coef term2, var term1]
        }
}

Polynomial: with {
        new: List(Term) -> %;
        dispose!: % -> ();
        <<: (TextWriter, %) -> TextWriter;
        leadingMonomial: % -> Term;
        apply: (%, SingleInteger) -> Term;
        degree: % -> SingleInteger;
        0: %;
        zero?: % -> Boolean;
        +: (%,%) -> %;
        -: (%,%) -> %;
 }
== add {
        import from List Term;
        import from SingleInteger;
        Rep ==> Array Term;
        import from Rep;

        new(terms: List Term): % == {
                size: SingleInteger := #terms;
                result: Rep := new(size, sample@Term);

                for i in 1..size repeat
                        result.i := terms.i;

                per(result)
                }

        dispose!(ignore: %):() == {}  -- undefined

        prefix(term: Term): String == 
                if negative? term then " - " else " + ";

        abs(term: Term): Term == 
                if negative? term then -term else term;

        (stream: TextWriter) << (poly: %): TextWriter == {
                zero? poly => stream << 0@%;

                size: SingleInteger := #(rep(poly));

                sign: String:=
                        if negative? (poly.1) then " - " else "";

                for i in 1..(size - 2) repeat
                        if not zero?(poly.i) then {
                                stream << sign << abs(poly.i);
                                stream << "^" << (size - i);
                                sign := prefix(poly.(i+1))
                        }
                if not zero?(poly.(size-1)) then {
                        stream << sign << abs(poly.(size-1));
                        sign := prefix(poly.size)
                }
                if not zero?(poly.size) then 
                        stream << sign << abs(coef(poly.size));
                stream
                }

        leadingMonomial(poly: %): Term == 
                rep(poly).(#(rep(poly)));

        apply(poly: %, exponent: SingleInteger): Term == 
                rep(poly).exponent;

        degree(poly: %): SingleInteger == 
                #(rep(poly));

        0: % == new(list())@Polynomial;

        zero?(poly: %): Boolean == 
              #(rep(poly)) = 0;

        (poly1: %) + (poly2: %): % == {
                zero? poly1 => poly2;
                zero? poly2 => poly1;

                if (l1: SingleInteger := #(rep(poly1)))
		    < (l2: SingleInteger := #(rep(poly2))) then {

                        result: Rep := new(l2, sample@Term);
			d: SingleInteger := l2 - l1;

                        for i in 1..d repeat 
                                result.i := poly2.i;
                        for i in (d + 1)..l2 repeat 
                                result.i := poly1.(i - d) + poly2.i
                }
		else {

                        result: Rep := new(l1, sample@Term);
			d: SingleInteger := l1 - l2;
                        for i in 1..d repeat 
                                result.i := poly1.i;
                        for i in (d + 1)..l1 repeat 
                                result.i:=poly2.(i - d) + poly1.i
                }

                per result
        }

        (poly1: %) - (poly2: %): % == {
                zero? poly1 => poly2;
                zero? poly2 => poly1;

                if (l1: SingleInteger := #(rep(poly1)))
		    < (l2: SingleInteger := #(rep(poly2))) then {

                        result: Rep := new(l2, sample@Term);
			d: SingleInteger := l2 - l1;

                        for i in 1..d repeat 
                                result.i := - poly2.i;
                        for i in (d + 1)..l2 repeat 
                                result.i:=poly1.(i - d) - poly2.i
                }
		else {

                        result: Rep := new(l1, sample@Term);
			d: SingleInteger := l1 - l2;
                        for i in 1..d repeat 
                                result.i :=  poly1.i;
                        for i in (d + 1)..l1 repeat 
                                result.i:=poly2.(i - d) - poly1.i
                }

                per result
        }
 }

21.7 : Parameterized types

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.