Implementing Prolog
You will use the same team for this assignment as for the previous one. Please remember to follow the style and testing guidelines outlined in the syllabus.
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:
-
(== e1 e2)
: attempts to unifye1
withe2
(succeeds at most once) -
=succeed
: succeeds exactly once -
=fail
: does not succeed -
(== e1 e2)
: attempts to unifye1
withe2
(succeeds at most once) -
(=var (v ...) e)
: binds all of the(v ...)
to fresh logic variables and evaluatese
in the extended environment -
(_)
: returns a fresh anonymous variable (its binding always succeeds and affects nothing else) -
(=or e ...)
: searches for variable assignments that satisfy any of thee ...
expressions -
(=and e ...)
: searches for variable assignments that satisfy all of thee ...
expressions
==
,
=succeed
, =fail
, =or
, and
=and
) consume a failure continuation (to be
invoked on failure) and, if successful, return a success
continuation (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:
-
(=find-all (v ...) e)
: returns a list of all the solutions toe
; each solution is a list of variable binding (one binding for each of thev ...
), 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. -
(=find-some n (v ...) e)
: returns a list of solutions toe
, as in(findall ...)
from above, except that search is bounded to at mostn
solutions (this allows us to test on queries with infinite solutions)
show
and next
:
(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))]))
Example 1: Simple Search
You might want to start by just testing =and
and
=or
with success and failure (no logic variables). In
this restricted setting, there are a couple of useful properties:
namely, if e1
succeeds in n1 ways, e2
succeeds in n2 ways, etc., then (=or e1 e2 ...)
succeeds in n1 + n2 + ... ways, and (=and e1 e2
...)
succeeds in n1 * n2 * ... ways. For instance,
(=and (=or =succeed =succeed =fail =succeed) (=or =fail =succeed =succeed))succeeds in six ways. The first
=or
succeeds in three
ways, the second =or
succeeds in two ways, and the
=and
combines them in all possible ways.
Likewise,
(=or (=and =succeed =succeed) (=and =fail =succeed =succeed) (=and =succeed))succeeds in two ways. The first and third
=and
s each
succeed in one way, and the =or
explores both of
them.
You can use show
(with an empty variable list) and
next
to count how many times a query succeeds.
Example 2: Family Trees
As a more complicated example, suppose we have the following definitions:
(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)))))Then we get the following query results:
> (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)))
Hand In
Only one partner should submit the .ss files for the implementation and a readme to WebCT. The readme file should contain the names of the members of the group. The other member of the group should submit an empty file. If you do not submit to WebCT, you will not receive a grade for the assignment.
FAQ
Nothing yet.