Day 4, Part 1

I've got to stop thinking that I must complete, polish and edit before posting to a blog. The reason I started one is so I could publish un-finished things before I forgot them.

On Thursday we covered something quite a bit more interesting in Gerry's lecture. First, though, I'm going to discuss the AMB operator in more detail. Here's a simple puzzle that is trivially solved via appropriate use of AMB

 
Baker, Cooper, Fletcher, Miller, and Smith live on different
floors of an apartment house that contains only five floors. Baker
does not live on the top floor. Cooper does not live on the bottom
floor. Fletcher does not live on either the top or the bottom
floor. Miller lives on a higher floor than does Cooper. Smith does not
live on a floor adjacent to Fletcher's. Fletcher does not live on a
floor adjacent to Cooper's. Where does everyone live?

(define (multiple-dwelling)
  (let ((baker  (amb 1 2 3 4 5))
        (cooper (amb 1 2 3 4 5))
        (fletcher  (amb 1 2 3 4 5))
        (miller (amb 1 2 3 4 5))
        (smith  (amb 1 2 3 4 5)))
    ;; They live on different floors.
    (require
      (distinct? (list baker cooper fletcher miller smith)))

    ;; Baker does not live on the top floor.
    (require (not (= baker 5)))

    ;; Cooper does not live on the bottom floor.
    (require (not (= cooper 1)))

    ;; Fletcher does not live on either the top 
    ;; or the bottom floor.
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))

    ;; Miller lives on a higher floor than does Cooper.
    (require (> miller cooper))

    ;; Smith does not live on a floor adjacent to Fletcher's. 
    (require (not (= (abs (- smith fletch)) 1)))

    ;; Fletcher does not live on a floor adjacent to Cooper's.
    (require (not (= (abs (- fletcher cooper)) 1)))

    (list (list 'baker baker)
          (list 'cooper cooper)
          (list 'fletcher fletcher)
          (list 'miller miller)
          (list 'smith smith))))

Even if this seems familiar to you, don't let your eyes glaze over, this is important.

There are a few ways to look at what the AMB operator does. The first is very abstract: AMB splits the interpreter into several copies, each copy attempts to proceed in parallel with one of the values, and if any interpreter computes an answer, we'll use it. This is the essence of non-deterministic programming: we try all the possibilities at the same time and arbitrarily pick a successful one.

Of course we don't implement the AMB operator that way. We certainly can't split a physical computer into several copies, and although we might be able to do that with virtual machines, the amount of memory and CPU usage would be way too high. Instead we look at the AMB operator in this way: AMB makes a snapshot of the state of the interpreter and then arbitrarily chooses one of the possible values to proceed with. If the computation doesn't fail, we can discard the snapshot, but if it does fail, we restore the snapshot and pick a different possible value. In this case, we are simulating non-deterministic programming by sequential iterative testing.

The simulation differs from the abstract model in a few important ways, some of these differences (and especially the consequences of these differences) are not obvious. The first obvious benefit is that by sequentially testing solutions, we limit our peak resource use. The tradeoff here is that we have to serially search through the solution space, so we have traded space for time. This is obvious because it is the tradeoff we desired. A less obvious benefit is this: if we don't use every solution to the problem, there is no need to exhaustively test every possibility. If we stop at the first solution, we are likely to use less time than if we try to enumerate all the solutions. So by testing sequentially we have traded space for *less* time. Another less obvious benefit is that instead of having just `solutions' and `failures', we can have a continuum of `great solutions', `good solutions', `poor solutions', `terrible solutions', etc. We can now dynamically decide how much time we wish to trade for a solution of sufficient quality. We may have to wait a long time to find the best solution, but we find an acceptable solution quite quickly.

These tradeoffs depend directly on how we decide to order the sequential testing. Refer to the multiple-dwelling problem. If AMB is implemented by sequential left-to-right trials, then we'll first try every combination that puts Baker on the first floor. Once we'e exhausted those, we try every combination that puts Baker on the second floor. Then we'll check the third, etc. It should be obvious that we can find a solution much faster if we can eliminate some of the problem constraints as quickly as possible. For example, we could trim the AMB forms to skip some combinations before we even run the program. Why does Fletcher have (amb 1 2 3 4 5) when we already know that possibility 1 and 5 cannot lead to a solution? Another thing we can do is re-order the AMB clauses and evaluate the require clauses sooner. We know that Fletcher cannot live next to Cooper, so we can check that reqirement before we even assign a floor to Miller and Smith and save ourselves a huge amount of time.

What's going on here? Our implementation of AMB has imposed an implicit order on the search through our possible solution space. By re-arranging the AMB clauses and testing the restrictions intelligently, we direct the code to search the more likely places in our solution space first and to avoid parts of our search space that we know don't contain valid solutions. We're pretty clever, eh?

Well, no, not really. Since we are the ones doing the re-ordering of clauses, the computer is making us do the hard work. Sure it is reasonably easy for this problem, but suppose the search space was for a good chess move. Should we examine queen moves first, or knight moves? What requirements should be checked and when? If we try a particular ordering, can we re-order the search?

In our implementation of AMB, every time we fail to meet a requirement, we backtrack to the most recent AMB and try the next option. This is called depth-first chronological backtracking. It naturally falls out of the implementation. We can change the implementation slightly. Rather than AMB making a snapshot of the world and proceeding along the first suggested path through the search space, we'll have AMB prepare a number of snapshots (one for each value) and place them in a queue. Then whenever we reach a failure point, we'll restart by popping a suggested search path off the queue. If you think about this a bit, you'll come to the conclusion that we can now direct the order in which we seach the solution space by defining a policy on how we use the queue. If we use the queue as a LIFO stack, then we get depth-first chronological backtracking. If we use the queue as a FIFO, we get breadth-first backtracking. So now we can change how we traverse the possible solution space without re-ordering the code.

We're now a bit more clever, but how do we know which order is best? We don't. We can only guess. On the other hand, the computer has more information than we have. If we annotate how the choices are made by amb we can make the backtracking smarter. We could, for example, assign a score to each potential path that is waiting in the queue and when we backtrack, select the highest scoring path. If we find that some path cannot satisfy a requirement, perhaps we can check the pending computations in the queue and simply remove the ones that would also follow the same path.

Now I'm going to abandon this line of though for a little while. I'll return to it.

Next post: propagator networks.