如何在 Haskell 中实现状态图？

Question

在阅读了 Miro Samek 的优秀著作《Practical UML Statecharts in C/C++》之后，我迫不及待地想尝试一下。最近，我开始自学 Haskell 和函数式编程。

\n

在我关于 Haskell 的书刚读了几章后，我就突然意识到状态图可能很困难，甚至与 Haskell 的风格背道而驰。毕竟，创建无状态程序需要付出巨大的努力，或者至少将代码的所有不纯部分与纯代码部分很好地分开。

\n

当我在网上搜索“Haskell”结合“statechart”时，我几乎什么也没找到！这激起了我的好奇心。毕竟，Haskell 是一种相当古老的通用编程语言。怎么可能\n似乎几乎没有与状态图相关的活动？

\n

Haskell 的 Reddit 子主题“ haskeller 对状态图的思考”中提出了几种可能的解释，我希望我的简短摘录不会扭曲任何作者的观点：

\n

\n

1. /\xe2\x80\xa6/ Haskell 社区总体上在 UI 开发方面不是很活跃 /\xe2\x80\xa6/

   \n
\n

2. /\xe2\x80\xa6/ 状态图的缺点是它们提供的所有灵活性\n使得模型检查（以及基于模型的\n测试）变得更加困难。/\xe2\x80\xa6/

   \n
\n

3. /\xe2\x80\xa6/ 状态机是状态和转换规则的集合。但由于实现状态是多余的，您可以单独使用转换规则，这些规则被整齐地表示为（相互递归的）函数族。/\xe2\x80\xa6/ 但 Haskell 不受此限制，因此显式实现状态机通常是多余的。

   \n

   Hense（原文如此！），作为一名 Haskeller，我大多数时候并不真正需要显式状态机。作为一等公民和 TCO 的功能，在最好的情况下是一个实施细节，在最坏的情况下是不需要的。/\xe2\x80\xa6/

   \n
\n

4. A。/\xe2\x80\xa6/ 在 Haskell 生态系统中，你可能会更幸运地使用“转换系统”、“演员模型”或“状态转换器”等搜索词。/\xe2\x80\xa6/

   \n

   b. /\xe2\x80\xa6/ 函数反应式编程 (FRP) 和箭头是 Haskell 中\n实现信号流的方法。/\xe2\x80\xa6/

   \n

   C。/\xe2\x80\xa6/ State monad 转换器可以对此进行建模。如果中间步骤中有\n外部信号，则可以\n将其嵌入\n延续 monad 中。/\xe2\x80\xa6/

   \n
\n

\n

我允许自己解释一下，并对此进行评论：

\n

\n
1. 我发现 H. 程序员不使用状态图的想法是因为他们不进行这种编程，这有点令人难以置信。我可能是错的，但我认为应用领域比 UI 更广泛。
\n
2. 这个论点有点超出我的想象。作者可能关注某种类型的测试、某种工具。我的意思是，如果有什么的话，预先定义明确的一组状态是否会使测试变得更加容易？
\n
3. 这也许是最有趣的论点，显式状态在 Haskell 中是多余的，因此需要编写可见的状态机。我的反对意见也许不公平，但状态机抽象（或者更确切地说，它在代码中的可见化身）不就是为了让事情变得更清晰、更容易理解而发明的吗？\n它解决的问题\xe2\x80\x94使未指定的、事实上的状态机器隐藏在“普通”程序中，根据大量组织不良的变量的值做出决策，更加明显\n\xe2\x80\x94，这不是被否定了吗？摆脱状态机？
\n
4. 难道真的这么简单，状态图就在那里，但只是被称为完全不同的东西吗？\xe2\x80\xa6 还是在 Haskell 的世界中，这些\n是针对同一问题的更好的解决方案，\n有效地使状态图真正变得多余？
\n

\n

当我读完 Haskell 和 FP 的书后，这一切会变得非常明显吗？

\n

Answer 1

您可以使用状态图来完成此操作，但您不需要这样做，因为 Haskell 的工作级别比其他语言更高，并将状态图设计纳入代码中。以下是具体操作方法。（注意：我从 monad 转换器版本简化了它，它也处理异常，如果我犯了任何错误，很抱歉）

首先，你可以在 Haskell 中定义一个状态机，如下所示：

newtype AutoS i o = AutoS {runAutoS :: (o, i -> AutoS i o)}

