temperance/usage/index.html @ f5e7f6bd113f

temperance: Update site.
author Steve Losh <steve@stevelosh.com>
date Sun, 22 Oct 2017 14:54:40 -0400
parents 7f39fe8a8012
children (none)
<!DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8"/>
        <title>Usage / Temperance</title>
        <link rel="stylesheet" href="../_dmedia/pygments-clean.css"/>
        <link rel="stylesheet/less" type="text/css" href="../_dmedia/style.less"/>
        <script src="../_dmedia/less.js" type="text/javascript">
        </script>
    </head>
    <body class="content">
        <div class="wrap">
            <header><h1><a href="..">Temperance</a></h1></header>
                <div class="markdown">
<h1 id="usage"><a href="">Usage</a></h1><p>This guide assumes you know the basics of logic programming.  If you've never
done any logic programming before, you should probably start with an
introduction to that before trying to read this.</p>
<div class="toc">
<ul>
<li><a href="#hello-temperance">Hello, Temperance</a></li>
<li><a href="#databases">Databases</a></li>
<li><a href="#logic-frames">Logic Frames</a><ul>
<li><a href="#assertion-pushing">Assertion / Pushing</a></li>
<li><a href="#retraction-popping">Retraction / Popping</a></li>
<li><a href="#convenience">Convenience</a></li>
<li><a href="#restrictions">Restrictions</a></li>
<li><a href="#why">Why?</a></li>
</ul>
</li>
<li><a href="#rules">Rules</a><ul>
<li><a href="#basic-rulefact-macros">Basic Rule/Fact Macros</a></li>
<li><a href="#dynamic-rules">Dynamic Rules</a></li>
</ul>
</li>
<li><a href="#queries">Queries</a><ul>
<li><a href="#query">query</a></li>
<li><a href="#query-all">query-all</a></li>
<li><a href="#query-map">query-map</a></li>
<li><a href="#query-for">query-for</a></li>
<li><a href="#query-do">query-do</a></li>
<li><a href="#query-find">query-find</a></li>
<li><a href="#prove">prove</a></li>
<li><a href="#anonymous-variables">Anonymous Variables</a></li>
<li><a href="#dynamic-queries">Dynamic Queries</a></li>
</ul>
</li>
<li><a href="#lists">Lists</a></li>
<li><a href="#cut">Cut</a></li>
<li><a href="#call">Call</a></li>
<li><a href="#built-in-predicates">Built-In Predicates</a></li>
</ul></div>
<h2 id="hello-temperance">Hello, Temperance</h2>
<p>Temperance is a pretty big system and we'll need to look at a few different
pieces one by one before you'll have a good picture of how it all fits
together, but let's at least get something on the screen.  First we'll set up
a logic database with some basic facts:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">in-package</span> <span class="ss">:cl-user</span><span class="p">)</span>
<span class="p">(</span><span class="nb">use-package</span> <span class="ss">:temperance</span><span class="p">)</span>

<span class="p">(</span><span class="nv">push-logic-frame</span> <span class="no">t</span><span class="p">)</span>

<span class="p">(</span><span class="nv">facts</span> <span class="no">t</span>
  <span class="p">(</span><span class="nv">likes</span> <span class="nv">steve</span> <span class="nv">cats</span><span class="p">)</span>
  <span class="p">(</span><span class="nv">likes</span> <span class="nv">steve</span> <span class="nv">beer</span><span class="p">)</span>
  <span class="p">(</span><span class="nv">likes</span> <span class="nv">kim</span> <span class="nv">cats</span><span class="p">)</span>
  <span class="p">(</span><span class="nv">likes</span> <span class="nv">kim</span> <span class="nv">tea</span><span class="p">)</span>
  <span class="p">(</span><span class="nv">likes</span> <span class="nv">sally</span> <span class="nv">cats</span><span class="p">)</span>
  <span class="p">(</span><span class="nv">likes</span> <span class="nv">sally</span> <span class="nv">beer</span><span class="p">))</span>

