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

尽管CHR是一门 General Purpose 的编程语言，可以像C/C++那样用来做任何通用工作。然而，目前已有的实现，都是将CHR实现成一门嵌入式语言，就像lua那样。

CHR的语法，本身也是Prolog语法。这样做的好处是，CHR程序可以和Prolog程序混合在一起，让人毫不察觉。而对于那些不想和Prolog代码混合在一起的CHR实现来说，这似乎并没有什么好处，这些实现同样采用Prolog风格的语法。

让我们先从Prolog语法讲起，让大家有一个简单的印象即可。对于熟悉Prolog的同学，可以直接跳过这一节。

Prolog 语法基础

Prolog的语法[1]十分的简单，只有一种形式，也就是 Term 。下面具体说说。

Terms

Term分成两大类，一种是变量和不可再细分的，另一种是Compound Term。

Atoms

  1. 小写字母开头，字母、数字、下划线都可使用。如 abc,a11 , …

  2. 如果用单引号包裹，可以是任意内容（是否能跨行则看具体实现），如 'Abc111' , '_f3' , …

  3. 通常用作 identifier。

Numbers

数字（包括整数和浮点数），如 3,4, 5.5, …

Variables

  1. 变量以大写字母或者下划线开头为，如 Var, Hello, _Wo333, …

  2. 名为_ 的变量为匿名变量，通常用做占位符，不能被引用。

  3. 名为_XXX 的变量，若没有被引用到，编译器也不会警告。

  4. 变量有两种状态（instantiatedness），分别是：

    • Free：变量刚开始的状态是Free，这时候变量没有和任何一个值进行绑定。
    • Ground：变量经过unification以后，变量已有值，值不可改。

Compound Term

  1. 所有符合foo(xxx,xxx,...)形态的都是Compound Term，括号里是参数。

  2. 如果不在意参数内容的话，"带Arity个参数的foo"可以用foo/Arity来描述，例如： f/3, f/10 , …

    • Atom 可以看成是 arity 为 0。例如，foo可以看成是foo()，也可以用foo/0来描述。

  3. [xxx,xxx,...]叫 list 。list 也是一种 Compound Term，为了方便，给了相应的词法支持。empty list，也就是[]，这是一个 atom 。而普通的list，像[1,2,3]相当于[1|[2|[3|[]]]]。[H|T]这种结构称为 cons，H部分称为 head，T部分称为 tail，[H|T]对应的 Compound Term 为 '.'(H,T)。

Unification

通俗讲，unifucation 就是通过类似解方程那的方法，让等式左右两边看起来一样。

例如，为了让p(1,t(B)) + D = p(A,C) + 4左右两边的形态保持一致，那么求出来其中的变量的值如下。

1
2
3
4
?- p(1,t(B)) + D = p(A,C) + 4.
D = 4,
A = 1,
C = t(B).

把求出来的变量的值代入原等式，你会发现等式两边的形态变成了一样。

在 unify[2] 以后，式子中的所有变量，都将和具体的值绑定，变量的状态也从 free 变成 ground。当然，这个例子中的B是个例外，这个变量不管有没有值，是什么值，都是可以的，所以这里在 unify 以后，B仍保持 free 状态。

显示 Uniication 通过 =/2 或者 unify_with_occurs_check/2 来达成。在调用的过程中，也会自动进行 unification 。在本系列前边的文章中，例如min(X)匹配min(1)，之后可以得到X=1，可以先粗浅的按照 unification 来理解[3]。

Prolog 程序的结构

Prolog不区分所谓的“数据”和“代码”。所有的代码和数据结构都只有一个形式，也就是Term。也许你看到的Prolog代码是这样的：

1
2
3
hello :-
	write('hello world'), 
	nl.

“这似乎有点语法哦！”

实际上，这是一个 Compound Term[4] 。对于Prolog来说，是像下面这个样子。

1
:-(hello,','(write('hello world'),nl))

在 Prolog 中，可以把任意 atom 定义成一个操作符。例如，把+定义成中缀操作符[5]以后，3+4就会被理解成+(3,4)这样的 Compound Term 。Prolog 通过不同运算符的优先级和结合性，来使得代码更容易阅读。

这段程序可以理解为：调用:-/2来定义一个叫hello的谓词 。类似C中的“函数”，Prolog对应的叫“谓词”。谓词没有返回值，执行的结果只有 true 和 fail （类似返回值）。

Prolog 程序的执行，可以看成是一个个对谓词的调用，就这么简单。但是，Prolog 和 C 之类的有一点不同。例如，f(g(3))对于C来说，会先调用g(3)再把返回值丢给f；而 Prolog 只调用 f， 且把 g(3) 作为参数传给 f，由 f 决定怎么处理 g(3) 。

在 Prolog 代码中嵌入 CHR 代码

由于 Prolog 语法的特性，在 Prolog 代码中嵌入 CHR 代码变得十分简单。对于流行的K.U.Leuven CHR system来说，只需要在 Prolog 中定义两个操作符 ==> 和 <=>，语法就搞定了。CHR编译器再把这些CHR代码编译成 Prolog 代码以后，使用上和普通的 Prolog 代码没有差别。

  1. 这里是指ISO Prolog的语法。 ↩︎

  2. “Unify” 是指这个动作，动词。“Unification” 是指这件事，名词。 ↩︎

  3. 其实并不是。CHR的机制还是有些不一样的。 ↩︎

  4. 结尾的.起到一个分隔符的作用。 ↩︎

  5. +这个运算符已经内置了，不需要再自己定义。 ↩︎