This post serves three purposes, one is to plug my new, cool library, next is to talk a bit about free monad transformers and finally, to spread some knowledge and love for the Plan 9 operating system.
Algebraic effects have become my go-to tool when developing new applications and libraries and my usage of monad transformers has fallen to the wayside so it’s not a surprised that the two technologies are often presented as in some way competing ways of dealing with effects, but I don’t think this is true. Each approach lends itself to a kind of application or library. If I were to write a compiler, I’d be much more inclined to reach for mtl for example. This is because in a compiler, the transformation of data is more important than the effects themselves. When writing a networked application with custom TCP protocols, I’d reach for freer-simple because the application is more about managing effects than it is anything else.
The reason I want to present the two approaches as not actually competing is because, if algebraic effects and monad transformers did the exact same thing in two different ways, then a free monad transformer makes no sense. But I have found myself in a situation where I needed such a construction. I don’t like blog posts that present these alien constructions in a contextless void because it can be tricky to see how they can be applied to real world code and harder to realise that they should be. So I’m going to walk through the library I just wrote, to build up and understanding and contextualisation of free monad transformers.
Plan 9
To understand what the library does, it helps to start with a short history lesson. Many of us know that unix was developed at bell labs in the 70s, but development slowed after the 70s, and the last major release was in 1989. What did the unix developers do after? In the late 1980s, the same group who developed unix started work on a new operating system, Plan 9, which replaced unix as the primary platform for operating system research. Unix was built around the idea that several people would access one machine via dumb terminals, but the computing landscape had already changed significantly. Now, many computers were hosting services used by many people and the old ways were becoming cumbersome. There was nothing to help you develop network protocols, you would have to handle all of the socket logic yourself. You’d have to role your own binary parsers and handle dropped connections. In many ways, what the networked world needed was an operating system to abstract the complexity of multicomputer systems away.
The genius behind Unix was that it was based on a few simple principles which solved a huge number of problems, instead of providing an endless list of solutions to an endless list of problems. The “everything is a file” principle is a pivotal example. Plan 9 builds on this with two simple ideas:
- per-process namespaces
- simple message-oriented file system protocol
The first idea is that processes can all have a different view of the file system. So if I have two terminals open and in the first I mount a network drive, I cannot see that mount in the second terminal. Also, a single path may refer to different resources to different processes. The second point is that processes can present themselves to other processes by providing a virtual file system. This brings back what was lost as the world moved to sockets, the file system is again the primary way in people and programs access computing resources, be that hardware or software.
9P
9P is the message-oriented protocol file system protocol. First thing to say is that it’s a really simple, byte-oriented
protocol; it can easily run over TCP, or unix sockets. This means that if your program speaks 9p, then it can produce
a virtual file system that can be mounted locally or over the network. That means that if you write a client program that
reads and writes to your virtual file system, then the only difference between running it all locally, or as a distributed
system is what arguments you provide to your mount command. To give an example of how powerful this is, I’d like to
introduce you to Plan 9’s cpu command. It’s like ssh, in that it lets you open a shell or run a command on another
computer. But if you run cpu -h other-machine, and then type ls, it will looks as though you are in the exact
same local folder on your computer as before. If you were to play an audio file, the sound would come out of your machine’s
speakers instead of the remote machine. The reason is because the CPU command duplicates the mounts in your namespace on the
remote machine using the 9p protocol over the network. Say you were compiling some software and it was taking too long,
you could interrupt and cpu it to another machine and it would carry on working on the same files but using the other
machine’s computing resources!
But virtual file systems don’t have to correspond to real files on a disk. Take the acme editor (plan 9’s default editor). When run, it has a virtual file system. Every open buffer creates a few virtual files which other applications can read and write to to implement plugins. So you don’t have to learn lua or emacs lisp to write acme plugins, you can write them in any language which can read and write to files.
But we don’t use plan 9 so why does any of this matter? Well, 9P (or at least the slightly newer 9P2000) is used a lot today, but pretty much for one single task. When you are running virtual machines and want to share a folder between guest and host, it uses the 9p protocol! What this means is that even though we don’t have the full distributed package that you get with plan 9, from linux, mac os, bsd (etc), you can at least mount 9p file systems and use them as an idiot proof way to scale applications to clusters with great ease!
The haskell library
So now we get back to haskell. I am completely convinced that plan 9 is genius, and I want all of my applications
to start speaking 9p what are my options? Well there is Network-NineP, but the
file systems that it creates work with the mount command in linux, but don’t seem to work with 9pfuse
and so I cannot mount them from Mac OS. I’m sure I could have fixed it but I felt like there was an opportunity to
design a library with a far more idiomatic haskell interface.
A Monadic Interface
The first version of the interface that I came up was inspired heavily by lucid. This is an eDSL for building HTML. Both HTML and file systems are trees so it is a less crazy place to source inspiration than it initially seems.
So to start with, I wanted a file system monad, FileSystem a, and just like with lucid, I want sane
defaults and changes to the defaults to be provided optionally through type class magic. We end up with
the following two functions:
dir :: (INodeDir arg res) => String -> arg -> res
file :: (Monad m, INodeFile m (File m) t, Ends () t) => String -> t
And I’ll confess, the types give nothing away… that is the downside to type class magic. I’ll define a simple file system to show you how they are used:
demo :: FileSystem ()
demo = dir "/" $ do
file "foo"
file "bar"
Now in the library, this types and you can run it. If you mount it, you get a boring file system with two files. You can’t interact with them. So the next trick is to attach reader and writer functions to files:
demo :: FileSystem ()
demo = dir "/" $ do
file "foo" (StringR $ return "Hello, World!")
file "bar" (StringW . putStr)
Now, if you cat from foo, you see Hello, World! and if you echo into bar you see what you echoed on the server.
There is also syntax for changing file permissions and owner:
demo :: FileSystem ()
demo = dir "/" $ do
file "foo" [#perms := 0o444] (StringR $ return "Hello, World!")
file "bar" (StringW . putStr)
Now I won’t go into how this is implemented, this post isn’t about such scary type class magic, but I will go into
what happens when you pass this FileSystem to the server. Almost nothing! It’s a free monad! The TL;DR is
that a free monad is a monad which, instead of performing a computation, produces an abstract syntax tree of the monad.
This is used by algebraic effects, the AST is then split up and each command is dispatched to the correct effect handler.
But essentially, the code is already data. The definition of FileSystem was something like this:
data FileSystemF r = FileNode (File IO) r
| DirNode (Directory IO) ~(FileSystem ()) r
deriving Functor
data FileSystem a = Pure a
| Free ~(FileSystemF (FileSystem a))
But this interface doesn’t quite sit right with me. Readers and writers are in the IO monad. What if we wanted another
monad? For example, the State or STM monad could be really useful. You can see that File and Directory are parameterised
by IO, we could parameterise them by some monad m and run the effects in any arbitrary monad? But it isn’t that simple!
Maybe you want the file tree to change depending on what has been written to a file? Say we used the state monad, you would
need access to the State in the FileSystem monad! We need to reach for something stronger and make a full blown free monad
transformer.
The Free Monad Transformer
What is actually defined in the library now is FileSystemT. It’s definition is the following:
data FileSystemFT m r = FileNode (File m) r
| DirNode (Directory m) ~(m (FileSystemT m ())) r
| Embed (m r)
deriving Functor
data FileSystemT m a = Pure a
| Free ~(FileSystemFT m (FileSystemT m a))
instance Functor m => Functor (FileSystemT m) where
fmap f (Pure a) = Pure $ f a
fmap f (Free r) = Free $ fmap (fmap f) r
instance Monad m => Applicative (FileSystemT m) where
pure = Pure
(<*>) = ap
instance Monad m => Monad (FileSystemT m) where
(Pure x) >>= f = f x
(Free r) >>= f = Free (fmap (>>= f) r)
instance MonadTrans FileSystemT where
lift ma = Free (Embed (ma >>= \a -> return $ Pure a))
Embed is used to embed monadic actions from the inner monad into FileSystemT a. This allows you to write code like this:
demo :: FileSystemT (StateT [String] IO) ()
demo = dir "/" $ do
files <- get
forM_ files $
\f -> file f (StringR $ return $ "I am called " <> f)
Both the file system and the file operations are parameterised upon the same state from the State Monad! Perfect! The
final bit of explanation is how this monadic-monster is evaluated? Each time the file system has to be queried, it runs
evalTree :: Monad m => (m ~> IO) -> FileSystemT m a -> IO [Tree IO], The code of which is:
treeAlgebra :: Monad m => FileSystemFT m (m [Tree m]) -> m [Tree m]
treeAlgebra (FileNode f r) = do
rest <- r
pure $ TFile f : rest
treeAlgebra (DirNode d childrenM r) = do
children <- childrenM >>= runTree
rest <- r
pure $ TDir d children : rest
treeAlgebra (Embed xm) = join xm
runTree :: Monad m => FileSystemT m a -> m [Tree m]
runTree (Pure _) = pure []
runTree (Free ft) = treeAlgebra (fmap runTree ft)
evalTree :: Monad m => (m ~> IO) -> FileSystemT m a -> IO [Tree IO]
evalTree h = fmap (map toIO) . h . runTree
where toIO (TDir d kids) = TDir (evalDir h d) (map toIO kids)
toIO (TFile f) = TFile (evalFile h f)
We have three functions here. treeAlgebra tells us how to flatten the FileSystemFT m structure in the context of the
inner monad, m. Notice that this is when Embed is actually used to invoke a monadic action in the context monad.
runTree uses treeAlgebra to flatten the actual monadic structure. And evalTree uses a user-defined natural transformation
to pull it into the IO monad, so the server can invoke the file operations.
That’s all from me! If you want to check out the library, you can find it here!