Üles Järgmine

Peatükk 1  Haskelli tutvustus

1.1  Motivatsioon

Haskell on moderne üldotstarbeline programmeerimiskeel millele on aja jooksul lisatud väga erinevaid võimalusi ja omadusi. Keele õppimisel vaatame kõigepealt selle kõige põhilisemaid osi — neid kirjeldavad programmeerimiskeele peamised omadused. Haskell on

Järgnevalt vaatamegi lühidalt, mis need mõisted tähendavad ning millega selliseid valikuid põhjendada.

Funktsionaalne keel

Kõik üldotstarbelised keeled võimaldavad defineerida funktsioone — kuigi neid võidakse nimetada teise nimega, näiteks meetod, protseduur või operaator. Igal juhul on võimalik mingitele operatsioonide kogule anda uus nimi ning seda hiljem välja kutsuda.

Mõni keel raskendab funktsioonide kasutamist: Java-s tuleb defineeritavad funktsioonid pakendada mingi klassi sisse. Näiteks võime vaadata, kuidas erinevates keeltes arvutada arvude 4 ja 7 maksimumi:

Pane Tähele! Haskellis kirjutatakse funktsiooni argumendid lihtsalt funktsiooni järele ja lisasulge panna vaja ei ole. Hiljem näeme, miks see kasulik on.

Funktsiooniga koos kasutatakse tihti mõistet abstraktsioon, kuna maksimumi leidmise täpne definitsioon pole meile oluline. Sellisel juhul öeldakse, et maksimumi leidmine on välja abstraheeritud.

Funktsionaalsed programmeerimiskeeled eelistavad uute vahendite lisamise asemel olemasolevate abstraktsioonivahendi (e. funktsiooni) üldistamist. Näiteks Haskelli keeles ei ole tarvis if lauset, kuna igaüks saab defineerida funktsiooni, millega seda asendada saab.

kui True t e = t kui False t e = e

Üks viis, kuidas Haskellis funktsioone defineerida on läbi võrduste. Siin defineeritakse kolme argumendiga funktsioon kui, mis tagastab teise argumendi t, kui esimene on True ja kolmanda argumendi e, kui esimene on False.

Pane Tähele! Haskellis algavad muutujanimed (sh funktsioonid) väikese tähega ja andmekonstruktorid (näiteks True ja False) ja tüübid suure algustähega. (Andmekonstruktoritest ja tüüpidest tuleb juttu õige pea.)

Programmeerimise algõppes on tavaks esitleda programme sarnaselt klassikalisele Turingi masinale: programm on staatiline ja andmed dünaamilised. Samas tänapäevased arvutiarhitektuuris on hoopis sarnased universaalsete Turingi masinatega, kus nii programm kui andmed on samas klassis. See ongi funktsionaalse programmeerimise üks põhimõte: samamoodi, kuidas programmeerimiskeeles saab käsitleda andmeid, peab saama käsitleda ka alamprogramme.

Seetõttu käib funktsionaalse programmeerimise juurde kindlasti võimalus kasutada kõrgemat järku funktsioone ehk funktsioone, mis võtavad argumentideks teisi funktsioone. Näiteks, kui meil on täisarvude järjent [2,3,4] aga me tahame sellest teha järjendit, kus kõik arvud, mis on väiksemad kui 3, asendataks arvuga 3. Seda saame teha kõrgemat järku funktsiooniga map, mis võtab esimese argumendina funktsiooni, mida kõigile järjendi elementidele rakendada. Sümbol ⇝ tähistab arvutusprotsessi s.t. vasakpoolsest avaldisest saadakse arvutusprotsessi käigus parempoolne.

     
map (max 3) [2,3,4]⇝  [max 3 2, max 3 3, max 3 4] ⇝  [3,3,4]          

Kõrgemat järku funktsioonid võimaldavad meil programmi osadest mõelda kõrgemal abstraktsiooni tasemel ehk siis suuremate tükkidena.

