如何让含DCG的Prolog查询终止？（SWI-Prolog 8.4.3）

将alphanum/1的DCG规则调整为先约束字符类型，再匹配字符，即可在保留原功能的前提下让查询正常终止：

foo([]) --> [].
foo([Start|Rest]) --> alphanum(Start), foo(Rest).

alphanum(Ch) --> { char_type(Ch, alnum) }, [Ch].

原理说明 #

原规则的执行顺序存在问题：

• 先匹配任意字符到变量Ch
• 再通过char_type(Ch, alnum)过滤合法字符

在生成模式下（即需要构造满足条件的列表I），Prolog会先尝试所有可能的字符（Unicode中字母数字字符数量极大），再过滤合法值，回溯时会持续生成新的字符，导致查询看似无法终止。

调整后的规则修正了执行顺序：

• 先通过char_type(Ch, alnum)枚举所有合法的字母数字字符（有限集合）
• 再匹配对应的列表元素[Ch]

由于合法字符的数量是有限的，Prolog会枚举完所有长度为2的字母数字组合后，正常终止查询，同时完全保留原程序的功能——仅匹配或生成由字母数字组成的列表。

验证 #

在SWI-Prolog 8.4.3环境中执行原查询：

length(I, 2), phrase(foo(C), I), false.

调整后的程序会完成所有可能组合的枚举，最终正常终止。

内容的提问来源于stack exchange，提问作者Edgar