SICP - 1.6 -- 1.8

1.6

Alyssa P. Hacker doesn't see why if needs to be provided as a special form.
``Why can't I just define it as an ordinary procedure in terms of cond?'' she asks.
Alyssa's friend Eva Lu Ator claims this can indeed be done, and she defines a new
version of if:

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

Eva demonstrates the program for Alyssa:

(new-if (= 2 3) 0 5)
5

(new-if (= 1 1) 0 5)
0

Delighted, Alyssa uses new-if to rewrite the square-root program:

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

What happens when Alyssa attempts to use this to compute square roots? Explain.

***

Ha már gép előtt vagyunk próbáljuk ki, mit csinál. Bumm, végtelen ciklus. Oké, akkor
biztosan a kiértékeléssel lesz valami probléma.

Először természetesen arra gondoltam, hogy itt az

if

és a

cond

közötti különbségre kell figyelni. Csak az a gond, hogy a jelek szerint bármelyik

if

-et használó kód átírható volt

cond

-ra. Például a:

(define (fct1 n)
  (cond ((= 1 n) n)
        (else (* n (fct1 (- n 1))))))

függvény pontosan azt az eredményt adja, mint a következő:

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

Nyilván valahol máshol kell lennie a problémának. A megoldásra később jöttem rá (biztos
vannak hozzám hasonlóak akik újra visszatérnek a már elvetett megoldáshoz és később
szinte teljesen váratlanul ugrik be a megoldás). Először is figyeljük meg, hogy mi történik
akkor ha az új

if

-et nem

cond

-dal hanem

if

-fel
definiáljuk:

(define (new-if predicate then-clause else-clause)
  (if predicate 
      then-clause
      else-clause))

Nahát, így is végtelen ciklusba kerülünk! A megoldás ekkor ugrott be: a definiált
procedúrák és a special form-ok közti különbségről van szó. Mivel applicative ordert
használunk, ezért szépen kiértékeljük az operátorokat és az argumentumokat, és utána
az eredményt kombináljuk. Igen ám, de az olyan rekurzív procedúráknál, mint például
a

sqrt-iter

ez nem lehetséges, hiszen újra és újra saját magára alkalmazzuk
a procedúrát. Ennek a megtörésére alkalmasak a special form-ok, amelyek nem feltétlenül
értékelik ki az összes argumentumukat. De ha az

if

-et definiálni akarjuk, akkor pont
ezt a specialitását dobjuk el, így a

new-if

-fel már végtelen ciklusba futunk.

1.7

The

good-enough?

test used in computing square roots will not be very effective for finding
the square roots of very small numbers. Also, in real computers, arithmetic operations are almost always
performed with limited precision. This makes our test inadequate for very large numbers. Explain these
statements, with examples showing how the test fails for small and large numbers. An alternative strategy
for implementing

good-enough?

is to watch how guess changes from one iteration to the next and
to stop when the change is a very small fraction of the guess. Design a square-root procedure that uses
this kind of end test. Does this work better for small and large numbers?

***

Na, ez volt az a feladat, amelyhez szerintem nem volt teljesen elég az eddigi részek elolvasása.
Egy kicsit jobban bele kellett volna ásnom magam a számítógépes aritmetikába ahhoz, hogy egy igazán
elegáns választ tudjak adni. Enélkül viszont csak egy egy "hopefully educated guess"-t tudok adni. :)

1. A nagyon kicsi számok gyökvonásánál azért nem jó a
   

   good-enough?

   mert egy rögzített
   számhoz hasonlít minden számot (pontosabban a közelítés négyzetét). Ha azonban ennél a számnál jóval
   kissebb számokkal dobálózunk, akkor az iteráció két lépése közti különbség jóval kisebb lehet ennél,
   még akkor is, ha ez még bőven nem az optimális gyök. Kis számoknál így gyorsan kaphatunk egy
   pontatlan gyököt.

2. A nagy számokkal ugyanez a probléma még viccesebb helyzetet teremt: bár nagyon gyorsan kaphatunk
   jó közelítést a nagy szám gyökére, a procedúra még sem áll le, mert a két iteráció között megkívánt
   különbséget csak nagyon sokára éri el. Feltéve persze, hogy eléri, és nem veszik el a kerekítések között!
   (Ez az a rész, aminek jobban utána kéne néznem.)
3. A jó hír viszont az, hogy a kicsit sötét foltok ellenére is le lehet kódolni az optimálisabb
   megoldást. Elég csak szigorúan odafigyelve követni a feladat leírását:

   watch how guess changes from one iteration to the next and to stop when the change
   is a very small fraction of the guess.

   Azaz:

   
   (define (good-enough2? guess x)
     (< (abs (- (improve guess x) guess)) 0.001))
   

4. A fenti teszt már nagyon gyorsan pontos eredményeket ad nagy számokra, kis számokra pedig tovább
   ad pontos eredményeket, mint az eredeti teszt.

1.8

Newton's method for cube roots is based on the fact that if y is an approximation to the cube
root of x, then a better approximation is given by the value

Use this formula to implement a cube-root procedure analogous to the square-root procedure.
(In section 1.3.4 we will see how to implement Newton's method in general as an abstraction
of these square-root and cube-root procedures.)

***

Ezzel a feladattal szerintem a szerzők meg akarnak ágyazni a modularitás tanításának. Végülis
nincs is más dolgunk mint az egyik procedúrát módosítani, minden mást pedig hagyni az eredetiben.
(Azaz, dehogy hagyjuk: át kell nevezni mindent. De mennyivel egyszerűbb lenne, ha nem kéne lemásolni
hanem csak megfelelően paraméterezni egy általános procedúrát. Erre utalnak is a lábjegyzetben.)

A formula az aktuális

improve

implementálásához kell:

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

Másoljuk át a többi elemet és nevezzük át őket:

(define (cuberoot-iter guess x)
  (if (good-enough3? guess x)
      guess
      (cuberoot-iter (improve3 guess x)
                 x)))

(define (good-enough3? guess x)
  (< (abs (- (improve3 guess x) guess)) 0.001))

(define (cbrt n)
  (cuberoot-iter 1.0 n))

> (cbrt 27.0)
3.0000005410641766
> (cbrt 1000.0)
10.000000145265767
> (cbrt 2.0)
1.259933493449977

A pontosságon természetesen javíthatunk, ha a

good-enough?

-ban kissebb számot adunk meg.