=> Tehtävä 1 <=
Sisäiset määrittelyt, lohkorakenne
----------------------------------

Olettakaamme, että henkilön, joka painaa n kg, maksa polttaa
x grammaa alkoholia tunnissa vieläpä siten, että alkoholin
palamisnopeus on vakio ja että lukujen x ja n välillä
vallitsee likimain riippuvuus x = ln(n) * y, missä y olkoon 1.7.

Tee funktio (burning-time x n), joka palauttaa arvonaan sen ajan
tunteina, joka kuluu n-kiloisen henkilön maksalta x gramman
polttamiseen. (Huomaa, että niksulan Scheme-tulkin (log n) palauttaa
tuon toivotun luonnollisen logaritmin, ei siis kymmenkantaista kuten
voisi luulla.)

Laajenna ohjelmaa siten, että teet fuktiot (beer-time m n)
sekä (snaps-time m n), jotka palauttavat vastaavasti
m:n kaljan sekä m:n paukun palamiseen n-kiloiselta henkilöltä
kuluvan ajan. Olettakaamme tässä edelleen, että yksi kalja
on tilavuudeltaan 0,5 l ja vahvuudeltaan 3,5 tilavuusprosenttia,
ja että yksi paukku vastaa 4 cl vodkaa (40 tilavuusprosenttia).
Alkoholin (etanolin) tiheys oletettakoon olevan 0,789 g/cm^3.

Yhdistä vielä edelliset siten, että (total-time b s n) palauttaa
sen ajan, joka n-kiloiselta kuluu b:n kaljan ja s:n paukun
polttamiseen.

Ohjeita: Sijoita "maagiset luvut" 1.7, 0.5, 38 jne let-lauseisiin,
käytä kaavoissa kuvaavia muuttujia. Tehtävänasettelu toivottavasti
pakottaa sinut mahdollisimman modulaariseen ohjelmarakenteeseen.

Toteuta funktiot burning-time, beer-time ja snaps-time
total-time-funktion sisäisinä määrittelyinä. (Ks. SICP luku 1.1.8,
kohta "Internal definitions and block structure", s. 29 - 30.).
Palautuksesi tulee siis koostua vain yhdestä funktiosta total-time,
jonka sisäisinä funktiona muut tehtävänannossa vaaditut funktiot ovat.

Esimerkki:

> (total-time 5 2 70)
13.05451828557916
> (total-time 5 5 70)
18.298174165979155
> (total-time 3 6 70)
16.222560379987492
> (total-time 3 3 70)
10.978904499587493
> (total-time 3 3 50)
11.923197656223113
> (total-time 1 1 50)
3.9743992187410377
> (total-time 1 0 50)
2.0761786963572586

Palauta tekemäsi total-time-funktion määrittely.

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

=> Tehtävä 2 <=
lambda, funktiot paluuarvoina ja argumentteina
----------------------------------------------

Määrittele proseduuri (no-good func x value y), joka palauttaa
1-argumenttisen funktion. Tämä funktio palauttaa funktion func, jos
annettu funktion argumentti on x (x on kokonaisluku), jos annettu
argumentti on y (y on kokonaisluku), palautetaan value. Mikäli
argumentiksi annetaan epätosi, palautetaan funktio, joka palauttaa
luvun 1976. Muulloin palautetaan epätosi #f.

Huom! Tällaiset funktiot, jotka palauttavat erilaisia arvoja ovat
yleensä huonoa ohjelmointityyliä, siitä nimi no-good! Yleensä on
parempi, että funktiot palauttavat arvoja vain samalta arvoalueelta
(mutta tämä sääntö ei ole ehdoton, poikkeuksia on).

Tässä tehtävässä on tarkoitus harjoitella funktioiden käyttöä
argumentteina ja paluuarvoina.

Esimerkki:

