【译】状态机

时间：2020-09-13 21:48:04 阅读：49 评论：0 收藏：0 [点我收藏+]

STATE MACHINES 译文（状态机）

原文链接：https://blog.yoshuawuyts.com/state-machines/

原文作者：https://blog.yoshuawuyts.com/

译文来自：https://github.com/suhanyujie/article-transfer-rs/

译者：suhanyujie

译者博客：suhanyujie

ps：水平有限，翻译不当之处，还请指正。

标签：数据库，Rust，解析，状态机

很多时候，我想到一些和日常工作无关的话题。其中一个主题就是解析器：在 1 月份，我写了一篇关于字节顺序流解析的文章，并且我认为我们可以通过添加一组 API 来改进 Rust 中的流解析。

最近，我一直在思考改善方案，其中一个有趣的方式是状态机。[1] 很多解析逻辑包括这样的序列：如果你有了字符 X，则读取字符直到 Y，然后寻找字符 Z。这段描述可以称为“状态之间的转换”，而状态机则是描述这些状态转换的常用技术/结构/模式[2]

状态机是什么？

在 Rust 中的状态通常以 enum 类型体现：一个 boolean 可以是 true 或 false。一个 Option 可以是 Some 或 None。状态机是描述状态之间的关系。比如，交通灯可以从红变绿，但不能从红到黄 —— 它必须先变绿，才能变黄。[3].

技术分享图片

上图描述了 4 种状态和 5 种转换，由 @_lrlna 为我们的 "Graphs" 文章所作。

状态机不仅仅是编码哪些状态转换是有效的。如，在金融系统中，在确定事务成功之前可能需要执行一些重要的检查。状态机允许我们对“成功”状态进行编码，也就是在“验证”状态之前必须有一个“校验”状态。

在状态机中，有一个我觉得非常有趣且重要的属性是它们在活动代码库中提供了多少使用的东西。与用布尔逻辑编码关系不同的是，前者可以被提取（转换）到自己的状态现场。这样一来，它们对突发异常情况的健壮性就会增强。

如今 Rust 中的状态机

既然我们已经初步了解了状态机是什么，并且希望用户能够相信它们的有用性，接下来我们看看，在 Rust 中实现它。我们这里所说的很多东西都是收到了 Hoverbear 的“状态机模式”文章的启发，我推荐大家阅读它。

状态机的理想场景是在编译时对其进行完全编码：这样，如果我们的程序进行编译，我们可以确保发生的状态转换是我们定义的允许的状态转换。

如今的 Rust 中要实现这个是通过类型参数来做到的。如果以我们前面的“交通灯”为例，我们用 Rust 可以进行如下编码：

#[derive(Debug)]
pub struct Green;
#[derive(Debug)]
pub struct Yellow;
#[derive(Debug)]
pub struct Red;

#[derive(Debug)]
struct State<S> {
    _inner: S
}

impl State<Green> {
    pub fn new() -> State<Green> {
        State { _inner: Green{} }
    }
}

impl State<Green> {
    pub fn next(self) -> State<Yellow> {
        State { _inner: Yellow {} }
    }
}


impl State<Yellow> {
    pub fn next(self) -> State<Red> {
        State { _inner: Red {} }
    }
}

impl State<Red> {
    pub fn next(self) -> State<Green> {
        State { _inner: Green {} }
    }
}

fn main() {
    let state = State::new(); // 绿
    let state = state.next(); // 黄
    let state = state.next(); // 红
    let state = state.next(); // 绿
    dbg!(state);
}

Rust 训练场链接

正如你看到的，调用 next 可以将状态从一个值抓换为另一个。尽管方法可能看起来相同并且存在于多个结构体中：但它们是非常不同的。

如果我们在一个不正确的状态中尝试调用一个方法，编译器会提供一些有用的相关信息来改进。比如说，我们想确保自行车在绿灯亮的时候可以穿行。下面的例子是使自行车在红灯状态时穿行，此时就是一个典型的编译错误场景。

fn main() {
    let state = State::new(); // 绿灯
    let state = state.next(); // 黄灯
    let state = state.next(); // 红灯
    allow_bikes(&state);
    let state = state.next(); // 绿灯
}

fn allow_bikes(state: &State<Green>) {
    todo!();
}

Compiling playground v0.0.1 (/playground)
error[E0308]: mismatched types
  --> src/main.rs:42:17
   |
42 |     allow_bikes(&state);
   |                 ^^^^^^ expected struct `Green`, found struct `Red`
   |
   = note: expected reference `&State<Green>`
              found reference `&State<Red>`

error: aborting due to previous error

然而，这种模式有个比较大的限制就是不能在另一个结构体中存储状态；它只能以特定的方式存在于当前的栈中。所以，我们不能进行如下的操作：

struct Foo<S> {
    state: State<S>,
}

例如，当我们初始化 Foo 的时候，Green 是入参，在安全的 Rust 中，它现在不能再转换成 Red。这就是枚举的作用，不过，我们暂且不用它。

现在，检查状态机系统的 crate 比较有前景的有 machine 和 state_machine_future。

