在Haskell标记中生成唯一值

Question

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

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

此类型用于如下所示的标记.这样可以轻松编写用于生成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)

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

这是我尝试过的:

• 增加全球反击.=> Haskell不能安全地允许IO monad之外的全局状态.
• 使用Statemonad.=>我已经研究了很多例子,但是不明白如何将它们集成到我现有的X86monad中.
• 跟踪monad外的计数器.=>我宁愿在"幕后"更新计数器; 否则,许多不使用标签的代码模板需要手动传播计数器.

Answer 1

我们可以使用mtl类将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.