2.21 Prolog

Complete this assignment with Team Three.

You must submit this in an archive named "prolog.zip".

You must submit this in a file named "prolog.ss".

You must complete this assignment in the PLAI Scheme language. You can do so by choosing it from the Language|Choose Language... menu in DrScheme or via the language chooser at the bottom-left. You can also choose the Module language and have the following as the first line of your program:

#lang planet plai/plai

In this assignment, you will implement Prolog-style logic variables and backtracking search using Scheme’s macros and continuations.

In this assignment, a prolog-expression? is a function that accepts a failure-continuation? and returns a success-continuation?.

A failure-continuation? is a function that accepts a value (which it ignores) and fails; failure may mean aborting the entire Prolog search (meaning it returns nothing), or it may mean backtracking to an earlier point and trying something different (meaning it returns a success-continuation?).

A success-continuation? is a function that accepts a value (which it ignores) and tries again; trying again may not be possible, so the search is aborted (meaning it returns nothing), or it may mean backtracking to an earlier point and trying something different (meaning it returns a success-continuation?).

You must define a new data structure for logic-variable?s. The assignment text imposes some constraints on this data structure. This data structure will contain prolog-value?s. prolog-value?s are numbers, strings, symbols, logic-variable?s, empty, or cons cells that only contain prolog-value?s.

You must implement the following:

=succeed : prolog-expression?

Succeeds exactly once.

=fail : prolog-expression?

Never succeeds.

(_) → logic-variable?

Returns a fresh anonymous variable. This always succeeds and affects nothing else.

(=var (v ...) e)

identifier?

Binds all of the v identifiers to fresh logic variables (returned from _) and evaluates e in the extended environment.

This can be implemented by expanding to let.

(=or2 e1 e2) → prolog-expression?

e1 : prolog-expression?

e2 : prolog-expression?

Succeeds when either e1 or e2 succeeds. If e1 succeeds n times and e2 succeeds m times then (=or2 e1 e2) succeeds (+ n m) times, with all of the e1 successes before the e2 successes.

For example, (=or2 (=or2 =succeed =succeed) =succeed) succeeds 3 times.

(=and2 e1 e2) → prolog-expression?

e1 : prolog-expression?

e2 : prolog-expression?

Succeeds when both e1 and e2 succeed. If e1 succeeds many times, then e2 must be evaluate for each of those times, with all of its successes for a particular e1 success succeeding before e1 succeeds again. In many cases this means (=and2 e1 e2) suceeds (* n m) times if e1 succeeds n times and e2 succeeds m times. (This is not always the case because some of e1’s successes may be incompatible with e2.)

For example, (=and2 (=or2 =succeed =succeed) =succeed) succeeds 2 times.

(=or e ...)

prolog-expression?

Like =or2 but for many Prolog expressions.

(=and e ...)

prolog-expression?

Like =and2 but for many Prolog expressions.

(=find-all (v ...) e)

v : identifier?
e : prolog-expression?

Evaluates to a list of all the solutions to e. Each solution is a list of logic variable bindings (one binding for each of the v). Each variable binding is a two-element list consisting of the quoted variable name (a symbol) and its value. Note that if the value is a list, it should be returned as a Scheme list.

The solutions should be returned in the order of their discovery (by a left-to-right depth-first search) and each solution should list the variables in the order provided.

For example,

(=find-all (x y)

(=or (=and (== x 1) (== y 2))

(=and (== x 3) (== y 4))

(=and (== x 5) (== y 6))))

evalutes to

(list (list (list 'x 1) (list 'y 2))

(list (list 'x 3) (list 'y 4))

(list (list 'x 5) (list 'y 6)))

(=find-some n (v ...) e)

   n : exact-nonnegative-integer?
   v : identifier?
   e : prolog-expression?

Like =find-all, except the search is bound to at most n solutions. This makes it possible to test queries with infinite solutions.

(== e1 e2) → prolog-expression?

e1 : prolog-value?

e2 : prolog-value?

