environment:

There are multiple List dialects. The one used in this book is Scheme:

sudo apt-get install mit-scheme

Then run “mit-scheme” in the shell.

I also installed Steel Bank Common Lisp:

sudo apt-get install sbcl

Then run “sbcl” in the shell.

in “mit-scheme”, if you type something by mistake, or the expression is invalid, We will enter “Error system”, like: 2 error>

To jump out of Error system, input (RESTART x) x is the option number

Chapter 1 Building Abstractions with Procedures

1. define variables

(define size 2)

2. define functions

(define (square x) (* x x))

3. condition expression

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

(define (abs x)
  (cond ((< x 0) (- x))
  	(else x)))

(define (abs x)
  (if (< x 0)
      (- x)
      x))

(define (>= x y)
  (or (> x y) (= x y)))
or alternative as
(define (>= x y)
  (not (< x y)))

4. Newton’s method to get square root

Whenever we have a guess y for the value of the square root of a number x, we can perform a simple manipulation to get a better guess by average y with x/y.

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
	guess
    	(sqrt-iter (improve guess x) x)
  ))

(define (improve guess x)
	(average guess (/ x guess)))

(define (average x y)
	(/ (+ x y) 2))

(define (good-enough? guess x)
	(< (abs (- (square guess) x)) 0.001)) 

(define (mysqrt x)
	(sqrt-iter 1.0 x))

5. Internal definitions and block structure

(define (sqrt x)
	(define (good-enough? guess)
		(< (abs (- (square guess) x)) 0.001))
	(define (improve guess)
		(average guess (/ x guess)))
	(define (sqrt-iter guess)
		(if (good-enough? guess)
			guess
			(sqrt-iter (improve guess))))
	(sqrt-iter 1.0))

It is not necessary to pass x explicitly to each of these procedures. Instead, we allow x to be a free variable in the internal definitions. This discipline is called lexical scoping.

6. Linear Recursion and Iteration

Linear Recursion:

(define (factorial n)
	(if (= n 1)
		1
		(* n (factorial (- n 1)))))

Linear Iterative:

(define (factorial n)
	(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
	(if (> count max-count)
		product
		(fact-iter (* counter product)
			(+ counter 1)
			max-count)))

Difference: bottom-up vs. top-down Linear iterative does not grow and shrink. At each step, all we need to keep track of, are the current value of the variables product, counter and max-count.

Scheme will execute an iterative process in constant space even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive.

7. How many different ways can we make change of $1.00

The number of ways to change amount a using n kinds of coins equals: The number of ways to change amount a using all but the first kind of coins, plus The number of ways to change amount a-d using all n kinds of coins, where d is the denomination of the first kind of coin

(define (count-change amount)
	(cc amount 5))
(define (cc amount kinds-of-coins)
	(cond ((= amount 0) 1)
	      ((or (< amount 0) (= kinds-of-coins 0)) 0)
	      (else (+ (cc amount (- kinds-of-coins 1))
	      		(cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins)))))  	
(define (first-denomination kinds-of-coins)
	(cond 	((= kinds-of-coins 1) 1)
		((= kinds-of-coins 2) 5)
		((= kinds-of-coins 3) 10)
		((= kinds-of-coins 4) 25)
		((= kinds-of-coins 5) 50)))

8. GCD and Fibonacci number

Lame’s Theorem: If Euclid’s Algorithm requires k steps to compute the GCD of some pair, then the smaller number in the pair must be greater than or equal to the kth Fibonacci number.

Let n be the smaller of the two inputs to the procedure. If the process takes k steps, then we must have $n\geq Fib(k) \approx \phi^{k}/\sqrt{5}$, Hence the order of growth is $\Theta(log n)$

$gcd(F\_m, F\_n)=F\_{gcd(m,n)}$ (Concrete Mathematics, 6.111)

9. the Fermat test

Fermat’s Little Theorem: If n is a prime number and a is any positive integer less than n, then a raised the nth power is congruent to a modulo n.

the Fermat test: If n is not prime, then, in general, most of the number a<n will not satisfy the above relation. This leads to the following algorithm for testing primality: Given a number n, pick a random number a<n and compute the remainder of a^n modulo n. If the result is not equal to a, then n is certainly not prime. If it is a, then chances are good that n is prime. Now pick another random number a and test it with the same method. If it also satisfies the equation, then we can be even more confident that n is prime. By trying more and more values of a, we can increase our confidence in the result.

(define (expmod base exp m)
	(cond ((= exp 0) 1)
	      ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m))
	      (else (remainder (* base (expmod base (- exp 1) m)) m)))) 

