Desugaring the State (Transformer) Monad Part I

Why is learning Monads difficult?

One of the things Haskell is most famous for are monads.
There is a page on the Haskell wiki https://wiki.haskell.org/Monad_tutorials_timeline#year_2015 where a lot of Monad
tutorials a listed. So it seems that understanding monads is somehow difficult. Why is this the case?

There is this great ebook of Stephen Diehl called “What I wish I Knew When Learning Haskell” http://dev.stephendiehl.com/hask/.
Inside the monads chapter he asked the question what makes monads so difficult when
first learning Haskell and he makes three assumptions:

  1. There are several levels on indirection with desugaring
  2. Asymmetric binary infix operators for higher order functions are not common in other langugaes
  3. Ad-hoc polymorphism is not commonplace in other languages

And he suggested what he called the “Eightfold Path to Monad Satori”, the way to understand Monads.

  1. Don’t read the monad tutorials
  2. No really, don’t read the monad tutorials
  3. Learn about the Haskell types
  4. Learn about what a typeclass is
  5. Read the Typeclassopedia
  6. Read the monad definitions
  7. Use the monad in real code
  8. Don’t write monad-analogy tutorials

What this blog post series is about

In this blog post, I will not try to explain what a monad is or what it is not.
Actually all you can do with monads is possible to do also without monads excepting IO.
IO must be done inside the IO Monad, but this is a decision of the language designers from Haskell,
so it does not mean that a functional programming lanugage has to do their IO inside the IO Monad.

Level of Abstraction

I think abstractions playing a crucial role in explaining and understanding things.
An expert has a higher level of abstraction and if he tries to explain something
to some one who is not an expert, he must take care that he uses the right level of abstraction
so that the other person can understand his explanations.
If he try to explain it the same way as he would explain to another expert, this will usually fail because
the other person does not have the same level of knowledge and abstraction as he.

The same applies to Haskell, as Haskell has a high level of abstraction inside it, which makes
Haskell a lot harder to understand for the most people as other programming languages.
If we go on a lower level of abstraction and look around, we may see the pattern
that the abstraction of the higher level tries to hide, and our understanding may be get better.

In this post I will start with a small example of the State Monad, and then desugar it step for step
to bring it to a lower abstraction level.
That means after the desugaring is finished, we wont have monadic elements like (<<, <<=, return, etc.) in
the code.

Some important things

Understanding the Implementation of Typeclasses

The term Monad is somewhat misleading. A better definition would be that a datatype (newtype) has an
instance of the Monad typeclass.
Typeclasses are used in Haskell to implement ad hoc polymorphism, which can be thought of as
operator overloading. One thing, as pointed out in Stephen Diehl’s ebook, which you cant see in the source code
is how typeclasses are actually implemented. They are implemented by implicity passing a dictionary.

For example:

m >>= k

-- If we make the dictionary explicit and order it vertically it would be:
>>= 
dict 
m 
k

The dictionary will contain the implementation of the >>= operator.

GHC Pipeline

The job of the Glasgow Haskell Compiler is to create machine code from your source code.
As other compilers does too, it uses a pipeline for this. A simplified version of the pipleline looks like this:
SourceCode -> Lexer -> Parser -> AST -> Core -> STG -> C– -> MachineCode
which implies the directions from
Abstraction -> more concrete
smaller code size -> larger code size

If you want know more about the GHC Pipeline, here is an article written by Simon Marlow and Simon Peyton-Jones
http://www.aosabook.org/en/ghc.html,
also there is a very interesting blog post which shows how the source code of a factorial function
is transformed till the corresponding machine code is generated
http://blog.ezyang.com/2011/04/tracing-the-compilation-of-hello-factorial/

  • Core

    Starting with the source code the compiler will transform it in other intermediates languages
    (like Core, STG, C–). In the last step machine code is generated.

    We will have a look at the core output.
    Core is a tiny functional language, which is quite human readable and if you read it
    you can gain more insights in what is going on under the hood.

    If you want to learn more about core, here is a stackoverflow post containing a lot of links:
    https://stackoverflow.com/questions/6121146/reading-ghc-core.
    Also in the other links mentioned regarding the GHC Pipeline,
    http://www.aosabook.org/en/ghc.html there is also a part about Core.

Monad Transformers

Till sometime ago, the state monad was implemeted as solely the state monad but this has changed.
The state monad now is implemented as an combination of StateT and the identity monad.
As the name identity monad suggest, it is like a dummy monad doing nothing.
As an side effect, this blog post also gives you some insights into monad transformers.

  • Why do we need monad transformers?

    It is possible to combine for example two arbritary functors yielding a new functor.
    With two arbitrary monads, this is not possible. Combining two monads is possible
    with monad transformers. They fix one monad, so that we have one arbitary monad.
    The fixed monad is the transformer monad, for example StateT where the
    T stands for Transformer. The Transformer monad is also called outer monad, the other monad is called “inner monad”.

    If we look at the definition of the StateT

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

    we see that we have the runStateT function which when applied to a StateT type give us a
    s -> m (a, s) function, where m is the “inner monad”.

    If you want to learn more about monad transformers, I can recommend you
    the chapters 25 and 26 from the book “Haskell Programming from first principles”.

Getting the core output

GHC has a lot of compiler flags. For a complete list look at this link:
Interesting are the compiler debugging options:
https://downloads.haskell.org/~ghc/8.4.1/docs/html/users_guide/debugging.html#options-debugging
which can be used to print out different artefacts from the GHC Pipeline.

Unoptimized

We can get the unoptimized core output in ghci via:
stack ghci –ghci-options -dsuppress-all –ghci-options -ddump-simpl Main.hs
The -dsupress-all supresses a lot of output we may not be interested it, to make the core output more readable.
The -ddump-simpl says that the Core output should be shown.

Optimized

If we want the optimized core output we can not get it via ghci, so we have to compile it.
The -O flag is the optimisation flag. If we compiled it once via
stack exec ghc – -ddump-simpl -dsuppress-all -O2 Main.hs
we do not get the output again if we compile it one time more.
First we have to delete the Main.hi, Main.o and Main file.
There may also be a switch for this in the GHC compiler flags so that you dont have to delete the files.
We can write a little script which does this for us containing:
rm Main.hi
rm Main.o
rm Main
stack exec ghc – -ddump-simpl -dsuppress-all Main.hs

Colored Output

There is also a package on hackage, ghc-core, which can give you colored output, but
with that you can only use a tiny set of compiler flags.

Leave a Reply

Your email address will not be published. Required fields are marked *