在Haskell中编写汇编程序 - mapM与状态？

Question

我在Haskell中编写了一个非常简单的两遍汇编程序,我遇到了一个我还没有解决过的经验的场景.我认为解决方案很可能涉及monad变压器,我并不理解.

汇编程序将汇编代码解析为Statements 的列表,s是指令或标签.有些人Statement可能会提到标签.汇编程序需要将Statements转换为Instructions,这涉及消除标签并用适当的值替换标签引用.

我编写了汇编程序的第一个传递,它生成一个[(String, Int)]表示从标签到地址的映射.我还编写了以下函数来将a Statement转换为Instruction:

stmtToInstruction :: Int -> [(String, Int)] -> Statement -> Either String [I.Instruction]
stmtToInstruction addr labels stmt = case stmt of
    ADD d s1 s2     -> Right [I.ADD d s1 s2]
    BEQL s1 s2 l    -> case do label <- find (\e -> fst e == l) labels
                               let labelAddr = snd label
                               let relativeAddr = I.ImmS $ fromIntegral (labelAddr - addr)
                               return (I.BEQ s1 s2 relativeAddr) of
                        Just i -> Right [i]
                        Nothing -> Left $ "Label " ++ l ++ " not defined"
    LABEL _         -> Right []

为简洁起见,我省略了几个案例,但您可以在此处看到所有可能的结果:

• ADD 总是成功并产生指令
• BEQL 可以成功还是失败,具体取决于是否找到标签
• LABEL 总是成功,即使它没有产生实际指示

这按预期工作.我现在的问题是编写这个函数:

replaceLabels :: [Statement] -> Either String [I.Instruction]

replaceLabels获取一个语句列表,并stmtToInstruction在每个语句上运行.该addr参数stmtToInstruction必须是长度[Instruction]累积至今.Left String如果其中一个标签引用无效,则输出可以是a ;如果Right [I.Instruction]没有错误,则输出可以是a .

mapM :: Monad m => (a -> m b) -> [a] -> m [b]让我们得到一些方法,但没有办法将当前地址注入(a -> m b)函数.我该如何工作？

Answer 1

我已经实现了一个递归解决方案，我确信该解决方案效率非常低。我仍然有兴趣了解执行此操作的“正确”方法。

replaceLabels :: [Statement] -> Either String [I.Instruction]
replaceLabels [] = Right []
replaceLabels stmts@(s:ss) = replaceLabels' labels stmts 0
    where labels = process stmts

replaceLabels' :: [(String, Int)] -> [Statement] -> Int -> Either String [I.Instruction]
replaceLabels' _ [] _ = Right []
replaceLabels' labels (s:ss) addr = do
                                instructions <- stmtToInstruction addr labels s
                                restInstructions <- replaceLabels' labels ss (addr + length instructions)
                                return (instructions ++ restInstructions)