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))))
- Where
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
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:
Which, when consulting the database will give you something like this:
Please note the different behavior of
prod()
andprod2()
when consulting Prolog in reverse direction - when tracing, please pay attention to the way Prolog binds its variables during the recursive calls:I would therefore discourage from the use of
prod()
as it doesn't reliably terminate in all thinkable scenarios and useprod2()
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