U L i k o o L matemaatika-informaatikateaduskond

type runList = \ v : @ .

value

(type

(\ t rec @ .

case t of

List a ->

value \ xs : t .

concat (map (type rec a) xs);

Maybe a ->

value \ mx : t .

concat (map (type rec a) (maybeToList mx));

_ ->

value \ x : t .

x :: Nil;

end

) (typeof type v)

) (type v);

newmonad List;

newmonad Maybe;

lr = do

. x <- 1 :: 2 :: 3 :: Nil;

. y <- Just 700;

. z <- 10 :: 20 :: Nil;

in

x + y + z;

main = type runList (value lr)

Siin ei ole erinevalt GHC-st vaja Stop-konstruktorit sisse tuua ning kasutada

saab do-notatsiooni. lr on t¨u¨upi

List (Maybe (List Int))

ning type runList (value lr) on t¨u¨upi List Int.

6.5.4

Monaadiliste v¨

a¨

artuste pol¨

umorfismi piiramine

M˜onikord v˜oib selles peat¨ukis vaadeldav monaadiliste v¨a¨artuste pol¨umorfism

ootamatuid tulemusi anda, kui me tegelikult ei plaaninud seda kasutada.

N¨aiteks avaldise

Just (3 :: 4 :: Nil)

58

---

v¨a¨artuse t¨u¨up ilma monaadiliste v¨a¨artuste pol¨umorfismita on

Maybe (List Int), aga pol¨umorfismiga on hoopis List (Maybe Int). See

tuleb sellest, et Just on t¨u¨upi forall A. A -> Maybe A, kuid talle antak-

se argumendiks v¨a¨artus t¨u¨upi List Int. Nagu kvantorite avamisel, avatakse

argumendiks antud v¨a¨artuse t¨u¨ubis enne unifitseerimist v˜oimalikult palju

tipmisel tasemel olevaid monaade. Seega ei v¨a¨artustata kvantori avamisel

A = List Int, vaid A = Int ning funktsiooni rakendamisel kasutatakse

operaatorit fmap (listimonaadi oma), mitte tavalist funktsiooni rakendamist.

Et selliseid ¨ullatusi v¨altida, on Fumontrixis v˜oimalik m¨a¨arata, milliseid

konstruktoreid k¨asitletakse mingis skoobis monaadidena (monaadiliste v¨a¨ar-

tuste pol¨umorfismi m˜ottes). Alguses ei k¨asitleta ¨uhtegi konstruktorit monaa-

dina, isegi kui see on monad klassi esindajaks defineeritud. Deklaratsioon

newmonad M;

muudab monaadikonstruktori M antud alamskoobis monaadina k¨asitletavaks.

Kui mingis alamskoobis ei soovita seda enam monaadina k¨asitleda, siis v˜oib

anda deklaratsiooni

unmonad M;

Kui mingis alamskoobis ei soovita ¨uhtegi konstruktorit monaadina k¨asitleda,

siis v˜oib anda deklaratsiooni

nomonads;

selle asemel, et iga monaadi jaoks unmonad-deklaratsioon anda. Alamskoopi-

des on siis v˜oimalik vajaduse korral j¨alle m˜oni newmonad-deklaratsioon anda.

newmonad- ja unmonad-deklaratsioone v˜oib kasutada ka keerulisemat liiki

kui * -> * monaadikonstruktorite korral, n¨aiteks

newmonad ST;

(ST on liiki * -> * -> *). Sellisel juhul k¨aib deklaratsioon k˜oigi monaadide

kohta, mis on antud konstruktoriga konstrueeritavad. Praegusel juhul siis

ST a kohta iga t¨u¨ubi a jaoks.

59

---

7

Semantika kirjeldamisest

7.1

Fumontrixi interpretaatori realiseerimisest

Fumontrixi interpretaator on realiseeritud Haskellis. S¨untaksi parseri gene-

reerimiseks kasutatakse Happy’t [6], mis on Yacc’i analoog, kuid genereerib

C koodi asemel Haskelli koodi. Lekser on realiseeritud k¨asitsi Haskellis.

Interpretaatoris on s¨untaktilistele konstruktsioonidele ¨uritatud anda se-

mantika funktsionaalsel kujul, kasutades ainult puhtalt funktsionaalseid and-

mestruktuure (sh monaade, kuid mitte sisendit-v¨aljundit). Seega on interpre-

taatori koodist v˜oimalik v¨alja lugeda teatud liiki denotatsiooniline semantika.

Et semantika j¨a¨aks v˜oimalikult lihtsaks, ei ole optimiseerimisele eriti r˜ohku

pandud ning see interpretaator on seet˜ottu aeglasem ja m¨alun˜oudlikum (eba-

efektiivsem) kui traditsioonilised interpretaatorid.

Samuti ei ole selles interpretaatoris r˜ohku pandud veateadete (nt t¨u¨ubivi-

gade) informatiivsusele, kuna see j¨a¨ab k¨aesoleva t¨o¨o skoobist v¨alja. Seet˜ottu

on koodi mittetundval kasutajal veateatest aru saamine raskendatud.

7.2

Interpretaatori koodi struktuur

Lekser on realiseeritud failis Lexer.hs. Lekser teisendab stringikujul oleva

l¨ahtekoodi lekseemide listiks. Lekseemid on defineeritud failis Syntax.hs.

Parseri kirjeldus on antud failis Parser.y, millest genereeritakse Hap-

py abil fail Parser.hs. See viimane on ka interpretaatori l¨ahtekoodi juurde

alles j¨aetud, et interpretaatori kompileerimiseks ei oleks vaja Happy’t instal-

lida. Parser teisendab lekseemide listi abstraktse s¨untaksi kujule. Abstraktne

s¨untaks on defineeritud failis AbsSyntax.hs.

Failis Types.hs on defineeritud m˜oned t¨u¨ubis¨unon¨u¨umid, mida mujal ka-

sutatakse.

Failis SemCats.hs on defineeritud semantilised kategooriad (t¨u¨ubid, v¨a¨ar-

tused jne) ning kontekst ja keskkond. Failis SemHelpers.hs on m˜oningad

abifunktsioonid semantika andmiseks (kvantorite lisamine ja avamine, muu-

tujate asendamine t¨u¨ubiavaldises jne). Failis SemUnify.hs on defineeritud

unifitseerimise ja monaadiliste v¨a¨artuste pol¨umorfismiga seotud funktsioo-

nid, mida kasutatakse andmetaseme funktsiooni rakendamise operaatori se-

mantika andmisel.

Failis Denot.hs on p˜ohiline denotatsioonilise semantika kirjeldus. Seal

antakse nii staatiline kui d¨unaamiline semantika erinevate s¨untaktiliste kate-

gooriate jaoks, samuti lihtrekursiooni ja t¨u¨ubiklasside semantika.

Failis SemInitCtx.hs defineeritakse Fumontrixi programmi algkontekst

ja -keskkond (sisseehitatud t¨u¨ubid ja operatsioonid) ning kogu programmi

60

---