FUTURE 指引

P 编程语言将状态机作为一级类构造。它使用 state 关键字定义状态，并且使用 on、goto 和 raise 关键字在状态间切换[4]。看到这一点后，我开始思考：“Rust 是否有可能，只需最小的改动，就能将一流的状态机作为它本身的一部分？”嗯，我想，也许可以吧？

在我们继续之前，我要声明：我不是语言设计师，也不是任何语言团队的成员。上面那些都是猜测。这一切都来自一个有趣的点子，而我在这方面也不是权威。

因此，他们的想法是：“如果枚举是描述状态的一种方式，而方法是描述行为的一种方式，是否能将两者结合起来成为一个状态机？”

当前枚举类型的局限性在于其成员不是完全合格的类型。但是再仔细想一想它们。这意味着我们可以将枚举成员视为完全类型（译注：与之相对的是不完全类型）。

现在假设我们可以使用枚举成员作为任意的 self 类型，并且从方法 [5] 中返回枚举成员。然后我们可以像这样重写交通灯示例：

enum State {
    Green,
    Yellow,
    Red,
}

impl State {
    pub fn new() -> Self::Green {
        Self::Green
    }

    pub fn next(self: Self::Green) -> Self::Yellow {
        Self::Yellow
    }

    pub fn next(self: Self::Yellow) -> Self::Red {
        Self::Red
    }

    pub fn next(self: Self::Red) -> Self::Green {
        Self::Green
    }
}

fn main() {
    let mut state = State::new(); // 绿
    state = state.next(); // 黄
    state = state.next(); // 红
    state = state.next(); // 绿
}

正如你看到的，它很好地将状态重新组合为单个枚举上，并使用命名的转换在一种和另一种状态之间切换。这使得枚举成为状态和状态切换的唯一来源。

此外，方法不仅可以返回 Self：它们还可以返回 result 或者 future；允许发生各种类型的转换。下面的诊断分析很有参考意义：

Compiling playground v0.0.1 (/playground)
error[E0308]: mismatched types
  --> src/main.rs:42:17
   |
42 |     allow_bikes(&state);
   |                 ^^^^^^ expected `State::Green`, found `State::Red`
   |
   = note: expected reference `&State::Green`
              found reference `&State::Red`

error: aborting due to previous error

然而，这里有很多猜测 "if" 绑定。是否有可能以这种方式充分地推理枚举成员？这是否有效？能实现这一点会有很副作用，这些需要更专业的人来解答。

结论

在这篇相当仓促的文章中，我分享了什么是状态机，如何在现有的 Rust 中编写它们，它们的局限性，并推测如何通过语言扩展来简化它们的实现。

原则上，现在已经可以在 Rust 中编写状态机。编译器会为你校验它们，并在出错时提供有用的信息。这在一定程度上说明了线性类型的实用性。然而，它们也有严重的局限性，感觉它不是最自然的方式。

对于我在这篇文章中描绘的未来方向，我希望它是现在的 Rust 非常自然的延伸。但这会使像 Rust 中这样，存在经编译器检查的通用状态机的方式，在编程语言中似乎并不常见。

到目前为止，我喜欢我这边文章中描绘的方向，它描述的，感觉像是今天的 Rust 的一个相当自然的延伸。

也许这篇文章在将来的某个时候对 Rust 中一流状态机的实现产生启发。也有可能我说的完全不对。无论如何，这都是一个有趣的思考练习，并且值得分享[6]。感谢你的阅读[7]！

注释

1.去年 12 月份，我探索了解析器，并在“解析器组合子”和“解析器生成器”之间有了一些认识。Mountain Ghosts (James Coglan) 在 Twitter 上之处，还有一种变体的解析器：Prolog 的 “定义字句语法”。在阅读了 Wiki 的介绍后，我感觉它确实看起来像状态机。我碰巧知道编译器的基于 Prolog 的类型解析。因此我想知道：如果 Rust 将状态机作为语言的一部分，那么这是否会使我们更接近以另辟蹊径的方式来表达解析器呢？我敢打赌，了解这个的人一定会有更多的东西来阐述。←

2.现在是星期一的 23:05。刚过去的整个周末我都在思考状态机，没什么特别的原因，所以我写了这篇文章是为了在我失去这些灵感之前把它们拿出来，变成一种结构化的形式存在。←

3.在德国，交通灯是 绿 -> 黄 -> 红 -> 黄 -> 绿，在本文，我们假设它们是 绿 -> 黄 -> 红 -> 绿。←

4.我还发现了 Plaid 语言，它讨论了一堆状态机，但其中大部分是用 pdf 和 tarballs 源编写的，所以我还没有真正深入研究它。←

5.这可能也需要专业化。此处插入做个标记（译注：此处不知怎么翻译好 ?? ）。 ←

6.因为我一直在尝试并且没有失去理智；我已经在思考状态机 72 小时了。需要将其从我的“系统”中清理掉。←

7.在那些做了很多尝试的时间里。←

参考

【译】状态机

原文：https://www.cnblogs.com/ishenghuo/p/13662977.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)