Last time, I said that I was going to put our cheap new free monad to work, so let's give it a shot.

Yield for Less

Last month at TPDC 2011, Roshan James and Amr Sabry presented Yield: Mainstream Delimited Continuations.

Without calling it such they worked with the free monad of the indexed store comonad. Ignoring the comonad, and just looking at the functor we can see that

```
data Store i o r = Store (i -> r) o
deriving (Functor)
```

```
class Functor y => Yieldable y i o | y -> i o where
yield :: o -> y i

instance Yieldable (Store i o) i o where
yield = Store id
```

The free monad of `Store i o` is a nice model for asymmetric coroutines.

```
type Yield i o = Free (Store i o)

liftFree :: Functor f => f a -> Free f a
liftFree = Free . fmap Pure

instance Yieldable y i o => Yieldable (Free y) i o where
yield = liftFree . yield
```

With its `Monad`, you can write computations like:

```
foo :: Num o => Yield () o ()
foo = do
yield 1
yield 2
yield 3
```

or to streamline one of James and Sabry's examples

```
walk :: Traversable f => f o -> Yield i o (f i)
walk = traverse yield
```

is an asymmetric coroutine that yields each of the elements in a traversable container in turn, replacing them with the responses from whatever is driving the coroutine.

James and Sabry called this the naive frame grabbing implementation. It is inefficient for the same reasons that we discussed before about retraversing the common trunk in free monads in general. Note that the unchanging trunk here isn't the data structure that we're traversing, but instead the chain of `Store i o` actions we took to get to the current instruction.

James and Sabry then proceeded to optimize it by hitting it with Codensity.

```
type Iterator i o = Codensity (Yield i o)

instance (Monad y, Yieldable y i o) => Yieldable (Codensity y) i o where
yield = liftCodensity . yield
```

But we've now seen that we can get away with something smaller and get the same benefits.

```
liftF :: Functor f => f a -> F f a
liftF f = F (\kp kf -> kf (fmap kp f))

instance Yieldable y i o => Yieldable (F y) i o where
yield = liftF . yield
```

Flattened, and with the store untupled the new optimized representation looks like:

```
newtype Iterator i o a = Iterator
{ runIterator ::
forall r. (a -> r) -> (o -> (i -> r) -> r) -> r)
}
```

and provides the same performance improvements for asymmetric coroutines as the `Codensity` version, used by James and Sabry, which would flatten to the much larger and less satisfying:

```
newtype RSIterator i o a = RSIterator
{ runRSIterator :: forall r.
(a -> (o -> (i -> r) -> r) -> r)
-> (o -> (i -> r) -> r) -> r
}
```

They proceed to give an encoding of delimited continuations into this type and vice versa, but the rest of their material is of no further use to us here.

As an aside the performance benefits of encoding Oleg's iteratees in continuation passing style arise for much the same reason. The resuting encoding is a right Kan extension!

Who Needs the RealWorld?

As Runar recently tweeted, we have put this to good use here at ClariFI. (Yes, we are hiring! If the contents of my blog make sense to you then email me and let's talk.)

At ClariFI have a strongly typed functional language that bears a strong resemblance to Haskell with rank-n types and a number of other interesting type system features that are particularly suited to our problem domain.

However, as with Haskell, we needed a story for how to deal with `IO`.

Now, GHC models IO with the type

```
newtype IO a =
IO (State# RealWorld -> (# a, State# RealWorld #))
```

where they model `IO` by working in a strict state monad, passing around a real world that they promise not to mutate or copy. (In practice, the world is passed around as a 0-byte token.

This is somewhat problematic semantically, for a number of reasons.

First, There is always the risk of copying it or plumbing it through backwards, so we carefully hide the `State# RealWorld` from the end user. So this model really wants some notion of uniqueness or linear typing to render it perfectly safe. Heck, the entire Clean language arose from just trying to address this concern.

Second, you don't really get to pass the real world around! We have multiple cores working these days. Stuff is happening in the back end, and as much as you might want it to be, your program isn't responsible for everything that happens in the `RealWorld`!.

Third, if in some sense all bottoms are the same, then `forever (putStrLn "Hello World")` and `undefined` are the same in that sense, despite the slew of side-effects that arise from the first one. Now, in Haskell you are allowed to catch some bottoms in the IO monad, and thereby escape from certain doom, but it is still a reasonable objection.

One alternate model for talking about `IO` is to view it as a free monad of some set of operations. This approach was taken by Wouter Swierstra's Functional Pearl: Data Types a la Carte.

You can then supply some sort of external interpreter that pumps that tree structure, performing the individual actions.

This is unsatisfying because of two things:

First, the performance is abysmal using the common ADT encoding of a free monad. Janis VoigtlĂ¤nder of course showed, that this can be rectified by using the `Codensity` monad.

Second, the set of `FFI` operations is closed.

What we've done instead is to define our primitive `IO` actions externally as some `FFI` type:

```
type FFI o i -- external, side-effecting computation taking o, returning i
```

In practice, these are obtained by reflection by our `foreign import` statements since we run in the JVM.

Then we looked at the free monad of

```
newtype OI a = forall o i. OI (FFI o i) o (i -> a) deriving Functor
```

where `OI` is the indexed store comonad used as the building block above, yielding arguments to `FFI` of type o, and representing a computation that would resume with a value of type i to obtain a result of type a.

``` ```

`In some sense this yields a more useful notion than Richard Kieburtz's novel, but largely unimplementable, ``OI` comonad from Codata and Comonads in Haskell.

Flattening `Free OI` would yield the naive

```
-- data FIO a where
--    Return :: a -> FIO a
--    FIO :: FFI o i -> o -> (i -> FIO a) -> FIO a
```

which would be interpreted by the runtime system.

But once we've converted to our Church-encoded Free monad and flattened we obtain:

```
newtype IO a = IO
(forall r. (a -> r) ->
(forall i o. FFI o i -> o -> (i -> r) -> r) ->
r)
```

with the `Functor` and `Monad` instances defined above.

This then gives us a number of choices on how we implement the runtime system:

We can use the machinery described earlier to convert from `IO a` to `Free OI a` or `FIO a`, and then have the runtime system pattern match on that structure on our main method, taking the `FFI` actions and their arguments and passing the results in to the language, or we can invert control, and implement things more directly by just defining

```
FFI = (->)
```

while letting the `FFI`'d methods have side-effects, and then defining

```
unsafePerformIO :: IO a -> a
unsafePerformIO (IO m) = m id (\ oi o ir -> ir (oi o))
```

But regardless of how `FFI` is implemented, this model provides a clear structural difference between `forever (putStrLn "Hello")` and `undefined` and does not require us to believe the pleasant fiction that we can get our hands on the real world and pass it around.

Our actual `IO` representation is only slightly more complicated than the one presented here in order to deal with the plumbing of an extra continuation to deal with Java exceptions, but the substance of this approach isn't changed by this addition.

[Edit: incorporated a minor typographical fix into Iterator from Max Bolingbroke]
[Edit: fixed Store to be data, an liftM that should have been an fmap and added the missing Functor constraint that was present in my actual implementation but didn't make it to the web, and a couple of typos in the implementation of RSIterator, all noted by Clumsy.]