Memory Regions à la carte

In the previous post we saw how to implement checked exceptions using free monads. The crucial idea was that, so long as the underlying monad was written using the "à la carte" style, we could add exceptions in such a way that

1. Programms would only compile if all exceptions were caught
2. We could program exactly as we would in the underlying (free) monad
3. Type inference was sufficient such that we did not require any type signatures
4. Client code only required language extensions to write functions with uncaught exceptions

Related to checked exceptions is another kind of fine grained effect control: memory regions. The basic idea is to allow blocks of mutable memory to be accessed in such a way that the type system ensures external purity. This is already achievable in Haskell using the ST monad. But, ST has some clunky-ness. In particular ST does not compose well with other monads.

An alternative to the ST monad is the ST monad transformer. There are problems with the ST transformer though. The one we fix is that it is not well suited for code that involves multiple memory regions. The second problem is that the ST transformer does not play nice with all monads. I strongly suspect this second problem still exists with the code presented here. In fact, our implementation uses STMonadTrans internally, and I am not convinced it can be implemented in terms of ST alone. More about this at the end.

As much as possible we would like to reuse the machinery built for checked exceptions. Lets get started.
Nothing that interesting in the extensions and the API we expose is again very simple With the imports out of the way the first thing we need to do is to define a datatype to express the operations we want our monad to be able to perform. There are three essential operations involving references, so we implement all three of them as a single functor. The one complexity is that reference are quantified over a type, so our data constructors need to be existentially quantified. We this use a GADT. The meat of our implementation is a function that converts a region into a ST monad transformer. We can easily implement this using the removeStep function from the last post Now, we define the public API. The first thing is a type for references in a region The big problem implementing memory regions by stacking ST transformers on top of each other, is that we have no way of knowing which of the various STs is intended when we use newSTRef. We solve this by adding "keys" associated with each region now, when a user wants to use a new region, they will define a function taking a key and returning an appropriate action the remainder of the API is trivial

What can we do with this? Well, lets test it out running it produces the expected results.

*Main> run $ region $ testRegion1
"in region"

we can do some more interesting things which produces the expected

*Main> run $ region $ testRegion2
"set in region 2"

we can even combine regions and exceptions

*Main> run $ region $ testRegion3
"set in region 2 before exception was thrown"

Fine grained effect control. And it didn't cost too much either. Of course, the STMonadTrans library provides support for arrays, but those can easily be added by amending the definition of RG to have more constructors.

Now, we haven't solved the second problem with STMonadTrans, namely, that we can have effects happen unexpected number of times if we are careful about it. This is obvious, since we can define a simple monad transformer as a free monad: and an algebra for running it supporting functions such as now, consider the following function which has no control flow operators the problem is that if we run it

*Main> runM $ region $ unexpected
[1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,231,253,276,300,325,351,378,406,435,465]

we see that combining mutation with a monad that represent multiple answers produces interesting results. The documentation for STMonadTrans warns that it might break referential transparency--I'm not sure that I understand why this is (how is this different than a StateT over a list?) but, this warning is enough for me to not be willing to advocate the use of these free regions just yet.