使用 Haskell 状态 monad 有代码味道吗？

Question

天哪，我讨厌“代码味道”这个词，但我想不出更准确的词了。

我正在设计一种高级语言& 闲暇时将编译器转换为 Whitespace 来学习编译器构造、语言设计和函数式编程（编译器是用 Haskell 编写的）。

在编译器的代码生成阶段，我必须在遍历语法树时维护“状态”数据。 例如，在编译流程控制语句时，我需要为要跳转到的标签生成唯一名称（从传入、更新和返回的计数器生成的标签，并且计数器的旧值绝不能再次使用） 。 另一个例子是，当我在语法树中遇到内联字符串文字时，它们需要永久转换为堆变量（在空白中，字符串最好存储在堆上）。 我目前正在将整个代码生成模块包装在状态单子中来处理这个问题。

有人告诉我，编写编译器是一个非常适合函数范式的问题，但我发现我的设计方式与用 C 语言设计它的方式大致相同（你真的可以用任何语言编写 C 语言 - 甚至带状态单子的 Haskell）。

我想学习如何在 Haskell 中思考（而不是在函数范式中），而不是使用 Haskell 语法的 C 语言。 我真的应该尝试消除/最小化状态单子的使用，还是它是一个合法的功能“设计模式”？

Answer 1

我已经用 Haskell 编写了多个编译器，状态 monad 是许多编译器问题的合理解决方案。 但你想让它保持抽象——不要让你明显地看出你正在使用一个 monad。

这是来自 Glasgow Haskell 编译器的示例（我不是编写的；我只是围绕一些边缘进行工作），我们在其中构建控制流图。 以下是制作图表的基本方法：

empyGraph    :: Graph
mkLabel      :: Label -> Graph
mkAssignment :: Assignment -> Graph  -- modify a register or memory
mkTransfer   :: ControlTransfer -> Graph   -- any control transfer
(<*>)        :: Graph -> Graph -> Graph

但是正如您所发现的，维护唯一标签的供应充其量是乏味的，因此我们也提供了这些函数：

withFreshLabel :: (Label -> Graph) -> Graph
mkIfThenElse :: (Label -> Label -> Graph) -- branch condition
             -> Graph   -- code in the 'then' branch
             -> Graph   -- code in the 'else' branch 
             -> Graph   -- resulting if-then-else construct

整个 Graph 事物是一个抽象类型，而翻译者只是以纯函数的方式愉快地构建图表，而没有意识到任何单子正在发生。 然后，当最终构建图时，为了将其转换为我们可以生成代码的代数数据类型，我们为其提供唯一标签，运行状态 monad，并提取数据结构。

状态单子隐藏在下面； 虽然它没有暴露给客户端，但是 Graph 的定义是这样的：

type Graph = RealGraph -> [Label] -> (RealGraph, [Label])

或者更准确一点

type Graph = RealGraph -> State [Label] RealGraph
  -- a Graph is a monadic function from a successor RealGraph to a new RealGraph

状态 monad 隐藏在抽象层后面，它一点也不臭！

Answer 2

我想说，状态通常不是代码味道，只要它保持较小且控制良好即可。

这意味着使用诸如 State、ST 或定制的 monad，或者只是拥有一个包含传递到几个地方的状态数据的数据结构，并不是一件坏事。 （实际上，单子只是帮助做到这一点！）然而，拥有到处都是的状态（是的，这意味着你，IO 单子！）是一种不好的气味。

一个相当明显的例子是，当我的团队正在为 ICFP 编程竞赛 2009 制作参赛作品时（代码可在在 git://git.cynic.net/haskell/icfp-contest-2009）。 我们最终得到了几个不同的模块化部分：

• VM：运行模拟程序的虚拟机
• 控制器：几组不同的例程，用于读取模拟器的输出并生成新的控制输入
• 解决方案：基于以下内容生成解决方案文件控制器的输出
• 可视化器：几组不同的例程，它们读取输入和输出端口，并生成某种可视化或模拟过程中所发生情况的日志。

其中每一个都有自己的状态，并且它们都以不同的方式交互通过VM的输入和输出值的方式。 我们有几个不同的控制器和可视化器，每个都有自己不同的状态。

