prolog - 在 swi-prolog 中乘以 peano 整数

Question

我目前正处于疯狂的边缘，试图在 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 整数并建立正确的结果。我相信这很容易实现，并且生成的代码可能不会超过几行代码。几个小时以来，我一直在努力实现这一目标，它开始让我发疯。

非常感谢您的帮助，还有...圣诞快乐!

迈克

Answer 1

感谢@false 对这篇文章的提示: Prolog successor notation yields incomplete result and infinite loop

这篇文章中引用的 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 绑定(bind)其变量的方式在递归调用期间:

?- 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 successor notation yields incomplete result and infinite loop 再次审视了这个问题