CS 4536(BS/MS)/CS536 - Prolog Assignment/title> <base href="http://www.cs.wpi.edu/~cs4536/a09/Assignments/" /> <style type="text/css"> body { color: #336633 ; }  </style> </head> <body> <a name="exercises"> <h2><a href="../index.html">CS 4536(BS/MS)/CS536 </a> Implementing Prolog</h2> <p> <strong>Due: </strong>Anytime before December 17th. Submit by email to Kathi <br> <strong><a href="../policies.html">Collaboration Policy</a>: </strong> Pairs Permitted (but will grade/codewalk individually) </p> <h3>The Assignment</h3> <p>For this assignment, you will implement the core of Prolog as outlined below. This requires a combination of continuations and a small bit of macros.</p> <p>For an introduction to Prolog and its implementation, read chapters 33 and 34 of the text. If you are new to Prolog, you should run at least the programs from chapter 33 to get a feel for it. <a href="http://www.swi-prolog.org/">SWI Prolog</a> is one good Prolog implementation (freely downloadable). If anyone wants to work on CCC machines instead of your own computer, let me know and I'll arrange to have this installed on the CCC machines.</p> <p>Chapter 36 introduces macros. The macros material you need for this assignment is fairly straightforward. Please don't hesitate to ask for an appointment or send mail if you need help with the macros material.</p> <hr> <h4>What to Implement</h4> <p>In this assignment, you will implement Prolog-style logic variables and backtracking search using Scheme's macros and continuations. In particular, you must implement the following: <ul> <li> <code> =succeed </code>: succeeds exactly once </li> <li> <code> =fail </code>: does not succeed </li> <li> <code> (== e1 e2) </code>: attempts to unify <code>e1</code> with <code>e2</code> (succeeds at most once) <li> <code> (=var (v ...) e) </code>: binds all of the <code>(v ...)</code> to fresh logic variables and evaluates <code>e</code> in the extended environment </li> <li> <code> (_) </code>: returns a fresh anonymous variable (its binding always succeeds and affects nothing else) <li> <code> (=or e ...) </code>: searches for variable assignments that satisfy <b>any</b> of the <code>e ...</code> expressions <li> <code> (=and e ...) </code>: searches for variable assignments that satisfy <b>all</b> of the <code>e ...</code> expressions </ul> Some of these abstractions may be implementable as Scheme procedures, while others will require the use of macros (for example, <code>and</code> and <code>or</code> cannot be written as functions since all arguments to functions are evaluated before calling the function). In either case, recall the pattern described in the text for performing backtracking: the unification and search primitives (i.e., <code>==</code>, <code>=succeed</code>, <code>=fail</code>, <code>=or</code>, and <code>=and</code>) consume a <b>failure continuation</b> (to be invoked on failure) and, if successful, return a <b>success continuation</b> (to allow resumption of the search). This pattern prevents the Prolog embedding from communicating ordinary program answers through procedure return values. Instead it uses logic variables, which you will need to update imperatively, taking care to restore when backtracking. In addition to these linguistic extensions, you must also implement the following testing interface: <ul> <li> <code> (=find-all (v ...) e) </code> : returns a list of all the solutions to <code>e</code>; each solution is a list of variable bindings (one binding for each of the <code>v ...</code>), and each variable assignment is a two-element list consisting of the quoted variable name (a symbol) and its value. The solutions should be returned in their order of discovery (by a left-to-right depth-first search), and each solution should list the variables in the order provided.</li> <li> <code> (=find-some n (v ...) e) </code> : returns a list of solutions to <code>e</code>, as in <code>(findall ...)</code> from above, except that search is bounded to at most <code>n</code> solutions (this allows us to test queries with infinite numbers of solutions) </ul> For interactive testing, you may include the following definitions for <code>next</code> (produces next solution) and <code>show</code> (starts producing solutions): <pre> (define resumer-box (box 'resumer)) (define (next) ((unbox resumer-box) 'dummy)) (define-syntax show (syntax-rules () [(show (vars ...) e) (=var (vars ...) (let/cc esc (let/cc fk (esc (let ([next (e fk)]) (set-box! resumer-box next) (printf "~a: ~a~n" (quote vars) (lv-value vars)) ... (void)))) 'fail))])) </pre> <h4> Example 1: Simple Search </h4> <p> You might want to start by just testing <code>=and</code> and <code>=or</code> with success and failure (no logic variables). In this restricted setting, there are a couple of useful properties: namely, if <code>e1</code> succeeds in <i>n1</i> ways, <code>e2</code> succeeds in <i>n2</i> ways, etc., then <code>(=or e1 e2 ...)</code> succeeds in <i>n1 + n2 + ...</i> ways, and <code>(=and e1 e2 ...)</code> succeeds in <i>n1 * n2 * ...</i> ways. For instance, <pre> (=and (=or =succeed =succeed =fail =succeed) (=or =fail =succeed =succeed)) </pre> succeeds in six ways. The first <code>=or</code> succeeds in three ways, the second <code>=or</code> succeeds in two ways, and the <code>=and</code> combines them in all possible ways. Likewise, <pre> (=or (=and =succeed =succeed) (=and =fail =succeed =succeed) (=and =succeed)) </pre> succeeds in two ways. The first and third <code>=and</code>s each succeed in one way, and the <code>=or</code> explores both of them. <p> You can use <code>show</code> (with an empty variable list) and <code>next</code> to count how many times a query succeeds. <br> <h4> Example 2: Family Trees </h4> <p> As a more complicated example, suppose we have the following definitions: <pre> (define (=parent c p) (=or (=and (== c 'vito) (== p 'dom)) (=and (== c 'sonny) (== p 'vito)) (=and (== c 'michael) (== p 'vito)) (=and (== c 'fredo) (== p 'vito)) (=and (== c 'sophia) (== p 'michael)) (=and (== c 'tony) (== p 'michael)))) (define (=ancestor X Y) (=or (=parent X Y) (=var (Z) (=and (=parent X Z) (=ancestor Z Y))))) </pre> Then we get the following query results: <pre> > (show (x) (=ancestor x 'vito)) x: sonny > (next) x: michael > (next) x: fredo > (next) x: sophia > (next) x: tony > (next) 'fail > (find-all (x) (=parent x 'michael)) (list (list (list 'x 'sophia)) (list (list 'x 'tony))) > (find-some 3 (x y) (=ancestor x y)) (list (list (list 'x 'vito) (list 'y 'dom)) (list (list 'x 'sonny) (list 'y 'vito)) (list (list 'x 'michael) (list 'y 'vito))) </pre> <hr> <h3>Grading</h3> <p>We will grade these through an oral code review (aka "codewalk"). During the codewalk, you'll be asked to present your implementation and to explain how it solves the problem. All students will codewalk individually, even if you worked on the implementation with a partner. We will schedule codewalks after you are done with the assignment.</p> <hr> <h4>What to Turn In</h4> <P>Submit a single Scheme program containing your implementation. Make sure all participating student's names are at the top of the file (in a comment).</p> <hr> <h4>FAQ</h4> <p>Nothing yet ...</p> </body></html>