sicp-exercise-1.13

Exercise 1.13.

Using mathematical induction, it's not hard to prove:
Fib(n) = (phi^n - psi^n)/sqrt5

0). The base cases are easy:
Fib(0) = 0 = (phi^0 - psi^0) / sqrt5
Fib(1) = 1 = (phi^1 - psi^1) / sqrt5

1).. The induction step:
Assume for ALL k <= n, we have:
Fib(k)=(phi^k - psi^k)/sqrt5

So,
Fib(n+1)
= Fib(n) + Fib(n-1)
= (phi^n - psi^n)/sqrt5
+ (phi^(n-1) - psi^(n-1))/sqrt5
= phi^(n-1) * (phi+1)
- psi^(n-1) * (psi + 1)
= phi^(n-1) * phi^2
- psi^(n-1) * psi^2
(because phi+1=phi^2, and the same to psi)
= (phi^(n+1) - psi^(n+1))/sqrt5

====
Then having such a lemma, we have:

Fib(n) = (phi^n)/sqrt5 - something,

where the something = (psi^n)/sqrt5, but we know abs(psi) is smaller than 1,
which will become arbitrarily small when raised to n times (if n is big
enough). So Fib(n) is the closest integer to (phi^n)/sqrt5.(The logic seems not that good)

sicp-exercise-1.11-1.12

Exercise 1.11.

1). recursive one

(define (f-rec n)
(if (< n 4)
n
(+ (f-rec (- n 1))
(* 2 (f-rec (- n 2)))
(* 3 (f-rec (- n 3))))))

2). iterative one

a = (f 1)
b = (f 2)
c = (f 3)
Each update will get:
new a <== orig b
new b <== orig c
new c <== orig 3a+2b+c

(define (f-iter n)
(define (f-iter-iter a b c ix)
(if (= ix n)
a
(f-iter-iter b
c
(+ c (* 2 b) (* 3 a))
(+ ix 1))))
(f-iter-iter 1 2 3 1))

(f-rec 5)
(f-iter 5)


Exercise 1.12.

The counting of columns and rows all start from 1.

