CS 22
Clab 39: Nondeterministic Computing
Last clab we hinted that something called non-deterministic computing
could be nice.
Why Nondeterministic Computing Would Be Nice
We will soon look at a whole new way to do things. It's called
non-deterministic computing. It may or may not be magic. But
we can make a modified evaluator do it. Unfortunately, on ordinary
computers, raw non-deterministic computing is very inefficient.
But, if physicists can build modest size quantum computers, this will
be an efficient way to program.
Before we really dig into this though I want you to spend at least
a few minutes of
this clab on some exercises. It is my hope that you will agree that
these are not trivial in any of the ordinary imperative, functional,
or object-oriented styles of programming. We will see that
they are easy in a non-deterministic, declarative style of
programming.
- In your favorite language, write a function
that will take a list (or array) as an argument and return all the
permutations of that list (or array) either one at a time or in
another collection.
- In your favorite language, write a program to solve:
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?
- The eight queens problem ex2.42 on page 124-126. (you can get
this on the web by going to:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2.4
and backing up several screeen-fulls. (Here the hardest conceptual work
is done for you, but make sure you thoroughly understand it.)
Nondeterministic Computing
The basic idea of non-deterministic computing is really simple but it
depends on a new type of evaluator that will allow nondeterministic
selections and a way to request a different nondeterministic
selection. We can make a modified evaluator do it. Well the truth is
our amb evaluator will simulate it. As a programmer, we can assume we
have a machine that does it. Physicists have recently built a real
machine that really does it on 6 qubits. A qubit is a quantum
bit. There isn't too much you can do with only 6 bits but never
underestimate physicists. The fact that our selections really come in
a fixed order and that we can request a different selection is
where our simulator differs from true non-determinisim. If normal
size quantum computers can be built, they will be able to make all the
nondeterministic selections simultaneously.
We will look at the insides of our nondeterministic simulator
(called ambeval) next week. Here is a demo:
<![CDATA[
;;; Amb-Eval input:
(nond-perm '(a b c))
;;; Starting a new problem
;;; Amb-Eval value:
(a b c)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(a c b)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(b a c)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(b c a)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(c a b)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(c b a)
;;; Amb-Eval input:
try-again
;;; There are no more values of
(nond-perm '(a b c))
]]>
Here is the code that did it:
<![CDATA[
(define (nond-perm lis)
(let
((thisone (nondseln lis (length lis))))
(require
(distinct? thisone))
thisone))
]]>
The idea here is really simple. nondseln, require,
and distinct? are procedures
that satify the following descriptions.
<![CDATA[
;;; (nondseln ls n) returns a list of n (2nd parameter) elements
;;; selected nondeterministically from the list ls (1st parameter).
;;; The predicate p is evaluated. If p is false, another
;;; non-deterministic choice is made. If p is true
;;; (require p) has no effect.
;;; (distinct? items) assumes the parameter items is a list
;;; (distinct? items) returns true if all elements of items
;;; are different, otherwise (distinct? items) returns false
]]>
So, assuming lis contains k items, nond-perm works like this:
- nondeterministically select k items from lis and put
them in thisone (there may be repeats and some may not be
selected).
- the require clause forces the evaluator to keep trying
until the elements selected (and put in thisone) are all
distinct (which means it must be a permutation).
- Once a distinct list is found, return it.
The idea is really simple but it depends on a new type of evaluator
that will allow nondeterministic selections and a way to request a
different nondeterministic selection. As stated before, the fact that
our selections really come in a fixed order and that we can request a
different selection is where our simulator differs from true
non-determinisim.
Make a week13 subdirectory and copy mceval.scm and ambeval.scm
from /home/cfk/pub/cs22/week13 into your week13 directory.
We will look at the insides of our nondeterministic simulator
(called ambeval) next clab. Today we want to see what you can do
with it. ambeval is based on the special form amb. The
expression (amb e1 e2 e3 ... en) 'nondeterministically' evaluates
and returns the value of one of the expressions e1, e2, e3, ..., en.
So fire up ambeval.scm and try:
<![CDATA[
;; Amb-Eval input:
(amb 1 2 3)
;;; Starting a new problem
;;; Amb-Eval value:
1
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
2
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
3
;;; Amb-Eval input:
try-again
;;; There are no more values of
(amb 1 2 3)
]]>
Now we can define require, distinct, an-element-of:
<![CDATA[
(define (require p)
(if (not p) (amb)))
(define (an-element-of items)
(require (not (null? items)))
(amb (car items) (an-element-of (cdr items))))
;;; (distinct? items) assumes the parameter items is a list
;;; (distinct? items) returns true if all elements of items
;;; are different, otherwise (distinct? items) returns false
(define (distinct? items)
(cond ((null? items) true)
((null? (cdr items)) true)
((member (car items) (cdr items)) false)
(else (distinct? (cdr items)))))
]]>
Let's try these out a bit.
<![CDATA[
;;; Amb-Eval input:
(an-element-of '( a dog cat x Y))
;;; Starting a new problem
;;; Amb-Eval value:
a
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
dog
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
cat
;;; Amb-Eval input:
(let ((trylis (list 'dog (an-element-of '( a dog cat x Y)))))
(require (distinct? trylis))
trylis)
;;; Starting a new problem
;;; Amb-Eval value:
(dog a)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(dog cat)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(dog x)
]]>
Now we can define nondseln and nond-perm:
<![CDATA[
;;; (nondseln ls n) returns a list of n (2nd parameter) elements
;;; selected nondeterministically from the list ls (1st parameter).
(define (nondseln ls n)
(if (= n 0)
'()
(cons
(an-element-of ls)
(nondseln ls (- n 1)))))
(define (nond-perm lis)
(let
((thisone (nondseln lis (length lis))))
(require
(distinct? thisone))
thisone))
]]>
Let's try em.
<![CDATA[
;; Amb-Eval input:
(nondseln '(a b c d) 2)
;;; Starting a new problem
;;; Amb-Eval value:
(a a)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(a b)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(a c)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(a d)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(b a)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(b b)
]]>
You get the idea. So lets try nond-perm:
<![CDATA[
;;; Amb-Eval input:
(nond-perm '(a b cat))
;;; Starting a new problem
;;; Amb-Eval value:
(a b cat)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(a cat b)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(b a cat)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(b cat a)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(cat a b)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(cat b a)
;;; Amb-Eval input:
try-again
;;; There are no more values of
(nond-perm '(a b cat))
]]>
ambeval is based on the special form amb. The
expression (amb e1 e2 e3 ... en) 'nondeterministically' evaluates
and returns the value of one of the expressions e1, e2, e3, ..., en.
Once we have amb, we can define require, distinct, an-element-of.
Then nondseln and nond-perm are easy.
But non-deterministic computing can be a lot more fun than permutations.
We looked at the logic puzzle
on page 418
"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?"
Now run the following in ambeval.
<![CDATA[
(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)))
(require
(distinct? (list baker cooper fletcher miller smith)))
(require (not (= baker 5)))
(require (not (= cooper 1)))
(require (not (= fletcher 5)))
(require (not (= fletcher 1)))
(require (> miller cooper))
(require (not (= (abs (- smith fletcher)) 1)))
(require (not (= (abs (- fletcher cooper)) 1)))
(list (list 'baker baker)
(list 'cooper cooper)
(list 'fletcher fletcher)
(list 'miller miller)
(list 'smith smith))))
]]>
If you think of "(require p)" to be syntactic sugar for the
declarative sentence, "The solution will not be valid unless p.",
then the above is just a somewhat formalized declarative
restatement of what makes
a valid solution.
This is just a hint of what declarative programming is like.
The language Prolog is the best example of a declarative programming
language.
Most people regard the four major programming paradigms to be:
- imperative
- functional
- object-oriented
- declarative
In this course, we have emphasized functional (esp. chapter 1)
and object-oriented (especially chapter 3).
As one more example of nondeterminism, let's look at the queens problem.
Here is the old way of doing queens:
<![CDATA[
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (positions) (safe? k positions))
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(queen-cols board-size))
(define empty-board '())
(define enumerate-interval
(lambda (low high)
(if (> low high)
'()
(cons low (enumerate-interval (+ low 1) high)))))
(define in-check?
(lambda (q1 q2)
(or (= (queen-row q1) (queen-row q2))
(= (queen-column q1) (queen-column q2))
(= (abs (- (queen-row q1) (queen-row q2)))
(abs (- (queen-column q1) (queen-column q2)))))))
(define queen-row
(lambda (queen)
(car queen)))
(define queen-column
(lambda (queen)
(cadr queen)))
(define (adjoin-position new-row k rest-of-queens)
(cons (list new-row k) rest-of-queens))
(define (safe-help? q rest)
(if (null? rest) #t
(and (not (in-check? q (car rest))) (safe-help? q (cdr rest)))))
(define (safe? k positions)
(cond
((< k 2) #t)
(else (safe-help? (car positions) (cdr positions)))))
(define filter
(lambda (pred? l)
(cond
((null? l) '())
((pred? (car l)) (cons (car l) (filter pred? (cdr l))))
(else (filter pred? (cdr l))))))
(define flatmap
(lambda (proc l)
(if (null? l)
'()
(append (proc (car l)) (flatmap proc (cdr l))))))
;;-----------------------------------------------------------------
;; Printing procedures
(define print-board
(lambda (board)
(newline)
(print-divider)
(for-each
(lambda (row)
(display "|")
(for-each
(lambda (col)
(if (on-board? (make-queen row col) board)
(display " Q |")
(display " |")))
(enumerate-interval 1 board-size))
(newline)
(print-divider))
(enumerate-interval 1 board-size))
(newline)
'done))
(define print-divider
(lambda ()
(display "+")
(for-each
(lambda (col) (display "---+"))
(enumerate-interval 1 board-size))
(newline)))
(define on-board?
(lambda (queen board)
(and (not (empty-board? board))
(or (equal? queen (last-queen-on-board board))
(on-board? queen (other-queens board))))))
;;-----------------------------------------------------------------
;; Auxiliary procedures
(define other-queens
(lambda (board)
(cdr board)))
(define make-queen
(lambda (row column)
(list row column)))
(define empty-board?
(lambda (board)
(null? board)))
(define add-queen-to-board
(lambda (queen board)
(cons queen board)))
(define last-queen-on-board
(lambda (board)
(car board)))
(define b1 '((1 3) (4 2) (2 1)))
(define q4 '(3 4))
]]>
Half of that is just pretty printing stuff. We can test by:
<![CDATA[
Welcome to DrScheme, version 103p1.
Language: Graphical Full Scheme (MrEd) Custom.
> (queens 4)
(((3 4) (1 3) (4 2) (2 1)) ((2 4) (4 3) (1 2) (3 1)))
> (define board-size 4)
> (print-board '((3 4) (1 3) (4 2) (2 1)))
+---+---+---+---+
| | | Q | |
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | | Q |
+---+---+---+---+
| | Q | | |
+---+---+---+---+
done
> (print-board '((2 4) (4 3) (1 2) (3 1)))
+---+---+---+---+
| | Q | | |
+---+---+---+---+
| | | | Q |
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | Q | |
+---+---+---+---+
done
>
]]>
The heart of it is:
<![CDATA[
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (positions) (safe? k positions))
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(queen-cols board-size))
]]>
If we alter safe? and other helping programs to run
under amb.
<![CDATA[
(define (safe-help? q rest)
(if (null? rest) true
(if (not (in-check? q (car rest)))
(safe-help? q (cdr rest))
false)))
(define (safe? k positions)
(cond
((< k 2) true)
(else (safe-help? (car positions) (cdr positions)))))
(define in-check?
(lambda (q1 q2)
(cond
((= (queen-row q1) (queen-row q2)) true)
((= (queen-column q1) (queen-column q2)) true)
(else (= (abs (- (queen-row q1) (queen-row q2)))
(abs (- (queen-column q1) (queen-column q2))))))))
(define queen-row
(lambda (queen)
(car queen)))
(define queen-column
(lambda (queen)
(car (cdr queen))))
]]>
we can use non-determinism to generate safe configurations. Spend
the rest of this clab on this and exercise 4.38 on page 419.
Next week we will look at continuations and the amb-evaluator.
Remember no clab on Monday.