Monday 17 August 2009

Finite fields, part 1

Okay, so you could think of this as the beginning of chapter two of the imaginary book that I'm writing in this blog. Chapter one was about graphs, groups and symmetry. In chapter two I want to talk about some other highly symmetric combinatorial objects: finite geometries and (probably) designs. But first, I need to talk about finite fields.

A field is roughly a set where you can add, subtract, multiply and divide. You're probably familiar with the following fields:
  • Q, the rational numbers
  • R, the real numbers
  • C, the complex numbers
And also with the following non-fields:
  • N, the natural numbers. Not a field, because it doesn't contain additive inverses (the negative numbers), so you can't always subtract.
  • Z, the integers. Not a field, because it doesn't contain multiplicative inverses, so you can't always divide.
I can't resist mentioning a little curiosity. To a number theorist / discrete mathematician like myself, the most interesting of the above are Q and Z. I like to think that this is why they were given the most interesting letters. Indeed, the interestingness of the mathematical objects appears to be correlated with the Scrabble value of the letters: in Scrabble, Q and Z are worth 10, indicating highly interesting; R and N are worth 1, indicating a bit boring; C is worth 3 - moderately interesting. Going further, H, the quaternions, is worth 4 - slightly more interesting than C. However, O, the octonions, is only worth 1, which looks like an anomaly.

Anyway, back to fields. Before we go any further, here's the HaskellForMaths version of Q, the rationals:
import Data.Ratio

newtype Q = Q Rational deriving (Eq,Ord,Num,Fractional)

instance Show Q where
show (Q x) | b == 1 = show a
| otherwise = show a ++ "/" ++ show b
where a = numerator x
b = denominator x
Silly, I know, but I just got a bit annoyed with those percentage signs all over the place when using Haskell's built-in rationals.

Anyway, in addition to the fields Q, R, and C, there are many other types of field. The ones I want to look at here are the finite fields of prime order. These are the fields you get if you do arithmetic modulo p, where p is a prime. For each different prime p, we have a field Fp, consisting of the set {0,1, ... p-1}, with arithmetic performed modulo p. For example, in the field F5, we have 3*3 = 4; while in the field F7, we have 3*3 = 2.

Okay, so how to represent these fields in Haskell?

Well, in an earlier version of the HaskellForMaths code, I tried this:

data Fp = F Integer Integer

The idea is that the first integer is p, the prime we are working over, and the second is the value. For example, F 5 3 would represent the value 3 in the field F5.

Next we either derive or define instances of Eq, Ord, Show, Num, Fractional. The Num instance looks something like this:

instance Num Fp where
F p x + F q y | p == q = F p $ (x+y) `mod` p
F p x * F q y | p == q = F p $ (x*y) `mod` p
fromInteger _ = error "Fp.fromInteger: not well defined"


The drawbacks of this approach are probably pretty obvious:
  • Whenever I have two Fp values, F p x and F q y, I first have to check that p = q. This is a run-time check of something that would be better handled at compile time by the type system
  • When defining numerical types in Haskell, the fromInteger function gives us implicit type conversion from integers to our type, so that we can just write code like 3 * 3, and have the type system convert them into the correct type. However, in this case, we can't give a sensible definition of fromInteger, because we don't know which prime p the user wants to work over. This means that everything is going to have to be written longhand as F 5 3 * F 5 3, and so on.
  • It feels like a waste of memory to be carrying that first Integer p around all the time, when if I'm using the code correctly, all the ps in a given calculation will be the same.
For these reasons, I decided to try another approach. The aim is to make F2, F3, F5, etc be different types, so that adding 3 :: F5 to 3 :: F7 is a type error, which can be spotted at compile time, rather than a runtime error.

It's fairly simple really.

First, define a whole bunch of phantom types representing the primes:

data T2
data T3
data T5
...

Now define a mechanism for retrieving the values from the types:
class IntegerAsType a where
value :: a -> Integer

instance IntegerAsType T2 where value _ = 2
instance IntegerAsType T3 where value _ = 3
instance IntegerAsType T5 where value _ = 5
...

This enables us to do the following:

> value (undefined :: T2)
2
> value (undefined :: T3)
3

Now, we use the phantom types to parameterise a finite field data type:

newtype Fp n = Fp Integer

Here, Fp (the one on the left of the equals sign) is a type constructor which takes a type parameter n. This type parameter will be one of the phantom types we just defined. For example:

type F2 = Fp T2
type F3 = Fp T3
type F5 = Fp T5

As before, we need to derive or define Eq, Ord, Show, Num, and Fractional instances. The Num instance looks like this:

instance IntegerAsType n => Num (Fp n) where
Fp x + Fp y = Fp $ (x+y) `mod` p where p = value (undefined :: n)
Fp x * Fp y = Fp $ (x*y) `mod` p where p = value (undefined :: n)
fromInteger m = Fp $ m `mod` p where p = value (undefined :: n)
...

This is all fairly standard phantom type trickery, but it now enables us to do things like the following:

> :load Math.Algebra.Field.Base
> 3*3 :: F5
4
> 3*3 :: F7
2
> (3 :: F5) * (3 :: F7)
#type error#

We still have to tell Haskell which prime p we're working over, but now we do it via a type annotation, rather than an argument to the constructor. This means that Haskell can catch errors where we mix values from different fields at compile time, rather than run time.

The module Math.Algebra.Field.Base provides types for the finite fields F2, F3, F5, ..., F97. The module also provides functions to list the elements of each field:

