Here's a very simple example that I pulled from http://www.csm.astate.edu/~rossa/cs3543/plect5.html.
on(red_box, table).
on(glove, red_box).
on(blue_box, table).
on(baseball, blue_box).
Let's say that I want to find all X that is on Y that, in turn, is on Z. I would issue the following query:
?- on(X,Y),on(Y,Z).
Here's how the backtracking works.
- X = red_box, Y = table.
- There are no facts where Y is the first argument to the fact, so this fails.
- Prolog backtracks and sets X = glove, Y = red box.
- Y is matches the first fact, so we have our first answer.
- Prolog backtracks to match Y to another fact, but this fails.
- X = blue_box. Y = table
- Y does not match any first arguments, so this fails.
- Prolog backtracks again and sets X = baseball and Y = blue_box.
- Y matches the third fact, so we have our second answer.
- Prolog backtracks to match Y to another fact, but this fails.
- Prolog backtracks again and tries to set X to another argument, but no more arguments are available, so this fails and the unification of arguments to variables halts.
This is a trivial example (and I took some shortcuts - see the actual link above), but imagine what happens why we have facts embedded in facts and we need to gain information from those subfacts:
gives(ovid,book(learning_perl,[merlyn,rootbeer],publisher(o_reilly),th
+ird_edition),grep).
Now, if I issue queries against that (and we're in a proper SQL database), I have at least three tables that I need to span and potentially backtrack across. If my query is more complicated, the number of tables can rise dramatically.
You can also read this link for a more complicated example, or an example of how a bad database can lead to infinite recursion with backtracking.
Cheers,
Ovid
Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.