Crypto me a tea

Vault - a persistent store for values of arbitrary types

Mutable variables vs. the type system

Having adopted the purely functional point of view on programming, I don’t like mutable variables very much.

But there is something strange about them that goes far beyond their mutability: somehow, they seem to wreak havoc to the type system. For instance, their spooky “action over a distance” allows you to decompose a function type a -> IO b into two separate entities

decompose :: (a -> IO b) -> IO (a -> IO (), IO b)
decompose f = do
    ref <- newIORef Nothing
    let argument = writeIORef ref . Just
        result   = f . fromJust =<< readIORef ref
    return $ (argument, result)

that “magically” communicate with each other. Interestingly, each part carries only half the type information of the original function.

Another, more drastic example is that polymorphic mutable variables can destroy type safety. This is what forced ML to adopt the value restriction and this is also why unsafePerformIO and IORef can be used to implement unsafeCoerce :: a -> b in Haskell.

Of course, sometimes you want to stretch the type system a bit and that’s where mutable variables are quite handy, even when their mutability is not useful.

A type-safe, persistent storage

In particular, while implementing my reactive-banana library, I have found the need for a type-safe, persistent storage. Like IORef, I want to be able to store values of any type in it, but unlike IORef, I want the storage space to behave like a persistent, first-class data structure, as appropriate for a purely functional language.

I will call this data structure a vault, because it is analogous to a bank vault, where you can access different bank boxes with different keys. In other words, a Vault is an abstract data type with the following signature

data Key a
data Vault

newKey :: IO (Key a)
empty  :: Vault
lookup :: Key a -> Vault -> Maybe a
insert :: Key a -> a -> Vault -> Vault
delete :: Key a -> Vault -> Vault

The idea is that keys obtained with the newKey functions correspond to “secure deposit boxes” in the vault. You can insert or remove items of any type by using different keys.

Solution: Dynamic Typing?

Implementing a vault in Haskell is straightforward with some form of dynamic typing, like the Typeable class:

import Data.Map as Map
import Data.Unique
import Data.Dynamic

data Vault = Map.Map Unique Dynamic 
data Key a = Unique

newKey = newUnique
empty  = Map.empty
lookup key vault   = Map.lookup key vault >>= fromDynamic
insert key x vault = Map.insert key (toDyn x) vault
delete key vault   = Map.delete key vault

Unfortunately, we now have to include the Typable constraint in the type signatures, for instance

insert :: Typable a => Key a -> a -> Vault -> Vault

But this is really bad for my library because the constraint would creep into the publicly visible API and for example prohibit me from providing a Functor instance. Some other solution is needed.

Solution: Mutable variables

That’s where the strange properties of mutable variables come in very handy.

The idea is to use a finite map as storage, but we don’t store the values themselves, we store actions of type IO (). This way, all items in the store have the same type.

type Vault = Map Unique Item
type Item  = IO ()

Of course, these IO actions must somehow contain the values. In particular, the idea is that executing an action will write the corresponding value to a temporary mutable variable. Furthermore, it is the Key who keeps track of the mutable variable

data Key a   = Key Unique (Item' a)
type Item' a = IORef (Maybe a)

In other words, storing a value works like this

insert :: Key a -> a -> Vault -> Vault
insert (Key k ref) x = Map.insert k (writeIORef ref $ Just x)

while reading a value works like this

lookup :: Key a -> Vault -> IO (Maybe a)
lookup (Key k ref) vault = case Map.lookup k vault of
    Nothing   -> return Nothing
    Just item -> do
        item                    -- write into IORef
        mx <- readIORef ref     -- read the value
        writeIORef ref Nothing  -- clear IORef
        return mx

We have to make a small concession here: the type of lookup is no longer pure. That said, it is safe to wrap this in unsafePerformIO because the function itself actually is pure. After all, we don’t want to mutate anything, we just want to play a trick on the type system.

To create a new key, we simply allocate both a new unique identifier and the temporary mutable variable.

newKey :: IO (Key a)
newKey = do
    k   <- newUnique
    ref <- newIORef Nothing
    return $ Key k ref

Voilà, that’s my implementation of a vault, i.e. a persistent store for values of arbitrary types. I have implemented a variant in my reactive-banana library and used it for great, purely functional good.

Comments