状态思维

# 以状态思考 来源：https://www.metalevel.at/tist/ ## 动机 如果你习惯了命令式编程语言，然后学习函数式或逻辑编程语言，你可能会在顺利解决一些简单练习后，突然发现自己无法在声明式语言中解决看似简单的任务。例如，你可能会问：“我到底如何增加一个变量的值？”或者“我到底如何从列表中删除一个元素？”，更一般地说，“我到底如何对这个数据结构应用一个简单的变换？”等等。 这类问题的解决方案总是一样的：以**关系**来思考不同实体之间的联系。这些实体的例子包括变量、列表、树、**状态**等。例如，在命令式语言中，改变一个变量的**状态**很简单：`i = i + 1;` 执行这样的语句后，`i` 的**状态**就**改变**了。`i` 的旧状态不再可访问。注意，声明式地看，这个等式没有意义：没有数 `i` 等于 `i+1`。 在 Prolog 中，上面的片段可以变成：`I #= I0 + 1`。这意味着 `I` 和 `I0` 处于某种关系中。在这个例子中，`(#=)/2` 表示整数表达式的**等价关系** (https://www.metalevel.at/prolog/clpfd)。 重要的是，这样的关系可以用于**所有方向**。对应于上面命令式方式的做法是让 `I0` 实例化为一个具体的整数，然后让 `I` 表示下一个整数。由于 Prolog 的通用性，如果 `I` 实例化而 `I0` 未知，甚至如果**两者**都还是变量，也可以使用**相同**的片段。要从这种通用性中受益，你需要完成的心智飞跃是以**两个**变量而不是一个变量来思考。这是必要的，因为同一个变量不能同时反映两个不同的状态，旧的和新的。 再举一个例子，当你发现自己问“我到底如何从列表中删除一个元素 `E`？”时，声明式地思考，描述两个列表之间的**关系**：一个列表可能包含元素 `E`，第二个列表包含第一个列表中所有不等于 `E` 的元素。实际上，正如你已经看到的，在这种情况下我们描述的是**三个**实体之间的关系：两个列表和一个元素。你可以通过陈述使关系**成立**的条件在 Prolog 中表达这种关系： ``` list1_element_list2([], _, []). list1_element_list2([E|Ls1], E, Ls2) :- list1_element_list2(Ls1, E, Ls2). list1_element_list2([L|Ls1], E, [L|Ls2]) :- dif(L, E), list1_element_list2(Ls1, E, Ls2). ``` 这个关系为每个实体都有一个参数，我们可以**声明式地**读取每个子句 (https://www.metalevel.at/prolog/reading#declarative)。例如，第一个子句的意思是：**如果**第一个和第三个参数是空列表，则关系成立。第二个子句意思是：**如果**关系对于 `Ls1`、`E` 和 `Ls2` 成立，**那么**关系对于 `[E|Ls1]`、`E` 和 `Ls2` 也成立。第三个子句类似地解读，额外约束条件是**如果** `L` 和 `E` 是**不同**的项。这个谓词在所有方向都可用：它可以回答比“如果我们删除所有出现的元素 `E`，列表会是什么样子？”更一般的问题。你还可以用它来回答例如：“在给定的例子中，哪个元素（如果有的话）被删除了？”，或者回答最一般的查询：“这个关系对于哪三个实体成立？”这种通用性就是为什么像“remove/3”这样的命令式名称在这种情况下不合适。 Prolog 提供了几种语言结构来使谓词通用、高效**且**简洁。例如，使用来自 `library(reif)` (https://www.metalevel.at/prolog/metapredicates#if_3) 的元谓词 `tfilter/3`，我们可以等价地写 `list1_element_list2/3` 为： ``` list1_element_list2(Ls1, E, Ls2) :- tfilter(dif(E), Ls1, Ls2). ``` 如果所有参数都充分实例化，这个版本是**确定性的**。例如： ``` ?- list1_element_list2("abc", b, Ls). Ls = "ac". ``` 再举一个例子，当你发现自己问：“我到底如何对树应用一个变换？”时，再次声明式地思考，描述两棵树之间的**关系**：一棵树**在**变换**之前**，另一棵树**在**变换**之后**。 注意，**函数**是关系的一种特殊情况，所以下面的大部分内容既适用于函数式编程语言也适用于逻辑编程语言。逻辑编程语言通常允许用更少的努力得到更通用的解决方案，因为谓词通常可以在几个方向使用。在本文中，我们将看到几个关于**状态**之间关系的例子：谜题中的状态、程序中的状态、编译器中的状态等等，以便你看到各种任务如何在声明式语言中表达。所有这些例子的核心思想是相同的：以**状态之间的关系**来思考。这与命令式语言形成对比，在命令式语言中，我们通常思考对状态的破坏性**修改**。 ## 全局状态 如果你习惯于用命令式编程语言思考，你也会尝试在声明式语言中找到操纵**全局状态**的方法。例如，你可能尝试在 Prolog 中查询和改变**全局变量** (https://www.metalevel.at/prolog/global)。 Prolog**确实**通过各种方式支持改变全局状态。例如，我们可以通过几种方式破坏性地改变全局数据库。然而，如果 Prolog 程序通过设置全局变量或修改全局数据库来改变全局状态，我们期望的纯逻辑程序的重要属性可能会**被破坏**。这样的程序可能不再在所有方向可用，可能对相同的查询产生不同的结果，并且通常不能再孤立于准备或清理这些全局状态的其他程序片段进行测试和使用。出于这些原因，这**不是**我们在本文中讨论的那种状态。为了充分利用**纯** (https://www.metalevel.at/prolog/purity) Prolog 程序的优势，你应该始终致力于找到表达状态变化的**声明式**方式。推理变化的声明式方式是描述由这些变化引起的状态之间的**关系**。 ## 谜题中的状态 状态表示的选择可以显著影响你描述任务的优雅程度。考虑一个简单的谜题来说明这一点： 给定**水壶** A、B 和 C，容量分别为 8、5 和 3，初始填充状态分别为**满**、**空**和**空**，要求在 A 和 B 中恰好量出 4 个单位。显然，这个谜题中的一个重要**状态**是每个壶中的水量。使用 Haskell，让我们将这个状态表示为一个三元组 (A,B,C)： ``` type State = (Int,Int,Int) ``` 现在，我们要找到从状态 (8,0,0) 到状态 (4,4,0) 的一系列转移。我们从一个函数开始，该函数给定一个状态，返回所有合适的后继状态列表： ``` successors :: State -> [State] successors (a,b,c) = let ab = min a (5 - b) ac = min a (3 - c) ba = min b (8 - a) bc = min b (3 - c) ca = min c (8 - a) cb = min c (5 - b) ss = [(ab,a-ab,b+ab,c), (ac,a-ac,b,c+ac), (ba,a+ba,b-ba,c), (bc,a,b-bc,c+bc), (ca,a+ca,b,c-ca), (cb,a,b+cb,c-cb)] in [(a',b',c') | (transfer,a',b',c') <- ss, transfer > 0] ``` 我们可以交互式地测试这个函数： ``` Main> successors (8,0,0) [(3,5,0),(5,0,3)] ``` 现在让我们确定，从初始状态开始，我们是否真的能到达目标状态。我们尝试广度优先搜索，一种完备但空间效率低下的搜索策略： ``` search :: [State] -> Bool search (s:ss) | s == (4,4,0) = True | otherwise = search $ ss ++ successors s ``` 在每次迭代中，我们考虑给定状态列表中的第一个状态。如果它是目标状态，我们就完成了。否则，它的后继状态被追加到剩余状态（待以后考虑），然后搜索继续。我们现在可以查询 ``` search [(8,0,0)] True ``` 并且知道谜题实际上有解。为了找到导致目标状态的一系列动作，我们重新考虑**状态表示**。我们不再仅仅记录壶中的水量，还存储每个配置是如何获得的。我们将这个新状态表示为一个对 (J,P)：J 是壶配置 (A,B,C) 和以前一样，P 是一个“路径”，它从起始状态通往配置 J。路径是一个 `FromTo Jug1 Jug2` 移动的列表，表示我们从 `Jug1` 倒水到 `Jug2`。对于每个后继状态，我们通过将相应的路径元素追加到其前驱路径的（副本）上来记录它的配置是如何到达的。新程序 (jugs.hs (https://www.metalevel.at/tist/jugs.hs)) 是： ``` data Jug = A | B | C deriving Show data Move = FromTo Jug Jug deriving Show type Path = [Move] type State = ((Int,Int,Int), Path) start :: State start = ((8,0,0), []) successors :: State -> [State] successors ((a,b,c),path) = let ab = min a (5 - b) ac = min a (3 - c) ba = min b (8 - a) bc = min b (3 - c) ca = min c (8 - a) cb = min c (5 - b) ss = [(ab, a-ab, b+ab, c, path ++ [FromTo A B]), (ac, a-ac, b, c+ac, path ++ [FromTo A C]), (ba, a+ba, b-ba, c, path ++ [FromTo B A]), (bc, a, b-bc, c+bc, path ++ [FromTo B C]), (ca, a+ca, b, c-ca, path ++ [FromTo C A]), (cb, a, b+cb, c-cb, path ++ [FromTo C B])] in [((a',b',c'), path') | (amount,a',b',c',path') <- ss, amount > 0] search :: [State] -> Path search (s:ss) | fst s == (4,4,0) = snd s | otherwise = search $ ss ++ successors s ``` 现在很容易找到一个路径： ``` search [start] [FromTo A B,FromTo B C,FromTo C A,FromTo B C,FromTo A B,FromTo B C,FromTo C A] ``` 有几种方法可以使它更高效。例如，我们可以**预置**新的路径元素，并在搜索结束时一次性反转路径。 更重要的是，我们也可以让它更优雅：显然，上面的代码包含一些冗余，我们可以用不同的状态表示来避免。下面的 Prolog 版本说明了这一点： ``` jug_capacity(a, 8). jug_capacity(b, 5). jug_capacity(c, 3). moves(Jugs) --> { member(jug(a,4), Jugs), member(jug(b,4), Jugs) }. moves(Jugs0) --> [from_to(From,To)], { select(jug(From,FromFill0), Jugs0, Jugs1), FromFill0 #> 0, select(jug(To,ToFill0), Jugs1, Jugs), jug_capacity(To, ToCapacity), ToFill0 #< ToCapacity, Move #= min(FromFill0, ToCapacity-ToFill0), FromFill #= FromFill0 - Move, ToFill #= ToFill0 + Move }, moves([jug(From,FromFill),jug(To,ToFill)|Jugs]). ``` 通过这种状态表示，可以统一描述移动，无需显式枚举。我们使用**迭代加深**来找到最短解： ``` ?- length(Ms, _), phrase(moves([jug(a,8),jug(b,0),jug(c,0)]), Ms). Ms = [from_to(a,b),from_to(b,c),from_to(c,a),from_to(b,c),from_to(a,b),from_to(b,c),from_to(c,a)] . ``` **练习**：在 Haskell 版本中使用这种状态表示。 以类似的方式，你可以解决其他涉及搜索的谜题，如“狼和山羊”、8 数码问题、**逃离佐格** (https://www.metalevel.at/zurg/) 以及“传教士和食人者”。 ## 程序中的状态 现在让我们用 Prolog 为一种简单的整数编程语言构建一个**解释器**。使用 Prolog 项，我们将程序表示为抽象语法树 (AST)，例如： ``` function(Name, Parameter, Body) call(Name, Expression) return(Expression) assign(Variable, Expression) if(Condition, Then, Else) while(Condition, Body) sequence(First, Second) ``` 为了在符号上区分算术表达式中的变量和数字，我们分别使用一元函子 "v" 和 "n"。在源代码 (interp.pl (https://www.metalevel.at/tist/interp.pl)) 中查找 **is_program/2** 的定义，以获得所选表示的完整声明式规范。其中还包含一个解析器，可以从更易读的语法自动生成这种项表示。例如，以下程序（递归地）计算并打印第四个卡特兰数 ``` catalan (n) { if (n == 0) { return 1; } else { c = catalan(n-1); r = 2*(2*n + 1)*c / (n + 2); return r; } } print catalan(4); ``` 被转换为如下语法树： ``` ?- string_ast("catalan (n) { if (n == 0) { return 1; } else { c = catalan(n-1); r = 2*(2*n + 1)*c / (n + 2); return r; } } print catalan(4);", AST). AST = sequence(function(catalan, n, if(bin(=, v(n), n(0)), return(n(1)), sequence(assign(c, call(catalan, bin(-, v(n), n(1)))), sequence(assign(r, bin(/, bin(*, bin(*, n(2), bin(+, bin(*, n(2), v(n)), n(1))), v(c)), bin(+, v(n), n(2)))), return(v(r)))))), print(call(catalan, n(4)))) . ``` 要解释这样的程序，我们必须跟踪计算的**状态**。它由以下部分组成： - 变量的绑定环境 - 所有遇到的函数定义 这两者统称为**环境**，表示为一对联接列表：变量名与值的关联，以及函数头与函数体的关联。这使得定义和引用函数以及访问变量分别成为遇到函数和变量数量的 O(log(N)) 操作。 显然，负责解释语法树的谓词定义了这种环境之间以及**状态**之间的关系。这就是我们以纯粹声明式方式解释命令式程序的方法。要相对于当前环境**求值**表达式，我们使用谓词 **eval/3**： ``` eval(bin(Op,A,B), Env, Value) :- eval(A, Env, VA), eval(B, Env, VB), eval_(Op, VA, VB, Value). eval(v(V), Env, Value) :- env_get_var(Env, V, Value). eval(n(N), _, N). eval(call(Name, Arg), Env0, Value) :- eval(Arg, Env0, ArgVal), env_func_body(Env0, Name, ArgName, Body), env_clear_variables(Env0, Env1), env_put_var(ArgName, ArgVal, Env1, Env2), interpret(Body, Env2, Value). eval_(+, A, B, V) :- V #= A + B. eval_(-, A, B, V) :- V #= A - B. eval_(*, A, B, V) :- V #= A * B. eval_(/, A, B, V) :- V #= A // B. eval_(=, A, B, V) :- goal_truth(A #= B, V). eval_(>, A, B, V) :- goal_truth(A #> B, V). eval_(<, A, B, V) :- goal_truth(A #< B, V). goal_truth(Goal, V) :- ( Goal -> V = 1 ; V = 0 ). ``` 访问环境的谓词（**env_get_var/3** 等）是直接的，你可以在源代码中查找它们的定义。最后，谓词 **interpret/3** 规定了我们语言的每个结构如何（如果有的话）改变环境： ``` interpret(print(P), Env, Env) :- eval(P, Env, Value), format("~w\n", [Value]). interpret(sequence(A,B), Env0, Env) :- interpret(A, Env0, Env1), ( A = return(_) -> Env = Env1 ; interpret(B, Env1, Env) ). interpret(call(Name, Arg), Env0, Env0) :- eval(Arg, Env0, ArgVal), env_func_body(Env0, Name, ArgName, Body), env_clear_variables(Env0, Env1), env_put_var(ArgName, ArgVal, Env1, Env2), interpret(Body, Env2, _). interpret(function(Name,Arg,Body), Env0, Env) :- env_put_func(Name, Arg, Body, Env0, Env). interpret(if(Cond,Then,Else), Env0, Env) :- eval(Cond, Env0, Value), ( Value #\= 0 -> interpret(Then, Env0, Env) ; interpret(Else, Env0, Env) ). interpret(assign(Var, Expr), Env0, Env) :- eval(Expr, Env0, Value), env_put_var(Var, Value, Env0, Env). interpret(while(Cond, Body), Env0, Env) :- eval(Cond, Env0, Value), ( Value #\= 0 -> interpret(Body, Env0, Env1), interpret(while(Cond, Body), Env1, Env) ; Env = Env0 ). interpret(return(Expr), Env0, Value) :- eval(Expr, Env0, Value). interpret(nop, Env, Env). ``` 有两件事需要特别注意：第一，`print` 语句产生一个**副作用**：它旨在终端上显示输出，这不能通过转换绑定环境来表达。因此解释器并不完全是逻辑的。要解决这个问题，我们可以将“世界”状态的合适表示纳入我们的环境中，并在遇到 `print` 语句时适当调整它。第二，`return` 语句是特殊的，因为它们产生的环境由一个单一值组成。**eval/3** 谓词在求值时利用了这个特性。