prolog dcg限制

Question

我想用DCG作为发电机.截至目前,语法是

s-->a,b.
a-->[].
a-->a,c.
c-->[t1].
c-->[t2].
b-->[t3].
b-->[t4].

我想生成所有s地方的长度a是< someNumber.

使用?- phrase(a,X),length(X,Y),Y<4.i可以获得 a少于4项的所有内容.但是,当所有组合都用尽时,系统(SWI-Prolog 6.2.5)似乎停滞不前.有时候,这里也提出了类似的问题.但是,作为Prolog的新手,我无法使用上面的语法.有任何想法吗？

更新:(canrememberthename)有一个评论被删除,不知何故.无论如何,有人建议between(1,4,Y),length(X,Y),phrase(a,X).用来设定限制.将代码更改为后,这很有效a-->c,a.

Answer 1

进入Prolog的第一步往往有点困难.但是你走在正确的轨道上:

目前,您的问题是您得到了一些预期的答案/解决方案,但随后系统停滞不前; 事实上,它处于无限循环中.你通过耐心地击打发现了这一点SPACE.这可能适用于一小组解决方案,但是对于更大的解决方案来说,这将是乏味的.想想看看所有短于20的句子.

有一个简单的键盘和腕管友好的方式来模拟击球空间:只需false在最后添加一个目标,如下所示:

?- phrase(a,X),length(X,Y),Y<4, false.

Prolog能回答这个问题吗？由于false最后,Prolog没有太多选择:它要么自己回答false; 或者它循环(或产生错误或产生一些副作用).在这种情况下,它循环.

现在,我们可以通过false在您的计划中添加更多目标来缩小问题范围.

?- phrase(a,X),length(X,Y),false, Y<4, false.
**LOOPS**

为了使其更易读,我将只使用一个false目标并查看查询的其余部分:

?- phrase(a,X),length(X,Y),false, Y<4.
**LOOPS**

让我们进一步减少:

?- phrase(a,X),false,length(X,Y),Y<4.
**LOOPS**

他们都循环!但是我们得到了一些有趣的见解:由于这些false多样化的查询不会终止,原始程序也不会终止.因此,当您查看查询,并且第一个目标不会自行终止时,整个查询将不会终止(请参阅最后的细则以获取更多信息).

因此:你必须以某种方式解决第一个目标!

我的第一次尝试是交换length和phrase:

?- length(X,Y), phrase(a,X), Y<4.

这会有用吗？只看循环的第一个目标:

?- length(X,Y), false, phrase(a,X), Y<4.

所以这再次不会终止.

您必须再次更改程序:

?- between(1,3,Y), length(X,Y), false, phrase(a,X).
false.

所以这终止了.如果有终止问题,phrase(a,X)现在要承担责任:

?- between(1,3,Y), length(X,Y), phrase(a,X), false.
**LOOPS**

你可能想看看实际的答案:

?- between(1,3,Y), length(X,Y), phrase(a,X).
Y = 1,
X = [t1] ;
Y = 1,
X = [t2] ;
ERROR: Out of local stack

您可能会得出结论,这种行为比您原来的定义更糟糕.毕竟,我们现在的答案比以前少.但究竟那种推理不帮你改善终止:随着两者是同一种不正确的,你必须解决这个第一.因此,通过隐藏答案,您可以更好地专注于其余部分.false

但为什么你的语法有问题呢？我们可以继续使用我们的技术来插入目标false以缩小范围.但是这次你的语法.用目标装饰的程序false称为故障切片.

只是一个实用的评论:当我在你的程序中插入false时,我将保存程序并输入makeSWI:以这种方式快速重新编译程序.

尝试了一下之后,我得到了以下最小的失败切片.请注意,在DCG中,false必须写为{false}.

?- between(1,3,Y), length(X,Y), phrase(a,X), false

s--> {false}, a,b.

a-->[], {false}.
a-->a,{false},  c.

c-->{false}, [t1].
c-->{false}, [t2].

b-->{false}, [t3].
b-->{false}, [t4].

几乎所有代码库都属于false!所以你必须解决微小的可见剩余部分.在其他地方改变一些东西是毫无意义的.这a --> a, ...必须改变!事实上,改变它来a --> c, s解决问题.

你为什么一开始写作a --> a, c.？我怀疑你想以公平的方式列举所有解决方案.新版本没有:

?- phrase(a,X).
X = [] ;
X = [t1] ;
X = [t1, t1] ;
X = [t1, t1, t1] ;
X = [t1, t1, t1, t1] ;
X = [t1, t1, t1, t1, t1] ;
X = [t1, t1, t1, t1, t1, t1] ;
X = [t1, t1, t1, t1, t1, t1, t1] ...

这看起来非常令人生畏.事实上,它看起来是错误的.不是吗？但是不要让你混淆:我们这里有无限的句子.所以Prolog唯一正确的回答是产生无限多的答案.因为,如果它们是有限的,一些列表将会丢失!但是,当然,你希望以公平的方式列举它们.要得到这个,只需写:

?- length(X,N),  phrase(a,X).
X = [],
N = 0 ;
X = [t1],
N = 1 ;
X = [t2],
N = 1 ;
X = [t1, t1],
N = 2 ;
X = [t1, t2],
N = 2 ;
X = [t2, t1],
N = 2 ;
X = [t2, t2],
N = 2 ;
X = [t1, t1, t1],
N = 3 ...

这是Prolog计划的一个重点:始终首先寻找最好的(可能的)终止财产.并且不要看Prolog如何列举答案的准确顺序.因为,如果一个程序具有更好的终止属性,那么使用它以公平的方式枚举所有解决方案是非常重要的.但是:以更公平的方式列举无限多个解决方案而牺牲终止的程序不能用于更有趣的情况.

_{精细打印
请参阅此答案.}

Answer 2

非终结符 a//0都是递归和“epsilon”（生成空序列），phrase/2 将在空产生式之后立即循环。

您可以解决边界列表长度问题：

?- between(1,4,Y),length(X,Y),phrase(a,X).

并且，正如您已经完成的那样，删除左递归。