Sunday, July 1, 2012

pipes-2.1 and index-core-1.0 - Indexed types

This new release marks a major upgrade to the pipes Frame implementation that unifies the entire implementation within a single type using indexed types. The most important benefits of this are:
  • Frames are now unified into a single type
  • The newtype is gone
  • do notation can be rebound to work with monads on indexed types.
Now, Frame code is virtually indistinguishable from Pipe code. For example, the take' Frame looks like this:
take' n = do
    replicateMR_ $ do
        a <- await
        yield a
    liftU $ putStrLn "You shall not pass"
However, before I continue, I want to make good on a promise to notify readers of my blog that I made some mistakes in my previous post on bugs in conduit. I corrected some of the mistakes in the original post and in Michael's response post he explained several of his design decisions.

Indexed types

To upgrade pipes to use indexed types, I wrote a base library that provides the foundation for indexed types: index-core-1.0, which you can find here. This library is strongly based on the functional pearl "Kleisli arrows of outrageous fortune" by Conor McBride.

The other significant alternative for indexed monads was the indexed package, but I chose not to use it for several reasons.

First, Conor's approach is strictly more powerful, allowing computations that can end in multiple states while still preserving type safety. Although pipes does not make use of this facility, I preferred using a stronger framework for indexed types as a dependency to encourage others to use his approach.

Second, Conor's approach makes it MUCH easier to translate ordinary types into indexed types mechanically. The best example of this is the "indexed free monad transformer" (what a mouthful) used to implement Frame, which is the indexed equivalent to the free monad transformer used for Pipes. However, not only are the types mechanically translatable, but so is the code, which is almost indistinguishable from unindexed code.

However, I make one important deviation from Conor's approach, which is terminology. Unfortunately, Conor's paper uses the term "indexed monads" to refer to the conventional approach represented in the indexed package, and uses the term "monads on indexed types" to describe his approach, and it actually took me my third read-through of his paper before I even caught that distinction at all. As a result, I decided to use more distinctive terminology to distinguish them so I prefer to use the term "indexed monad" to refer to Conor's approach and "restricted monad" to refer to the more restrictive approach found in indexed. All the documentation in index-core follows this naming convention.

Besides providing indexed and restricted monads, index-core also provides the tools to switch between ordinary monads and restricted monads. For example, you can always upgrade an ordinary monad to a restricted monad using the u (for 'u'pgrade) function, and downgrade it again using unU. This is useful when you enable do notation for indexed monads, but you still want to also use do notation for ordinary monads:
-- Upgrading IO to work in an indexed do block
unU $ do
    str <- u getLine
    u $ putStrLn str
Alternatively, you can choose to not enable indexed do notation and instead downgrade index-preserving restricted monads to ordinary monads using the D (for 'D'owngrade) function and upgrade it again using unD:
-- Downgrading Frame to work in an ordinary do block
unD $ do
    a <- D await
    D $ yield a
However, if you took the latter approach, you would need to use the indexed monad bind directly anytime you use an operation that changes the index (such as the close operation). It's up to you which approach you prefer.

Also, index-core exports restricted monad versions of the functions found in Control.Monad, except with 'R'-suffixed names (for 'R'estricted), like foreverR and replicateMR.

Note that index-core does not yet export a restricted Applicative class. It can be done, but I just haven't gotten a chance to do it, so all the examples in this post and in the pipes tutorial don't yet use the Applicative style.


Frames are now on par with Pipes in terms of elegance and syntactic sugar. All of the complaints raised for pipes-2.0 are fixed by this upgrade. There is no two-stage monad any longer, meaning that you can do elegant things like:
strict = toList >>= fromList
... and the implementation of toList is now very succinct, exactly the way you'd expect to write it:
toList = do
    a' <- awaitF
    case a' of
        Nothing -> return []
        Just a  -> do
            as <- toList
            return (a:as)
Note that I've switched the roles of awaitF and await. This is so that Frame await is now a drop-in replacement for Pipe await and also to bring pipess in line with pipes-core, notationally, which uses await to denote the default request which does not return a Maybe. awaitF becomes the Frame equivalent to tryAwait from pipes-core.


The hierarchy has been reorganized a bit. I've moved Frames to Control.Frame because they are no longer built on top of the Pipe type. Also, now I've moved the tutorials to Control.Pipe.Tutorial and Control.Frame.Tutorial and made a lot of updates to the Frame tutorial, especially the strictness part, which now does a really good job of demonstrating how you can be selectively strict in the input.

Now that conduit is also expanding its documentation, I thought it would be a good time to choose a better module hierarchy to set as an example for other libraries. I think that a simple ".Tutorial" extension for a module's corresponding tutorial is perhaps the most flexible and straightforward way to navigate to the tutorial for a particularly module. The advantage of splitting the tutorial module from the actual API module is so that you can feel free to write a long tutorial without worrying about getting in the way of navigating the API.

The Streaming Haskell Group

Besides cleaning up the Frame implementation, there's another reason I'm switching to indexed types. Recently, Michael founded the streaming-haskell group and after a some of discussion with the other members of the Streaming Haskell group, I'm beginning to believe that the final type that we will end up agreeing on will require some form of indexed types, so this release is my effort to lay the groundwork for an indexed type ecosystem so that people will be less afraid to experiment with indexed types. With this release I hope to give people:
  • The tools to work with indexed types
  • An instructive library to consult as a reference
  • A motivating example for the practical benefits of indexed types
In a future post I will discuss in greater length why indexed types are the future of more advanced iteratee implementations, perhaps even for ones that rely on implementation hiding.

Future Directions

As many people know, I make a big deal about avoiding implementation hiding when enforcing class laws. I believe strongly in keeping the entire library correct by construction so that it is easy for other people to extend without worrying about breaking any laws. At the same time, I strive to simplify the interface the user must understand to use the library and I think this version is a big step in that direction.

I'm a big advocate for free monads and one of the big benefits of free monads is the power to choose your observation function. Historically, runPipe (or runFrame) has been the canonical observation function, but I believe people's creativity has been filtered through the lens of what they could accomplish through runPipe and they don't think of all the things they could do by writing their own observation functions. By sticking to strong guarantees I try to promote experimentation in the observation function and in the future I will write a post with some motivating examples to get people to think outside the runPipe box.

Now that I'm happier with the state of the Frame API you will soon see a library of utility functions included in upcoming minor releases so that you don't have to write your own (although, it's very easy to do so now!). Also, parsing is a major goal in the near future and a complete parsing implementation is my target for version 3.0.

As far as exceptions go, you can still have the same exception-handling power that conduit does by just layering Frame on top of ResourceT, but I choose not to do so yet because I have other ideas for how to implement it. Because advanced Frame users can in theory implement exception handling using the API I currently present, it's lower on my priority list than parsing, which is non-trivial. However, if you disagree with my priorities, feel free to let me know. I always strive to follow feedback from users.

No comments:

Post a Comment