(define (fermat-test n)
	(define (try-it a)
		(= (expmod a n n) a))
	(try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
	(cond ((= times 0) true)
	      ((fermat-test n) (fast-prime? n (- times 1)))
	      (else false)))

Miller-Rabin primality test: if p is a prime, x is a positive integer less than p, and x^2 mod p=1, then x=1 or x=p-1.

10. Higher-order Procedure

Procedures that can accept procedures as arguments or return procedures as values are called high-order procedures

11. Procedures as Arguments

Consider the following 3 procedures. The first computes the sum of the integers from a through b

(define (sum-integers a b)
	(if (> a b)
	    0
	    (+ a (sum-integers (+ a 1) b))))

The second computes the sum of the cubes of the integers in the given range.

(define (sum-cubes a b)
	(if (> a b)
	    0
	    (+ (cube a) (sum-cubes (+ a 1) b))))

The third computes the sum of a sequence of terms in the series

1/(1*3) + 1/(5*7) + 1/(9*11) + …

which converges to pi/8 (very slowly):

(define (pi-sum a b)
	(if (> a b)
	    0
	    (+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))

We would like our language to be powerful enough so that we can write a procedure that express the concept of summation itself rather than only procedures that compute particular sums.

(define (sum term a next b)
	(if (> a b)
	    0
	    (+ (term a)
	       (sum term a (next a) next b))))

We can use it to define sum-cubes, sum-integers and pi-sum:

(define (inc n) (+ n 1))
(define (sum-cubes a b)
	(sum cube a inc b))

(define (identity x) x)
(define (sum-integers a b)
	(sum identity a inc b))

(define (pi-sum a b)
	(define (pi-term x)
		(/ 1.0 (* x (+ x 2))))
	(define (pi-next x)
		(+ x 4))
	(sum pi-term a pi-next b))

Once we have sum, we can use it as a building block in formulating further concept. For instance, the definition integeral of a function f between the limits a and b can be approximated numberically using the formula:

\int_a^b f(x) dx=[f(a+dx/2)+f(a+dx+dx/2)+f(a+2dx+dx)+\cdots]dx

(define (integeral f a b dx)
	(define (add-dx x) (+ x dx))
	(* (sum f (+ a (/ dx 2.0)) add-dx b)
	   dx))

(integral cube 0 1 0.01)
.2499875

12. Construct procedure using Lambda

(lambda (x) (+ x 4))

(lambda (x) (/ 1.0  (* x (+ x 2))))

(define (pi-sum a b)
	(sum (lambda (x) (/ 1.0 (* x (+ x 2))))
	     a
	     (lambda (x) (+ x 4))
	     b))

(define (plus4 x) (+ x 4))

is equivalent to

(define plus4 (lambda (x) (+ x 4)))

a lambda expression can be used as the operator in a combination such as

((lambda (x y z) (+ x y (square z))) 1 2 3)
12

13. Using let to create local variables

Suppose we wish to compute the function

f(r,y)=r(1+ry)^2+y(1-y)+(1+ry)(1-y)

which we could also express as

a=1+ry

b=1-y

f(r,y)=ra^2+yb+ab

Using let, the f procedure could be written as

(define (f x y)
	(let ((a (+ 1 (* x y)))
	      (b (- 1 y)))
	     (+ (* x (square a))
	        (* y b)
		(* a b))))

the scope of the variable specified by a let expression is the body of let

The variables’ values are computed outside the let. For example, if the value of x is 2, the expression

(let ((x 3)
      (y (+ x 2)))
     (* x y))

will have the value 12 because, inside the body of the let, x will be 3 and y will be 4 (which is the outer x plus 2)

14. Find roots of equations by the half-interval method

(define (search f neg-point pos-point)
  	(let ((midpoint (average neg-point pos-point)))
	     (if (close-enough? neg-point pos-point)
	         midpoint
		 (let ((test-value (f midpoint)))
		      (cond ((positive? test-value) (search f neg-point midpoint))
			    ((negative? test-value) (search f midpoint pos-point))
			    (else midpoint))))))

(define (close-enough? x y)
  	(< (abs (- x y)) 0.001))

(define (half-interval-method f a b)
  	(let ((a-value (f a))
	      (b-value (f b)))
	     (cond ((and (negative? a-value) (positive? b-value)) (search f a b))
		   ((and (negative? b-value) (positive? a-value)) (search f b a))
		   (else (error "Values are not of opposite sign" a b)))))

15. Find fixed points of functions

A number x is called fixed point of a function f if x satisfies the equation f(x)=x. For some functions f we can locate a fixed point by beginning with an initial guess and applying f repeatedly.

f(x), f(f(x)), f(f(f(x))), …

(define (fixed-point f first-guess)
  	(define (try guess)
	  	(let ((next (f guess)))
		     (if (close-enough? guess next)
		         next
			 (try next))))
	(try first-guess))

We can try to compute square root as

(define (sqrt x)
	(fixed-point (lambda (y) (/ x y))
	1.0))

Unfortunately, this fixed-point search does not converge. Consider an initial guess y1, the next guess y2=x/y1 and the next guess y3=x/y2=x/(x/y1)=y1

One way to control such oscillations is to prevent the guesses from changing so much. Since the answer is always between our guess y and x/y, we can make new guess that is not as far from y as x/y by averaging y with x/y, so that the next guess after y is (1/2)(y+x/y) instead of x/y

(define (sqrt x)
	(fixed-point (lambda (y) (average y (/ x y)))
	1.0))

16. Procedures as Returned Values

(define (average-damp f)
	(lambda (x) (average x (f x))))

((average-damp square) 10)
55

Using average-damp, we can reformulate the square-root procedure as follows:

(define (sqrt x)
	(fixed-point (average-damp (lambda (y) (/ x y)))
	1.0))

Notice that the cube root of x is a fixed point of the function f(y)=x/y^2, so we can generalize our square-root procedure:

(define (cube-root x)
	(fixed-point (average-damp (lambda (y) (/ x (square y))))
	1.0))

17. Newton’s method

If g(x) is a differentiable function, then a solution of the equation g(x)=0 is a fixed point of the function f(x) where

f(x)=x-g(x)/Dg(x)

Wiki page

derivative:

(define (deriv g)
	(lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))

With the aid of deriv, we can express Newton’s method as a fixed-point process:

(define (newton-transform g)
	(lambda (x) (- x (/ (g x) ((deriv g) x)))))

(define (newtons-method g guess)
	(fixed-point (newton-transform g) guess))

To find the square root of x, we can use Newton’s method to find a zero of the function f(y)=y^2-x starting with an initial guess of 1

(define (sqrt x)
	(newtons-method (lambda (y) (- (square y) x))
	1.0))

We’ve seen to ways to express the square-root computation as instance of a more general method. We can express this general idea idea itself as a procedure:

(define (fixed-point-of-transform g transform guess)
	(fixed-point (transform g) guess))

Using this abstraction, we can recast the first square-root computation as:

(define (sqrt x)
	(fixed-point-of-transform (lambda (y) (/ x y))
				  average-damp
				  1.0))

Similar, we can express the second square-root computation as:

(define (sqrt x)
	(fixed-point-of-transform (lambda (y) (- (square y)  x))
				  newton-transform
				  1.0))

Elements with the fewest restrictions are said to have first-class status. Some of the “rights and privileges” of first elements are:

They may be named by varialbes
They may be passed as arguments to procedures
They may be returned as the results of procedures
They may be included in data structures.

Lisp awards procedures full first-class status.

Exercise 1.1

ddd

false

Exercise 1.2

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 3))))) (* 3 (- 6 2) (- 2 7)))