The elements on the shoulders of element(row,col) are:
(row-1,col-1) and (row-1,col)
(Only if (row, col) is not on the edge of Pascal's Triangle.)

(define (pascal-triangle row ix)
(cond ((= ix 1) 1)
((= ix row) 1)
(else (+ (pascal-triangle (- row 1) (- ix 1))
(pascal-triangle (- row 1) ix)))))

(pascal-triangle 4 3)
(pascal-triangle 1 1)
(pascal-triangle 5 2)

And I haven't taken illegal inputs into consideration.

sicp-exercise-1.10

Exercise-1.10

(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
(A 1 10) ;; 1024
(A 2 4) ;; 65536
(A 3 3) ;; 65536


(A 0 n)
2n


(A 1 n)
(A 0 (A 1 (- n 1)))
(A 0 (A 0 (A 1 (- n 2))))
(A 0 (A 0 (A 0 (A 1 (- n 3)))))
(A 0 (A 0 (A 0 ... (A 0 (A 0 (A 1 1)))))) ;;now have n-1 (A 0.. defered
(A 0 (A 0 (A 0 ... (A 0 (A 0 2))))) ;;(A 1 1) ==> 2
(A 0 (A 0 (A 0 ... (A 0 2^2)))) ;;(A 0 x) ==> 2x
(A 0 (A 0 (A 0 ... 2^3)))
(A 0 2^(n-1))
2^n

;; so (A 1 10) ==> 2^10

(A 2 n)
(A 1 (A 2 (- n 1)))
(A 1 (A 1 (A 2 (- n 2))))
(A 1 (A 1 (A 1 (A 2 (- n 3)))))
(A 1 (A 1 (A 1 ... (A 1 (A 1 (A 2 1)))))) ;have n-1 (A 1.. defered
(A 1 (A 1 (A 1 ... (A 1 (A 1 2))))) ;(A 2 1) ==> 2
(A 1 (A 1 (A 1 ... (A 1 (2^2))))) ;(A 1 x) ==> 2^x
(A 1 (A 1 (A 1 ... 2^(2^2))))
2^(2^(2^...(2^2)))
;;;;;;;;
;; so (A 2 4) ==> 2^(2^(2^2)) = 2^(2^4) = 2^16


In another way,
(A 1 n)
(A 0 (A 1 (- n 1)))
(A 0 (g (- n 1))) ;; definition of (g n)
(f (g (- n 1))) ;; definition of (f n)
2 * (g (- n 1)) ;; result of the (f n)
2^n ;; mathematical induction; and, (g 1) = 2
;;;;;;;;;;
(A 2 n)
(A 1 (A 2 (- n 1)))
(A 1 (h (- n 1))) ;; definition of (h n)
(g (h (- n 1))) ;; definition of (g n)
2^(h (- n 1)) ;; result of (g n)
2^(2^ ... (2^2)) ;; mathematical induction; and, (h 1) = 2

sicp-exercise-1.9

xercise 1.9

The first +:
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

The second +:
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

This first + procedure generates a recursive process, and the second
generates a iterative process. Why?
Because the second does not envolve defered operations?

sicp-section-1.2.1

1.2 points out that, to become an expert programmer, I need to know the
common patterns of usage in the domain, I should be able to
predict/visualize the consequences of the actions under consideration.

But 1.2 just (you can't be TAUGHT to be an expert!) introduce some common
types of processes: linear recursion, linear iteration, tree recursion, and
then something similar to that in Introduction to Algorithms (which means
there will be a lot tricky skills).

In 1.2.1 it has an explanation to recursive and iterative; it's a different
experience hearing a recursive procedure generates iterative process...

Recursive processes are characterized by defered operations. Iterative
processes has fixed number of state variables, a fixed rule to update and
and (optional) end test.

Recursive process requires the interpreter dod additional work, while
iterative process has everything needed in the program.

sicp-exercise-1.3-1.7

Exercise 1.3

(define (sq x) (* x x))
(define (sum-of-sq x y) (+ (sq x) (sq y)))
(define (>= x y) (or (> x y) (= x y)))
(define (sq-of-two-larger a b c)
(if (>= a b)
  (if (>= b c) (sum-of-sq a b) (sum-of-sq a c))
  (if (>= a c) (sum-of-sq a b) (sum-of-sq b c))))

Exercise 1.5

If the interpreter is using applicative-order, when running (test 0 (p)), first will evaluate the operand, which is a procedure, (p). This, according to the definition of p, will result in infinite loop. Just the case with MIT-Scheme.
With normal-order evaluation, it doesn't first evaluate (p), rather, it substitute the operand (p) into the body of test. And (if (= x 0) will make test return 0.

Exercise 1.6

Since the interpreter uses applicative-order, as stated above, in the call to new-if, all three of good-enough?, guess, (sqrt-iter ...) must first be evaluated. The call to (sqrt-iter ...) will then never stop, leading to infinite loop.

Exercise 1.7

I don't know now how the test fails for small and large numbers.

[UPDATE]
Eli Bendersky has a good explanation, the idea to use a relative ratio instead of hard-coded 0.001 is very pretty. BTW, (sqrt 92400000000000000) and (sqrt 0.0005) works well on my laptop with the original solution.

The updated version of sqrt:

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

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

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

(define (good-enough? guess x)
(< (abs (- guess (update guess x)))
   0.0001))

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

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

(define (update guess x)
(average guess (/ x guess)))

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

Exercise 1.8

(define (cube-root x)
(cube-root-rec 1.0 x))

(define (cube-root-rec guess x)
(if (good-enough? guess x)
  guess
  (cube-root-rec (update guess x) x)))

(define (good-enough? guess x)
(< (abs (- (update guess x) guess))
   0.0001))

(define (update guess x)
(/ (+ (/ x (square guess)) (* 2 guess)) 3))

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

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

sicp-section-1.1

Now part 1.1 has been finished, and I have to say it's quite a different
experience.

But there is hardly more, since this is my first playing with functional
programming and I can't grasp much. Programming in Lisp IS fun, and
gives me some new and strange feelings.

====
1.1 is titled The Elements of Programming, and in sequence introduces
the fundamental parts of programming (languages): primitive expressions,
means of combination and means of abstraction. (The authors emphasize that,
when we describe a language, we should pay particular attention to the means
that the language provides for combining simple ideas to from more complex
ideas.

In this part there are only numbers and procedures, which are no much
different from other languages. Lisp treats data and procedures the same,
which differs from C-likes (but Python also has an elegant model of objects,
for now I am not sure of Lisp's view of variables and objects, it just says
'the name identifies a variable whose value is the object).

Lisp's means of combination is united and elegant, and very interesting :-).
It is powerful, which can be seen even from the simple toy programs in 1.1.

The book then demonstrates several of Lips's means of abstraction: 'define'
viables and procedues, the later being much powerful.

There is a 'substitution' model for apply procedures, which can use
applicative order or normal order.

And we have expressions to do condional processing and other things,
including the special forms: cond, if, and, or, as well as 'define'. 'Not'
is an ordinary procedure.

====
Procedures are black-box abstractions, thus enabling and stressing the
decompositon of the big problem into small subproblems. It also take us to
the level of 'procedual abstraction'.

Regarding this abstraction, there are local names, bound and free variables.

====
Environment seems to be a big thing and comes later in the book.

====
Since it just begins, this post may well need update. The book is in
an academic way, and results the academic taste of my post ;-)

sicp-0-get started

Now I start with the Structure and Interpretation of Computer Programs. My
plan is to finish it within the next semester (I'm not quite sure how long
it will take exactly).

Part of my motivation comes from the curiosity about Lisp, part comes from
those sweet sayings about this magic wizard book, and another part comes
from the Israel guy Eli Bendersky.

I don't plan to follow step by step after this great guy, but his way of
learn is of interest to me and it seems to do an excellent job.

So I decided to follow him. Read through the wizard book, do the
exercises, post my answer and some thinking here. And I hope I can
get a good harvest when finished.