Quoting from "The Glasgow Haskell Copiler User's Guide, Version 6.2", section 7.2, "GHC is built on a raft of primitive data types and operations". Here, I walk the reader through the steps of adding a particular new primitive operation to GHC Haskell, one that calls the GMP function `mpz_powm`. This is for non-.NET platforms, since .NET uses `BigInteger` rather than GMP.

I should warn the reader that I, in writing this piece, am a rank amateur in many of the involved issues, including working with the GHC compiler, darcs, and trac. Hence, I will often digress in various directions, reflecting that this is a learning experience for me.

## Why do I want to add new primitive operations to GHC Haskell?

My basic interest is computing with rather large integers. This means integers with hundreds or even thousands of decimal digits. Haskell's `Integer` type fits this purpose perfectly. However, I am ultimately concerned about performance and some of the more complex algorithms for operating on large integers require the use of operations, such as shifting, that cannot be implemented efficiently in standard Haskell.

The `Integer` operations of GHC Haskell for non-.Net platforms use GMP. And, actually, GMP includes some of the functions on large integers that I am looking for. So, adding new primitive operations that call these GMP functions solves my problem.

## Why do I not use FFI?

Quite simply because I have so far been unable to figure out how to pass `Integer` operands efficiently between Haskell and C. I am still, however, in the market for a solution of this nature.

## Why do I need `mpz_powm`?

The GMP `mpz_powm` function computes "(BASE raised to EXP) modulo MOD" for some integers BASE, EXP, and MOD. So this is really not the sort of low-level function (like shifting) that I am looking for. But it provides a nice example for the present text. And also allows me to compare my Haskell implementation of the same function with the GMP implementation and thereby gain some general insight into the overhead incurred when using Haskell rather than GMP called directly from C.

## Basics: Versions of GHC

The GHC that I am working on is ghc-6.4.1-src.tar.bz2 that I downloaded 2006-March-01. I also found it valuable to consult the version that I downloaded from the darcs respository on 2006-March-21.

## Steps required to add a new primop

The steps are actually described in "ghc/compiler/prelude/primops.txt.pp" of the 2006-March-21 darcs version of GHC as follows:

```-- To add a new primop, you currently need to update the following files:
--
--      - this file (ghc/compiler/prelude/primops.txt.pp), which includes
--        the type of the primop, and various other properties (its
--        strictness attributes, whether it is defined as a macro
--        or as out-of-line code, etc.)
--
--      - if the primop is inline (i.e. a macro), then:
--              ghc/compiler/AbsCUtils.lhs (dscCOpStmt)
--                defines the translation of the primop into simpler
--                abstract C operations.
--
--      - or, for an out-of-line primop:
--              ghc/includes/StgMiscClosures.h (just add the declaration)
--              ghc/rts/PrimOps.cmm     (define it here)
--              ghc/rts/Linker.c       (declare the symbol for GHCi)
--
--      - the User's Guide
```

The part about `ghc/compiler/AbsCUtils.lhs` is no longer valid, at least I cannot figure out the details related to this. But is any case, the present piece is about adding `Integer` primitive operations and they are not inline (as we will see in a minute), so I don't care right now.

The part about the User's Guide is also not accurate: In "The Glasgow Haskell Copiler User's Guide, Version 6.2", section 7.2, I read that

There used to be long section about [the primitives] here in the User Guide, but it became out of date and wrong information is worse than none.

So that's a relief.

## Digression: How to refer to things?

The basic mechanism is, of course, the hypertext link. Unfortunately, I cannot seem to find a way of referring to things that won't easily break. It is comforting to know that others appear to have the same problem: I noted the other day in passing a letter from Simon Marlow (I believe it was) that explained how he had now eliminated a level (ghc) of the directory tree. As a result, several links in DebuggingGhcCrashes are now broken.