Funktsionaalsed programmeerimiskeeled liigituvad enamasti deklaratiivse paradigma alla. Erinevalt imperatiivsest paradigmast, kus arvutus on sammude või instruktsioonide järjest rakendamine, defineeritakse deklaratiivse paradigma puhul tulemus, mida süsteemil on vaba voli erinevat viisi arvutada. Seetõttu on deklaratiivse programmi alamosadest tihtipeale lihtsam aru saada, kuna programmi alamosade sõltuvused on selgemad. Sellist suuremat selgust nimetatakse ajaloolistel põhjustel miskipärast ilmutatud viidatavuseks.

Tugevalt ja staatiliselt tüübitud

Esmapilgul võib tunduda, et mida rohkem programmeerimiskeel lubab seda parem. Tegelikult see nii siiski pole. Võtame näiteks PDF (Portable Document Format) keele ja PS (PostScript) keele. Aastal 1982 loodi programmeerimiskeel PS, väljendamaks printeri poolt trükitavat dokumenti. Üksteist aastat hiljem võeti sama otstarbe jaoks kasutusele PDF, mille peamine erinevus võrreldes PostScriptiga on tsüklite ja globaalsete muutujate puudumine. Tänu sellele on võimalik suure PDF faili viimast (või ükskõik millist) lehekülge trükkida või vaadata ilma eelnevaid lehekülgi arvutamata/joonistamata. Vahemärkusena nendime, et Haskellis puuduvad nii globaalsed kui ka lokaalsed muutujad.

Üks võimalus keele võimsust piirata on seda teha tüübisüsteemiga. Kui PDF keele puhul oli eesmärgiks jõudluse suurendamine (ehk odavamate protsessorite kasutamine printerites) siis Haskelli puhul on hoopis soov vähendada vigade hulka programmis.

Staatiline tüübikontroll tehakse kompileerimise (või interpreteerimise) käigus ning tüübivea puhul väljastatakse sellesisuline teade. Näiteks, kui programmi mingis osas on vaja kasutada täisarvu aga programmeerija kirjutab sinna sõne, siis kompilaator näeb seda viga. Dünaamilise tüübikontrolli puhul tuleb tüübiviga välja alles programmi (mitte kompilaatori) töö käigus. Tugevalt tüübitud keele puhul väljastatakse kohe veateate aga nõrgalt tüübitud keele võib püüda sõnet arvuks teisendada.

Tugevalt ja staatiliselt tüübitud keeled on kõige rohkem piiratud ning nad “tülitavad” programmeerijat kõige rohkem — pakkudes samas kõige rohkem turvalisust. Seetõttu on Haskelli programmide testimise vajadus mingil määral väiksem.

Puhas keel

Haskell on puhas funktsionaalne keel, mis tähendab et selles keeles defineeritavad funktsioonid on kõrvaltoimevabad ehk funktsiooni kutse tulemus sõltub ainult parameetrite väärtustest. Selline keele omadus lihtsustab oluliselt testimist, kuna seetõttu saab igat funktsiooni testida teistest eraldi.

Puhtuse nõude pahupooleks on aga see, et mittepuhtaid funktsioone, nagu juhuarvude genereerimine, pole võimalik funktsioonidena defineerida. Mittepuhtaid arvutuste jaoks on vaja kasutada monaade, millest varsti juttu teeme.

Laisk keel

Kõige rohkem eristab Haskelli teistest populaarsetest keeltest tõsiasi, et Haskell on laisk keel. Kui agarates keeltes arvutatakse funktsioonikutse argumendid enne funktsiooni kutsumist väärtusteks, siis laisa keele puhul lükatakse argumentide väärtustamist edasi nii kaua kui võimalik. Ning kui tuleb välja, et argumenti polnudki vaja, siis seda ei arvutatagi.

Näiteks, olgu meil selline funktsioon, mis iga argumendikorral tagastab arvu 5:

tagastaViis x = 5

Sellisel juhul vajaks agar väärtustamine kaks sammu:

     
  tagastaViis (1+1)   
agar
 
   tagastaViis 2   
