CODEWITHSUNDEEP
recursionprologconstraint-programming
Anderson Green
Anderson Green

Reputation: 31800

Solving mutually recursive constraints in Prolog

I am attempting to solve some mutually recursive constraints with SWI-Prolog. These constraints are relatively simple, but querying any of these predicates leads to infinite recursion:

%If X is an animal, then X is a bird or a mammal, and vice-versa.
animal(X) :- 
    (mammal(X);bird(X)),
    (male(X);female(X)).

male(X) :- animal(X).
female(X) :- animal(X).

bird(X) :- (X='parrot';X='pigeon'),animal(X).

mammal(X) :- (X='cat';X='dog'),animal(X).

Would it be possible to solve these constraints in Prolog without making them non-recursive?

I wrote a similar program with several base cases, but the query mammal(X),bird(X) still leads to infinite recursion instead of returning false:

%If X is an animal, then X is a bird or a mammal, and vice-versa.
animal(X) :- 
    (mammal(X);bird(X)).

bird('parrot').
bird('pigeon').
bird(X) :- (X='parrot';X='pigeon'),animal(X).

mammal('cat').
mammal('dog').
mammal(X) :- (X='cat';X='dog'),animal(X).

Upvotes: 0

Views: 341

Answers (4)

Anderson Green
Anderson Green

Reputation: 31800

It is possible to find solutions for mutually recursive constraints using constraint handling rules.

This is a set of mutually recursive constraints:

%If X is an animal, then X is a bird or a mammal, and vice-versa.
:- use_module(library(chr)).

:- chr_constraint mammal/2,bird/2,animal/1,male/1,female/1,species/2.

animal(X) <=> 
    (mammal(X,Species);bird(X,Species)),
    (male(X);female(X)).

male(X),female(X) ==> false.

bird(X,Species) <=> member(Species,[parrot,pigeon,crow]),species(X,Species).
bird(X,Species) ==> animal(X).

mammal(X,Species) <=> member(Species,[cat,dog,bull]),species(X,Species).
mammal(X,Species) ==> animal(X).

species(X,bull) ==> male(X).

...and this is the output of a query for this program:

?- male(X),mammal(X,Species).
male(_G67406)
species(_G67406,cat)
Species = cat

Upvotes: 3

mat
mat

Reputation: 40768

One solution to such problems is to simply enable your Prolog system's tabling mechanism.

For example, in SWI-Prolog (latest development version), if I simply add the following directives at the start of your program:

:- use_module(library(tabling)).

:- table animal/1.

Then I get for example:

?- animal(X).
false.

?- male(X).
false.

?- bird(X).
false.

So, in these cases, we still do not find any solution, but at least we get answers.

Upvotes: 2

lurker
lurker

Reputation: 58224

I think what you're trying to get at is that you have birds and you have mammals. And you are further trying to establish that a creature is an animal if it is either a bird or a mammal.

The code currently over-specifies, and has circular logic.

Walking through the code...

animal(X) :- 
    (mammal(X); bird(X)).

This says that X is an animal if X is a mammal or X is a bird. So far, so good.

The description of bird reads:

bird('parrot').
bird('pigeon').

These are facts that indicate that a parrot is a bird and a pigeon is a bird. But then there's this rule:

bird(X) :- (X='parrot';X='pigeon'),animal(X).

Which says that X is a bird if X is either a parrot or pigeon, AND if X is an animal. The prior two facts already establish that parrot and pigeon are birds. Why is this rule necessary? And it further adds the condition that X is an animal, which is, in turn, defined in terms of bird and mammal, so is circular.

Similar holds true for the mammal definition. It has the needed facts for mammals:

mammal('cat').
mammal('dog').

And then overspecifies with circular logic:

mammal(X) :- (X='cat';X='dog'), animal(X).

The essence of what you need is simply:

bird('parrot').
bird('pigeon').

mammal('cat').
mammal('dog').

animal(X) :- 
    mammal(X); bird(X).

This logic defines what creatures are birds or mammals using facts, then provides a rule that says if a creature is known to be a bird or a mammal, then it's an animal.

Upvotes: 2

Scott Hunter
Scott Hunter

Reputation: 49803

Solving a recursive constraint requires one or more base cases; you have not provided any. The problem isn't with Prolog; its with the problem definition.

Upvotes: 3

Related Questions