4.23. StableName

A haskell object can be given a stable name by calling makeStableName on it. Stable names solve the following problem: suppose you want to build a hash table with Haskell objects as keys, but you want to use pointer equality for comparison; maybe because the keys are large and hashing would be slow, or perhaps because the keys are infinite in size. We can't build a hash table using the address of the object as the key, because objects get moved around by the garbage collector, meaning a re-hash would be necessary after every garbage collection.

Enter stable names. A stable name is an abstract entity that supports equality and hashing, with the following interface:

data StableName a -- abstract, instance Eq.
makeStableName :: a -> IO (StableName a)
hashStableName :: StableName a -> Int

All these operations run in constant time.

Stable names have the following properties:

  1. If sn1 :: StablePtr and sn2 :: StablePtr and sn1 == sn2 then sn1 and sn2 are either the same stable name, or they were created by calls to makeStableName on the same object.

  2. The reverse is not necessarily true: if two stable names are not equal, it doesn't mean that they don't refer to the same Haskell object (although they probably don't).

  3. There is no freeStableName operation. Stable names are reclaimed by the runtime system when they are no longer needed.

  4. There is no deRefStableName operation. You can't get back from a stable name to the original Haskell object. The reason for this is that the existence of a stable name for an object doesn't guarantee the existence of the object itself; it can still be garbage collected.

  5. There is a hashStableName operation, which converts a stable name to an Int. The Int returned is not necessarily unique (that is, it doesn't satisfy property (1) above), but it can be used for building hash tables of stable names.

Properties (1) and (2) are similar to stable pointers, but the key differences are that you can't get back to the original object from a stable name, and you can convert one to an Int for hashing.