Search code examples
prologmultiplicationsuccessor-arithmetics

Multiplying peano integers in swi-prolog

I am currently on the verge of getting mad trying to solve a simple "multiply peano integers" problem in Prolog.

Basic rules

  • A peano integer is defined as follows: 0 -> 0; 1 -> s(0); 2 -> s(s(0)) s(s(s(0) -> 3 etc.
  • The relation is to be defined as follows: multiply(N1,N2,R)
    • Where
      • N1 is the first peano integer (i.e. something like s(s(0)))
      • N2 is the second peano integer (i.e. something like s(s(0)))
      • R is the resulting new peano integer (like s(s(s(s(0))))

I am aware of the fact that Prolog provides basic arithmetic logic by default, but I am trying to implement basic arithmetic logic using peano integers.

As a multiplication is basically a repeated addition, I think it could look something like this:

Prolog attempts

%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).

The problem is that I am out of ideas how I can get prolog to run the loop N times based on the coefficient, adding the peano integers and building up the correct result. I'm confident that this is rather easy to achieve and that the resulting code probably won't be longer than a few lines of code. I've been trying to achieve this for hours now and it's starting to make me mad.

Thank you so much for your help, and ... Merry Christmas!

Mike

Solution

  • thanks @false for the hint to this post: Prolog successor notation yields incomplete result and infinite loop

    The referenced PDF doc in this post helps clarifying a number of features regarding peano integers and how to get simple arithmetic to work - pages 11 and 12 are particularly interesing: http://ssdi.di.fct.unl.pt/flcp/foundations/0910/files/class_02.pdf

    The code could be set up like this - please note the two approaches for multiplying the integers:

    %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).

    Which, when consulting the database will give you something like this:

    ?- 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))))))))).

    Please note the different behavior of prod() and prod2() when consulting Prolog in reverse direction - when tracing, please pay attention to the way Prolog binds its variables during the recursive calls:

    ?- 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.

    I would therefore discourage from the use of prod() as it doesn't reliably terminate in all thinkable scenarios and use prod2() instead.

    I'm really excited by the people here at StackOverflow. I got so much useful feedback, which really helped me in getting a deeper understanding of how Prolog works. Thanks a ton everyone!

    Mike

    Edit: Had another look at this issue thanks to @false and the following post: Prolog successor notation yields incomplete result and infinite loop