# Dependent types

It’s time to implement polynomials in D. It’s important to realise that we aren’t just going to implement polynomials over ZZ, but over an arbitrary ring, including possibly another polynomial ring. For example $\mathbb{Z}[x][y]$ is the ring of polynomials in $y$ with coefficients in $\mathbb{Z}[x]$, etc.

There are two pieces of information which the type for a polynomial ring is going to need to contain. The first is the base ring, i.e. the ring in which the coefficients live, and the variable itself.

The latter is especially important. Imagine you have the polynomial $f = x + 1$ as an element of $S = \mathbb{Z}[x][y]$. Now suppose you have to print $f$. How will you do that, considering it apparently contains no information about $y$ at all? Obviously not the value $x + 1$, but the type $S$ needs to contain this information!

Amazingly, D allows us to do precisely this using its dependent types. Types can be parameterised by other types and also by values. We need to do both; our polynomials will depend on the type of the base ring and on the value of the variable string, e.g. “x”.

# The polynomial class

Here is how we define a new class for our polynomials which depends on another type T and on a string X representing the variable:

class poly(T, string X)
{
T[] coeff;
}


The only actual data in our poly objects will be a D array of coefficients of type T.

# Constructors

At first it is convenient to introduce a constructor which takes no arguments and simply returns a polynomial object with no entries in its coefficient array and also constructors which accept an array of coefficients. For example, we’d like to be able to write

auto P = poly!(ZZ, "x")([1, 2, 3])


to create the polynomial $3x^2 + 2x + 1$ with coefficients coerced into ZZ.

My first attempt at creating the relevant constructors was as follows:

class poly(T, string X)
{
T[] coeff;

this() {} /* Causes a conflict!! */
this(S)(S[] c) { coeff = to!(T[])(c); }
}


The “to!” template in D is a “one stop shop” for converting between types, defined in the standard library module std.conv.

If we pass an array of any type S[] to our constructor, “to!” will convert it to an array of type T[]. (The (S) immediately following “this” is a type parameter. It means that S can be any type in what follows.)

Unfortunately, the D compiler complains about the above immediately. It claims the first constructor conflicts with the second, which is news to me. I had no idea that void was an array type! I tried this using multiple D compilers (gdc, dmd and ldc), so presumably it is meant to be this way.

One way to avoid the conflict is as follows:

class poly(T, string X)
{
T[] coeff;

this()() {}
this(S)(S[] c) { coeff = to!(T[])(c); }
}


But there’s a further problem. What if we pass an empty array [] (whose type is void[] in D)? For reasons beyond my comprehension, the D compiler barfs on this. So we have to add a case to detect it.

There is a very interesting way that D provides to deal with such cases. It has a “static if” directive, which works like an ordinary “if” statement, but at compile time. Here is how we can use it:

class poly(T, string X)
{
T[] coeff;

this()() {}
this(S)(S c)
{
static if (is(S == void[])) {}
else coeff = to!(T[])(c);
}
}


# Constructing polynomials from integers

We shall also need to be able to create polynomials from ints and ZZ’s. This will be required by our coercion code which is defined later. To do this we shall need to be able to distinguish between the cases where S is an array type or not.

We can do this using another interesting feature of D. The “is” function can check equality of two types or that a type is syntactically correct. We use it as follows:

class poly(T, string X)
{
T[] coeff;

this()() {}
this(S)(S c)
{
static if (is(S == void[])) {}
else static if (is(typeof(c[0])))
coeff = to!(T[])(c);
else { if (c != 0) coeff = [T(c)]; }
}
}


If c is not actually an array, it is not meaningful to take the type of c[0] and so the condition on the second “static if” will evaluate to false. Instead, we simply coerce “c” to type T and make an array containing just that value (that is if the value of “c” is not zero, otherwise we want the coefficient array to have no entries).

We don’t quite have a recursive polynomial class yet. After all, we’ve not overloaded opCall for the class or defined any of the other methods that we have for bignums.

Next Post ›››