Exercise 1.3

(define (f a b c)
	(define maxab (if (>= a b)
		      	a
			b)
	)
	(define minab (if (>= a b)
			b
			a)
	)
  
	(if (>= maxab c)
      		(if (>= c minab)
        		(+ (* maxab maxab) (* c c))
	  		(+ (* maxab maxab) (* minab minab))
      		)
      		(+ (* maxab maxab) (* c c))
  	)
)

Exercise 1.6

maximum recursion depth exceeded Since the else-clause is always executed in new-if.

Exercise 1.8

(define (mycbrt x)
  	(cbrt-iter 1.0 x))

(define (cbrt-iter guess x)
	(if (cb-good-enough? guess x)
	  	guess
		(cbrt-iter (cbimprove guess x) x)))

(define (cb-good-enough? guess x)
  	(< (abs (- (* (* guess guess) guess) x)) 0.001))

(define (cbimprove guess x)
  	(/ (+ (/ x (* guess guess)) (* 2 guess)) 3))

Exercise 1.10

1024

65536

(f n) = 2n

(g n) = 2^n

(h n) = 2^(2^(2^(…)))

Exercise 1.11

(define (f n)
  	(cond ((< n 3) n)
	      (else (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3)))))))

(define (f2 n)
  	(f-iter 2 1 0 2 n))
(define (f-iter a b c i count)
  	(cond ((< count 3) count)
		((= i count) a)
		(else (f-iter (+ a (* 2 b) (* 3 c)) a b (+ i 1) count))))

Exercise 1.12

