SICP « Dan's Thoughts

7Aug/090

Exercise 2.22 of SICP

Exercise 2.22: Louis Reasoner tries to rewrite the first square-list procedure of exercise 2.21 so that it evolves an iterative process:

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things) 
              (cons (square (car things))
                    answer))))
  (iter items nil))

Unfortunately, defining square-list this way produces the answer list in the reverse order of the one desired. Why?

The reason the above works in reverse is because cons step of iter, cons puts new elements to the left of list answer.
(list 1 2 3) end up as (list 1), (list 2 1) and finally (list 3 2 1).

Louis then tries to fix his bug by interchanging the arguments to cons:

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square (car things))))))
  (iter items nil))

This doesn't work either. Explain.

Because (square (car things)) is not a list, cons creates a dotted pair out of answer which is an empty list and a number.
The result looks like this:
> (square-list (list 1 2 3 4))
((((() . 1) . 4) . 9) . 16)

Filed under: lisp, SICP No Comments

6Aug/090

Exercise 2.21 of SICP

Exercise 2.21: The procedure square-list takes a list of numbers as argument and returns a list of the squares of those numbers.

(square-list (list 1 2 3 4))
(1 4 9 16)

Here are two different definitions of square-list. Complete both of them by filling in the missing expressions:

(define (square-list items)
  (if (null? items)
      nil
      (cons <??> <??>)))
(define (square-list items)
  (map <??> <??>))

(define (square-list items)
  (if (null? items)
    '()
    (cons 
      ((lambda (x) (* x x))
       (car items))
      (square-list (cdr items)))))
 
(define (square-list2 items)
  (map (lambda (x) (* x x)) items))

> (square-list (list 1 2 3 4 5))
(1 4 9 16 25)
> (square-list2 (list 1 2 3 4 5))
(1 4 9 16 25)

Filed under: lisp, SICP No Comments

5Aug/090

Exercise 2.20 of SICP

Exercise 2.20: The procedures +, *, and list take arbitrary numbers of arguments. One way to define such procedures is to use define with dotted-tail notation. In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter's value will be a list of any remaining arguments. For instance, given the definition

(define (f x y . z) )

the procedure f can be called with two or more arguments. If we evaluate

(f 1 2 3 4 5 6)

then in the body of f, x will be 1, y will be 2, and z will be the list (3 4 5 6). Given the definition

(define (g . w) )

the procedure g can be called with zero or more arguments. If we evaluate

(g 1 2 3 4 5 6)

then in the body of g, w will be the list (1 2 3 4 5 6).11

Use this notation to write a procedure same-parity that takes one or more integers and returns a list of all the arguments that have the same even-odd parity as the first argument. For example,

(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)

(same-parity 2 3 4 5 6 7)
(2 4 6)

