Debugging unwanted strictness?

Question

I have a problem that I don't know how to reason about. I was just about to ask if somebody could help me with the specific problem, but it dawned on me that I could ask a more general question and hopefully get a better general understanding as a result. Hopefully. So here goes:

It's usually obvious enough when your program is too lazy, because you end up with glaring issues like space leaks, for example. I have the opposite problem: my program is too strict. I am trying to tie knots, and find that certain things I attempt to do will somehow defeat the laziness I need. So my general question is, how does one debug unwanted strictness?

---

For completeness, here's my specific case: I'm in RWS, where the writer component populates a map, and the reader component observes the final state of that map. I can't do anything strict with this map before I've finished populating it. It appears to be no problem to look up values in the map, like:

do
  m <- ask
  val <- m ! key
  doSomething val -- etc.

But (!) fails using error, where I'd instead prefer to fail using my monad's fail. So I'd like to do something like the following:

do
  m <- ask
  maybe
    (fail "oh noes")
    (doSomething)
    (lookup key m)

This causes my program to <<loop>>, which I don't understand. It doesn't seem to me like this should be any more strict than using (!), but obviously I'm wrong...

Answer 1

Your first example is strict in the map. The following looks up print "1", then runs it, and the program actually prints 1. Of course, that requires evaluating m.

main = do let m = Map.fromList [(1, print "1")]
          val <- m ! 1
          return val

You probably meant to write something that only reads the map. The following is not strict, since val is not used in a case expression.

main = do let m = Map.fromList [(1, print "1")]
          let val = m ! 1
          return val

Your second example is strict because it checks whether the result of lookup succeeded in order to decide how to finish executing the do-block. That requires reading the map. It's equivalent to:

do m <- ask
   case lookup key m of
     Nothing -> fail "oh noes"
     Just x  -> doSomething x 

Debugging strictness problems

Evaluation is always forced by a case expression or by some built-in operators like + for integers. If you suspect that your program is failing because a value is forced before it's available, you will want to find out which value is being forced and where it is being forced.

Which value was forced?

In this kind of bug, the program attempts to evaluate an expression that depends on the result of its own evaluation. You can use trace to track down which expression is being evaluated. In this problem, it looks like the value of m is being forced, so use trace to print a message just before it is evaluated:

do m1 <- ask
   let m = trace "Using m" m1
   ...

If "Using m" is the last output from your program (before the <<loop>>), you're getting closer to the bug. If it's not in the output, then m isn't being evaluated, so the problem is elsewhere. If something follows this line in the output, then the program continued executing and an error occurred later, so the problem must be somewhere else.

Where was it forced?

This tells you that evaluation got at least this far before stopping. But how far did it go? Did the problem actually happen much later? To see that, try putting a trace on something that gets evaluated later. We know that m is evaluated in order to decide which branch of maybe runs, so we can put trace at those points.

do m1 <- ask
   let m = trace "Using m" m1
   maybe (trace "Used m" $ fail "oh noes")
         (\x -> trace "Used m" $ doSomething x)
         (lookup key m)

If you see "Using m" followed by "Used m" in the output, then you know that evaluation of m finished and the program kept going. If you see "Using m" only, then the program stopped between these points. In this particular case, you should not see "Used m", because maybe forces evaulation of m and causes a <<loop>>.