Zapiski #1 srečanja programerskega bralnega krožka SICP

Zanimivi izseki

str. 9

Every reader should ask himself periodically "Toward what end, toward what end?" — but do not ask it too often lest you pass up the fun of programming for the constipation of bittersweet philosophy.

Lisp is a survivor, having been in use for about a quarter of a century.

str. 11

It is better to have 100 functions operate on one data structure than to have 10 functions operate on 10 data structures.

str. 18

Thus, programs must be written for people to read, and only incidentally for machines to execute.

str. 19

Underlying our approach to this subject is our conviction that "computer science" is not a science and that its significance has little to do with computers.

str. 27

Finally, we would like to acknowledge the support of the organizations that have encouraged this work over the years, including support from Hewlett-Packard, made possible by Ira Goldstein and Joel Birnbaum, and support from DARPA, made possible by Bob Kahn.

Bob Kahn je mdr. soavtor protokolov TCP in IP, pionir omreževanja. V DARPA postal kasneje direktor IPTO (Informational Processing Techniques Office), kjer je ustanovil milijardo-dolarski projekt Strategic Copmuting Initiative, največjo investicijo ameriške federalne vlade v računalništvo ever ('83 do '93) - razvijali so proizvodnjo čipov in umetne inteligence. Ustrašili so se japoncev, podobno kot v 50ih sovjetov.

Po DARPA ustanovil CNRI (corporation for national research initiatives), neprofitno organizacijo kjer je delal tudi guido van rossum (avtor pythona). Tam so izdali python verzije 1.3 do 1.6 ter GNU mailman.

Preko očeta v sorodu s fizikom Hermanom Kahnom, ki je napisal knjigo o tem kako bi amerika lahko zmagala nuklearno vojno in postal inspiracija za dr. Strangelove-a v znanem Kubrickovem filmu. Ustanovil je Hudson institut, konzervativni think tank ki je začel pri premišljevanju hladnovojnih scenarijev in se razširil na polja ekonomije, zdravstva, šolstva in gemblanja. Delal je tudi v RAND korporaciji, močnem hladnovojnem inštitutu, vpletenem v vietnamsko vojno, iraško vojno, danes pa kuri "AI apokaliptični" scenarij.

str. 77

Stoy 1977

Vaje

1.1 Kaj vrnejo izrazi?

(+ 5 3 4)

(- 9 1)

(/ 6 2)

(+ (* 2 4) (- 4 6))

(define a 3)

#nil

(define b (+ a 1))

#nil

(+ a b (* a b))

(= a b)

(if (and (> b a) (< b (* a b)))
    b
    a)

(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))

(+ 2 (if (> b a) b a))

(* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1))

1.2 Pretvori izraz v prefix obliko

\begin{equation} \frac{5+4+(2-(3-(6+\frac{4}{5}))) }{3(6-2)(2-7)} \end{equation}

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

-37/150

1.3 določi postopek, ki prejme 3 števila kot argumente in vrne vsoto kvadratov večjih dveh

(define (vsota-vecjih-kvadratov a b c)
  (cond ((<= a b c) (+ (* b b) (* c c)))
        ((<= b a c) (+ (* a a) (* c c)))
        (else (+ (* b b) (* a a)))))
;; ^ NAROBE! <= primerja vse tri stevilke, ne prvo z drugima dvema oz. ostalimi

(define (+kvadrat a b) (+ (* a a) (* b b)))
(define (vsota-vecjih-kvadratov2 a b c)
  (if (>= a b)
      (if (>= b c)
          (+kvadrat a b)
          (+kvadrat a c))
      (if (>= a c)
          (+kvadrat a b)
          (+kvadrat b c))))

(list
  '("Pričakovano" 85 41 164 89)

  (list "Funkcija1"
    (vsota-vecjih-kvadratov 6 1 7)
    (vsota-vecjih-kvadratov 3 4 5)
    (vsota-vecjih-kvadratov 8 10 2)
    (vsota-vecjih-kvadratov 3 8 5))

  (list "Funkcija2"
    (vsota-vecjih-kvadratov2 6 1 7)
    (vsota-vecjih-kvadratov2 3 4 5)
    (vsota-vecjih-kvadratov2 8 10 2)
    (vsota-vecjih-kvadratov2 3 8 5)))

Pričakovano	85	41	164	89
Funkcija1	85	41	164	73
Funkcija2	85	41	164	89

1.4 Opis procedure

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

Izraz if vrne funkcijo + ali - , glede na to, ali je argument b večji ali manjši od 0.

Če je b manjši od 0, ga odšteje od a, sicer pa ga prišeje. Zato je rezultat funkcije ekvivalenten vsoti a in absolutnega b.

1.5 Aplikativni red in normalni red evalvacije

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

;; Evalvira:
(test 0 (p))

Če interpreter deluje po aplikativnem zaporedju, bo najprej evalviral argumente. Ker je drugi argument postopek, ki v neskončnost vrača vrednost klica samega sebe, se bo program zaciklal oz. zmrznil.

Če pa interpreter deluje po normalnem zaporedju, bo pa začel izvajat postopek pred evalvacijo argumentov, le-te pa šele ko jih potrebuje. Tako bo, if stavek prepoznal ekvivalenco x in 0 ter vrnil 0.

Klic takšne funkcije torej preveri ali interpreter deluje po aplikativnem ali normalnem zaporedju. Guile scheme deluje po aplikativnem redu (in se zacikla). Normalni red pa lahko "simuliramo", če proceduro definiramo kot macro, z define-case. Klic macroja se ne zacikla.

(define-macro (test-m x y)
  (if (= x 0)
      0
      y))

(test-m 0 (p))

1.6 Novi if

Imamo nov if, new-if.

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

Kaj se zgodi, če ga uporabimo za računanje kvadratnih korenov?

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

Navaden if je v bistvu makro in deluje po normalnem zaporedju. Ker je new-if definiran kot procedura, mora zaradi aplikativnega zaporedja najprej evalvirati argumente. Zato se zacikla oz. zamrzne.

1.7 good-enough? ni dovolj dober?

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

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

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

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

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

Pri premajhnih številih good-enough? prehitro "odneha" in dobimo slab približek, pri prevelikih številih pa "predolgo vztraja", saj ne potrebujemo tako natančnega približka. Boljša rešitev s precej elegance je, recimo, primerjava s promilom x namesto 0.001.

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

1.8 kubični koren

Formula za izboljšanje približka y kubičnemu korenu x je

\begin{equation} \frac{x/y^{2}+2y}{3} \end{equation}

Postopek: TODO

1.10 Ackermannov postopek

Sledeči postopek je Ackermannov:

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0)
         (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

Kakšni so rezultati sledečih izrazov?

(A 1 10)

(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

(A 2 4)

(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 1 2)))
(A 1 (A 1 (A 0 (A 1 1)))
(A 1 (A 1 (A 0 2)))
(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)
(A 0 (A 1 15))
(A 0 (A 0 (A 1 14))
...
(A 0 (A 0 (A 1 14))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1))))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (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 (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 (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 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024))))))
(A 0 (A 0 (A 0 (A 0 (A 0 2048)))))
(A 0 (A 0 (A 0 (A 0 4096))))
(A 0 (A 0 (A 0 8192)))
(A 0 (A 0 16384))
(A 0 32768)

65536

(A 3 3)

(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)

65536

Če imamo še sledeče postopke:

(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n ) (A 2 n))
(define (k n) (* 5 n n))

Jedrnato opredeli matematične funkcije izračuna postopkov f, g in h. k, recimo izračuna 5n^2.

f: 2n

g: 2ⁿ

h: 2^2ⁿ