Archive for September, 2010

Exercise 2.56

Working in top-down fashion we start by adding a rule for taking derivatives of exponentiation expressions to the deriv procedure:

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum (make-product (multiplier exp)
                                 (deriv (multiplicand exp) var))
                   (make-product (deriv (multiplier exp) var) 
                                 (multiplicand exp))))
        ((exponentiation? exp) ; Rule for handling exponentiation.
         (make-product (exponent exp)
                       (make-product (make-exponentiation (base exp)
                                                          (- (exponent exp) 1))
                                     (deriv (base exp) var))))
        (else (error "unknown expression type --DERIV" exp))))

Having done this we can choose a representation for the exponentiation expression data abstraction and implement the predicate exponentiation?, the constructor make-exponentiation, and the selectors base and exponent.

The exponentiation expression data abstraction is represented as a list whose first element is the symbol **, followed by the base and the exponent.

The rule that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself is “built” in the constructor make-exponentiation.

(define (make-exponentiation base exponent)
  (cond ((=number? exponent 0) 1)
        ((=number? exponent 1) base)
        (else (list '** base exponent))))

(define (exponentiation? exp)
  (and (pair? exp) (eq? (car exp) '**)))

(define (base e)
  (cadr e))

(define (exponent e)
  (caddr e))

Exercise 2.57

A sum of more than two terms can be represented as a list whose first element is the symbol + followed by the terms.

To implement this new representation we have to redefine the constructor make-sum and the selector augend. The new version of the selector evaluates to the third element of the list if the list contains three elements, or to the sum of all the elements after the second if the list contains more than three elements.

(define (make-sum . args)
  (if (>= (length args) 2)
      (cons '+ args)
      (error "A sum must have at least 2 arguments.")))

(define (augend s)
  (if (= (length s) 3)
      (caddr s)
      (cons '+ (cddr s))))

Products of more than two terms can be implemented in a similar way.

Only the definitions of the constructor make-product and the selector multiplicand have to be changed:

(define (make-product . args)
  (if (>= (length args) 2)
      (cons '* args)
      (error "A product must have at least 2 arguments.")))

(define (multiplicand p)
  (if (= (length p) 3)
      (caddr p)
      (cons '* (cddr p))))

Exercise 2.58

The case where the expressions are fully parenthesized and contain only the operations + and * which always take two arguments is trivial to handle.

Sums can be represented as lists of three elements, the second one of which is the symbol +, and the other two are the terms to be added. Sum?, addend, augend, and make-sum can be defined as follows:

(define (sum? s)
  (and (pair? s) (eq? (cadr s) '+)))

(define (addend s)
  (car s))

(define (augend s)
  (caddr s))

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list a1 '+ a2))))

Products are represented in a similar way:

(define (product? p)
  (and (pair? p) (eq? (cadr p) '*)))

(define (multiplier p)
  (car p))

(define (multiplicand p)
  (caddr p))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list m1 '* m2))))

However, If the expressions are not fully parenthesized, the problem becomes considerably more difficult.

Instead of designing a complete parser we can use the following observation: the “type” of an expression (sum or product) is determined by the last operation that is performed during its evaluation. For example the expression (x + y * z) is a sum since we first multiply y by z and than as a last operation add the result to x.

So, in order to determine the “type” of an expression, we can “scan” the expression list examining the top-level operation symbols it contains. If both + and * symbols are found we can safely say that the expression is a sum – the last operation to be performed will be an addition, since multipkication(s) takes precedence and will be performed earlier in the computation.

In case of multiple symbols + which addition will be performed last? Here we have several choices. If we assume that the leftmost addition is performed last than we are creating an right-associative system with regard to addition. If we assume that the rightmost addition is performed last than we are creating an left-associative system. In case of addition (and by the way multiplication) the choice we make is actually irrelevant, since this operation obeys the associativity law.

Having the above in mind we can say that an expression list is a sum if it contains the symbol + at the top level (not inside a nested list). This allows us to implement the predicate sum? as a recursive search:

(define (sum? exp)
  (cond ((null? exp) #f)
        ((not (pair? exp)) #f)
        ((eq? (car exp) '+) #t)
        (else (sum? (cdr exp)))))

Defining selectors becomes much cleaner if we define two helper procedures: lhs (left-hand-side), and rhs (right-hand-side) which take as arguments an expression and an operation symbol and return respectively the expression to the left of the first occurence of the symbol and the expression to the right of it:

(define (lhs exp op)
  (if (eq? (car exp) op) 
      (cons (car exp) (lhs (cdr exp) op))))

(define (rhs exp op)
  (if (eq? (car exp) op)
      (cdr exp)
      (rhs (cdr exp) op)))

The fact that these procedures stop at the first (leftmost) occurrence of the operation makes the system right-associative. For the purposes of the exercise this is adequate, since we are dealing only with addition and multiplication. But if we would like at some later stage to add other operations, including left-associative ones, a change in the definitions of lhs and rhs will be required.

The selectors addend and augend take respectively the expression to the left and to the right of the operator and remove the list wrapper if the corresponding list consists of only one element:

(define (addend s)
  (let ((left (lhs s '+)))
    (if (= (length left) 1)
        (car left)

(define (augend s)
  (let ((right (rhs s '+)))
    (if (= (length right) 1)
        (car right)

No change in the constructor make-sum is required – it can remain the same as in the fully parenthesized version.

The implementation of products is similar to that of sums.

An expression is a product if it contains a top-level symbol *, and furthermore it is not a sum.

When implementing the predicate product?, we can exploit the fact that in our definition of deriv we first check if the argument is a sum before applying product?. So we can assume that the argument of product? will never be a sum and an explicit check for that is not necessary. This makes the code more efficient but less maintainable.

(define (product? exp)
  (cond ((null? exp) #f)
        ((not (pair? exp)) #f)
        ((eq? (car exp) '*) #t)
        (else (product? (cdr exp)))))

The definitions of the selectors multiplier and multiplicand, and of the constructor make-product follow:

(define (multiplier p)
  (let ((left (lhs p '*)))
    (if (= (length left) 1)
        (car left)

(define (multiplicand p)
  (let ((right (rhs p '*)))
    (if (= (length right) 1)
        (car right)

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list m1 '* m2))))

Read Full Post »

Exercise 2.53

(list 'a 'b 'c)
=> (a b c)

(list (list 'george))
=> ((george))

(cdr '((x1 x2) (y1 y2)))
=> ((y1 y2))

(cadr '((x1 x2) (y1 y2)))
=> (y1 y2)

(pair? (car '(a short list)))
=> #f

(memq 'red '((red shoes) (blue socks)))
=> #f

(memq 'red '(red shoes blue socks))
=> (red shoes blue socks)

Exercise 2.54

My-equal? is implemented without the use of any conditional expressions. Instead it relies on or and and special forms:

(define (my-equal? a b)
  (or (and (symbol? a)
           (symbol? b)
           (eq? a b))
      (and (pair? a)
           (pair? b)
           (my-equal? (car a) (car b))
           (my-equal? (cdr a) (cdr b)))
      (and (null? a) (null? b))))

Exercise 2.55

The single quote symbol ‘ is “syntactic sugar” for a list whose first element is quote and whose second element is the quoted object. Quote is a special form, which when applied evaluates to the object that is being quoted. Having this in mind we can apply the substitution model:

(car ''abracadabra)               =>
(car (quote (quote abracadabra))) =>
(car (quote abracadabra))         =>

Read Full Post »

So, little progress was being made, but I think that whenever we say “computer science” or “software engineering,” and especially whenever we think we’re teaching it, the worst thing we could ever do is to pretend to the students that we know what it is, because the students are going to be the ones that are going to save us. So we should teach the students what I was taught when I was in graduate school in the ’60s, and that is: it isn’t done yet. It’s not even close to done. We have to understand what the actual scope of the computing is going to be, and you have to help us invent it

… people in general take great delight in complexity. It seems like… if you go to schools, it’s remarkable how much work they make the poor kids do, when if they taught the math better and differently, the kids would be doing much less work. But in fact, people delight in complexity and think that putting immense amounts of hard work in, even if there’s an easier way, is actually — there’s something morally good about it. And so I think for our field, one of the hardest things is the delight in complexity, … . I believe that most of this complexity is absolutely unnecessary, and I believe it can be proved that it’s unnecessary.

… the other thing I’ve noticed in talking with younger people and teaching a course, … and that is that it’s not so much that the juniors and seniors don’t know that much. They actually don’t know that much, for being close to graduating from college, but the thing that is distressing about them is that the things that they do know, they know very badly, because they know them in ways that are almost counterproductive for their thinking. So I think in a first course, you have a real chance to not just teach the one subject, but … you can actually touch on a lot of subjects. … I think math and science should always be taught together in the beginning. They came about that way. One is a language, one is a process. I think systems and computing should be taught together. I think the four of them should be taught together.

I think the same thing is true of computing. … right now, it’s thought of as, even by Stanford — with its mighty endowment — as basically vocational training for a job. It’s primarily thought of as teaching kids programming. It’s absolutely important to learn how to program, but computer science and software engineering are not the same as programming, any more than building Chartres cathedral is the same as bricklaying. You have to understand one to do the other, but they’re very different.

What we don’t want to imprint them on, for God’s sakes, is data structures and algorithms. That was a great idea in the ’50s, and we have to understand it and it’s still useful today for optimization and other sorts kinds of things, but it’s not the center of the field. It hasn’t been the center of the field for a long time, and what’s worse about it, it doesn’t scale. There’s very little systems aspect in the way the data structures and algorithms are taught. So I believe what we have to do is give the students a real taste of what the whole deal is, so they have to start thinking in systems ways, and thinking in mathematical ways, scientific ways, as we go along.

Alan Curtis Kay

“First Courses in Computing Should be Child’s Play”

Turing Award lecture, OOPSLA 2004



Read Full Post »

The section introduces the design of a simple picture drawing language. The primitives, the means of combination, and the means of abstraction, provided by the language, allow for experimentation with complex graphical patterns.

My basic implementation of the picture language system in PLT Racket can be downloaded from here.

A few examples of patterns generated using the language follow.

A “wave” (“George with smile”) painter beside of flipped-vertical copy of itself (himself):

Square-limit of a “wave” (“George with smile”) painter:

Square-limit of a cross painter squashed-inwards:

Next are the solutions to the exercises in the section.

Exercise 2.44

Definition of up-split procedure:

(define (up-split painter n)
  (if (= n 0)
      (let ((smaller (up-split painter (- n 1))))
        (below painter (beside smaller smaller)))))

Exercise 2.45

Split takes two procedures (operations) as arguments and returns a new custom procedure:

(define (split op1 op2)
  (define (splitter painter n)
    (if (= n 0)
        (let ((smaller (splitter painter (- n 1))))
          (op1 painter (op2 smaller smaller)))))

To achieve the same functionality in a language that does not support higher-order procedures (e.g. Java), a relatively complicated workaround (“design pattern”) is needed.

Exercise 2.46

Implementation of the vector data abstraction:

(define (make-vect x y)
  (cons x y))

(define (xcor-vect v)
  (car v))

(define (ycor-vect v)
  (cdr v))

Implementation of the procedures add-vect, sub-vect, and scale-vect in terms of the provided constructor and selectors:

(define (add-vect v1 v2)
  (make-vect (+ (xcor-vect v1)
                (xcor-vect v2))
             (+ (ycor-vect v1)
                (ycor-vect v2))))

(define (sub-vect v1 v2)
  (make-vect (- (xcor-vect v1)
                (xcor-vect v2))
             (- (ycor-vect v1)
                (ycor-vect v2))))

(define (scale-vect s v)
  (make-vect (* s (xcor-vect v))
             (* s (ycor-vect v))))

Exercise 2.47

Implementation of the frame data abstraction as a list:

(define (make-frame origin edge1 edge2)
  (list origin edge1 edge2))

(define (origin-frame frame)
  (car frame))

(define (edge1-frame frame)
  (cadr frame))

(define (edge2-frame frame)
  (caddr frame))

Alternative implementation of the frame data abstraction as two pairs:

(define (make-frame origin edge1 edge2)
  (cons origin (cons edge1 edge2)))

(define (origin-frame frame)
  (car frame))

(define (edge1-frame frame)
  (cadr frame))

(define (edge2-frame frame)
  (cddr frame))

Exercise 2.48

Representation of the segment data abstraction as a pair of vectors:

(define (make-segment start end)
  (cons start end))

(define (start-segment s)
  (car s))

(define (end-segment s)
  (cdr s))

Exercise 2.49

Definitions of the primitive painters outline, cross, diamond and wave:

(define outline
   (list (make-segment (make-vect 0.0 0.0) (make-vect 1.0 0.0))
         (make-segment (make-vect 1.0 0.0) (make-vect 1.0 1.0))
         (make-segment (make-vect 1.0 1.0) (make-vect 0.0 1.0))
         (make-segment (make-vect 0.0 1.0) (make-vect 0.0 0.0)))))

(define cross
   (list (make-segment (make-vect 0.0 0.0) (make-vect 1.0 1.0))
         (make-segment (make-vect 1.0 0.0) (make-vect 0.0 1.0)))))

(define diamond 
   (list (make-segment (make-vect 0.0 0.5) (make-vect 0.5 0.0))
         (make-segment (make-vect 0.5 0.0) (make-vect 1.0 0.5))
         (make-segment (make-vect 1.0 0.5) (make-vect 0.5 1.0))
         (make-segment (make-vect 0.5 1.0) (make-vect 0.0 0.5)))))

(define wave 
   (list (make-segment (make-vect 0.25 0.00) (make-vect 0.37 0.37)) ;1
         (make-segment (make-vect 0.40 0.00) (make-vect 0.50 0.25)) ;2
         (make-segment (make-vect 0.50 0.25) (make-vect 0.62 0.00)) ;3
         (make-segment (make-vect 0.75 0.00) (make-vect 0.70 0.50)) ;4
         (make-segment (make-vect 0.70 0.50) (make-vect 1.00 0.30)) ;5
         (make-segment (make-vect 1.00 0.50) (make-vect 0.75 0.62)) ;6
         (make-segment (make-vect 0.75 0.62) (make-vect 0.62 0.62)) ;7
         (make-segment (make-vect 0.62 0.62) (make-vect 0.75 0.75)) ;8
         (make-segment (make-vect 0.75 0.75) (make-vect 0.62 1.00)) ;9
         (make-segment (make-vect 0.40 1.00) (make-vect 0.30 0.75)) ;10
         (make-segment (make-vect 0.30 0.75) (make-vect 0.40 0.62)) ;11
         (make-segment (make-vect 0.40 0.62) (make-vect 0.25 0.62)) ;12
         (make-segment (make-vect 0.25 0.62) (make-vect 0.20 0.50)) ;13
         (make-segment (make-vect 0.20 0.50) (make-vect 0.00 0.70)) ;14
         (make-segment (make-vect 0.37 0.37) (make-vect 0.30 0.50)) ;15
         (make-segment (make-vect 0.30 0.50) (make-vect 0.12 0.37)) ;16
         (make-segment (make-vect 0.12 0.37) (make-vect 0.00 0.50)) ;17

Exercise 2.50

Definitions of flip-horiz, rotate180, and rotate270:

(define (flip-horiz painter)
   (make-vect 1.0 0.0)
   (make-vect 0.0 0.0)
   (make-vect 1.0 1.0)))

(define (rotate180 painter)
  (transform-painter painter
                     (make-vect 1.0 1.0)
                     (make-vect 0.0 1.0)
                     (make-vect 1.0 0.0)))

(define (rotate270 painter)
  (transform-painter painter
                     (make-vect 0.0 1.0)
                     (make-vect 0.0 0.0)
                     (make-vect 1.0 1.0)))

Exercise 2.51

Definition of below operation analogous to the beside procedure:

(define (below painter1 painter2)
  (let ((paint-bottom 
         (transform-painter painter1
                            (make-vect 0.0 0.0)
                            (make-vect 1.0 0.0)
                            (make-vect 0.0 0.5)))
         (transform-painter painter2
                            (make-vect 0.0 0.5)
                            (make-vect 1.0 0.5)
                            (make-vect 0.0 1.0))))
    (lambda (frame)
      (paint-bottom frame)
      (paint-top frame)))

Definition of below in terms of beside, rotate90 and rotate270:

(define (below painter1 painter2)
  (rotate90 (beside (rotate270 painter1)
                    (rotate270 painter2))))

Exercise 2.52

A change made at the level of the primitive painter – a few segments are added to the wave painter:

(define wave 
   (list (make-segment (make-vect 0.25 0.00) (make-vect 0.37 0.37)) ;1
         (make-segment (make-vect 0.40 0.00) (make-vect 0.50 0.25)) ;2
         (make-segment (make-vect 0.50 0.25) (make-vect 0.62 0.00)) ;3
         (make-segment (make-vect 0.75 0.00) (make-vect 0.70 0.50)) ;4
         (make-segment (make-vect 0.70 0.50) (make-vect 1.00 0.30)) ;5
         (make-segment (make-vect 1.00 0.50) (make-vect 0.75 0.62)) ;6
         (make-segment (make-vect 0.75 0.62) (make-vect 0.62 0.62)) ;7
         (make-segment (make-vect 0.62 0.62) (make-vect 0.75 0.75)) ;8
         (make-segment (make-vect 0.75 0.75) (make-vect 0.62 1.00)) ;9
         (make-segment (make-vect 0.40 1.00) (make-vect 0.30 0.75)) ;10
         (make-segment (make-vect 0.30 0.75) (make-vect 0.40 0.62)) ;11
         (make-segment (make-vect 0.40 0.62) (make-vect 0.25 0.62)) ;12
         (make-segment (make-vect 0.25 0.62) (make-vect 0.20 0.50)) ;13
         (make-segment (make-vect 0.20 0.50) (make-vect 0.00 0.70)) ;14
         (make-segment (make-vect 0.37 0.37) (make-vect 0.30 0.50)) ;15
         (make-segment (make-vect 0.30 0.50) (make-vect 0.12 0.37)) ;16
         (make-segment (make-vect 0.12 0.37) (make-vect 0.00 0.50)) ;17
         (make-segment (make-vect 0.50 0.70) (make-vect 0.35 0.75)) ;smile 1
         (make-segment (make-vect 0.50 0.70) (make-vect 0.65 0.75)) ;smile 2

A change to corner-split is made at a higher level of abstraction:

(define (corner-split painter n)
  (if (= n 0)
      (let ((up (up-split painter (- n 1)))
            (right (right-split painter (- n 1)))
            (corner (corner-split painter (- n 1))))
          (beside (below painter up)
                  (below right corner)))))

A change to square-limit that makes painters, such as Mr. Rogers, appear to be looking outwards is done at even higher level of abstraction:

(define (square-limit painter n)
  (let ((combine4 (square-of-four flip-horiz identity rotate180 flip-vert)))
    (combine4 (corner-split (flip-horiz painter) n))))

Read Full Post »

Exercise 2.33

Definitions of the basic list-manipulation operations map, append, and length as accumulations:

(define (my-map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) '() sequence))

(define (my-append seq1 seq2)
  (accumulate cons seq2 seq1))

(define (my-length sequence)
  (accumulate (lambda (x y) (+ 1 y)) 0 sequence))

Exercise 2.34

Definition of horner-eval:

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms)
                (+ this-coeff (* x higher-terms)))

(horner-eval 2 '(1 3 0 5 0 1))
=> 79

Horner’s algorithm is worth remembering. Due to its simplicity and efficiency it finds numerous applications in computing. Horner’s algorithm is used in extracting the numeric values from string representations of integers in different positional numeral systems, in computing various hash functions, in finding roots of polynomials in conjunction with Newton-Raphson method, etc.

Exercise 2.35

Definition of count-leaves as an accumulation – the enumerate-tree procedure is used as a building block in the signal-flow structure:

(define (enumerate-tree tree)
  (cond ((null? tree) '())
        ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))

(define (count-leaves tree)
  (accumulate +
              (map (lambda (x) 1)
                   (enumerate-tree tree))))

Exercise 2.36

Definition of accumulate-n procedure:

(define (accumulate-n op initial seqs)
  (if (null? (car seqs))
      (cons (accumulate op initial (map car seqs))
            (accumulate-n op initial (map cdr seqs)))))

Exercise 2.37

Definitions of dot-product, matrix-*-vector, transpose, and matrix-*-matrix procedures:

(define (dot-product v w)
  (accumulate + 0 (map * v w)))

(define (matrix-*-vector m v)
  (map (lambda (row)
         (dot-product row v))

(define (transpose m)
  (accumulate-n cons

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (row)
           (matrix-*-vector cols row))

It is amazing how sequence operations let us smoothly stick together procedures, achieving more and more complex functionality.

This reminds me of LEGO toys, that allow us to construct a practically infinite variety of cool stuff just by combining a few types of simple building blocks.

Exercise 2.38

To understand under what conditions fold-left is equivalent to fold-right let’s consider the differences between the two.

Fold-right applies the operation op from right to left, whereas fold-leftt applies it from left to right. What this means is that everything else being the same the operation op must be insensitive to the order of its application. In mathematics such an operation is called associative. Therefore op must obey the associative law: (a op b) op c = a op (b op c).

Another difference between fold-left and fold-right is the “positioning” of initial with respect to sequence. In the case of fold-left initial is “placed” to the left of sequence, and in the case of fold-right – to the right. This implies that op has to be also insensitive to the order of its arguments. Such an operation is called commutative. So op must also obey the commutative law: a op b = b op a.

In the given example neither the operation “/” nor the operation “list” is simultaneously associative and commutative:

(fold-right / 1 '(1 2 3))
=> 3/2

(fold-left / 1 '(1 2 3))
=> 1/6

(fold-right list '() '(1 2 3))
=> (1 (2 (3 ())))

(fold-left list '() '(1 2 3))
=> (((() 1) 2) 3)

Exercise 2.39

Definitions of reverse in terms of fold-right and fold-left:

(define (reverse-1 sequence)
  (fold-right (lambda (x y) (append y (list x)))

(define (reverse-2 sequence)
  (fold-left (lambda (x y) (cons y x))

Exercise 2.40

Definitions of unique-pairs and prime-sum-pairs in terms of unique-pairs:

(define (unique-pairs n)
  (flatmap (lambda (i)
             (map (lambda (j) (list i j))
                  (enumerate-interval 1 (- i 1))))
           (enumerate-interval 1 n)))

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum?
               (unique-pairs n))))

Abstracting away the generation of pairs into a separate procedure simplifies the definition of prime-sum-pairs.

Exercise 2.41

The definition of triple-sum in terms of a filter and a cascade of nested maps, flatmaps, and enumerate-intervals again bears a striking resemblance to the compositional power of LEGO blocks:

(define (triple-sum n s)
  (filter (lambda (t) 
            (= s (+ (car t) 
                    (cadr t)
                    (caddr t))))
          (flatmap (lambda (i)
                     (flatmap (lambda (j)
                                (map (lambda (k)
                                       (list i j k))
                                     (enumerate-interval 1 (- j 1))))
                              (enumerate-interval 1 (- i 1))))
                   (enumerate-interval 1 n))))

Exercise 2.42

I have chosen to represent sets of board positions as lists of queens. A queen is an abstract data type defined by its constructor (make-queen row col) and the selectors (row queen) and (col queen). Queens themselves are represented as lists of two elements – row and col, which correspond to the row and the column of the square the piece occupies:

;; Queen data-type constructor and selectors.
(define (make-queen row col)
  (list row col))

(define (row queen)
  (car queen))

(define (col queen)
  (cadr queen))

;; A board position is represented as a list of queens.
(define empty-board '())

(define (adjoin-position row col rest-of-queens)
  (cons (make-queen row col) rest-of-queens))

Once these definitions are in place the predicate safe? can be implemented. It is defined using a helper procedure attacks? that given two queens as arguments determines do they attack each other. Attacks? itself relies on the helper predicates same-row?, same-col?, and same-diagonal? that focus on the different ways in which queens may attack each other. The most interesting one of them is same-diagonal?. It uses the fact that for all squares located on the same diagonal either row + col or row – col is a constant.

;; Helper functions.
(define (same-queens? q1 q2)
  (and (= (row q1) (row q2))
       (= (col q1) (col q2))))

(define (same-row? q1 q2)
  (= (row q1) (row q2)))

(define (same-col? q1 q2)
  (= (col q1) (col q2)))

(define (same-diagonal? q1 q2)
  (or (= (+ (row q1) (col q1))
         (+ (row q2) (col q2)))
      (= (- (row q1) (col q1))
         (- (row q2) (col q2)))))

(define (attacks? q1 q2)
  (and (not (same-queens? q1 q2))
       (or (same-row? q1 q2)
           (same-col? q1 q2)
           (same-diagonal? q1 q2))))

;; Checks if the queen at column k is safe. The queen is safe 
;; if the set of all queens that attack it is the empty set.
(define (safe? k queens)
  (let ((new-queen (car (filter (lambda (q) (= k (col q))) queens))))
    (null? (filter (lambda (q) (attacks? q new-queen)) queens))))

Exercise 2.43

Let’s consider the algorithm for generating solutions to the queens puzzle more carefully. It dictates that to generate all valid placements for the first k queens in the first k columns of a n X n chessboard, recursively generate all valid placements for k – 1 queens in the first k – 1 columns. For each such placement try augmenting it with a queen in the k-th column in all possible ways and keep all valid resulting placements.

The implementation of this algorithm is given as part of the specification of the problem in the previous exercise.

However Mr. Reasoner has done something different. First he places a queen in the k-th column in all possible ways. Then for each such placement he recursively generates all the solutions for the first k – 1 columns, appends the current queen to each of these and keeps all valid resulting arrangements. The flaw of this implementation is that instead of only one recursive call for each column Mr. Reasoner’s code performs as many calls as there are ways to put a queen in a column – n. This would not be a problem if Mr. Reasoner was using memoization, but he is not.

In analyzing the first algorithm we see that it makes a total of n recursive calls – one for each column to solve the n – queens problem on an n x n chessboard.

Mr. Reasoner’s algorithm, however, makes n recursive calls for each column. Each such call itself results in new n recursive calls, and each of these spawns another n recursive calls and so on until they bottom out at the 0-th column. This generates a tree of recursive calls of depth n with each non-leaf node having n children. Summing up all the nodes at each level we get:

n^0 + n^1 + n^2 + \ldots + n^{n - 1}

This makes a total of nn – 1 recursive calls.

Let’s assume that the “work” done at each recursive node is the same for both algorithms. Then the “work” done by the “right” algorithm for an 8 x 8 board will be 8 units. The “work” done by Mr. Reasoner’s algorithm will be 88 units. This means that if the “right” algorithm solves the puzzle in time T, Mr. Reasoner’s code will solve it in approximately T8 time.

Read Full Post »

Older Posts »