2

I am new to Prolog, and need to implement some basic arithmetic operations on natural numbers, without using the built-in predicates.

I represent natural number Term in unary notaion, meaning I have the constant 0, and the recursive successor functor s [i.e. 4 = s(s(s(s(0))))]. I implement the arithmetic operations, with respect to the above notation.

The set of rules is:

% nat(N)/1 ---> N is a natural number
nat(0).
nat(s(X)) :-
    nat(X).

% add(X,Y,Z)/3 ---> Z = X + Y
add(X,0,X) :-
    nat(X).
add(X,s(Y),s(Z)) :-
    add(X,Y,Z).

% mult(X,Y,Z)/3 ---> Z = X * Y
mult(0,X,0) :-
    nat(X).
mult(s(X),Y,Z) :-
    mult(X,Y,XY),
    add(XY,Y,Z).

now, when I query:

?- mult(s(s(0)), s(s(s(0))), RES).

I get everything OK:

RES = s(s(s(s(s(s(0)))))).

when I query: (like to ask 6/3=?)

?- mult(X, s(s(s(0))), s(s(s(s(s(s(0))))))).

I stuck in an infinite loop and get S.O.

even if I change the order of the recursive call in the mult predicate it doesn't help:

mult(s(X),Y,Z) :-
    add(XY,Y,Z),
    mult(X,Y,XY).

I run swi-prolog on linux machine.

Will appreciate your advice!

false
  • 10,264
  • 13
  • 101
  • 209
Mike
  • 575
  • 1
  • 5
  • 15

1 Answers1

1

OK, there is a quick fix (wrong recursion):

% add(X,Y,Z)/3 ---> Z = X + Y
add(0,X,X) :-
    nat(X).
add(s(X),Y,s(Z)) :-
    add(X,Y,Z).

and then the mult:

mult(s(X),Y,Z) :-
   add(XY,Y,Z),
   mult(X,Y,XY).

will give the desired result.

yet, for the query:

?- mult(X,Y,s(s(s(s(s(s(0))))))).

it will output all pairs of X,Y that correspond to: X * Y = s(s(s(s(s(s(0)))))), and after the last pair, will go into infinite loop, for unknown reason to me.

Mike
  • 575
  • 1
  • 5
  • 15