agar
 
   5 ,
          

aga laisk ainult ühe sammu:

     
  tagastaViis (1+1)   
laisk
 
   5 .
          

Laisk väärtustamine võimaldab teha arvutusi lõpmatute järjenditega, kui hiljem läheb sellest järjendist vaja ainult lõplik osa. Näiteks saab Haskellis defineerida lõpmatu järjendi kõikidest algarvudest ning seejärel võtta sellest sada esimest.

1.2  Lihtsate programmide arendamistsükkel

Haskelli õppimisel kasutame interaktiivset keskkonda GHCi, mille paigaldamisest ja käivitamisest on juttu peatükis ??. Võtke lahti käsurida, kus te saate hiljem GHCi-d käivitada, ning samal ajal ka tekstiredaktor oma programmi lähtekoodiga. Lähtekoodiks võtame näiteks fail nimega Ex1.hs kus on järgnev kood:

arv = 5 tekst = "Tere"

Järgnevalt salvestage failis tehtud muudetused, avage käsurealt GHCi ning laadige sinna enda fail. Interaktiivse keskkonna käivitamiseks ja faili Ex1.hs avamiseks piisab enamasti kas “ghci Ex1.hs” või “stack ghci Ex1.hs” kirjutamisest käsureale. Seejärel saate failis olevaid definitsioone testida, kirjutades avaldisi mis definitsioone kasutavad. Näiteks:

Ok, modules loaded: Main. *Main> 2*arv+5 15 *Main> 3*arv-5 10 *Main> tekst "Tere" *Main> tekst ++ " hommikust!" "Tere hommikust!"

Enda kogemuse põhjal võime kinnitada, et Haskelli õppimiseks on vaja ise programme kirjutada, ise testida, vigu teha ja enda vigadest õppida. Kirjutage GHCi-s avaldisi või programmifailis deklaratsioone ja uurige, mis on tulemus! Millised veateated tekivad? Miks?

GHCi trükib algsel käivitamisel enda kohta infot, sealhulgas versiooni numbri. Niikaua kui trükitud ridade seas on ka “Ok, modules loaded: Main.” v.m.s. peaks kõik olema korras ja te ei ole kohustatud ülejäänud infot dešifreerimia.

Nüüd lisage faili selline definitsioon “liidaArv x = arv + x”. Selle definitsiooni testimiseks GHCi-s tuleb fail uuesti sisse lugeda. Kõige lihtsam on seda teha GHCi käsuga “:r”. Näiteks nii

*Main> :r [1 of 1] Compiling Main ( Ex1.hs, interpreted ) Ok, modules loaded: Main. *Main> liidaArv 2 7

Lihtsamate Haskelli programmide arendamine käib kokkuvõtlikult nii, et 1. muudate faili, 2. salvestate faili, 3. laete GHCi-s faili (uuesti) sisse, 4. testite enda koodi GHCi-s, 5. goto 1.

1.3  Programmide näited

Haskelli õppimise esimene samm on kõige keerulisem, kuna ideeliselt väga lihtsad programmid kasutavad keerukaid keele omadusi. Näiteks lihtne aritmeetiline avaldis 5/a+4 kasutab infix operaatoreid ja erinevaid tüübiklasse. Seega, kui õpetada keelt nn. alt-ülesse, siis läheks väga kaua aega enne kui keele õppija saaks ise mingeid programme kirjutada. Kuna aga meie tahame kohe programmeerida hakata, ei saa me kohe detailidesse laskuda. Intuitsiooni saamiseks vaatame lihtsamate programmide lähtekoode ja uurime pealiskaudselt, mida need programmid teevad. Detailidesse laskume alles järgmises peatükkis.

Nagu juba enne mainitud, koosneb Haskelli programm definitsioonidest. Näiteks

a = 40.0 b = 30.0 c = sqrt (a^2 + b^2)

Koodi järgi paistab, et siin arvutatakse Pythagorose valemi abil täisnurkse kolmnurga hüpotenuusi pikkust kaatetite pikkuste järgi. Nii see ongi.

