Common Lisp CAS

History

During my master thesis, I had written some Common Lisp for continued fraction expansions. It represented Laurent series using lazy evaluation and worked reasonable well. However, the code structure was not very elegant and it worked only with the Common Lisp number type for the coefficients. So essentially the base field was restricted to the rational numbers.

As far as I remember, Prof. Masser asked me if I could do the same type of calculations over finite fields. I started to reorganise the code and started to use generic functions for the arithmetical operations, which allowed me to add support for modular arithmetic and perform some finite field calculations.

During the first two years of my PhD, I continued to extend the mathematical capabilities of the system, and collected and unified the Lisp code I had already written in the past for various projects. For example, when I was following a cryptography lecture in Basel, I had written a bit of code for primality tests, factorisation of integers.

I also had several versions of linear algebra code, which I unified and tried to use for an implementation of the Berlekamp algorithm for factorising polynomials. Unfortunately, that code is probably still rather bug ridden.

The project got stuck when I wanted to implement multivariate polynomials and algebraic extensions (to complete the finite field support, and to add number fields), maybe because I did not have a proper coercion model and ran into trouble.

At that time it was also clear to me that the key feature, the lazy Laurent series, was not really necessary for the calculations touching my research. Support for number fields was much more important to me at the time, so I switched to systems which already supported that.

Components

The Lisp Code is split into 4 components. Apart from my utility library ol-utils, all dependencies are available on Quicklisp.

  • math-utils contains all the general purpose mathematical data structures and algorithms.
  • continued-fractions has various code for computing (polynomial) continued fraction expansions. There is a general implementation for lazy Laurent series, but also specialised code only for hyperelliptic continued fractions (essentially square roots of polynomials).
  • math-formatter is a library for converting mathematical expressions from an in memory representation to something nicely readable. It implements output to a text terminal or in LaTeX format, and is also used by the math-interactor interface.
  • math-interactor is a simple CLIM application. It provides a graphical interface to math-utils, and is currently focused on working with hyperelliptic continued fractions.

Capabilities

There are no major algorithms implemented (I did not need them), the focus is very much on the data structures.

  • Generic mathematical operations (for example +, -, *, /)
  • Modular arithmetic
  • Polynomials, and rational functions via fractions
  • Lazy Laurent series
  • Lazy infinite sequences
  • p-adic valuations and Gauss norms
  • Primality tests and factorisation for integers
  • Vectors and matrices, LU decomposition
  • Elliptic curves in Weierstrass form
  • Permutations

These features can in principle be composed, for example you can have Laurent series of rational functions with coefficients modulo some prime. Sometimes one runs into trouble with coercion, unfortunately.

There is also an implementation of the Berlekamp algorithm for factoring polynomials, however it requires further work and testing.

About CLIM

The Common Lisp Interface Manager allows to build rich graphical applications. It is rather old and follows a different philosophy from modern UI toolkits. However, it remains functional and powerful, and implementing the rendering of mathematical expressions was surprisingly easy.

It allows to naturally attach a mathematical object to its graphical expression and distinguish its type. This is in some sense richer, but maybe also less flexible than mere copy-paste selection. The command based interface also allows for a command-line like user experience.

Figuring out how to use CLIM requires some experimentation. The McCLIM project also has some user documentation.