2

我有一个关于调试功能的问题。我应该定义下面某些命令的执行，然后我必须创建一个调试函数，该函数在每次执行被调用后递归地打印出当前的内存值。

这是我的 exec（执行）、调试和数据类型的代码

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))))))

当我在某些内存状态和命令上运行该函数时，它只打印出起始内存和终止内存，例如，如果我运行debug [('y',4)] com1我得到的只是[[('y',0),('z',24)],[('y',4)]]而我需要它来打印

  [('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)]

我想问的问题是我需要在调试功能中进行哪些更改才能使其递归打印？

4

3 回答 3

6

比较你的exec和debug函数，我们可以看到为什么你debug没有打印出所有中间状态：它只是获取返回的状态exec并将其附加到原始内存状态m。

由于exec不保存中间内存状态并且debug基本上exec已经存在，我建议只重写debug以递归调用自身而不是exec. 另外，让我们将返回类型更改debug为([Memory], Memory)- 第一个组件将是所有先前状态的列表，第二个将是最近的结果。（严格来说，由于最近的结果是历史的一部分，所以这不是必需的，但它有助于保持我们的代码更干净，并且更通用——我们可以很容易地更改debug以保留除内存历史之外的其他内容，例如作为执行操作的日志。）

无论如何，我们得到这样的东西：

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

我会把剩下的留给你——这并不难。

这还不错。但是，仍然存在一些问题：

  • 完成的程序肯定会使用++，这有点吓人——我们很容易得到一个程序在日志长度上花费时间的二次方（例如，如果我们的日志是按时间倒序编写的，我们会重复附加早期的州到一长串的末尾）。
  • 我们基本上复制了（并且稍微丑化了）原来的exec.

上面的程序是函数式编程“模式”的典型示例，称为线程状态，我们在函数调用的返回类型中添加了一些信息，以存储有关我们程序历史的信息。您实际上可以将此程序视为线程化两种类型的状态：我们检查和修改的内存和我们只写入但从不读取的日志。

当然，函数式编程都是关于抽象的，有众所周知的方法可以解决上述问题并消除“线程”模式：monads！

您可以使用Writer monad来消除日志的显式线程。

奖励：您可以使用状态单子并使用它来消除内存状态的显式线程。

您可以使用差异列表来消除潜在的昂贵使用++.

要了解所有这些主题，我推荐倒数第二章 Learn You a Haskell，之后您应该能够使用标准库中定义的 monad。

于 2012-12-10T05:52:11.293 回答
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."

于 2012-12-10T05:23:57.140 回答
1

这可能有点矫枉过正，但无论如何......

首先，我会把它放在 state monad 中，这样就可以清楚地看到你在做什么。

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

现在，正如 user5402 已经建议的那样，可以通过添加一个来进行调试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
于 2012-12-10T05:54:01.080 回答