(define (pascal row idx)
  	(cond ((or (<= row 0) (<= idx 0) (< row idx)) 0)
	      ((= idx 1) 1)
	      ((= row idx) 1)
	      (else (+ (pascal (- row 1) (- idx 1)) (pascal (- row 1) idx)))))

Exercise 1.13

define $\widehat{\phi}=(1-\sqrt{5})/2$, both $\phi$ and $\widehat{\phi}$ are the roots of the equation $x^2-x-1=0$, so we have ${\phi}^2={\phi}+1$; ${\widehat{\phi}}^2={\widehat{\phi}}+1$

Suppose $Fib(k)=({\phi}^{k}-{\widehat{\phi}}^{k})/{\sqrt{5}}$ for all the $k<n$, then,

\[Fib(n)=Fib(n-1)+Fib(n-2)\] \[Fib(n)=({\phi}^{n-1}-{\widehat{\phi}}^{n-1})/{\sqrt{5}}+({\phi}^{n-2}-{\widehat{\phi}}^{n-2})/{\sqrt{5}}\] \[Fib(n)=({\phi}^{k-2}({\phi}+1)-{\widehat{\phi}}^{k-2}({\widehat{\phi}}+1))/{\sqrt{5}}\] \[Fib(n)=({\phi}^{n}-{\widehat{\phi}}^{n})/{\sqrt{5}}\]

Exercise 1.14

\[F(m,n)=F(m,n-1)+F(m-f(n),n)\]

There are at most n levels in its recursion tree, so there are at most 2^n leaf nodes. Time complexity O(m*2^n) ??

Exercise 1.15

$(12.15/3^n)<0.1$, n=5

O(log(a)))

Exercise 1.16

(define (fast-expt b n)
  	(fast-expt-iter 1 b n))
(define (fast-expt-iter extra ret n)
  	(cond ((= n 1) (* extra ret))
	      ((= (remainder n 2) 0) (fast-expt-iter extra (* ret ret) (/ n 2)))
	      ((= (remainder n 2) 1) (fast-expt-iter (* extra ret) (* ret ret) (/ (- n 1) 2)))))

Exercise 1.17

(define (times a b)
  	(cond ((= b 0) 0)
	      ((= (remainder b 2) 0) (times (double a) (halve b)))
	      ((= (remainder b 2) 1) (+ a (times (double a) (halve (- b 1)))))))

Exercise 1.18

(define (times2 a b)
  	(times-iter 0 a b))
(define (times-iter ret a b)
  	(cond ((= b 0) ret)
	      ((even? b) (times-iter ret (double a) (halve b)))
	      (else (times-iter (+ ret a) a (- b 1)))))

Exercise 1.19

$a’=bq+aq+ap$, $b’=bp+aq$, $a’‘=b’q+a’q+a’p$, $b’‘=b’p+a’q$

so $a’‘=bq(q+2p)+aq(q+2p)+a(p^2+q^2)$, $b’‘=b(p^2+q^2)+aq(q+2p)$

so $p’=(p^2+q^2)$, $q’=q(q+2p)$

Exercise 1.21

199

1999

Exercise 1.22

(define (start-prime-test n start-time)
  	(if (prime? n)
	  	(report-prime n (- (runtime) start-time))
		0))

(define (report-prime n elapsed-time)
  	(newline)
  	(display n)
  	(display " *** ")
	(display elapsed-time)
	1)
(define (search-for-primes start count)
  	(if (< count 3)
	    (if (timed-prime-test start)
	      	(search-for-primes (+ start 1) (+ count 1))
		(search-for-primes (+ start 1) count))
	    0))

(wrong?)

Exercise 1.23

(define (next n)
  	(if (= n 2) 3
	    (+ n 2)))

(define (smallest-divisor2 n)
  	(find-divisor2 n 2))
(define (find-divisor2 n test-divisor)
  	(cond ((> (square test-divisor) n) n)
	      ((divides? test-divisor n) test-divisor)
	      (else (find-divisor2 n (next test-divisor)))))

Exercise 1.25

I think his solution is correct but slow. May cause overflow issue when base^exp is large

Exercise 1.26

The procedure expmod will be executed twice using explicit multiplication, rather than once using square

Exercise 1.28

(define (Miller-Rabin-test a n)
	(define (getOdd x)
	       	(if (odd? x)
		     	x
	     		(getOdd (/ x 2))))

	(define (check x y)
	  	(if (or (= x (- n 1)) (= y 1) (= y (- n 1)))
		    (or (= y (- n 1)) (odd? x))
		    (check (* x 2) (expmod y 2 n))))

	(define d (getOdd (- n 1)))
  	(if (= n 2)
	    1 
	    ((if (or (= n 1) (even? n))
	         0
		 ((check d (expmod a d n)))))))

