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

先看一段CHR代码[1]，这段代码描述了一个CHR规则。

1
min(X) \ min(Y) <=> X =< Y | true.

如何理解这段代码呢？若min(X)和min(Y)同时出现，且X≤YX \leq Y, 那么删除min(Y)。也就是，min(X)和min(Y)同时出现的时候，删掉大的那一个。

下文的讨论，都基于这段代码。

Declarative和执行顺序

如同这段代码呈现的一样，CHR是一门declarative的语言（声明式语言）。CHR的代码由一个个的规则所组成。这些规则很简单，不外乎是说“当出现什么的时候，替换成什么”。这样的语言，就像一个ini文件[2]一样，只描述“是什么样子”，而不说“应该怎么执行”，就像在C语言中声明一个变量一样。

通常，我们会说，函数式语言（如Haskell、Ocaml等），以及，逻辑式语言（如Prolog），都是“声明式语言”。然而，这种情形下，仅仅只是说，很多这些语言写的程序， “也可以用声明式的方式去阅读和理解它” 。因为，这些语言写的程序，都按照既定的执行顺序[3]去执行，只是有时候， “看起来也可以用声明式的方法去理解哦”。

既然提到了“执行顺序”，那么，就得说一下。 一个真正的声明式语言，是不描述执行顺序的。 因为，这些语言只是在描述“是什么样子”，而不是像别的语言那样是在描述“先执行什么，再执行什么”。这样的语言，CHR算一个。而Mercury则是purely declarative的编程语言。

执行过程、Confluent、Terminating、Well-behaved

那么，一个CHR程序，是怎么执行的呢？

CHR执行的过程，就是在一个给定的Goal上，反复随意的应用这些规则[4]，直到没办法再应用为止。

假设给定这么一个Goal：min(3), min(1), min(4), min(2), min(1), min(2).，那么可以按照这样的顺序来执行（应用规则）。下面的执行过程，用 斜体 来表示每次选中的constraints，用 删除线 表示每次应用规则在选中的constraints上后删除的constraints。
min(3), min(1), min(4), min(2), min(1), min(2).
=> min(3), min(1), min(4), min(1), min(2).
=> min(3), min(1), min(1), min(2).
=> min(1), min(1), min(2).
=> min(1), min(1).
=> min(1).

最后只剩下min(1).。

由于执行顺序是随意的，我们也可以用这样的顺序来执行。
min(3), min(1), min(4), min(2), min(1), min(2).
=> min(3), min(1), min(4), min(2), min(1).
=> min(3), min(1), min(2), min(1).
=> min(1), min(2), min(1).
=> min(1), min(1).
=> min(1).

最后只剩下min(1).。

当然，还可以用很多不同的顺序来执行。而无论以什么顺序执行，最终的结果都是min(1)。其实，不是说所有的CHR程序都只有一个可能的执行结果，大部分时候，不同的执行顺序，会导致不同的执行结果。所以，写出无论什么顺序执行，结果都一致的程序，这很重要。像这个程序一样，无论什么顺序执行，结果都一样，这样的CHR程序，我们说它是 Confluent 的。

一个CHR程序是否是confluent的，是可以通过一定的算法来计算的。所以也就有相应的检查工具。

我们再看这个程序，会发现，无论以什么样的顺序执行，最终都能执行结束。我们称这样的程序，是 Terminating 的。

这里有两个点：

  1. Terminating的准确定义是“no infinite computation”。
  2. 由于CHR是图灵完全的，所以，程序会不会结束，这个是无法确定的（undecidable）。

如果一个CHR程序，既是 Confluent 的，又是 Terminating 的，那么我们说这个程序是 Well-behaved。

并行的天然性

大部分的函数式语言的介绍文章会说函数式程序有利于并行，但这往往显得一厢情愿[5]。然而，CHR程序，天然是可以并行执行的。显然，对于同一个Goal，分成几个不同的组，分别同时应用不同的规则，并不改变程序的语义。

我们还是用min(3), min(1), min(4), min(2), min(1), min(2).作为例子，假设现在首先有两个线程来执行这个Goal，第一个线程执行前半部分[6]，即min(3), min(1), min(4)，第二个线程执行后半部分，即min(2), min(1), min(2)。那么执行过程如下。
min(3), min(1), min(4) min(2), min(1), min(2)
=> min(3), min(1) min(2), min(1)
=> min(1) min(1)

当两个线程都执行完以后，分别都得到结果min(1)。接下来把这两个线程得到的结果合并，得到min(1), min(1)，再继续用一个线程执行最后一次应用，得到最终结果min(1)。

  1. 本文所讲的一切，都是基于CHR的原始语义。 ↩︎

  2. 可能现在很多人已经不知道什么是ini文件了。ini文件是Windows下常见的用来保存信息的格式。类似的文件类型，比方说XML，Java的properties文件，等等。这些文件格式，都是一门声明式语言。（当然，XSLT之类的特殊XML不在此列） ↩︎

  3. 很多初学者认为Haskell语言的程序，是没有执行顺序的。这是不对的。Haskell是一门有严格执行顺序的编程语言。Haskell和通常语言的区别在于，默认lazy evaluation，且只在执行的时候需要到了才会被force。但Haskell是有严格的执行顺序的，并不会因为lazy evaluation就导致“没有执行顺序”。 ↩︎

  4. 这种应用顺序的随机性，不止是说，对Goal中的constraints可以随意选择，如果有多条规则，那么每次可以随意选择一条规则来应用。 ↩︎

  5. 这也是这些文章从来不论证这一点的原因。他们的逻辑往往只是“因为变量不可变，所以有利于并行”。且不说“有利于”不明所以，主流C编译器，首先都会把C语言翻译成一种叫SSA的语言的程序，这种程序的变量就是不可变的，为什么从来没人提“因此，C语言有利于并行”呢？ ↩︎

  6. 这种拆分其实可以是很随意的。这种随意使得一个CHR实现可以灵活决定怎么拆分。 ↩︎