Re: prolog and backtracking

Markus Triska <>
Mon, 24 Sep 2007 03:34:06 +0200

          From comp.compilers

Related articles
prolog and backtracking (James Sison) (2007-09-22)
Re: prolog and backtracking (Markus Triska) (2007-09-24)
Re: prolog and backtracking (2007-09-24)
| List of all articles for this month |

From: Markus Triska <>
Newsgroups: comp.compilers
Date: Mon, 24 Sep 2007 03:34:06 +0200
Organization: Compilers Central
References: 07-09-087
Keywords: prolog
Posted-Date: 23 Sep 2007 22:31:51 EDT

James Sison <> writes:

> but jake has already been found and it should be different from the
> result of the first parent.

You can state this constraint in Prolog, using e.g. dif/2 or \==/2:

      sibling(X,Y):- dif(X, Y), parent(bill,X), parent(bill,Y).

You could also omit symmetrical solutions using e.g. @</2:

      sibling(X,Y):- parent(bill,X), parent(bill,Y), X @< Y.

This is hardly advisable though, since sibling/2 is after all a
symmetrical relation in reality, whereas you'd have for example:

      %?- sibling(jake, ruby).
      %@ Yes

      %?- sibling(ruby, jake).
      %@ No

> Is there a simpler way to address this problem?

Consider the built-in predicates setof/3 or findall/3, which you can
use to find all solutions; sort to eliminate duplicates if necessary:

      %?- findall(X-Y, sibling(X, Y), XYs0), sort(XYs0, XYs).
      %@ XYs0 = [jake-ruby, ruby-jake, jake-ruby, ruby-jake],
      %@ XYs = [jake-ruby, ruby-jake]

>From this list you can easily generate your facts in Prolog (tested
with SWI-Prolog, where $XYs refers to the previous toplevel binding):

      %?- forall(member(X-Y, $XYs), format("sibling(~w, ~w).\n", [X,Y])).


      sibling(jake, ruby).
      sibling(ruby, jake).

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.