Bill the Lizard

SICP 2.66: Sets and information retrieval

2013-04-30T22:07:00.000-04:00

From SICP section 2.3.3 Sets and information retrieval

The final part of section 2.3.3 asks us to consider a database that contains records, each of which has a key and some data. If the database is represented as an unordered list, a record can be looked up by its key using the following procedure.

(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) false)
        ((equal? given-key (key (car set-of-records)))
         (car set-of-records))
        (else (lookup given-key (cdr set-of-records)))))

We can define simple procedures for making a record out of a key and its data, and for extracting the key and data from an existing record in order to test the procedure above.

(define (key record) (car record))
(define (data record) (cdr record))
(define (make-record key data) (cons key data))

(define database
  (list (make-record 1 'Bill)
        (make-record 2 'Joe)
        (make-record 3 'Frank)
        (make-record 4 'John)))
  
> (lookup 3 database)
'(3 . Frank)
> (data (lookup 1 database))
'Bill

Exercise 2.66 asks us to implement the lookup procedure for the case where the set of records is structured as a binary tree, ordered by the numerical values of the keys.

We can start by including the list->tree and partial-tree procedures given for exercise 2.64, along with a few required supporting procedures.

(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
  (list entry left right))
  
(define (list->tree elements)
  (car (partial-tree elements (length elements))))

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
        (let ((left-result (partial-tree elts left-size)))
          (let ((left-tree (car left-result))
                (non-left-elts (cdr left-result))
                (right-size (- n (+ left-size 1))))
            (let ((this-entry (car non-left-elts))
                  (right-result (partial-tree (cdr non-left-elts)
                                              right-size)))
              (let ((right-tree (car right-result))
                    (remaining-elts (cdr right-result)))
                (cons (make-tree this-entry left-tree right-tree)
                      remaining-elts))))))))

This makes it easier to convert the existing database to one structured as a binary tree.

> (define tree-db (list->tree database))
> tree-db
'((2 . Joe) ((1 . Bill) () ()) ((3 . Frank) () ((4 . John) () ())))

Finally, we can write the new implementation of lookup using element-of-set? as a guide.

(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) #f)
        ((= given-key (key (car set-of-records)))
         (car set-of-records))
        ((< given-key (key (car set-of-records)))
         (lookup given-key (left-branch set-of-records)))
        ((> given-key (key (car set-of-records)))
         (lookup given-key (right-branch set-of-records)))))

> (lookup 3 tree-db)
'(3 . Frank)
> (lookup 1 tree-db)
'(1 . Bill)
> (lookup 5 tree-db)
#f
> (data (lookup 2 tree-db))
'Joe

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.63 - 2.65: Sets as binary trees

2013-03-24T16:29:00.000-04:00

From SICP section 2.3.3 Example: Representing Sets

So far in this section we've looked at two ways of representing sets. First as unordered lists, then as ordered lists. Now we'll look at how we can represent sets as binary trees, and we'll see what advantages this representation has over ordered lists.

Each node of a tree holds one element of the set, called the "entry" at that node, and a link to each of two other (possibly empty) nodes. The "left" link points to elements smaller than the one at the node, and the "right" link to elements greater than the one at the node. The same set may be represented by a number of different trees. The only requirements for a valid representation is that all elements in the left subtree must be smaller than the node entry and all elements in the right subtree be must be larger than the node entry. Figure 2.16 in the text shows several valid tree representations of the same set of values.

Recall that for an ordered set of n elements, we had to search through (on average) n/2 elements to locate a particular value. We do this by searching through the elements in order. The advantage of a tree representation is that we can cut this effort down to log n if the tree is balanced.

Exercise 2.63 asks us if the following two procedures produce the same results for every tree, and if not how they differ.

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append (tree->list-1 (left-branch tree))
              (cons (entry tree)
                    (tree->list-1 (right-branch tree))))))
     