Attempts to unify e1 and e2, succeeding at most once.

If e1 and e2 can be unified, the expression succeeds. If they cannot be unified, the expression fails. Unification must always terminate: you must implement an occurs check.

Two Scheme values can be unified if they are equal?. For example, (== 5 5) succeeds, whereas (== 0 1) fails. Unification for logic variables is trickier. If a logic variable is unbound, it assumes the value necessary to make the expression succeed. For example, the following expression succeeds:

(=var (x) (== x 0))

The logic variable x assumes the value 0. However, if a logic variable is already bound, it must be treated as the value its bound to. For example, the following expression fails:

(=var (x) (=and (== x 0) (== x 1)))

2.21.1 Interactive Testing

These are not required by the assignment, but to aid in interactive testing (as shown in the examples below), you may find the following two definitions helpful:

(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" 'vars (lv-value vars))

...

(void))))

'fail))]))

where lv-value accesses the value stored in the given logic variable.

Please note that these definitions are very implementation specific.

2.21.2 Testing Harness

Please use the following definitions to help you with your testing:

; symbol -> boolean : returns true if and only if the given

; symbol is an uninterned symbol

(define (gensym? s)

(not (equal? (string->symbol (symbol->string s)) s)))

; list X list -> boolean : takes two bindings (for example,

; returned from =find-all) and returns true if and only if

; the two variables they bind are equal to the same thing.

(define (binding-equal? b1 b2)

(equal? (second b1) (second b2)))

; Prolog-Expr X symbol X bool-Exprs ... -> Test result : Takes a

; (=find-all ...) or (=find-some ...), an identifier, and a set of

; expressions that evaluate to booleans when the identifier is

; bound to the result of the given Prolog-expr. The test passes

; if and only if all of the boolean expressions are true.

(define-syntax test-prolog

(syntax-rules (test-prolog)

[(test-prolog find-expr result-id bool ...)

(test (let ([result-id find-expr])

(and bool ...)) true)]))

2.21.3 Additional Notes

Do not use global variables for this assignment. We expect your implementation to have the ability to do a query, capture the continuation returned, do a different query, and then invoke the first continuation with no trouble.

Unbound variables should have a unique “value” in their output. That is, if y is unbound, it should have a unique symbol as its value. If x and y are dependently unbound, they should have the same unique symbol as their values. For example, in the evaluation of (=var (x y) (== x y)), x and y are dependently unbound.

Remember that order counts. Please carefully read the definitions for =find-all and =find-some. Even if your results are correct, if they are in the wrong order or format, they will be marked as incorrect.

2.21.4 Example 1: Simple Search

You might want to start by just testing =and and =or with =succeed and =fail (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. You can also use the following test-prolog expression:

(test-prolog

(=find-all () (=or (=and =succeed =succeed)

(=and =fail =succeed =succeed)

(=and =succeed)))

result

(= (length result) 2))

2.21.5 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)))

← prev up next →

1	Introduction
2	Assignments
3	Lectures
4	Help
5	Turn In Policy
6	Readings
7	Software
8	Exams
9	Grading
10	Your Final Grade
11	Team Work
12	Codewalks
13	Advice

2.1	Musical Notation
2.2	Survey
2.3	Basic Scheme
2.4	Lists and Trees
2.5	Higher-order Functions
2.6	Rudimentary Interpreter
2.7	Substitution
2.8	Extended Interpreter
2.9	Laziness and Infinite Data
2.10	Laziness
2.11	Raw Web Programming
2.12	Language Design
2.13	Continuations
2.14	PLT Web Programming
2.15	Garbage Collectors
2.16	Garbage Collection
2.17	Type Checking
2.18	Type Checker
2.19	Type Inferrer
2.20	Type Inference
2.21	Prolog
2.22	Final

2.21.1	Interactive Testing
2.21.2	Testing Harness
2.21.3	Additional Notes
2.21.4	Example 1: Simple Search
2.21.5	Example 2: Family Trees