Lisaks definitsioonidele saab programmi dokumenteerimiseks koodi kirjutada ka tüübideklaratsioone. Näiteks nii

a, b, c :: Float a = 40.0 b = 30.0 c = sqrt (a^2 + b^2)

Float ja Double on ujukomaarvu tüübid ning Int ja Integer on täisarvutüübid.

Funktsioonide defineerimiseks tuleb samuti kirjutada vastav võrdus. Näiteks

pyth :: Float -> Float -> Float pyth x y = sqrt (x^2 + y^2)

Siin defineeritakse funktsioon pyth formaalsete parameetritega x ja y ning kehaga sqrt (x^2 + y^2). Funktsiooni saab välja kutsuda interaktiivses keskkonnas või näiteks asendades c definitsioon selliselt: c = pyth a b.

Pane Tähele! Haskellis on funktsioonid Currietud (loogiku Haskell Curry järgi) kujul s.t. funktsiooni tuleb välja kutsuda pyth a b, mitte pyth(a,b).

Funktsiooni tüübiks on α ->  β , kus α on funktsiooni argumendi tüüp ja β tagastatud väärtuse tüüp. Kui mingi funktsiooni tüüp on Int -> Bool siis see võtab argumendiks täisarvu ja tagastab tõeväärtuse. Funktsiooni pyth tüüp on Float -> Float -> Float s.t. kui sellele anda argumendiks kaks ujukomaarvu, on tulemus samuti ujukomaarv.

Pane Tähele! Kui te mõnda argumenti funktsiooni kehas ei kasuta, on soovitatav selle asemel kirjutada alakriips, näiteks const _ x = x.

Faktoriaali näide

Järgnevalt vaatame erinevaid viise, kuidas defineerida faktoriaali arvutavat funktsiooni. Teadupärast on faktoriaal defineeritud järgnevalt

n! = n * (n−1) * (n−2) * … * 2 * 1 .

Paljude tudengite arvates on kõige lihtsam tingimuslausel põhinev faktoriaal.

fact1 :: Int -> Int fact1 n = if n==0 then 1 else n * fact1 (n-1)

Kui kirjutada GHCi-sse fact1 2 siis toimub arvutus selliste sammudena:

     
  fact1 2⇝  if 2 == 0 then 1 else 2 * fact1 (2-1)          
 ⇝  2 * fact1 (2-1)          
 ⇝  2 * (if 1 == 0 then 1 else 1 * fact1 (1-1))          
 ⇝  2 * (1 * fact1 (1-1))          
 ⇝  2 * (1 * if 0 == 0 then 1 else 1 * fact1 (0-1))          
 ⇝  2 * (1 * 1)          
 ⇝  2 * 1          
 ⇝  2           

Pane Tähele! Enamasti ei kirjuta me igat arvutussammu välja vaid juhime tähelepanu viimati defineeritud funktsiooni arvutuskäigule.

Avaldise väärtustamise põhiliseks sammuks on funktsiooni keha asendamine funktsiooni väljakutse asemele ning argumentide asendamine formaalsete parameetrite asemele. Tingimusavaldise väätustamiseks arvutatakse esimese sammuna tingimuse väärtus ja siis valitakse sellele vastav haru. Aritmeetiliste avaldiste (näiteks korrutise või võrdsuskontrolli) väärtustamiseks peavad argumendid olema väärtustatud.

Tingimuslaused pole Haskellis nii populaarsed kui näidiste sobitamine (i.k. pattern matching), kus funktsioon defineeritakse erinevate võrdustega. Faktoriaali saab defineerida niimoodi:

fact2 :: Int -> Int fact2 0 = 1 fact2 n = n * fact2 (n-1)

