/usr/share/doc/racket/racklog/backtracking.html is in racket-doc 6.1-4.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"/><title>4 Backtracking</title><link rel="stylesheet" type="text/css" href="../scribble.css" title="default"/><link rel="stylesheet" type="text/css" href="../racket.css" title="default"/><link rel="stylesheet" type="text/css" href="../manual-style.css" title="default"/><link rel="stylesheet" type="text/css" href="../manual-racket.css" title="default"/><link rel="stylesheet" type="text/css" href="../manual-racket.css" title="default"/><link rel="stylesheet" type="text/css" href="../doc-site.css" title="default"/><script type="text/javascript" src="../scribble-common.js"></script><script type="text/javascript" src="../manual-racket.js"></script><script type="text/javascript" src="../manual-racket.js"></script><script type="text/javascript" src="../doc-site.js"></script><script type="text/javascript" src="../local-redirect/local-redirect.js"></script><script type="text/javascript" src="../local-redirect/local-user-redirect.js"></script><!--[if IE 6]><style type="text/css">.SIEHidden { overflow: hidden; }</style><![endif]--></head><body id="doc-racket-lang-org"><div class="tocset"><div class="tocview"><div class="tocviewlist tocviewlisttopspace"><div class="tocviewtitle"><table cellspacing="0" cellpadding="0"><tr><td style="width: 1em;"><a href="javascript:void(0);" title="Expand/Collapse" class="tocviewtoggle" onclick="TocviewToggle(this,"tocview_0");">▼</a></td><td></td><td><a href="index.html" class="tocviewlink" data-pltdoc="x">Racklog:<span class="mywbr"> </span> Prolog-<wbr></wbr>Style Logic Programming</a></td></tr></table></div><div class="tocviewsublistonly" style="display: block;" id="tocview_0"><table cellspacing="0" cellpadding="0"><tr><td align="right">1 </td><td><a href="simple.html" class="tocviewlink" data-pltdoc="x">Simple Goals and Queries</a></td></tr><tr><td align="right">2 </td><td><a href="predicates.html" class="tocviewlink" data-pltdoc="x">Predicates</a></td></tr><tr><td align="right">3 </td><td><a href="racket-w-logic.html" class="tocviewlink" data-pltdoc="x">Using Conventional Racket Expressions in Racklog</a></td></tr><tr><td align="right">4 </td><td><a href="" class="tocviewselflink" data-pltdoc="x">Backtracking</a></td></tr><tr><td align="right">5 </td><td><a href="unification.html" class="tocviewlink" data-pltdoc="x">Unification</a></td></tr><tr><td align="right">6 </td><td><a href="and-or.html" class="tocviewlink" data-pltdoc="x">Conjuctions and Disjunctions</a></td></tr><tr><td align="right">7 </td><td><a href="lv-manip.html" class="tocviewlink" data-pltdoc="x">Manipulating Racklog Variables</a></td></tr><tr><td align="right">8 </td><td><a href="cut.html" class="tocviewlink" data-pltdoc="x">The Cut (<span class="RktSym"><span class="RktStxLink">!</span></span>)</a></td></tr><tr><td align="right">9 </td><td><a href="set-of.html" class="tocviewlink" data-pltdoc="x">Set Predicates</a></td></tr><tr><td align="right">10 </td><td><a href="Racklog_Module_Language.html" class="tocviewlink" data-pltdoc="x">Racklog Module Language</a></td></tr><tr><td align="right">11 </td><td><a href="glossary.html" class="tocviewlink" data-pltdoc="x">Glossary of Racklog Primitives</a></td></tr><tr><td align="right"></td><td><a href="doc-bibliography.html" class="tocviewlink" data-pltdoc="x">Bibliography</a></td></tr></table></div></div></div></div><div class="maincolumn"><div class="main"><div class="navsettop"><span class="navleft"><form class="searchform"><input class="searchbox" style="color: #888;" type="text" value="...search manuals..." title="Enter a search string to search the manuals" onkeypress="return DoSearchKey(event, this, "6.1", "../");" onfocus="this.style.color="black"; this.style.textAlign="left"; if (this.value == "...search manuals...") this.value="";" onblur="if (this.value.match(/^ *$/)) { this.style.color="#888"; this.style.textAlign="center"; this.value="...search manuals..."; }"/></form> <a href="../index.html" title="up to the documentation top" data-pltdoc="x" onclick="return GotoPLTRoot("6.1");">top</a></span><span class="navright"> <a href="racket-w-logic.html" title="backward to "3 Using Conventional Racket Expressions in Racklog"" data-pltdoc="x">← prev</a> <a href="index.html" title="up to "Racklog: Prolog-Style Logic Programming"" data-pltdoc="x">up</a> <a href="unification.html" title="forward to "5 Unification"" data-pltdoc="x">next →</a></span> </div><h3 x-source-module="(lib "racklog/racklog.scrbl")" x-part-tag=""backtracking"">4<tt> </tt><a name="(part._backtracking)"></a>Backtracking</h3><p>It is helpful to go into the following evaluation (<a href="predicates.html#%28part._rules%29" data-pltdoc="x">Predicates with Rules</a>)
in a
little detail:</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._~25which%29%29" class="RktStxLink" data-pltdoc="x">%which</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">%computer-literate</span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">Penelope</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></blockquote><p>The starting goal
is:</p><blockquote class="SCodeFlow"><p><span class="RktSym">G0</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=generic-numbers.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._%7E3d%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">=</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">%computer-literate</span><span class="hspace"> </span><span class="RktSym">Penelope</span><span class="RktPn">)</span></p></blockquote><p>(I’ve taken out the quote because <span class="RktRes">Penelope</span> is the result
of evaluating <span class="RktVal">'</span><span class="RktVal">Penelope</span>.)</p><p>Racklog tries to match this with the head of the first
clause of <span class="RktSym">%computer-literate</span>. It succeeds, generating a
binding <span class="RktPn">[</span><span class="RktSym">person</span><span class="stt"> </span><span class="RktPn">. </span><span class="RktSym">Penelope</span><span class="RktPn">]</span>.</p><p>But this means it now has two new goals —<wbr></wbr> <span style="font-style: italic">subgoals</span>
—<wbr></wbr> to solve. These are the goals in the body of the
matching clause, with the logic variables substituted by
their instantiations:</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="RktSym">G1</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=generic-numbers.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._%7E3d%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">=</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">%knows</span><span class="hspace"> </span><span class="RktSym">Penelope</span><span class="hspace"> </span><span class="RktSym">TeX</span><span class="RktPn">)</span></td></tr><tr><td><span class="RktSym">G2</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=generic-numbers.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._%7E3d%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">=</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">%knows</span><span class="hspace"> </span><span class="RktSym">Penelope</span><span class="hspace"> </span><span class="RktSym">Racket</span><span class="RktPn">)</span></td></tr></table></blockquote><p>For <span class="RktInBG"><span class="hspace"></span><span class="RktIn">G1</span><span class="hspace"></span></span>, Racklog attempts matches with the clauses of
<span class="RktSym">%knows</span>, and succeeds at the fifth try. (There are no
subgoals in this case, because the bodies of these “fact”
clauses are empty, in contrast to the “rule” clauses of
<span class="RktSym">%computer-literate</span>.)
Racklog then tries to solve <span class="RktInBG"><span class="hspace"></span><span class="RktIn">G2</span><span class="hspace"></span></span> against the clauses of
<span class="RktSym">%knows</span>, and since there is no clause stating that
Penelope knows Racket, it fails.</p><p>All is not lost though. Racklog now <span style="font-style: italic">backtracks</span> to the
goal that was solved just before, viz., <span class="RktInBG"><span class="hspace"></span><span class="RktIn">G1</span><span class="hspace"></span></span>. It
<span style="font-style: italic">retries</span> <span class="RktInBG"><span class="hspace"></span><span class="RktIn">G1</span><span class="hspace"></span></span>, ie, tries to solve it in a
different way.
This entails searching down the previously unconsidered
<span class="RktSym">%knows</span>
clauses for <span class="RktInBG"><span class="hspace"></span><span class="RktIn">G1</span><span class="hspace"></span></span>, ie, the sixth onwards. Obviously,
Racklog fails again, because the fact that Penelope knows
TeX occurs only once.</p><p>Racklog now backtracks to the goal before <span class="RktInBG"><span class="hspace"></span><span class="RktIn">G1</span><span class="hspace"></span></span>, ie,
<span class="RktInBG"><span class="hspace"></span><span class="RktIn">G0</span><span class="hspace"></span></span>. We abandon the current successful match with the
first clause-head of <span class="RktSym">%computer-literate</span>, and try the
next clause-head. Racklog succeeds, again producing a binding
<span class="RktPn">[</span><span class="RktSym">person</span><span class="stt"> </span><span class="RktPn">. </span><span class="RktSym">Penelope</span><span class="RktPn">]</span>, and two new subgoals:</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="RktSym">G3</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=generic-numbers.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._%7E3d%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">=</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">%knows</span><span class="hspace"> </span><span class="RktSym">Penelope</span><span class="hspace"> </span><span class="RktSym">TeX</span><span class="RktPn">)</span></td></tr><tr><td><span class="RktSym">G4</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=generic-numbers.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._%7E3d%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">=</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">%knows</span><span class="hspace"> </span><span class="RktSym">Penelope</span><span class="hspace"> </span><span class="RktSym">Prolog</span><span class="RktPn">)</span></td></tr></table></blockquote><p>It is now easy to trace that Racklog finds both <span class="RktInBG"><span class="hspace"></span><span class="RktIn">G3</span><span class="hspace"></span></span> and <span class="RktInBG"><span class="hspace"></span><span class="RktIn">G4</span><span class="hspace"></span></span> to be
true. Since both of <span class="RktInBG"><span class="hspace"></span><span class="RktIn">G0</span><span class="hspace"></span></span>’s subgoals are true, <span class="RktInBG"><span class="hspace"></span><span class="RktIn">G0</span><span class="hspace"></span></span> is
itself considered true. And this is what Racklog reports. The
interested reader can now trace why the
following query has a different denouement:</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._~25which%29%29" class="RktStxLink" data-pltdoc="x">%which</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">%computer-literate</span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">Telemachus</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></td></tr><tr><td><p><span class="RktRes">#f</span></p></td></tr></table></blockquote><div class="navsetbottom"><span class="navleft"><form class="searchform"><input class="searchbox" style="color: #888;" type="text" value="...search manuals..." title="Enter a search string to search the manuals" onkeypress="return DoSearchKey(event, this, "6.1", "../");" onfocus="this.style.color="black"; this.style.textAlign="left"; if (this.value == "...search manuals...") this.value="";" onblur="if (this.value.match(/^ *$/)) { this.style.color="#888"; this.style.textAlign="center"; this.value="...search manuals..."; }"/></form> <a href="../index.html" title="up to the documentation top" data-pltdoc="x" onclick="return GotoPLTRoot("6.1");">top</a></span><span class="navright"> <a href="racket-w-logic.html" title="backward to "3 Using Conventional Racket Expressions in Racklog"" data-pltdoc="x">← prev</a> <a href="index.html" title="up to "Racklog: Prolog-Style Logic Programming"" data-pltdoc="x">up</a> <a href="unification.html" title="forward to "5 Unification"" data-pltdoc="x">next →</a></span> </div></div></div><div id="contextindicator"> </div></body></html>
|