5

为了生成 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)

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

这是我尝试过的：

  • 增加一个全局计数器。=> Haskell 不允许 IO monad 之外的全局状态。
  • 使用State单子。=> 我研究了一些例子，但不明白如何将它们集成到我现有的X86monad 中。
  • 跟踪单子外的柜台。=> 我宁愿计数器在“幕后”更新；否则，许多不使用标签的代码模板将需要手动传播计数器。
4

3 回答 3

8

我们可以使用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.
于 2018-03-27T02:47:00.103 回答
4

您可能想使用这个 monad 堆栈：

type X86 a = StateT Integer (Writer String) a

由于您有一个状态和一个作家，您还可以考虑使用RWS(reader-writer-state all in one)：

type X86 a = RWS () String Integer a

让我们选择第一个好玩。我首先定义一个辅助函数来增加计数器（单子不能合法地“自动”增加一个计数器）：

instr :: X86 a -> X86 a
instr i = do
    x <- i
    modify (+1)
    return x

然后你可以定义jmp为：

jmp :: String -> X86 ()
jmp l = instr $ do
    lift (tell ("jmp " ++ l ++ ";\n"))
       -- 'tell' is one of Writer's operations, and then we 'lift'
       -- it into StateT

（do有多余的，但我怀疑会有一种以 开始指令定义的模式instr $ do）

我不会为此推出我自己的 monad —— 这样做可能很有启发性，但我认为使用标准库来实现这一点会更有用。

于 2018-03-27T02:47:34.487 回答
3

正如您现在可能从其他答案中理解的那样，您的方法的问题在于，即使您使用计数器，您仍然在本地生成标签。尤其是

label1 <- allocateUniqueLabel
label label1

相当于

X86 { code = "Label1:\n", counter = 1, value = const () }

我们需要首先组装整个代码，生成标签，然后（在某种意义上）使用标签生成实际代码。这就是其他答案通过将计数器存储在State(or RWS) monad 中所暗示的。

我们还可以解决另一个问题：您希望能够向前和向后跳跃。这很可能是您拥有单独的 allocateUniqueLabel和label功能的原因。但这允许两次设置相同的标签。

实际上可以使用do带有“向后”绑定的符号使用 MonadFix，它定义了这个单子操作：

mfix :: (a -> m a) -> m a

由于两者State都有RWS实例MonadFix，我们确实可以编写如下代码：

{-# LANGUAGE GeneralizedNewtypeDeriving, RecursiveDo #-}
module X86
    ( X86()
    , runX86
    , label
    , jmp
    ) where

import Control.Monad.RWS

-- In production code it'll be much faster if we replace String with
-- ByteString.
newtype X86 a = X86 (RWS () String Int a)
    deriving (Functor, Applicative, Monad, MonadFix)

runX86 :: X86 a -> String
runX86 (X86 k) = snd (execRWS k () 1)

newtype Label = Label { getLabel :: String }

label :: X86 Label
label = X86 $ do
    counter <- get
    let l = "Label" ++ show counter
    tell (l ++ ":\n")
    modify (+1)
    return (Label l)

jmp :: Label -> X86 ()
jmp (Label l) = X86 . tell $ "jmp " ++ l ++ ";\n"

并像这样使用它：

example :: X86 ()
example = do
    rec l1 <- label
        jmp l2
        l2 <- label
    jmp l1

有几点需要注意：

  • 我们需要使用RecursiveDo扩展来启用rec关键字。
  • 关键字rec界定了一个相互递归的定义块。在我们的例子中，它也可以稍后开始一行（rec jmp l2）。然后 GHC 将其转换为mfix内部使用。（使用 deprecatedmdo关键字代替rec 会使代码更自然一些。）

  • 我们将内部封装在新类型中X86。首先隐藏内部实现总是好的，它允许以后轻松重构。其次，mfix 要求传递给它的函数a -> m a的参数不严格。效果不能依赖于参数，否则会mfix 发散。这是我们的函数满足条件，但如果内部暴露，有人可以定义一个人为的函数，如下所示：

    -- | Reset the counter to the specified label.
evilReset :: Label -> X86 ()
evilReset = X86 . put . read . drop 5 . getLabel

    不仅破坏了标签的唯一性，还会导致下面的代码挂掉：

    diverge :: X86 ()
diverge = do
    rec evilReset l2
        l2 <- label
    return ()

另一个非常相似的替代方法是使用 Rand monad 并 Random 使用 UUID. 类似的东西WriterT String Rand a，它也有一个MonadFix实例。

（从纯粹的学术角度来看，可以构造一个箭头而不是一个 monad，这将实现 ArrowLoop，但不允许依赖于值的状态修改，例如 in evilReset。但是封装X86实现了相同的目标，保持了更友好的do语法。 )

于 2018-03-31T04:45:25.547 回答