2

I have a problem regarding a debugging function. I'm supposed to define the execution of certain commands which are down below and then I have to create a debug function which recursively prints out the current memory values after each execution is called.

Heres my code for exec (execution), debug and the data types

data Com = Ass Char Exp 
         | While Exp Com 
         | Seq Com Com
           deriving Show

exec :: Memory -> Com -> Memory
exec m (Ass c e) = update m (c, (eval m e))
exec m (While e c) = if (eval m e) == 0 then m
                     else exec (exec m c) (While e c)
exec m (Seq c1 c2) = exec (exec m c1) c2


debug :: Memory -> Com -> [Memory]
debug m (Ass c e) = update m (c, (eval m e)) : [m]
debug m (Seq c1 c2) = (exec (exec m c1) c2) :[m]
debug m (While e c) = if (eval m e) == 0 then [m]
                      else (exec (exec m c) (While e c)) : [m]

com1 :: Com
com1 =  Seq (Ass 'z' (Num 1))       
        (While (Var 'y') (Seq (Ass 'z' (Mul (Var 'z') (Var 'y')))
                              (Ass 'y' (Add (Var 'y') (Num (-1))))))

When I run the function onto certain memory states and commands it only prints out the starting memory and the terminated memory for example if I run debug [('y',4)] com1 all I get is [[('y',0),('z',24)],[('y',4)]] whereas I need it to print

  [('y',4)]
  [('y',4),('z',1)]
  [('y',4),('z',4)]
  [('y',3),('z',4)]
  [('y',3),('z',12)]
  [('y',2),('z',12)]
  [('y',2),('z',24)]
  [('y',1),('z',24)]
  [('y',1),('z',24)]
  [('y',0),('z',24)]

The question I want to ask what do I need to change in my debug function to get it to print recursively?

3 Answers 3

6

Comparing your exec and debug functions, we can see why your debug doesn't print out all intermediate states: it just takes the state returned by exec and attaches it to the original memory state m.

Since exec doesn't save the intermediate memory states and since the debug is basically exec already, I suggest just rewriting debug to call itself recursively instead of exec. Also, let's change the return type of debug to be ([Memory], Memory) -- the first component will be the list of all previous states, and the second will be the most recent result. (Strictly speaking, since the most recent result is part of the history, this isn't needed, but it will help keep our code cleaner, and is more general -- we could easily change debug to keep something other than the memory history, such as a log of operations performed.)

Anyway, we get something like this:

debug :: Memory -> Com -> ([Memory], Memory)
debug m (Ass c e)   = ([m'],m')
  where m' = update m (c, eval m e)

I'll leave the rest to you -- it's not too difficult.

This isn't too bad. However, there are still a few problems:

  • The finished program will certainly use ++, which is a bit frightening -- we could easily end up with a program taking time quadratic in the length of the log (for instance, if our log were written in reverse chronological order, we would repeatedly append the early states to the end of a long list).
  • We've basically duplicated (and slightly uglified) the original exec.

The program above is a typical example of the functional programming "pattern" known as threading the state, where we add some information to the return type of function calls to store information about the history of our program. You can actually think of this program as threading two types of state: the memory, which we both examine and modify, and the log, which we only write to but never read.

Of course, functional programming is all about abstraction, and there are well-known ways to solve the above problems and eliminate the "threading" pattern: monads!

You can use the Writer monad to eliminate the explicit threading of the log.

Bonus: you can use the state monad and use it to eliminate the explicit threading of the memory state.

You can use difference lists to eliminate potentially expensive use of ++.

To learn about all of these topics, I recommend the penultimate chapter of Learn You a Haskell, after which you should be able to use the monads defined in the standard libraries.

2

Your debug function is calling exec (which doesn't do any logging). Instead you want it to call debug recursively.

This is a good opportunity to learn about the Writer monad which is useful for "computations which produce a stream of data in addition to the computed values."

1

This may be overkill, but anyway...

First of all, I'd put this in the state monad so it's clear to see what you're doing.

type MemState a = State Memory a
type EvalVal = ... -- result of eval


  -- You'd better define those two right /instead/ of 'eval' and 'update'
eval' :: Exp -> MemState EvalVal
eval' e = state $ \m -> (eval m e, m)
update' :: Char -> EvalVal -> MemState ()
update' c v = state $ \m -> ((), update m (c, v))

exec :: Com -> MemState ()
exec (Ass c e)   = eval' e >>= update' c
exec whileCom@(While e c) = do
        v <- eval'
        when (v /= 0) $ do
           exec c
           exec whileCom
exec (Seq c1 c2) = do
        exec c1
        exec c2

Now, as user5402 already suggested, debugging can be done by adding a Writer:

type DebugState a = WriterT [Memory] MemState a

tellMemory :: DebugState ()
tellMemory = do
     m <- lift . state $ \m' -> (m',m')
     tell [m]

debug :: Com -> DebugState ()
debug com@(Ass _ _) = do
         tellMemory
         lift $ exec com
         tellMemory
debug (Seq c1 c2) = do
         tellMemory
         debug c1
         debug c2
debug com@(While e c) = do
         tellMemory
         v <- lift eval'
         when (v /= 0) $ do
            debug c
            debug com

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.