U L i k o o L matemaatika-informaatikateaduskond

7.5.2

¨

Uldisuskvantorite avamine . . . . . . . . . . . . . . . . 67

7.5.3

Monaadiliste v¨a¨artuste pol¨umorfism . . . . . . . . . . . 68

7.5.4

Unifitseerimine . . . . . . . . . . . . . . . . . . . . . . 69

7.6 T¨u¨ubitaseme programmeerimise semantikast . . . . . . . . . . 70

7.6.1

T¨u¨ubitaseme funktsioonid . . . . . . . . . . . . . . . . 70

7.6.2

V¨a¨artused t¨u¨ubitasemel . . . . . . . . . . . . . . . . . 71

7.6.3

Lihtrekursioon . . . . . . . . . . . . . . . . . . . . . . . 73

7.6.4

T¨u¨ubiklassid . . . . . . . . . . . . . . . . . . . . . . . . 73

Kokkuv˜

ote

75

Viited

77

Resume

78

5

---

1

Sissejuhatus

Selle t¨o¨o eesm¨argiks on luua uus funktsionaalne programmeerimiskeel Fu-

montrix, realiseerida sellele interpretaator ja uurida selle keele olulisemate

konstruktsioonide semantikat.

See keel peaks olema laisk ja puhtalt funktsionaalne, staatilise ja v˜oi-

malikult t¨apse t¨u¨ubis¨usteemiga, v˜oimalikult pol¨umorfne, v˜oimaldama mingil

m¨a¨aral ka imperatiivset stiili kasutada ning olema loetav ¨ulevalt alla (seega

programmis hiljem defineeritavaid identifikaatoreid ei tohiks enamasti saa-

da kasutada). Samuti ei tohiks peataseme skoop olla v¨aga erinev tavalisest

skoobist (seega suvalises alamskoobis peaks saama defineerida uusi andme-

t¨u¨upe jne). Samas peaks t¨u¨ubikontroll j¨a¨ama garanteeritult termineeruvaks.

T¨o¨os uurime m˜oningaid erinevaid v˜oimalusi nende eesm¨arkide saavutamiseks

ning Fumontrixis tehtud valikuid. Fumontrixi ¨uldiseid p˜ohim˜otteid vaatleme

peat¨ukis 2.

Fumontrixi eeskujuks on Haskell [1], mis on samuti laisk puhas funkt-

sionaalne keel ning milles on realiseeritud Fumontrixi interpretaator. Inter-

pretaatoris antakse enamikule s¨untaktilistele konstruktsioonidele semantika

funktsionaalsel kujul, kasutades ainult puhtalt funktsionaalseid andmestruk-

tuure (sh monaade, kuid mitte sisendit-v¨aljundit), seega on sealt v˜oimalik

v¨alja lugeda teatud liiki denotatsiooniline semantika. Sellest semantikast an-

name ¨ulevaate peat¨ukis 7. Ka Fumontrixi s¨untaks on sarnane Haskelli omaga

ja seda vaatleme l¨ahemalt peat¨ukis 3.

Enamik olulisemaid Haskelli konstruktsioone v˜oi nende alternatiivid on

ka Fumontrixis realiseeritud. Haskellil on m˜oningaid puudusi, mida on Fu-

montrixis ¨uritatud k˜orvaldada.

Haskellis on t¨u¨ubitaseme programmeerimise v˜oimalused piiratud. Ka GHC

laiendustes ([2], peat¨ukk 8) on selle kasutamine millegi muu kui t¨u¨ubiklasside

jaoks kohmakas. Fumontrixis saab t¨u¨ubitasemel defineerida suvalisi lihtrekur-

siivseid funktsioone ning lisaks t¨u¨upidele saab arvutada ka v¨a¨artustega, kuid

ainult parameetriliselt pol¨umorfselt. Ka t¨u¨ubiklassid on realiseeritud t¨u¨ubi-

