Due: Ideally by end of term, but negotiable. Submit by email to Kathi
Collaboration Policy:
Pairs Permitted
For this assignment, you will implement the core of Prolog as outlined below. This requires a combination of continuations and a bit of macros (as you saw in 2135/1102).
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. SWI Prolog is available on CCC Unix (command "pl" starts the evaluator), or you can download it to your own computer.
This is a challenging assignment, pulling together various concepts from across the course. If you've struggled with the assignments so far, you are unlikely to be able to do this one.
Grading will be done by 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. For pair submissions, both students are expected to participate in codewalk. This will confirm that both of you understand the submitted solution. We will schedule codewalks after you are done with the assignment.
As this assignment has no bearing on your undergrad course grade, I can be flexible with the due date. The main constraint is that I will be out of the country for a month starting a few days after C term ends. Ideally, I'd like to run the codewalks by the Tuesday after C term. If you want to work on this through break though, we can schedule your codewalk for mid-April instead.
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:
=succeed : succeeds exactly once =fail : does not succeed (== e1 e2) : attempts to unify e1
with e2 (succeeds at most once)
(=var (v ...) e) : binds all of the (v
...) to fresh logic variables and evaluates e 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 the e ... expressions
(=and e ...) : searches for variable assignments
that
satisfy all of the e ... 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 to e; each solution is a list of variable
bindings (one binding for each of the v ...), 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 to e, as in (findall ...) from
above, except that search is bounded to at most n
solutions (this allows us to test queries with infinite numbers of
solutions)
next (produces next solution) and show
(starts producing solutions):
(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))]))
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.
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)))
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).
Nothing yet ...