(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list (left-branch tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch tree)
                                          result-list)))))
  (copy-to-list tree '()))

The tree->list-1 procedure checks to see if the tree passed in is null, and if so returns an empty list. If the tree is not null, it creates a list by appending the left branch of the tree, the element at the root node, and the right branch of the tree. Elements of the left and right branches are flattened into lists using recursive calls to tree->list-1. The tree->list-2 procedure defines a helper function copy-to-list that takes the tree and a result-list as arguments. When the tree is null, it returns the result-list that was passed in. The copy-to-list helper function also uses recursive calls to the left and right branches of the tree while building the final result list. These two procedures will produce the same results for every tree.

We're asked to test the two procedures on the trees in figure 2.16.

(define tree1 '(7 (3 (1 () ()) (5 () ())) (9 () (11 () ()))))
(define tree2 '(3 (1 () ()) (7 (5 () ()) (9 () (11 () ())))))
(define tree3 '(5 (3 (1 () ()) ()) (9 (7 () ()) (11 () ()))))

> (tree->list-1 tree1)
'(1 3 5 7 9 11)
> (tree->list-2 tree1)
'(1 3 5 7 9 11)
> (tree->list-1 tree2)
'(1 3 5 7 9 11)
> (tree->list-2 tree2)
'(1 3 5 7 9 11)
> (tree->list-1 tree3)
'(1 3 5 7 9 11)
> (tree->list-2 tree3)
'(1 3 5 7 9 11)

We can see from these results that both procedures return an in-order traversal for every tree.

We're also asked if the two procedures have the same order of growth for a balanced tree, and if not, which one grows more slowly?

We can see from the results above and from inspecting the two procedures that each node of the tree is visited one time by each algorithm. What happens at each of those n steps is subtly different though. The second procedure simply calls cons at each step, which we'll assume is a constant-time operation, so the tree->list-2 procedure has a time complexity of $O(n)$. The first procedure calls append at each step, which we saw in section 2.2.1 has the following definition:

(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

From this definition we can see that the order of growth of append is proportional to the first list argument that's passed in. In the case of tree->list-1, the first list argument is the left branch of the tree, which is about half of a node's elements for a balanced tree. This means that for each recursive call, approximately half of the number of nodes will be in the first list argument as in the previous call. Since the number of elements is cut in half on each of the n calls to append, the tree->list-1 procedure has a complexity of $O(n log n)$ for a balanced tree.

Exercise 2.64 introduces the list->tree procedure, which converts an ordered list to a balanced binary tree using the helper procedure partial-tree that takes as arguments an integer n and list of at least n elements and constructs a balanced tree containing the first n elements of the list.

(define (list->tree elements)
  (car (partial-tree elements (length elements))))

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
        (let ((left-result (partial-tree elts left-size)))
          (let ((left-tree (car left-result))
                (non-left-elts (cdr left-result))
                (right-size (- n (+ left-size 1))))
            (let ((this-entry (car non-left-elts))
                  (right-result (partial-tree (cdr non-left-elts)
                                              right-size)))
              (let ((right-tree (car right-result))
                    (remaining-elts (cdr right-result)))
                (cons (make-tree this-entry left-tree right-tree)
                      remaining-elts))))))))

First we're asked to explain how partial-tree works, then draw the tree produced by list->tree for the list (1 3 5 7 9 11).

The partial-tree procedure works by dividing the list into three parts, a center element (the root node of the tree), everything before the center element, and everything after the center element. All the elements before the center element are then passed to a recursive call to partial-tree to create the left branch of the tree, and all the elements after the center element are passed recursively to partial-tree to create the right branch. These recursive call continue until no elements are remaining, and the balanced binary tree is assembled.

The tree produced by list->tree for the list (1 3 5 7 9 11) is:

To verify this, we can simply call the procedure.

> (list->tree '(1 3 5 7 9 11))
'(5 (1 () (3 () ())) (9 (7 () ()) (11 () ())))

Next we're asked what is the order of growth in the number of steps required by list->tree to convert a list of n elements? The procedure only needs to visit each element of the list once, and it only performs a cons for each element it visits, so the number of steps is proportional to the size of the list, or $O(n)$.

Exercise 2.65 asks us to use the results of the previous two exercises to give $O(n)$ implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.

We implemented union-set for the unordered list representation of sets back in exercise 2.59. This implementation had to check all elements of one set for each element of the other, so it's complexity was $O(n^2)$, quite poor. We improved on this in exercise 2.62 when we wrote an implementation of union-set for the ordered list representation of sets, which was $O(n)$. The text supplied a similar implementation of intersection-set that was also $O(n)$. We could use these ordered set implementations as a guide to writing efficient implementations of union-set and intersection-set for balanced binary trees, but that wouldn't require the results of the previous two exercises. Instead, we can use the $O(n)$ implementations of all of the procedures we've built so far to perform the following steps:

Convert the balanced binary trees to ordered lists.
Perform the desired operation (union-set or intersection-set).
Convert the resulting ordered set back to a balanced binary tree.

(define (union-set tree1 tree2)
  (define (union-list set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          ((= (car set1) (car set2))
           (cons (car set1) (union-list (cdr set1) (cdr set2))))
          ((< (car set1) (car set2))
           (cons (car set1) (union-list (cdr set1) set2)))
          (else (cons (car set2) (union-list set1 (cdr set2))))))
  (list->tree (union-list (tree->list-2 tree1)
                          (tree->list-2 tree2))))

(define (intersection-set tree1 tree2)
  (define (intersection-list set1 set2)
    (if (or (null? set1) (null? set2))
        '()    
        (let ((x1 (car set1)) (x2 (car set2)))
          (cond ((= x1 x2)
                 (cons x1
                       (intersection-list (cdr set1)
                                          (cdr set2))))
                ((< x1 x2)
                 (intersection-list (cdr set1) set2))
                ((< x2 x1)
                 (intersection-list set1 (cdr set2)))))))
  (list->tree (intersection-list (tree->list-2 tree1)
                                 (tree->list-2 tree2))))

In the implementations above, I've just defined the earlier ordered set implementations of union-set and intersection-set as helper functions named union-list and intersection-list. With these helper functions, all union-set and intersection-set need to do is convert from tree to list and back from list to tree. We can define a few balanced trees to test that these new implementations work as expected.

> (define evens (list->tree '(0 2 4 6 8 10)))
> (define odds (list->tree '(1 3 5 7 9)))
> (define primes (list->tree '(2 3 5 7 11 13 17 19)))
>
> evens
'(4 (0 () (2 () ())) (8 (6 () ()) (10 () ())))
> odds
'(5 (1 () (3 () ())) (7 () (9 () ())))
> primes
'(7 (3 (2 () ()) (5 () ())) (13 (11 () ()) (17 () (19 () ()))))
>
> (union-set odds evens)
'(5
  (2 (0 () (1 () ())) (3 () (4 () ())))
  (8 (6 () (7 () ())) (9 () (10 () ()))))
> (union-set odds odds)
'(5 (1 () (3 () ())) (7 () (9 () ())))
> (intersection-set evens primes)
'(2 () ())
> (intersection-set odds primes)
'(5 (3 () ()) (7 () ()))
> (intersection-set odds evens)
'()

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

12 (Really) Controversial Programming Opinions

2012-09-01T22:58:00.005-04:00

A few days ago, Yannis Rizos posted 20 controversial programming opinions on the Programmers Community Blog. Judging by the comments on the blog, and on reddit and Hacker News, none of these opinions are considered all that controversial by the programming community at large. The problem stems from the fact that the opinions posted were selected from among the top-voted answers to Jon Skeet’s question What’s your most controversial programming opinion?, originally asked on Stack Overflow on January 2, 2009. People seem to have voted for answers they strongly agreed with, making those top answers some of the least controversial opinions you could gather.

I decided to take a different approach. What follows are some of the opinions that I found near the middle or at the end of the list. I tried to pick only answers where the author made an attempt at supporting their opinion, but as you can see some of these opinions were downvoted more heavily than they were upvoted by the Stack Overflow community. (I'll add that my own "controversial" opinion is that Jon's question is perhaps the best argument we have that these types of opinion polls simply do not work on Stack Overflow.)

1. Two lines of code is too many. (+20/-32) by Jay Bazuzi

If a method has a second line of code, it is a code smell. Refactor.

2. If it's not native, it's not really programming (+5/-15) by Mason Wheeler

By definition, a program is an entity that is run by the computer. It talks directly to the CPU and the OS. Code that does not talk directly to the CPU and the OS, but is instead run by some other program that does talk directly to the CPU and the OS, is not a program; it's a script. Read more

3. The "While" construct should be removed from all programming languages. (+6/-14) by seanyboy

You can easily replicate While using "Repeat" and a boolean flag, and I just don't believe that it's useful to have the two structures. In fact, I think that having both "Repeat...Until" and "While..EndWhile" in a language confuses new programmers. Read more

4. Copy/Pasting is not an antipattern, it fact it helps with not making more bugs (+4/-5) by serg

My rule of thumb - typing only something that cannot be copy/pasted. If creating similar method, class, or file - copy existing one and change what's needed. (I am not talking about duplicating a code that should have been put into a single method). Read more

5. Developing on .NET is not programming. Its just stitching together other people's code. (+7/-5) by Gerard

Having come from a coding background where you were required to know the hardware, and where this is still a vital requirements in my industry, I view high level languages as simply assembling someone else's work. Nothing essentially wrong with this, but is it 'programming'? Read more

6. The use of try/catch exception handling is worse than the use of simple return codes and associated common messaging structures to ferry useful error messages. (+11/-3) by Einstein

Littering code with try/catch blocks is not a solution.

Just passing exceptions up the stack hoping whats above you will do the right thing or generate an informative error is not a solution. Read more

7. Test Constantly (+15/-7) by PJ Davis

You have to write tests, and you have to write them FIRST. Writing tests changes the way you write your code. It makes you think about what you want it to actually do before you just jump in and write something that does everything except what you want it to do. Read more

8. Object Oriented Programming is absolutely the worst thing that's ever happened to the field of software engineering. (+34/-14) by Breton

The primary problem with OOP is the total lack of a rigorous definition that everyone can agree on. This easily leads to implementations that have logical holes in them, or language like Java that adhere to this bizarre religious dogma about what OOP means, while forcing the programmer into doing all these contortions and "design patterns" just to work around the limitations of a particular OOP system. Read more

9. C (or C++) should be the first programming language (+24/-5) by hansen j

The first language should NOT be the easy one, it should be one that sets up the student's mind and prepare it for serious computer science.
C is perfect for that, it forces students to think about memory and all the low level stuff, and at the same time they can learn how to structure their code (it has functions!)

C++ has the added advantage that it really sucks :) thus the students will understand why people had to come up with Java and C#.

10. Classes should fit on the screen. (+22/-7) by Jay Bazuzi

If you have to use the scroll bar to see all of your class, your class is too big.

Code folding and miniature fonts are cheating.

11. Making invisible characters syntactically significant in python was a bad idea (+43/-5) by Paul Wicks

It's distracting, causes lots of subtle bugs for novices and, in my opinion, wasn't really needed. About the only code I've ever seen that didn't voluntarily follow some sort of decent formatting guide was from first-year CS students. And even if code doesn't follow "nice" standards, there are plenty of tools out there to coerce it into a more pleasing shape.

12. Singletons are not evil (+42/-7) by Steve

There is a place for singletons in the real world, and methods to get around them (i.e. monostate pattern) are simply singletons in disguise. For instance, a Logger is a perfect candidate for a singleton. Additionally, so is a message pump. My current app uses distributed computing, and different objects need to be able to send appropriate messages. There should only be one message pump, and everyone should be able to access it. The alternative is passing an object to my message pump everywhere it might be needed and hoping that a new developer doesn't new one up without thinking and wonder why his messages are going nowhere. The uniqueness of the singleton is the most important part, not its availability. The singleton has its place in the world.

SICP 2.61 - 2.62: Sets as ordered lists

2012-07-01T19:16:00.000-04:00

From SICP section 2.3.3 Example: Representing Sets

In exercises 2.59 and 2.60 we looked at how to represent sets as unordered lists. In the next two we'll look at representing sets as ordered lists, and at what benefits we get from the new implementation.

First, if elements in a set are guaranteed to be in order, we can improve the performance of element-of-set by returning false as soon as we encounter an element of the set that's less than the value that we're looking for. All of the remaining elements are guaranteed to be smaller as well. This saves us on average half the number of comparisons from the previous implementation.

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (car set)) true)
        ((< x (car set)) false)
        (else (element-of-set? x (cdr set)))))

We get a more impressive improvement from intersection-set. In the old implementation using unordered lists we had to compare every element of each set to every element in the other set. This had a complexity of $O(n^2)$. With the elements of both sets in order we can reduce that all the way down to $O(n)$. This is possible due to the fact that if the car of one ordered set is smaller than the car of another ordered set, it has to be smaller than all the other elements and we can discard it right away.

(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
      '()    
      (let ((x1 (car set1)) (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1
                     (intersection-set (cdr set1)
                                       (cdr set2))))
              ((< x1 x2)
               (intersection-set (cdr set1) set2))
              ((< x2 x1)
               (intersection-set set1 (cdr set2)))))))

Exercise 2.61 asks us to give an implementation of adjoin-set using the ordered representation. Like element-of-set?, our implementation of adjoin-set should require only half as many steps on average as the unordered representation.

The original implementation of adjoin-set made use of element-of-set? to check and see if the new element was already a member of the set. We no longer need to do this since we need to find the exact position in the set to insert the new element. As we scan through the set looking for the right position, we can simply return the set if we encounter the element we're trying to place.

(define (adjoin-set x set)
  (cond ((null? set) (cons x '()))
        ((= x (car set)) set)
        ((< x (car set)) (cons x set))
        ((> x (car set)) (cons (car set)
                               (adjoin-set x (cdr set))))))

There are several different conditions, and we need to cover them all. First, since we're no longer using element-of-set, we need to check to see if the set itself is null or empty. Second, if the we encounter the element we're trying to add, we can just return the set. Next, if the element we're adding is smaller than the first element of the set, we can simply cons the new element to the beginning of the set. Last, if the new element is greater than the first element of the set, we join the first element followed by the adjoin-set of the new element and the rest of the set.

> (adjoin-set 3 null)
(3)
> (adjoin-set 3 '())
(3)
> (adjoin-set 3 '(3 4 5))
(3 4 5)
> (adjoin-set 3 '(4 5 6))
(3 4 5 6)
> (adjoin-set 3 '(1 2 4 5))
(1 2 3 4 5)
> (adjoin-set 3 '(0 1 2))
(0 1 2 3)

Like element-of-set?, this implementation should only scan through half the set on average before finding the correct insertion point for the new element.

Exercise 2.62 asks us to give a $O(n)$ implementation of union-set for sets represented as ordered lists. Since the two sets are in order, we can simply step through each set comparing the first elements of each. At each step we decide which of the first two elements to place in the resulting set.

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((= (car set1) (car set2))
         (cons (car set1) (union-set (cdr set1) (cdr set2))))
        ((< (car set1) (car set2))
         (cons (car set1) (union-set (cdr set1) set2)))
        (else (cons (car set2) (union-set set1 (cdr set2))))))

Anyone familiar with the mergesort algorithm will quickly recognize that this implementation of union-set is almost exactly the same procedure as the merge subroutine. It's purpose is to quickly merge two sorted lists into one. The only difference is that the union-set implementation above only keeps one copy of duplicate elements.

> (define odds '(1 3 5 7))
> (define evens '(2 4 6 8))
> (define primes '(2 3 5 7))
> (union-set odds evens)
(1 2 3 4 5 6 7 8)
> (union-set odds primes)
(1 2 3 5 7)
> (union-set evens primes)
(2 3 4 5 6 7 8)

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.59 - 2.60: Sets as unordered lists

2012-05-28T21:02:00.000-04:00

From SICP section 2.3.3 Example: Representing Sets

Section 2.3.3 shows us several ways to represent sets in Scheme, starting with unordered sets. To start, we define what a 'set' is by specifying the operations that are to be used on sets. These are:

element-of-set? - a predicate function that determines whether a given element is a member of a set.
adjoin-set - takes an object and a set as arguments and returns the set that contains the elements of the original set and the adjoined object.
intersection-set - computes the intersection of two sets, which is the set containing only elements that appear in both arguments.
union-set - computes the union of two sets, which is the set containing each element that appears in either argument.

We represent a set as an unordered list by making sure no element appears more than once. The text provides the following implementations for representing sets as unordered lists.

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))

(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))

(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)        
         (cons (car set1)
               (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))

We can define a few lists to test and see how these procedures work together.

> (define odds '(1 3 5 7))
> (define evens '(2 4 6 8))
> (define primes '(2 3 5 7))
> (element-of-set? 5 odds)
#t
> (element-of-set? 5 evens)
#f
> odds
(1 3 5 7)
> (adjoin-set 9 odds)
(9 1 3 5 7)
> (intersection-set odds evens)
()
> (intersection-set odds primes)
(3 5 7)
> (intersection-set evens primes)
(2)

Exercise 2.59 asks us to implement the union-set operation for the unordered-list representation of sets.

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((element-of-set? (car set1) set2) (union-set (cdr set1) set2))
        (else (cons (car set1) (union-set (cdr set1) set2)))))

This implementation starts by checking to see if either set is null. If so, the other set is returned immediately. The procedure then checks to see if the first element of set1 is an element of set2. If so, that element is discarded from the first set, and the union of the remaining elements of set1 and set2 are returned. If the first element of set1 is not an element of set2, it is included in the list returned by the procedure.

> (union-set odds evens)
(1 3 5 7 2 4 6 8)
> (union-set odds primes)
(1 2 3 5 7)
> (union-set evens primes)
(4 6 8 2 3 5 7)

Exercise 2.60 asks us what would need to change in the implementations above if we redefine 'set' to allow duplicate elements. For example, the set {1, 2, 3} could be represented as the list (2 3 2 1 3 2 2). We need to compare the efficiency of each of the new procedures with their original (non-duplicate) implementations. The exercise also asks if there are applications where the new representation would be preferred over the original.

The implementation of element-of-set? doesn't need to change. It returns #t when it finds an element that matches the input element, otherwise it returns #f. The implementation of adjoin-set is simplified by the new definition. Since we no longer need to check to see if the input element already exists in the set, we can just cons the element to the existing set.

(define (adjoin-set x set)
   (cons x set))

Like adjoin-set, union-set is also simplified by allowing duplicate elements.

(define (union-set set1 set2) 
   (append set1 set2))

We have an interesting choice when it comes to intersection-set. The intersection of two sets under the original (non-duplicate) definition doesn't seem like it requires any change in implementation since duplicates are now allowed, not necessarily required. However, look what happens when you execute intersection-set with duplicate elements in the first set vs. the second set.

> (define primes '(2 3 5 7))
> (define twos '(2 2 2))
> (intersection-set primes twos)
(2)
> (intersection-set twos primes)
(2 2 2)

The result is different depending on which set has duplicate elements. This is because the original implementation checks each element of the first set independently to see if they're present in the second set. When the first set contains duplicates, so will the result. Since the instructions in the exercise are ambiguous (and being the typical lazy programmer that I am), I'm going to say that this implementation does not need to change.

Since element-of-set? and intersection-set haven't changed, neither will their performance. Since adjoin-set and union-set no longer need to check for duplicate elements, the performance of both of these procedures is improved. The number of steps required by adjoin-set has gone from $O(n)$ to $O(1)$. The number of steps required by union-set has gone from $O(n^2)$ to $O(n)$.

The penalty that we pay for these performance improvements is that sets now require more memory to accommodate duplicate elements. This representation would be preferred over the original in cases where we don't care about that added memory overhead, and where most of our operations are either adjoin-set or union-set.

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

Which Open Source License?

2012-05-06T11:27:00.000-04:00

I was doing a little research on open source software licenses with a student when I came across this flow chart.

I like the balance it strikes between being funny and still being at least somewhat useful and informative. Credit for the original flowchart goes to the creators Dan Bentley and Brian Fitzpatrick. (Thanks to @jldeev for pointing me to the chart.)

For a short break down of the key differences between some of the more popular software licenses, see Jeff Atwood's post Pick a License, Any License on the Coding Horror blog. The main point to take away from the article is that if you don't explicitly declare a license on software you publish, your code is copyrighted by default. To use the code people have to contact you and ask permission. So if you post a lot of code examples on your blog, take a few minutes to pick a license then add a notice to the footer of your site.

SICP 2.56 - 2.58: Symbolic Differentiation

2012-04-22T23:23:00.000-04:00

From SICP section 2.3.2 Example: Symbolic Differentiation

This section of SICP presents an application of symbol manipulation in the form of the following procedure that performs symbolic differentiation of algebraic expressions.

(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))))
        (else
         (error "unknown expression type -- DERIV" exp))))

The following supporting procedures are required by deriv. Each one is explained in the text.

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (make-sum a1 a2) (list '+ a1 a2))
(define (make-product m1 m2) (list '* m1 m2))

(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))

(define (addend s) (cadr s))
(define (augend s) (caddr s))

(define (product? x)
  (and (pair? x) (eq? (car x) '*)))

(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))

With these definitions, we can perform differentiation on algebraic expressions in Scheme's familiar prefix notation.

> (deriv '(+ x 3) 'x)
(+ 1 0)
> (deriv '(* x y) 'x)
(+ (* x 0) (* 1 y))
> (deriv '(* (* x y) (+ x 3)) 'x)
(+ (* (* x y) (+ 1 0)) (* (+ (* x 0) (* 1 y)) (+ x 3)))

This procedure returns results that are correct, but the expressions are not in their simplest form. For example, instead of (+ 1 0) we'd like the procedure to simplify the expression to 1. Similarly, the expression (+ (* x 0) (* 1 y)) can be simplified to y. We only need to change the constructors make-sum and make-product to simplify the resulting expressions. We can change make-sum so that if both its arguments are numbers, make-sum will return their sum. Also, if either of the arguments is 0, then make-sum will return the other summand (whether it's a number or a symbol).

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

Similarly, make-product should return 0 if either of its arguments is 0, and if either of its arguments is 1 it should return the other argument.

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

Both of these new implementations make use of the =number? procedure to check whether an expression is equal to an expected value.

(define (=number? exp num)
  (and (number? exp) (= exp num)))

Here's how the improved procedures work with the same three examples.

> (deriv '(+ x 3) 'x)
1
> (deriv '(* x y) 'x)
y
> (deriv '(* (* x y) (+ x 3)) 'x)
(+ (* x y) (* y (+ x 3)))

The first two resulting expressions are now in simplest form. The third is greatly improved, but could still be better.

Exercise 2.56 asks us to extend the deriv procedure to handle more kinds of expressions. We're to implement the differentiation rule

$\frac{d(u^n)}{dx} = nu^{(n-1)} (\frac{du}{dx})$

by adding a new clause to the deriv program and defining appropriate procedures exponentiation?, base, exponent, and make-exponentiation. (We'll use the symbol ** to denote exponentiation.) We'll also build in the rules that anything raised to the power 0 is 1 and any expression raised to the power 1 is the expression itself. We can base the implementations of exponentiation?, base, and exponent on the corresponding procedures used for sums and products.

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

(define (base e) (cadr e))
(define (exponent e) (caddr e))

Similarly, our implementation of make-exponentiation will be based on the updated versions of make-sum and make-product, since we're going to build in two rules of exponentiation that will simplify resulting expressions.

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

The last step before testing is to extend the deriv procedure itself to recognize and handle exponentiation.

(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)
         (make-product
          (make-product (exponent exp)
                        (make-exponentiation
                         (base exp)
                         (make-sum (exponent exp) -1)))
          (deriv (base exp) var)))
        (else
         (error "unknown expression type -- DERIV" exp))))

We can test the extended implementation of deriv using an example from the beginning of the current section of the text. "For example, if the arguments to the procedure are $ax^2 + bx + c$ and x, the procedure should return $2ax + b$." I'll translate the expression to prefix notation in multiple steps so we can see the effect that each term has on the result.

> (deriv '(** x 2) 'x)
(* 2 x)
> (deriv '(* a (** x 2)) 'x)
(* a (* 2 x))
> (deriv '(+ (* a (** x 2)) (* b x)) 'x)
(+ (* a (* 2 x)) b)
> (deriv '(+ (+ (* a (** x 2)) (* b x)) c) 'x)
(+ (* a (* 2 x)) b)

Exercise 2.57 asks us to extend the deriv program to handle sums and products with arbitrary numbers of (two or more) terms. The third example above could be expressed as

(deriv '(* x y (+ x 3)) 'x)

We'll do this by changing only the representation for sums and products, without changing the deriv procedure itself. (For example, the addend of a sum would be the first term, and the augend would be the sum of the rest of the terms.) We can change the representation for sums and products by changing only two procedures, augend and multiplicand. The original implementations of these procedures simply returned the second argument in a sum or product, respectively. Instead of returning a single value or symbol, we'll need to modify these procedures so they can return an expression.

(define (augend s)
  (if (null? (cdddr s))
      (caddr s)
      (cons '+ (cddr s))))

The new augend procedure first tests to see if the expression passed in has only two arguments by checking to see if its third argument is null. If the expression has only two arguments, the second one is returned, just as it would have been in the original implementation. Otherwise, if the expression has more than two arguments, all of the arguments following the first one are returned in a new sum expresssion. The new implementation of multiplicand is pretty much the same.

(define (multiplicand p)
  (if (null? (cdddr p))
      (caddr p)
      (cons '* (cddr p))))

We can use the example from the text to test that the deriv procedure works correctly with the new representations of sums and products.

> (deriv '(* x y (+ x 3)) 'x)
(+ (* x y) (* y (+ x 3)))

Exercise 2.58 asks us to modify the differentiation program so that it works with ordinary mathematical notation (where + and * are infix rather than prefix operators). Since the differentiation program is defined in terms of abstract data, we can modify it to work with different representations of expressions solely by changing the predicates, selectors, and constructors that define the representation of the algebraic expressions on which the differentiator is to operate. We're to do this in two steps, a fully parenthesized version and a version that drops unnecessary parentheses:

a. Show how to do this in order to differentiate algebraic expressions presented in infix form, such as (x + (3 * (x + (y + 2)))). To simplify the task, assume that + and * always take two arguments and that expressions are fully parenthesized.

We can solve the first part of the problem simply by changing the procedures that define how a sum is represented. Instead of the + symbol appearing first in an expression, it will now appear second.

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

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

(define (addend s) (car s))
(define (augend s) (caddr s))

The definitions for products are equivalent.

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

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

(define (multiplier p) (car p))
(define (multiplicand p) (caddr p))

We can test with a few simple examples before moving to the more complicated example given in the text.

> (deriv '(x + 3) 'x)
1
> (deriv '(x * y) 'x)
y
>  (deriv '(x + (3 * (x + (y + 2)))) 'x)
4

b. The problem becomes substantially harder if we allow standard algebraic notation, such as (x + 3 * (x + y + 2)), which drops unnecessary parentheses and assumes that multiplication is done before addition. Can you design appropriate predicates, selectors, and constructors for this notation such that our derivative program still works?

Only a few additional changes are necessary in order to correctly interpret expressions where unnecessary parentheses are excluded. In part a above we defined both the augend and multiplicand of an expression using caddr. We were able to do this because we knew all expressions would be two parameters separated by an operator, and that the expression would be contained in parentheses.

Since this is no longer the case, we now want the augend and multiplicand procedures to return an entire subexpression, so we'd like to use cddr. The only problem with this is that cddr always returns a list, so it will fail in those cases where the augend or multiplicand is a single value or symbol, as would be the case in fully-parenthesized expressions. We can get around this limitation by introducing a procedure that will simplify sub-expressions of this form by returning a single value or symbol if that's all there is to an expression.

(define (simplify exp)
  (if (null? (cdr exp)) (car exp) exp))

Now we can define augend and multiplicand in terms of simplify and cddr.

(define (augend s) (simplify (cddr s)))
(define (multiplicand p) (simplify (cddr p)))

We can test a few different expressions, starting with the example given.

> (deriv '(x + 3 * (x + y + 2)) 'x)
4
> (deriv '(x + 3 * (x + y + 2)) 'y)
3

Finally, we should also test a few simpler cases to make sure our changes didn't break anything.

> (deriv '(x + 3) 'x)
1
> (deriv '(x * y) 'x)
y
> (deriv '(x * y * (x + 3)) 'x)
((x * y) + (y * (x + 3)))

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.53 - 2.55: Symbolic Data

2012-03-01T21:48:00.002-05:00

From SICP section 2.3.1 Quotation

This section of SICP introduces quotation, which gives us the ability to manipulate symbols as well as data values. When we quote a symbol the interpreter returns the literal symbol instead of the value that the symbol points to.

> (define a 1)
> a
1
> (quote a)
a

As a shorthand for quote we can place a single quote symbol at the beginning of the object to be quoted.

> 'a
a

We can also use quotation with compound objects.

> (define x '(a b c))
> x
(a b c)
> (car x)
a

Finally, we're introduced to the primitive eq?, which takes two symbols as arguments and tests whether they are the same (they consist of the same characters in the same order). We're also shown how we can use eq? to create a procedure memq that takes two arguments, a symbol and a list. If the symbol is not contained in the list, then memq returns false. Otherwise, it returns the sub-list that begins with the first occurrence of the symbol.

Exercise 2.53 asks us what the interpreter would print in response to evaluating each of the following expressions? See if you can predict what the output should be before trying each expression.

(list 'a 'b 'c)

(list (list 'george))

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

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

(pair? (car '(a short list)))

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

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

The first expression just creates a list containing three symbols, so it should evaluate the same as '(a b c).

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

The second expression creates a list that contains a list that contains a symbol.

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

The third expression gets the cdr of a list containing two lists of symbols. Remember from earlier sections that the car of a list is the first element in a list and the cdr is the remainder of the list.

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

The fourth expression gets the second element of the same list as above.

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

The fifth expression is checking to see if the car of a quoted list is a pair. You should be able to see that it's not, but try evaluating sub-expressions if you're unsure.

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

The sixth expression is using the memq procedure to see if a symbol is contained in a list. Remember that memq only checks the highest-level elements of the list, it doesn't recursively look inside any sub-lists.

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

The final expression is also using memq to look for a symbol in a list, but this time with different results.

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

Exercise 2.54 asks us to define a procedure equal? that takes two parameters and returns true if they contain equal elements arranged in the same order. The parameters can be values, symbols, lists of symbols, or lists containing both symbols and nested lists. We are to define equal? recursively in terms of the basic eq? equality of symbols.

(define (equal? p1 p2)
  (cond ((and (null? p1) (null? p2)) #t)
        ((or (null? p1) (null? p2)) #f)
        ((and (pair? p1) (pair? p2))
         (and (equal? (car p1) (car p2))
              (equal? (cdr p1) (cdr p2))))
        ((or (pair? p1) (pair? p2)) #f)
        (else (eq? p1 p2))))

The procedure starts by checking to see if both parameters are null and returns #t if they are. It then checks to see if only one parameter but not the other is null. Next it checks to see if both parameters are pairs, and if they are it recursively checks to see if they have the same car and the same cdr. Next it checks to see if only one of the parameters is a pair and returns #f if that's the case. Finally, it checks to see if the two parameters are the same symbol or have the same value. We can run several tests to validate all the cases above.

> (equal? '() '())
#t
> (equal? '() 'a)
#f
> (equal? '((x1 x2) (y1 y2)) '((x1 x2) (y1 y2)))
#t
> (equal? '((x1 x2) (y1 y2)) '((x1 x2 x3) (y1 y2)))
#f
> (equal? '(x1 x2) 'y1)
#f
> (equal? 'abc 'abc)
#t
> (equal? 123 123)
#t

Exercise 2.55 asks us to explain why when a user types the expression

(car ''abracadabra)

the interpreter prints back quote.

Remember that ' is just shorthand for quote, so the expression above is equivalent to

(car (quote (quote abracadabra)))

The sub-expression (quote (quote abracadabra)) is equivalent to '(quote abracadabra), which is just the list containing the two symbols quote and abracadabra, making the car of that list simply the symbol quote.

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.52: Levels of Language for Robust Design

2012-02-05T17:08:00.005-05:00

From SICP section 2.2.4 Example: A Picture Language

Just as we did in previous exercises, we can use the PLT Scheme SICP Picture Language package to run the solutions to the following exercises. You can load the picture package by putting the following (require...) expression at the beginning of your Scheme file.

(require (planet "sicp.ss" ("soegaard" "sicp.plt" 2 1)))

Exercise 2.52 asks us to make changes to the square limit of wave shown in figure 2.9 by working at the appropriate level of abstraction for the required change. (We'll need all the code we wrote in exercises 2.44 and 2.49 to start out with, so copy those into a new Scheme file.)

2.52a. Add some segments to the primitive wave painter of exercise 2.49 (to add a smile, for example).

This change requires that we make a change at a low level of abstraction, in adding segments to the wave painter itself. Let's add an eye and a smiling mouth on the left side of the head so it looks like the person in wave is looking in that direction.

; The wave painter (2.49d).
; Add some segments to form a smile (2.52a)
(define wave-segments
 (list
  (make-segment
   (make-vect 0.006 0.840)
   (make-vect 0.155 0.591))
  (make-segment
   (make-vect 0.006 0.635)
   (make-vect 0.155 0.392))
  (make-segment
   (make-vect 0.304 0.646)
   (make-vect 0.155 0.591))
  (make-segment
   (make-vect 0.298 0.591)
   (make-vect 0.155 0.392))
  (make-segment
   (make-vect 0.304 0.646)
   (make-vect 0.403 0.646))
  (make-segment
   (make-vect 0.298 0.591)
   (make-vect 0.354 0.492))
  (make-segment ; left face
   (make-vect 0.403 0.646)
   (make-vect 0.348 0.845))
  (make-segment
   (make-vect 0.354 0.492)
   (make-vect 0.249 0.000))
  (make-segment
   (make-vect 0.403 0.000)
   (make-vect 0.502 0.293))
  (make-segment
   (make-vect 0.502 0.293)
   (make-vect 0.602 0.000))
  (make-segment
   (make-vect 0.348 0.845)
   (make-vect 0.403 0.999))
  (make-segment
   (make-vect 0.602 0.999)
   (make-vect 0.652 0.845))
  (make-segment
   (make-vect 0.652 0.845)
   (make-vect 0.602 0.646))
  (make-segment
   (make-vect 0.602 0.646)
   (make-vect 0.751 0.646))
  (make-segment
   (make-vect 0.751 0.646)
   (make-vect 0.999 0.343))
  (make-segment
   (make-vect 0.751 0.000)
   (make-vect 0.597 0.442))
  (make-segment
   (make-vect 0.597 0.442)
   (make-vect 0.999 0.144))
  (make-segment ; eye
   (make-vect 0.395 0.916)
   (make-vect 0.410 0.916))
  (make-segment ; smile
   (make-vect 0.376 0.746)
   (make-vect 0.460 0.790))))

2.52b. Change the pattern constructed by corner-split (for example, by using only one copy of the up-split and right-split images instead of two).

For this requirement we need to work in the middle layer of abstraction. To use only one copy of the up-split and right-split images instead of two, we can simply remove the references to top-left and bottom-right that appear in the original implementation of corner-split.

(define (corner-split painter n)
 (if (= n 0)
     painter
     (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)))))

2.52c. Modify the version of square-limit that uses square-of-four so as to assemble the corners in a different pattern. (For example, you might make the big Mr. Rogers look outward from each corner of the square.)

We're not using the Mr. Rogers painter from the text, but we can still rearrange the square-limit painter so that the largest wave image is drawn in the four corners by simply rotating the corner-split painter by 180 degrees.

(define (square-limit painter n)
 (let ((quarter (rotate180 (corner-split painter n))))
   (let ((half (beside (flip-horiz quarter) quarter)))
     (below (flip-vert half) half))))

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.50 - 2.51: Transforming and Combining Painters

2012-01-02T17:28:00.008-05:00

From SICP section 2.2.4 Example: A Picture Language

Just as we did in exercises 2.44, 2.45, and 2.49, we can use the PLT Scheme SICP Picture Language package to run the solutions to the following exercises. You can load the picture package by putting the following (require...) expression at the beginning of your Scheme file.

(require (planet "sicp.ss" ("soegaard" "sicp.plt" 2 1)))

Exercise 2.50 asks us to define the transformation flip-horiz, which flips painters horizontally, and transformations that rotate painters counterclockwise by 180 degrees and 270 degrees.

We're expected to use the transform-painter procedure defined earlier in section 2.2.4 of the text. Since we're using the PLT Scheme SICP Picture Language package, we'll be using a version of transform-painter that's defined slightly differently than the one in the text. This procedure does not take the painter to be transformed as an argument, as does the version given in the text. Instead it takes the points that specify the corners of the new frame as arguments and returns a procedure that takes the painter as its argument.

For example, instead of defining flip-vert as:

(define (flip-vert painter)
   (transform-painter painter
             (make-vect 0.0 1.0)   ; new origin
             (make-vect 1.0 1.0)   ; new end of edge1
             (make-vect 0.0 0.0))) ; new end of edge2

We would instead pass the painter as an argument to the procedure returned from transform-painter as follows:

(define (flip-vertical painter)
   ((transform-painter (make-vect 0.0 1.0)
                       (make-vect 1.0 1.0)
                       (make-vect 0.0 0.0))
    painter))

The arguments to transform-painter are points (represented as vectors) that specify the corners of the new frame. The first point specifies the new frame's origin and the other two specify the ends of its edge vectors. Remember that the origin point in a frame is normally in the lower left hand corner. The first edge vector is the bottom edge of frame and the second edge vector is the left edge of the frame.

These edges are defined by the points (0, 0) for the origin, (1, 0) for the end point of the first edge, and (0, 1) for the end point of the second edge. In order to transform a painter we just need to redraw the figure above in the desired orientation, then call transform-painter with the new positions of the origin and the end points of the edges.

To flip a painter horizontally we just move the origin and left edge to the right.

This gives the bottom edge a new endpoint as well. The procedure (based on flip-vert) would be:

(define (flip-horizontal painter)
   ((transform-painter (make-vect 1.0 0.0)   ; origin
                       (make-vect 0.0 0.0)   ; corner1
                       (make-vect 1.0 1.0))  ; corner2
    painter))

The following images show the locations of the origin and edges when we rotate an image counterclockwise by 180 and 270 degrees.

We can implement the procedures using the origin and endpoints shown in the figures above.

(define (rotate-180 painter)
   ((transform-painter (make-vect 1.0 1.0)
                       (make-vect 0.0 1.0)
                       (make-vect 1.0 0.0))
    painter))

(define (rotate-270 painter)
   ((transform-painter (make-vect 0.0 1.0)
                       (make-vect 0.0 0.0)
                       (make-vect 1.0 1.0))
    painter))

Use the einstein painter provided by the PLT Scheme SICP Picture Language package to check the output of the procedures above.

Exercise 2.51 asks us to define the below operation for painters. The below procedure takes two painters as arguments. The resulting painter draws the first painter in the bottom of the frame and the second painter in the top. We're asked to define below in two different ways -- first by writing a procedure that is analogous to the beside procedure given in the text, and again in terms of beside and suitable rotation operations like the ones we defined in exercise 2.50.

Translating the beside procedure from the text to create the first below procedure is a simple matter of applying what we learned in exercise 2.50 above.

(define (beside painter1 painter2)
   (let ((split-point (make-vect 0.5 0.0)))
   (let ((paint-left
         (transform-painter painter1
                            (make-vect 0.0 0.0)
                            split-point
                            (make-vect 0.0 1.0)))
         (paint-right
         (transform-painter painter2
                            split-point
                           (make-vect 1.0 0.0)
                           (make-vect 0.5 1.0))))
   (lambda (frame)
     (paint-left frame)
     (paint-right frame)))))

The beside procedure first defines a split-point at the bottom center of the frame that splits the frame vertically. It then transforms the two painters provided so that they each fit into one half of the frame. Finally, it returns a procedure that, when given a frame, paints the two images in the left and right halves of the frame. Here's the analogous below procedure:

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

We need to redefine the split-point so that it divides the frame horizontally instead of vertically. We then transform the painters so that they fit into the bottom and top halves of the frame. Finally, we return a procedure that draws the two halves.

The second implementation of below is even simpler than the first. We just need to draw the two painters beside each other then rotate the frame by 90 degrees. When we do that the two images will be draw on their side, so we need to rotate the individual images 90 degrees in the opposite direction inside their smaller frames. This is equivalent to rotating them 270 degrees in the same direction.

; 2.51b
(define (rotate-90 painter)
 ((transform-painter (make-vect 1.0 0.0)
                     (make-vect 1.0 1.0)
                     (make-vect 0.0 0.0))
   painter))

(define (below-b painter1 painter2)
   (rotate-90 (beside (rotate-270 painter1) (rotate-270 painter2))))

Once again, we can test with einstein to verify that these two procedures both give us the desired output.

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

The "N Days of Christmas" Solution

2011-12-22T21:12:00.007-05:00

A few days ago in The "N Days of Christmas" Puzzle I asked if you could figure out how many gifts you receive in total for all twelve days (not just on the twelfth day) of the song "The Twelve Days of Christmas," and to find an elegant way to calculate the number of gifts you'd receive if the number of days is extended beyond twelve.

First we need to figure out how many gifts we receive on a given day. It is a cumulative song, so you receive one partridge in a pear tree on the first day, then on the second day you receive two turtle doves and another partridge in a pear tree, and so on for twelve days. So the sequence for each day is:

1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 4 = 10
1 + 2 + 3 + 4 + 5 = 15
...

That's probably enough terms that you'll start to recognize a pattern is forming. Each number in the sequence is just the sum of the first n integers, which you may recognize as the triangle numbers. For a small number of days like 12 we can just continue adding terms to the sequence and have the answer in about a minute. We could look up the formula for the nth triangle number, but with a little bit of intuition we can come up with one ourselves. (When you write your own blog, you get to pretend you're a little bit smarter and less lazy than you really are.) Sometimes it helps to draw a picture like the following:

Notice that the circles form the same sequence that we're after. Also note that since the circles are arranged in a triangle we can calculate the total number of circles by multiplying the height of the enclosing rectangle (n) by the width (n + 1) and dividing by 2. This gives us the formula for the nth triangle number.

$T_n = \frac{n(n + 1)}{2}$

That only gives us the number of gifts on the last day though. We wanted to know the number of gifts on all days combined, and we wanted to know it for any number of days. So what we really want isn't the nth triangle number (the sum of the first n integers), but the sum of the first n triangle numbers. That's a formula that we can derive from what we already know.

$\sum_{k=1}^{n}\frac{k(k + 1)}{2}$

$\frac{1}{2}\sum_{k=1}^{n}k(k + 1)$

$\frac{1}{2}\sum_{k=1}^{n}(k^2 + k)$

$\frac{1}{2}\sum_{k=1}^{n}k^2 + \frac{1}{2}\sum_{k=1}^{n}k$

At this point we should take a moment to say out loud what the two terms in this equation mean in plain English. On the left we have one-half of the sum of the first n squares, and on the right we have one-half of the sum of the first n integers. We already found a formula for the sum of the first n integers, and it seems like there ought to be a similar formula for the sum of the first n squares. There is, and to save us some time I’ll just substitute it here¹.

$\frac{1}{2}\frac{n (n + 1) (2n + 1)}{6} + \frac{1}{2}\frac{n (n + 1)}{2}$

$\frac{(n^2 + n)(2n + 1)}{12} + \frac{n(n + 1)}{4}$

$\frac{(2n^3 + 3n^2 + n)}{12} + \frac{(n^2 + n)}{4}$

$\frac{(2n^3 + 3n^2 + n)}{12} + \frac{(3n^2 + 3n)}{12}$

$\frac{(2n^3 + 6n^2 + 4n)}{12}$

$\frac{(n^3 + 3n^2 + 2n)}{6}$

$\frac{n(n^2 + 3n + 2)}{6}$

$\frac{n(n + 1)(n + 2)}{6}$

That gives us our formula for the sum of the first n triangle numbers, which is also known as a tetrahedral number. This is the number you get when you turn the first n triangles on their side and stack them in a pyramid.

So if we plug 12 into the formula above, we find out that in total there are

$\frac{12 \times 13 \times 14}{6} = 364$

total gifts given in the Twelve Days of Christmas.

Happy Holidays!

¹ The sequence given by the sum of the first N squares is called the square pyramidal numbers.

The "N Days of Christmas" Puzzle

2011-12-16T22:58:00.006-05:00

I received an interesting puzzle in an email from my friend Tim recently. See if you can figure it out.

My dad and I were bored at a Christmas concert lately, so we started
talking about how many items you receive in the 12 days of Christmas.

You get 1 item on day 1, 3 items on day 2, 6 on day 3, etc. We
figured that out pretty easily, but then we were trying to come up
with a closed form solution for any number of days.

When I got home and had some paper to work with I managed to do it,
but I felt like my approach wasn't very nice.

So, can you find a solution, and more importantly do you know an
elegant way to do it?

If you're not familiar with the song, you can find the basic structure of the lyrics on Wikipedia, or just Google "the 12 days of Christmas" and you'll find it.

Just to be clear, it is a cumulative song, so you receive one partridge in a pear tree on the first day, then on the second day you receive two turtle doves and another partridge in a pear tree, for a total of four items on the first two days, and so on for twelve days. The puzzle is to find out how many gifts you receive in total for all twelve days (not just on the twelfth day), and to find an elegant way to calculate the number of gifts you'd receive if the number of days is extended beyond twelve.

You can see the solution here.

SICP 2.49: Defining Primitive Painters

2011-10-09T13:09:00.006-04:00

From SICP section 2.2.4 Example: A Picture Language

Exercise 2.49 asks us to use segments->painter to define the following primitive painters:

The painter that draws the outline of the designated frame.
The painter that draws an "X'' by connecting opposite corners of the frame.
The painter that draws a diamond shape by connecting the midpoints of the sides of the frame.
The wave painter.

Just as we did in exercises 2.44 & 2.45, we can use the PLT Scheme SICP Picture Language package to run the exercises. You can load the picture package by putting the following (require...) expression at the beginning of your Scheme file.

(require (planet "sicp.ss" ("soegaard" "sicp.plt" 2 1)))

Since segments->painter takes a list of segments as its input parameter, each solution is just a matter of figuring out the coordinates of the endpoints of each required segment. Recall that the (0.0, 0.0) coordinate is the bottom left corner in the frame, not the top left corner as it is in many GUI environments. For each solution, we can define the list of segments first, then define a painter.

; 2.49 a.
; The painter that draws the outline of the designated frame.
(define outline-segments
 (list
  (make-segment
   (make-vect 0.0 0.0)
   (make-vect 0.0 0.99))
  (make-segment
   (make-vect 0.0 0.0)
   (make-vect 0.99 0.0))
  (make-segment
   (make-vect 0.99 0.0)
   (make-vect 0.99 0.99))
  (make-segment
   (make-vect 0.0 0.99)
   (make-vect 0.99 0.99))))

(define outline (segments->painter outline-segments))

Note that I used 0.99 instead of 1.0 for the edges of the frame. This is because the top and right edges won't be displayed if you use 1.0.

; 2.49 b.
; The painter that draws an ``X'' by connecting opposite corners of the frame.
(define x-segments
 (list
  (make-segment
   (make-vect 0.0 0.0)
   (make-vect 0.99 0.99))
  (make-segment
   (make-vect 0.0 0.99)
   (make-vect 0.99 0.0))))

(define x-painter (segments->painter x-segments))

; 2.49 c.
; The painter that draws a diamond shape by connecting the midpoints of the sides of the frame.
(define diamond-segments
 (list
  (make-segment
   (make-vect 0.0 0.5)
   (make-vect 0.5 0.0))
  (make-segment
   (make-vect 0.0 0.5)
   (make-vect 0.5 0.999))
  (make-segment
   (make-vect 0.5 0.999)
   (make-vect 0.999 0.5))
  (make-segment
   (make-vect 0.999 0.5)
   (make-vect 0.5 0.0))))

(define diamond (segments->painter diamond-segments))

The wave painter in the last part of the exercise is the image shown in Figure 2.10 of the text. It consists of 17 separate segments.

; 2.49 d.
; The wave painter.
(define wave-segments
 (list
  (make-segment
   (make-vect 0.006 0.840)
   (make-vect 0.155 0.591))
  (make-segment
   (make-vect 0.006 0.635)
   (make-vect 0.155 0.392))
  (make-segment
   (make-vect 0.304 0.646)
   (make-vect 0.155 0.591))
  (make-segment
   (make-vect 0.298 0.591)
   (make-vect 0.155 0.392))
  (make-segment
   (make-vect 0.304 0.646)
   (make-vect 0.403 0.646))
  (make-segment
   (make-vect 0.298 0.591)
   (make-vect 0.354 0.492))
  (make-segment
   (make-vect 0.403 0.646)
   (make-vect 0.348 0.845))
  (make-segment
   (make-vect 0.354 0.492)
   (make-vect 0.249 0.000))
  (make-segment
   (make-vect 0.403 0.000)
   (make-vect 0.502 0.293))
  (make-segment
   (make-vect 0.502 0.293)
   (make-vect 0.602 0.000))
  (make-segment
   (make-vect 0.348 0.845)
   (make-vect 0.403 0.999))
  (make-segment
   (make-vect 0.602 0.999)
   (make-vect 0.652 0.845))
  (make-segment
   (make-vect 0.652 0.845)
   (make-vect 0.602 0.646))
  (make-segment
   (make-vect 0.602 0.646)
   (make-vect 0.751 0.646))
  (make-segment
   (make-vect 0.751 0.646)
   (make-vect 0.999 0.343))
  (make-segment
   (make-vect 0.751 0.000)
   (make-vect 0.597 0.442))
  (make-segment
   (make-vect 0.597 0.442)
   (make-vect 0.999 0.144))))

(define wave (segments->painter wave-segments))

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.46 - 2.48: Frames & Painters

2011-09-25T18:56:00.002-04:00

From SICP section 2.2.4 Example: A Picture Language

A frame can be described by three vectors -- an origin vector and two edge vectors. The origin vector specifies the offset of the frame's origin from some absolute origin in the plane, and the edge vectors specify the offsets of the frame's corners from its origin. If the edges are perpendicular, the frame will be rectangular. Otherwise the frame will be a more general parallelogram. A two-dimensional vector v running from the origin to a point can be represented as a pair consisting of an x-coordinate and a y-coordinate.

Exercise 2.46 asks us to implement a data abstraction for vectors by giving a constructor make-vect and corresponding selectors xcor-vect and ycor-vect. In terms of these selectors and constructor, we'll also implement procedures add-vect, sub-vect, and scale-vect that perform the operations for vector addition, vector subtraction, and multiplying a vector by a scalar:

(x1, y1) + (x2, y2) = (x1 + x2, y1 + y2)
(x1, y1) - (x2, y2) = (x1 - x2, y1 - y2)
s * (x, y) = (sx, sy)

The solution for the constructor and selectors uses cons, car, and cdr in the same pattern we've seen at least a dozen times by now.

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

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

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

Once we have those procedures in place, we can use them to build the vector operations specified.

(define (add-vect u v)
   (make-vect
     (+ (xcor-vect u) (xcor-vect v))
     (+ (ycor-vect u) (ycor-vect v))))

(define (sub-vect u v)
   (make-vect
     (- (xcor-vect u) (xcor-vect v))
     (- (ycor-vect u) (ycor-vect v))))

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

We can test these procedures out with a few known values before moving on to the next step.

> (define u (make-vect 2 4))
> u
(2 . 4)
> (define v (make-vect 3 1))
> v
(3 . 1)
> (define w (add-vect u v))
> w
(5 . 5)
> (define x (sub-vect w u))
> x
(3 . 1)
> (define y (scale-vect 3 w))
> y
(15 . 15)

Exercise 2.47 gives us the following constructors for frames, one using list and the other using cons:

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

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

We're asked to supply the appropriate selectors to produce an implementation for frames for each of the two constructors. Like any selector implementation, the task here is simply to extract each piece from the assembled object. We'll follow the naming convention from the previous exercise and call our selectors origin-frame, edge1-frame, and edge2-frame. Let's start with the version that uses list.

; 2.47a
(define (make-frame origin edge1 edge2)
   (list origin edge1 edge2))

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

(define (edge1-frame frame)
   (car (cdr frame)))

(define (edge2-frame frame)
   (car (cdr (cdr frame))))

The selectors simply use the right combinations of car and cdr to extract the appropriate elements from the list. We can test it with some of the same values used in the previous exercise, but we'll need to add an origin vector.

> (define f (make-frame (make-vect 0 0) (make-vect 2 4) (make-vect 3 1)))
> f
((0 . 0) (2 . 4) (3 . 1))
> (origin-frame f)
(0 . 0)
> (edge1-frame f)
(2 . 4)
> (edge2-frame f)
(3 . 1)

Because the internal representation of a frame is different in the second implementation of make-frame, one of the selectors will have to change for the second part of the exercise. The original origin-frame and edge1-frame implementations will still work, but the edge2-frame procedure causes an error if you try to use it.

; 2.47b
(define (make-frame origin edge1 edge2)
   (cons origin (cons edge1 edge2)))

(define (edge2-frame frame)
   (cdr (cdr frame)))

Run exactly the same test from above to verify that you get the same results (except for the internal structure of the frame in the second step).

> (define f (make-frame (make-vect 0 0) (make-vect 2 4) (make-vect 3 1)))
> f
((0 . 0) (2 . 4) 3 . 1)
> (origin-frame f)
(0 . 0)
> (edge1-frame f)
(2 . 4)
> (edge2-frame f)
(3 . 1)

Exercise 2.48 asks us to define a representation for segments using our vector representation from exercise 2.46 above. We'll need to define the constructor make-segment and the selectors start-segment and end-segment.

(define (make-segment v1 v2)
   (cons v1 v2))

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

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

Again, these use the same pattern we've seen before. In the next exercise, we'll take a closer look at the procedures above by drawing pictures with line segments using The SICP Picture Language package.

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.44 & 2.45: A Picture Language

2011-08-20T16:00:00.018-04:00

From SICP section 2.2.4 Example: A Picture Language

The next section of SICP is an extended example that illustrates the features of the picture language introduced in SICP Lecture 3A: Henderson Escher Example. I'm going to be using the PLT Scheme SICP Picture Language package to run the examples and exercises. You can load the picture package by putting the following (require...) expression at the beginning of your Scheme file.

(require (planet "sicp.ss" ("soegaard" "sicp.plt" 2 1)))

The painter primitive in the PLT package behaves slightly differently than the one presented in the text, in that it doesn't display itself. To display a painter you must call the paint procedure, which takes a painter as its argument.

> (paint einstein)





> (paint diagonal-shading)

The einstein and diagonal-shading painter values are built in to the PLT Scheme Picture Language package. The package also includes procedures for flipping, rotating and combining painter values, similar to those discussed in the lecture.

> (paint (flip-horiz einstein))





> (paint (flip-vert einstein))





> (paint (rotate90 einstein))





> (paint (beside einstein einstein))





> (paint (below einstein einstein))

Now that we can work with painters, we can start to combine them in ways that form patterns. For example, the text shows us how we can combine an image beside a flipped representation of itself, then draw the resulting painter below itself.

(define (flipped-pairs painter)

   (let ((painter2 (beside painter (flip-vert painter))))

     (below painter2 painter2)))



> (paint (flipped-pairs einstein))

We can also define recursive operations, like right-split, which makes painters split and branch towards the right as many times as we specify.

(define (right-split painter n)

   (if (= n 0)

       painter

       (let ((smaller (right-split painter (- n 1))))

         (beside painter (below smaller smaller)))))



> (paint (right-split einstein 3))

Exercise 2.44 asks us to define the procedure up-split. It's similar to right-split, except that it switches the roles of below and beside.

(define (up-split painter n)

   (if (= n 0)

       painter

       (let ((smaller (up-split painter (- n 1))))

         (below painter (beside smaller smaller)))))



> (paint (up-split einstein 3))

Once we have both right-split and up-split defined, we can create balanced patterns by branching in both directions.

(define (corner-split painter n)

   (if (= n 0)

      painter

       (let ((up (up-split painter (- n 1)))

            (right (right-split painter (- n 1))))

         (let ((top-left (beside up up))

               (bottom-right (below right right))

               (corner (corner-split painter (- n 1))))

           (beside (below painter top-left)

                   (below bottom-right corner))))))



> (paint (corner-split einstein 1))





> (paint (corner-split einstein 2))

By combining four copies of the corner-split pattern, we can create the square-limit pattern from the Escher drawing that we saw in the lecture.

(define (square-limit painter n)

   (let ((quarter (corner-split painter n)))

     (let ((half (beside (flip-horiz quarter) quarter)))

       (below (flip-vert half) half))))



> (paint (square-limit einstein 4))

Exercise 2.45 points out that right-split and up-split can be expressed as instances of a general splitting operation. We are to define a split procedure, and then rewrite right-split and up-split in terms of split as follows:

(define right-split (split beside below))

(define up-split (split below beside))

We already noted the similarity between the two procedures right-split and up-split when we solved exercise 2.44 above. The only real difference between them is in which direction they split the painter first. Given the amount of duplication between the two, we can use either one of these procedures as a template for split.

(define (split dir1 dir2)

   (lambda (painter n)

     (if (= n 0)

         painter

         (let ((smaller ((split dir1 dir2) painter (- n 1))))

           (dir1 painter (dir2 smaller smaller))))))

The biggest change is that split uses a lambda to return the procedure that it creates. Once you're done substituting the new definitions for right-split and up-split, you can run the square-limit procedure again to verify that the output hasn't changed.

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP Lecture 3A: Henderson Escher Example

2011-07-24T16:02:00.008-04:00

Structure and Interpretation of Computer Programs
Henderson Escher Example
Covers Text Section 2.2.2

You can download the video lecture or stream it on MIT's OpenCourseWare site. It's also available on YouTube.

This lecture is presented by Professor Harold Abelson.

This lecture starts out with a review of the material covered in the previous lecture on compound data. The main points covered are pairs and the closure property (the things we make by forming pairs can also be combined to form pairs).

We're then shown how cons can be used to create lists of primitive elements in Scheme.

(cons 1
    (cons 2
         (cons 3
              (cons 4 nil))))

is the same as

(list 1 2 3 4)

A common pattern in programming is to write procedures that takes a list, do something to every element of that list, and return a list containing the results. We saw an example, scale-list, that takes a list and a factor and returns the result of each element in the list multiplied by the factor.

(define (scale-list items factor)
   (if (null? items)
       nil
       (cons (* (car items) factor)
             (scale-list (cdr items) factor))))

In Scheme terms, the general pattern here is to recursively do something to the cdr of the list and cons that on to actually doing something to the first element of the list.

The very fact that there's a general pattern there means I shouldn't be writing this procedure at all.

Instead of embedding a general pattern in each procedure that uses it, we should write a procedure that's the general pattern itself and write our procedure in terms of that higher-order procedure. For this example, that higher-order procedure is map. (See SICP 2.21 - 2.23: Mapping over lists for examples.)

(define (map proc items)
   (if (null? items)
       nil
       (cons (proc (car items))
             (map proc (cdr items)))))

The important idea here is that we stop thinking about control structures and start thinking about applying operations to aggregates.

Henderson Escher Example

The remainder of the lecture talks about one particular example, the Henderson Escher Example, that summarizes everything that's been covered in the course so far, list structure, abstraction, representation, and capturing commonality with higher-order procedures. It also goes into the third major theme of the course, meta-linguistic abstraction.

Meta-linguistic abstraction:

Primitives
Means of Combination
Means of Abstraction

The example is a language developed by Peter Henderson for describing images that are composed of repeated elements that are shifted and scaled, like the M. C. Escher woodcut "Square Limit" pictured below.

The other theme illustrated by this example is the issue that there is no real difference between procedures and data.

The language operates on primitives called pictures. A picture is a procedure that draws a figure scaled to fit a rectangle that you specify. The following operations are supported in the language.

rotate - Rotate a picture 90 degrees.
flip - Flip a picture horizonally or vertically.
beside - Draw two pictures beside one another.
above - Draw two pictures, one above the other.

The closure property allows you to build complex pictures with just these few operations and one primitive (the picture itself). When you combine two pictures with beside or above, the result is itself a picture, which can be combined with other pictures.

We're going to see a lot of details concerning the implementation of the picture language illustrated in this example as we go through the exercises in the next section of the text, so I won't reproduce those details here. The gist is that we define one set of procedures to draw pictures inside of rectangles, another set of procedures that do the geometric manipulations of those pictures listed above (rotate, flip, beside, and above), then a higher-order set of procedures that combine those manipulated pictures in different ways to make an image like the Escher drawing above..

Software Design Methodologies

The last part of the lecture talks about the common software design methodology of decomposing a problem into discrete components, which are themselves decomposed into discrete components, and so on until you reach a design that looks like the tree structure below.

Each component in this kind of design is created to do one specific task, and the components only communicate with direct parent or child components in the hierarchy. Contrast this with the way the picture language was developed in the Henderson Escher example. First, a language for drawing primitive pictures was presented, then on top of that we build a language for geometric rotations, and finally, on top of that we built a language for schemes of combination.

This scheme gives you a full range of linguistic power at each level.

Lisp is a lousy language for doing any particular problem. What it's good for is figuring out the right language that you want and embedding that in Lisp.

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

Letter Frequencies and Keyboard Layouts

2011-07-09T12:41:00.006-04:00

I saw Mike Knuepfel's Keyboard Frequency Sculpture a few weeks ago and thought it was an excellent idea for visualizing letter frequency data.

The height of each key corresponds to how frequently that letter is used in samples of English writing.

I wanted to see how the layout of the most frequently used letters on a QWERTY keyboard compared to those on a Dvorak keyboard. Unfortunately, I'm no sculptor, and I couldn't see an easy way to slice and edit the original image to rearrange the keys, so I decided to use a color mapping instead.

The images below were created using the same letter frequency chart as the original sculpture. Pure blue is for the least frequently used letters, while pure red is most frequent.

QWERTY

Dvorak

Note that the majority of the most frequently used keys are on the home row in the Dvorak layout, but they're scattered all around on a QWERTY keyboard. The QWERTY layout originated in the very early days of mechanical typewriters, so the keys were arranged such that common two-letter combinations were placed on opposite sides of the keyboard so that the mechanical parts would not jam. The Dvorak layout was designed to reduce finger motion in order to increase typing rate and decrease errors. Despite these advantages, the Dvorak layout has still failed to catch on.

SICP 2.42 & 2.43: The N Queens Problem

2011-06-30T18:23:00.005-04:00

From SICP section 2.2.3 Sequences as Conventional Interfaces

The eight queens puzzle is the problem of placing eight queens on an 8x8 chess board so that no two queens attack each other. A solution requires that no two queens share the same row, column, or diagonal. One possible solution (there are 92) is shown in the figure below.

The eight queens puzzle is an example of the more general n queens problem of placing n queens on an nxn chessboard. SICP suggests that one way to solve the puzzle is to work across the board, placing a queen in each column. Once k - 1 queens are placed, the kth queen must be placed in a position where it is not in check from any of the queens already on the board. This approach can be formulated recursively.

Assume that we have already generated the sequence of all possible ways to place k - 1 queens in the first k - 1 columns of the board. For each of these ways, generate an extended set of positions by placing a queen in each row of the kth column. Now filter these, keeping only the positions for which the queen in the kth column is safe with respect to the other queens. This produces the sequence of all ways to place k queens in the first k columns. By continuing this process, we will produce not only one solution, but all solutions to the puzzle.

Exercise 2.42 implements a partial solution as the procedure queens, which returns a sequence of all solutions to the problem of placing n queens on an nxn board. The internal procedure queen-cols returns the sequence of all ways to place queens in the first k columns of the board.

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

In this procedure rest-of-queens is a way to place k - 1 queens in the first k - 1 columns, and the parameter new-row is a proposed row in which to place the queen for the kth column.

Our task is to complete the program by implementing the representation for sets of board positions, including the procedure adjoin-position, which adjoins a new row-column position to a set of positions, and empty-board, which represents an empty set of positions. (Note that the word position in this problem means the row and column of a single queen, not the placement of all pieces on the board, as is the normal use of the word position in chess terminology. Here the plural form positions is used to indicate the position of all the queens on a single board. A set of positions represents one solution to the problem.) We must also write the procedure safe?, which determines for a set of positions, whether the queen in the kth column is safe with respect to the others.

Since a position is just a row-column pair, we can use what should by now be the familiar method for representing pairs.

(define (make-position row col)
   (cons row col))

(define (position-row position)
   (car position))

(define (position-col position)
   (cdr position))

We can represent an empty board with null, and adjoin a new position to a board using list operations.

(define empty-board null)

(define (adjoin-position row col positions)
   (append positions (list (make-position row col))))

A queen is safe if no other queen is in the same row, column, or diagonal. Since we're only placing one queen in each column at a time, we can skip checking the column.

(define (safe? col positions)
   (let ((kth-queen (list-ref positions (- col 1)))
         (other-queens (filter (lambda (q)
                                 (not (= col (position-col q))))
                               positions)))
   (define (attacks? q1 q2)
     (or (= (position-row q1) (position-row q2))
         (= (abs (- (position-row q1) (position-row q2)))
            (abs (- (position-col q1) (position-col q2))))))

   (define (iter q board)
     (or (null? board)
         (and (not (attacks? q (car board)))
              (iter q (cdr board)))))
   (iter kth-queen other-queens)))

The safe? procedure starts be defining the symbols kth-queen and other-queens. We use the list-ref procedure introduced in SICP section 2.2.1 to separate the kth queen from the rest of the board. Next we define an attacks? procedure that takes two queens and returns true if they are in the same row or on the same diagonal. Then we define an iterative helper procedure to check and see if the kth queen attacks any of the others.

After adding in the definitions for accumulate, flatmap, and enumerate-interval given earlier in the text, we can finally test our implementation of queens.

> (queens 1)
(((1 . 1)))
> (queens 2)
()
> (queens 3)
()

So far, so good. There is only one solution to the puzzle for a 1x1 board, and no possible solutions for 2x2 and 3x3 boards.

> (queens 4)
(((2 . 1) (4 . 2) (1 . 3) (3 . 4)) ((3 . 1) (1 . 2) (4 . 3) (2 . 4)))

The two solutions given for a 4x4 board are illustrated below.

For the remaining tests, we'll just show how many distinct solutions queens comes up with instead of listing them all. You can check that the number of solutions matches those given in the Online Encyclopedia of Integer Sequences A000170.

> (length (queens 5))
10
> (length (queens 6))
4
> (length (queens 7))
40
> (length (queens 8))
92
> (length (queens 9))
352
> (length (queens 10))
724

Exercise 2.43 gives the following alternate implementation for a portion of the queens procedure above.

(flatmap
  (lambda (new-row)
    (map (lambda (rest-of-queens)
           (adjoin-position new-row k rest-of-queens))
         (queen-cols (- k 1))))
  (enumerate-interval 1 board-size))

This new implementation works, but it runs extremely slowly because the order of nested mappings in flatmap has been swapped. Our task is to explain why this interchange makes the program run slowly, and to estimate how long it will take the new implementation to solve the eight queens puzzle assuming that the original implementation solved the puzzle in time T.

In the original solution, queen-cols is called once for each column in the board. This is an expensive procedure to call, since it generates the sequence of all possible ways to place k queens in k columns. By moving queen-cols so it gets called by flatmap, we're transforming a linear recursive process to a tree-recursive process. The flatmap procedure is called for each row of the kth column, so the new procedure is generating all the possible solutions for the first k - 1 columns for each one of these rows.

We learned back in section 1.2.2 that a tree-recursive process grows exponentially. If it takes time T to execute the original version of queens for a given board size, we can expect the new version to take roughly T^board-size time to execute.

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.40 & 2.41: Nested Mappings

2011-05-30T11:01:00.002-04:00

From SICP section 2.2.3 Sequences as Conventional Interfaces

The next sub-section of SICP shows us how we can express nested loops using sequence operations. The first example given is the following problem:

Given a positive integer n, find all ordered pairs of distinct positive integers i and j, where 1 <= j < i <= n, such that (i + j) is prime.

In pseudocode, a solution using nested loops would be:

for i = 1 to n:
   for j = 1 to (i - 1):
       if isPrime( i + j ):
           print i, j, i + j

For n = 6, the output of the program above would be:

2, 1, 3
3, 2, 5
4, 1, 5
4, 3, 7
5, 2, 7
6, 1, 7
6, 5, 11

One way of looking at this is that the two nested loops generate a sequence of pairs, and the if statement applies a filter to each pair in the sequence.

In Scheme we can produce a sequence of pairs using nested mappings.

(accumulate append
           null
           (map (lambda (i)
                  (map (lambda (j) (list i j))
                       (enumerate-interval 1 (- i 1))))
                (enumerate-interval 1 n)))

The flatmap procedure is defined to abstract the portion of the code above that accumulates with append.

(define (flatmap proc seq)
   (accumulate append null (map proc seq)))

Procedures are then defined to filter out prime sums and to create the pair sum output from each pair in the sequence.

(define (prime-sum? pair)
   (prime? (+ (car pair) (cadr pair))))

(define (make-pair-sum pair)
   (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))

Combining all of these steps with the filter and enumerate-interval procedures from earlier in SICP section 2.2.3, we get the complete procedure.

(define (prime-sum-pairs n)
   (map make-pair-sum
        (filter prime-sum?
                (flatmap
                 (lambda (i)
                   (map (lambda (j) (list i j))
                        (enumerate-interval 1 (- i 1))))
                 (enumerate-interval 1 n)))))

Exercise 2.40 asks us to define a procedure unique-pairs that, given an integer n, generates the sequence of pairs (i j) with 1 <= j < i <= n. We are to use unique-pairs to simplify the definition of prime-sum-pairs given above.

Since we already have code embedded in prime-sum-pairs that generates the sequence of unique pairs that we need, this exercise basically amounts to an extract method refactoring of that piece of code.

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

The body of unique-pairs is a simple copy/paste from prime-sum-pairs. Replacing that portion of code in the original is just as easy.

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

We can test it with a known value to verify.

> (prime-sum-pairs 6)
((2 1 3) (3 2 5) (4 1 5) (4 3 7) (5 2 7) (6 1 7) (6 5 11))

Exercise 2.41 asks us to write a procedure to find all ordered triples of distinct positive integers i, j, and k less than or equal to a given integer n that sum to a given integer s.

If we were solving this using loops, we'd just nest our loops three deep. This exercise teaches us that nested mappings can be extended the same way. Let's start by creating a procedure that just finds ordered triples of distinct positive integers. We'll base it on unique-pairs from the previous exercise.

(define (ordered-triples n)
   (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)))

> (ordered-triples 5)
((3 2 1)
(4 2 1)
(4 3 1)
(4 3 2)
(5 2 1)
(5 3 1)
(5 3 2)
(5 4 1)
(5 4 2)
(5 4 3))

Next we can create a filtering procedure that checks to see if a triple sums to a given integer.

(define (triple-sum? triple s)
   (= s (accumulate + 0 triple)))

> (triple-sum? (list 1 2 3) 5)
#f
> (triple-sum? (list 1 2 3) 6)
#t

We also need a procedure to append the sum of the elements of a triple to the end of the triple so it's included in the output.

(define (make-triple-sum triple)
   (append triple (list (accumulate + 0 triple))))

> (make-triple-sum (list 1 2 3))
(1 2 3 6)

Finally, we can put it all together. Since filter takes only two arguments, a predicate and a sequence, we need to embed our predicate procedure triple-sum? in the final solution so that it can have access to the target sum variable s.

(define (ordered-triple-sum n s)
   (define (triple-sum? triple)
     (= s (accumulate + 0 triple)))
   (map make-triple-sum
        (filter triple-sum?
                (ordered-triples n))))

> (ordered-triple-sum 5 10)
((5 3 2 10) (5 4 1 10))
> (ordered-triple-sum 10 5)
()
> (ordered-triple-sum 10 6)
((3 2 1 6))
> (ordered-triple-sum 12 12)
((5 4 3 12)
(6 4 2 12)
(6 5 1 12)
(7 3 2 12)
(7 4 1 12)
(8 3 1 12)
(9 2 1 12))

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.38 & 2.39: Folding Left and Right

2011-04-30T16:29:00.004-04:00

From SICP section 2.2.3 Sequences as Conventional Interfaces

Exercise 2.38 informs us that another name for the accumulate procedure we've been using is fold-right, because it combines the elements of a sequence starting on the left and moving to the right. There's also a fold-left procedure that combines elements working in the opposite direction.

; fold-right is another name for accumulate
(define (fold-right op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (fold-right op initial (cdr sequence)))))

; fold-left is given in exercise 2.38
(define (fold-left op initial sequence)
   (define (iter result rest)
     (if (null? rest)
         result
         (iter (op result (car rest))
               (cdr rest))))
   (iter initial sequence))

We're given a few expressions that illustrate how these two procedures behave differently.

> (fold-right / 1 (list 1 2 3))
1 1/2
> (fold-left / 1 (list 1 2 3))
1/6
> (fold-right list null (list 1 2 3))
(1 (2 (3 ())))
> (fold-left list null (list 1 2 3))
(((() 1) 2) 3)

We're asked what property the op parameter needs to satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.

The property that will guarantee that fold-right and fold-left will produce the same values for any sequence is commutativity. You may remember the commutative property of both addition and multiplication from algebra. It's the law that says that:

A + B = B + A

and

A x B = B x A

Subtraction and division are not commutative operations. The AND and OR operations in Boolean algebra are commutative.

Exercise 2.39 asks us to complete the following definitions of reverse (from exercise 2.18) in terms of fold-right and fold-left:

(define (reverse sequence)
   (fold-right (lambda (x y) <??>) null sequence))

(define (reverse sequence)
   (fold-left (lambda (x y) <??>) null sequence))

Since we only need to define the operator used in each implementation, the key to this exercise lies in how the operator is applied in each folding procedure. Pay close attention to the order of the arguments of the op procedure.

In fold-right the operator is applied to the car of the sequence and the result of a recursive call to fold-right. Just as we did in exercise 2.18, we can reverse the sequence using fold-right by appending the car of the sequence to the reverse of its cdr.

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

In fold-left the operator is applied to the result sequence and the car of the unused elements in the initial sequence. Since the result sequence starts with an initial value of null, and we're starting at the end of the sequence and working backwards anyway, we can just cons each element to the end of the result.

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

As expected, we get the same test results for either of the two reverse implementations above.

> (reverse (list 1 2 3 4))
(4 3 2 1)
> (reverse (list 1 4 9 16 25))
(25 16 9 4 1)
> (reverse (list 1 3 5 7))
(7 5 3 1)
> (reverse (list 23 72 149 34))
(34 149 72 23)

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.36 & 2.37: Matrix Algebra

2011-04-24T14:56:00.006-04:00

From SICP section 2.2.3 Sequences as Conventional Interfaces

Exercise 2.36 asks us to complete the accumulate-n procedure, which is similar to accumulate except that it takes as its third argument a sequence of sequences that are assumed to all have the same length. It applies the accumulation procedure to all the first elements of the sub-sequences, all the second elements, third elements, and so on and returns a sequence of the results. For example, given the sequence s containing the following values, ((1 2 3) (4 5 6) (7 8 9) (10 11 12)), the value of (accumulate-n + 0 s) should return the sequence (22 26 30).

Our task is to fill in the missing expressions in the following definition:

(define (accumulate-n op init seqs)
   (if (null? (car seqs))
       null
       (cons (accumulate op init <??>)
             (accumulate-n op init <??>))))

If you've been doing all the exercises up to this point, then this procedure's overall structure of recursively building up a sequence with cons will be familiar.

In exercise 2.35 we used map and a simple lambda expression to flatten out a tree so the result could be used as the third parameter to accumulate. We can do something very similar here to fill in the missing expressions above. We'll still use map to loop over each of the sub-sequences, but in this case we need map to return a sequence that contains the first element from each sub-sequence (in the first missing expression) and the remaining elements of each sub-sequence (in the second missing expression). We already know two procedures that meet those needs, car and cdr.

; accumulate from sicp section 2.2.3
(define (accumulate op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (accumulate op initial (cdr sequence)))))

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

The first call to map returns a sequence containing the first element of each of the original sub-sequences. The second call to map returns the sequence of sub-sequences with each of their first elements removed. This continues recursively until no more elements remain. We can test the solution with the values given in the exercise.

> (define s (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 10 11 12)))
> s
((1 2 3) (4 5 6) (7 8 9) (10 11 12))
> (accumulate-n + 0 s)
(22 26 30)

Exercise 2.37 introduces a representation for vectors and matrices. A vector can be represented as a sequence of numbers, and a matrix as a sequence of vectors. For example, the matrix

can be represented as the sequence ((1 2 3 4) (4 5 6 6) (6 7 8 9)).

We can use this representation to express the basic operations of matrix algebra in terms of sequence operations. These basic operations are:

(dot-product v w) - returns the sum Σ_i(v_iw_i)

(matrix-*-vector m v) - returns the vector t, where t_i = Σ_j(m_ijv_j)

(matrix-*-matrix m n) - returns the matrix p, where p_ij = Σ_k(m_ikn_kj)

(transpose mat) - returns the matrix n, where n_ij = m_ji

Dot product

The dot product is defined for us.

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

The dot-product procedure takes two vectors (that are assumed to be equal length) and returns a single number obtained by multiplying corresponding elements and then summing those products.

Note that the use of map in this procedure takes more arguments than we've seen up to this point. That's because map takes a procedure of n arguments, together with n lists, and applies the procedure to all the first elements of the lists, all the second elements of the lists, and so on, returning a list of the results. Up to this point, we've been using map where n = 1.

Our task is to fill in the missing expressions in the given procedures for computing the remaining matrix operations. Let's take them one at a time.

Multiply a matrix by a vector

(define (matrix-*-vector m v)
   (map <??> m))

When multiplying a matrix by a vector, each row of the matrix is multiplied by the vector (using the dot product procedure described above). The result is a vector containing each dot product. Since map will pass each row of the matrix to whatever function we provide, we can just define a lambda expression that uses the dot-product procedure already defined.

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

Transpose a matrix

(define (transpose mat)
   (accumulate-n <??> <??> mat))

There are several ways of looking at matrix transposition, but the one that makes the most sense given the code above is to write the columns of the input matrix as the rows of the output matrix. Remember that accumulate-n will combine the columns with whatever function we give it, and this part of the exercise is a snap.

(define (transpose mat)
   (accumulate-n cons null mat))

We can test this procedure with the matrix s defined in the exercise above.

> (define s (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 10 11 12)))
> (transpose s)
((1 4 7 10) (2 5 8 11) (3 6 9 12))

Multiply two matrices

(define (matrix-*-matrix m n)
   (let ((cols (transpose n)))
      (map <??> m)))

When multiplying two matrices m and n, the resulting matrix will have the same number of rows as m and the same number of columns as n. Each element of the result matrix can be found by taking the dot product of each row of m and each column of n.

When viewed this way, it's easy to see that each row the resulting matrix is the product of a row in the first input matrix (m) and the entire second input matrix (n). Using this knowledge, we can define multiplication of two matrices in terms of matrix-*-vector.

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

Testing

We have to remember a few rules of matrix algebra that aren't enforced in the procedures we've defined.

For dot-product, two vectors can only be multiplied if they're the same length.
For matrix-*-vector, the vector must be the same length as the number of columns in the matrix.
For matrix-*-matrix, two matrices A and B can be multiplied only if the number of columns of A matches the number of rows of B.

> (define v (list 1 3 -5))
> (define w (list 4 -2 -1))
> (dot-product v w)
3
> (define m (list (list 1 2 3) (list 4 5 6)))
> (define v (list 1 2 3))
> (matrix-*-vector m v)
(14 32)
> (define a (list (list 14 9 3) (list 2 11 15) (list 0 12 17) (list 5 2 3)))
> (define b (list (list 12 25) (list 9 10) (list 8 5)))
> (matrix-*-matrix a b)
((273 455) (243 235) (244 205) (102 160))

Note that the values above are the same as those used as as examples on pages I linked to explaining each operation. The results above are correct, but you can do a Google search for "matrix multiplication calculator" to find several online calculators if you want to test with other values.

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.35: Counting the Leaves of a Tree

2011-04-09T17:37:00.003-04:00

From SICP section 2.2.3 Sequences as Conventional Interfaces

Exercise 2.35 asks us to redefine the count-leaves procedure from section 2.2.2 as an accumulation. Our procedure should take the following form:

(define (count-leaves t)
   (accumulate <??> <??> (map <??> <??>)))

When I encounter a problem like this (implement X in terms of Y), I find that it helps to take a look at both procedures side-by-side to see what they have in common. The count-leaves procedure just returns 1 when it encounters each leaf node, and recursively combines all those 1s with addition otherwise.

; count-leaves from sicp section 2.2.2
(define (count-leaves x)
   (cond ((null? x) 0)
         ((not (pair? x)) 1)
         (else (+ (count-leaves (car x))
                  (count-leaves (cdr x))))))

The accumulate procedure takes an operator, and initial value, and a sequence as its parameters. It then combines all elements of the sequence with the initial value using the operator.

; accumulate from sicp section 2.2.3
(define (accumulate op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (accumulate op initial (cdr sequence)))))

The operator and initial value in the case of count-leaves are pretty easy to guess. They should be + and 0 respectively. For its third argument accumulate is expecting a sequence, and our template is using map. Recall that map takes a function and a list and returns a new list. The new list is simply the result of the function being applied to each element of the old list. What we'd really like to accumulate is a sequence of 1s, one for each leaf in the tree. To implement that we need the help of one more procedure from SICP section 2.2.3.

; enumerate-tree from sicp 2.2.3
(define (enumerate-tree tree)
   (cond ((null? tree) null)
         ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                       (enumerate-tree (cdr tree))))))

The enumerate-tree procedure "flattens out" a tree into a sequence of its leaves. Once we have the tree in the form of a sequence, we just need to define a function for the first argument of map. This function should simply return a 1 for any input. Here's the complete (but very short) solution.

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

Test it out with trees of different shapes, just to be sure there are no corner cases missed.

&gt; (count-leaves (list))
0
&gt; (count-leaves (list 1 2 3))
3
&gt; (count-leaves (list 1 (list 1 2 3)))
4
&gt; (count-leaves (list (list 1 2) (list 1 2 3) 1))
6

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.34: Horner's rule

2011-04-03T17:37:00.003-04:00

From SICP section 2.2.3 Sequences as Conventional Interfaces

Exercise 2.34 introduces Horner's rule, an algorithm for the efficient evaluation of polynomial expressions at a given value of x. Horner's rule evaluates a polynomial expression using the fewest possible number of additions and multiplications.

Let's take a look at a specific example to see how this works.

4x³ + 3x² + 2x + 1

The terms of the polynomial above can be grouped as follows

(4x³ + 3x² + 2x) + 1

Once that grouping is in place it's easier to see that you can now factor out an x from the term in parentheses.

x * (4x² + 3x + 2) + 1

Now you can apply the same grouping and factoring steps to the term left in parentheses.

x * (x * (4x + 3) + 2) + 1

This is as far as we can go because another x cannot be factored out of the term in the innermost parentheses.

More generally, Horner's rule says that the polynomial

a_nxⁿ + a_n-1x^n-1 + ... + a₀

can be evaluated as

((a_nx + a_n-1)x + ...)x + a₀

This reduces the total number of multiplications performed because the exponents in each term of the original polynomial are not computed separately.

Using Horner's rule, evaluating polynomials can be formulated as an accumulation. Our task in this exercise is to complete the following implementation, assuming that the coefficients of the polynomial are arranged in a sequence from a₀ through a_n.

(define (horner-eval x coefficient-sequence)
   (accumulate (lambda (this-coeff higher-terms) <??>)
               0
               coefficient-sequence))

Given the framework and assumption above, there really are not a lot of different ways to go about this. The accumulate procedure is already doing most of the work for us, recursively accumulating the terms of the polynomial in the order that they're (conveniently) provided. All we have to do is implement the operator function that gets passed to accumulate.

The piece that we need to implement is summarized in the text as follows:

In other words, we start with a_n, multiply by x, add a_n-1, multiply by x, and so on, until we reach a₀.

In our lambda, a₀ through a_n are represented by this-coeff, so all we need to do is add this-coeff to the accumulation and multiply by x.

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

Here also is the implementation of accumulate so you can test the horner-eval procedure.

(define (accumulate op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (accumulate op initial (cdr sequence)))))

Let's start with a simpler test case than the one provided in the text and add terms so we can more easily predict what the correct output should be. The first example below is evaluating the polynomial (1 + 3x) where x = 2, and the final example is evaluating (1 + 3x + 5x³ + x⁵), also at x = 2.

&gt; (horner-eval 2 (list 1 3))
7
&gt; (horner-eval 2 (list 1 3 0))
7
&gt; (horner-eval 2 (list 1 3 0 5))
47
&gt; (horner-eval 2 (list 1 3 0 5 0))
47
&gt; (horner-eval 2 (list 1 3 0 5 0 1))
79

Related:

For an interesting application of Horner's rule, see the solution to Look And Say, Revisited from Programming Praxis.

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.33: List-manipulation operations as accumulations

2011-03-20T18:49:00.002-04:00

From SICP section 2.2.3 Sequences as Conventional Interfaces

Section 2.2.3 of SICP introduces the accumulate procedure, which combines elements of a list given an initial value and an operation to combine them with.

(define (accumulate op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (accumulate op initial (cdr sequence)))))

> (accumulate + 0 (list 1 2 3 4 5))
15
> (accumulate * 1 (list 1 2 3 4 5))
120

Exercise 2.33 asks us to fill in the missing expressions in the following procedure definitions to implement some basic list-manipulation operations as accumulations.

map

(define (map p sequence)
   (accumulate (lambda (x y) <??>) nil sequence))

The map procedure should accept a procedure and a list as arguments, and it should apply the procedure to each element of that list. We can finish the lambda above by making it apply the procedure p to x, then cons that result to the accumulated sequence.

(define (map p sequence)
   (accumulate (lambda (x y) (cons (p x) y)) null sequence))

Let's also define a couple of simple procedures to test with.

(define (double x)
   (* 2 x))
(define (square x)
   (* x x))

> (map double (list 1 2 3 4 5))
(2 4 6 8 10)
> (map square (list 1 2 3 4 5))
(1 4 9 16 25)

append

(define (append seq1 seq2)
   (accumulate cons <??> <??>))

The append procedure accepts two lists as its parameters and simply appends the second list to the end of the first. My first attempt at this solution was to simply pass the two sequences to accumulate in their original order, but this gives us the wrong output.

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

> (append (list 1 2 3) (list 4 5 6))
(4 5 6 1 2 3)

This is because of the way the accumulate procedure works. Each element of seq2 is being recursively appended to the front of seq1. All we need to do to fix this problem is reverse the order in which the lists are passed to accumulate.

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

> (append (list 1 2 3) (list 4 5 6))
(1 2 3 4 5 6)

length

(define (length sequence)
   (accumulate <??> 0 sequence))

This seems like it should be the easiest one of the bunch. The length procedure should simply return the length of the initial sequence. But accumulate combines each element of a sequence using the operation we pass to it. How do we get it to just return the length of the sequence? We can do that by simply giving it an operation that will ignore each element of the sequence, and just increment the accumulated value.

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

> (length (list 2 4 6))
3
> (length (list 9 8 7 6 5))
5

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.32: Generating Power Sets

2011-03-06T12:41:00.005-05:00

From SICP section 2.2.2 Hierarchical Structures

Exercise 2.32 introduces the concept of the "set of all subsets" of a given set, which you may recognize from mathematics as the power set. If we have the set S = {x, y, z}, then the power set of S is:

P(S) = { {}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z} }

There are a couple of details to note:

The empty set {} is a member of every power set.
The original set {x, y, z} is also a member of its own power set.

In Scheme we can represent a set as a list of distinct elements, and the power set as a list of sets. In this exercise, we're given the following definition of a procedure that generates the power set of a set, and asked to complete it:

(define (subsets s)
   (if (null? s)
       (list nil)
       (let ((rest (subsets (cdr s))))
          (append rest (map <??> rest)))))

If we're given the set (1 2 3), then the finished procedure should return:

(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

If you read the Wikipedia Power set article that I linked to earlier, you'll see that there's a recursive algorithm for calculating power sets (which I'll now quote liberally).

The first step is to define the following operation:

This function takes an element e and a set T, and returns a set with the element e added to each set X in T.

The procedure for generating the power set follows:

If S = {}, the P(S) = {{}} (the set contaning only the empty set) is returned.

Otherwise:

Let e be any single element of S.
Let T be the relative complement of {e} in S.

In other words, the power set of the empty set is the set containing the empty set and the power set of any other set is all the subsets of the set containing some specific element and all the subsets of the set not containing that specific element.

This is exactly the same procedure defined in the text. The only part we have to do is finish the initial operation:

The append and map procedures are already doing much of the work for us. We just need to define a function that will add an element e to the set X. The map procedure will apply whatever function we give it to each set in rest (T in the mathematical definition above). We can define that using lambda as follows.

(define (subsets s)
   (if (null? s)
       (list null)
       (let ((rest (subsets (cdr s))))
          (append rest (map (lambda (x) (cons (car s) x))
                            rest)))))

Here we're recursively calling subsets with (cdr s), which will append to that the car of s (which represents e from the mathematical definition) to each subset of (cdr s). The recursion stops when we run out of elements and the empty set is returned.

We can test it out with the example given.

> (subsets (list 1 2 3))
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.