3

我目前正试图在 Prolog 中解决一个简单的“乘 peano 整数”问题。

基本规则

  • 一个peano整数定义如下：0 -> 0；1 -> s(0); 2 -> s(s(0)) s(s(s(0) -> 3 等等。
  • 关系定义如下： multiply(N1,N2,R)
    • 在哪里
      • N1 是第一个 peano 整数（例如 s(s(0))）
      • N2 是第二个 peano 整数（例如 s(s(0))）
      • R 是生成的新 peano 整数（如 s(s(s(s(0))))）

我知道 Prolog 默认提供基本算术逻辑，但我正在尝试使用 peano 整数实现基本算术逻辑。

由于乘法基本上是重复加法，我认为它可能看起来像这样：

序言尝试

%Addition
% Adds two peano integers 3+2: add(s(s(s(0))),s(s(0)),X). --> X = s(s(s(s(s(0)))))
add(X,0,X).
add(X,s(Y),s(Z)) :- add(X,Y,Z).

%Loop
%Loop by N
loop(0).
loop(N) :- N>0, NewN is N-1, loop(NewN).

问题是我不知道如何让prolog根据系数运行循环N次，添加peano整数并建立正确的结果。我相信这很容易实现，并且生成的代码可能不会超过几行代码。几个小时以来，我一直在努力实现这一目标，这让我很生气。

非常感谢您的帮助，还有……圣诞快乐！

麦克风

4

1 回答 1

1

感谢@false 对这篇文章的提示： Prolog 后继符号产生不完整的结果和无限循环

这篇文章中引用的 PDF 文档有助于阐明有关 peano 整数的一些特性以及如何使简单的算术起作用 - 第 11 页和第 12 页特别有趣：http: //ssdi.di.fct.unl.pt/flcp/foundations /0910/files/class_02.pdf

代码可以这样设置 - 请注意整数相乘的两种方法：

%Basic assumptions
int(0). %0 is an integer
int(s(M)) :- int(M). %the successor of an integer is an integer

%Addition
sum(0,M,M). %the sum of an integer M and 0 is M.
sum(s(N),M,s(K)) :- sum(N,M,K). %The sum of the successor of N and M is the successor of the sum of N and M.

%Product
%Will work for prod(s(s(0)),s(s(0)),X) but not terminate for prod(X,Y,s(s(0)))
prod(0,M,0). %The product of 0 with any integer is 0
prod(s(N),M,P) :- 
    prod(N,M,K), 
    sum(K,M,P).%The product of the successor of N and M is the sum of M with the product of M and N. --> (N+1)*M = N*M + M

%Product #2
%Will work in both forward and backward direction, note the order of the calls for sum() and prod2()
prod2(0,_,0). %The product of 0 with any given integer is 0
prod2(s(N), M, P) :- % implements (N+1)*M = M + N*M
   sum(M, K, P),
   prod2(M,N,K).

其中，在查询数据库时会给你这样的东西：

?- prod(s(s(s(0))),s(s(s(0))),Result).
Result = s(s(s(s(s(s(s(s(s(0))))))))).

?- prod2(s(s(s(0))),s(s(s(0))),Result).
Result = s(s(s(s(s(s(s(s(s(0))))))))).

请注意逆向查询 Prolog 的不同行为prod()和prod2()当查询时 - 跟踪时，请注意 Prolog 在递归调用期间绑定其变量的方式：

?- prod(F1,F2,s(s(s(s(0))))).
F1 = s(0),
F2 = s(s(s(s(0)))) ;
F1 = F2, F2 = s(s(0)) ;
ERROR: Out of global stack

?- prod2(F1,F2,s(s(s(s(0))))).
F1 = s(s(s(s(0)))),
F2 = s(0) ;
F1 = F2, F2 = s(s(0)) ;
F1 = s(0),
F2 = s(s(s(s(0)))) ;
false.

因此，我不鼓励使用，prod()因为它不能在所有可以想到的场景中可靠地终止并prod2()改为使用。

我对 StackOverflow 的人们感到非常兴奋。我得到了很多有用的反馈，这真的帮助我更深入地了解 Prolog 的工作原理。非常感谢大家！

麦克风

编辑：感谢@false 和以下帖子，再次查看此问题：Prolog 后继符号产生不完整的结果和无限循环

于 2014-12-20T18:09:10.250 回答