CS 22

Clab 42: The amb-evaluator and a Short Wrap-up

Last clab, we discussed how the amb evaluator can be implemented. It there is time, we will say a few more words about that today.

In clab39, I left you with several tasks, one of which was to use non-determinism to solve the 8-queens puzzle. Here is the old way of doing queens:

(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. And if we define rows to be a global list of eligible rows, we can use non-determinism to generate a possible configuration as follows: ;;; Amb-Eval input: ;;; Amb-Eval input: (define (ambqueens board-size) (let ((x (an-element-of rows)) (y (an-element-of rows))) (if (= board-size 1) (list (list x y)) (let ((sofar (cons (list x y) (ambqueens (- board-size 1))))) (require (safe? board-size sofar)) sofar)))) ;;; Starting a new problem ;;; Amb-Eval value: ok ;;; Amb-Eval input: (ambqueens 4) ;;; Starting a new problem ;;; Amb-Eval value: ((1 2) (2 4) (3 1) (4 3))

This is certainly simpler than the deterministic queens program. Here is a deterministic permutation generator.

;;; assumes lis is a list of sublists ;;; x is an element (define prependall (lambda (x lis) (if (null? lis) '() (cons (cons x (car lis)) (prependall x (cdr lis)))))) (define remove (lambda (x lis) (cond ((null? lis) '()) ((equal? x (car lis)) (cdr lis)) (else (cons (car lis) (remove x (cdr lis))))))) (define (perms lis) (define (xfstperms x ls) (let ((lst (remove x ls))) (if (null? lst) (list (list x)) (prependall x ( perms lst))))) (define (phelp fsttogo psofar) (cond ((null? fsttogo) psofar) (else (phelp (cdr fsttogo) (append (xfstperms (car fsttogo) lis) psofar))))) (phelp lis '())) This deterministic permutation generator works but it is not simple. In clab 39, we wrote a simple non-deterministic permutation generator: (define (nond-perm lis) (let ((thisone (nondseln lis (length lis)))) (require (distinct? thisone)) thisone)) Using non-deterministic selection and require, we have a conceptualy simple program. It may be inefficient but the machine is paying the price of the inefficiency. We noted that if quantum computers can be built, this will not be inefficient on a quantum computer.

We also saw that we could write 'programs' for solving certain kinds of logic puzzles that looked like little more than restating the problem in a scheme-like syntax.

"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?"

We defined and ran:

(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:

In this course, we have emphasized functional (esp. chapter 1) and object-oriented (especially chapter 3).

If there is time, we'll spend a few more minutes looking at the amb-evaluator.

Some SICP quotes that I like:

"Underlying our approach to this subject is our conviction that ``computer science'' is not a science and that its significance has little to do with computers. The computer revolution is a revolution in the way we think and in the way we express what we think. The essence of this change is the emergence of what might best be called procedural epistemology -- the study of the structure of knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects. Mathematics provides a framework for dealing precisely with notions of ``what is.'' Computation provides a framework for dealing precisely with notions of ``how to.'' "

"After a short time we forget about syntactic details of the language (because there are none) and get on with the real issues -- figuring out what we want to compute, how we will decompose problems into manageable parts, and how we will work on the parts. Another advantage of Lisp is that it supports (but does not enforce) more of the large-scale strategies for modular decomposition of programs than any other language we know. We can make procedural and data abstractions, we can use higher-order functions to capture common patterns of usage, we can model local state using assignment and data mutation, we can link parts of a program with streams and delayed evaluation, and we can easily implement embedded languages. "

"Our traffic with the subject matter of this book involves us with three foci of phenomena: the human mind, collections of computer programs, and the computer. Every computer program is a model, hatched in the mind, of a real or mental process. These processes, arising from human experience and thought, are huge in number, intricate in detail, and at any time only partially understood. They are modeled to our permanent satisfaction rarely by our computer programs. Thus even though our programs are carefully handcrafted discrete collections of symbols, mosaics of interlocking functions, they continually evolve: we change them as our perception of the model deepens, enlarges, generalizes until the model ultimately attains a metastable place within still another model with which we struggle. The source of the exhilaration associated with computer programming is the continual unfolding within the mind and on the computer of mechanisms expressed as programs and the explosion of perception they generate. If art interprets our dreams, the computer executes them in the guise of programs! "