prolog using recursion to find successor

0
votes

I'm trying to learn prolog now and I started recursion topic. Came across this example for successor.

numeral(0).
numeral(succ(X)) :- numeral(X)

I do understand how it works in theory. It takes the number X and succ increments it. My questions here is, is succ an in-built predicate? Or is there something else going on in this example. Example taken from learnprolognow.org

Then I came across this exercise

pterm(null).
pterm(f0(X)) :- pterm(X).
pterm(f1(X)) :- pterm(X).

It is meant to represent binary, that is 0 is f0(null), 1 is f1(null), 2(10) is f0(f1(null)), 3(11) is f1(f1(null)) etc. The question asks to define predicate (P1, P2) so that P2 is the successor of P1 by using pterms. Could someone explain this question in more detail for me? The way I see it now, I have to traverse back through P1 until I hit the end and then compare it to P2, but I'm not exactly sure about the syntax. Any hints would be useful

2
prologsuccessor-arithmetics
succ/1 is just an arbitrary function symbol. More common is s/1. – false

2 Answers

2
votes

succ is a compound term, not a built-in predicate.

Taking the two clauses in order you have:

numeral(0).

This means numeral(0) is true, i.e. 0 is a numeral

numeral(succ(X)) :- numeral(X)

This means numeral(succ(X)) is true if you can show that numeral(X) is true.

If you ask the query:

?- numeral(succ(succ(0)).

Then prolog will say True: numeral(succ(succ(0)) is true if numeral(succ(0)) is true. And numeral(succ(0)) is true if numeral(0) is true. And we know numeral(0) is true.

If you ask

?- numeral(X).

Then prolog will reply X=0 then X=succ(0) then X=succ(succ(0)) and so on as it finds terms which satisfy your clauses.

Now to answer your pterm question...

First think about the structure you are building. Its a binary number and the outermost term is the least significant bit. Here are some examples for things which are true:

1: succ(f1(null),f0(f1(null))
2: succ(f0(f1(null)),f1(f1(null))
3: succ(f1(f1(null)),f0(f0(f1(null)))

If you look at the examples for 2 and 3 above then you should be able to derive three cases of interest. As a hint the first case is that if the term is of the form f0(X) then the successor is f1(X).

1
votes

seems that inspecting the top level argument could be enough. Just an hint

psucc(pterm(f0(X)), pterm(f1(f0(X)))).
...