=> Tehtävä 1 <=
Sykliset listat
---------------

Tee kirjan tehtävä 3.18 tekemällä proseduuri cyclic-list?, joka ottaa
argumentiksi tarkistettavan listan ja palauttaa totuusarvon. Kokeile
ratkaisuasi kirjan tehtävän 3.13 tehtävänannossa tehdyllä listalla.

Palauta vastauksena tekemäsi cyclic-list?-proseduurin määrittely.

=> Tehtävä 2 <=
Struktuurit
-----------

Struktuurit ovat eräänlainen tietorakenne, joka koostuu kentistä.
Kenttiä voi olla mielivaltainen määrä. Jokaisella kentällä on nimi ja
alkuarvona tyhjä lista '().

Struktuureja luodaan konstruktorilla:

(make-struct <field1> ... <fieldn>)

Tälle konstruktorille annetaan argumenteiksi struktuurin kenttien
nimet. Make-struct palauttaa funktion, joka osaa käsitellä seuraavat
viestit.

* (s 'ref <field name>) palauttaa kentän <field name> arvon

* (s 'set! <field name> <value>) asettaa kentän <field name> arvoksi
  <value>.

* (s 'set-all! <value1> ... <valuen>) asettaa kaikkien kenttien arvot.
  Arvoja on oltava yhtä monta kuin  make-structilla on luotu
  struktuurille kenttiä.

Esimerkki:

> (define time (make-struct 'hour 'min 'sec))
> (time 'set-all! 12 5 10)
> (time 'ref 'hour)
12
> (time 'ref 'min)
5
> (time 'ref 'sec)
10
> (time 'set! 'hour 15)
ok  ; return value is unspecified
> (time 'ref 'hour)
15

Toteuta tällaiset struktuurit itse schemellä tekemällä edellä
kuvatulla tavalla toimiva make-struct-proseduuri. Palauta
vastauksenasi tekemäsi make-struct-proseduurin määritelmä.

(R5RS-standardin mukainen Schemed ei sisällä tapaa luoda/käsitellä
struktuureja, mutta monissa Scheme-toteutuksissa on vastaavanlainen
rakenne kieleen tehtynä tulkkikohtaisena laajennuksena.)


=> Tehtävä 3 <=
Olio-ohjelmointia
-----------------

Kirjan kolmosluvussa käytetty "message passing"-tyyli on melko lähellä
olio-ohjelmoinnin ohjelmointityyliä, mutta kirjassa ei puhuta mm.
perinnästä ja muista olio-ohjelmoinnin tärkeistä käsitteistä.

Perintä tarkoittaa sitä, että jokin olio voi periä jonkin toisen olion
ominaisuuksia ja laajentaa niitä. Esimerkiksi olio, joka simuloi
kerrostalon hissiä, voisi olla seuraavanlainen:

(define (make-elevator min-floor max-floor)
  (let ((current-floor min-floor))
    (define (go-down! self)
      (if (= current-floor min-floor)
	  (error "ELEVATOR: Can't go down")
	  (set! current-floor (- current-floor 1))))
    (define (go-up! self)
      (if (= current-floor max-floor)
	  (error "ELEVATOR: Can't go up")
	  (set! current-floor (+ current-floor 1))))
    (define (get-floor self)
      current-floor)
    (define (dispatch m)
      (cond ((eq? m 'go-down!) go-down!)
	    ((eq? m 'go-up!) go-up!)
	    ((eq? m 'get-floor) get-floor)
	    (else (error "ELEVATOR: Invalid message received" m))))
    dispatch))

Tämä on vielä melkein tavallista message passing -tyyliä (vrt. esim.
kirjan sivun 223 make-account), mutta viesteille annetaan ylimääräinen
self-argumentti, jonka on tarkoitus viitata olioon, joka viestin saa
(self-argumentin merkitys selviää kohta).

Tällaista hissioliota voitaisiin käyttää näin:

(define (ask object message . args)
  (apply (object message) (cons object args)))

> (define e (make-elevator 1 5))
> (ask e 'get-floor)
1
> (ask e 'go-up!)
> (ask e 'get-floor)
2

Ask-apuproseduuri antaa viesteille selkeämmän syntaksin; esimerkiksi
(ask e 'get-floor):n sijasta voitaisiin yhtä hyvin kirjoittaa
((e 'get-floor) e), jossa jälkimmäinen e menee self-argumentiksi
get-floor-proseduurille.

Nyt voimme tehdä olion, joka perii tämän hissiolion ominaisuudet,
mutta jolla voi myös liikkua suoraan tiettyyn kerrokseen:

(define (make-better-elevator min-floor max-floor)
  (let ((parent (make-elevator min-floor max-floor)))
    (define (go-to-floor! self new-floor)
      (let ((current (ask self 'get-floor)))
	(cond ((< current new-floor)
	       (ask self 'go-up!)
	       (go-to-floor! self new-floor))
	      ((> current new-floor)
	       (ask self 'go-down!)
	       (go-to-floor! self new-floor))
	      (else
	       'done))))
    (define (dispatch m)
      (cond ((eq? m 'go-to-floor!) go-to-floor!)
	    (else (parent m))))
    dispatch))

Tämä olio siis käsittelee itse viestin go-to-floor!, mutta lähettää
muut viestit käsiteltäväksi luomalleen elevator-oliolle, jolle on
annettu nimi parent.

Go-to-floor!:n käsittelyssä olio lähettää viestin itselleen mm.
kohdassa (ask self 'go-up!). Self-argumentin tulee siis viitata olioon
itseensä (eli make-better-elevatorin palauttamaan
dispatch-proseduuriin). Lähettetty viesti menee dispatch-proseduurin
kautta parent-oliolle.

Edellisen lisäksi teemme olion, joka perii better-elevator-olion,
mutta joka näyttää hissin liikkeet käyttäjälle displayllä:

(define (make-displaying-elevator min-floor max-floor)
  (let ((parent (make-better-elevator min-floor max-floor)))
    (define (go-up! self)
      (display "going up")
      (newline)
      (ask parent 'go-up!))
    (define (go-down! self)
      (display "going down")
      (newline)
      (ask parent 'go-down!))
    (define (dispatch m)
      (cond ((eq? m 'go-up!) go-up!)
	    ((eq? m 'go-down!) go-down!)
	    (else (parent m))))
    dispatch))

Tämä siis käsittelee itse viestit go-up! ja go-down! ja lähettää muut
parent-oliolleen. Go-up!:n käsittelijä tulostaa ensin tekstin "going
up" ja lähettää sitten parent-oliolle go-up!-viestin, jonka parent
käsittelee normaalisti.

Self-argumenttia tarvitaan juuri tämän ominaisuuden toteuttamiseksi.
Self-argumentin sijasta viesti voitaisiin lähettää suoraan saman olion
dispatch-proseduurille, eli go-to-floor!-proseduurin (ask self
'go-up!) voitaisiin korvata (ask dispatch 'go-up!):lla, mutta tällöin
displaying-elevator ei näyttäisi hissin liikkeitä go-to-floor!:lla
liikuttaessa.

Displaying-elevator-olio toimii näin:

> (define e (make-displaying-elevator 1 5))
> (ask e 'get-floor)
1
> (ask e 'go-up!)
going up
> (ask e 'get-floor)
2
> (ask e 'go-to-floor! 5)
going up
going up
going up
done
> (ask e 'get-floor)
5

Tee carrying-elevator-olio, joka perii better-elevator-olion ja lisää
siihen seuraavien viestien käsittelyn (ce viittaa tekemääsi olioon,
esim. (define ce (make-carrying-elevator 1 5))):
 * viesti (ask ce 'people-in! n) lisää hissiin n ihmistä
 * viesti (ask ce 'people-out! n) ottaa hissistä pois n ihmistä
 * viesti (ask ce 'get-people-count) palauttaa kokonaisluvun, joka
   kertoo, montako ihmistä hississä tällä hetkellä on
Hississä on aluksi 0 ihmistä.

Tee proseduuri make-carrying-elevator täydentämällä seuraavaa runkoa:

(define (make-carrying-elevator min-floor max-floor)
  (let ((parent (make-better-elevator min-floor max-floor))
	<??>)
    <??>
    (define (dispatch m)
      <??>)
    dispatch))

Saat ladattua tehtävänannossa esiintyvän koodin Scheme-tulkille
evaluoimalla (load-course-extension "elevator-objects"). Jos haluat, voit
kopioida load-course-extensionin lataaman koodin itsellesi evaluoimalla esim.
(copy-course-extension "elevator-objects" "elevator-objects.scm"), joka siis
kopioi koodin tiedostoon elevator-objects.scm Scheme-tulkin nykyiseen
hakemistoon.

Palauta vastauksena vain tekemäsi make-carrying-elevator-proseduurin
määrittely (ei siis tehtävänannossa olevaa koodia).

=> Tehtävä 4 <=
partial-sums
------------

Tee kirjan tehtävä 3.55 sivulta 331. Palauta vastauksena tekemäsi
partial-sums-proseduurin määrittely.

Voit käyttää apuna kirjassa määriteltyjä virtojenkäsittelyfunktioita,
joita voit ladata Scheme-tulkkiin evaluoimalla (load-course-extension
"streams"). Näiden funktioiden määritelmiä ei tarvitse palauttaa
palautusjärjestelmälle.

=> Tehtävä 5 <=
pairs-muunnelma
---------------

Kirjassa oleva (pairs integers integers)-virta tuottaa
kokonaislukupareja varsin omalaatuisessa järjestyksessä. Tee
integer-pairs-niminen ääretön virta, jossa on kaikki kokonaislukuparit
seuraavassa järjestyksessä:
(0, 0) (0, 1) (1, 0) (0, 2) (1, 1) (2, 0) (0, 3) (1, 2) (2, 1) (3, 0) ...

Lisää halutusta järjestyksestä: Kokonaislukupareja voidaan ajatella
poimittavaksi äärettömästä taulukosta:

      x=0       1       2       3     ...
    +---------------------------------
y=0 | (0, 0)  (1, 0)  (2, 0)  (3, 0)  ...
  1 | (0, 1)  (1, 1)  (2, 1)  (3, 1)  ...
  2 | (0, 2)  (1, 2)  (2, 2)  (3, 2)  ...
  3 | (0, 3)  (1, 3)  (2, 3)  (3, 3)  ...
 ...       . . .          . . .

Pyydetyssä järjestyksessä otettaisiin taulukosta ensin kulma (0, 0),
sitten sen vierestä vinorivi (0, 1), (1, 0), sitten seuraava vinorivi
(0, 2), (1, 1), (2, 0) ja niin edelleen.

Tässä tehtävässä, kuten kirjan pairs-virrassa, "pari" on
kaksialkioinen lista (0 1) eikä (0 . 1).

Palauta vastauksena tekemäsi integer-pairs-virran määritelmä.

Voit käyttää apuna kirjassa määriteltyjä virtojenkäsittelyfunktioita,
joita voit ladata Scheme-tulkkiin evaluoimalla
(load-course-extension "streams"). Näiden funktioiden määritelmiä
ei tarvitse palauttaa palautusjärjestelmälle.

=> Tehtävä 6 <=
Interaktiivista funktionaalista ohjelmointia
--------------------------------------------

Schemessä on read-primitiivi, joka lukee käyttäjältä jonkin alkion
(esimerkiksi numeron) ja palauttaa sen. Tätä ja displayta käyttäen
voidaan tehdä interaktiivisia ohjelmia.

Schemen display-, newline- ja read-proseduureilla on siis
sivuvaikutuksia (näytölle tulostus ja näppäimistön lukeminen), eivätkä
ne siten ole funktionaalisia. Niissä onkin periaatteessa samoja
ongelmia kuin set!:n käytössä; esimerkiksi eri display-kutsujen
järjestykseen täytyy kiinnittää huomiota.

Virtoja apua käyttäen interaktiivisia ohjelmia voidaan tehdä
funktionaalisesti. Esimerkkinä ohjelma, joka ottaa käyttäjältä lukuja
ja tulostaa niiden neliöjuuret:

(define (run-io io-proc)
  (define (get-input-stream)
    (cons-stream (delay (read)) (get-input-stream)))
  (define (display-output-stream stream)
    (if (stream-null? stream)
	'end
	(begin
	  (display (stream-car stream))
	  (newline)
	  (display-output-stream (stream-cdr stream)))))
  (display-output-stream (io-proc (get-input-stream))))

(define (io-sqrt input-stream)
  (cons-stream
   "Enter a number or q to quit:"
   (let ((input (force (stream-car input-stream))))
     (if (eq? input 'q)
	 the-empty-stream
	 (cons-stream
	  "The square root is:"
	  (cons-stream
	   (sqrt input)
	   (io-sqrt (stream-cdr input-stream))))))))

(run-io io-sqrt)

Tämä ohjelma toimii näin:

> (run-io io-sqrt)
Enter a number or q to quit:
5
The square root is:
2.2360679774998
Enter a number or q to quit:
81
The square root is:
9
Enter a number or q to quit:
q
end

Jos run-io:n ajatellaan olevan kielen primitiivi, sitä käyttävät
ohjelmat voivat olla täysin funktionaalisia mutta kuitenkin
interaktiivisia. (Proseduuri, jonka run-io ottaa argumentikseen,
laskee funktion, joka muuttaa virran näppäimistöltä luettuja alkioita
virraksi näytölle tulostettavia alkioita, eikä tämän laskemisessa
tarvita sivuvaikutuksia.)

Koodissa olevista delaysta ja forcesta päästäisiin eroon, jos virrat
olisivat sellaisia, että myös stream-car olisi viivytetty (delayed),
tai ohjelmointikieli käyttäisi laiskaa laskentaa kuten kirjan luvussa
4.2.

Tee tässä esitetyllä tavalla funktionaalinen ohjelma, joka pyytää
kaksi lukua ja antaa vastaukseksi niiden tulon, ja toistaa tätä kunnes
käyttäjä antaa q:n. Nimeä proseduurisi io-productiksi ja tee se niin,
että ohjelman voi käynnistää evaluoimalla (run-io io-product). Et siis
saa kutsua readia etkä displayta suoraan!

Kokeillaksesi ratkaisuasi voit ladata run-io-proseduurin
Scheme-tulkkiin evaluoimalla (load-course-extension "run-io").

Palauta vastauksena vain tekemäsi proseduurin määritelmä (ei siis
run-io:ta).

=> Tehtävä 7 <=
Y-operaattori
-------------

Katso kirjan tehtävien 4.20 ja 4.21 tehtävänantoja (näitä tehtäviä ei
kuitenkaan tarvitse tehdä!). Kertomaproseduurin voisi siis määritellä
näin, niin että määrittely ei ole rekursiivinen:

(define (factorial nn)
  ((lambda (n)
     ((lambda (fact)
	(fact fact n))
      (lambda (ft k)
	(if (= k 1)
	    1
	    (* k (ft ft (- k 1)))))))
   nn))

Tässä määrittelyssä ei siis viitata määriteltävään proseduuriin (eli
factorial-sanaa ei esiinny määrittelyn sisällä) eikä siellä ole
sisäisiä määrittelyjä (ei defineitä eikä letrec-rakenteita).

Tee samaan tyyliin proseduuri count-leaves, joka toimii kuten kirjan
sivulla 109 oleva count-leaves, mutta määrittely ei viittaa itseensä
eikä sisällä sisäisiä määrittelyjä.

Yleistä lisäksi tätä menetelmää tekemällä proseduuri nimeltä y, jonka
avulla em. factorial-proseduurin voisi määritellä näin:

(define factorial
  (y (lambda (ft k)
       (if (= k 1)
	   1
	   (* k (ft ft (- k 1)))))))

Saman y:n pitäisi toimia mille tahansa yhden argumentin
rekursiiviselle proseduurille. Esimerkiksi kirjan sivun 37
fib-proseduurin voisi määritellä y:n avulla näin:

(define fib
  (y (lambda (fib n)
       (cond ((= n 0) 0)
	     ((= n 1) 1)
	     (else (+ (fib fib (- n 1))
		      (fib fib (- n 2))))))))

Tällainen y on yksi versio tehtävän 4.21 alaviitteessä mainitusta
"Y-operaattorista".

Palauta vastauksena tekemäsi määrittelyt proseduureille count-leaves
ja y. Count-leaves ei saa käyttää y:tä.

=> Tehtävä 8 <=
Silmukkarakenne
---------------

Lisää SICP:in luvun 4.1 metasirkulaariseen tulkkiin seuraavanlainen
toistorakenne:

(for (<var> <min-value> <max-value> <step>) <body>)

missä <var> on muuttuja, <min-value>, <max-value> ja <step> ovat
kokonaislukuja. <body> koostuu yhdestä tai useammasta
Scheme-lausekkeesta. For-silmukka luo uuden sidoksen muuttujalle <var>
ja asettaa <var>:n alkuarvoksi <min-value>. Jokaisella silmukan
kierroksella muuttujan <var> arvoa kasvatetaan <step>:n osoittaman
luvun verran kunnes <var> on suurempi kuin <max-value>. Tällöin
silmukkarakenne loppuu. For-rakenteen paluuarvo on määrittelemätön.

Esimerkiksi

;; laskee kertoman
(define (fact n)
 (let ((result 1))   ; olettaa että tulkkiin on toteutettu let
  (for (i 0 n 1)
    (set! result (* result i)))
  result))


;; tulostaa luvut 0, 2 ja 4 eri riveillä
(for (i 0 5 2)
 (display i)
 (newline))

(define i 5)
(display "i: ") (display i) (newline)
(for (i 0 1 1)
 (display "i: ") (display i) (newline))
(display "i: ") (display i) (newline)

Tämä esimerkki tulostaa:
i: 5
i: 0
i: 1
i: 5

Leksikaalisesta ylempänä olevan i:n sidoksen arvoa ei siis saa
muuttaa.

Palauta Scheme-robolle kaikki ne proseduurit jotka lisäsit tai
muokkasit metasirkulaarisesta tulkista.

Voit kopioida kirjassa olevan metasirkulaarisen tulkin koodin
itsellesi muokattavaksi evaluoimalla (copy-course-extension "m-eval"
"m-eval.scm"), joka kopioi koodin Scheme-tulkin nykyiseen hakemistoon
tiedostoon m-eval.scm. Tulkin voi käynnistää evaluoimalla tiedoston
lopussa olevat kaksi kommentoitua riviä.

=> Tehtävä 9 <=
Sisäiset määrittelyt
--------------------

Tee kirjan tehtävät 4.6 ja 4.16. Tekemäsi muutosten tulee siis
vaikuttaa niin, että esimerkiksi tehtävän 4.19 tehtävänannossa oleva
lauseke antaa metasirkulaarisessa tulkissa järkevän virheilmoituksen
(esim. "Variable has no value") Schemen error-primitiiviä käyttäen.

Voit kopioida kirjassa olevan metasirkulaarisen tulkin koodin
itsellesi muokattavaksi evaluoimalla (copy-course-extension "m-eval"
"m-eval.scm"), joka kopioi koodin Scheme-tulkin nykyiseen hakemistoon
tiedostoon m-eval.scm. Tulkin voi käynnistää evaluoimalla tiedoston
lopussa olevan kommentoidun rivin.

Palauta vastauksena tekemäsi uusien proseduurien ja muuttamasi
eval-proseduurin määrittelyt (eli kaikki mitä muutit kopioidusta
koodista). Palauta siis kaikki mikä muuttui alkuperäisestä
m-eval-koodista eli myös tehtävää 4.6 varten tekemäsi muutokset.

=> Tehtävä 10 <=
define-macro
------------

Makrot ovat LISP-tyyppisissä kielissä sellaisia erikoismuotoja, joita
kutsuttaessa argumentteja ei evaluoida, vaan ne annetaan sellaisenaan
makrolle (vrt. proseduurit).

Makrojen avulla on helppo määritellä uusia johdettuja lausekkeita
(derived expressions) ilman että tulkkia tarvitsee muokata.
Esimerkiksi kertoman laskeva proseduuri voidaan määritellä näin
käyttäen eräänlaista unless-erikoismuotoa:

(define (factorial n)
 (unless (= n 1)
         (* n (factorial (- n 1)))
         1))

Tätä unless-erikoismuotoa ei ole vielä implementoitu tulkkiin. Se
voitaisiin toteuttaa muokkaamalla metasirkulaarista tulkkia tai
käyttäen erikoismuotoa define-macro:

(define-macro (unless condition usual-value exception-value)
 (list 'if condition exception-value usual-value))

(Huomaa, että primitive-procedures listaan tulee lisätä
list-primitiivi, jotta em. esimerkki toimisi.)

Makrot lavennetaan siten, että lauseke korvataan toisella
lausekkeella, joka evaluoidaan normaalisti. Esimerkiksi määritellään
em. unless-makro ja factorial proseduuri metasirkulaariseen tulkkiin
ja evaluoidaan (factorial 5).

Tällöin tulkki korvaa unless-lausekkeen määritellyllä if-lausekkeella
ja vasta tämän jälkeen evaluoi lausekkeen normaalisti. Tätä kutsutaan
makrolavennukseksi (macro expansion).

Huom! Makrojen avulla voi ohjelmasta tulla hyvin vaikeaselkoinen ja
yleensä niiden käyttöä kannattaa välttää.

Toteuta erikoismuoto define-macro sekä muu tarvittava tuki makroille
metasirkulaariseen tulkkiin. Palauta vain ne proseduurit, joita
muokkasit. Älä kuitenkaan palauta primitive-procedures-listan
määrittelyä.