Prolog 入门: 运算
在本章中, 我们将对 Prolog 内置的运算方法进行简介, 并讨论如何使用这些方法解决一些和列表相关的计算问题.
1. Prolog 的内置运算方法
Prolog 提供了基本的面向整数的运算方法. 在此处由于实用性不大, 我们不再讨论面向实数的运算. 首先来讨论整数运算:
我们可以用下述例子展示的方式进行运算或验证运算结果:
1
2
3
4
5
6
7
// verify arithmetic result
?- 114514 is 1919 + 112595.
true
// perform calculation
?- X is 114514 + 1919810.
X = 2034324
此外, 我们还可以在定义谓词时使用预置运算符:
1
2
3
4
5
6
// if we define a predicate as follows...
add_3_and_double(X, Y) :- Y is (X + 3) * 2.
// then it will work!
?- add_3_and_double(114514, X).
X = 229034
同时需要注意的是, Prolog 中定义的数值运算符优先级和我们常识中的一致.
2. 数值算符的一些特性
由于 Prolog 为逻辑型语言, 因此与大部分程序设计语言不同的是, 数值运算符 +, -, *, / 和取模运算符本身 并不执行任何运算. 若我们执行
1
2
3
4
5
6
7
?- X = 114514 + 1919810
~~
或
~~~prolog
?- 114514 + 1919810 = X
我们并不会得到计算结果, 而程序也不会如我们预料的一样执行运算, 而是会单纯地依照内置谓词 =/2 的语法规则将等号一边的算式作为复杂项与另一边的变量 $X$ 相联合.
为了让 Prolog 实际的执行运算, 我们需要使用内置的另一个谓词 is/2. 由于数值预算只是 Prolog 的附加功能而与逻辑语句的处理并非强相关, 因此这一谓词本身 (或者说 Prolog 的运算功能本身) 存在一些限制:
首先, 我们需要求解的算式必须位于 is 谓词的 右侧. 其次, 在执行运算时, 我们必须保证 is 谓词右侧的算式中所有的变量 (如果存在的话) 必须已经被实例化 (也就是赋值).
3. 数值运算与列表
我们还是从一个简单的例子开始探究数值运算与列表数据结构相结合后可以为我们带来的简便性.
考虑对给定列表长度的计算. 显然我们可以结合第三, 四章中的知识, 使用 递归定义 实现一个可计算列表长度的程序:
1
2
3
4
5
6
7
// base case: the empty list has length 0.
len([], 0).
// recursive examining: a non-empty list has
// length 1 + len(T), where len(T) is the length
// if its tail.
len([_|T], N) :- len(T, X), N is X + 1.
我们下面从另一个角度考虑相同的问题. 在本章的前两节中, 我们引入了数值运算. 我们考虑在 Prolog 中构造一个在其他程序设计语言中常见的, 用于存储次数或长度的变量, 并利用加法令其记录循环的深度, 由此计算出列表的长度.
首先定义一个三元谓词 accLen(List, Acc, Length)/2:
其中 List 为我们要计算长度的目标列表, Length 为在最后记录列表最终长度的变量, 数据类型为整数, 直到递归循环结束时才会被赋值. Acc 为用于记录中间值的加法器 Accumulator. 在程序执行伊始, 首先将 Acc 初始化为 $0$, 然后递归地寻找列表的表头, 每次找到一个表头为 Acc $+1$, 直到无法再找到表头 (此时目标列表为空列表, 意味着我们已经遍历了整个列表) 为止, 此时 Acc 就是我们所要的值, 它的值将被联合到 L 上.
1
2
accLen([_|T], A, L) :- Anew is A+1, accLen(T, Anew, L).
accLen([], A, A).
4. 整数的比对
我们下面介绍一些无需内置谓词 is 的辅助就可自行完成计算结果的内置谓词:
它们显然有下列含义:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
?- 114 < 514.
true
?- 114 =< 514.
true
?- 514 =< 514.
true
?- 514 =:= 514.
true
?- 514 =\= 1919.
true
?- 514 =\= 514.
false
?- 514 >= 514.
true
?- 514 > 114.
true
注:
- 上述谓词在执行时会强制将自身 两侧 的复合项视为算式并执行运算.
- 注意谓词
=:=和=的差别. 前者比对的是谓词两侧复合项经过计算后的结果, 而后者直接对项本身进行联合. - 谓词两侧的参数必须被实例化为整数.
下面来看一个结合了累加器 accumulator 和 “>” 运算符的, 用于找出列表中最大元的程序:
1
2
3
accMax([H|T], A, Max) :- H > A, accMax(T, H, Max).
accMax([H|T], A, Max) :- H =< A, accMax(T, A, Max).
accMax([], A, A).
在执行程序时, Prolog 会抽取列表头并选择表头元素的值和 A 中最大的那个为变量 A 赋值, 然后对剩下的表尾执行同样的操作, 知道遍历完整个列表为止, 此时 Max 与累加器 A 联合, Max 的值就是所要求的全表最大值.
而若要考虑表中可能出现非正元素的情形, 我们需要对程序定义稍作修改. 由于在任何情况下作为程序输入的列表始终是非空的, 我们只需要单独取出表头将其作为 A 的初始值即可:
1
max(List, Max) :- List = [H|_], accMax(List, H, Max).