> (define ng-1 (no-good (lambda (x) (+ 10 x)) 1 100 5))
> (ng-1 #f)
#<procedure>
> ((ng-1 #f))
1976
> ((ng-1 1) 50)
60
> (ng-1 5)
100
> (define ng-2 (no-good (lambda (x) (- x)) 5 6 7))
> ((ng-2 5) 10)
-10

Palauta tekemäsi no-good-funktion määrittely.

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

=> Tehtävä 3 <=
lambda, jatkoa
--------------

Määrittele proseduuri (compose f g), joka palauttaa funktion, joka
laskee funktioiden f ja g yhdistelmän f(g(x)).

Esimerkki:

> (define (square x) (* x x))
> (define (inc x) (+ x 1))
> ((compose square inc) 6)
49


Määrittele myös proseduuri (double-repeated f g n), missä f ja g ovat
yksiargumenttisia funktioita ja n on kokonaisluku. Funktio
double-repeated laskee funktioiden f ja g toistetun yhdistelmän:

  f(g(...(f(g(x)))...))

Esimerkiksi kutsu ((double-repeated square inc 2) 2) laskee funktion

  (square (inc (square (inc 2)))) => 100.

Palauta tekemäsi compose- ja duoble-repeated-funktioiden määrittelyt.

=> Tehtävä 4 <=
let vs. lambda
--------------

Schemen let-lausekkeet ovat syntaktista sokeria lambda-lausekkeille
eli ne eivät lisää Scheme-kieleen mitään uusia ominaisuuksia, vaan
niiden tarkoitus on helpottaa paikallisten muuttujien määrittelyä.

Kirjoita seuraavat let-lausekkeet ilman let-erikoismuotoa eli
lambda-lausekkeiden avulla (ks. SICP 1.3.2 s. 64 - 65):

(let ((x 1))
 x)

(let ((x 1)
      (y 2))
 (+ x y))

(let ((x (lambda () 1)))
 (x))

(let ((x 1))
 (let ((y x))
  (+ x y)))

(+ (let ((x 3)) x) 4)

(let ()
  1)

Esimerkki:

Lauseke (let ((z (+ 3 4))) (+ z 1)) muodostetaan lambda-lausekkkeen
avulla seuraavasti:

((lambda (z)
  (+ z 1))
 (+ 3 4))

Palauta tehtävänannon let-lausekkeita vastaavat lambda-lausekkeet. Älä
palauta esimerkkiä!


=> Tehtävä 5 <=
Pascalin kolmio
---------------

Tee kirjan tehtävä 1.12. Tee vastaukseksi proseduuri nimeltä
pascal-triangle, joka ottaa argumenteiksi rivin ja sarakkeen ja
palauttaa luvun seuraavan näköisestä Pascalin kolmiosta:

sarake   1 2 3 4 5 ...
-------+--------------
rivi 1 | 1
rivi 2 | 1 1
rivi 3 | 1 2 1
rivi 4 | 1 3 3 1
rivi 5 | 1 4 6 4 1
...         ...

Muista kokeilla ratkaisuasi! Esimerkiksi (pascal-triangle 5 3):n
pitäisi palauttaa 6 (viidennen rivin kolmas sarake).

Kun olet tehnyt tehtävän, tutkitaan hieman, miten se toimii. Kurssilla
käytetystä Scheme-tulkista löytyy primitiivi trace, jota voi käyttää
proseduurikutsujen debuggaukseen. Tässä ensin esimerkki tracen
käytöstä rekursiivisen kertomaproseduurin tutkimisessa:

> (define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))
> (fact 5)
120
> (trace fact)
> (fact 5)
| > (fact 5)
| | > (fact 4)
| | | > (fact 3)
| | | | > (fact 2)
| | | | | > (fact 1)
| | | | | | > (fact 0)
| | | | | | 1
| | | | | 1
| | | | 2
| | | 6
| | 24
| 120
120

Trace siis ottaa argumentikseen definellä määritellyn proseduurin, ja
muuttaa sitä niin, että se aina kutsuttaessa näyttää argumenttinsa ja
tuloksensa siten, että rekursiiviset kutsut näkyvät selkeästi. Untrace
poistaa tracen tekemän muutoksen.

Kokeile nyt tracea tekemäsi pascal-trianglen kanssa. Evaluoi (trace
pascal-triangle) ja katso, mitä esimerkiksi Pascalin kolmion viidennen
rivin keskimmäisen alkion laskeminen näyttää.

Palauta vastauksena vain tekemäsi pascal-triangle-niminen proseduuri.

=> Tehtävä 6 <=
dotted-tail
-----------

Scheme-kielen primitiivit +, * ja list ottavat mv. määrän
argumentteja. Ohjelmoija voi määritellä itse vastaavanlaisia
proseduureja käyttämällä ns. dotted tail -notaatiota määritellessään
proseduuria.

Esimerkiksi:

Suoritetaan tulkille seuraava määritelmä:
(define (f x y . z)
  (list 'x: x 'y: y 'z: z))

Nyt kutsutaan funktiota f seuraavasti:
> (f 1 2 3 4 5)
(x: 1 y: 2 z: (3 4 5))

Eli nähdään, että x:llä on f:n rungossa arvo 1, y:llä 2 ja z on lista,
jonka alkiot ovat 3, 4 ja 5.

Piste voi olla myös ennen ensimmäistä argumenttia:
(define (f . z)
  (list 'z: z))

Tällöin saadaan:
> (f)
(z: ())
> (f 1 2)
(z: (1 2))

Ensimmäisessä tapauksessa proseduuria f kutsuttiin ilman argumentteja,
jolloin z:n arvoksi tuli tyhjä lista. Toisessa tapauksessa
argumentteina oli 1 ja 2 ja lista z sai arvokseen (1 2).

Katso myös SICP s. 104 tehtävä 2.20, huomaa erityisesti
alaviitteessä 11 mainittu dotted-tail syntaksi lambda-lausekkeille.

Määrittele proseduuri less-than, joka ottaa vähintään yhden
numero-argumentin ja palauttaa listan, joka sisältää ne muina
argumentteina annetut luvut, jotka ovat pienempiä kuin ensimmäinen
argumentti.

Esimerkki:
> (less-than 5 1 7 3 6)
(1 3)
> (less-than 1 10 -5 15 -10)
(-5 -10)

Määrittele myös proseduuri remove-if, jonka ensimmäinen argumentti on
predikaattiproseduuri. Proseduuri muodostaa listan muista annetuista
argumenteista siten, että niitä alkioita joille predikaattifunktio
palauttaa toden, ei oteta mukaan (vrt. filter). Proseduurin tulee
tarkistaa, että sille annetaan vähintään yksi argumentti ja että tämä
argumentti on proseduuri (käytä procedure? primitiivipredikaattia).
Jos argumentti ei ole proseduuri, annetaan virheilmoitus käyttäen
error-primitiiviä.

Esimerkki:
> (remove-if odd? 1 2 3 4)
(2 4)
> (remove-if negative? 1 -2 3 -4)
(1 3)
> (remove-if number?)
()
> (remove-if symbol? 1 2 'a 'c '(+ 1 2))
(1 2 (+ 1 2))
> (remove-if)
remove-if: invalid number of arguments
> (remove-if 1)
remove-if: first argument must be a procedure

Proseduuri remove-if on yleiskäyttöisempi kuin less-than eli
remove-if:n avulla voidaan määritellä less-than. Toisinaan on hyvä
idea pyrkiä määrittelemään hyvin yleiskäyttöisiä proseduureja; tällöin
vältetään samanlaisen koodin toistoa. Miten määrittelet less-than
proseduurin remove-if:in avulla?

Palauta tekemäsi proseduurien remove-if ja less-than määrittelyt.

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

=> Tehtävä 7 <=
Auto erämaassa
--------------

Auto pystyy ottamaan mukaansa polttoainetta k * 100 km:n matkalle.
Ylitettävänä on erämaa, jonka pituus on n * 100 km. Reitin varrelle on
asetettu tyhjiä tarpeeksi suuria säiliöitä 100 km:n välein
välivarastojen rakentamiseksi. Auton on erämaan ylipäästäkseen
rakennettava sopivat varastot.

Tee proseduuri nimeltä total-trip, joka ottaa argumenteikseen n:n ja
k:n ja laskee auton kokonaismatkan (satoina kilometreina). Jos
annetuilla parametreilla n, k auto ei pääse lainkaan perille,
proseduurin tulee palauttaa nolla (0).

Esimerkki tehtävän ratkaisusta hyvin yksinkertaisessa tapauksessa:

L |---o---o---o---| M    n = 4, o = asema, L = lähtö, M = maali

Autoon mahtuu kolmen välimatkan verran bensiiniä (k = 3).

Auto tekee ilmeisesti seuraavat matkat: (numerot kuvaavat asemilla
olevan polttoaineen määrää)

1. Auto vie ensimmäiselle asemalle bensaa 100 km matkaa varten ja
   palaa lähtöpaikkaansa.

   |---1---0---0---|

2. Auto ajaa ensimmäiselle asemalle, täyttää tankin sieltä
   uudelleen ja ajaa maaliin.

Esimerkin perusteella (total-trip 4 3):n pitäisi siis palauttaa 6
(matkan kokonaispituus on 600 km, joka on 6 kpl satoja kilometrejä).

Palauta vastauksena tekemäsi total-trip-proseduuri.

(Huom. Ratkaisu on varsin lyhyt: se mahtuu 15-25 riviin koodia. Mieti
tehtävää kunnolla ennen kuin alat kirjoittamaan koodia.)


=> Tehtävä 8 <=
Korvausmalli, iteratiivinen ja rekursiivinen prosessi
-----------------------------------------------------

Tee kirjan tehtävä 1.9. Proseduurien dec ja inc lavennusta ei näytetä,
mikäli ne voidaan laskea heti. Näytä evaluoinnin tulos askelittain
täydentämällä seuraavaa runkoa:

(+ 4 5)
(inc (+ 3 5))
...
...
...
...
...
...
...
9
(+ 4 5)
...
...
...
...
9


Ensimmäisesta (+ 4 5) lausekkeesta alkaa tehtäväannossa ensimmäisenä
määritellyn +-proseduurin evaluointi. Toisesta (+ 4 5) lausekkeesta
vastaavasti toisen +-proseduurin evaluointi.

Tehtävänannossa esitettyihin kysymyksiin ei tarvitse vastata. Palauta
vain em. runko täydennettynä vastauksillasi.

=> Tehtävä 9 <=
Listan läpikäynti
-----------------

Määrittele proseduurit every-second, every-third ja every-nth, jotka
poimivat listasta joka toisen, kolmannen ja n:nnen alkion.

> (every-second (list 1 2 3 4 5 6 7 8 9))
(2 4 6 8)
> (every-third (list 1 2 3 4 5 6 7 8 9))
(3 6 9)
> (every-nth 4 (list 1 2 3 4 5 6 7 8 9))
(4 8)

Palauta tekemiesi every-second-, every-third- ja every-nth-proseduurien
määrittelyt. Mieti myös, miten every-nth-proseduurilla voidaan
määritellä proseduurit every-second ja every-third.

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

=> Tehtävä 10 <=
Kokonaislukuparit
------------------


Olkoon (x,y) kokonaislukupari, joka on suorakaiteen 0 <= x <= M,
0 <= y <= N sisällä. Tee ohjelma, joka ottaa positiiviset
kokonaislukuparametrit M, N, a, b, ja c ja palauttaa
kokonaislukuparien (x,y) määrän, jotka toteuttavat yhtälön

a*x^2 + b*y^2 = c^2.

Esimerkkejä: (pairs M N a b c)

(pairs 100 100 4 4 40)
==> 4

(pairs 100 200 7 1 121)
==> 3

(pairs 0 100 4 4 40)
==> 1

(pairs 4 -5 9 9 100)    ; Tyhjä suorakaide
==> 0

(pairs 100 100 0 4 10)
==> 101

Palauta tekemäsi pairs-funktion määrittely.

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