[博客翻译]Prolog的简洁性

由 发布于 编程语言声明式语言逻辑编程Prolog命令式语言
 收藏

原文地址：https://bitsandtheorems.com/the-simplicity-of-prolog/


Prolog的简洁之美

如今，最流行的编程语言包括Python、Javascript、Java、C++、C#、Kotlin和Ruby，大多数程序员可能熟悉其中一种或多种语言。这些语言之间的切换相对容易（除了可能需要掌握特定的框架知识），因为它们都是命令式（大部分也是面向对象）语言，设计上非常相似。

命令式语言关注的是如何解决问题，通过一系列指令来操作状态。它们的流行有多个原因。首先，它们被认为易于学习，因为可以轻松地将内存中的物理单元想象为存储值，并通过指令进行更新。其次，计算模型与硬件很好地映射，因此命令式语言的指令通常可以轻松地转换为机器代码，并且可以进行大量优化。出于同样的原因，命令式语言比其他编程范式发展得更早，因此历史上得到了更多的支持。

相比之下，声明式语言关注的是描述问题是什么或期望的结果是什么。你可能熟悉的声明式语言的例子是SQL。在指定SELECT语句时，通常并不关心记录是如何检索的，只关心它们是否符合指定的条件。虽然SQL通常不被用作通用编程语言，但我认为它对于不熟悉声明式语言的人来说是一个很好的例子（尽管它实际上是图灵完备的）。声明式语言的实际通用编程语言有多个范式，其中最主要的是函数式编程和逻辑编程。

来源：https://xkcd.com/1033/

使用函数式编程语言的程序员不会编写更新状态的语句。事实上，函数式编程中根本没有状态。相反，他们通过应用和组合函数来转换数据。因此，程序不过是一系列数据转换的链条。函数式语言中的一些概念，如map、fold和filter，现在已经被命令式语言所采用。函数式编程语言中最著名的例子是Haskell。

使用逻辑编程语言的程序员既不编写语句，也不编写函数。在逻辑程序中，你只需定义事物之间的关系，然后可以提出问题，系统会根据这些关系推导出所有可能的答案。这听起来可能非常模糊且繁琐，但实际上并非如此。逻辑编程语言中最著名的例子是Prolog，我们将在本文中对其进行探讨。此外，我们还将比较用Kotlin和Prolog实现一个简单应用程序的差异。在接下来的文章中，我们将使用Prolog来解决一些更复杂的问题。

逻辑编程简介

Prolog是一种简单的语言：它只有少数几种语言结构，因此不需要记住太多的细节。编写良好的Prolog程序通常也很简单，因为它们几乎不会为所解决的问题增加额外的复杂性。然而，Prolog的学习曲线可能较陡峭，因为它与人们通常熟悉的语言有很大的不同。

Prolog中唯一的基本语言结构是事实、规则和查询。这些结构由谓词的逻辑组合构成。简单来说：事实是程序中固有的真命题，规则是条件关系“如果A为真，则B为真”，而查询是我们希望根据系统中的事实和规则得到答案的任何问题。Prolog通过合一（一种高级的模式匹配）来找到这些查询的答案。

事实、规则和查询都是霍恩子句，因此可以说Prolog只有一种语言结构。

让我们从一个例子开始：回文。如果一个序列、字符串或数组在反转其所有元素后保持不变，那么它就是一个回文。我们首先定义列表反转的含义，并用它来定义回文。对于辅助谓词，我们的目标是关联一个列表与另一个列表，使得它们是彼此的反转。

% reverse(A, B) 关联列表A与其反转B
reverse([], []).
reverse([Element|Tail], Reversed) :-
  reverse(Tail, ReversedTail),
  append(ReversedTail, [Element], Reversed).

% 如果列表等于其反转，则视为回文
palindrome(List) :- reverse(List, List).

这段代码以一个注释开头。Prolog中只有单行注释，以百分号开头。

接下来是一个事实。它们写作Fact.——一个谓词后跟一个点。在这里，我们简单地声明空列表的反转是空列表。