Funktsiooni väljakutse puhul üritatakse võrduste vasakuid pooli järjest sobitada funktsiooni tegelike argumentidega. Meie näite puhul on väljakuste fact2 2 mistõttu esimene võrdus ei sobi aga teine sobib. Kui argumendiks on mingi avaldis, tuleb see mustri sobitamise jaoks väärtustada. See tähendab, järgmisel sammul peame arvutama 2-1 tulemuse, et seda saaks nulliga võrrelda. Kogu arvutuskäik on järgmine

     
  fact2 2⇝  2 * fact2 (2-1)          
 ⇝  2 * fact2 1          
 ⇝  2 * (1 * fact2 (1-1))          
 ⇝  2 * (1 * fact2 0)          
 ⇝  2 * (1 * 1)          
 ⇝  2 * 1          
 ⇝  2           

Näidiste sobitamise asemel saab Haskellis kasutada nn. valvureid (i.k guards). Valvurid on sarnased tingimuslausega lahendusele, kuid valvuritega on lihtsam ja selgem kirjutada hargnemist kolmeks või enamaks juhuks. Sarnaselt mustrisobitusele võetakse valvurite puhul esimesele tõese tingimusele vastav haru.

fact3 :: Int -> Int fact3 n | n==0 = 1 | otherwise = n * fact3 (n-1)

Kasutades valvureid saab kirjutada faktoriaali funktsiooni, mis ei lähe negatiivse argumendi puhul lõpmatusse tsükklisse.

fact4 :: Int -> Int fact4 n | n == 0 = 1 | n >= 1 = n * fact4 (n-1)

Juhul kui ükski muster ei sobitu või ükski valvur pole tõene tekitatakse erind.

*Main> fact4 (-1) *** Exception: …: Non-exhaustive patterns in function fact4

Pange tähele, et eelnevalt väljatoodud funktsioonide arvutuskäik ehitab teguritega avaldise, mis on vaja hiljem tulemuse saamiseks kokku korrutada. GHC implementatsioonis lisatakse esmalt kõik tegurid funktsioonikutse magasini andmestruktuuri, mistõttu on mälu kasutamine lineaarne argumendi väärtusega. Mäluga priiskamise vältimiseks on standardne kasutada nn. akumulaatori mustrit. Järgneb akumulaatorit where-konstruktsiooniga kasutav faktoriaali implementatsioon

fact5 :: Int -> Int fact5 n = fact5' 1 n where fact5' a 0 = a fact5' a m = fact5' (a*m) (m-1)

Laisa väärtustamise reeglite järgi kasutatakse küll lineaarne kogus mälu korrutise hoidmiseks kuid ei raisata piiratud funktsioonikutsete magasini mälu. Tehakse järgnevad arvutussammud:

     
  fact5 2⇝  fact5' 1 2          
 ⇝  fact5' (1*2) (2-1)          
 ⇝  fact5' (1*2) 1          
 ⇝  fact5' (1*2*1) (1-1)          
 ⇝  fact5' (1*2*1) 0           
 ⇝  1*2*1          
 ⇝  2*1          
 ⇝  2           

GHC-s on aga optimeering, mis esmalt tõestab, et funktsiooni esimene argument tuleb paratamatult lõpuks väätustada, ja väärtustab selle siis jooksvalt.

     
  fact5 2⇝  fact5' 1 2          
 ⇝  fact5' (1*2) (2-1)          
 ⇝  fact5' 2 1          
 ⇝  fact5' (2*1) (1-1)          
 ⇝  fact5' 2 0           
 ⇝  2           

Sarnaselt where-konstruktsioonile on abifunktsioone võimalik teha ka let-konstruktsiooniga. Funktsioone on võimalik teha λ-avaldisega (koodis kirjuta lambda langjoonena ehk “\”) ning mustrisobitust case-of avaldisega.

fact6 :: Int -> Int fact6 n = let fact6' = \ a n -> case n of 0 -> a _ -> fact6' (a*n) (n-1) in fact6' 1 n

Kasutades standardteegi võimalusi saab faktoriaali tegureid genereerida listi enumeratsiooni süntaksiga ning korrutada see kokku product funktsiooniga.

fact7 :: Int -> Int fact7 n = product [1..n]

Üles Järgmine