haskell - 在 Haskell do-notation 中生成唯一值

Question

为了生成 x86 汇编代码，我定义了一个名为 X86 的自定义类型。 :

data X86 a = X86 { code :: String, counter :: Integer, value :: (X86 a -> a) }

这种类型在 do-notation 中使用，如下所示。这使得编写用于生成 if 语句、for 循环等的模板变得很容易......

generateCode :: X86 ()
generateCode = do
  label1 <- allocateUniqueLabel
  label2 <- allocateUniqueLabel
  jmp label1
  label label1
  jmp label2
  label label2

指令定义如下:

jmp :: String -> X86 ()
jmp l = X86 { code = "jmp " ++ l ++ ";\n", counter = 0, value = const () }

label :: String -> X86 ()
label l = X86 { code = l ++ ":\n", counter = 0, value = const () }

完成的汇编文件打印如下:

printAsm :: X86 a -> String
printAsm X86{code=code} = code

main = do
  putStrLn (printAsm generateCode)

我实现了 X86 monad 以下列方式。本质上，序列运算符按顺序连接汇编代码块并确保计数器递增。

instance Monad X86 where
  x >> y = X86 { code = code x ++ code y, counter = counter x + counter y, value = value y }
  x >>= f = x >> y
    where y = f (value x x)

问题是标签没有正确增加，所以它们不是唯一的!以下是输出:

jmp Label1;
Label1:
jmp Label1;
Label1:

我希望输出对每个标签都有一个唯一的值:

jmp Label1;
Label1:
jmp Label2;
Label2:

为了完成这个例子，这里是 allocatedUniqueLabel 的实现。功能:

allocateUniqueId :: X86 Integer
allocateUniqueId = X86 { code = "", counter = 1, value = counter }

allocateUniqueLabel :: X86 String
allocateUniqueLabel = do
  id <- allocateUniqueId
  return ("Label" ++ show id)

如何修复我的 X86 monad 所以标签是独一无二的？

这是我尝试过的:

增加一个全局计数器。 => Haskell 不允许 IO monad 之外的全局状态。

使用 State单子(monad)。 => 我查看了一些示例，但不明白如何将它们集成到我现有的 X86 中单子(monad)。

跟踪单子(monad)外的柜台。 => 我宁愿计数器在“幕后”更新；否则，许多不使用标签的代码模板将需要手动传播计数器。

Answer 1

我们可以使用mtl classes将 X86 代码描述为有效的程序。我们想要:

要生成代码，这是 Writer影响;

维护一个计数器，这是一个 State影响。

我们担心最后实例化这些效果，在我们使用的程序的描述中 MonadWriter和 MonadState约束。

import Control.Monad.State  -- mtl
import Control.Monad.Writer

分配一个新的标识符会增加计数器，而不生成任何代码。这仅使用 State影响。

type Id = Integer

allocateUniqueLabel :: MonadState Id m => m String
allocateUniqueLabel = do
  i <- get
  put (i+1)  -- increment
  return ("Label" ++ show (i+1))

当然，我们有生成代码的操作，不需要关心当前状态。所以他们使用 Writer影响。

jmp :: MonadWriter String m => String -> m ()
jmp l = tell ("jmp " ++ l ++ ";\n")

label :: MonadWriter String m => String -> m ()
label l = tell (l ++ ":\n")

实际程序看起来与原始程序相同，但具有更通用的类型。

generateCode :: (MonadState Id m, MonadWriter String m) => m ()
generateCode = do
  label1 <- allocateUniqueLabel
  label2 <- allocateUniqueLabel
  jmp label1
  label label1
  jmp label2
  label label2

当我们运行这个程序时，效果会被实例化，这里使用 runWriterT/ runWriter和 runStateT/ runState (顺序无关紧要，这两个影响通勤)。

type X86 = WriterT String (State Id)

runX86 :: X86 () -> String
runX86 gen = evalState (execWriterT gen) 1 -- start counting from 1
-- evalState and execWriterT are wrappers around `runStateT` and `runWriterT`:
-- - execWriterT: discards the result (of type ()), only keeping the generated code.
-- - evalState: discards the final state, only keeping the generated code,
--   and does some unwrapping after there are no effects to handle.