代码之家 › 专栏 › 技术社区 › Eusebius

太多的回溯:为什么这里有一个“重做”?

successor-arithmetics backtracking prolog

2

Eusebius · 技术社区 · 13 年前

我在Prolog中做了一个非常简单的练习,其中有一些我不理解的地方。该程序是一个“大于”( > )关于表示为后继的整数:

greater_than(succ(_), 0).
greater_than(succ(A), succ(B)) :-
  greater_than(A, B).

我的问题是:我不明白为什么提出这个要求 greater_than(succ(succ(succ(0))),succ(0)) 生成 redo 在以下跟踪中:

[trace] ?- greater_than(succ(succ(succ(0))),succ(0)).
Call: (6) greater_than(succ(succ(succ(0))), succ(0)) ? creep
Call: (7) greater_than(succ(succ(0)), 0) ? creep
Exit: (7) greater_than(succ(succ(0)), 0) ? creep
Exit: (6) greater_than(succ(succ(succ(0))), succ(0)) ? creep
true ;
Redo: (7) greater_than(succ(succ(0)), 0) ? creep
Fail: (7) greater_than(succ(succ(0)), 0) ? creep
Fail: (6) greater_than(succ(succ(succ(0))), succ(0)) ? creep
false.

为什么有 重做 在这里我怎样才能避免它(当然没有伤口)?

顺便说一句,在你问之前:不,这不是什么家庭作业。。。

2 回复 | 直到 12 年前

1

2

Will Ness Derri Leahy 13 年前

好吧,这是一个编译器优化,给定的编译器/版本组合可能有,也可能没有。

SWI的后续版本不存在此问题。可能与 子句索引 。这种行为将在没有索引的实现上出现,或者仅在第一个参数上进行索引。

但显然, "SWI-Prolog provides `just-in-time' indexing over multiple arguments" .SWI 5.6.56手册 states “最多可以索引4个参数”。所以它可能会索引不止一个。

2

0

Thanos Tintinidis 13 年前

之所以有重做,是因为prolog无法推断(在不检查的情况下),通过遵循下一个子句,是否会有替代解决方案。的确,在这种情况下,这只是一次头部统一检查(并不是说这总是微不足道的),但它可能需要花费大量时间(甚至永远不会终止)。

现在,这正是你应该使用cut的地方:你知道额外的选择点不会产生解决方案(所以你没有改变语义——绿色切割)。或者(但它主要是覆盖切口的句法糖),你可以使用if-then-else:

greater_than(succ(A), B):-
    B = succ(BI) ->
    greater_than(A,BI)
    ; B = 0.

并不是说这仍然会进行额外的计算,而这些计算可以通过cut来避免。

附言:我怀疑有人会认为这是家庭作业XD