Compilers - prolog and backtracking

Author

prolog and backtracking

James Sison

2007-09-23, 7:15 pm

I'M Trying To Write This Prolog Interpreter For A Subset Of The Prolog
Grammar In Java And I Encountered Problems With Bakctracking.

For example

Given the following database:

father(bill,jake).
father(bill,ruby).
mother(carmen, jake).
mother(carmen, ruby).
parent(X,Y):-father(X,Y).
parent(X,Y):-mother(X,Y).
sibling(X,Y):-parent(P,X),parent(P,Y).

What i'm trying to do is, since this grammar does not
include lists or cuts or any of prolog's built in
goals, i'm going to solve for all the possible goals
for the rules so that when the user asks a query, it
would be easier to solve. So, using the said idea in
the above mentioned database, this would be the list
of goals.

father(bill,jake).
father(bill,ruby).
mother(carmen, jake).
mother(carmen, ruby).
parent(bill,jake).
parent(bill,ruby).
parent(carmen, jake).
parent(carmen, ruby).
sibling(jake,ruby).

I think it's a good idea but it would still have to
use prolog's standard way of solving goals. So, my
problem is, how do i tell prolog where to restart a
search when i want to find all solutions for a query.
For example

sibling(X,Y):-parent(P,X),parent(P,Y).

It would first solve parent(P,X)

parent(P,X):-father(P,X).
so
P=bill
X=jake.

so...

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

parent(bill,Y):-father(bill,Y).
but...
father(bill,Y).
Y=jake

but jake has already been found and it should be
different from the result of the first parent. Any
tips on how to remedy this. Also, if for example the
second parent(P,Y) has found all its solutions and the
first parent(P,X) will solve for the next X, how do i
tell that it should look at the next father fact? I
tried storing the current state of the facts needed to
solve parent(P,Y) inside the node of parent(P,Y) but
java said there was an out of memory exception. Is
there a simpler way to address this problem?

Markus Triska

2007-09-23, 10:10 pm

James Sison <the_evil_trembles@yahoo.com> 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])).

Output:

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

Hans Aberg

2007-09-24, 7:19 pm

James Sison <the_evil_trembles@yahoo.com> wrote:

> I'M Trying To Write This Prolog Interpreter For A Subset Of The Prolog
> Grammar In Java And I Encountered Problems With Bakctracking.

There is a MiniProlog that comes with the Haskell interpreter Hugs
<http://haskell.org/hugs/>, which is OO, and therefore easy
to translate into languages like C++ and Java. For the Prolog interactive
query style, it relies on laze evaluation, so that goes out of the window
when translated into a strict language. And I recall the cut was wrongly
implemented (but easily fixed).

But you might take a look at that one, to see how this stuff is implemented.

Hans Aberg

Sponsored Links