monad thinking process

[Theodore Norvell]

Cagdas Ozgenc wrote:
> 
> Greetings.
> 
> I have very little experience with monads. However my first impression is
> that there is too much thinking process involved in programming with monads,
> and it is very time consuming, at least for a beginner like myself. I don't
> know how productivity changes once you get used to programming with them.
> Also, I have serious concerns about the maintenance of programs written in
> monadic style. Since there is too much plannning overhead, it doesn't seem
> suitable for evolutionary software development process.
> 
> What do monad experts think? What do you think of code readability? How easy
> is it to prove that programs written with monads are correct? How does
> changing one function affect other functions, in terms of maintenance?

This is an interesting point of view, since the main point in favour
of using Monads for me has been the increase in maintainability.

Well I'm not a Monad expert.  But I have used them extensively in
a Haskell program of a few thousand lines written _and_maintained_ by me
and my grad students. I should say that this program was essentially
imperative and consisted of traversing one graph to create another graph
and then performing a number of in-place transformations on the output graph.
So the state consisted mostly of the output graph.  Of course we could have
solved the problem nonimperatively, but early on I made the decision to
write the program imperatively.  Given this decision, monads are really the
best option.  Suppose you have a function that manipulates the state: say

	f s = let a = g s
                  s' = h a s
                  s'' = i a s'
                  b = j s''
               in k s'' b

Now you want to insert a computation step between i and j.  I can write
	
	f s = let a = g s
                  s' = h a s
                  s'' = i a s'
                  s''' = m s'' <-- new line
                  b = j s'''    <-- changed line
               in k s''' b        <-- changed line

With a state Monad the code is first off more readable (an important factor
in maintainability) and, since the plumbing is encapsulated in the Monad, it
is easier to change.  Even more importantly, it is harder to make the
wrong change.

           f = do   a <- g
                    h a
                    i a
                    m         <-- new line
                    b <- j
                    return k b

The other side of the maintenance question comes up when you want to change
how data is passed.  I started out this project with a lazy state
monad (in my defence, this was originally in Gofer, and I'm not sure if all the
strictness features that Haskell has were available).  Anyway it was soon apparent
that space was a problem, so after translating to Haskell, did my best to make the
state monad strict.  This affected only the monad, the declaration of the state type,
and the low-level state manipulation functions.  In the nonmodadic example we might
write
	f s = let a = seq s $g s
                  s' =  h a s
                  s'' = seq s' $ i a s'
                  b = seq s'' $ j s''
               in k s'' b

Also it took me a few tries to get the Monad the way I wanted it. I would make
a change, profile, make another change, and so on. Had I had to change the client
code every time, I changed the way I wanted the state passed, it would have been
unfeasible.

Suppose that at some point in development you realize that you might need to
stop the computation because an error was detected.  With a Monad, I can simply
change the Monad and the modification to the code is something like this:

           f = do   a <- g
                    assert (a /= 0) "Error: ..."  <-- new line
                    h a
                    i a
                    b <- j
                    return k b

For the unmonadic version, the change to f isn't bad (still not as nice as
the monadic version), but the type of f changes to allow for an error
return and so every caller of f changes and every caller of every caller
of f changes and so forth.

At one point in my project, I decided that (for efficiency reasons, mostly)
I wanted to be able to do output on the fly (my early version had accumulated
a string -- hidden in the monad). This change was accomplished simply by a
change to the Monad to compose the state monad I had been using with
Haskell's built-in IO Monad (see my recent post on that subject).
No client code had to change.

So for code that is conceived and written in terms of changes to state,
Monads are clearly the way to go. They make maintenance much easier, both
for local changes to the client code and for global changes to how you want
the state passed around. But you might argue that I should have written my
program in a "functional" rather than an "imperative" style.  I think if I
had done that, there would have been a lot of variables representing 
partially constructed graphs and a lot of code that put these pieces together.
Furthermore, I think that the space performance might have been far less controllable.
It's not that my particular problem was inherently sequential, but rather that
any way you do it, there is a lot of plumbing and Monads provide one nice
way to hide the plumbing.

I haven't addressed the question of proving programs correct.  In my example
program, it really wouldn't have been feasible, owing to size considerations.

Functional programmers sometimes forget that while it is possible to prove
functional programs correct, it is also possible to prove imperative programs
correct.  In fact you sometimes see statements like "functional programs
can be proven correct by equational reasoning, imperative programs can't, so 
functional programming is better".  Monads show that (some) imperative programs _are_
functional programs and so show this reasoning to be fallacious.  However,
it may be that equational reasoning is not the best way to reason about
Monadic functional programs. For example, for functional programs 
using a state Monad, methods such as Hoare logic, weakest preconditions,
or predicative programming, might be more effective. 

Cheers,
Theodore Norvell

----------------------------
Dr. Theodore Norvell                                           theo@engr.mun.ca
Electrical and Computer Engineering                http://www.engr.mun.ca/~theo
Engineering and Applied Science
Memorial University of Newfoundland
St. John's, NF, Canada, A1B 3X5

Currently visiting the Department of Computer Science and ICICS at the
University of British Columbia. See my web page for contact details.