# Computer algebra

I eat my corn in rows instead of spirals, which is apparently highly correlated with thinking algebraically instead of analytically as a mathematician. So it is no surprise that when it comes to computers, I find computer algebra interesting.

There’s a certain mindset that goes with computer algebra, and it includes a desire to construct mathematical objects called rings, in a recursive manner. For example, the ordinary integers (often denoted $\mathbb{Z}$) form a ring. But then we like to construct the ring $R$ of polynomials over $\mathbb{Z}$ (denoted $ZZ[x]$ say) and maybe the ring $S$ of $n\times n$ matrices over $R$ (denoted $M_n(ZZ[x])$), and so on.

Constructing all these rings in a recursive fashion means that we need to be able to model these rings using types in a computer algebra system. It’s not enough to be able to model matrices of polynomials over the integers as multidimensional arrays of arrays of bignums. Things get even more complicated when we want to construct the ring of integers modulo $n$, or take quotients of our rings by ideals, etc. Now we really do need to do operations on the types (rings) themselves, not just the values (elements of the rings).

Therefore, as a computer algebraist, I have a list of requirements for a computer programming language. Any half decent 21st century language would have all of these features. Let’s call it the BOTCH (Bill’s Own Twenty-first Century Hacker’s) programming language test. Of course if a programming language is useful for me, it’s obviously going to be useful for everyone else in the world as well. So I hereby promulgate the following requirements for any half-way decent language:

**The BOTCH Programming Language Test**

- Must have parametric types (so we can define say the ring of polynomials over another type/ring R).
- Types must be able to contain additional information, such as the variable name for the polynomial, e.g. S = polynomial<”x”, ZZ> where ZZ is the bignum integer type and “x” is a string representing the variable name in the ring. In other words, we must have dependent types.
- Must have bignums, and these better be fast, preferably based on the gold standard GMP (GNU Multi Precision) bignum library. A sensible native Foreign Function Interface will achieve the same thing, for then we can link to GMP.
- Must have operator overloading. One does not prefer typing add(mul(pow(x, 5), 7), mul(pow(x, 4), 3), etc., to construct polynomials or to perform computations in a ring in general!
- Should be able to enter polynomials in standard algebraic notation, e.g. 5*x^2 + 3*x + 7.
- Should be able to coerce elements from one ring into another in a simple way, preferably S(3*x + 1) to coerce 3*x+1 into the ring S of polynomials in x and y with integer coefficients, say, where S is the actual name of the type.
- Everything should run at about the same speed as a hand coded recursive rings implementation written in C.
- The language should provide an interactive REPL and an option of ahead of time compilation. The REPL is essential, as mathematicians will want to use the language to experiment with mathematical objects in real time.
- The REPL should be as fast as the natively compiled code.
- All of the above should occur in the native syntax of the language itself, not as an external DSL (one does not prefer to write a parser for everything one wishes to do).

For the last point I am highly influenced by the Sage computer algebra package. The language of Sage is Python. As a user, if you want to construct and manipulate rings in Sage, you learn Python. You don’t learn some special ad hoc language invented for the task. Standard programming skills can then be employed for any task. (Of course Python is not fast enough, so Sage nails up the front end to a bunch of Cython and C libraries, amongst others.)

Naturally, any programming language which does not meet all these requirements shall be considered rubbish and not worthy of 21st century programming language status.

This blog post and those following is about my attempts to achieve all of the above using the D programming language.

**Disclaimer:** this will be the first non-trivial code I will have written in D and so it may or may not be be idiomatic D. Also I have only written a few hundreds of thousands of lines of code in other languages before, and have only looked at a few hundreds of languages over the years. So I’m obviously no expert (one is a mathematician, not a computer scientist). But hopefully I can figure out how to get something crude running.

Nimrod (http://nimrod-code.org/) fullfills most of your requirements plus it has a feature you don’t even know exists: Term rewriting macros (http://build.nimrod-code.org/docs/manual.html#term-rewriting-macros)

I was also looking for a modern language allowing me to write general desktop applications for niche market (it has to do with calculating planetary positions, transits of the planets etc,). At first tried with Haskell which has nice syntax, but coping with too much category theory to properly digest monads was a bit too much for some potential contributors of my project.

For a short time we considered (wx)Python+Cython, but then took a look at D which seems to be promising, but it’s, imho, too long in that status.

Final evaluation has brought 4 candidates for a programming language which is practical, type-safe and can spare of from fiddling with pointers and obscure bugs found so often in C(++) world.

So, the 4 candidates were: Ada, OCaml, FPC(Lazarus) and Nimrod and although I do not see at the present moment the need to se term-rewriting-macros feature, as mentioned by dom, I’ve chosen to use Nimrod which is the only language which has brought some fresh air and enthusiasm for adequate programming in 21st century.