(And please forgive me here: Although an amateur in many respects, I am a professional programmer and I have had years of experience dealing with multiple versions of things, relations that shouldn't break, etc. So I know that the solution is not easy. But I need some guidance in this case: Should I just quietly go and correct these few links that are wrong? The problem is that I know I could find dozens, if not hundreds, of broken links, so I could spend the rest of my life doing this sort of thing.)

## `ghc/compiler/prelude/primops.txt.pp` changes

This file "should first be preprocessed" and is then "processed by the utility program genprimopcode to produce a number of include files within the compiler"

In this file we have, for example, the following:

```  primop   IntegerQuotOp   "quotInteger#" GenPrimOp
Int# -> ByteArr# -> Int# -> ByteArr# -> (# Int#, ByteArr# #)
{Rounds towards zero.}
with out_of_line = True
```

which is the basis of the `quot::Integer->Integer->Integer` function. A Haskell `Integer` "is represented as a pair consisting of an `Int#` representing the number of 'limbs' in use and the sign, and a `ByteArr#` containing the 'limbs' themselves."

Mimicking `IntegerQuotOp`, we add:

```  primop   IntegerPowerModOp   "powerModInteger#" GenPrimOp
Int# -> ByteArr# -> Int# -> ByteArr# -> Int# -> ByteArr# -> (# Int#, ByteArr# #)
{Base raised to a power modulo a modulus.}
with out_of_line = True
```

for our power operation: It needs three `Integer` operands and returns one `Integer` result, hence the type has an `Int#` and a `ByteArr#` for each.

## `ghc/includes/StgMiscClosures.h` changes

In this file, we should just "add the declaration". Hence, we add the line

```   RTS_FUN(powerModIntegerzh_fast);
```

somewhere suitable in the (alphabetically sorted) list of other symbols. The name used here (`powerModIntegerzh_fast`) is what is called the Z-encoding of the primitive operation `powerModInteger#`. A nice description of Z-encoding can be found in DebuggingGhcCrashes.

## `ghc/rts/PrimOps.cmm` changes

This is where the code that actually implements (out of line) primitive operations go. In this file we find, for example:

```  #define GMP_TAKE2_RET1(name,mp_fun)                     \
name                                                    \
{                                                       \
CInt s1, s2;                                          \
W_ d1, d2;                                            \
\
/* call doYouWantToGC() */                            \
MAYBE_GC(R2_PTR & R4_PTR, name);                      \
\
s1 = W_TO_INT(R1);                                    \
d1 = R2;                                              \
s2 = W_TO_INT(R3);                                    \
d2 = R4;                                              \
\
MP_INT__mp_alloc(mp_tmp1) = W_TO_INT(StgArrWords_words(d1));  \
MP_INT__mp_size(mp_tmp1)  = (s1);                     \
MP_INT__mp_d(mp_tmp1)     = BYTE_ARR_CTS(d1);         \
MP_INT__mp_alloc(mp_tmp2) = W_TO_INT(StgArrWords_words(d2));  \
MP_INT__mp_size(mp_tmp2)  = (s2);                     \
MP_INT__mp_d(mp_tmp2)     = BYTE_ARR_CTS(d2);         \
\
foreign "C" mpz_init(result1);                        \
\
/* Perform the operation */                           \
foreign "C" mp_fun(result1,mp_tmp1,mp_tmp2);          \
\
RET_NP(TO_W_(MP_INT__mp_size(result1)),               \
MP_INT__mp_d(result1) - SIZEOF_StgArrWords);   \
}
```

defining a macro which is called, for example, like this:

```  GMP_TAKE2_RET1(quotIntegerzh_fast,     mpz_tdiv_q)
```

to provide an implementation of the `quotInteger#` primitive operation. So we go ahead and define

```  #define GMP_TAKE3_RET1(name,mp_fun)                             \
name                                                            \
{                                                               \
CInt s1, s2, s3;                                              \
W_ d1, d2, d3;                                                \
\
/* call doYouWantToGC() */                                    \
MAYBE_GC(R2_PTR & R4_PTR & R6_PTR, name);                     \
\
s1 = W_TO_INT(R1);                                            \
d1 = R2;                                                      \
s2 = W_TO_INT(R3);                                            \
d2 = R4;                                                      \
s3 = W_TO_INT(R5);                                            \
d3 = R6;                                                      \
\
MP_INT__mp_alloc(mp_tmp1)     = W_TO_INT(StgArrWords_words(d1));      \
MP_INT__mp_size(mp_tmp1)      = (s1);                         \
MP_INT__mp_d(mp_tmp1)         = BYTE_ARR_CTS(d1);             \
MP_INT__mp_alloc(mp_tmp2)     = W_TO_INT(StgArrWords_words(d2));      \
MP_INT__mp_size(mp_tmp2)      = (s2);                         \
MP_INT__mp_d(mp_tmp2)         = BYTE_ARR_CTS(d2);             \
MP_INT__mp_alloc(mp_tmp3)     = W_TO_INT(StgArrWords_words(d3));      \
MP_INT__mp_size(mp_tmp3)      = (s3);                         \
MP_INT__mp_d(mp_tmp3)         = BYTE_ARR_CTS(d3);             \
\
foreign "C" mpz_init(result1);                                \
\
/* Perform the operation */                                   \
foreign "C" mp_fun(result1,mp_tmp1,mp_tmp2,mp_tmp3);          \
\
RET_NP(TO_W_(MP_INT__mp_size(result1)),                       \
MP_INT__mp_d(result1) - SIZEOF_StgArrWords);           \
}
```

and a call

```  GMP_TAKE3_RET1(powerModIntegerzh_fast, mpz_powm)
```

(Actually, defining a macro for this single call may seem needless, but it is not particularly more troublesome, and leaves some reduced work ahead.)

```  section "bss" {
mp_tmp3:
bits8 [SIZEOF_MP_INT];
}
```

to cater for the (new) situation of having to deal with 3 `Integer` operands.

(Caring for efficiency, I am somewhat dismayed by the remark

```  /* ToDo: this is shockingly inefficient */
```

describing the PrimOps.cmm implementation of `Integer` primitive operations. But that will have to be dealt with later.)

## `ghc/rts/Linker.c` changes

In this file, we should just "declare the symbol for GHCi". Adding

```        SymX(powerModIntegerzh_fast)            \
```

takes care of that.

## `libraries/base/GHC/Num.lhs` changes

The internal `Integer` representation is defined here as:

```  data Integer
= S# Int#                            -- small integers
#ifndef ILX
| J# Int# ByteArray#                 -- large integers
#else
| J# Void BigInteger                 -- .NET big ints

foreign type dotnet "BigInteger" BigInteger
#endif
```

that is, for the non-.NET situation envisioned here, either a single precision integer or a GMP integer represented by a limb count and a limb pointer. The `Integer` functions defined in this file provide an interface between the primitive operations defined in terms of this internal `Integer` representation and the externally visible `Integer` operations in GHC.Num (like `quotInteger`). So, similar to

```  quotInteger :: Integer -> Integer -> Integer
quotInteger ia 0
= error "Prelude.Integral.quot{Integer}: divide by 0"
quotInteger a@(S# (-LEFTMOST_BIT#)) b = quotInteger (toBig a) b
quotInteger (S# a) (S# b) = S# (quotInt# a b)
{- Special case disabled, see remInteger above
quotInteger (S# a) (J# sb b)
| sb ==# 1#  = S# (quotInt# a (word2Int# (integer2Word# sb b)))
| sb ==# -1# = S# (quotInt# a (0# -# (word2Int# (integer2Word# sb b))))
| otherwise  = zeroInteger
-}
quotInteger ia@(S# _) ib@(J# _ _) = quotInteger (toBig ia) ib
quotInteger (J# sa a) (S# b)
= case int2Integer# b of { (# sb, b #) ->
case quotInteger# sa a sb b of (# sq, q #) -> J# sq q }
quotInteger (J# sa a) (J# sb b)
= case quotInteger# sa a sb b of (# sg, g #) -> J# sg g
```

we define

```  powerModInteger :: Integer -> Integer -> Integer -> Integer
powerModInteger a@(S# _) b c = powerModInteger (toBig a) b c
powerModInteger a b@(S# _) c = powerModInteger a (toBig b) c
powerModInteger a b c@(S# _) = powerModInteger a b (toBig c)
powerModInteger (J# sa a) (J# sb b) (J# sc c)
= case powerModInteger# sa a sb b sc c of (# sr, r #) -> ( J# sr r )
```

First: make clean! GHC doesn't correctly track changes to the `GHC.Prim`, so it won't recompile enough things if you just type `make`, so you need to `make clean` first. (strictly speaking you don't need to clean the stage 1 compiler, so if you know what you're doing you might want to try cleaning just the right bits).
Then we `make all` in the top-level directory. The error message that we get is
```GHC/Num.lhs:507:9: Not in scope: `powerModInteger#'
So dependencies are missing. I have not bothered to track down why this happens in detail. But, guided by wise persons, I simply say `make clean` in both `ghc/compiler` and `libraries/base` and that helps: The compiler builds and actually works, including the newly implemented primitive operation `powerModInteger`.