/usr/share/doc/racket/racklog/cut.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 35 36 37 38 39 40 41 42 | <!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>8 The Cut (!)</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="tocviewsublisttop" 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="backtracking.html" class="tocviewlink" 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="" class="tocviewselflink" 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 class="tocviewlist"><table cellspacing="0" cellpadding="0"><tr><td style="width: 1em;"><a href="javascript:void(0);" title="Expand/Collapse" class="tocviewtoggle" onclick="TocviewToggle(this,"tocview_1");">►</a></td><td>8 </td><td><a href="" class="tocviewselflink" data-pltdoc="x">The Cut (<span class="RktSym"><span class="RktStxLink">!</span></span>)</a></td></tr></table><div class="tocviewsublistbottom" style="display: none;" id="tocview_1"><table cellspacing="0" cellpadding="0"><tr><td align="right">8.1 </td><td><a href="#%28part._if-then-else%29" class="tocviewlink" data-pltdoc="x">Conditional Goals</a></td></tr><tr><td align="right">8.2 </td><td><a href="#%28part._not%29" class="tocviewlink" data-pltdoc="x">Negation as Failure</a></td></tr></table></div></div></div><div class="tocsub"><div class="tocsubtitle">On this page:</div><table class="tocsublist" cellspacing="0"><tr><td><span class="tocsublinknumber">8.1<tt> </tt></span><a href="#%28part._if-then-else%29" class="tocsubseclink" data-pltdoc="x">Conditional Goals</a></td></tr><tr><td><span class="tocsublinknumber">8.2<tt> </tt></span><a href="#%28part._not%29" class="tocsubseclink" data-pltdoc="x">Negation as Failure</a></td></tr></table></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="lv-manip.html" title="backward to "7 Manipulating Racklog Variables"" data-pltdoc="x">← prev</a> <a href="index.html" title="up to "Racklog: Prolog-Style Logic Programming"" data-pltdoc="x">up</a> <a href="set-of.html" title="forward to "9 Set Predicates"" data-pltdoc="x">next →</a></span> </div><h3 x-source-module="(lib "racklog/racklog.scrbl")" x-part-tag=""cut"">8<tt> </tt><a name="(part._cut)"></a>The Cut (<span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._%21%29%29" class="RktStxLink" data-pltdoc="x">!</a></span>)</h3><p>The cut (called <span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._%21%29%29" class="RktStxLink" data-pltdoc="x">!</a></span>) is a special goal that is used to
prune backtracking options. Like the <span class="RktSym"><a href="glossary.html#%28def._%28%28lib._racklog%2Fmain..rkt%29._~25true%29%29" class="RktValLink" data-pltdoc="x">%true</a></span> goal, the
cut goal too succeeds, when accosted by the Racklog
subgoaling engine. However, when a further subgoal down the
line fails, and time comes to retry the cut goal, Racklog
will refuse to try alternate clauses for the predicate in
whose definition the cut occurs. In other words, the cut
causes Racklog to commit to all the decisions made from the
time that the predicate was selected to match a subgoal till
the time the cut was satisfied.</p><p>For example, consider again the <span class="RktSym">%factorial</span>
predicate, as defined in <a href="racket-w-logic.html#%28part._is%29" data-pltdoc="x"><span class="RktSym"><span class="RktStxLink">%is</span></span></a>:</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktSym">%factorial</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._~25rel%29%29" class="RktStxLink" data-pltdoc="x">%rel</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">x</span><span class="hspace"> </span><span class="RktSym">y</span><span class="hspace"> </span><span class="RktSym">x1</span><span class="hspace"> </span><span class="RktSym">y1</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktPn">(</span><span class="RktVal">0</span><span class="hspace"> </span><span class="RktVal">1</span><span class="RktPn">)</span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktPn">(</span><span class="RktSym">x</span><span class="hspace"> </span><span class="RktSym">y</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._~25is%29%29" class="RktStxLink" data-pltdoc="x">%is</a></span><span class="hspace"> </span><span class="RktSym">x1</span><span class="hspace"> </span><span class="RktPn">(</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._-%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x"><span class="nobreak">-</span></a></span><span class="hspace"> </span><span class="RktSym">x</span><span class="hspace"> </span><span class="RktVal">1</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">%factorial</span><span class="hspace"> </span><span class="RktSym">x1</span><span class="hspace"> </span><span class="RktSym">y1</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._~25is%29%29" class="RktStxLink" data-pltdoc="x">%is</a></span><span class="hspace"> </span><span class="RktSym">y</span><span class="hspace"> </span><span class="RktPn">(</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._%252A%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">*</a></span><span class="hspace"> </span><span class="RktSym">y1</span><span class="hspace"> </span><span class="RktSym">x</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></blockquote><p>Clearly,</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">%factorial</span><span class="hspace"> </span><span class="RktVal">0</span><span class="hspace"> </span><span class="RktVal">1</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></td></tr><tr><td><p><span class="RktRes">'()</span></p></td></tr><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="RktSym">n</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">%factorial</span><span class="hspace"> </span><span class="RktVal">0</span><span class="hspace"> </span><span class="RktSym">n</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></td></tr><tr><td><p><span class="RktRes">'((n . 1))</span></p></td></tr></table></blockquote><p>But what if we asked for <span class="RktPn">(</span><span class="RktSym"><a href="glossary.html#%28def._%28%28lib._racklog%2Fmain..rkt%29._~25more%29%29" class="RktValLink" data-pltdoc="x">%more</a></span><span class="RktPn">)</span> for either query?
Backtracking will try
the second clause of <span class="RktSym">%factorial</span>, and sure enough the
clause-head unifies, producing binding <span class="RktPn">[</span><span class="RktSym">x</span><span class="stt"> </span><span class="RktPn">. </span><span class="RktVal">0</span><span class="RktPn">]</span>.
We now get three subgoals. Solving the first, we get <span class="RktPn">[</span><span class="RktSym">x1</span><span class="stt"> </span><span class="RktPn">. </span><span class="RktVal"><span class="nobreak">-1</span></span><span class="RktPn">]</span>, and then we have to solve <span class="RktPn">(</span><span class="RktSym">%factorial</span><span class="stt"> </span><span class="RktVal"><span class="nobreak">-1</span></span><span class="stt"> </span><span class="RktSym">y1</span><span class="RktPn">)</span>. It
is easy to see there is no end to this, as we fruitlessly
try to get the factorials of numbers that get more and more
negative.</p><p>If we placed a cut at the first clause:</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=stx-patterns.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fstxcase-scheme..rkt%2529._......%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">...</a></span></td></tr><tr><td><span class="RktPn">[</span><span class="RktPn">(</span><span class="RktVal">0</span><span class="hspace"> </span><span class="RktVal">1</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._%21%29%29" class="RktStxLink" data-pltdoc="x">!</a></span><span class="RktPn">]</span></td></tr><tr><td><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=stx-patterns.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fstxcase-scheme..rkt%2529._......%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">...</a></span></td></tr></table></blockquote><p>the attempt to find more solutions for <span class="RktPn">(</span><span class="RktSym">%factorial</span><span class="stt"> </span><span class="RktVal">0</span><span class="stt"> </span><span class="RktVal">1</span><span class="RktPn">)</span> is nipped in the bud.</p><p>Calling <span class="RktSym">%factorial</span> with a <span style="font-style: italic">negative</span> number would still cause an
infinite loop. To take care of that problem as well, we
use another cut:</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktSym">%factorial</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._~25rel%29%29" class="RktStxLink" data-pltdoc="x">%rel</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">x</span><span class="hspace"> </span><span class="RktSym">y</span><span class="hspace"> </span><span class="RktSym">x1</span><span class="hspace"> </span><span class="RktSym">y1</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktPn">(</span><span class="RktVal">0</span><span class="hspace"> </span><span class="RktVal">1</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._%21%29%29" class="RktStxLink" data-pltdoc="x">!</a></span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktPn">(</span><span class="RktSym">x</span><span class="hspace"> </span><span class="RktSym">y</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="glossary.html#%28def._%28%28lib._racklog%2Fmain..rkt%29._~25~3c%29%29" class="RktValLink" data-pltdoc="x">%<</a></span><span class="hspace"> </span><span class="RktSym">x</span><span class="hspace"> </span><span class="RktVal">0</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._%21%29%29" class="RktStxLink" data-pltdoc="x">!</a></span><span class="hspace"> </span><span class="RktSym"><a href="glossary.html#%28def._%28%28lib._racklog%2Fmain..rkt%29._~25fail%29%29" class="RktValLink" data-pltdoc="x">%fail</a></span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktPn">(</span><span class="RktSym">x</span><span class="hspace"> </span><span class="RktSym">y</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._~25is%29%29" class="RktStxLink" data-pltdoc="x">%is</a></span><span class="hspace"> </span><span class="RktSym">x1</span><span class="hspace"> </span><span class="RktPn">(</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._-%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x"><span class="nobreak">-</span></a></span><span class="hspace"> </span><span class="RktSym">x</span><span class="hspace"> </span><span class="RktVal">1</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">%factorial</span><span class="hspace"> </span><span class="RktSym">x1</span><span class="hspace"> </span><span class="RktSym">y1</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._~25is%29%29" class="RktStxLink" data-pltdoc="x">%is</a></span><span class="hspace"> </span><span class="RktSym">y</span><span class="hspace"> </span><span class="RktPn">(</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._%252A%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">*</a></span><span class="hspace"> </span><span class="RktSym">y1</span><span class="hspace"> </span><span class="RktSym">x</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></blockquote><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">%factorial</span><span class="hspace"> </span><span class="RktVal">0</span><span class="hspace"> </span><span class="RktVal">1</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></td></tr><tr><td><p><span class="RktRes">'()</span></p></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="glossary.html#%28def._%28%28lib._racklog%2Fmain..rkt%29._~25more%29%29" class="RktValLink" data-pltdoc="x">%more</a></span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">#f</span></p></td></tr><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">%factorial</span><span class="hspace"> </span><span class="RktVal"><span class="nobreak">-1</span></span><span class="hspace"> </span><span class="RktVal">1</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><p>Using <span style="font-style: italic">raw</span> cuts as above can get very confusing. For this
reason, it is advisable to use it hidden away in
well-understood abstractions. Two such common abstractions
are the conditional and negation.</p><h4 x-source-module="(lib "racklog/racklog.scrbl")" x-part-tag=""if-then-else"">8.1<tt> </tt><a name="(part._if-then-else)"></a>Conditional Goals</h4><p>An “if ... then ... else ...” predicate can be defined
as follows</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktSym"><a href="glossary.html#%28def._%28%28lib._racklog%2Fmain..rkt%29._~25if-then-else%29%29" class="RktValLink" data-pltdoc="x">%if-then-else</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._~25rel%29%29" class="RktStxLink" data-pltdoc="x">%rel</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">p</span><span class="hspace"> </span><span class="RktSym">q</span><span class="hspace"> </span><span class="RktSym">r</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktPn">(</span><span class="RktSym">p</span><span class="hspace"> </span><span class="RktSym">q</span><span class="hspace"> </span><span class="RktSym">r</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktSym">p</span><span class="hspace"> </span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._%21%29%29" class="RktStxLink" data-pltdoc="x">!</a></span><span class="hspace"> </span><span class="RktSym">q</span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktPn">(</span><span class="RktSym">p</span><span class="hspace"> </span><span class="RktSym">q</span><span class="hspace"> </span><span class="RktSym">r</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktSym">r</span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></blockquote><p>(Note that for the first time we have predicate arguments that
are themselves goals.)</p><p>Consider the goal</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"><a href="glossary.html#%28def._%28%28lib._racklog%2Fmain..rkt%29._~25if-then-else%29%29" class="RktValLink" data-pltdoc="x">%if-then-else</a></span><span class="hspace"> </span><span class="RktSym">Gbool</span><span class="hspace"> </span><span class="RktSym">Gthen</span><span class="hspace"> </span><span class="RktSym">Gelse</span><span class="RktPn">)</span></p></blockquote><p>We first unify <span class="RktInBG"><span class="hspace"></span><span class="RktIn">G0</span><span class="hspace"></span></span> with the first clause-head,
giving
<span class="RktPn">[</span><span class="RktSym">p</span><span class="stt"> </span><span class="RktPn">. </span><span class="RktSym">Gbool</span><span class="RktPn">]</span>, <span class="RktPn">[</span><span class="RktSym">q</span><span class="stt"> </span><span class="RktPn">. </span><span class="RktSym">Gthen</span><span class="RktPn">]</span>, <span class="RktPn">[</span><span class="RktSym">r</span><span class="stt"> </span><span class="RktPn">. </span><span class="RktSym">Gelse</span><span class="RktPn">]</span>. <span class="RktInBG"><span class="hspace"></span><span class="RktIn">Gbool</span><span class="hspace"></span></span> can
now either succeed or fail.</p><p>Case 1: If <span class="RktInBG"><span class="hspace"></span><span class="RktIn">Gbool</span><span class="hspace"></span></span> fails, backtracking will cause the
<span class="RktInBG"><span class="hspace"></span><span class="RktIn">G0</span><span class="hspace"></span></span> to unify with the second clause-head. <span class="RktSym">r</span> is bound
to <span class="RktInBG"><span class="hspace"></span><span class="RktIn">Gelse</span><span class="hspace"></span></span>, and so <span class="RktInBG"><span class="hspace"></span><span class="RktIn">Gelse</span><span class="hspace"></span></span> is tried, as expected.</p><p>Case 2: If <span class="RktInBG"><span class="hspace"></span><span class="RktIn">Gbool</span><span class="hspace"></span></span> succeeds, the cut commits to this
clause of the <span class="RktSym"><a href="glossary.html#%28def._%28%28lib._racklog%2Fmain..rkt%29._~25if-then-else%29%29" class="RktValLink" data-pltdoc="x">%if-then-else</a></span>. We now try <span class="RktInBG"><span class="hspace"></span><span class="RktIn">Gthen</span><span class="hspace"></span></span>. If
<span class="RktInBG"><span class="hspace"></span><span class="RktIn">Gthen</span><span class="hspace"></span></span> should now fail —<wbr></wbr> or even if we simply retry for
more solutions —<wbr></wbr> we are guaranteed that the second
clause-head will not be tried. If it were not for the cut,
<span class="RktInBG"><span class="hspace"></span><span class="RktIn">G0</span><span class="hspace"></span></span> would attempt to unify with the second clause-head, which will
of course succeed, and <span class="RktInBG"><span class="hspace"></span><span class="RktIn">Gelse</span><span class="hspace"></span></span> <span style="font-style: italic">will</span> be tried.</p><h4 x-source-module="(lib "racklog/racklog.scrbl")" x-part-tag=""not"">8.2<tt> </tt><a name="(part._not)"></a>Negation as Failure</h4><p>Another common abstraction using the cut is <span style="font-style: italic">negation</span>.
The negation of goal <span class="RktInBG"><span class="hspace"></span><span class="RktIn">G</span><span class="hspace"></span></span> is defined as <span class="RktPn">(</span><span class="RktSym"><a href="glossary.html#%28def._%28%28lib._racklog%2Fmain..rkt%29._~25not%29%29" class="RktValLink" data-pltdoc="x">%not</a></span><span class="stt"> </span><span class="RktSym">G</span><span class="RktPn">)</span>, where
the predicate <span class="RktSym"><a href="glossary.html#%28def._%28%28lib._racklog%2Fmain..rkt%29._~25not%29%29" class="RktValLink" data-pltdoc="x">%not</a></span> is defined as follows:</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktSym"><a href="glossary.html#%28def._%28%28lib._racklog%2Fmain..rkt%29._~25not%29%29" class="RktValLink" data-pltdoc="x">%not</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._~25rel%29%29" class="RktStxLink" data-pltdoc="x">%rel</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="RktPn">(</span><span class="RktSym">g</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktSym">g</span><span class="hspace"> </span><span class="RktSym"><a href="glossary.html#%28form._%28%28lib._racklog%2Fmain..rkt%29._%21%29%29" class="RktStxLink" data-pltdoc="x">!</a></span><span class="hspace"> </span><span class="RktSym"><a href="glossary.html#%28def._%28%28lib._racklog%2Fmain..rkt%29._~25fail%29%29" class="RktValLink" data-pltdoc="x">%fail</a></span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktPn">(</span><span class="RktSym">g</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktSym"><a href="glossary.html#%28def._%28%28lib._racklog%2Fmain..rkt%29._~25true%29%29" class="RktValLink" data-pltdoc="x">%true</a></span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></blockquote><p>Thus, <span class="RktSym">g</span>’s negation is deemed a failure if <span class="RktSym">g</span>
succeeds, and a success if <span class="RktSym">g</span> fails. This is of course
confusing goal failure with falsity. In some cases, this
view of negation is actually helpful.</p><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="lv-manip.html" title="backward to "7 Manipulating Racklog Variables"" data-pltdoc="x">← prev</a> <a href="index.html" title="up to "Racklog: Prolog-Style Logic Programming"" data-pltdoc="x">up</a> <a href="set-of.html" title="forward to "9 Set Predicates"" data-pltdoc="x">next →</a></span> </div></div></div><div id="contextindicator"> </div></body></html>
|