taseme funktsioonide abil, mis seavad t¨u¨ubile vastavusse klassi eksemplari

v¨a¨artuse selle t¨u¨ubi jaoks. T¨u¨ubitaseme funktsioone vaatleme l¨ahemalt pea-

t¨ukis 5.

Samuti on Haskellis k˜orvalefektide kasutamine ebamugav. Haskell on pu-

has funktsionaalne keel ja k˜orvalefektide jaoks kasutatakse monaade. K˜or-

valefekte sisaldavaid v¨a¨artusi ei saa puhast v¨a¨artust ootavale funktsioonile

argumendiks anda sama lihtsalt kui mittepuhastes keeltes. Fumontrixis on

funktsiooni rakendamise operaator ¨ule laaditud ja seda saab kasutada eri-

nevate monaadiliste v¨a¨artuste kombinatsioonide korral, kus Haskellis tuleks

kasutada erinevaid funktsioone nagu liftM, ap jne. Seda v˜oime vaadelda ¨uhe

6

---

pol¨umorfismi liigina. Pol¨umorfismi vaatleme l¨ahemalt peat¨ukis 6, kus uurime

erinevaid pol¨umorfismi liike ja nende kasutamise v˜oimalusi.

Keeles on olemas ka universaalselt ja eksistentsiaalselt kvantifitseeritud

t¨u¨ubid, kus kvantorid v˜oivad esineda suvalise t¨u¨ubikomponendi ¨umber, mit-

te ainult tipmisel tasemel. Rakendamise hetkel tipmise taseme ¨uldisuskvan-

toritega t¨u¨upide v¨a¨artusi on v˜oimalik funktsiooni rakendamisel pol¨umorfselt

kasutada. T¨u¨ubis¨usteemi olulisemaid ise¨arasusi vaatleme peat¨ukis 4.

T¨o¨ole on CD-plaadil (lisa 1) lisatud realiseeritud Fumontrixi interpretaa-

tori l¨ahtekood koos m˜onede n¨aidetega. Selle kasutusjuhend on failis README.

7

---

2

Fumontrixi ¨

uldised p˜

ohim˜

otted

2.1

¨

Ulalt alla loetavus

Haskellis (ning ka Javas) on ¨uhes deklaratsioonide nimekirjas (peatasemel,

let-avaldises, where-deklaratsioonis) olevad deklaratsioonid alati ¨uksteise

skoobis. Seega v˜oivad ¨uhes deklaratsioonis esineda viited nii ¨ulal- kui all-

pool defineeritud muutujatele. See muudab koodi lugemise raskeks, kui ¨uhes

skoobis on palju deklaratsioone, nagu peataseme skoobis tavaliselt on. Koodi

lugemisel on vaja pidevalt h¨upata edasi-tagasi. Samuti v˜oib programmeerija

kogemata tekitada rekursiooni, mida ta ei kavatsenud tekitada.

Haskellis ei saa ka defineerida uut muutujat eelmise samanimelise muu-

tuja kaudu. Sageli on vaja defineerida uus v¨a¨artus, mille t¨ahendus on v¨a-

ga sarnane mingi varem defineeritud ja nimetatud v¨a¨artuse t¨ahendusega,

ning on kindel, et vanale v¨a¨artusele enam viidata vaja ei ole. Imperatiivsel

programmeerimisel saab sel juhul lihtsalt omistada muutujale uue v¨a¨artuse.

Funktsionaalsel programmeerimisel tuleb defineerida uus muutuja. Vaatleme

j¨argmist pseudo-Haskelli avaldist:

let

r = x ‘mod‘ m

r = if r*2 < m then

r

else

r - m

in

f r

Haskellis nii ei lubata kirjutada, ¨uhes let-avaldises ei lubata defineerida

mitut samanimelist muutujat. Seega peame kasutama mitut ¨uksteise sees

olevat let-avaldist:

let

r = x ‘mod‘ m

in let

r = if r*2 < m then

r

else

r - m

in

f r

8

---