August 31, 2017

So for the past couple of days I’ve been chasing down what I thought was a space leak introduced by monadic while loops. It’s a reasonable thing to think because reinforcement learning in haskell requires nested monadic loops: one outer loop to iterate through all episodes, another nested loop to travel through all steps in each episode. A pattern which has been documented by others as potentially leaky but which, never-the-less, is still sometimes useful*.

It turns out that the culprit to this bug was not a space leak but, rather, a problem with the conflict between DeriveAnyClass and GeneralizeNewtypeDeriving. GHC will throw out compiler warnings about this interaction, and it would be wise to dig deeper into what each one does. Here’s some code which will exemplify what I’ve been dealing with:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE GeneralizeNewtypeDeriving #-}

data Config = Config { maxOinks :: Int }
deriving (Eq, Show)

newtype Oink a = Oink { kniO :: Reader Config a }
deriving (Functor, Applicative, Monad, MonadReader Config)

This code is perfectly fine, but if we make a slight modification, we introduce a bug:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE Generic #-}
{-# LANGUAGE DeriveAnyClass #-}
{-# LANGUAGE GeneralizeNewtypeDeriving #-}

data Config = Config { maxOinks :: Int }
deriving (Eq, Show, Generic ToJSON, FromJSON)

newtype Oink a = Oink { kniO :: Reader Config a }
deriving (Functor, Applicative, Monad, MonadReader Config)

At this point, GHC 8.0.2 shouts at us, telling us that it can do what we want it to do but it’ll use DeriveAnyClass before GeneralizeNewtypeDeriving, and while GeneralizeNewtypeDeriving is actually filling out code we would not write (lifting instance functions from our wrapped level to our newtype wrapper level), DeriveAnyClass is just adding an empty instance ToJSON Config line to our code. This works due to default functions in a typeclass. For instance, ToJSON’s instace looks like this:

-- From aeson:

class ToJSON a where
-- | Convert a Haskell value to a JSON-friendly intermediate type.
toJSON     :: a -> Value

default toJSON :: (Generic a, GToJSON Zero (Rep a)) => a -> Value
toJSON = genericToJSON defaultOptions

So by declaring instance ToJSON Config, we use the defaulted toJSON = genericToJSON defaultOptions code if our code can satisfy (Generic a, GToJSON Zero (Rep a)).

The bug exists with MonadReader. Now that both pragmas exist in our module, DeriveAnyClass takes precedence and we get instance MonadReader Config Oink. Unfortunately, it turns out that, while there isn’t default code, there is existing code which satisfies properties we’ve set out by default so we wind up with a problem:

-- From mtl-2.2.1

#endif
-- | Retrieves the monad environment.

-- | Executes a computation in a modified environment.
local :: (r -> r) -- ^ The function to modify the environment.
-> m a      -- ^ @Reader@ to run in the modified environment.
-> m a

-- | Retrieves a function of the current environment.
reader :: (r -> a) -- ^ The selector function to apply to the environment.
-> m a
return (f r)
Look at that! we’ve just slipped through a MINIMAL constraint! This code will recurse infinitely and crash your machine in a fiery blaze.
So what is the solution? Well there are two: if you are on GHC-8.0.x, never put both of these pragmas in the same module (possibly more sternly, never use DeriveAnyClass in a module where there is a typeclass with a MINIMALy annotated instance, but I need to doublecheck that). In GHC-8.2.x, you can now use dedriving strategies to determine how to get the instances you want. There are three types of strategies: stock, newtype, and anyclass. newtype and anyclass will work the ways detailed above while stock will generate code like instance Eq in the current way GHC generates code automatically to get your instance.
* - That being said, after a bit of reflection I’m strongly motivated to model these types of problems simply as functions working on ListT, if i am able to think about how to handle both finite and empty lists, as in the case with reinforcement learning.