f2 = map fromInteger [0..1] :: [F2]
f3 = map fromInteger [0..2] :: [F3]
f5 = map fromInteger [0..4] :: [F5]
...

And that's about it.

However, we must recognise, in all honesty, that there are also drawbacks to this implementation of the fields Fp.

First, whenever we want to work over a new prime p, we have to define a new type. For example, if we want to work over F101, we are going to have to define a new type for it.

(For the avoidance of doubt: No, type level Peano arithmetic is not what I'm after.)

Second, I can't decide at run time what field to work over. For certain applications it would be very useful to choose my p at run time. I could do that with the first implementation, but I can't do it with the second.

What I really want then, is for Fp and Fq to be different types when p /= q, but to be able to decide at run-time which p to work over. For example, I might have calculated the p I want to work over as the result of a previous calculation. This is impossible in Haskell.

However, there is a technology called "dependent types", in which what I want is possible. Dependent types means roughly that types can depend upon values. So in a Haskell-like language that supported dependent types, I might be able to write code like the following (not valid Haskell):

> 3 * 3 :: F 5
4

Here, the value 5 (not the type T5) is being passed as a type parameter to the type constructor F.

For a while, I thought this was the holy grail. I even considered defecting from Haskell. I did look into languages that support dependent types, such as Coq. However, I concluded that, sadly, this is not the answer. The problem is that - I think - if you have types dependent on values, then you lose the distinction between compile time and run time, which means - I think - that you can't compile the language any more.

Or does someone else know better?

8 comments:

  1. Take a look at the prepose pdf, it has a section on modular arithmatic very similar to what you have done here.

    http://hackage.haskell.org/package/reflection-0.2.0

    ReplyDelete
  2. I believe that Oleg's method uses MPTCs (for wandering audience: Multi-Parameter Type Classes - functions that pin down the types of its argumnts or result based on other arguments its already been given). You may want to give his site, http://okmij.org/ftp/ a try.

    ReplyDelete
  3. I'm not an expert on dependent types, but your intuition is at least somewhat wrong. Dependently typed languages can be compiled, and types can be checked at compile time.

    The downside is that you lose type inference, and that users will frequently need to provide additional proofs (beyond the lambda terms) if types are to be checked at compile time.

    However, with things like Coq, you can add proof tactics and decision procedures as part of the library to reduce or eliminate this burden on the user.

    The trickiest thing about type systems is to balance what can be expressed with ease of use. Hindley-Milner style type systems and many of its extensions offer one particularly sweet spot in this spectrum.

    ReplyDelete
  4. I have a somewhat extensive number theory library, nothing special, and I've seen several people publish libraries not too dissimilar from my own. So I have given some thought about how to structure a library such as this... however at the time I gave up on doing much with the type system, in the interest of creating something usable more quickly.

    You have covered two approaches I've considered. If all you care about is finite fields, the latter approach might not be too unreasonable, however I've thought more about how to express modular rings.

    For the latter case, I've thought about implementing binary numbers in the type system, and use Template Haskell to be able to express types in standard base-10 notation. This should be fairly straightforward, in principle, fo field operations, so long as you can live with the inverse operation being partial.

    The tricky thing that I anticipate would be implementing type-safe modulus and the chinese remainder theorem. I mean, mod : Z_a -> Z_b is well-defined iff b is a divisor of a, and crt : Z_a * Z_b -> Z_(a*b) needs a and b to be relatively prime.

    So, if all this was coded up and was finally working, I don't really know how usable it would all be. It would be cute, but could you ultimately compute on moduli that weren't known in advance, for example?

    Again, the challenge in type systems is more of balancing ease of use with expressivity. ;-)

    ReplyDelete
  5. The reflection package is probably the most standard way, but you can get 90% there with much less type-hackery, I think. Just encode Fp :: F (Integer -> Integer) -- i.e. everything that was previously a value in a field over a prime now becomes a function *from* a prime to a value in that prime's field. So everything is coded over an arbitrary prime, to be determined later (i.e. passed in once), and you can't mix values from different fields accidentally. I'm not sure this approach has been taken before, but it seems like an elegant win.

    ReplyDelete
  6. Hi all,

    Many thanks for the pointers. It sounds like it is possible to get an approximation to what I want in Haskell, but that it involves somewhat more heavyweight type hackery than I'm really comfortable with.

    (And for real dependent types in Coq etc, giving up type inference feels like too high a price.)

    For the moment, the F2, F3, F5 etc types that I defined in the post are sufficient for constructing the combinatorial objects I'm interested in, so I'll leave further investigation of this area to another day.

    ReplyDelete
  7. @David:

    I think the reflection library is a much easier path to go than type level integers.

    @Sterling:

    Actually the example of working over a finite field was the original motivating example for the reflection library!

    In the older version of my monoids library (0.1.36) there was a Ring for modular arithmetic that used reflection.

    I have not updated it since I factored rings and so forth out of the monoids and rewrote the reflection to carry the reflected term-as-type via a phantom type parameter on a newtype.

    ReplyDelete
  8. Hi. I'm pretty new to Haskell programming so all this talk about phantom and dependent types blew me away but it all seems very interested. It just makes me want to delve deeper and deeper into Haskell so thanks alot for that.

    BTW. I checked out the link that BlackMeph provided http://okmij.org/ftp/ and came across this paper http://okmij.org/ftp/papers/number-parametized-types.pdf by Oleg Kiselyov.

    If Coq can do it, Haskell can definitely do it so I'm not surprised by the existence of this paper.

    ReplyDelete

Followers