介绍
对于一套系统的设计，通常我都是想好了，然后直接捋起袖子写代码了。写完了，在开始加很多 test 来保证它的正确性。但其实，我并不能保证设计是完全正确的。也就是说，我的实现满足了该系统的需求，但也有可能在一些 corner case 上面并没有考虑周全。同时， 虽然后面可以写很多 test，但并不一定能 cover 到所有的分支。所以，为了更好的确保设计的正确性，我们需要使用 TLA+ 或者其他类似的工具。
TLA+ 是一门形式规格说明语言(formal specification language)，主要用来验证系统的设计和算法的正确性。TLA+ 是大神 Lamport 捣鼓出来的东西，关于大神 Lamport，这里就不多做介绍了，反正就是 NB 的一塌糊涂了。
TLA+ 是对系统（譬如程序，算法，操作系统等）更高层的建模，但 TLA+ 并不能生产任何代码。对于很多程序员来说，首要直觉这是这玩意到底有啥用？TLA+ 可以认为是一种新的思考方式，是在代码之上更上层的规格说明。通过 TLA+ 来设计系统，能让我们更好的对整个系统进行抽象。
抽象
抽象对于程序员来说，可能是最重要的一个能力。通过抽象，能然我们更好的理解复杂的系统，如果我们不能对一个系统进行抽象，我们并不能正确的理解这个系统。悲催的是，我个人认为我自己还需要提高这方面的能力，正好，可以通过学习 TLA+ 来提高。因为对于学习 TLA+ 来说，最难的部分就是对系统进行抽象。
对于 TLA+ 来说，一个系统的执行其实可以表示为一个离散步骤序列（A sequence of discrete steps）。这里我们主要关注三个东西。
- Discrete：对于一个连续演化的系统，我们可以抽象为一系列的离散事件。譬如，对于一个时钟来说，虽然时间的流逝是连续的，但我们可以抽象为每次按照一个离散的 tick 前进的。
- Sequence：对于一个并行的系统来说，我们能使用一个步骤序列来表示。虽然这看起来很奇怪，但实际上我们我们是能够用一个序列程序来模拟并发系统的。
- Step：TLA+ 描述一个 step 就是一个状态变更。一次执行可以表示为一个状态序列，而一个 step 就是从一个状态切换到另一个状态。对于一个状态来说，就是给一些变量赋值。
状态机
对于一个系统来说，TLA+ 会将其抽象为状态机。一个状态机可以被如下描述：
- 所有可能的初始状态
- 对于任意状态，后面的状态是什么
因为我们在上面说过，状态就是一次对变量的赋值，所以我们继续做如下描述：
- 变量是什么
- 变量的所有可能初始值
- 在当前状态下这些变量的值以及在下一个状态下这些变量的可能的值之间的关系
这个听起来有点绕，我们可以用一个简单的 C 例子（先别纠结 main 前面的 void）来说明：
int i;
void main() {
i = someNumber();
i = i + 1;
}
这里 someNumber() 会随机返回 0 到 1000 里面的一个数值。所以对于不同的返回值，我们其实有不同的执行。
这里，我们就一个变量，也就是 i，假设 someNumber() 返回 42，那么一个执行就是 [i : 0] -> [i : 42] -> [i: 43]。我们先按照状态机来描述这个例子：
- 变量，也就是 i
- 初始值，这里就是 0
- 当前状态 i 的值和下一个状态 i 的可能值之间的关系。
上面最后 i 为 43 之后，下一个状态并没有值，因为程序结束了。但如果 someNumber() 返回 43，那么整个执行就是 [i : 0] -> [i : 43] -> [i: 44]，在 43 之后，下一个状态的值是 44。所以对于当前状态 43 来说，我们在下一个状态会有不同的值，这是不可能的。也就是说，我们不能只通过一个 i 变量来将这个程序描述成状态机。
这里，我们引入另一个变量，pc（program control），作为一个控制状态。对于上面例子，现在就是两个变量 i 和 pc。初始值 i 为 0，pc 为 “start”。当第一条语句执行之后，pc 为 “middle”，而程序结束的时候，pc 为 “done”。那么我们现在可以描述两个状态之间的关系了：
- 如果当前 pc 值为 “start”，那么 i 的下一个值就是在
{0, 1, …, 1000}里面的一个值，pc 就是 “middle” - 如果当前 pc 值为 “middle”，那么 i 的下一个值就是当前 i 的值加 1， pc 就是 “done”
- 否则没有下一个值
Math
我们现在开始尝试用数学的方式来描述上面的状态机。我们定义 pc 和 i 分别为当前值，而下一个状态的值为 pc’ 和 i’。我们可以从一个伪代码开始，然后开始逐渐用 TLA+ 来描述。
if pc = "start"
then i' in {0, 1, ..., 1000}
pc' = "middle"
else if pc = "middle"
then i' = i + 1
pc' = "done"
else no next values
这里需要注意，= 在数学里面是相等的意思，类似 2 + 2 = 4，并不是通常程序里面的赋值的意思。
{0, 1, ..., 1000} 是一个集合，我们可以使用 0..1000 来表示，in 在集合里面是 ∈，但为了方便输入，我们直接使用 ASCII 的 \in 来表示。
对于第一个 then ，里面有两个独立的公式（formula），但 then 这个应该是一个单一的公式，并且断定里面所有的公式都要为真，所以我们这里可以使用 and 来连接这两个公式。我们使用 /\ 来表示。
no next values 也是一个公式，我们直接使用 FALSE 来表示。所以上面可以写成：
if pc = "start"
then i' \in 0..1000 /\
pc' = "middle"
else if pc = "middle"
then i' = i + 1 /\
pc' = "done"
else FALSE
这里需要注意，我们不能按照程序执行的顺序思维来思考，也就是说，如果 pc 为 start，我们就 then 做什么事情，不然我们就 else 做什么事情。这个公式应该理解为，如果 pc 是 start，那么这个公式的值就等于 then 这个公式的值，否则就是等于 else 这个公式的值。
对于这个公式，i = 17, pc = "start", i' = 534, pc' = "middle"它的值等于 true，而对于 i = 534, pc = "middle", i' = 77, pc' = "done" 则是 false。
我们继续，对于上面的公式，返回 true 的情况就是两种，if pc = "start" /\ (i' \in 0..1000 /\ pc' = "middle") 为 true 或者 if pc = "middle" /\ (i' = i + 1 /\ pc' = "done") 等于 true。or 我们可以使用 \/ 来表示，所以上面可以写成：
((pc = "start)
/\ (i' \in 0..1000)
/\ (pc' = "middle"))
\/ ((pc = "middle")
/\ (i' = i + 1)
/\ (pc' = "done"))
TLA+ 支持符号列表这样的格式，我们顺便去掉括号，继续简化，得到：
\/ /\ pc = "start
/\ i' \in 0..1000
/\ pc' = "middle"
\/ /\ pc = "middle"
/\ i' = i + 1
/\ pc' = "done"
上面我们对一个简单的 C 程序重新用 TLA+ 来描述，代码上面看起来比 C 的复杂了不少，但却能更好的描述系统。在 C 里面，someNumber() 这个函数返回值是不确定的，我们并不能很好的对不确定的系统进行描述的。但使用 TLA+ 却非常方便，在上面的例子里面我们直接使用数学集合来描述。
这里我们需要注意，我们通过 TLA+ 来思考的是一个公式，并不是程序命令执行的序列。所以一定要用数学的方式来思考整个系统，这点恰恰是对程序员来说最困难的一点，毕竟要转换之前的设计思路。后面我们会先介绍一下 TLA+ 相关的数学知识。
小结
TLA+ 是一门非常强大的语言，它在系统设计上面能让我们更好的对系统进行抽象，然后验证设计的正确性。
上面介绍的是 Lamport 的 TLA+ 视频第一章的学习笔记。实话，个人还没有完全理解状态机这些东西，毕竟它的思考模式跟传统的程序语言完全不一样。
后面，我会开始逐渐学习 TLA+，最终目标是将我们系统里面的一些关键模块，譬如分布式事务这些，使用 TLA+ 进行验证。
网友评论