Prolog 中的全局堆栈错误

发布于 2024-11-25 09:25:14 字数 1070 浏览 1 评论 0原文

我正在尝试在 Prolog 中运行以下程序。

mama_mia1(A,M,LI,HI,LO,HO,AA) :-
   p1(A,M,LI,HI,LO,HO,PROGS),
   reverse(PROGS,PROG),
   atom_chars(AA,PROG),
   !.

p1(_,_,LO,LO,LO,_,[]).
p1(_,_,HO,HO,_,HO,[]).
p1(_,_,LO,HO,LO,HO,[]).
p1(_,_,X,LO,LO,HO,[]) :- X>LO,X<HO.
p1(_,_,X,HO,LO,HO,[]) :- X>LO,X<HO.
p1(_,_,LO,Y,LO,HO,[]) :- Y>LO,Y<HO.
p1(_,_,HO,Y,LO,HO,[]) :- Y>LO,Y<HO.
p1(_,_,X,Y,LO,HO,[]) :- X>LO,X<HO,Y>LO,Y<HO.
p1(A,M,X,Y,LO,HO,PROG) :-
   (  (X1 is X+A,  H1 is HO+1, X1<H1, Y1 is Y+A,  Y1<H1 )
   -> append(PROG1,['A'],PROG),
      p1(A,M,X1,Y1,LO,HO,PROG1)
   ;  false).
p1(A,M,X,Y,LO,HO,PROG) :-
   (  (X2 is X * M,  H1 is HO+1, X2<H1, Y2 is Y * M,  Y2<H1)
   -> append(PROG2,['M'],PROG),
      p1(A,M,X2,Y2,LO,HO,PROG2)
   ;  false).

该程序应计算从 li 和 hi 之间的每个数字到 lo 和 ho 之间的结果的适当的加法和乘法路径。加法对应于字母 A，乘法对应于 M。在程序结束时，我们应该得到与我们找到的路径相对应的 As 和 Ms 字符串。

该程序运行良好，但在尝试测试用例时：

mama_mia1(70000,17,2,5,89000,89900,P)

我收到一条“错误：超出全局堆栈”消息。

任何想法代码有什么问题吗？

原文

I am trying to run the following program in Prolog.

mama_mia1(A,M,LI,HI,LO,HO,AA) :-
   p1(A,M,LI,HI,LO,HO,PROGS),
   reverse(PROGS,PROG),
   atom_chars(AA,PROG),
   !.

p1(_,_,LO,LO,LO,_,[]).
p1(_,_,HO,HO,_,HO,[]).
p1(_,_,LO,HO,LO,HO,[]).
p1(_,_,X,LO,LO,HO,[]) :- X>LO,X<HO.
p1(_,_,X,HO,LO,HO,[]) :- X>LO,X<HO.
p1(_,_,LO,Y,LO,HO,[]) :- Y>LO,Y<HO.
p1(_,_,HO,Y,LO,HO,[]) :- Y>LO,Y<HO.
p1(_,_,X,Y,LO,HO,[]) :- X>LO,X<HO,Y>LO,Y<HO.
p1(A,M,X,Y,LO,HO,PROG) :-
   (  (X1 is X+A,  H1 is HO+1, X1<H1, Y1 is Y+A,  Y1<H1 )
   -> append(PROG1,['A'],PROG),
      p1(A,M,X1,Y1,LO,HO,PROG1)
   ;  false).
p1(A,M,X,Y,LO,HO,PROG) :-
   (  (X2 is X * M,  H1 is HO+1, X2<H1, Y2 is Y * M,  Y2<H1)
   -> append(PROG2,['M'],PROG),
      p1(A,M,X2,Y2,LO,HO,PROG2)
   ;  false).

The program should calculate an appropriate path of additions and multiplications leading from every number between li and hi to a result between lo and ho. An addition corresponds to the letter A and multiplication corresponds to M. At the end of the program we are supposed to get a string of As and Ms corresponding to the path we found.

The program runs well but when trying the test case :

mama_mia1(70000,17,2,5,89000,89900,P)

I get an "ERROR: out of global stack " message.

Any ideas what is wrong with the code?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

寻梦旅人 2024-12-02 09:25:14

程序运行良好，但是......

真的吗？让我们尝试一个最小的情况：

?- p1(1,3,1,1,1,2,P).
   P = []
;  P = "A"
;  loops.

也就是说，即使在这种非常简单的情况下，您的程序也会循环。然而，却偏偏找到了两个答案！第二个答案使用 library(double_quotes) 来打印 "A" 代替 ['A']。

在 Prolog 中，你不会只得到一个答案，你可能会得到几个答案...