然后，我们有一个规则。它们写作Head :- Body.，其中如果Body为真，则推导出Head。Body可以包含多个用逗号分隔的谓词，所有这些谓词都必须成立（因此逗号表示规则体中的合取/“与”），以便推导出Head。在这里，我们在第一个参数中对非空列表进行“模式匹配”（注意[X|Y]表示我们考虑一个列表，其中第一个元素是X，其余部分是Y）。因此，这条规则表示：如果列表的第一个元素是Element，其余部分（可能为空）是Tail，那么该列表的反转是Reversed，前提是Reversed是反转Tail后在其末尾添加Element得到的列表（append(X, Y, Z)表示列表X和Y共同构成列表Z）。以大写字母或下划线开头的单词在Prolog中被视为变量。变量只能绑定一次。

这两个子句完成了reverse的定义，我们现在可以用它来定义palindrome。palindrome的定义由一条规则组成，该规则表示：如果List的反转是其自身，则List被视为回文。

好了，现在怎么办？现在我们可以向系统提问（查询）。查询以:-或?开头，后跟问题。如果查询中有任何变量，系统将告诉我们这些变量的哪些赋值使查询成立。如果没有解决方案，我们将得到false，或者如果查询在变量无关紧要的情况下为真，我们将得到true。

以下是一些reverse的示例查询及其结果：

% [1, 2, 3]的反转是[3, 2, 1]吗？是的。
:- reverse([1, 2, 3], [3, 2, 1]).
true.

% [1,2,3]的反转是空列表吗？不是。
:- reverse([1, 2, 3], []).
false.

% [1, 2, 3]的反转是什么？[3, 2, 1]。
:- reverse([1, 2, 3], X).
X = [3, 2, 1].

% 反转[1, 2, 3]的第一个元素是什么？3。
:- reverse([1, 2, 3], [X, _, _]).
X = 3.

% 如果[A, B, C]的反转是[X, Y, Z]，那么什么必须成立？
:- reverse([A, B, C], [X, Y, Z]).
A = Z, B = Y, C = X.

% 如果反转是[3, 2, 1]，原始列表是什么？
:- reverse(X, [3, 2, 1]).
X = [1, 2, 3].

% 所有互为反转的列表A和B是什么？
:- reverse(A, B).
A = B, B = [];
A = B, B = [_];
A = [_A, _B], B = [_B, _A];
A = [_A, _B, _C], B = [_C, _B, _A];
% 非终止：有无限多个解

（其中_表示“匿名变量”，它可以是任何值，但我们不关心它实际是什么。_A、_B和_C是系统生成的“辅助”变量，用于回答我们的问题。）

这揭示了Prolog的一些有趣特性：我们不需要指定谓词的每个参数，我们可以“多方向”执行代码，如果有多个答案，我们可以得到多个答案（用分号分隔），我们可以“补全”部分解，甚至可以生成所有解——所有这些都使用同一段代码！

同样，以下是一些palindrome的示例查询及其结果：

% [1, 2]是回文吗？
:- palindrome([1, 2]).
false.

% [1, A]何时是回文？
:- palindrome([1, A]).
A = 1.

% [1, A, B, 4 | C]何时是回文？
:- palindrome([1, A, B, 4 | C]).
A = 4, C = [1];
B = 4, C = [A, 1];
C = [B, A, 1];
C = [4, B, A, 1];
% 非终止：有无限多个解

% X何时是回文？
:- palindrome(X).
X = [];
X = [_];
X = [_A, _A];
X = [_A, _, _A];
X = [_A, _B, _B, _A];
X = [_A, _B, _, _B, _A];
X = [_A, _B, _C, _C, _B, _A];
% 非终止：有无限多个解

花点时间欣赏一下，我们只需做很少的工作就能支持所有这些不同的调用方式。此外，试着想想在你熟悉的语言中如何实现这样的功能（测试、补全和生成回文）——这可能需要更多的工作！

你可以在SWISH上玩转这段代码，并尝试一些查询。查询应写在右下角的文本字段中，开头不需要指定:-。（SWISH并非在所有移动设备上都能正常工作。右下角应该有一个蓝色的“Run!”按钮；这个按钮有时不会出现。）

本节中的reverse谓词不应在实际中使用——大多数Prolog实现实际上提供了一个内置版本，性能比我们的实现要好得多。

案例研究：授权系统

让我们考虑一个你可能作为软件工程师需要构建的简单系统：一个跟踪用户、角色和权限的服务，并能够通过角色回答用户是否拥有某个权限。我们将只关注核心应用逻辑，因此抽象掉数据库交互、MVC结构等。我们将用Kotlin（面向对象编程）和Prolog（逻辑编程）分别构建这个系统。