Exercise 1.29

(define (Simpson f a b n)
	(define h (/ (- b a) n))
	(define (y k) (f (+ a (* k h)))) 
	(define (next x) (+ x 1))
	(define (term x)
		(cond ((or (= 0 x) (= n x)) (y x))
		      ((odd? x) (* 4 (y x)))
		      (else (* 2 (y x)))))
	(if (odd? n)
	    (display "n must be even")
	    (* (sum term 0 next n) (/ h 3))))

Exercise 1.30

(define (sum term a next b)
	(define (iter a result)
		(if (> a b)
		    result
		    (iter (next a) (+ (term a) result))))
	(iter a 0))

Exercise 1.31

(define (product term a next b)
	(if (> a b)
	    1
	    (* (term a) (product term (next a) next b)))) 

(define (factorial n)
	(define (term a) a)
	(define (next a) (+ a 1))
	(product term 1 next n)) 

(define (pi n)
	(define (term x)
		(if (odd? x)
		    (/ (+ 1 x) (+ 2 x))
		    (/ (+ 2 x) (+ 1 x))))
	(define (next x) (+ x 1))
	(* 4 (product term 1 next n)))

(define (product term a next b)
	(define (iter a result)
		(if (> a b)
		    result
		    (iter (next a) (* (term a) result))))
	(iter a 1))

Exercise 1.32

(define (accumulate combiner null-value term a next b)
	(if (> a b)
	    null-value
	    (combiner (term a) (accumulate combiner null-value term (next a) next b))))

(define (accumulate combiner null-value term a next b)
	(define (iter a result)
		(if (> a b)
		    result
		    (iter (next a) (combiner (term a) result))))
	(iter a null-value))

Exercise 1.33

(define (filterd-accumulate combiner null-value term a next b filter)
	(if (> a b)
	    null-value
	    (if (filter (term a))
	        (combiner (term a) (filterd-accumulate combiner null-value term (next a) next b))
		(combiner null-value (filterd-accumulate combiner null-value term (next a) next b)))))

(define (primeSquareSum a b)
	(define (term x) (* x x))
	(define (next x) (+ x 1))
	(filterd-accumulate + 0 term a next b prime?)) 

(define (relativelyPrimeProduct n)
	(define (term x) (x))
	(define (next x) (+ x 1))
	(define (relPrime? x) (= (gcd i n) 1))
	(filterd-accumulate * 1 term 2 next n relPrime?))

Exercise 1.34

There will be an error since 2 will be treated as a function

Exercise 1.35

\phi is the root of x=1+1/x

(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)

Exercise 1.36

(define (fixed-point f first-guess)
  	(define (try guess)
	  	(let ((next (f guess)))
		     (newline)
		     (display next)
		     (if (close-enough? guess next)
		         next
			 (try next))))
	(try first-guess))

(fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)

Exercise 1.37

(define (cont-frac n d k)
  	(define (f n d idx)
	  	(if (= idx k)
		    (/ (n idx) (d idx))
  		    (/ (n idx) (+ (d idx) (f n d (+ idx 1))))))
	(f n d 1))

Exercise 1.38

(define (d x)
	(if (or (= (remainder x 3) 1) (= (remainder x 3) 0))
	    1
	    (+ (* (floor (/ x 3)) 2) 2)))

(+ (cont-frac (lambda (x) 1.0) d 100) 2)

Exercise 1.39

(define (d x) (- (* x 2) 1))

(define (tan-cf x k)
	(define (n idx)
		(if (= idx 1)
		    x
		    (* x x)))
	(cont-frac n d k))

Exercise 1.40

(define (cubic a b c)
	(lambda (x) (+ (cube x) (* a (square x)) (* b x) c)))

Exercise 1.41

(define (double f)
	(lambda (x) (f (f x))))

Exercise 1.42

(define (compose f g) 
	(lambda (x) (f (g x))))

Exercise 1.43

(define (repeated f n)
  	(if (= n 1)
	    f
	    (compose f (repeated f (- n 1)))))

Exercise 1.44

(define (smooth f dx)
	(lambda (x)
		(/ (+ (f x) (f (- x dx)) (f (+ x dx))) 3)))

Exercise 1.46

(define (Iterative-improve good-enough? improve)
	(lambda (guess)
		(if (good-enough? guess)
		    guess
		    ((Iterative-improve good-enough? improve) (improve guess)))))

[Link] (http://wqzhang.wordpress.com/2009/06/16/sicp-exercise-1-46/)

Home

Tags

Structure and Interpretation of Computer Programs notes I