为什么我的序言规则陷入无限递归 [英] Why does my prolog rule get stuck in infinite recursion

问题描述

我的代码按其预期目的工作，但最后总是卡在循环中，给我一个错误，提示超出堆栈限制".我的代码如下:

My code works for its intended purpose but always gets stuck in a loop at the end giving me an error saying "Stack limit exceeded." My code is below:

byCar(auckland,hamilton).
byCar(hamilton,raglan).
byCar(valmont,saarbruecken).
byCar(valmont,metz).
   
byTrain(metz,frankfurt).
byTrain(saarbruecken,frankfurt).
byTrain(metz,paris).
byTrain(saarbruecken,paris).
   
byPlane(frankfurt,bangkok).
byPlane(frankfurt,singapore).
byPlane(paris,losAngeles).
byPlane(bangkok,auckland).
byPlane(singapore,auckland).
byPlane(losAngeles,auckland).


travel(X,Y):- byCar(X,Y).
travel(X,Y):- byTrain(X,Y).
travel(X,Y):- byPlane(X,Y).
travel(X,Y):- travel(X,Z), travel(Z,Y).

推荐答案

当你调用类似 travel(metz, To) 之类的东西时，travel/2 的最后一个子句将使用新变量 Z 调用 travel(metz, Z)，然后使用新变量 travel(metz, Z2) 调用 travel(metz, Z2)代码>Z2，依此类推.

When you call something like travel(metz, To), the last clause of travel/2 will call travel(metz, Z) with a new variable Z, which can then call travel(metz, Z2) with a new variable Z2, and so on.

这个问题叫做左递归":你有一个递归调用，相当于原来的目标一直向左"；(即，在开头)子句.解决办法是取得一些进展".在递归调用之前.在这种情况下，您可以在递归前走一跳:

This problem is called "left recursion": You have a recursive call that is equivalent to the original goal all the way "to the left" (i.e., at the beginning) of a clause. The solution is to "make some progress" before a recursive call. In this case, you can travel one hop before the recursion:

step(X, Y) :-
    byCar(X, Y).
step(X, Y) :-
    byTrain(X, Y).
step(X, Y) :-
    byPlane(X, Y).

travel(X, Y) :-
    step(X, Y).
travel(X, Z) :-
    step(X, Y),
    travel(Y, Z).

现在终止:

?- travel(metz, To).
To = frankfurt ;
To = paris ;
To = bangkok ;
To = singapore ;
To = auckland ;
To = hamilton ;
To = raglan ;
To = auckland ;
To = hamilton ;
To = raglan ;
To = losAngeles ;
To = auckland ;
To = hamilton ;
To = raglan ;
false.

正如 false 在评论中指出的那样，您可以使用通用谓词来捕获这种闭包:自反传递闭包的定义.或者，一些 Prolog 系统提供了一种称为表格"的功能.您可以使用它来避免此类问题:https://www.swi-prolog.org/pldoc/man?section=tabling-non-termination

As pointed out in a comment by false, you can use a general predicate to capture this kind of closure: Definition of Reflexive Transitive Closure. Alternatively, some Prolog systems provide a feature called "tabling" which you can use to avoid this kind of problem: https://www.swi-prolog.org/pldoc/man?section=tabling-non-termination

这篇关于为什么我的序言规则陷入无限递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！