SICP - 1.1 -- 1.5

A terv a következő: az elkövetkező egy évben megpróbálom végigolvasni
a SICP-et, és megoldani az összes, vagy majdnem az összes feladatot. A
feladatok megoldásait és a számomra érdekesebb részeket poszolom ide, az
esetleg felmerült kérdéseimmel együtt.

Nem tudom, hogy az egyetem meg minden más elfoglaltságom mellett milyen
tempóban fogok haladni, de igyekezni fogok olyan 7-10 naponta egy újabb
részletet feldolgozni. Ennek jegyében következzen itt az 1.-től az 1.1.6-ig
tartó szakasz, a feladatok megoldásaival.

***

Az első rész a "Building Abstractions With Procedures" címet viseli.
Az már az első oldalaktól kezdve nyilvánvaló, hogy a könyv túl sűrű ahhoz,
hogy néhány bekezdésben summázni lehessen a fejezeteit. Ezzel nem is fogok
próbálkozni. Inkább néhány fontos fogalomra fogok koncentrálni,
elsősorban olyanokra, amelyek termékenyeknek vagy homályosnak tűnnek (
vagy esetleg -- horribile dictu -- mindkettőnek egyszerre).

A könyv szerzői szerint a céljuk a "computational process"-ek vizsgálata.
Nem világos, hogy az itt szereplő "process"-t minek kéne fordítani, főleg
azért mert a szerzők szóhasználatában ez nem egyenlő egy programmal.
Ehelyett szerintük a program azon szabályok gyűjteménye, amelyek
befolyásolják az "evolution of the process"-t. Arról nem is beszélve, hogy
ezek a programok LISP "procedure"-okból állnak össze, de közben a
"procedure"-ök azok amelyek a "process"-eket leírják.

Én az olvasott -- és elvileg folyamatosan self-contained -- rész alapján
a "process"-t folyamatnak a "procedure"-t pedig eljárás-nak
fordítanám. A folyamatok absztrakt entitások, talán az algoritmusokkal és
egyéb matematikai objektumokkal állnak rokonságban, míg az eljárások
egy konkrét programozási nyelv, konkrét kifejezései. Eddig úgy tűnik, hogy
ugyanazt a folyamatot leírhatja több különböző eljárás is (azonos
algoritmus, különböző nyelvekben) de egy eljárás leírhat különböző
folyamatokat is egyéb tényezők függvényében (mint például a kiértékelési
sorrend). [Ha ez a leírás pontatlan vagy zavaros, kérlek javítsatok ki.]

Az 1.1-től kezdődő részben a könyv a Scheme eljárások alapelemeit mutatja be.
A könyv egyik alaptörekvése, hogy felkészítsen komplex rendszerek tervezésére
és kezelésére. Talán ennek köszönhető az, hogy egy olyan bonyolult és absztrakt
dolgot, mint egy programozási nyelv gyakorlatilag három mechanizmusra
vezetnek vissza. Adottak ugyanis (a) primitív kifejezések (b) eszközök
amivel összetett elemeket alkothatunk egyszerűbbekből (means of combination)
és (c) eszközök amivel összetett elemeket ragadhatunk meg egységekként
(means of abstraction). Ez a hármas felosztás elvileg az egész könyvben
kulcsszerepet fog kapni.

A továbbiakban bemutatják a Scheme alapelemeit, a kifejezéseket, a prefix
jelölést, a névadást, a környezet fogalmát, a kiértékelés és az összetett
eljárások (kb.: függvények definiálása) fogalmát. Különösen fontos az a rész
amit az applikáció behelyettesítéses modelljéről írnak, különösen azért
mert reflektálnak arra, hogy mit modellez mi (1.1.5-ös rész). Itt esik szó
az applicative order-ről és a normal order-ről is, ez is lényeges (már
a feladatok szempontjából is). Ezután még bevezetésre kerülnek a feltételes
kifejezések (mindjárt ketten is, a

cond

és az

if

)
valamit a predikátumok is(Igazra vagy Hamisra kiértékelődő kifejezések).

Mindezzel a tudással felszerelkezve már megoldhatóak a következő feladatok:

1.1 "Játsszunk interpretert feladat"

-> 10
10
-> (+ 5 3 4)
12
-> (- 9 1)
8
-> (/ 6 2)
3
-> (+ (* 2 4) (- 4 6))
6
-> (define a 3)

-> (define b (+ a 1))

-> (+ a b (* a b))
19
-> (= a b)
#f ;; ez a False
-> (if (and (> b a) (< b (* a b)))
       b
       a)
4
-> (cond ((= a 4) 6)
         ((= b 4) (+ 6 7 a))
         (else 25))
16
-> (+ 2 (if (> b a) b a))
6
-> (* (cond ((> a b) a)
            ((< a b) b) 
            (else -1))
         (+ a 1))
16

1.2 "Fordítsunk törtet prefix alakra"

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

1.3 Írjunk egy eljárást amely három szám közül a két nagyobbik négyzeteinek
összegét adja vissza.

;; Eloszor definialjuk a negyzetek osszeget

(define (sum-of-squares x y)
  (+ (* x x) (* y y)))

;; Mondjuk meg mikor nagyobb x y-nál

(define (grtr x y)
  (if (> x y)
      x
      y))

;; Most pedig kombinaljuk oket ossze

(define (s-o-s-grtr-two x y z)
  (sum-of-squares (grtr x y) (grtr y z)))

1.4 "Observe that our model of evaluation allows for combinations whose operators
are compound expressions. Use this observation to describe the behavior of the
following procedure:"

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

Itt ugye az történik, hogy az

a-plus-abs-b

kiértékelésekor
először megkapjuk

((if (> b 0) + -) a b))

-t amiben
az ki kell értékelnünk az if-es kifejezést
ami egy b-től függő műveletet ad vissza. Ez '-' ha b negatív és '+' ha
b pozitív, azaz mindenképpen a és abs(b) összegét fogjuk megkapni. Trükkös
egyfelől az, hogy összetett kifejezés is állhat egy definíció részeként,
de az még inkább, hogy egy kondicionális kifejezés visszaadhat egy operátort
amit a következő lépésekben alkalmazhatunk is a szembejövő argumentumokra.
Így az eljárás pontosan azt éri el, amit a neve ígér.

1.5. "Ben Bitdiddle has invented a test to determine whether the interpreter
he is faced with is using applicative-order evaluation or normal-order evaluation.
He defines the following two procedures:

(define (p) (p))

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

Then he evaluates the expression

(test 0 (p))

What behavior will Ben observe with an interpreter that uses applicative-order
evaluation? What behavior will he observe with an interpreter that uses
normal-order evaluation? Explain your answer. (Assume that the evaluation rule
for the special form if is the same whether the interpreter is using normal or
applicative order: The predicate expression is evaluated first, and the result
determines whether to evaluate the consequent or the alternative expression.)"

Applicative order esetén az operátorok alkalmazása esetén előbb minden
részkifejezést ki kell értékelni és utána alkalmazni rájuk az operátorokat.
Ez esetben a a

(test 0 (p))

egy szép kis végtelen ciklust
fog generálni (hiszen p-t ki kell értékelni, de p-t kapunk, amit ki kell
értékelni, de ...). Normal order esetén azonban csak akkor értékelünk
ki valamit, ha szükségünk van rá (innen a másik név: "call by need") így
mivel 0 = 0, ezért a feltételes kifejezés

else

ágára nem fogunk
ráfutni, hanem csak kapunk egy 0-t válaszként.