►Programming Language Design (Fall 2012)
▼3 Assignments
►3.12 Prolog
On this page:
=fail
=succeed
=and2
=or2
=and
=or
=find-some
=find-all
_
=var
==
3.12.1 Interactive Testing
3.12.2 Testing Harness
3.12.3 Additional Notes
3.12.4 Example 1: Simple Search
3.12.5 Example 2: Family Trees
    ← prev  up  next → 

3.12 Prolog

You must complete this assignment using a specific language. Choose Determine language from source in the DrRacket menu, then write

#lang plai

as the first line of your program, overwritting the default #lang at the top of the file.

In this assignment, you will implement Prolog-style logic variables and backtracking search using Racket’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 booleans, numbers, strings, symbols, logic-variable?s, empty, or cons cells that only contain prolog-value?s.

You must implement the following, and I suggest writing them in this order:

value

=fail : prolog-expression?

Never succeeds.

value

=succeed : prolog-expression?

Succeeds exactly once.

procedure

(=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 evaluated 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.

procedure

(=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.

syntax

(=and e ...)

 
  e : prolog-expression?
Like =and2 but for many Prolog expressions and short-circuiting.

syntax

(=or e ...)

 
  e : prolog-expression?
Like =or2 but for many Prolog expressions and short-circuiting.

syntax

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

 
  n : exact-nonnegative-integer?
  v : identifier?
  e : prolog-expression?
Binds each v with =var and 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 Racket 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. The search is bound to at most n solutions. This makes it possible to test queries with infinite solutions.

For example,
(=find-some 3 (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)))

In your first version of this, before you’ve implemented =var, just ignore the new logic variables.

This macro should probably be paired with a function that does most of the work.

syntax

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

 
  v : identifier?
  e : prolog-expression?
Like =find-some, except uses +inf.0 (infinity) as the bound.

procedure

(_) → logic-variable?

Returns a fresh anonymous variable.

syntax

(=var (v ...) e)

 
  v : 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.

procedure

(== 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 Racket 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)))

3.12.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.

3.12.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)]))

3.12.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.

3.12.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))

3.12.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 →