Complete this assignment with the same team you worked with for Type Inference (Written). You and your partner must each understand the answers to all the problems, so don't just split up the work.

A Brief History of Prolog at Brown

Student: Are you doing Prolog again this year?
Shriram: Yes.
Student: That was the hardest assignment I ever did at Brown—and I even did Weenix!
Shriram: Well, I was thinking of scaling it down this year....
Student: No! You can't do that. It's like a rite of passage.

Overview

In this assignment, you will implement Prolog-style logic variables and backtracking search using Scheme's macros and continuations. Unlike the interpreters you've written so far, the "language" for this assignment is embedded in Scheme, and will use Scheme's environment for its environment, Scheme's store, etc.

The language has two principal features: logic variables and syntactic forms for construction search trees. Search trees are defined by the following grammar:

<search-expr> ::= =succeed
              |   =fail
              |   (=and <search-expr> ...)
              |   (=or <search-expr> ...)
              |   (== <logic-expr> <logic-expr>)
              |   <scheme-expr> ; that evaluates to a <search-expr>

The form (== <logic-expr> <logic-expr>) attempts to unify logic variables and Scheme values:

<logic-expr> ::= (_)
             |  (=cons <logic-expr> <logic-expr>)
             |   <scheme-expr> ; that evaluates to a flat value, list or logic variable
The expression (_) creates a fresh, anonymous logic variable. You will also define a derived form that creates named logic variables:
<search-expr> ::= ... as before ...
              |   (=var (id ...) <search-expr>)

Finally, you will define forms to query the search trees that are constructed by <search-expr>s:

(=find-all (id ...) <search-expr>) 
=> (list (list ('id <value>) ...) ...)

; n is a non-negative integer
(=find-some n (id ...) <search-expr>) 
=> (list (list ('id <value-1>) ...) ... (list ('id <value-n>) ...))

Search Trees and Logic Variables

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.

However, you may represent search-trees (i.e. <search-expr>) and logic variables with any data structure you choose.

Conducting a Search and Printing Results

In principle, evaluating a <search-expr> will construct a search tree, but will not execute a search. To conduct a search, you must specify which logic variables you are interested in and how many results to return. To this end, you must implement the following forms:

Note that there is nothing special about the variables bound by =find-all and =find-some. They are simply the logic variables whose values the user is interested in.

Data Structures

Your implementation must be able to cope with flat values and lists. Flat values (numbers, symbols, strings, empty, ...) are straightforward; you will be able to directly bind logic variables to them and unify them with logic variables.

Composite data structures may require more effort, particularly when they contain logic variables. You are only required to support lists (and therefore, lists containing logic variables). To this end, you may define =cons to create a pair, along with any additional processing you need.

All other list processing functions should be trivial to define with =cons. For example, this definition of =list should work:

(define =list
  (lambda args
    (if (empty? args)
        empty
        (=cons (first args) (apply =list (rest args))))))
        
(test (=find-all (x y) (== (=list x 5) (=cons 6 (=cons y empty))))
      '([(x 6) (y 5)]))

Testing

Test your code using the standard testing forms. (test, test/exn, etc.) Since the representation of search trees is implementation-specific, your test cases will probably all use =find-all and =find-some. Keep in mind that these expressions have a specified output format and return results in a predictable order.

Interactive Testing

printf: the weapon of champions

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" (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 write test cases for this language that count the number for successes. For example:

(test (length
       (=find-all ()
                  (=and (=or =succeed =succeed =fail =succeed)
                        (=or =fail =succeed =succeed))))
      6)

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

Non-deterministic Finite Automata

The textbook defines an automaton macro that allows you to define deterministic finite automata. For example, the following automaton is supposed to accept lists of the form c(a|d)*r:

(define m (automaton init
            [init : (c -> more)
            [more : (a -> more)
                    (d -> more)
                    (r -> end)]
            [end :]))

Unfortunately, automaton as specified in the text has a bug. One characterization of the bug is that automaton doesn't distinguish accepting states from other states. Fix the bug by making accepting states explicit. The interface for automata with explicit accepting states should be:

(automaton
  start-state
  (accept accept-state ...)
  (state : (label -> target-state) ...)
  ...)

Alter your implementation so that you can define non-deterministic finite automata. Non-determinism allows you to repeat a label on the right-hand side of a state's transition table. For example:

(automaton
  init
  (accept end)
  (init : (c -> more))
  (more : (a -> more)
          (a -> end)
          (d -> more)
          (d -> end)
          (r -> end))

Your NFA implementation should use your Prolog implementation to achieve non-determinism.

Handin

Turn in one file, prolog.ss, containing your Prolog implementation, your NFA macro and your test suite.