直接检测此类非终止问题的一种简单方法是添加一个目标 false 对于您的查询：

?- p1(1,3,1,1,1,2,P), false.
   loops.

我们可以在您的计划中添加更多此类目标false。严格来说，只有当您的程序是纯粹的、单调的程序时，这才有可能。您正在使用 cut 和 if-then-else，它们在一般情况下都会破坏此类属性。但是，就您而言，它们可以在以下 failure-slice

p1(_,_,LO,LO,LO,_,[]) :- false.
p1(_,_,HO,HO,_,HO,[]) :- false.
p1(_,_,LO,HO,LO,HO,[]) :- false.
p1(_,_,X,LO,LO,HO,[]) :- false, X>LO,X<HO.
p1(_,_,X,HO,LO,HO,[]) :- false, X>LO,X<HO.
p1(_,_,LO,Y,LO,HO,[]) :- false, Y>LO,Y<HO.
p1(_,_,HO,Y,LO,HO,[]) :- false, Y>LO,Y<HO.
p1(_,_,X,Y,LO,HO,[]) :- false, X>LO,X<HO,Y>LO,Y<HO.
p1(A,M,X,Y,LO,HO,PROG) :-
   (  (X1 is X+A,  H1 is HO+1, X1<H1, Y1 is Y+A,  Y1<H1 )
   -> append(PROG1,['A'],PROG), false,
      p1(A,M,X1,Y1,LO,HO,PROG1)
   ;  false ).
p1(A,M,X,Y,LO,HO,PROG) :- false,
   (  (X2 is X * M,  H1 is HO+1, X2<H1, Y2 is Y * M,  Y2<H1)
   -> append(PROG2,['M'],PROG),
      p1(A,M,X2,Y2,LO,HO,PROG2)
   ;  false ).

考虑这个目标append(PROG1,['A'],PROG)。变量PROG1在这里第一次出现，因此它从未被实例化。此外，PROG 未实例化。因此这个目标将会循环。

将 append(PROG1,['A'],PROG) 替换为 PROG = ['A'|PROG1]。现在元素以相反的方向出现，因此不需要反转。

查询 mama_mia1(70000,17,2,5,89000,89900,P) 现在就像 false 一样失败。

The program runs well but ...

Really? Let's try out a minimal case:

?- p1(1,3,1,1,1,2,P).
   P = []
;  P = "A"
;  loops.

That is, even in this very simple case your program loops. However, it happened to find two answers! The second answer uses library(double_quotes) for printing "A" in place of ['A'].

In Prolog you do not get just one answer, you may get several of them...

An easy way to directly detect such problems of non-termination is to add a goal false to your query:

?- p1(1,3,1,1,1,2,P), false.
   loops.

We can add further such goals false into your program. Strictly speaking, this is only possible if your program is a pure, monotonic one. You are using cut and if-then-else which both destroy such properties in the general case. However, in your case, they can just be discarded in the following failure-slice

p1(_,_,LO,LO,LO,_,[]) :- false.
p1(_,_,HO,HO,_,HO,[]) :- false.
p1(_,_,LO,HO,LO,HO,[]) :- false.
p1(_,_,X,LO,LO,HO,[]) :- false, X>LO,X<HO.
p1(_,_,X,HO,LO,HO,[]) :- false, X>LO,X<HO.
p1(_,_,LO,Y,LO,HO,[]) :- false, Y>LO,Y<HO.
p1(_,_,HO,Y,LO,HO,[]) :- false, Y>LO,Y<HO.
p1(_,_,X,Y,LO,HO,[]) :- false, X>LO,X<HO,Y>LO,Y<HO.
p1(A,M,X,Y,LO,HO,PROG) :-
   (  (X1 is X+A,  H1 is HO+1, X1<H1, Y1 is Y+A,  Y1<H1 )
   -> append(PROG1,['A'],PROG), false,
      p1(A,M,X1,Y1,LO,HO,PROG1)
   ;  false ).
p1(A,M,X,Y,LO,HO,PROG) :- false,
   (  (X2 is X * M,  H1 is HO+1, X2<H1, Y2 is Y * M,  Y2<H1)
   -> append(PROG2,['M'],PROG),
      p1(A,M,X2,Y2,LO,HO,PROG2)
   ;  false ).

Consider this goal append(PROG1,['A'],PROG). The variable PROG1 occurs here for the first time and thus it is never instantiated. Also PROG is not instantiated. And thus this goal will loop.

Replace append(PROG1,['A'],PROG) by PROG = ['A'|PROG1]. Now the elements occur in opposite direction and thus no reversing is needed.

The query mama_mia1(70000,17,2,5,89000,89900,P) now simply fails just like false did.

回复收藏 0 原文