这里的关键点是，任何特定状态的内部都仅限于它们自己的特定模块，并且每个模块甚至不知道其他模块的状态是否存在。 任何特定的有状态代码和数据集通常只有几十行长，并且状态中有少量数据项。

所有这些都被粘合在一个由大约十几行代码组成的小函数中，该函数无法访问任何状态的内部结构，并且在循环模拟时仅以正确的顺序调用正确的事物，并通过一个非常有限的函数。每个模块的外部信息量（当然还有模块之前的状态）。

当状态以如此有限的方式使用时，并且类型系统阻止您无意中修改它，那么处理起来就很容易了。 Haskell 的优点之一就是它可以让你做到这一点。

一个答案是：“不要使用 monad”。 从我的角度来看，这完全是本末倒置。 Monad 是一种控制结构，除其他外，它可以帮助您最大限度地减少涉及状态的代码量。 如果您以一元解析器为例，则解析器的状态（即正在解析的文本、已解析的程度、累积的任何警告等）必须贯穿解析器中使用的每个组合器。 然而，只有少数组合器能够真正直接操纵状态； 其他任何东西都使用这几个函数之一。 这使您可以在一个地方清楚地看到所有可以更改状态的少量代码，并且更容易地推断如何更改它，再次使其更容易处理。

Answer 3

您看过属性语法（AG）吗？ （有关维基百科和Monad 阅读器中的文章）？

使用 AG，您可以将属性添加到语法树中。 这些属性分为合成和继承属性。

综合属性是您从语法树生成（或综合）的东西，这可能是生成的代码，或所有注释，或您感兴趣的任何其他内容。

继承的属性是语法树的输入，这可能是环境，或代码生成期间使用的标签列表。

在乌得勒支大学，我们使用属性语法系统 (UUAGC) 编写编译器。 这是一个预处理器，它从提供的 .ag 文件生成 haskell 代码（.hs 文件）。

---

不过，如果您仍在学习 Haskell，那么也许现在还不是开始学习另一层抽象的时候。

在这种情况下，您可以手动编写属性语法为您生成的代码，例如：

data AbstractSyntax = Literal Int | Block AbstractSyntax
                    | Comment String AbstractSyntax

compile :: AbstractSyntax -> [Label] -> (Code, Comments)
compile (Literal x) _      = (generateCode x, [])
compile (Block ast) (l:ls) = let (code', comments) = compile ast ls
                             in (labelCode l code', comments)
compile (Comment s ast) ls = let (code, comments') = compile ast ls
                             in (code, s : comments')

generateCode :: Int -> Code
labelCode :: Label -> Code -> Code

Answer 4

您可能需要一个应用函子而不是
monad：

http://www.haskell.org/haskellwiki/Applicative_functor

我认为原始论文然而，它比 wiki 解释得更好：

http://www. soi.city.ac.uk/~ross/papers/Applicative.html

Answer 5

我不认为使用 State Monad 来建模状态时会产生代码味道。

如果您需要通过函数对状态进行线程化，
您可以明确地执行此操作，将状态作为参数并在每个函数中返回它。
State Monad 提供了一个很好的抽象：它为你传递状态，并且
提供了许多有用的函数来组合需要状态的函数。
在这种情况下，使用 State Monad（或 Applicatives）并不是代码异味。

但是，如果您使用 State Monad 来模拟命令式编程风格
虽然一个功能性的解决方案就足够了，但你只是让事情变得复杂。

Answer 6

一般来说，您应该尽可能避免使用状态，但这并不总是可行的。 Applicative 使有效的代码看起来更好、更实用，尤其是树遍历代码可以从这种风格中受益。 对于名称生成的问题，现在有一个相当不错的包可用： 价值供应。

Answer 7

好吧，不要使用 monad。 函数式编程的强大之处在于函数的纯粹性及其重用。 我的一位教授曾经写过一篇论文，他是帮助构建 Haskell 的人之一。

我建议该论文名为“为什么函数式编程很重要”你读完它。 这是一本好书。

Answer 8

让我们注意这里的术语。 状态本身并不是坏事，而是坏事。 函数式语言有状态。 什么是“代码味道”是当您发现自己想要分配变量值并更改它们时。

当然，Haskell 状态 monad 正是出于这个原因而存在的——与 I/O 一样，它允许您在受限的上下文中执行不安全且非功能性的操作。

所以，是的，这可能是代码味道。