在Haskell标记中生成唯一值-Java 学习之路

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

如何修复 X86 monad以使标签独一无二？

Here is what I've tried:

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

3 回答

我们可以使用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 Id
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.

回复于 2024-04-26T02:12:19+08:00

4
您可能想要使用此monad堆栈：
```
type X86 a = StateT Integer (Writer String) a
```
既然你有一个州和一个作家，你也可以考虑使用 RWS （读者 - 作家 - 状态一体化）：
```
type X86 a = RWS () String Integer a
```
设's pick the first one for fun. I' d首先定义一个辅助函数来递增计数器（monads cannot lawfully increment a counter "automatically"）：
```
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 - 这样做可能很有启发性，但我认为使用标准库可以获得更多里程 .
回复于 2024-04-26T02:12:19+08:00
6
正如您现在可能从其他答案中看到的那样，您的方法存在的问题是，即使您使用的是计数器，您仍然在本地生成标签 . 特别是
```
label1 <- allocateUniqueLabel
label label1
```
相当于
```
X86 { code = "Label1:\n", counter = 1, value = const () }
```
我们需要首先组装整个代码，生成标签，然后（在某种意义上）使用标签生成实际代码 . 这就是其他答案通过将计数器存储在 State （或 RWS ）monad中而提出的建议 .

我们还可以解决另一个问题：您希望能够向前和向后跳跃 . 这很可能是为什么你有单独的 allocateUniqueLabel 和 label 函数 . 但这允许两次设置相同的标签 .

实际上可以使用 do 使用"backwards"使用 do 表示法来定义这个monadic操作：
```
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 . （使用弃用的 mdo 关键字而不是 rec 会使代码更自然 . ）
- 我们将内部包裹在 X86 newtype . 首先，隐藏内部实现总是好的，它允许以后轻松重构 . 其次， 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，但是不允许依赖于值的状态修改，例如 evilReset . 但 X86 的封装实现了相同的目标，保持了很多友善的 do 语法 . ）
回复于 2024-04-26T02:12:19+08:00

在Haskell标记中生成唯一值

3 回答

相关问题