* 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
** 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.
