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:

Some of these abstractions may be implementable as Scheme procedures, while others will require the use of macros. In either case, recall the pattern we developed in class for performing backtracking: the unification and search primitives (i.e., ==, =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: For interactive testing, you may include the following definitions for 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 =ands 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.