* notes
** 1
*** 1
**** 5
#+BEGIN_QUOTE
In general, when modeling phenomena in science and engineering, we
begin with simplified, incomplete models. As we examine things in
greater detail, these simple models become inadequate and must be
replaced by more refined models.
#+END_QUOTE
*** 2
**** 6
***** The Fermat Test
#+BEGIN_EXAMPLE
(expmod 2 5 5)
(remainder (* 2 (expmod 2 4 5)) 5)
(remainder (* 2 (remainder (square (expmod 2 2 5)) 5)) 5)
(remainder (* 2 (remainder (square (remainder (square (expmod 2 1 5))
5)) 5)) 5)
(remainder (* 2 (remainder (square (remainder
(square (remainder
(* 2 (expmod
2
0
5))
5)) 5)) 5)) 5)
(remainder (* 2 (remainder (square (remainder
(square (remainder
(* 2 1) 5))
5)) 5)) 5)
(remainder (* 2 (remainder (square (remainder (square (remainder 2 5))
5)) 5)) 5)
(remainder (* 2 (remainder (square (remainder (square 2) 5)) 5)) 5)
(remainder (* 2 (remainder (square (remainder 4 5)) 5)) 5)
(remainder (* 2 (remainder (square 4) 5)) 5)
(remainder (* 2 (remainder 16 5)) 5)
(remainder (* 2 1) 5)
(remainder 2 5)
2
#+END_EXAMPLE
#+BEGIN_EXAMPLE
(expmod 2 6 6)
(remainder (square (expmod 2 3 6) 6))
(remainder (square (remainder (* 2 (expmod 2 2 6)) 6)) 6)
(remainder (square (remainder (* 2 (remainder (square (expmod 2 1 6))
6)) 6)) 6)
(remainder (square (remainder (* 2 (remainder
(square (remainder
(* 2 (expmod 2 0 6))
6)) 6)) 6)) 6)
(remainder (square (remainder (* 2 (remainder
(square (remainder (* 2 1) 6))
6)) 6)) 6)
(remainder (square (remainder (* 2 (remainder (square (remainder 2 6))
6)) 6)) 6)
(remainder (square (remainder (* 2 (remainder (square (remainder 2 6))
6)) 6)) 6)
(remainder (square (remainder (* 2 (remainder (square 2) 6)) 6)) 6)
(remainder (square (remainder (* 2 (remainder 4 6)) 6)) 6)
(remainder (square (remainder (* 2 4) 6)) 6)
(remainder (square (remainder 8 6)) 6)
(remainder (square 2) 6)
(remainder 4 6)
4
#+END_EXAMPLE
** guile
*** use module
#+BEGIN_SRC scheme
(use-modules (some thing))
#+END_SRC
* exercises
** 1
*** 4
#+BEGIN_SRC scheme
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))
#+END_SRC
If ~b~ is greater than 0, do ~a + b~; otherwise do ~a - b~.
*** 5
code at [[./one/five.scm]]
If the interpreter uses *applicative order* to evaluate the
expression:
#+BEGIN_SRC scheme
(test 0 (p))
#+END_SRC
The parameters are evaluated before applying the compound procedure
~test~; 0 evaluates to 0, ~(p)~ never finishes evaluating as the
compound procedure ~p~ recursively calls itself again and again
infinitely.
If same expression is evaluated by the interpreter using *normal
order*, the expression will be expanded to
#+BEGIN_SRC scheme
(if (= 0 0)
0
(p)))
#+END_SRC
and will evaluate to ~0~.
*** 6
If I've understood it correctly, scheme uses applicative-order
evaluation, meaning, it evaluates the operands before appling the
procedure.
In the case when ~new-if~ used in the ~sqrt-iter~ procedure, the
operands/arguments for the ~new-if~ -- ~(good-enough? guess x)~,
~guess~, ~(sqrt-iter (improve guess x) x)~ -- are evaluated. Due
to the last operand, which is a call to the ~sqrt-iter~ procedure,
we get into infinite loop of evaluating the ~sqrt-iter~ procedure
again and again.
*** 7
The following list show the tolerance value and the corresponding
square root of 0.1 computed with that tolerance value.
#+BEGIN_EXAMPLE
((0.001 . 0.316245562280389)
(1.0e-4 . 0.316245562280389)
(1.0e-5 . 0.31622776651756745)
(1.0000000000000002e-6 . 0.31622776651756745)
(1.0000000000000002e-7 . 0.31622776651756745)
(1.0000000000000002e-8 . 0.31622776651756745)
(1.0000000000000003e-9 . 0.31622776651756745)
1.0000000000000003e-10 . 0.31622776601683794)
#+END_EXAMPLE
Guile's =sqrt= function says the square root of 0.1 is
0.31622776601683794:
#+BEGIN_SRC scheme
scheme@(guile-user)> (sqrt 0.1)
$7 = 0.31622776601683794
#+END_SRC
From above, it can be observed that the only when the tolerance value
for the =good-enough?= function is ~1.0e-10, does the square root of
0.1 produced by our custom square root function matches the value
produced by Guile's =sqrt= function.
If the =good-enough?= is changed such that it returns =true= if the
difference between the present guess and the previous guess is less
than or equal to 0.001, the sqrt function yields 0.31622776651756745
for sqrt(0.1).
#+BEGIN_SRC scheme
scheme@(guile-user)> (sqrt-sicp-alt 0.1)
$9 = 0.31622776651756745
#+END_SRC
0.31622776651756745 is more precise than 0.316245562280389 (the answer
returned by the custom sqrt function that uses the ol' =good-enough=
function) but not as precise as the answer returned by the guile's
sqrt function.
For a number as large as 1000000000, guile's =sqrt= function and
=sqrt-sicp-alt= returns 31622.776601683792, =sqrt-sicp= returns
31622.776601684047; =sqrt-sicp= being slightly more precise than the
other functions.
*** 9
**** recursive process
#+BEGIN_SRC scheme
(define (+ a b)
(if (= a 0)
b
(inc (+ dec a) b)))
#+END_SRC
#+BEGIN_SRC
(+ 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 <-----|
#+END_SRC
**** iterative process
#+BEGIN_SRC scheme
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
#+END_SRC
#+BEGIN_SRC
(+ 4 5 --+
(+ 3 6) |
(+ 2 7) |
(+ 1 8) |
(+ 0 9) |
9 <------+
#+END_SRC
*** 10
#+BEGIN_SRC scheme
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
#+END_SRC
**** (A 1 10) = 2^y
#+BEGIN_SRC scheme
(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
(A 0 (A 0 (A 0 (A 1 7))))
(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
(A 0 (A 0 (A 0 (A 0 (A 0 32)))))
(A 0 (A 0 (A 0 (A 0 64))))
(A 0 (A 0 (A 0 128)))
(A 0 (A 0 256))
(A 0 512)
1024
#+END_SRC
At this point, I'm guessing function ~A = 2^xy~.
After some thinking, I don't think it is ~A = 2^xy~. I'm guessing it
is ~A = 2x2^y~.
**** (A 2 4)
#+BEGIN_SRC scheme
(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 8))
(A 1 16)
2^16 = (expt 2 16) = 65536
#+END_SRC
**** (A 3 3)
#+BEGIN_SRC scheme
(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 (A 1 (A 2 1)))
(A 2 (A 1 2))
(A 2 (A 0 (A 1 1)))
(A 2 (A 0 2))
(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 8))
(A 1 16)
2^16 = (expt 2 16) = 65536
#+END_SRC
**** (A 2 5)
#+BEGIN_SRC scheme
(A 2 5)
(A 1 (A 2 4))
(A 1 (A 1 (A 2 3)))
(A 1 (A 1 (A 1 (A 2 2))))
(A 1 (A 1 (A 1 (A 1 (A 2 1)))))
(A 1 (A 1 (A 1 (A 1 2))))
(A 1 (A 1 (A 1 (A 0 (A 1 1)))))
(A 1 (A 1 (A 1 (A 0 2))))
(A 1 (A 1 (A 1 4)))
(A 1 (A 1 16))
(A 1 65536)
2^65536
#+END_SRC
**** (A 2 6)
#+BEGIN_SRC scheme
(A 2 6)
(A 1 (A 2 5))
(A 1 (A 1 (A 2 4)))
(A 1 (A 1 (A 1 (A 2 3))))
(A 1 (A 1 (A 1 (A 1 (A 2 2)))))
(A 1 (A 1 (A 1 (A 1 (A 1 (A 2 1))))))
(A 1 (A 1 (A 1 (A 1 (A 1 2)))))
(A 1 (A 1 (A 1 (A 1 4))))
(A 1 (A 1 (A 1 16)))
(A 1 (A 1 65536))
(A 1 2^65536)
2^(2^65536)
#+END_SRC
**** mathematical definitions for
***** (define (f n) (A 0 n))
=(f n)= computes =(* 2 n)=
***** (define (g n) (A 1 n))
=(g n)= computes =(expt 2 n)=
***** (define (h n) (A 2 n))
=(h n)= computes =(expt 2 (h (1- n)))=
***** (define (k n) (* 5 n n))
=(k n)= computes =(* 5 n n)=
*** 11
I could not come up with a an iterative procedure.
two versions of the recursive procedure are available at
one/eleven.scm.
*** 12
#+BEGIN_SRC
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
#+END_SRC
*** 20
#+BEGIN_SRC scheme
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
#+END_SRC
#+BEGIN_EXAMPLE
normal order - no. of calls to remainder - 14
applicative order - no. of calls to remainder - 4
#+END_EXAMPLE
#+BEGIN_EXAMPLE
normal order
(gcd 206 40)
(= (= 40 0)) # #f
(gcd 40 (remainder 206 40))
;; 1 call here.
(= (remainder 206 40) 0)
(= (6 0))
(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))
;; 2 calls here.
(= (remainder 40 (remainder 206 40)) 0)
(= (remainder 40 6) 0)
(= 4 0)
(gcd (remainder 40 (remainder 206 40))
(remainder (remainder 206 40)
(remainder 40 (remainder 206 40))))
;; 4 calls here.
(= (remainder (remainder 206 40)
(remainder 40 (remainder 206 40))) 0)
(= (remainder (remainder 206 40)
(remainder 40 6)) 0)
(= (remainder 6 4) 0)
(= 2 0)
(gcd (remainder (remainder 206 40)
(remainder 40 (remainder 206 40)))
(remainder (remainder 40 (remainder 206 40))
(remainder (remainder 206 40)
(remainder 40 (remainder 206 40)))))
;; 7 calls here.
(= (remainder (remainder 40 (remainder 206 40))
(remainder (remainder 206 40)
(remainder 40 (remainder 206 40)))) 0)
(= (remainder (remainder 40 (remainder 206 40))
(remainder (remainder 206 40)
(remainder 40 6))) 0)
(= (remainder (remainder 40 (remainder 206 40))
(remainder (remainder 206 40)
4)) 0)
(= (remainder (remainder 40 (remainder 206 40))
(remainder 6
4)) 0)
(= (remainder (remainder 40 (remainder 206 40))
2) 0)
(= (remainder (remainder 40 6)
2) 0)
(= (remainder 4
2) 0)
(= 0 0)
;; 4 calls here.
(remainder (remainder 206 40)
(remainder 40 (remainder 206 40)))
(remainder (remainder 206 40)
(remainder 40 6))
(remainder (remainder 206 40)
(remainder 40 6))
(remainder (remainder 206 40)
4)
(remainder 6
4)
2 ; (+ 1 2 4 7 4) => 14 calls in total.
#+END_EXAMPLE
#+BEGIN_EXAMPLE
applicative order
(gcd 206 40)
(gcd 40 (remainder 206 40))
(gcd 40 6)
(gcd 6 (remainder 40 6))
(gcd 6 4)
(gcd 4 (remainder 6 4))
(gcd 4 2)
(gcd 2 (remainder 4 2))
(gcd 2 0)
2
#+END_EXAMPLE
** 2
*** 22
#+BEGIN_SRC scheme
(cons ... (cons (cons LIST NUMBER²) NUMBER²) NUMBER²)
#+END_SRC
creates a list with the squared numbers in a messy nested list like:
#+BEGIN_SRC scheme
(square-list '(1 2 3 4 5))
;; $3 = (((((() . 1) . 4) . 9) . 16) . 25)
#+END_SRC
*** 24
#+BEGIN_EXAMPLE
(1 (2 (3 4)))
+----+----+ +----+----+ +----+----+ +----+----+
| o | o--|----->| o | o--|----->| o | o--|----->| o | / |
+----+----+ +----+----+ +----+----+ +----+----+
| | | |
| | | |
v v v v
+----+ +----+ +----+ +----+
| 1 | | 2 | | 3 | | 4 |
+----+ +----+ +----+ +----+
(1 (2 (3 4)))
o
/ \
/ \
/ \
/ \
/ \
1 \
\ (2 (3 4))
o
/ \
/ \
/ \
/ \
/ \
/ \
2 \
\ (3 4)
o
/ \
/ \
/ \
/ \
/ \
/ \
3 4
#+END_EXAMPLE
*** 25
#+BEGIN_SRC scheme
(define one '(1 3 (5 7) 9))
(car (cdr (car (cdr (cdr one)))))
#+END_SRC
#+BEGIN_SRC scheme
(define two '((7)))
(car (car two))
#+END_SRC
#+BEGIN_SRC scheme
(define three '(1 (2 (3 (4 (5 (6 7)))))))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr three))))))))))))
#+END_SRC
*** 26
#+BEGIN_SRC scheme
(define x (list 1 2 3))
(define y (list 4 5 6))
(append x y)
'(1 2 3 4 5 6)
(cons x y)
'((1 2 3) (4 5 6))
(list x y)
'((1 2 3) (4 5 6))
#+END_SRC
*** 29
**** d
Everything needs to be changed!
Initially, for =make-mobile=, it used be:
#+BEGIN_SRC scheme
scheme@(guile-user)> (make-mobile (make-branch 5 50) (make-branch 5 50))
$37 = ((5 50) (5 50))
#+END_SRC
Now (using =cons= instead of =list=) it is:
#+BEGIN_SRC scheme
scheme@(guile-user)> (make-mobile (make-branch 5 50) (make-branch 5 50))
$58 = ((5 . 50) 5 . 50)
#+END_SRC
Initially, for =make-branch=, it used be:
#+BEGIN_SRC scheme
scheme@(guile-user)> (make-branch 5 (make-mobile (make-branch 3 50) (make-branch 3 50)))
$61 = (5 ((3 50) (3 50)))
#+END_SRC
Now (using =cons= instead of =list=) it is:
#+BEGIN_SRC scheme
scheme@(guile-user)> (make-branch 5 (make-mobile (make-branch 3 50) (make-branch 3 50)))
$60 = (5 (3 . 50) 3 . 50)
#+END_SRC
*** 43
I'll measure the the time taken for function ~queens~ to complete
by calculating the number of times ~queen-cols~ gets called.
First, I'm going to see how many times ~queen-cols~ gets called
for the original version of ~queens~ with ~board-size=8~
#+begin_example
board-size = 8 ; k = 8 -> 1 * (queen-cols 7)
; k = 7 -> 1 * (queen-cols 6)
; k = 6 -> 1 * (queen-cols 5)
; k = 5 -> 1 * (queen-cols 4)
; k = 4 -> 1 * (queen-cols 3)
; k = 3 -> 1 * (queen-cols 2)
; k = 2 -> 1 * (queen-cols 1)
; k = 1 -> 1 * (queen-cols 0)
; k = 0 -> 0
#+end_example
~queen-cols~ gets called 8 times when ~board-size~ is 8
To generalize it ~queen-cols~ gets called B times when the
~board-size~ is B.
Next, I'm going to see how many times ~queen-cols~ gets called for
Louis Reasoner's version of the of ~queens~
#+begin_example
board-size = 8 ; k = 8 -> 8 * (queen-cols 7)
; k = 7 -> 8 * (queen-cols 6)
; k = 6 -> 8 * (queen-cols 5)
; k = 5 -> 8 * (queen-cols 4)
; k = 4 -> 8 * (queen-cols 3)
; k = 3 -> 8 * (queen-cols 2)
; k = 2 -> 8 * (queen-cols 1)
; k = 1 -> 8 * (queen-cols 0)
; k = 0 -> 0
#+end_example
Here, the ~queen-cols~ is getting called ~8^8~ times or ~B^B~
times when the ~board-size is B.
From above, if the original version of ~queens~ took time ~T~,
then Louis's version will take ~T^T~ to finish.