(define (same-parity a . rest)
  (define (filter rest)
    (cond ((null? rest) '())
          ((= (remainder a 2) (remainder (car rest) 2))
           (cons (car rest) (filter (cdr rest))))
          (else
            (filter (cdr rest)))))
  (filter (cons a rest)))

> (same-parity 2 3 4 5 6 7)
(2 4 6)
> (same-parity 1 2 3 4 5 6 7)
(1 3 5 7)

Filed under: lisp, SICP No Comments

4Aug/090

Exercise 2.19 of SICP

Exercise 2.19: Consider the change-counting program of section 1.2.2. It would be nice to be able to easily change the currency used by the program, so that we could compute the number of ways to change a British pound, for example. As the program is written, the knowledge of the currency is distributed partly into the procedure first-denomination and partly into the procedure count-change (which knows that there are five kinds of U.S. coins). It would be nicer to be able to supply a list of coins to be used for making change.

We want to rewrite the procedure cc so that its second argument is a list of the values of the coins to use rather than an integer specifying which coins to use. We could then have lists that defined each kind of currency:

(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

We could then call cc as follows:

(cc 100 us-coins)
292

To do this will require changing the program cc somewhat. It will still have the same form, but it will access its second argument differently, as follows:

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (&lt; amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

Define the procedures first-denomination, except-first-denomination, and no-more? in terms of primitive operations on list structures. Does the order of the list coin-values affect the answer produced by cc? Why or why not?

I wanted to use lexical scope so the whole program is bellow:

(define (cc amount coin-values)
  (define (no-more? coin-values)
    (null? coin-values))
  (define (first-denomination coin-values)
    (car coin-values))
  (define (except-first-denomination coin-values)
    (cdr coin-values))
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))
(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

> (cc 100 us-coins)
292
> (cc 100 uk-coins)
104561
> (cc 100 (list 50 5 25 1 10))
292
> (cc 100 (list 50 2 10 5 100 1 0.5 20))
104561

The order is irrelevant as long as all the coin values are in the list. This is true by looking and what the two recursion branches do:

Branch 1:

(cc amount (except-first-denomination coin-values))

will always bottom out. As the matter of fact, this branch doesn't even care if coin-values are numbers let alone what order they are in! As long as the (length coin-values) is the right number (in the case of us-coins that number is 5) it will execute without complaining.

Branch 2:

(cc (- amount (first-denomination coin-values)) coin-values)

this branch will subtract every term in coin-values until the amount less that or equal to 0 or coin-values is empty. The reason order is irrelevant is because coupled with the first branch, this second branch makes sure that all sublists of coin-values is evaluated.

While the order doesn't matter in the final result of computation it does matter in the "shape" of the computational process.
For instance (cc 51 (list 1 50)) has twice the amount of nodes as (cc 51 (list 50 1))

Filed under: lisp, SICP No Comments

3Aug/090

Exercise 2.18 of SICP

Exercise 2.18: Define a procedure reverse that takes a list as argument and returns a list of the same elements in reverse order:

(reverse (list 1 4 9 16 25))
(25 16 9 4 1)

(define (reverse-rec ls)
  (if (null? ls) 
    '()
    (append (reverse-rec (cdr ls)) (list (car ls)))))

(define (reverse ls)
  (define (reverse-iter ol nl)
    (if (null? ol)
      nl
      (reverse-iter (cdr ol) (cons (car ol) nl))))
  (reverse-iter ls '()))

> (reverse-rec (list 1 2 3 4))
(4 3 2 1)
> (reverse (list 1 2 3 4))
(4 3 2 1)

Filed under: lisp, SICP No Comments

2Aug/090

Exercise 2.17 of SICP

Exercise 2.17: Define a procedure last-pair that returns the list that contains only the last element of a given (nonempty) list:

(last-pair (list 23 72 149 34))
(34)

(define (last-pair ls)
  (let ((last-pair-index (- (length ls) 1)))
    (list-ref ls last-pair-index)))

> (last-pair (list 1 2 3 4 5))
5

Filed under: lisp, SICP No Comments

1Aug/090

Exercise 2.16 of SICP

Exercise 2.16: Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible? (Warning: This problem is very difficult.)

The errors are a lot tighter for par2 than par1. The reason that this is true is due to the fact that any operation between two intervals will increase errors. If two algebraically equivalent statements are evaluated, the statement with the least operations between intervals will produce less errors.

Here's a slightly exaggerated example:
$A = 10 \pm 0.1$
$A = \frac{A^7}{A^6} = \frac{A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A}{A \cdot A \cdot A \cdot A \cdot A \cdot A}$

> (define A (make-center-percent 10 1))
> (print A)
[10.,.9999999999999963]
> (print (div-interval (interval-pow A 7) (interval-pow A 6)))
[10.084120477031101,12.92768447766068]

The most noticeable difference is between percent errors of 1% and 13%. Even though the fraction is algebraically equivalent to A evaluating the intervals gives very different answers.

(define (interval-pow x n)
  (define (square i)
    (mul-interval i i))
  (cond ((= n 1) x)
        ((= 0 (remainder n 2)) (square (interval-pow x (/ n 2))))
        ((= 1 (remainder n 2)) (mul-interval x (interval-pow x (- n 1))))))

In order to devise a system that doesn't have this problem would mean it would have to be smart enough to detect duplicate entries and rewrite them in a more interval arithmetic efficient manner. At a minimum it would have to analyze code of this form:

(div-interval (interval-pow A 7) (interval-pow A 6))

and reduce it to A and than evaluate it.

Transforming the resistor example is even tougher.

(define (par1 r1 r2)
  (div-interval (mul-interval r1 r2)
                (add-interval r1 r2)))
(define (par2 r1 r2)
  (let ((one (make-interval 1 1)))
    (div-interval one
                  (add-interval (div-interval one r1)
                                (div-interval one r2)))))

The program would have to recognize division and simplify it by dividing the numerator and denominator by r1 and r2. Both the exponent and parallel resistor examples would have to be transformed symbolically since simplifying arithmetically would only introduce errors. I do not think it is feasible to write a program like this with the current lisp knowledge learned in the book so far.

Filed under: lisp, math, SICP No Comments

31Jul/090

Exercise 2.15 of SICP

Exercise 2.15: Eva Lu Ator, another user, has also noticed the different intervals computed by different but algebraically equivalent expressions. She says that a formula to compute with intervals using Alyssa's system will produce tighter error bounds if it can be written in such a form that no variable that represents an uncertain number is repeated. Thus, she says, par2 is a "better'' program for parallel resistances than par1. Is she right? Why?

> (print (div-interval (make-center-percent 6.8 1) (make-center-percent 6.8 1)))
[1.0002000200020003,1.9998000199979908]
> (print (div-interval (make-center-percent 6.8 .1) (make-center-percent 6.8 .1)))
[1.000002000002,.19999980000021655]

> (print (div-interval (make-center-percent 6.8 .1) (make-center-percent 3.4 .1)))
[2.000004000004,.19999980000021655]
> (print (div-interval (make-center-percent 6.8 .1) (make-center-percent 1.7 .1)))
[4.000008000008,.19999980000021655]
> (print (div-interval (make-center-percent 6.8 .1) (make-center-percent 1.7 .01)))
[4.000000440000004,.1099999890000035]

> (print (par1 (make-center-percent 6.8 .1) (make-center-percent 1.7 .01)))
[1.3600022771855311,.19199981581619266]
> (print (par2 (make-center-percent 6.8 .1) (make-center-percent 1.7 .01)))
[1.3599998237438813,.028000014256019334]

> (print (par1 (make-center-percent 6.8 .1) (make-center-percent 6.8 .1)))
[3.4000136000136,.2999992000024115]
> (print (par2 (make-center-percent 6.8 .1) (make-center-percent 6.8 .1)))
[3.4000000000000004,.10000000000000857]

> (print (par1 (make-center-percent 6.8 10) (make-center-percent 4.7 5)))
[2.844199964577264,22.613352145193346]
> (print (par2 (make-center-percent 6.8 10) (make-center-percent 4.7 5)))
[2.777440701636504,7.05260392723452]

(define (par1 r1 r2)
  (div-interval (mul-interval r1 r2)
                (add-interval r1 r2)))
(define (par2 r1 r2)
  (let ((one (make-interval 1 1))) 
    (div-interval one
                  (add-interval (div-interval one r1)
                                (div-interval one r2)))))

Alyssa's system will produce tighter error bounds. The errors are a lot tighter for par2 than par1. The reason that this is true is due to the fact that any operation between two intervals will increase errors. If two algebraically equivalent statements are evaluated, the statement with the least operations between intervals will produce less errors.

Here's a slightly exaggerated example:
$A = 10 \pm 0.1$
$A = \frac{A^7}{A^6} = \frac{A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A}{A \cdot A \cdot A \cdot A \cdot A \cdot A}$

> (define A (make-center-percent 10 1))
> (print A)
[10.,.9999999999999963]
> (print (div-interval (interval-pow A 7) (interval-pow A 6)))
[10.084120477031101,12.92768447766068]

The most noticeable difference is between percent errors of 1% and 13%.

(define (interval-pow x n)
  (define (square i)
    (mul-interval i i))
  (cond ((= n 1) x)
        ((= 0 (remainder n 2)) (square (interval-pow x (/ n 2))))
        ((= 1 (remainder n 2)) (mul-interval x (interval-pow x (- n 1))))))

Filed under: lisp, math, SICP No Comments

30Jul/090

Exercise 2.14 of SICP

Exercise 2.14: Demonstrate that Lem is right. Investigate the behavior of the system on a variety of arithmetic expressions. Make some intervals A and B, and use them in computing the expressions A/A and A/B. You will get the most insight by using intervals whose width is a small percentage of the center value. Examine the results of the computation in center-percent form (see exercise 2.12).

(define (par1 r1 r2)
  (div-interval (mul-interval r1 r2)
                (add-interval r1 r2)))
(define (par2 r1 r2)
  (let ((one (make-interval 1 1))) 
    (div-interval one
                  (add-interval (div-interval one r1)
                                (div-interval one r2)))))
 
(define (make-center-percent value p)
  (make-center-width value (* (abs value) (/ p 100.0))))
(define (percent int)
  (abs (* 100 (/ (width int) (center int)))))
 
(define (make-interval a b) (cons a b))
(define (lower-bound int) (car int))
(define (upper-bound int) (cdr int))
(define (make-center-width c w)
  (make-interval (- c w) (+ c w)))
(define (center i)
  (/ (+ (lower-bound i) (upper-bound i)) 2))
(define (width i)
  (/ (- (upper-bound i) (lower-bound i)) 2))
 
(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))
 
(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))
 
(define (div-interval x y)
  (define (spans-zero? i)
    (and 
      (not (> (lower-bound i) 0)) 
      (not (< (upper-bound i) 0)))) 
  (if (spans-zero? y)
    (error "The dividing interval cannot span 0.")
    (mul-interval x 
                  (make-interval (/ 1.0 (upper-bound y))
                                 (/ 1.0 (lower-bound y))))))
 
(define (sub-interval2 x y)
  (let ((p1 (- (lower-bound x) (lower-bound y)))
        (p2 (- (lower-bound x) (upper-bound y)))
        (p3 (- (upper-bound x) (lower-bound y)))
        (p4 (- (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))
(define (sub-interval x y)
  (make-interval (- (lower-bound x) (upper-bound y))
                 (- (upper-bound x) (lower-bound y))))
 
(define (print int)
  (newline)
  (display "[")
  (display (center int))
  (display ",")
  (display (percent int))
  (display "]")
  (newline))

Filed under: lisp, SICP No Comments

29Jul/090

Exercise 2.13 of SICP

Exercise 2.13: Show that under the assumption of small percentage tolerances there is a simple formula for the approximate percentage tolerance of the product of two intervals in terms of the tolerances of the factors. You may simplify the problem by assuming that all numbers are positive.

$(a-\epsilon_1,a+\epsilon_1) \cdot (b-\epsilon_2,b+\epsilon_2)$
$(a+\epsilon_1)\cdot(b+\epsilon_2)=ab+a\epsilon_2+b\epsilon_1+\epsilon_1\epsilon_2$
$(a+\epsilon_1)\cdot(b-\epsilon_2)=ab-a\epsilon_2+b\epsilon_1-\epsilon_1\epsilon_2$
$(a-\epsilon_1)\cdot(b+\epsilon_2)=ab+a\epsilon_2-b\epsilon_1-\epsilon_1\epsilon_2$
$(a-\epsilon_1)\cdot(b-\epsilon_2)=ab-a\epsilon_2-b\epsilon_1+\epsilon_1\epsilon_2$

Since a>0 and b>0:
$(a+\epsilon_1)\cdot(b+\epsilon_2) \approx ab+ a\epsilon_2+b\epsilon_1+\epsilon_1\epsilon_2$
$(a-\epsilon_1)\cdot(b-\epsilon_2) \approx ab -a\epsilon_2-b\epsilon_1+\epsilon_1\epsilon_2$
Assuming $\epsilon_1$ and $\epsilon_2$ are small, the quantity $\epsilon_1\epsilon_2$ can be discarded.
$(a+\epsilon_1)\cdot(b+\epsilon_2) \approx ab+a\epsilon_2+b\epsilon_1$
$(a-\epsilon_1)\cdot(b-\epsilon_2) \approx ab-a\epsilon_2-b\epsilon_1$

Since we are interested in the tolerance terms:
$(a+\epsilon_1)\cdot(b+\epsilon_2) \approx a\epsilon_2+b\epsilon_1$
$(a-\epsilon_1)\cdot(b-\epsilon_2) \approx -a\epsilon_2-b\epsilon_1$