<span class="p">(</span><span class="nv">rule</span> <span class="no">t</span> <span class="p">(</span><span class="nv">likes</span> <span class="nv">sally</span> <span class="nv">?who</span><span class="p">)</span>
  <span class="p">(</span><span class="nv">likes</span> <span class="nv">?who</span> <span class="nv">cats</span><span class="p">))</span>

<span class="p">(</span><span class="nv">finalize-logic-frame</span> <span class="no">t</span><span class="p">)</span>
</pre></div>


<p>Ignore the stuff about logic frames for now.  We've added some facts saying:</p>
<ul>
<li>Steve and Sally like cats and beer</li>
<li>Kim likes cats and tea</li>
<li>Sally also likes anybody who likes cats</li>
</ul>
<p>And now we can ask some questions:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">query-all</span> <span class="no">t</span> <span class="p">(</span><span class="nv">likes</span> <span class="nv">?who</span> <span class="nv">beer</span><span class="p">))</span>
<span class="c1">; =&gt;</span>
<span class="c1">; ((?WHO STEVE)</span>
<span class="c1">;  (?WHO SALLY))</span>

<span class="p">(</span><span class="nv">query-all</span> <span class="no">t</span> <span class="p">(</span><span class="nv">likes</span> <span class="nv">sally</span> <span class="nv">?what</span><span class="p">))</span>
<span class="c1">; =&gt;</span>
<span class="c1">; ((?WHAT CATS)</span>
<span class="c1">;  (?WHAT BEER)</span>
<span class="c1">;  (?WHAT STEVE)</span>
<span class="c1">;  (?WHAT KIM)</span>
<span class="c1">;  (?WHAT SALLY))</span>

<span class="p">(</span><span class="nv">query-all</span> <span class="no">t</span> <span class="p">(</span><span class="nv">likes</span> <span class="nv">?who</span> <span class="nv">?what</span><span class="p">))</span>
<span class="c1">; =&gt;</span>
<span class="c1">; ((?WHAT CATS ?WHO STEVE)</span>
<span class="c1">;  (?WHAT BEER ?WHO STEVE)</span>
<span class="c1">;  (?WHAT CATS ?WHO KIM)</span>
<span class="c1">;  (?WHAT TEA ?WHO KIM)</span>
<span class="c1">;  (?WHAT CATS ?WHO SALLY)</span>
<span class="c1">;  (?WHAT BEER ?WHO SALLY)</span>
<span class="c1">;  (?WHAT STEVE ?WHO SALLY)</span>
<span class="c1">;  (?WHAT KIM ?WHO SALLY)</span>
<span class="c1">;  (?WHAT SALLY ?WHO SALLY))</span>
</pre></div>


<h2 id="databases">Databases</h2>
<p>The main data structure of Temperance is a database.  Most functions in
Temperance's API take this as their first argument.</p>
<p>You can create a database with <code>make-database</code>:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">make-database</span><span class="p">))</span>
<span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*db2*</span> <span class="p">(</span><span class="nv">make-database</span><span class="p">))</span>
</pre></div>


<p>You can then use it in other functions:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">push-logic-frame</span> <span class="vg">*db*</span><span class="p">)</span>

