How to write number classifiers in prolog?

Question

Playing with Prolog for the first time and while I thought I knew what it basically is good for, I find it hard to get anything done in it. So, I tried to find the easiest possible task and even fail to accomplish that.

I think it is due to me not knowing how prolog data types (numbers) are supposed to work or they have special syntax.

So, my first attempt to classify even numbers was:

even(0).
even(X) :- even(X-2).

Result: stack overflow for the query: even(2).

So I thought well if this is not it, then maybe it is:

even(0).
even(X+2) :- even(X).

Result of even(2): false.

So my simple question is: How to write such simple things in prolog? Is it all not working because i use numbers?

Well, numbers are not that simple. Better start with [tag:successor-arithmetics] and then switch over to [tag:clpfd]. (Numbers are only simple as long as you have concrete values only, but in Prolog we permit also variables this is what makes them a bit more difficult - in the general case) — false, Jun 02 '15 at 00:16
Prolog is not that different. You test for "even" by checking the least significant bit in many languages, and this is how you should do it in Prolog, too. See my answer below. — , Jun 02 '15 at 06:13

score 3 · Answer 1 · 2015-06-03T05:36:49.210

3

Why not do it the normal way:

is_even(X) :-
    X /\ 0x1 =:= 0.

If you want to enumerate non-negative even numbers upon backtracking when the argument is not bound, this is a different thing altogether. It is probably easy to just say:

even(X) :-
    between(0, infinite, X),
    is_even(X).

You can use the second definition like this:

?- even(X).
X = 0 ;
X = 2 ;
X = 4 ;
X = 6 . % and so on

There are some differences between is_even/1 and even/1:

is_even/1 will work for any integer, positive or negative
is_even/1 will, surprisingly enough, work for expressions that evaluate to integers, too, for example, X = 3, ..., is_even(X + 1). This is because =:= accepts an arithmetic expression on either side.
even/1 uses between/3, so the domain of X and error conditions are the same as for the third argument of between/3.
As a consequence, even/1 does not work with negative integers or arithmetic expressions.

But wait, there's more!

Apparently, between(0, infinite, X) is not something you can do in almost any Prolog apart from SWI. So, instead, you can use another predicate that will enumerate positive integers (list lengths):

even_f(X) :-
    length(_, X),
    is_even(X).

(Thank you to @false for this)

edited Jun 03 '15 at 05:36

answered Jun 02 '15 at 06:03

you can use the second definition for both uses, I think. – Will Ness Jun 02 '15 at 10:13
@WillNess It really depends if you want to allow negative numbers or not I guess? – Jun 02 '15 at 10:22
@WillNess Thank you for the pointer, I added some detail to my answer to make it a bit more clear. – Jun 02 '15 at 10:45
1

`between(0, infinite, X)` is SWI specific - the common definition DEC10 library, Quintus, SICStus, GNU, XSB, [Prolog prologue](http://www.complang.tuwien.ac.at/ulrich/iso-prolog/prologue#between), B only permits an integer. – false Jun 02 '15 at 14:25
Use `length(_,X)` instead. For the time being -1 – false Jun 02 '15 at 14:26
@false I guess this are the risks or reading the manual of only one of the Prolog implementations. Added your comment to the answer. – Jun 03 '15 at 05:35

score 0 · Accepted Answer · answered Jun 02 '15 at 00:50

0

Use is/2 to force the arithmetic evaluation. On their own, Prolog terms are just structural symbolic entities, X-2 is a compound term of arity 2, -(X,2):

3 ?- write_canonical( X-2 ).
-(_,2)
true.

But is is for arithmetic expressions:

4 ?- Z is 5-2.
Z = 3.

Your definition should thus be

even(X):-  X=:=0 -> true 
        ;  X > 0 -> Y is X-2, even(Y).

The drawback of such definition is that it can't be called in a generative fashion, like even(X) to get all the evens generated one after the other.

It is only good for checking a given number. For simplicity, it ignores the negative numbers and always fails for them.

answered Jun 02 '15 at 00:50

Will Ness

70,110
9
98
181

This is a really roundabout way to do it, isn't it? – Jun 02 '15 at 06:05
it depends on whether your goal is to define the best `even` predicate, or to learn the very basics of Prolog. :) – Will Ness Jun 02 '15 at 09:26
:) Sure thing. However, it is altogether confusing to do things in a roundabout way, because someone (esp. a beginner) might be left with the impression that it was deliberate and for a specific reason. – Jun 02 '15 at 09:41
1

yes it was, deliberate, and direct -- about the use of `is`, which was the issue of OP as I understood it. – Will Ness Jun 02 '15 at 10:09

How to write number classifiers in prolog?

2 Answers2