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 `Type`

s *over* other `Type`

s. 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
`Type`

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

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;

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

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

For the first example we will construct a trivial program to determine
the sign of its argument (called the `SPMquot`

signum" 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 `Type`

s (with a capital `T`

).

`Type`

s (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 `Type`

s.
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 `String`

s,
for our purposes, is printing. This operation is called ```<<`

''.

To build a `Type`

we need to know the parts of the box (remember: `Type`

s
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" }Let's look at the parts.

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 `signum`

signum" 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 `Type`

s 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 `SingleInteger`s (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 `Type`

s.

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__

22.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 `SingleInteger`s
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
`SingleInteger`s. 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 `In order to define this function we use:`SPMquot`

signum"' that will take a thing of`SPMquot`

Type" ``SPMquot`

SingleInteger"' and return a thing of`SPMquot`

Type" ``SPMquot`

String"'.''

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 `SPMquot`

add" 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__

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:

3*x

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:

3*x*y

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 `SingleInteger`s (machine integers) as our coefficients.
Note that this will *not* allow us to write the polynomial:

(2/3)*x

as (2/3) is not a `SingleInteger`

. Thus we will need to revisit this design
decision if we need to divide polynomials.

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.

`Record`

s 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 `Type`

T (in this case,
SingleInteger and Character). `Record`

s are a useful
way of combining many different `Type`

s 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 `Term`

s, 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.

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.

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.

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 `Term`

s 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`

.

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.

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 `Record`s, `
SingleInteger`s and `Character`

s (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.

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.

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 `Term`

s are implemented as `Record`

s, 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.

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.

#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;

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.

We plan to construct our first polynomial. It will consist of `Term`

s
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*^{1000} -- 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*^{1} 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;

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:

Array(S: BasicType): ExtensibleArrayCategory S

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:

Array Term

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:

Term: with {

and we change it to read:

Term: BasicType with {

which says that `Term`

is a `BasicType`

with some additional functions.
Now when we try to compile it the compiler says:

Term is missing the following exports: =: (%, %) -> Boolean; ++ Equality test. sample: %; ++ Example element.

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.

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:

define BasicType: Category == with { =: (%, %) -> Boolean; ++ Equality test. ~=: (%, %) -> Boolean; ++ Inequality test. <<: (TextWriter, %) -> TextWriter; ++ Basic output. <<: % -> TextWriter -> TextWriter; ++ Basic output. sample: %; ++ Example element. hash: % -> SingleInteger; ++ Hashing function. default (x: %) ~= (y: %): Boolean == not (x = y); default hash(x: %): SingleInteger == (0$Machine)::SingleInteger; default (<<)(x: %)(p: TextWriter): TextWriter == p << x; }

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

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
`SingleInteger`s 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`

.

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.

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 `Term`

s, 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 `Term`

s for equality (because `Term`

is a
`BasicType`

and all `BasicType`

s have a definition for equality).

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;

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:

-: % -> %;to

`Term`

. This is unary negation. We also need predicates that tell
whether a term is positive or negative:
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.

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;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):
degree: % -> SingleInteger;

This is good enough for a first try at a `Polynomial`

type. The next example
is an implementation of this type.

#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

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.

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

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.

import from Character; import from SingleInteger; import from List Term; import from Polynomial;

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

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;

We need to check the handling of leading negative signs:

print << new(list(term5,term5,term5)) << newline; -- negative signs

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

print << new(list(term3,term2,term1)) << newline; -- 1 elision

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

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

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

print << new(list())@Polynomial << newline; -- true zero polynomial print << 0@Polynomial << newline; -- true zero polynomial

We need to check that term arithmetic is properly implemented:

print << term1 + term2 << newline; print << term1 - term2 << newline; print << term2 - term1 << newline; print << term1 - term1 << newline;

#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 } }

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:

3*x^2 + 2*x + 1 or 3.0*x^2 + 2.0*x + 1.0 or (3/5)*x^2 + (2/5)*x + (1/5)

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 `Polynomial`

s that take different kinds of `Term`

s.

The same argument applies for `Term`

s. Rather than having many
different kinds of `Term`

s, 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:

Term: BasicType with {

which has been changed to:

Term(CoefType: OrderedRing): BasicType with {

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:

Term(CoefType: BasicType): BasicType with {

but this fails, because the code that follows assumes that we can
compare the coefficient to the constant `1`

. However, things that
are `BasicType`

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

Term(CoefType: Monoid): BasicType with {

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:

Term(CoefType: OrderedRing): BasicType with {

We originally wrote the Rep so that it assumed that the
coef field of the `Record`

(which is how we store
`Term`

s internally) would be of `Type`

SingleInteger.
We must change this. The old Rep read:

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

and now it reads:

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

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:

new: (SingleInteger, Character) -> %;

which has been changed to:

new: (CoefType, Character) -> %;

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:

new(number: SingleInteger, variable: Character): % ==

and now it reads:

new(number: CoefType, variable: Character): % ==

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

coef: % -> SingleInteger; coef: % -> CoefType;

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:

coef(term: %): SingleInteger ==

and now it reads:

coef(term: %): CoefType ==

#include "aldor" Term(CoefType: OrderedRing): BasicType with { new: (CoefType, Character) -> %; dispose!: % -> (); <<: (TextWriter, %) -> TextWriter; coef: % -> CoefType; var: % -> Character; zero?: % -> Boolean; positive?: % -> Boolean; negative?: % -> Boolean; -: % -> %; -:(%,%) -> %; +:(%,%) -> %; } == add { Rep ==> Record(coef: CoefType, var: Character); import from Rep; new(number: CoefType, variable: Character): % == per [number,variable]; dispose!(ignore: %):() == {} -- undefined (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: %): CoefType == 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] } } #if TEST import from Character; import from Term SingleInteger; print << new(0$SingleInteger,char "x") << newline; import from Term Float; print << new(0$Float,char "x") << newline; #endif -- TEST

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

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