<span class="p">(</span><span class="nv">fact</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">drink</span> <span class="nv">coffee</span><span class="p">))</span>
<span class="p">(</span><span class="nv">fact</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">drink</span> <span class="nv">tea</span><span class="p">))</span>
<span class="p">(</span><span class="nv">fact</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">drink</span> <span class="nv">water</span><span class="p">))</span>

<span class="p">(</span><span class="nv">finalize-logic-frame</span> <span class="vg">*db*</span><span class="p">)</span>

<span class="p">(</span><span class="nv">query-all</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">drink</span> <span class="nv">?what</span><span class="p">))</span>
<span class="c1">; =&gt;</span>
<span class="c1">; ((?WHAT COFFEE)</span>
<span class="c1">;  (?WHAT TEA)</span>
<span class="c1">;  (?WHAT WATER))</span>

<span class="p">(</span><span class="nv">query-all</span> <span class="vg">*db2*</span> <span class="p">(</span><span class="nv">drink</span> <span class="nv">?what</span><span class="p">))</span>
<span class="c1">; =&gt;</span>
<span class="c1">; NIL</span>
</pre></div>


<p>Temperance also creates a database by default and stores it in
<code>*standard-database*</code>.  You can pass <code>t</code> to functions instead of a database
object to operate on this standard database if you don't want to bother creating
one of your own.</p>
<p>Databases are not (currently) thread-safe.  The consequences are undefined if
you access the same database object concurrently.  Thread-safety is on the
<strong>TODO</strong> list.</p>
<h2 id="logic-frames">Logic Frames</h2>
<p>Temperance supports adding/retracting rules and facts to/from a database at
runtime, but it has a special interface for doing this in the interest of speed.</p>
<p>(Note: from here on out we'll say "rules" to mean "rules and facts", because
facts are just rules with empty bodies.)</p>
<h3 id="assertion-pushing">Assertion / Pushing</h3>
<p>Each Temperance database has a "logic stack" consisting of zero or more "logic
frames".  To add some rules to the database you push a logic frame onto the
stack, add the rules, and then finalize the logic frame to compile the rules
into Prolog bytecode:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">make-database</span><span class="p">))</span>

<span class="c1">; Nothing's in the database yet.</span>
<span class="p">(</span><span class="nv">query-all</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">drink</span> <span class="nv">?what</span><span class="p">))</span>
<span class="c1">; =&gt; NIL</span>

<span class="c1">; Push a logic frame.</span>
<span class="p">(</span><span class="nv">push-logic-frame</span> <span class="vg">*db*</span><span class="p">)</span>

<span class="c1">; Still nothing in the DB.</span>
<span class="p">(</span><span class="nv">query-all</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">drink</span> <span class="nv">?what</span><span class="p">))</span>
<span class="c1">; =&gt; NIL</span>

<span class="c1">; Add some facts.</span>
<span class="p">(</span><span class="nv">fact</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">drink</span> <span class="nv">coffee</span><span class="p">))</span>
<span class="p">(</span><span class="nv">fact</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">drink</span> <span class="nv">tea</span><span class="p">))</span>
<span class="p">(</span><span class="nv">fact</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">drink</span> <span class="nv">water</span><span class="p">))</span>

<span class="c1">; There's STILL nothing in the DB, because we haven't</span>
<span class="c1">; finalized the frame yet!</span>
<span class="p">(</span><span class="nv">query-all</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">drink</span> <span class="nv">?what</span><span class="p">))</span>
<span class="c1">; =&gt; NIL</span>

<span class="c1">; Finalize the frame.  This compiles `drink`'s rules</span>
<span class="c1">; into bytecode.</span>
<span class="p">(</span><span class="nv">finalize-logic-frame</span> <span class="vg">*db*</span><span class="p">)</span>

<span class="c1">; And now we can finally see some results.</span>
<span class="p">(</span><span class="nv">query-all</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">drink</span> <span class="nv">?what</span><span class="p">))</span>
<span class="c1">; =&gt; ((?WHAT COFFEE) (?WHAT TEA) (?WHAT WATER))</span>
</pre></div>


<h3 id="retraction-popping">Retraction / Popping</h3>
<p>You can pop a logic frame off the stack to retract everything inside it:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">query-all</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">drink</span> <span class="nv">?what</span><span class="p">))</span>
<span class="c1">; =&gt; ((?WHAT COFFEE) (?WHAT TEA) (?WHAT WATER))</span>

<span class="p">(</span><span class="nv">pop-logic-frame</span> <span class="vg">*db*</span><span class="p">)</span>

<span class="p">(</span><span class="nv">query-all</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">drink</span> <span class="nv">?what</span><span class="p">))</span>
<span class="c1">; =&gt; NIL</span>
</pre></div>


<h3 id="convenience">Convenience</h3>
<p>Most of the time you'll want to push a logic frame, add some stuff, and then
immediately finalize it.  Temperance provides a <code>push-logic-frame-with</code> macro to
make this easier:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">push-logic-frame-with</span> <span class="vg">*db*</span>
  <span class="p">(</span><span class="nb">princ</span> <span class="s">"Adding some facts..."</span><span class="p">)</span>
  <span class="p">(</span><span class="nv">fact</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">sound</span> <span class="nv">cat</span> <span class="nv">meow</span><span class="p">))</span>
  <span class="p">(</span><span class="nv">fact</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">sound</span> <span class="nv">dog</span> <span class="nv">woof</span><span class="p">))</span>
  <span class="p">(</span><span class="nv">fact</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">sound</span> <span class="nv">cow</span> <span class="nv">moo</span><span class="p">)))</span>
<span class="c1">; =&gt; Adding some facts...</span>

<span class="p">(</span><span class="nv">query-all</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">sound</span> <span class="nv">cat</span> <span class="nv">?what</span><span class="p">))</span>
<span class="c1">; =&gt; ((?WHAT MEOW))</span>
</pre></div>


<p>Note how the body of <code>push-logic-frame-with</code> takes arbitrary code, not just
rules and facts.</p>
<h3 id="restrictions">Restrictions</h3>
<p>There main limitation introduced by Temperance's logic stack is that any
particular predicate must exist entirely in a single logic frame.  You <em>cannot</em>
spread the definition of a single predicate across multiple frames:</p>
<div class="codehilite"><pre><span/><span class="c1">; This is fine</span>
<span class="p">(</span><span class="nv">push-logic-frame-with</span> <span class="vg">*db*</span>
  <span class="p">(</span><span class="nv">fact</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">sound</span> <span class="nv">cat</span> <span class="nv">meow</span><span class="p">)))</span>

<span class="c1">; ERROR!  `sound/2` was already defined in a previous frame!</span>
<span class="p">(</span><span class="nv">push-logic-frame-with</span> <span class="vg">*db*</span>
  <span class="p">(</span><span class="nv">fact</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">sound</span> <span class="nv">dog</span> <span class="nv">woof</span><span class="p">)))</span>
</pre></div>


<h3 id="why">Why?</h3>
<p>Why does Temperance bother with this stack interface?  Why not just allow
arbitrary assertion and retraction of facts?</p>
<p>Arbitrary assertion and retraction would be a friendlier interface, but would be
slower.  Temperance was made with General Game Playing in mind, where speed is
important.  Asserting and retracting facts with a stack like this allows several
speed improvements:</p>
<ul>
<li>Predicates only need to be compiled once (when their frame is finalized),
  instead of being recompiled every time a new clause is asserted.</li>
<li>Retraction of a frame is lighting fast — it's just changing a single integer
  and zeroing out a contiguous block of memory.</li>
<li>The VM's code store no longer needs to deal with memory fragmentation or
  garbage collection.</li>
</ul>
<h2 id="rules">Rules</h2>
<p>Once you've got an open logic frame you can add some rules to the database.</p>
<h3 id="basic-rulefact-macros">Basic Rule/Fact Macros</h3>
<p>Temperance offers a number of macros for adding things to a logic frame.  <code>(fact
database fact)</code> is the simplest, and will just add a single fact to the
database:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">fact</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">cat</span> <span class="nv">scruffy</span><span class="p">))</span>
</pre></div>


<p>If you want to add more than one fact you can use <code>(facts database fact...)</code>:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">facts</span> <span class="vg">*db*</span>
  <span class="p">(</span><span class="nv">cat</span> <span class="nv">fluffy</span><span class="p">)</span>
  <span class="p">(</span><span class="nv">dog</span> <span class="nv">rover</span><span class="p">)</span>
  <span class="p">(</span><span class="nv">dog</span> <span class="nv">lassie</span><span class="p">)</span>
  <span class="p">(</span><span class="nv">dog</span> <span class="nv">spot</span><span class="p">))</span>
</pre></div>


<p>Adding rules can be done with <code>(rule database head body...)</code>:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">rule</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">pet</span> <span class="nv">?who</span><span class="p">)</span>
  <span class="p">(</span><span class="nv">cat</span> <span class="nv">?who</span><span class="p">))</span>

<span class="p">(</span><span class="nv">rule</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">pet</span> <span class="nv">?who</span><span class="p">)</span>
  <span class="p">(</span><span class="nv">dog</span> <span class="nv">?who</span><span class="p">))</span>
</pre></div>


<p>Logic variables in Temperance are any symbols that start with the <code>?</code> character.</p>
<h3 id="dynamic-rules">Dynamic Rules</h3>
<p>The <code>fact</code>, <code>facts</code>, and <code>rule</code> macros quote their arguments.  If you need to
build rules at runtime you'll need to use the <code>invoke-...</code> variants and manage
the quoting yourself:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defun</span> <span class="nv">add-cat-lover</span> <span class="p">(</span><span class="nv">database</span> <span class="nv">person</span><span class="p">)</span>
  <span class="p">(</span><span class="nv">invoke-rule</span> <span class="nv">database</span>
      <span class="o">`</span><span class="p">(</span><span class="nv">likes</span> <span class="o">,</span><span class="nv">person</span> <span class="nv">?who</span><span class="p">)</span>
    <span class="o">'</span><span class="p">(</span><span class="nv">cat</span> <span class="nv">?who</span><span class="p">)))</span>
</pre></div>


<p>The author is aware that <code>invoke-...</code> is an awful name and welcomes suggestions
for something better.</p>
<h2 id="queries">Queries</h2>
<p>Once you've got some logic frames finalized and ready to go you can query the
database with the <code>query...</code> macros.</p>
<h3 id="query">query</h3>
<p><code>(query database body...)</code> will return two values:</p>
<ul>
<li>A plist of the substitutions necessary to make <code>body</code> true (or <code>nil</code> if none
  is possible).</li>
<li><code>t</code> if the query was successful, <code>nil</code> otherwise.</li>
</ul>
<p>The second value lets you distinguish a successful query that required no
bindings from an unsuccessful query.  For example:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">make-database</span><span class="p">))</span>

<span class="p">(</span><span class="nv">push-logic-frame-with</span> <span class="vg">*db*</span>
  <span class="p">(</span><span class="nv">facts</span> <span class="vg">*db*</span>
    <span class="p">(</span><span class="nv">cat</span> <span class="nv">scruffy</span><span class="p">)</span>
    <span class="p">(</span><span class="nv">cat</span> <span class="nv">fluffy</span><span class="p">)))</span>

<span class="p">(</span><span class="nv">query</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">cat</span> <span class="nv">fluffy</span><span class="p">))</span>
<span class="c1">; =&gt;</span>
<span class="c1">; NIL</span>
<span class="c1">; T        successful, no bindings needed</span>

<span class="p">(</span><span class="nv">query</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">cat</span> <span class="nv">chad</span><span class="p">))</span>
<span class="c1">; =&gt;</span>
<span class="c1">; NIL</span>
<span class="c1">; NIL      unsuccessful</span>

<span class="p">(</span><span class="nv">query</span> <span class="vg">*db*</span> <span class="p">(</span><span class="nv">cat</span> <span class="nv">?who</span><span class="p">))</span>
<span class="c1">; =&gt;</span>
<span class="c1">; (?WHO SCRUFFY)</span>
<span class="c1">; T</span>
</pre></div>


<p><code>query</code> only returns the first set of substitutions it finds.  If you want to see <em>all</em> results you'll need to use <code>query-all</code>.</p>
<h3 id="query-all">query-all</h3>
<h3 id="query-map">query-map</h3>
<h3 id="query-for">query-for</h3>
<h3 id="query-do">query-do</h3>
<h3 id="query-find">query-find</h3>
<h3 id="prove">prove</h3>
<h3 id="anonymous-variables">Anonymous Variables</h3>
<p>Each bare <code>?</code> symbol is treated as a separate anonymous variable:</p>
<h3 id="dynamic-queries">Dynamic Queries</h3>
<h2 id="lists">Lists</h2>
<h2 id="cut">Cut</h2>
<h2 id="call">Call</h2>
<h2 id="built-in-predicates">Built-In Predicates</h2>
                </div>
            <footer><p><i>Made with Lisp and love by <a href="http://stevelosh.com/">Steve Losh</a> in Reykjavík, Iceland.</i></p>
<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

  ga('create', 'UA-15328874-3', 'auto');
  ga('send', 'pageview');

</script></footer>
        </div>
    </body>
</html>