换句话说，状态机由其最新输出和从输入到下一个状态的o函数组成。i我将其称为“自动”，因为它们是自动机，这是状态机的数学术语。

现在您只需获取 UML 状态图并将其直接转换为AutoS值的集合。但还有更好的方法。

newtype Auto i o a = Auto {runAuto :: (a -> AutoS i o) -> AutoS i o}

这是continuation monad的变体。对于传统的 monad，每个步骤的结果都用作下一步的参数，但在延续中，每个步骤将下一步作为函数参数，并将其结果传递给该函数。这听起来像是一种奇怪的做事方式，但这意味着您可以从 monad 内访问“其余的计算”，这可以让您做一些聪明的事情。但在解释之前，先看一些例子。特别值得花一些时间思考 Monad 实例。所有这些功能k都是延续；代表其余计算的参数。

instance (Functor m) => Functor (Auto i o) where
   fmap f (Auto act) = Auto $ \k -> act (k . f)

instance (Monad m) => Applicative (Auto i o ) where
   pure v = Auto $ \k -> k v
   f <*> v = Auto $ \k -> runAuto f $ \g -> runAuto v (k . g)

instance (Monad m) => Monad (Auto i o) where
   return = pure
   v >>= f = Auto $ \k -> runAuto v $ \x -> runAuto (f x) k

所以现在我们可以在 中编写动作Auto。但他们能做什么呢？这是yield函数，它是 中唯一的原语Auto：

yield :: o -> Auto i o i
yield v = Auto $ \k -> AutoS (v, k)

这就是神奇之处。与之前一样，k是延续（即此步骤之后的所有内容）。请记住，该步骤的结果（即 的结果yield）被传递给该函数。通过将其包装在AutoS生成值中，我们将该值作为状态机的输出传递，并为状态机调用者提供下一个状态转换。

因此，现在我们可以只编写单子代码，而不是将程序编写为具有大量命名状态的状态机。当我们的一元代码想要与世界其他地方交换信息时，它会yield发送一个值并获得一个新值作为回报。

有一个古老的笑话，讲的是一位数学家被要求去捕捉笼子里的狮子。数学家进入笼子，关上门，并宣布（通过几何倒转）他现在在笼子外面，而其他所有东西，包括狮子，都在笼子里面。这个延续单子有点像那样；你的一元代码就像数学家；它传递一个值yield并返回一个结果。但从世界其他地方的角度来看，屈服值从状态机（笼子）中出来，下一个状态转换返回成为 的结果yield。

这里您唯一需要的另一件事是运行操作的方法Auto：

startMachine :: Auto i o Void -> AutoS i o
startMachine act = runAuto act $ error "Can't happen: Auto terminated."

这假设您的状态机没有结束状态。Void你从void包中得到。如果你需要一个最终状态，那么它必须有一个单独的类型，并且该类型必须与其他所有东西一起徘徊。在原始的Cont延续单子中，类型是r.

这样做的一大优点是状态机的逻辑像普通程序一样被表达为一系列步骤。如果没有一元方法，您所拥有的只是状态和转换的列表，这使得遵循逻辑变得非常困难。这就像阅读一个每行都以 GOTO 结尾的程序。当代码难以理解时，您必须使用设计符号来解释它。状态图有点像状态机的流程图。通过使用 monad，您可以直接在状态图级别进行编程，使其变得不相关，就像结构化编程使流程图变得不相关一样。

创建 monad 转换器版本AutoT作为学生的练习。提示：newtype AutoS i o m = runAutoS :: m (o, i -> AutoS i o m)}，然后看看ContTmonad 变压器包中的内容。

实际上你可以通过替换为来做到这Auto一点Cont。我没有这样做，因为我也需要例外并且ContT不做例外。添加适当的异常处理之类的内容也可以作为学生的练习。暗示：newtype AutoS i o e m = AutoS {runAutoS :: m (o, i -> AutoS i o e m, e -> AutoS i o e m) }

编辑：您提到了测试状态图实现的难易程度。

是的，对于足够小的“测试”值。如果您使用由枚举索引的状态以传统语言实现状态图，那么测试您的状态转换是否与状态图匹配确实是微不足道的。但是，您仍然需要验证设计中的状态图是否正确。这与验证单子代码是否正确是完全相同的问题，Auto因为它们都在同一抽象级别描述解决方案。