让我们从Kotlin开始。

我们的系统的类图（使用Mermaid生成）可能如下所示：

---
         config:
          class:
           hideEmptyMembersBox: true
        ---
        classDiagram
        class User {
          roles : Set~Role~
          isAuthorized(right: Right) Boolean
        }
        class Role {
          rights : Set~Right~
          isAuthorized(right: Right) Boolean
        }
        class Right
        
        User --* Role : has many
        Role --* Right : has many
        classDef default fill:#f9f,stroke:#333,stroke-width:2px

三个核心组件都被建模为类，角色通过组合属于用户，权限通过组合属于角色。用户的授权检查委托给用户所拥有角色的授权检查。一个实现可能如下所示：

// 类结构
data class User(
  val name: String, 
  val roles: Set<Role>
) {
  fun isAuthorized(right: Right) = roles.any { role -> role.isAuthorized(right) }
}

data class Role(
  val name: String, 
  val rights: Set<Right>
) {
  fun isAuthorized(right: Right) = rights.contains(right)
}

data class Right(val name: String)

// 示例数据
val manage = Right("manage")
val view = Right("view")
val admin = Role("admin", setOf(view, manage))
val supervisor = Role("supervisor", setOf(view, manage))
val employee = Role("employee", setOf(view))
val damian = User("Damian", setOf(admin))
val kai = User("Kai", setOf(supervisor))
val nela = User("Nela", setOf(supervisor))
val anna = User("Anna", setOf(employee))
val reinier = User("Reinier", setOf(employee))

// 主方法
fun main() {
  listOf(damian, kai, nela, anna, reinier).forEach { user -> 
    val canManage = user.isAuthorized(manage)
    val canView = user.isAuthorized(view)
    println("User: ${user.name},\tmanage: $canManage\tview: $canView")
  }
}

你可以在Kotlin Playground中玩转这段代码。

我认为这是典型的面向对象解决方案。虽然它确实解决了问题，但其中涉及了一些不必要的复杂性。例如，User实际上通过组合包含roles这一事实，并没有帮助我们回答系统设计的核心问题：用户是否有权执行特定操作？

如果你只熟悉面向对象语言，你可能甚至没有意识到这种复杂性，因为以类和对象的方式思考是IT和CS课程的重要组成部分，定义类之间的交互是面向对象编程的核心。但无论你是否意识到，这种复杂性都存在，并且可能会影响程序的适应性。

可以通过private可见性修饰符来隐藏组合，例如将roles和rights设为private，但实现仍然依赖于这种有些任意的建模选择，这可能会在软件生命周期中产生影响；如果我们改变了底层行为，我们可能还需要修改我们的对象模型。可见性修饰符只能帮助清理外部接口。

现在，让我们尝试用Prolog做同样的事情。

与其将问题细分为类，我们尝试定义系统中必须保持的关系：授权意味着什么？

% 关系
authorized(User, Right) :- 
  user_role(User, Role), 
  role_right(Role, Right).

% 示例数据
user_role(damian, admin).
user_role(kai, supervisor).
user_role(nela, supervisor).
user_role(anna, employee).
user_role(reinier, employee).

role_right(admin, _).
role_right(supervisor, manage).
role_right(supervisor, view).
role_right(employee, view).

我们已经完成了！记住：以大写字母开头的单词被视为变量。以小写字母开头的单词是“项”（谓词或原子，像admin这样的原子是一种常量）。你可以在SWISH上玩转这段代码。

authorized谓词的定义可以理解为：如果User拥有一个Role，并且该Role拥有该Right，那么你可以说User拥有Right。

和之前一样，我们现在可以查询我们的Prolog系统。例如，我们可以问系统authorized(reinier, manage).是否在我们的程序中成立。由于这不成立，我们得到false。同样，询问authorized(damian, manage).会得到true。

正如我们在介绍中所看到的，Prolog的真正优势在于它的通用性。例如，我们可以问Prolog系统：authorized(nela, Right).，其中第二个参数Right是一个变量。这将返回所有使谓词成立的变量赋值，即返回nela拥有的所有权限。同样，我们可以问相反的问题：authorized(User, manage).，返回所有有权manage的`U