Case Study: Optimising Parsley

The best way to understand why a profiling report outputs certain performance metrics (for Haskell) is to dive into the actual core itself, which is what the surface-level Haskell code compiles down into.

Usually, if one is confused about something in the core, it is best to compare it with the original program.

regTest :: Parser Int
regTest = newRegister_ (code 7) (\r -> modify_ r makeQ (succ @Int) [||succ @Int||]) *> (let g = get r in g *> g))

This makes a new register, which in this context would be an STRef, containing 7; it then modifies it with +1, and afterwards it gets the value out twice, and returns it the second time.

(32) lvl =
 λs1 ->
   -- Using 'newMutVar', it makes the new register containing a value 'lvl' we expect to be 7.
   let! (#, #) ipv ipv1 = newMutVar# lvl s1 in
   -- Using 'readMutVar', it then reads then 7 to get an int out in ipv1
   let! (#, #) ipv ipv1 = readMutVar# ipv1 ipv in
   -- It performs the succ function on value 7 (ipv1) and puts it back in the hole using 'writeMutVar'
   let! s2# = writeMutVar# ipv1 ($fEnumInt_$csucc ipv1) ipv in
   -- We read from the register twice, using 'readMutVar', but we only care about the second value...
   let! (#, #) ipv _ = readMutVar# ipv1 s2# in
   let! (#, #) ipv ipv1 = readMutVar# ipv1 ipv in
   -- ... which is returned the second time after reading.
   (#, #) ipv (Just ipv1)

Is there a way of seeing if what your code compiles down into is nonoptimal? Usually we will see something we’re unhappy with. In the above case, there is no chance that the core version of the program could be better. If we start seeing function applications or random case statements, we might be suspicious.

Consider the following code, which is supposed to take a sequence of alternating a’s and b’s and roll them all up:

manyTest :: Parser [Char]
manyTest = many (string "ab" $> (code 'c'))

In the core version of manyTest, one of the problems we can observe within it is that a particular function called exit is created twice:

  λs1 ->
    ...
    let
      exit =
        λo# eta ipv ->
          case ==# o# ipv of
            DEFAULT ->
              (#, #) eta Nothing
            1 ->
              let! (#, #) ipv ipv1 = readMutVar# ipv1 eta in
              (#, #) ipv (Just (ipv1 []))
      exit =
        λo# eta ipv ->
          case ==# o# ipv of
            DEFAULT ->
              (#, #) eta Nothing
            1 ->
              let! (#, #) ipv ipv1 = readMutVar# ipv1 eta in
              (#, #) ipv (Just (ipv1 []))

The question becomes “why has the compiler not worked out that these are the same functions, and duplicated it when it didn’t need to?”. In the body of the let statement of the core version, we can observe where exit is used - it tells us that the program checks if there is enough input, and if so, is that input the character ‘b’. So we expect the call of exit to be somewhere where we read characters.

in
   let ...
   in case <# ipv dt of
        DEFAULT ->
          exit o# eta ipv
        1 ->
          case indexWideCharArray# input# ipv of
            DEFAULT ->
              exit o# eta ipv
            'b' ->
              ...

These exit variables would have been defined in our original code somewhere. In this case, we can see the two different functions sat and emitLengthCheck both use the expression $$bad which represents the exit variable.

sat ... =
  ... if ... then ... else $$bad

emitLengthCheck ... =
  ... if ... then ... else $$bad

We fail in the case in which we don’t have enough input, and we fail in the case where the character doesn’t match. So we ask why these exit variables are two different values, when they could have been the same one - these calls to $$bad should really come from the same place. The question then becomes: “how do we work out where they came from, and how do we trace them back to their common source?”.

We can find that in some function evalSat, that we’ve defined a function maybeEmitCheck that defines the bad variable in a let statement, and uses it twice in its body.

evalSat .. = do
  ...
  where
    maybeEmitCheck ... =
      [|| let bad = $$(raise y)
          in $$(emitLengthCheck n (sat (genDefunc p) mk [||bad||]) [||bad||] y)
       ||]

The first usage of bad is the one that gets passed to sat, and the second usage is the one that gets passed to emitLengthCheck. We can correspond this to the previous core code: the first exit corresponds to the bad passed to emitLengthCheck, and the second exit corresponds to the bad passed to sat. In this case, we don’t currently know why GHC has chosen to define exit twice.

We could also be curious as to whether certain operations can be factored out. For example, in the following code we could ask can these length checks <# o# dt and <# ipv dt be factored out - why is it doing these twice?

  λo# eta ->
    case <# o# dt of
      DEFAULT ->
        exit eta
      1 ->
        ...
        let
          ipv =
            +# o# 1
        in case <# ipv dt of
          DEFAULT ->
            ...

And we can actually fix this by changing the definition of manyTest to:

manyTest :: Parser [Char]
manyTest = many (try (string "ab") $> (code 'c'))

Going back to the core, we can see now that the first length check has been replaced with the second length check i.e. it’s been factored out. Because we always want to read an a character followed by a b character, this code will now always check if there are atleast two characters before trying to read any characters at all, rather than reading an a and then failing when there are no further characters.

  λo# eta ->
    case <# (+# o# 1) dt of
      DEFAULT ->
        exit eta
      1 ->
        ...
        let
          ipv =
            +# o# 1
        in
          ...

We can also make the distinction between lazy and strict values. When we see a let, this is a lazy variable declaration, whereas a let! signifies a strict variable declaration. We can spot code where values are lazily constructed and determine if that value doesn’t actually need to be lazy. For example, the following code is lazy, but we should be able to determine it strictly. In theory, we should be able to find where the creation of ipv is in the surface program and then bang-pattern it, resulting in let becoming let! in the core program.

  let
    ipv =
      +# o# 1

This entire process is the general work flow when searching for optimisations by looking at Haskell core:

• Writing the program
• Generating the core
• Analysing the core to see if we are unhappy about how some code has been generated
• Tweaking the way the code generates so that the ineffiency disappears. (If we are using staging, this means changing the code from the staging point-of-view.)

If we are trying to determine what is causing slowness in a certain effect system, one thing that could be interesting to inspect is abstraction - if we have a lot of function calls that could have been inlined, or unwrapping and rewrapping of data structures.

Another thing to look out for is if we certain arguments haven’t been unboxed when instead they could have been. Most types in GHC are boxed (values of that type are represented by a pointer to a heap object, e.g. the representation of Int is a two-word heap object). An unboxed type is represented by the value itself, no pointers or heap allocation is involved. These correspond to the “raw machine” types we would use in C. Most unboxed types end in the character #, e.g. Int#, Double#, Addr#, (#, #). Similarly, the primitive operations on these types look like, for example, <#, +#, *#.

To illustrate the consequence of boxed/unboxed types, consider the situation where we have a recursive call which takes an integer as an argument. If this integer had not been unboxed in the core, then the program would box the integer to the call of the recursive function; within the function it will then unbox the integer to do the work on it, and afterwards box up another integer as an argument to the recursive call. This is essentially a looping of unnecessarily boxing up and unboxing values.

The following code illustrates a recursive loop where the integer argument passed in (o#) is already successfully unboxed:

  let
    rec
      loop =
        λo# eta ->
          ...
          loop (+# ipv 1) s2#

So we are looking for constructors where we see a call to function wrap something up, and immediately on the other end of the function, wrap something up again. (This is something monad-bayes might be falling prey to).

As a helpful mindset, (if we were crazy) we could actually write the generated core code manually - we can look at this manual code and figure out what we can do to improve it ourselves. We then identify that we could have done something better, and wonder why hasn’t the compiler done it. Getting the compiler to play ball is then the hard part - we have to convince the compiler that a certain optimisation is possible.

The canonical way of fixing performance issues in effect systems is removing the monad transformers and hand-rolling the entire instance. Although this is against the point of effect systems, at the same it can be very helpful. If we handroll the instance (which we can do by basically taking the monad transformed instances and inlining the definitions ourselves until we get to something primitive), we are essentially looking to see whether the core has generated that. This is a pattern of creating the ideal program, and working out which bits the compiler has missed out on that we have recognised. This is always a good approach when we don’t understand what can be done better to the original program yet, and is a way to recognise and understand unfamiliar structures in core, such as (#, #).

The relationship between the profiling information and the core, is more obvious than the relationship between the profiling information and the original code. We can use the profiler to guide us to the parts of the core that we want to look at.

Additionally, although memory leaks might not be what our performance issues are, they also could be. In Haskell, it’s not called a memory leak, it’s a space leak which is a bunch of unevaluated thunks which is causing a long chain of computation. The memory is held on to by the thunks even though it is potentially not used. If we see lots of heap activity, this could be a sign that laziness in our program is adding overhead. Also, if we are seeing a lot of objects being churned through (even if they are going through quite fast), we could ask “are those objects necessary, or could they have been unboxed and thrown away?”.

In the core visualisation, we also can highlight over certain fragments of code, and in the top right corner, this shows us the type information and also strictness properties. Even though something may appear to be lazy, we can identify that something is actually a strict binding (because it says S rather than L).

Here’s an example of when the generated core has inlined and eliminated all the ST occurrences. We have the following code:

So the reader monad should be milling around. This is cata4:

And we have this function, evalPush:

But in the core, we can see the reader monad has been completely eliminated. There is no fmap, and no IFunctor instance from the cata4 - it’s just made as a recursive function.

Here is another example - this involves StateT + Reader

Let’s go find this in the core and verify again the abstraction is gone.

Now there is that suspicious looking bit here:

but the $s around here are indications of specialisation. We can visit these in this file and see what’s up.

That’s the code - it hasn’t been marked as inline and it’s quite big, so the compiler is probably reluctant to inline it (or specialise it a lot), but let’s check the core:

So it’s unpacked the dictionary straight into the function. You can see that here:

But it’s not as optimised as it could have been (probably because it wasn’t told it could specialise across the file boundary (this is defined in a different core dumped file)so it’s optimised as much as it could generally but hasn’t optimised it specifically to StateT as it could have done. That’s a shame, but fixable easily (if JW cared about the internal library performance).

Now to go and check out the specialised applicative state functions!

It’s created an app for readerT + stateT. We can see the r1 from reader, and s' from state in there. There are no references to the original dictionaries, or indeed the original functions from either ReaderT or StateT.

The file is however, full of crap. There are a lot of dead specialised instances etc.

Here as well is a specialised StateT + FreshT (<*>).

(CPS can be used to get rid of all the stupid tuples…)

Q: Were any particular code changes necessary to ensure that the program specialised, e.g. there are cases of non-concrete monads m in type definitions, are any actions needed to make sure that GHC can work m out?

A: Nope – GHC can specialise the monads when it sees them concretely then the inliner works its magic on the specialised code to form what we see there. In the ideal, monads should be just as fast as the hand written equivalent.

The reason GHC left the traverseCombinator function alone, is because it wasn’t marked with the INLINABLE pragma, so it doesn’t have the code in the interface file (in other words, it doesn’t know what it is in the other file). If we then chuck an INLINABLE pragma on it, let’s see how it affects the core of the function we saw before:

We can see that it still calls traverseCombinator, but it has an $s this time and there are no arguments passed to it. Let’s take a peek inside:

Now the reader and state monad code has been inlined and optimised within this function. Interestingly, the specialiser wanted to specialise, but the inliner chose not to inline the expose parameter, which looks like this:

Another thing to notice is that, before when the expose parameter was left there, it made the code more complex than it needed to be (because the expose function used here is actually just pure roughly). After having marked traverseCombinator as INLINE, it is inlined into the function, and the internals are simplified further. The eta is the reader context. We can obviously see that the state is being passed around happily - that’s as optimal as it gets, and all GHC needed to go from the slower only-unwrapped version to this fully inlined and optimised version was an INLINE pragma.

GHC has also done the same with the other use of traverseCombinator:

The $wg function above is the postprocess function.

The moral of the story is: if we don’t see $w or $s in the core anywhere, optimisations are not on.

• $w is usually prepended to functions that the compiler as unwrapped some of the arguments for (eliminating a pattern match).
• $s is usually prepended to specialised functions.

If we happen to inline a particular function and this results in a slower program, this implies that the code size is too big - so this leads to memory problems (cache issues). If the function isn’t being optimised after it has been inlined, then it shouldn’t be inlined.

Q: Is it ever the case that you can undo an inline for some other function, and keep the new inline (which previously resulted in slower performance), so that it results in an overall better run-time?

A: Yes. You can set the phase of the inliner. You can say “inline past phase 2” etc.

An example of using CPS in Parsley

Consider a program where we have the state monad in all different sorts of places, and we are unhappy with the building of the tuples being around.

type State s = StateT s Identity
newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }

A good way to get rid of that is to use the continuation-passing-style form of the state monad.

newtype StateT s m a = StateT { unStateT :: forall r. s -> (a -> s -> m r) -> m r }
  deriving Functor

The translation we do is, we leave the result type r abstract, we take the state s, and then we take the function that consumes the a produced by this computation as well as the s in order to return the m r. This is actually the transformation we get when we apply the codensity transformation to state.

To run the state itself, we call f which is the function of type forall r. s -> (a -> s -> m r) -> m r, but we have to give it an argument of type (a -> s -> m r) as well as the initial state s. What we’re looking for is an a -> s -> m (a, s) so that we can roughly recover m (a, s). So the function we pass it is simply something that takes an a and s and calls return on the tuple (a, s) – so this is the final continuation that runs with the state.

runStateT :: Monad m => StateT s m a -> s -> m (a, s)
runStateT (StateT f) s = f s (\x s' -> return (x, s'))

Defining the actual instances of the CPS-form state monad is relatively okay after that point. We will find that the m never actually requires a monad constraint, because what we’re actually doing all the time is building up continuations – we don’t actually have to interact with the underlying monad m until we lift stuff into it (but most of the time, we are just feeding along continuations).

instance Applicative (StateT s m) where
  {-# INLINE pure #-}
  pure x = StateT (flip ($ x))
  {-# INLINE liftA2 #-}
  liftA2 f (StateT mx) (StateT my) = StateT (\s k -> mx s (\x s' -> my s' (\y s'' -> k (f x y) s'')))

instance Monad (StateT s m) where
  {-# INLINE return #-}
  return = pure
  {-# INLINE (>>=) #-}
  StateT mx >>= f = StateT (\s k -> mx s (\x s' -> unStateT (f x) s' k))

The advantage is that given a monad with a data constructor containing n parameters, such as:

data Trace a
  = Trace
      { variables :: [Double],
        output :: a,
        density :: Log Double
      }

this becomes an n argument function.

For example with the StateT monad, this becomes a function where we say, here’s the next thing along, mx :

  StateT mx >>= f = StateT (\s k -> mx

we provide it with the current parameters one after another (which in this case is just s) :

  StateT mx >>= f = StateT (\s k -> mx s

and once it’s done (producing an x) :

  StateT mx >>= f = StateT (\s k -> mx s (\x

take all of the new parameters (which is just s') :

  StateT mx >>= f = StateT (\s k -> mx s (\x s'

and do what was meant to be done after the computation k, which is the f :

  StateT mx >>= f = StateT (\s k -> mx s (\x s' -> unStateT (f x) s' k))

Very often, CPS is a good technique for optimisation. It doesn’t always work, but it rarely makes things worse. The fact that we don’t have to interact with the underlying monad means that the effect of the monad m in the StateT s m only gets ran when we use an operation from that monad. We can think of it as, the StateT computation is building that computation using continuations, so it doesn’t need to interact with m at every step.

• Q : Given a record data type such as:

  data Trace a
    = Trace
        {
          variables :: [Double],
          output :: a,
          density :: Log Double
        }
  

  is it unavoidable to lose the whole record feature (named parameters) if we were to optimise this to avoid the wrapping and rewrapping of the constructor

• A : Nope! If it’s strict and haskell can unbox it, you can still use the record syntax and record accessors – it’s just they will get optimised out and replaced with just the relevant argument of the function directly.

A Conversation on CPS’ing Datatypes

MN: I’m struggling a bit to work out what this (monadic) data type looks like in CPS-form, could you help me out?

data Trace a
  = Trace
      { variables :: [Double],
        output    :: a,
        density   :: (Log Double)
      }

JW: What’s the instance?

MN:

instance Monad Trace where
  t >>= f =
    let t' = f (output t)
     in t' {variables = variables t ++ variables t', density = density t * density t'}

JW: Thats a writer monad

MN: I wasn’t aware that the instance mattered as well

JW: It helps me see what the semantics are.

This one is a weird one. I think this is it:

newtype Trace a = Trace { runTrace :: forall r. ([Double] -> a -> Log Double -> r) -> r }

MN: I was looking back at your StateT CPS example, and i was wondering why there was an extra parameter s before the continuation:

newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }
newtype StateT s m a = StateT { runStateT :: forall r. s -> (a -> s -> m r) -> m r}

I’m just trying to grasp a general blueprint of CPS’ing.

JW: That’s the input. The inputs stay as inputs, the outputs get turned into a function, and then you can curry the function when otherwise you return a tuple.

MN: Is there a general rule for multiple constructor data types? For example, would:

data Either a b = Left a | Right b

look like:

newtype Either a b = Either { forall r. (a -> b -> r) -> r}

JW: No, it can’t. That implies that you have both results available at once, i.e. a product. For a coproduct, you have two continuations:

newtype Except e a = Except { runExcept :: forall r. (a -> r) -> (e -> r) -> r }

MN: Ooh i understand, thanks.

JW: So here’s the same problem in reverse:

data ParsecT m a = ParsecT { runParsecT :: forall r. String -> (String -> a -> m r) -> (String -> m r) -> m r }

Can you figure out what the “original” datatype was?

MN: I’m having a think, the input String and the multiple continuations together are confusing

JW: Perhaps break it into two parts then?

MN: I would’ve thought that the original data type would contain a function String -> m (String, a)

JW: Ok, so that represents the StateT monad: String -> m (a, String) is StateT.

So now let’s factor that out:

type ParsecT m a = StateT (Foo m) a
newtype Foo m a = Foo { runFoo :: forall r. (a -> m r) -> m r -> m r }

Now, try to reverse engineer Foo.

MN: Alright, now that’s confusing because there’s an input after the continuation

JW: It’s not an input ;). Does this help:

newtype Foo m a = Foo { runFoo :: forall r. (a -> m r) -> (() -> m r) -> m r }

MN: Right, so something like:

data Foo m a = Foo (m a) | Bar

JW: Yep, or, in other words: MaybeT.

So now you have:

type ParsecT m a = StateT String (MaybeT m) a

or rather:

newtype ParsecT m a = ParsecT { runParser :: String -> m (Maybe (a, String)) }

MN: Ohh, that’s so complex - how that second continuation comes in is wacky

JW: You can conceptualise it as two outcomes: either the parser succeeds, or the parser fails. Those represent the two branches of the maybe.

In reality, the real parsec has 4 continuations:

type Parsec a = forall r. String -> (String -> a -> r) -> (a -> r) -> (String -> r) -> r -> r

One for success consuming input, one for success not consuming input, one for failure consuming input, and one for failure not consuming input.

MN: I see, so multiple continuations can represent either multiple constructors, or a nesting of monad transformers?

JW: The multiple continuations represent multiple constructors, or rather, multiple paths. It can mean that the nested monad has multiple branches itself, which is the case here, but all composed monads form their own unique monad.

MN: This is great stuff, thanks a lot!

JW: Just don’t be tempted to transform List, or any recursive type for that matter. It’s an infinite type unless you use Fix.

MN: I’m seeing two different versions of what the result r is when CPS’ing data types, for instance:

newtype Maybe a = Maybe { runMaybe :: forall r. (a -> r) -> r}

and

newtype Maybe a = Maybe { runMaybe :: forall r. (a -> Maybe r) -> Maybe r}

Are either/both correct?

JW: Neither is correct. They are both missing the Nothing continuation. However, the first is more correct. The second is technically more correct without the second continuation, but is far too strong. We want the r to be as weak as possible. Your second one is the codensity maybe.

MN: I was wondering about how to write the corresponding run functions for CPS data types - i understand your type definition for your CPS StateT, but i’m not sure how to apply it to types such as Maybe. Here’s my attempt:

data Maybe a = Just a | Nothing

newtype MaybeCPS a = MaybeCPS { unMaybeCPS :: forall r. (a -> r) -> (() -> r) -> r }

runMaybeCPS :: MaybeCPS a -> Maybe a
runMaybeCPS m = (unMaybeCPS m) Just (\() -> Nothing)

JW: Yeah that’s correct. Obviously you don’t need the const Nothing. You can just remove the () from the type.

MN: Thanks, also, given your runStateT has type:

runStateT :: Monad m => StateT s m a -> s -> m (a, s)

Would it also be valid to use the approach i’ve done with Maybe and MaybeCPS? Making a function:

runStateTCPS :: Monad m => StateTCPS s m a -> StateT s m a

JW: Nah, Maybe is kinda incidental. You want the same type as before. The runStateT provides (return . (,)) or something.

MN: Ah i see, so just for the cases where constructors don’t contain functions? Such as:

data Trace a
  = Trace
      { variables :: [Double],
        output    :: a,
        density   :: (Log Double)
      }

newtype TraceCPS a = TraceCPS { unTraceCPS :: forall r. ([Double] -> a -> Log Double -> r) -> r }

runTraceCPS :: TraceCPS a -> Trace a

JW: If you want the Trace datatype to come out, then sure. Perhaps you’re only interested in one of the outputs. Idk.

MN: I get it! thanks.

JW: Realistically you can provide anything, including the rest of your program if you wanted to eliminate the Trace datatype entirely..

MN: I’m having a difficult time defining the applicative instance for MaybeCPS:

newtype MaybeCPS a = MaybeCPS { unMaybeCPS :: forall r. (a -> r) -> (() -> r) -> r }

I think i need a function of type:

app :: ((a -> r)      -> (() -> r) -> r)
    -> ((a -> b -> r) -> (() -> r) -> r)
    -> ((b -> r)      -> (() -> r) -> r)

but i’ve no idea how to make that possible

JW: Again, I would get rid of the unit, but just intuitively:

mf <*> mx = \good bad -> mf (\f -> mx (\x -> good (f x)) bad) bad

That’ll do it.

MN: I’m just including the second continuation so i can see how this idea would apply to data types with multiple continuations

JW: The second continuation is still a continuation without the () because it’s lazy. () => a is iso to a in a lazy language. In a strict language you’d have to use () => a (like scalas =>A type).

You gave me the type of >>= above though, which is this:

mx >>= f = \good bad -> mx (\x -> f x good bad) bad

MN: So, i’m trying to redefine this function in terms of TraceCPS (which is essentially the writer monad), but it’s looking unbelievably awkward because m itself isn’t in CPS form:

bind :: Monad m => m (Trace a) -> (a -> m (Trace b)) -> m (Trace b)
bind dx f = do
  t1 <- dx
  t2 <- f (output t1)
  return $ t2 {variables = variables t1 ++ variables t2, density = density t1 * density t2}

Is there a nice way of doing this?

JW: Huh? Why not mT Trace a or TraceT m a

MN: Shit you’re right

JW: I think you want TraceT as it happens

MN: I’m also guessing that it’s not possible to swap two arbitrary monads, i.e. a generalised sequence?

JW: No, the order of composition matters. StateT s [] is not the same as ListT (State s) – one is localised state, the other is global state. In other words: s -> [(a, s)] vs s -> ([a], s)

MN: So, i obviously don’t expect you to look at all of this, but is this the general transformation i should expect when handling arbitrary monads m inside of a CPS-form monad transformer?

i.e. will there will inevitably be some block of normal monad work? I don’t know if that question makes sense, i’m just not too confident about how the rest of my program should transform to accommodate the introduction of a CPS’d monad.

JW: It shouldn’t need to accomodate it at all if you’ve done it right. You can substitute a monad in for its CPS form without any changes. Like, you’re passing in a TraceCPS a in there – I don’t expect that. The original trace data should be passed in at point of runTrace.

MN: Hmm, this might be the situation of me trying to convert functions which are already designed silly.

JW: Your mhTrace is weird.

MN: Yeah, that was the existing function found in monad-bayes.

JW: It starts with a trace, and ends in another monad that returns a trace, the whole thing should just be a TraceT m a computation. Then you provide the initial configuration by running that if you wanted.

runTraceT :: TraceCPST m a -> m (Trace a)

is something you can do. The input trace is a little weird because that implies it is more of a state than a writer.

It might be that Trace is used more like State, in which case runTraceT :: TraceCPST m a -> Trace a -> m (Trace a) is a more acceptable type.

MN: Could i double-check with you whether my translation of mapStateT to CPS is correct? i’ve had to introduce a Monad m, Monad n constraint, which i’m not sure is right:

mapStateT :: (m (a, s) -> n (b, s)) -> StateT s m a -> StateT s n b
mapStateT f m = StateT $ f . runStateT m

mapStateT :: (Monad m, Monad n) => (m (a, s) -> n (b, s)) -> StateT s m a -> StateT s n b
mapStateT f m = StateT (\s k -> do (b, s') <- f $ (runStateT m) s
                                   k b s' )

JW: Nothing intrinsically wrong with what you’ve done I don’t think. The Monad n constraint used to be in the »= , so it has to move somewhere. Both m and n have to be monads.

MN: This is interesting, i wonder if this has any performance impacts compared to the original mapStateT?

JW: Doubt it – it’s all amortized because the >>= you’ve introduced in n would have materialised somewhere else instead. You save binds in the CPS form, you don’t introduce them, except in one specific case where it introduces 1 which is if you immediately run out n after this computation.

runN . runStateT s . mapStateT f = runN . f . runStateT s

The left-hand side has 1 bind the right does not.

MN: Is it important to keep runStateT out of intermediate computations then?

JW: It’s not runStateT’s fault, but yes, you should because it introduces redundant returns.

MN: I see, is this unavoidable in mapStateT?

JW: It is, but return is cheap. The equality on both sides of the equation:

runN . runStateT s . mapStateT f = runN . f . runStateT s

by the way boils down to this:

mx >>= return = mx

They are equal because of that monad law, but the left hand side has the bind, and the right hand side does not.

The >>= is introduced by the mapStateT and the return by the runStateT. They should ideally cancel out, which is what happens on the right hand side.

MN: If i were looking to turn most of my monads into CPS-form, could i literally just throw the Cont monad on them and expect an improvement in performance?

JW: Cont is the wrong monad, you mean Cod. But in general, Cod can be a good strategy.

MN: Oh, i haven’t learned about the codensity monad.

JW: It’s like Cont but no r, which should feel familar.

newtype ContT r m a = ContT ((a -> m r) -> m r)

newtype Cod m a = Cod (forall r. (a -> m r) -> m r)

Cod is the difference list for monads – it ensures that all >>= are right associated.

Cod (StateT s m) a ~= StateCPST s m a

but the right hand side is more efficient - you’ll find it has no monad constraints just like yours don’t.

MN: Why would one ever use the ContT monad if Cod exists – i’m having difficulty understanding what one achieves over the other.

JW: They don’t do the same thing. ContT makes progress towards a known r. You’ll notice there is no CodT – Cod is intrinsically tied to another monad and has no callCC operation.

MN: I’m having an issue when trying to define a CPS version of liftPass (the bottom version doesn’t compile - i’m not sure what i’m supposed to do with the f).

liftPass :: (Monad m) => Pass w m (a,s) -> Pass w (StateT s m) a
liftPass pass m = StateT $ \ s -> pass $ do
    ~((a, f), s') <- runStateT m s
    return ((a, s'), f)

liftPass :: (Monad m) => Pass w m (a,s) -> Pass w (StateT s m) a
liftPass pass m = StateT $ \s k -> pass $ do
    ~((a, f), s') <- runStateT m s
    k (a, s') f

JW: What is Pass?

MN:

type Pass w m a =  m (a, w -> w) -> m a

JW: Let’s start with this non mangled function:

liftPass :: MonadWriter w m => StateT s (a, w -> w) -> StateT s a
liftPass m = StateT $ \ s -> pass $ do
    ((a, f), s') <- runStateT m s
    return ((a, s'), f)

Got it

pass (StateT mx) = StateT $ \ s k ->
    pass (mx s (\(x, f) s' -> return ((x, s'), f))) >>= uncurry k

I’ve not used runStateT here because it gets wrapped up in another return anyway, so no point in doing return ((a, f), s) >>= \((a, f), s) -> return ((a, s), f) – completely redundant.

I’ll write it in words:

Take mx, feed it the state s and you will get (x, f) out of it along with a new state s', these can be fed to a continuation (as opposed to using runStateT, which repackages them into a form that pass accepts. This produces a m (a, s) which we can bind on using uncurry k as the next step.

So you were close, just put the pass in the wrong place – at least, I think so.

It’s really hard to tell with operations like this – lots of wrong things type check. Like it also type checks if you put the pass inside the continuation for mx. It also type checks if you put the >>= uncurry k in there as well, but I think that changes the meaning slightly.

I think the key here is by putting the pass inside the continuation to mx, you make pass’s effect happen to the return, which always applies f to the mempty.

That’s probably not what you wanted, so best to run out the entire computation first. I think local from reader is another annoying one. Though they use mapStateT for that.

JW: There’s a couple of things at play with the CPS monads

The first is that you’re removing allocations of tuples and intermediate structures.The second is that you’re reassociating the binds into what may be their optimised form (but at worst it isn’t any more expensive).

By the way, did you replace your TraceCPS by the State? Or is it a complement?

MN: I haven’t, i just replaced the Control.Monad.Trans.State with the State

MN: by the way, im a bit confused, what you did with StateT was CPS right? Thy did you suggest using the Codensity monad yesterday

JW: I didn’t, you mentioned ContT and I said that’s the wrong abstraction. Cod accomplishes the second aim of the CPS – the reassociation into the optimised direction (which may or may not produce an improvement). But fully CPSing is how we can remove the allocations and get the best performance out because it physically changes the make up.

Like:

   Cod (StateT s m) a
~= forall r. (a -> StateT s m r) -> StateT s m r
~= forall r. (a -> s -> m (r, s)) -> s -> m (r, s)

You can see that’s not the same as:

forall r. (a -> s -> m r) -> m r

It’s very close though.

MN: Ah, yep i see! So the Cod still requires the use of StateT in that.

JW: Cod is a cheap dirty CPS – good in a pinch, but doing it by hand will yield better results.

MN: I haven’t learned about reassociation of binds and their optimisations before.

JW: It’s clear from this:

(mx >>= f) >>= g = m >>= (\x -> f x >>= g)

Now consider when mx = Nothing.

The left hand side evaluates using two steps:

  (Nothing >>= f) >>= g
= Nothing >>= g
= Nothing

The right hand side evalutes using one step:

  Nothing >>= (\x -> f x >>= g)
= Nothing

The left association of binds can cause an O(n^2) blowup, similar to how left associated ++ is problematic. This is talked about in freer-monads.

Cod is to monads as difference lists are to lists

MN: I understand, so a big build up in evaluation steps needed! Would you recommend CPS’ing other common monads used, such as Writer, Reader (or maybe even ListT using Fix, if i figure out how thats done)?

JW: Reader is already in CPS

I hope you’re not using ListT m a = m [a] !

• MN: Err, the Control.Monad.Trans.List one, so newtype ListT m a = ListT {runListT :: m [a] }
• JW: Ah yeah that’s what I meant – it’s technically problematic. But I think it’s major shortcomings might be with IO, I’m not sure. You should probably be using LogicT.
• MN: Is LogicT a better alternative in terms of correctness, or performance?
• JW: Correctness.

JW: I wouldn’t recommend the CPS’ing the List one anyway, you basically create a cascading tower of continuations. It’s not pretty even if you get it working.

CPS’ing Writer on the other hand, is a good bet. However, just using Cod on Writer might help, or ensuring the monoid is optimised properly – i.e. using the Difference List monoid instead of lists, for instance.

MN: I haven’t heard of difference lists before, i’ll do some reading.

JW: It’s a simple idea:

newtype DList a = DList ([a] -> [a])

fromList :: [a] -> DList a
fromList = (++)

toList :: DList a -> [a]
toList = ($ [])

instance Monoid (DList a) where
  mempty = DList id
  DList xs <> DList ys = DList (xs . ys)

cons :: a -> DList a -> DList a
cons x (DList xs) = DList ((x :) . xs)

Then if you have:

(fromList [1, 2, 3] <> fromList [4, 5, 6]) <> fromList [7, 8, 9]

Then this becomes right associated and optimal:

  (([1, 2, 3] ++) . ([4, 5, 6] ++)) . ([7, 8, 9] ++)
= ([1, 2, 3] ++) . ([4, 5, 6] ++) . ([7, 8, 9] ++)

  toList (DList (([1, 2, 3] ++) . ([4, 5, 6] ++) . ([7, 8, 9] ++)))
= (([1, 2, 3] ++) . ([4, 5, 6] ++) . ([7, 8, 9] ++))) []
= ([1, 2, 3] ++) (([4, 5, 6] ++) (([7, 8, 9] ++) []))
= [1, 2, 3] ++ ([4, 5, 6] ++ ([7, 8, 9] ++ []))

You can see how it relates to Cod:

(++) :: [a] -> ([a] -> [a])
DList = [a] -> [a]
(>>=) :: m a -> (a -> m b) -> m b
Cod = forall b. (a -> m b) -> m b

It’s just partially apply the operation to the first argument, and leave the rest as the function. It’s a trick you can pull for basically anything.

Here’s something i’ll bring your attention to:

instance Show (Fix Combinator a) where
  show = ($ "") . getConst1 . cata (Const1 . alg)
    where
      alg (Pure x)                                  = "(pure " . shows x . ")"
      alg (Satisfy f)                               = "(satisfy " . shows f . ")"
      alg (Const1 pf :<*>: Const1 px)               = "(" . pf . " <*> " .  px . ")"
      alg (Const1 p :*>: Const1 q)                  = "(" . p . " *> " . q . ")"
      alg (Const1 p :<*: Const1 q)                  = "(" . p . " <* " . q . ")"
      alg (Const1 p :<|>: Const1 q)                 = "(" . p . " <|> " . q . ")"
      alg Empty                                     = "empty"
      alg (Try (Const1 p))                          = "(try " . p . ")"
      alg (LookAhead (Const1 p))                    = "(lookAhead " . p . ")"
      alg (Let False v _)                           = "(let-bound " . shows v . ")"
      alg (Let True v _)                            = "(rec " . shows v . ")"
      alg (NotFollowedBy (Const1 p))                = "(notFollowedBy " . p . ")"
      alg (Branch (Const1 b) (Const1 p) (Const1 q)) = "(branch " . b . " " . p . " " . q . ")"
      alg (Match (Const1 p) fs qs (Const1 def))     = "(match " . p . " " . shows fs . " [" . intercalateDiff (", ") (map getConst1 qs) . "] "  . def . ")"
      alg (ChainPre (Const1 op) (Const1 p))         = "(chainPre " . op . " " . p . ")"
      alg (ChainPost (Const1 p) (Const1 op))        = "(chainPost " . p . " " . op . ")"
      alg (MakeRegister σ (Const1 p) (Const1 q))    = "(make " . shows σ . " " . p . " " . q . ")"
      alg (GetRegister σ)                           = "(get " . shows σ . ")"
      alg (PutRegister σ (Const1 p))                = "(put " . shows σ . " " . p . ")"
      alg (Debug _ (Const1 p))                      = p
      alg (MetaCombinator m (Const1 p))             = p . " [" . shows m . "]

I mean, this is magic, but same idea.

I had a show function for my ASTs, and I got a massive massive speedup by switching out all the (++) for (.).

It’s using overloaded strings:

instance IsString (String -> String) where
  fromString = showString

where a string literal is actually the showString of that string literal.

showString :: String -> (String -> String)
shows :: Show a => a -> (String -> String)

Overloaded strings lets me assign a new meaning for string literals – in this case, I give it the meaning of the difference list, because in this sort of instance, you can’t control how the (++) associates; the left and the right branches of the AST will contain them.

Using the difference list it transforms it into a fully linear sequence of them, reducing the show instance down to linear time.

MN: Would DListT look like:

newtype DListT m a = DListT { runDListT :: m [a] -> m [a] }

There are a few versions online, and they’re all using different designs/versions of ListT etc, its a bit confusing.

JW: A DList isn’t a monad, so it’s not a monad transformer, it’s a Monoid.

You are probably after this:

newtype LogicT m a = LogicT { unLogicT :: forall r. (a -> m r -> m r) -> m r -> m r}

It’s already in CPS form for you!

MN: Whaaaat, so it already has the benefits of a DList?

JW: DList isn’t for monadic computation, and Cod isn’t for alternative computation.

https://stackoverflow.com/questions/32252312/is-there-a-codensity-monadplus-that-asymptotically-optimizes-a-sequence-of-monad

MN: I’ll have a read; it looks like swapping from ListT to LogicT may be a difficult job - there aren’t any corresponding list helper functions.

JW: Well, it’s all about <|> – have a read of this too: http://okmij.org/ftp/papers/LogicT.pdf

I suspect nothing in your program changes, you use:

observeAllT :: Monad m => LogicT m a -> m [a]

You’re no doubt using alternative and monadic operations on lists anyway.

MN: How would one replace the ListT constructor with the LogicT constructor given such a function as:

newtype ListT m a = ListT { runListT :: m [a] }

fromWeightedList :: Monad m => m [(a, Log Double)] -> ListT m a
fromWeightedList = ListT

newtype LogicT m a = LogicT { unLogicT :: forall r. (a -> m r -> m r) -> m r -> m r }

fromWeightedList :: Monad m => m [(a, Log Double)] -> LogicT m a
fromWeightedList = LogicT ...

I think i’m essentially looking for m [a] -> LogicT m a, the opposite of observeAllT - not sure if this is possible.

JW: It’s possible – I’m thinking something like:

nondetermistically :: m [a] -> LogicT m a
nondetermistically mx = lift mx >>= foldr (<|>) empty . map pure

Essentially, promote mx to LogicT m [a], and then foldr (<|>) empty . map pure :: [a] -> LogicT m a.

MN: Could you explain how foldr (<|>) empty . map pure works?

JW:

The map pure part gives a list of all the nondeterminstic branches which have no computational effect:

map pure :: [a] -> [LogicT m a]

Then foldr (<|>) empty is the choice operation.

MN: I think the foldr <|> empty makes sense in terms of its type definition, but im a bit boggled by what it accomplishes.

JW: LogicT is the monad of backtracking choice it says nondeterministically pick one of the branches. The map pure says that each branch actually has no computation content – you are just nondeterministically picking a value from the [a], hence the LogicT m a. You’ll then go on to do some real work (which may involve m), with the result of this choice.

choice = foldr (<|>) empty

For example in parser terminology:

choice [string "abc", char 'a' $> "a"]

MN: Right, does this still retain all the original branches i.e. we can extract them by running observeAllT on the result?

JW: Yeah

observeAllT . nondeterministically = id

MN: This is kind of magical to me

JW: Well think of it in terms of parsers:

  map fst <$> runParserT (nondeterministically readLine) ""
= readLine

Why? Say the user inputs “abc” – then nondeterministically forms the parser:

pure 'a' <|> pure 'b' <|> pure 'c' <|> empty

Now suppose your parser is of type String -> m [(a, String)]. Then running that parser is going to return:

return [('a', ""), ('b', ""), ('c', "")]

Then just throw away that state and you get the original line.

A similar combinator is:

oneOf :: [Char] -> Parser Char
oneOf cs = foldr (<|>) empty . map char

In other words, make all the input characters into parsers that recognise those, and then try each of them in turn. If one branch matches, we are good – except when you use map pure, then all the branches will succeed, and LogicT observes all successful branches.

MN: Ahh, so folding <|> doesn’t collapse all of the branches into a non-deterministically chosen branch e.g. pure 'b' , but it combines them into the form pure 'a' <|> pure 'b' <|> pure 'c' <|> empty ?

JW: Yeah, that’s what fold do right. But the chain of <|>s create a “single” result which is nondeterministically chosen (which really means, it produces all the results and tries one after the other).

MN: And that part doesn’t actually happen until you choose to extract a result?

JW: Erm, well it happens when it happens. The choice doesn’t really happen because it took all possible choices – they are all processed in parallel as far as I’m concerned. It’s a black box.

MN: Is it correct to be able to have a function like State s a -> StateT s m a?

JW: I mean you could, but you’re basically saying that the Stateful part of that computation is completely pure, in which case it’s basically:

promoteState :: State s a -> StateT s m a
promoteState mx = StateT (\s -> return (runState mx s))

and I’m not sure that’s particularly valuable. I suppose it allows you to avoid the overhead of performing computation in m, but in the CPS form that’s not even a concern anyway because the stateful operations don’t even touch the underlying monad.

Also, see state:

promoteState :: State s a -> StateT s m a
promoteState = state . runState

It’s the inverse of runState, (assuming the State s a here is the non-CPS form).

MN: This is all stemming from the mess i’m in that i’ve got something like:

> MaybeT m a 
 which i need to turn into 
> m [Maybe a] 
 which i need to turn into
> [MaybeT m a] 

JW: That transformation isn’t possible, you can’t go from a generic monadic context and invert it. The opposite direction is easy.

MN: My bad, I meant m [MaybeT m a], so it looks vaguely like:

let mx' :: m ([Maybe a])
    mx' = fmap (:[]) $ runMaybeT mx
    foo :: MaybeT m a -> MaybeT m a
    foo = ...
in  do 
       (x : xs) <- mx' :: m [MaybeT m a]
       foo x?

JW: The function m [Maybe a] -> [MaybeT m a] is not possible in general, not unless you know how to run out m. The following is fine: m [Maybe a] -> m [MaybeT m a], but you can’t just exit m without knowing how.

MN: Hi! So I’ve got this problem which i don’t know is worth/possible solving or not. Currently, the monad bayes library has a number of modules which contain their own form of the Traced data type, commonly sharing the following structure (where Trace is a monad):

data Traced m a = Traced { ... , 
                           dist :: m (Trace a) 
                         }

and each Traced data type has a corresponding hoist function:

hoist :: (forall x. m x -> m x) -> Traced m a -> Traced m a
hoist f (Traced .. dist) = Traced .. (f dist)

Instead, I’d like to be able to use my own transformer version of Trace inside of Traced:

data Traced m a = Traced { ... ,
                           dist :: TraceT m a,
                         }

However, now I’m not sure how to redefine hoist or what type definition it should have. Do you have any thoughts on this?

JW: Well the forall x. m x -> m x implies to me that the function never touches or knows about the trace.

MN: This is true.

JW: So that’s ok. I suspect lift :: m a -> TraceT m a will be a part of it, it depends on how TraceT is defined. If it’s the non-CPS version it’s easy:

TraceT mx = TraceT (f mx)

Otherwise you just need to be a little more creative, but the general idea still applies. It doesn’t matter that the monad is carrying around tracey data, because the function works forall x.

MN: Unfortunately it’s the CPS version:

newtype TraceT m a =
  TraceT { unTraceT :: forall r. ([Double] -> a -> Log Double -> m r) -> m r}
  deriving Functor

JW: Still easy.

TraceT k = TraceT (\ds x log -> f (k ds x log))

MN: Ahhh, thank you! My previous (wrong) solution was

hoist :: (Monad m) => (forall x. m x -> m x) -> TraceT m a -> TraceT m a
hoist f mx =
  TraceT $ (\k -> do (Trace mx') <- f $ (runTraceT mx)
                     mx' k)

Even though it type-checks, it doesn’t work.

JW: I’m surprised that type checks – why does mx' take an argument? TraceT is the CPS form, the Trace that comes out of the runTraceT is not.

MN: Ooh, so mine is lol

runTraceTCPS :: Monad m => TraceTCPS m a -> m (TraceCPS a)

JW: Ok, I’d make sure your Trace is non-CPS – Trace is a data structure, the TraceT is the monad.

MN: Got you, thanks. Do you never tend to turn non-transformer monads into CPS?

JW: Yes, but in this case Trace is a proper data structure. You can have an internal TraceCPS that gets concretised into Trace, but it wouldn’t be useful. The CPS behaviour of TraceT does all the work for you, and also TraceCPS = TraceT Identity.

MN: I’ve got the following code:

newtype Coroutine s m r = Coroutine {
   resume :: m (Either (s (Coroutine s m r)) r)
   }

instance (Functor s, Monad m) => Monad (Coroutine s m) where
  t >>= f = Coroutine (resume t >>= apply f)
    where -- apply :: (a -> Coroutine s m b)
          --       -> Either (s (Coroutine s m a)) a
          --       -> m (Either (s (Coroutine s m b)) b)
          apply fc (Right x) = resume (fc x)
          apply fc (Left s)  = return (Left (fmap (>>= fc)) s))

which i’ve spent ages trying to define >>= using EitherCPS:

newtype EitherCPS e a
  = EitherCPS { unEitherCPS :: forall r. (e -> r) -> (a -> r) -> r }

newtype Coroutine s m r = Coroutine {
   resume :: m (EitherCPS (s (Coroutine s m r)) r)
   }

instance (Functor s, Monad m) => Monad (Coroutine s m) where
  t >>= f = Coroutine (resume t >>= apply f)
    where apply fc (EitherCPS k) = ???

but i don’t know if this is possible, could i check with you?

JW: Of course it is – think about the relation between the continuations and the pattern cases.

MN: I’m having a massive problem handling the resume and return, it seems like i’m getting close, but then i can’t get the types to match.

I’ll show you an attempt:

apply fc (EitherCPS k) =
    EitherCPS $ \l r -> k (l . (\s -> (fmap (>>= fc) s)))
                          (r . (\x -> (fc x)))

but then i’m not sure how to fit in resume and return from the original definition.

JW: Your issue is you haven’t cps’d Coroutine itself I believe, and when you do that you might as well inline EitherCPS straight into it.

MN: Ooh okay, i had no idea that was necessary, i’ll try giving that a go right now, thanks! I’m guessing it looks like:

newtype Coroutine s m a = Coroutine { 
  unCoroutine :: forall r. 
                 (m (EitherCPS (s (Coroutine s m a)) a) -> r)
              -> r
}

JW: I actually suspect it’s (EitherCPS s ... -> m r) -> m r

MN: Hm, this looks different from the normal translation i’m used to

JW: Nope! When I CPS:

data IdentityT m a = Identity (m a)

It becomes:

data IdentityT m a = Identity (forall r. (a -> m r) -> m r)

which is, hey presto, Cod.

MN: Ohh right! i forgot it was even a monad transformer.

MN: Hiya! I’m converting a lot of the Coroutine library to CPS, where:

-- Original Coroutine:
newtype Coroutine s m a = Coroutine { resume :: m (Either (s (Coroutine s m a)) a) }
-- CPS'd Coroutine:
newtype Coroutine' s m a = Coroutine' { resume' :: forall r. (s (Coroutine' s m a) -> m r) -> (a -> m r) -> m r }
runCoroutine' :: Monad m => Coroutine' s m a -> m (Either (s (Coroutine' s m a)) a)

But I’m finding that in a lot of functions i’m converting which involve monadic computation with m, such as:

f :: m (Either (s (Coroutine s m a)) a) 
  -> m (Either (s (Coroutine s m b)) b)
foo :: Coroutine s m a -> Coroutine s m b 
foo cort = Coroutine { f ( resume cort ) }

The CPS version i write always tends to involve me calling runCoroutine' and having to pattern match on Either:

foo cort = Coroutine' (\l r -> x <- f (runCoroutine' cort)
                               case x of
                                  Right rv -> r rv
                                  Left  lv -> l lv )

Am i doing it wrong?

JW: What is foo?

MN: Some function that just applies f to the m (Either (s (Coroutine s m a)) a) inside of Coroutine.

JW: Right but it must have a “normal” name.

MN: Shall i give you a more concrete example?

JW: Yes.

MN: Original non-CPS’d version of liftBinder:

newtype Coroutine s m a = Coroutine { resume :: m (Either (s (Coroutine s m a)) a) }

type PairBinder m = forall x y r. (x -> y -> m r) -> m x -> m y -> m r

liftBinder :: forall s m. (Functor s, Monad m) => PairBinder m -> PairBinder (Coroutine s m)
liftBinder binder f t1 t2 = Coroutine (binder combine (resume t1) (resume t2)) 
  where
   combine (Right x) (Right y) = resume (f x y)
   combine (Left s) (Right y)  = return $ Left (fmap (flip f y =<<) s)
   combine (Right x) (Left s)  = return $ Left (fmap (f x =<<) s)
   combine (Left s1) (Left s2) = return $ Left (fmap (liftBinder binder f $ suspend s1) s2)

CPS’d version of liftBinder:

newtype Coroutine' s m a = Coroutine' { resume' :: forall r. (s (Coroutine' s m a) -> m r) -> (a -> m r) -> m r }

runCoroutine' :: Monad m => Coroutine' s m a -> m (Either (s (Coroutine' s m a)) a)

type PairBinder m = forall x y r. (x -> y -> m r) -> m x -> m y -> m r

liftBinder :: forall s m. (Functor s, Monad m) => PairBinder m -> PairBinder (Coroutine' s m)
liftBinder binder f t1 t2 =
   Coroutine (\l r -> do x <- binder combine (runCoroutine' t1) (runCoroutine' t2)
                         case x of Right rv -> r rv
                                   Left  lv -> l lv)
   where
    combine (Right x) (Right y) = runCoroutine' (f x y)
    combine (Left s) (Right y)  = return $ Left (fmap (flip f y =<<) s)
    combine (Right x) (Left s)  = return $ Left (fmap (f x =<<) s)
    combine (Left s1) (Left s2) = return $ Left (fmap (liftBinder binder f $ suspend s1) s2)

JW: I think I see how to do this:

resume' t1 (\s1 -> resume' t2 (\s2 -> return (Left (fmap (liftBinder ...)) (\y -> return (Left (fmap (flip...)))))
           (\x -> resume' t2 (\s -> return (Left (fmap (f x =<< ...))) (\y -> runCoroutine' (f x y)))

Think about the four cases in terms of how each continuation can reach it – whenever you match on Either, you just use the continuations instead. P.S. there is no way that expression is well-bracketed, but you should get the picture.

MN: Oh wow, so, we don’t even have to use binder?

JW: You do. I just didn’t put it in there, it either stays on the outside, or it goes on the inside of each one. I’m not sure which, I just translated the combine application. It’s possible binder needs a different type.

MN: Oh right! So that’s combine t1 t2.

JW: Yeah

MN: That’s so awesome, i was thinking about that approach but i wasn’t sure how the cases translated to branching of continuations, thanks loads! I’ll have a try at fitting the rest in.

JW: I would probably not try and translate what I did, but use the principal. Really, you should implement a parser combinator library, it helps with this sort of thing. It’s basically 100% juggling these dual continuation structures (or in Parsecs case quad-continuation).

Minh 7:54 PM i’ve forgotten how to use RankNTypes, how does one do something like : evalDist :: Dist d => [Double] -> d evalDist (μ: σ: _) = normalDist μ σ where normalDist returns a concrete type NormalDist which is an instance of the class Dist?

Jamie Willis 8:10 PM erm 8:10 not sure what you mean

Minh 8:10 PM hm, so, i want to return a value where all i know about it is that its an instance of a certain class 8:11 but in the actual function definition, i want to be able to return different concrete types, where i know they have instances of that class 8:12 but i’m getting errors like Couldn’t match expected type ’d' with actual type ‘NormalDistribution’ ’d' is a rigid type variable bound by …

Jamie Willis 8:23 PM oh I think you want existentials 8:23 I always struggle with this stuff 8:23 but you basically want to capture the instance in the data constructor 8:24 image.png image.png

8:24 there is an example New 8:24 the SAME constructor has a positionOps instance 8:24 the instance must be present when the SAME value is made :heart: 1

8:24 and whenever we pattern match on SAME the instance is available

Minh 8:31 PM is it possible to place that constraint on the a of Defunc?

Jamie Willis 8:32 PM In a constructor sure 8:32 not on the main a at the top I don’t think no

Minh 4:10 PM is it possible to do this somehow: instance Show s => Pretty s where pretty = show For default types which don’t have a specific Pretty instance, but do have a Show instance

Jamie Willis 10:28 AM I think you can mark it as incoherent 10:28 which means it’s only chosen if there isn’t another alternative

Minh 1:43 PM i’m wondering how when works in the following example for callCC: – Returns a string depending on the length of the name parameter. – If the provided string is empty, returns an error. – Otherwise, returns a welcome message. whatsYourName :: String -> String whatsYourName name = (runCont id) $ do – 1 response <- callCC $ \exit -> do – 2 validateName name exit – 3 return $ “Welcome, " ++ name ++ “!” – 4 return response – 5 validateName name exit = do when (null name) (exit “You forgot to tell me your name!") i’m confused about the possible return values of when, and how validateName name exit can be ignored as a return value if null name is false in validateName

Jamie Willis 1:45 PM think of exit as an early return statement 1:45 and when as an if without an else

Minh 1:45 PM wouldn’t exit just be id in this case

Jamie Willis 1:45 PM I feel like you got confused about this before

Minh 1:45 PM yeah im reading over our old conversation

Jamie Willis 1:46 PM exit is return 1:46 from line 5 (edited) 1:46 I would just inline the definitions and see how they fall together 1:47 exit is essentially goto line 5 1:47 except it has a value, which becomes response

Minh 1:47 PM right, i get how it can exit early, similarly to when you have the following: do return 5 return 6 this will just return 5

Jamie Willis 1:47 PM if it’s not called then whatever was the last expression in the callCC “body” is returned 1:47 that will return 6

Minh 1:47 PM what

Jamie Willis 1:47 PM return isn’t like an imperative return 1:48 but callCC’s function is 1:48 it’s a goto 1:48 you goto whatever follows the callCC 1:48 this is why I don’t like return 1:48 I like pure for this very reason 1:49 it’s clear that do pure 5 pure 6 1:49 returns 6 1:49 and it’s identical to using return 1:49 the callCC has, in your example 1:50 created a continuation called exit with the shape \response -> return response (edited) 1:50 if you call exit at any time, your continuation is ignored 1:50 and you do exit instead New 1:50 again, just inline it and see 1:51 computations in Cont don’t return, they just go somewhere else

Minh 1:51 PM okay thanks, will do so

Jamie Willis 1:51 PM do notation just makes “go somewhere else” look like sequentiality

Minh 2:27 PM right, so inlining it looks like whatsYourName' :: String -> Cont r String whatsYourName' name = do response <- cont (\k -> runCont (do validateName name (\x -> cont (_ -> k x)) return $ “welcome, " ++ name ) k ) return response 2:27 so im guessing that the exit is always (\x -> cont (_ -> k x))

Jamie Willis 2:27 PM it is here 2:27 not in general 2:28 oh wait 2:28 no it is 2:28 I thought you’d inlined k

Minh 2:29 PM i see, so the line return $ “welcome, _” ++ name acts as the continuation _ which is ignored

Jamie Willis 2:29 PM yup

Minh 2:30 PM but otherwise, when will just return pure () New

Jamie Willis 2:31 PM sure

Minh 4:36 PM this is weird, in the following: validateName name exit = do when (null name) (exit “you forgot to tell me your name”) if when has type Bool -> f () -> f (), how does exit let us produce a type f () (edited) 4:38 assuming that exit is always (\x -> cont (_ -> k x)) New

Jamie Willis 4:39 PM look at the type of callCC 4:39 exit doesn’t return 4:39 it never produces a valid to the context that calls it 4:40 so it can return any type you want, call it b 4:40 in when’s case, that’s ()

Minh 11:31 AM I’ve got a problem that i’m not sure how to solve elegantly, i wonder if you’ve ever tried anything like this? I have a small DSL, and i want to perform a source-to-source language translation that allows me to attach a unique identifier to each current location in the program execution. But during this translation, the data type for the language must remain the same. This is like assigning a stack trace to each expression.

New

Jamie Willis 11:32 AM HasCallStack 11:32 Or StableName 11:32 I’ve used StableNames :+1: 1

Minh 11:54 AM did you find that you had to make any modifications to your language to incorporate StableNames, e.g. add an extra parameter to a constructor to store an StableName identifier ?

Jamie Willis 11:55 AM have a read of the staged selective parser combinators paper (edited) :+1: 1

Minh 12:02 PM ooh i see, so the names are held implicitly somewhere

Jamie Willis 12:53 PM sure 12:53 or you can regenerate them

12:53 they give the same name every time

Minh 12:54 PM im not sure if im understanding correctly, but do you use a hashmap to be able to resume your program from different points of execution? (edited)

Jamie Willis 12:55 PM when?

Minh 12:55 PM image.png image.png

Jamie Willis 12:55 PM I don’t “resume” anything there 12:55 I’m tracking them 12:56 I keep the Map from StableNames to Ints 12:56 later 12:56 I reference them by their Ints

Minh 12:56 PM right, is it possible to perform that functionality though 12:56 through what you’ve done

Jamie Willis 12:56 PM then I have a dependent Map from Int to Functions 12:57 and later when I see Call n I can run the function at mus DMap.! n 12:57 that’s not in the paper though

Minh 12:57 PM ooh i see, interesting 12:57 is there is a reason why you didn’t use a map directly from stable names to their function

Jamie Willis 12:58 PM a) Stable names require IO around 12:58 I wanted to get rid of that quickly 12:58 b) the entire tree is transformed multiple times, the StableNames wouldn’t be right anymore by the end :+1: 1

New 12:58 they are right at the beginning though :+1: 1

Minh 12:38 PM Hi, im wondering about how to correctly evaluate the following example: g = let x = 5 f = \y -> y + x x = 10 h f = \a -> f a in h f 15 At line 2, i’m assuming we’ve previously evaluated f to a closure with an environment {x → 5} . However, the environment when evaluating h f 15 would be {x → 10} . When merging the two environments at h f 15, is it correct to say that the current environment takes precedence over the closure’s environment?

Jamie Willis 12:39 PM I think it’s {x → 5} 12:39 but I would just test it

Minh 12:39 PM it isn’t haskell im doing it in, its just my own language 12:39 so i’m wondering about whether this is a design choice 12:39 or if there’s a single correct way

Jamie Willis 12:40 PM I would check other languages 12:40 I think it boils down to by-name evaluation or not :+1: 1

12:40 hard to tell 12:40 also, don’t forget: you don’t have to work weekends as a PhD student :slightly_smiling_face:

Minh 2:58 PM is there a way to use the Cont monad to both exit early with a value (using callCC) as well as return the rest of the execution that wasn’t carried out

New

Jamie Willis 2:58 PM two callCCs? 2:59 restOfWork <- callCC (\exit -> … leave exit) where leave = callCC (\rest -> exit rest) 3:00 that implies the type of restOfWork is itself a continuation 3:00 it’s the sort of thing you can do when you want to implement co-operative multi-tasking

Minh 10:43 AM I’ve been trying to use the Cont monad with callCC to return the rest of computation to be resumed later, similar to how Coroutine (i.e. the free monad) works with yield or await . (This is just me trying to sanity check whether this is possible). I’ve also tried your approach of using two callCCs , but all i’m able to do so far is exit the computation early. Have i misunderstood what’s possible using the Cont monad? (edited)

Jamie Willis 10:43 AM you will exit the computation early, if you don’t put the continutation somewhere 10:44 you need to store then if you want the yield behaviour

Minh 10:45 AM could you elaborate on how one “puts the continuation somewhere”?

Jamie Willis 10:45 AM in a list? 10:45 i.e. 10:45 StateT [Thread] (Cont …) 10:46 yield does a callCC, puts the continuation in the state, and then calls another continuation from that state

Minh 10:47 AM ah right, so i’m only able to store/capture the computation that is inside callCC?

Jamie Willis 10:47 AM yup 10:48 callCC (\k -> storeAndRecall k) (edited) 10:48 something like that

Minh 10:58 AM right, i’m not sure i understand how to use that. If i had an interpreter eval :: Expr -> Val that needed to pause at certain places, i would do callCC (\k -> eval k expr) somehow? New

Jamie Willis 11:09 AM it would be something like 11:09 you make the yield operation 11:10 and first you load all of the coroutines into the list 11:10 (if you are using await to spawn off, then that’s how they make it into the list) 11:10 and then you schedule one of them 11:10 it starts running, when it yields it takes the remainder of the continuation, pops it into the list, and then schedules another continuation in the list 11:11 cast your mind all the way back to the cooperative multithreading in the OS coursework in second year 11:11 you’re basically context-switching in and out continuations

Minh 11:11 AM thanks a lot, i’ll give this a go

I’m experimenting with GADTs to create an embedded DSL. It appears that the following definition of lambda functions can only support functions of one argument, so we have to nest lambdas to achieve multi-parameter functions. data Expr t where Lam :: (Expr a -> Expr b) -> Expr (a -> b) exampleFn :: Expr (Int -> Int -> Int) exampleFn = Lam (\a -> Lam (\b -> a)) Is there a way to achieve this without having to nest lambdas?

Jamie Willis 1:35 PM Heterogenous lists New 1:36 Lam :: (ExprList as -> Expr b) -> Expr (HigherArity as b) 1:37 type family HigherArity (as :: [*]) (b :: *) :: * where HigherArity ‘[] b = b HigherArity (a ‘: as) b = a -> HigherArity as b

Minh 1:37 PM wow this looks freaky

Jamie Willis 1:38 PM data ExprList (as :: [*]) where ExprNil :: ExprList ‘[] ExprCons :: Expr a -> ExprList as -> ExprList (a ‘: as) 1:38 {-# LANGUAGE DataKinds #-}

Minh 1:38 PM thanks i’ll try this out! :slightly_smiling_face: