Constraint Handling Rules 从入门到精通（一） - 如何用三行代码写一个最短路径

本文根据笔者2017年的一次讲座整理。

那今天我就给大家介绍一门新的编程语言，叫Constraint Handling Rules（缩写CHR）。CHR和C/C++等主流语言一样，是一门general purpose编程语言，换句话说，就是什么都能写。然而大多数时候，这个语言被实现为一个库。最主流的实现，是Leuven CHR System，被集成于各大主流Prolog实现中。下文若没有特别说明，例子代码都是在Prolog实现中自带的Leuven CHR System中执行。

在讲CHR之前，先让我装装逼，同时也让你们对CHR有个高大上的印象。

CHR被称为“超高级”的编程语言。一个语言越“高级”，通常也就带来越高的表达能力和更短的代码。同时，CHR的效率是非常高的！

“超高级”的CHR

下面借用Jon Sneyers的PPT，从一个简单的例子讲起。

先看这个图。

图中，每两个点(专业叫法是“顶点”)之间的箭头叫做“边”，箭头表示可以从一个点到另一个点，箭头上的数字表示从一个点到另一个点的距离(专业叫法是“权”)。

那么，在这个图中，如果找出从a点到e点最短的路径，会是什么呢？

显然，有两条路径，a->d->e或者a->b->c->d->e， 如图所示。每一条路径的长度都是5，图中每一种颜色表示一条最短路径。

如果用计算机来计算，经典有效的算法就是dijkstra算法了。就是你们数据结构课上讲的那些咯。（没上过课的，可以看下图体验下）

对应不同语言的话，实现这个算法的程序的长度也不同。如下图。

从图中我们看到，等级越高，代码量也越短，而最后的CHR版本只需要3行代码！下面解释这段CHR代码。

如果使用Leuven CHR System，那么每一个CHR程序，同时也是PROLOG程序。这些CHR程序会被编译成Prolog程序再执行。CHR的语法其实也是Prolog语法，互相调用非常简单直接，可以直接混合两种语言的代码。

第一个CHR程序

下面解释下如何理解图中的程序。

% 将 source(V) 替换成 distance(V, 0)。
source(V) <=> distance(V, 0).

% 若同时出现 distance(V, D1) 和 distance(V, D2)（不管以什么顺序出现），且D1 =< D2，则
% 去掉 distance(V, D2)。
% 两个到V点的距离，删掉小的；或者两个一样大的删掉其中一个。
distance(V, D1) \ distance(V, D2) <=> D1 =< D2 | true.

% 若同时出现 distance(V, D) 和 e(V, C, W) (不管以什么顺序出现)，则替换成distance(C, D + W)。
% 实际上就是，从V点出发，找到下一个能到达的点，计算到下一个点的距离。
distance(V, D), e(V, C, W) ==> distance(C, D + W).

在这个程序中，我们用e(X,Y,W)表示可以从点X移动到点Y，且距离为W，例如，e(a,b,1)表示从a到b的距离为1。用source(V)表示开始点，例如，source(a)表示起始点为a。用distance(V,D)表示从起始点到点V的距离为D。将图的信息用这些符号罗列出来，程序会被自动执行。如下所示。

1. 大写字母开头的是变量。

2. 执行的过程其实很简单，就是按照给出的这些初始数据，反复套用上面的几条规则。“运气好”就出结果了。这里先卖个关子，后续的文章会深入讲解。

?- e(a, b, 1), e(b, e, 5), e(b, c, 1), e(a, c, 3), e(c, e, 6), e(c, d, 2), e(a, d, 4), e(d, e, 1), source(a).
e(d, e, 1),
e(a, d, 4),
e(c, d, 2),
e(c, e, 6),
e(a, c, 3),
e(b, c, 1),
e(b, e, 5),
e(a, b, 1),
distance(c, 0+1+1),
distance(b, 0+1),
distance(e, 0+4+1),    <---  这是a点到e点的最短路径。
distance(d, 0+4),
distance(a, 0).

结果列出了所有从a开头所到达的点的最短距离。这正是dijkstra算法的中间过程和结果。其中，distance(e, 0+4+1)显示了从a到e的最短距离是0+4+1。

第一次改进

尽管我们已经得到了想要的结果，然而，这段程序有个问题：所有的距离都以每条经过的边的距离相加的式子来表示。这是因为，在Prolog中所做的一切，都是在对源代码进行操作，也就是所谓的“元编程”。和Lisp不同，Prolog并不区分代码和数据。所以，当我们写1+2来计算距离的时候，并不会被当成是计算1+2的值，而是保留了源码1+2所应该具有的原始形式。源码中使用D+W计算距离，所以结果也保留了相应的源码形式。

有的CHR实现，特别是那些不是在Prolog系统中运行的CHR实现，有的会自动计算表达式的值。

若要求和，必须调用Prolog的is/2，这个谓词（相当于“函数”）可以把数学式子的结果算出来。改进后的代码如下。

source(V) <=> distance(V, 0).
distance(V, D1) \ distance(V, D2) <=> D1 =< D2 | true.
distance(V, D), e(V, C, W) ==> DW is D + W, distance(C, DW).    % 这里加入is/2，解释执行D+W这条表达式的值。

执行结果如下。

?- e(a, b, 1), e(b, e, 5), e(b, c, 1), e(a, c, 3), e(c, e, 6), e(c, d, 2), e(a, d, 4), e(d, e, 1), source(a).
e(d, e, 1),
e(a, d, 4),
e(c, d, 2),
e(c, e, 6),
e(a, c, 3),
e(b, c, 1),
e(b, e, 5),
e(a, b, 1),
distance(c, 2),
distance(b, 1),
distance(e, 5),   <-- 这里已经不再是0+4+1了。
distance(d, 4),
distance(a, 0).

大功告成！distance(e, 5)就是我们想要的结果。

第二次改进

接下来，我们让程序在找出最短距离的同时，记录这条最短路径都经过哪些点。同时，我们把D1 =< D2改成D1 < D2，使得相同最短距离的两条路径不会被删除。

1. 这里我们引入了Prolog中list的语法，先不要急着看懂，不过相信接触过函数式编程语言的通常也能看懂。

2. 下划线开头的也是变量，不过这个变量是我们不关心的，只是必须写出来。通俗点说，就是起到个占位符的作用。

source(V) <=> distance([V], 0).
distance([V|_], D1) \ distance([V|_], D2) <=> D1 < D2 | true.
distance([V|T], D), e(V, C, W) ==> DW is D + W, distance([C, V|T], DW).

执行结果如下。

?- e(a, b, 1), e(b, e, 5), e(b, c, 1), e(a, c, 3), e(c, e, 6), e(c, d, 2), e(a, d, 4), e(d, e, 1), source(a).
e(d, e, 1),
e(a, d, 4),
e(c, d, 2),
e(c, e, 6),
e(a, c, 3),
e(b, c, 1),
e(b, e, 5),
e(a, b, 1),
distance([e, d, c, b, a], 5),
distance([d, c, b, a], 4),
distance([c, b, a], 2),
distance([b, a], 1),
distance([e, d, a], 5),
distance([d, a], 4),
distance([a], 0).

在这个执行结果中，从a到e的所有最短路径都被找出来了。distance([e, d, c, b, a], 5)和distance([e, d, a], 5)展示了到终点e距离最短的两条线路。

第三次改进

前边的程序，都有个问题，就是把中间结果都显示出来了。如果我们不想要看到中间结果呢？用destination(X)表示终点为X，再加一条规则，删除这些中间结果。

source(V) <=> distance([V], 0).
distance([V|_], D1) \ distance([V|_], D2) <=> D1 < D2 | true.
distance([V|T], D), e(V, C, W) ==> DW is D + W, distance([C, V|T], DW).

% 当 destination(V1) 和 distance([V2|_], _) 同时出现的时候（无论以什么顺序），且 V1 ≠ V2，则
% 删掉 distance([V2|_], _) 。
% 其实就是删掉所有和 destination(V1) 不一样的中间结果。 destination(V1) 指定了最终节点。
destination(V1) \ distance([V2|_], _) <=> V1 \== V2 | true.

执行结果如下。

?- e(a, b, 1), e(b, e, 5), e(b, c, 1), e(a, c, 3), e(c, e, 6), e(c, d, 2), e(a, d, 4), e(d, e, 1), source(a), destination(e).
e(d, e, 1),
e(a, d, 4),
e(c, d, 2),
e(c, e, 6),
e(a, c, 3),
e(b, c, 1),
e(b, e, 5),
e(a, b, 1),
destination(e),
distance([e, d, c, b, a], 5),
distance([e, d, a], 5).

这样，就只保留了到终点的距离和路径。我们再加一条规则，把destination(e)也删除掉。程序如下。

source(V) <=> distance([V], 0).
distance([V|_], D1) \ distance([V|_], D2) <=> D1 < D2 | true.
distance([V|T], D), e(V, C, W) ==> DW is D + W, distance([C, V|T], DW).
destination(V1) \ distance([V2|_], _) <=> V1 \== V2 | true.

% 删掉所有的 destination(_)。
destination(_) <=> true.

执行结果如下。

?- e(a, b, 1), e(b, e, 5), e(b, c, 1), e(a, c, 3), e(c, e, 6), e(c, d, 2), e(a, d, 4), e(d, e, 1), source(a), destination(e).
e(d, e, 1),
e(a, d, 4),
e(c, d, 2),
e(c, e, 6),
e(a, c, 3),
e(b, c, 1),
e(b, e, 5),
e(a, b, 1),
distance([e, d, c, b, a], 5),
distance([e, d, a], 5).

大功告成！

类型系统

和Prolog不同，使用 Leuven CHR System 写的CHR程序，每一个约束都必须被声明以区别于通常的Prolog谓词。 Leuven CHR System 也有自己一套独立于Prolog的类型系统。下面演示一下如何声明这个程序。

% 每一个约束都要声明。声明的同时，可以指定类型和mode（例如这里的“+”号）。
% 除了指定都有哪些constraint以外，类型和mode都是可以省略的。
% 指定类型、mode以后，编译的过程会进行静态类型检查，类型检查不通过的话会编译失败。指定类型以后，编译后的代码
% 性能将会明显提升。
% CHR的类型系统和Prolog是不一样的，CHR有自己的基础类型（如下面的number, any等）。
:- chr_constraint e(+node, +node, +length),
                  source(+node),
                  destination(+node),
                  distance(+list(node), +length).

% 自定义类型是允许的。
% 支持带参数的类型（类似Java的泛型），也支持代数数据类型。
:- chr_type list(T) ---> [] ; [T|list(T)].
:- chr_type length == number.
:- chr_type node == any.

这里有几点必须说明。

1. 类型声明不是必须的，但是指定了的话，编译后程序的速度会快很多。

2. 有一点和erlang和prolog很不同。在erlang和prolog中，指定了类型也没什么实际的作用，那主要是给人看的，编译的时候并不做检查。但是CHR如果指定了类型就会进行静态检查，类型错误是无法编译过去的。

3. 诸如source(V), distance([V], 0)的所有的这种形式的东西，在chr中叫做约束（constraint）。

完整的程序

下面给出完整的最终程序^[1]。

% CHR作为Prolog的一个模块出现，开头还是要引入这个模块的。
:- use_module(library(chr)).

% 启用优化编译。默认是不优化的。
:- chr_option(optimize, full).

% 每一个约束都要声明。声明的同时，可以指定类型和mode（例如这里的“+”号）。
% 除了指定都有哪些constraint以外，类型和mode都是可以省略的。
% 指定类型、mode以后，编译的过程会进行静态类型检查，类型检查不通过的话会编译失败。指定类型以后，编译后的代码
% 性能将会明显提升。
% CHR的类型系统和Prolog是不一样的，CHR有自己的基础类型（如下面的number, any等）。
:- chr_constraint e(+node, +node, +length),
                  source(+node),
                  destination(+node),
                  distance(+list(node), +length).

% 自定义类型是允许的。
% 支持带参数的类型（类似Java的泛型），也支持代数数据类型。
:- chr_type list(T) ---> [] ; [T|list(T)].
:- chr_type length == number.
:- chr_type node == any.

% 每一行是一条规则。@前边是规则的名称，名称是不必要的，仅仅是给人看的。
% <=>, ==> 左边是头部，右边是body。
% 大写字母是个逻辑变量，简称变量。头部的内容充当pattern，当匹配的时候进行替换。“_”是特殊的变量，作用仅仅充当
% 占位符，任意两处“_”都是不同的变量。

% 将 source(V) 替换成 distance([V], 0)。
init @ source(V) <=> distance([V], 0).     

% 若同时出现 distance([V|_], D1) 和 distance([V|_], D2)（不管以什么顺序出现），且D1 < D2，则
% 去掉 distance([V|_], D2)，并替换成“true”。
% 则实际上相当于两个到V点的距离，删掉小的那个（相等的会被保留哦）。
% 由于“替换成true”并不会产生什么实际作用，在这里仅仅是由于语法上的需要而补上的没有意义的内容。
min_distance @ distance([V|_], D1) \ distance([V|_], D2) <=> D1 < D2 | true.

% 若同时出现 distance([V|T], D) 和 e(V, C, W) （不管以什么顺序出现），则替换
% 成 DW is D + W, distance([C, V|T], DW) 。
% 实际上就是，从V点出发，找到下一个能到达的点，计算到下一个点的距离。
% 若直接写 distance([C, V|T], D + W) ，则算出来的结果会是“x+y+z+...”的形式，将整一条路径上的所有
% 权重的相加过程给表现出来。毕竟Prolog的一切操作，都在直接操作源代码文本，也就是从头到尾彻底滴在进行元编程。
% 这里调用is/2，A is expression的作用是，解释执行expression，然后将计算结果和A进行unify，在这里相当于
% 把DW初始化成相加的结果。
add_node @ distance([V|T], D), e(V, C, W) ==> DW is D + W, distance([C, V|T], DW).

% 当 destination(V1) 和 distance([V2|_], _) 同时出现的时候（无论以什么顺序），且 V1 ≠ V2，则
% 删掉 distance([V2|_], _) 。
% 其实就是删掉所有和 destination(V1) 不一样的中间结果。 destination(V1) 指定了最终节点。
destination(V1) \ distance([V2|_], _) <=> V1 \== V2 | true.

% 删掉所有的 destination(_) 。毕竟这个看起来很碍眼啊！
destination(_) <=> true. 

---

1. 本文的所有示例程序可以在这里下载。 ↩︎