prolog and backtracking

James Sison <the_evil_trembles@yahoo.com>
Sat, 22 Sep 2007 06:34:39 -0700 (PDT)

          From comp.compilers

Related articles
prolog and backtracking the_evil_trembles@yahoo.com (James Sison) (2007-09-22)
Re: prolog and backtracking triska@logic.at (Markus Triska) (2007-09-24)
Re: prolog and backtracking haberg@math.su.se (2007-09-24)
| List of all articles for this month |

From: James Sison <the_evil_trembles@yahoo.com>
Newsgroups: comp.compilers
Date: Sat, 22 Sep 2007 06:34:39 -0700 (PDT)
Organization: Compilers Central
Keywords: prolog, question

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?


Post a followup to this message

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