Return Integer with Prolog

Question

I try to understand prolog right now. I want to give the input: convert(s(s(s(X))),Y) and the output should be Y = 3.

convert(s(0), 1).
convert(s(s(0)), 2).
convert(s(X),Y) :- convert(X,Y is (Y+1)).

Those are my rules right now, but only the inputs: convert(s(0), 1). And convert(s(s(0)), 2). work.

If my recursion would work right, I wouldn't need the rule: convert(s(s(0)), 2). Can someone help me with that problem?

Answer 1

There are two problems here:

• Y is Y+1, does not makes any sense in Prolog; and
• note that you here actually have written a functor.

Prolog sees this as a call:

convert(X,is(Y,Y+1))

where is(Y,Y+1) is not called, but passed as a functor. In Prolog there is no clear input and output. You call predicates and through unification, you obtain results.

We can however solve the problem by using recursion: the convert/2 of 0 is of course 0:

convert(0,0).

and the convert of an s(X), is the convert of X plus one:

convert(s(X),R) :-
    convert(X,Y),
    R is Y+1.

Or putting these together:

convert(0,0).
convert(s(X),R) :-
    convert(X,Y),
    R is Y+1.

Now we can call the predicate to list all Peano numbers and the corresponding number, as well as converting a Peano number into a number. We can also validate if a Peano number is a normal number.

Unfortunately we can not use this predicate to obtain the Peano number from a given number: it will unify with the Peano number, but in a attempt to look for another Peano number, will get stuck into an infinite loop.

We can use the clpfd library to help us with this:

:- use_module(library(clpfd)).

convert(0,0).
convert(s(X),R) :-
    R #> 0,
    Y #= R-1,
    convert(X,Y).