=> Tehtävä 1 <=
Korkeamman kertaluvun proseduurit
---------------------------------

Tee kirjan tehtävä 2.33 sivulta 119. Käytä tehtävänannossa annettuja
runkoja, mutta määrittele proseduurien nimiksi: my-map, my-append ja
my-length.

Proseduurit map, append ja length voidaan määritellä suoraan tai, kuten
tässä tehtävässä, jonkin yleiskäyttöisemman proseduurin avulla. Tehtävässä
määriteltyjä my-map, my-append ja my-length kutsutaan korkeamman
kertaluvun proseduureiksi.

Palauta tekemäsi my-map, my-append ja my-length funktioiden
määrittelyt.

Älä käytä sivuvaikutuksellisia primitiivejä set!, set-car!, set-cdr!
ym. tässä tehtävässä.

=> Tehtävä 2 <=
Infix- vs. prefix-notaatio konvertteri
--------------------------------------

Toteuta proseduuri (infix->prefix e), joka muttaa infix-notaatiossa
olevan aritmeettisen lausekkeen prefix-notaation. Aritmeettiset
lausekkeet koostuvat numeroista, suluista sekä operaatioista  +,-,*,/

Toteuttavan kieliopin tulee olla muotoa (esitettyä BNF-syntaksia,
ks esim. http://en.wikipedia.org/wiki/Backus-Naur_form):

  E  ::= TE'
  E' ::= +TE' | -TE' | e
  T  ::= FT'
  T' ::= *FT' | /FT' | e
  F  ::= I | (E)
  I  ::= <Integer>

Merkintä 'e' tarkoittaa tyhjää lausekketta, eli sitä että kyseinen
sääntö ei enää jatku.

Mieti aluksi kieliopin avulla vaikka kynällä ja paperilla, miten jokin
aritmeettinen lauseke jäsennetään. Pystytkö määrittelemään
jäsentämisen niin formaalisti, että voit tehdä siitä
tietokoneohjelman.

Esimerkkejä:

> (infix->prefix '(1 - 2))
(- 1 2)
> (infix->prefix '(1 - 2 - 3))
(- (- 1 2) 3)
> (infix->prefix '(1 * 2 - 3))
(- (* 1 2) 3)
> (infix->prefix '(1 * 2 / 3))
(/ (* 1 2) 3)
> (infix->prefix '(1 + 2 / 3))
(+ 1 (/ 2 3))
> (infix->prefix '(1 * 2 - 3))
(- (* 1 2) 3)
> (infix->prefix '(1 * 2 - 3 - 5 - 6))
(- (- (- (* 1 2) 3) 5) 6)
> (infix->prefix '(1 * 2 + 3 - 5 + 6))
(+ (- (+ (* 1 2) 3) 5) 6)
> (infix->prefix '(1 / 2 / 3 / 5 / 6))
(/ (/ (/ (/ 1 2) 3) 5) 6)
> (infix->prefix '(1 / 2 / 3))
(/ (/ 1 2) 3)
> (infix->prefix '(1 / (2 / 3)))
(/ 1 (/ 2 3))

Palauta tekemäsi infix->prefix-proseduurin määrittely.

Pystytkö tekemään ratkaisustasi sellaisen, että se ei käytä
sivuvaikutuksia ollenkaan?

Tämä tehtävä saattaa olla aika hankala, jos jäsentimet eli parserit
eivät ole ennestään tuttuja.
=> Tehtävä 3 <=
Merge sort
----------

Merge sort on kohtuullisen tehokas lajittelualgoritmi, jolla voi
lajitella esimerkiksi listan (5 2 4 3 1 6) alkiot numerojärjestykseen
(1 2 3 4 5 6). Algoritmi toimii siten, että se jakaa lajiteltavan
listan kahtia, lajittelee molemmat puoliskot kutsumalla itseään
rekursiivisesti ja yhdistää lajitellut puoliskot toisiinsa. Rekursio
päättyy, kun yritetään lajitella yhden alkion pituista listaa, jolle
ei tarvitse tehdä mitään. Merge sortin kompleksisuus on O(n log n).

Tässä on lajittelualgoritmin toteutuksen runko:

(define (merge-sort l)
  (define (sort l len)
    (if (= len 1)
        (list (car l))
        (let ((mid (floor (/ len 2))))
	  (merge (sort l mid)
                 (sort (list-tail l mid) (- len mid))))))
  (define (merge l1 l2)
    ;; puuttuu
    )
  (sort l (length l)))

Tässä määritelty sort-proseduuri lajittelee argumentiksi annetun
listan l ensimmäiset len alkiota ja palauttaa uuden listan, jossa nämä
alkiot ovat järjestyksessä. (Schemen floor-primitiivi pyöristää
argumenttinsa alaspäin seuraavaksi pienempään kokonaislukuun ja
list-tailin kutsu palauttaa listan, josta on otettu ensimmäiset mid
alkiota pois.)

Tehtävässä saat täydentää tätä runkoa merge-proseduurilla, joka siis
ottaa argumenteikseen kaksi jo järjestettyä listaa ja palauttaa yhden
listan, jossa on molempien listojen alkiot kasvavassa
numerojärjestyksessä. Esimerkiksi (merge (list 1 5) (list 3 4 6)):n
pitäisi palauttaa lista (1 3 4 5 6).

Voit kopioida em. rungon itsellesi evaluoimalla
(copy-course-extension "merge-sort" "merge-sort.scm"), joka kopioi koodin
Scheme-tulkin nykyiseen hakemistoon tiedostoon merge-sort.scm.

Palauta vastauksena koko täydennetty merge-sort-proseduuri.

=> Tehtävä 4 <=
subsets
-------

Tee kirjan tehtävä 2.32 (s. 113). Tee tehtävä täydentämällä tehtävän-
annossa annettua runkoa. Palauta tekemäsi subsets-proseduurin
määrittely.

=> Tehtävä 5 <=
encode-symbol ja successive-merge
---------------------------------

Tee kirjan tehtävät 2.68 ja 2.69. Kirjan luvussa 2.3.4 esitetyn
Huffman-koodaus -järjestelmän saat kopioitua itsellesi evaluoimalla
(copy-course-extension "huffman" "huffman.scm") Scheme-tulkissa.

Palauta tekemäsi encode-symbol ja successive-merge proseduurien
määrittelyt.

=> Tehtävä 6 <=
zip ja unzip
------------

Määrittele proseduurit zip ja unzip.

Zip ottaa kaksi listaa argumenttieikseen ja palauttaa listan, joka
muodostuu pareista niin että parin ensimmäinen alkio on otettu
ensimmäisestä argumenttilistasta ja toinen toisesta. Esimerkiksi:

 > (zip '(a b c) '(1 2 3))
((a . 1) (b . 2) (c . 3))

Proseduuri unzip ottaa yhden argumentin: listan, joka koostuu pareista
ja palauttaa _listan_, jonka ensimmäinen alkio on argumenttilistan
parien ensimmäisistä alkioista muodostettu lista ja toinen vastaavasti
argumenttilistan parien toisista alkioista muodostettu lista.
Esimerkiksi:

> (unzip '((a . 1) (b . 2) (c . 3)))
((a b c) (1 2 3))

Palauta tekemiesi zip- ja unzip-proseduurien määrittelyt.

=> Tehtävä 7 <=
Symbolinen derivointi
---------------------

Tee kirjan tehtävä 2.56 (s. 150). Toteuta siis luvussa 2.3.2
esiteltyyn symboliseen derivointi -ohjelmaan tehtävänannossa annettu
derivointisääntö.

Esimerkki:
> (deriv '(** x 1) 'x)
1
> (deriv '(** x 3) 'x)
(* 3 (** x 2))

Voit kopioida luvussa esitellyn derivointi-paketin itsellesi
evaluoimalla (copy-course-extension "deriv" "deriv.scm") Niksulan
Scheme-tulkissa.

Palauta vastauksenasi kaikki muokkaamasi ja lisäämäsi proseduurit.

=> Tehtävä 8 <=
Constraint propagation
----------------------

Tee kirjan tehtävä 3.37 sivulta 296. Palauta vastauksena tekemäsi
määrittelyt proseduureille c-, c*, c/ ja cv.

Kokeillessasi tekemiäsi proseduureja voit ladata kirjassa olevan
constraint propagation -järjestelmän koodin (myös tehtävänannossa
olevan c+-proseduurin) Scheme-tulkkiin evaluoimalla (load-course-extension
"constraint").

=> Tehtävä 9 <=
Murtoviivan pituus
------------------

Haluamme tehdä proseduurin, joka ottaa sisään listan pisteitä (piste
on (list x y)) ja laskee niiden kautta piirretyn murtoviivan pituuden
(eli peräkkäisten pisteiden etäisyyksien summan). Sen pitäisi toimia
näin:
> (line-length '((10 0) (0 0) (0 10)))
20
> (line-length '((0 0) (2 2) (4 1) (8 3)))
9.5366310572456

Imperatiiviseen ohjelmointiin tottunut ohjelmoija voisi tehdä sen
näin: (tämä _ei_ ole esimerkki hyvin kirjoitetusta ohjelmasta!)

(define (square x)
  (* x x))

(define (line-length points)
  (let ((sum 0)
	(previous-x (caar points))
	(previous-y (cadar points))
	(rest-of-points (cdr points))
	(x 0)
	(y 0))
    (define (next-point)
      (cond ((not (null? rest-of-points))
	     (set! x (caar rest-of-points))
	     (set! y (cadar rest-of-points))
	     (set! sum (+ sum
			  (sqrt (+ (square (- x previous-x))
				   (square (- y previous-y))))))
	     (set! previous-x x)
	     (set! previous-y y)
	     (set! rest-of-points (cdr rest-of-points))
	     (next-point))
	    (else sum)))		; Return the sum
    (next-point)))

Tee saman asian laskeva ohjelma, joka ei käytä set!:iä. Yritä tehdä
ratkaisustasi mahdollisimman helppolukuinen. Palauta vastauksena
tekemäsi line-length-proseduurin määrittely.

Voit myös miettiä, tuliko tekemästäsi ohjelmasta parempi kuin
ylläoleva. Miksi tai miksi ei? Onko siinä ongelmia, joita ylläolevassa
ohjelmassa ei ole? (Vastauksia näihin kysymyksiin ei tarvitse
palauttaa.)

=> Tehtävä 10 <=
ripple-carry adder
------------------

Tee kirjan tehtävä 3.30 sivulta 278. Toteuta siis kirjan luvussa 3.3.4
esitellyllä digitaalisten piirien simulointijärjestelmää apuna
käyttäen proseduuri (ripple-carry-adder a-list b-list sum carry), joka
implementoi tehtävänannossa määritellyyn binäärilukujen
yhteenlaskupiirin.

Voit käyttää SICP:n luvussa 3.3.4 esiteltyjen proseduurien lisäksi
seuraavia apuproseduureja:

* (make-wire-list n)
  Luo n:n alkion kokoisen listan johtoja.

* (get-list-signal wires)
  Palauttaa listan, jossa on wires-listan sisältämien johtojen arvot.

* (set-list-signal! wires values)
  Asettaa johtolistan wires sisältämien johtojen alkioiden arvoiksi
  values-listan arvot.

* (probe-list name wires)
  Kuten kirjan probe-funktio. Lisää jokaiseen wires-listan johtoon
  "luotaimen."

Nämä ja SICP:n proseduurit saat käyttöösi evaluoimalla Niksulan Scheme-
tulkissa (load-course-extension "ripple-carry").

Huom: Tässä tehtävässä binääriluvut esitetään niin, että vähiten
merkitsevä bitti (Least Significant Bit, LSB) on listan ensimmäinen
alkio ja eniten merkitsevä bitti (Most Significant Bit, MSB) listan
viimeinen!

Esimerkiksi jos lasketaan binäärilukujen 10010 ja 11000 summa. (Tässä
bittijärjestys on vielä normaali eli eniten merkitsevä vasemmalla.)

      1<------------ sisäinen carry
      1 1 0 1 0
    + 1 1 0 0 0
    -----------
    1 1 0 0 1 0
    ^
    |
    +--------------- ulkoinen carry


Tämä lasku voitaisiin tehdä ripple-carry-adder-proseduurilla
seuraavasti

Luodaan ensimmäisen summattavan johtolista ja asetetaan sille arvot:
(define a (make-wire-list 5))
(set-list-signal! a '(0 1 0 1 1))

Luodaan toisen summattavan johtolista ja asetataan sille arvot:
(define b (make-wire-list 5))
(set-list-signal! b '(0 0 0 1 1))

Luodaan tuloksen johtolista:
(define sum (make-wire-list 5))

Luodaan ulkoisen carry:n johto:
(define carry (make-wire))

Kytketään johdot paikoilleen:
(ripple-carry-adder a b sum carry)

Käynnistetään simulaatio:
(propagate)

Haetaan summa-listan arvo:
(get-list-signal sum) => (0 1 0 0 1)

ja carry-bitin arvo:
(get-signal carry) => 1

Tulokseksi saatiin siis lista (0 1 0 0 1) ja carry-bitille arvoksi 1,
eli bittijono 10010 ja ulkoiselle carry-bitille arvo 1, aivan niin
kuin pitikin.

Palauta vastauksenasi vain tekemäsi ripple-carry-adder-proseduurin
määritelmä. Load-course-extension:illa ladattua koodia ei saa
palauttaa! Vastauksia tehtävänannossa esitettyihin kysymykseen
viiveestä ei palauteta. (Voit kyllä miettiä sitä. Keksitkö tavan
laskea bittejä yhteen rinnakkaisesti niin, että viive ei ole näin
suuri?)