on k˜orgemal tasemel kui nende value-avaldiste tegelik skoop ning info mada-
lamalt tasemelt k˜orgemale liigutamine muudaks semantika ¨usna keeruliseks.
Seet˜ottu on Fumontrixis valitud eespool kirjeldatud variant, mis on lihtsama
semantikaga.
7.6.3
Lihtrekursioon
Fumontrixis on t¨u¨ubitaseme programmeerimisel v˜oimalik kasutada lihtrekur-
siooni. Erinevalt ¨uldisest rekursioonist, on lihtrekursiooni korral garanteeri-
tud termineerumine. Kuna Fumontrixis soovitakse garanteerida t¨u¨ubikont-
rolli termineerumist, siis ¨uldist rekursiooni siin t¨u¨ubitasemel ei v˜oimaldata.
Lihtrekursiooni moodustamiseks on Fumontrixis lihtrekursiivne t¨u¨ubita-
seme λ-avaldis (mis on mitterekursiivsest λ-avaldisest eraldi). Selle λ-avaldise
sees lihtrekursiivse p¨o¨ordumise jaoks saab kasutada rec-avaldist.
Lihtrekursioonikonstruktsiooni semantika andmiseks defineeritakse k˜oi-
gepealt funktsioon g, mis saab parameetriks arvutatava funktsiooni v¨a¨artu-
sed mingi t¨u¨ubi (v˜oi t¨u¨ubikonstruktori) t k˜oigi komponentide (vahetute v˜oi
mitte) jaoks ning tagastab selle funktsiooni v¨a¨artused t¨u¨ubi t jaoks (vt ka
n¨aidet jaotises 5.1.3). Funktsiooni g defineerimisel saab neid parameetreid
(arvutatava funktsiooni v¨a¨artusi komponentidel) kasutada rec-avaldise abil.
Funktsiooni v¨a¨artus komponendil t
1
on n¨aiteks rec t
1
.
Selline funktsioon m¨a¨arab ¨uheselt mingi lihtrekursiivse funktsiooni f. Et
arvutada selle funktsiooni v¨a¨artust mingi argumendi jaoks, arvutatakse k˜oi-
gepealt rekursiivselt v¨a¨artused selle komponentide jaoks ning seej¨arel kasuta-
takse eespool mainitud funktsiooni, et leida funktsiooni v¨a¨artus vajaliku ar-
gumendi jaoks. Et t¨u¨upide ja t¨u¨ubikonstruktorite struktuur on Fumontrixis
l˜oplik, siis selle rekursiivne l¨abimine ja komponentidel funktsiooni v¨a¨artuste
v¨aljaarvutamine alati termineerub (eeldusel, et ka funktsioon g termineerub,
aga Fumontrixis ei saa kirjutada mittetermineeruvat t¨u¨ubitaseme funktsioo-
ni). Funktsioon f ongi lihtrekursioonikonstruktsiooni semantikaks.
rec-avaldise semantika andmiseks on kontekstis kujutus zSiRec, mis seab
lihtrekursiooni identifikaatorile (vt jaotist 5.1.3) vastavusse teise kujutuse.
See kujutus seab nendele argumendi komponentidele, millele vastav funkt-
siooni v¨a¨artus on vaadeldava identifikaatoriga lihtrekursiooni k¨aigus juba
v¨alja arvutatud, vastavusse need funktsiooni v¨a¨artused. rec-avaldisele se-
mantika andmiseks v˜oetakse lihtsalt sellest kujutusest vastav v¨a¨artus.
7.6.4
T¨
u¨
ubiklassid
T¨u¨ubiklassi defineerimiseks on Fumontrixis class-deklaratsioon kujul
class c t. See toob sisse nimega c t¨u¨ubiklassi, mille eksemplaride t¨u¨up
73
on kirjeldatud t¨u¨ubiavaldisega t. See t¨u¨ubiavaldis peab olema universaal-
selt kvantifitseeritud kujul forall A : k . t [A]. T¨u¨ubiklassi esindajad on
sellisel juhul liiki k ning esindajale A vastav eksemplar peab olema t¨u¨upi
t [A]. T¨u¨ubiklasside jaoks on kontekstis kujutus zClass, mis seab t¨u¨ubiklassi
nimele vastavusse selle eksemplaride t¨u¨upe kirjeldava t¨u¨ubi.
Eksemplarid m¨a¨aratakse t¨u¨ubitaseme funktsiooniga, mille nimi ¨uhtib vas-
tava t¨u¨ubiklassi nimega. See funktsioon seab t¨u¨ubile (v˜oi t¨u¨ubikonstruktorile)
vastavusse eksemplari. See eksemplar peab olema eelmises l˜oigus kirjeldatud
t¨u¨upi, kuid seda kontrollitakse alles eksemplari kasutamisel (t¨u¨ubiklassiga
kitsendatud ¨uldisuskvantori avamisel), mitte eksemplari defineerimisel.
Pol¨umorfsed v¨a¨artused, mille t¨u¨up sisaldab tipmisel tasemel t¨u¨ubiklassiga
kitsendatud ¨uldisuskvantorit, on semantiliselt esitatud funktsioonidena, mis
seavad t¨u¨ubiklassi eksemplari v¨a¨artusele vastavusse (monomorfsema) v¨a¨artu-
se. Kui selle v¨a¨artuse t¨u¨ubi ¨uldisuskvantor avatakse (kas automaatselt funkt-
siooni rakendamise k¨aigus v˜oi k¨asitsi), siis v˜oetakse jooksvast keskkonnast
t¨u¨ubiklassi eksemplari v¨a¨artus selle t¨u¨ubi jaoks ning antakse pol¨umorfse-
le v¨a¨artusele vastavale funktsioonile argumendiks. Selle pol¨umorfse avaldise
sees seotakse see argumendiks antud eksemplar selle kvantoriga seotud t¨u¨u-
bikonstruktoriga, mis muutub seega selle t¨u¨ubiklassi esindajaks.
Selle sidumise realiseerimiseks salvestatakse see eksemplar t¨uhja nimega
muutujasse, mis lisatakse keskkonda, saadud keskkond salvestatakse sellele
eraldatava unikaalse skoobiidentifikaatori abil jaotises 7.6.2 vaadeldud vii-
sil. Sisuliselt moodustatakse value-konstruktsioon, mille sisuks on see t¨uhja
nimega muutuja. T¨u¨ubiklassi eksemplare m¨a¨aravat t¨u¨ubitaseme funktsiooni
t¨aiendatakse nii, et vaadeldavale (uuele) t¨u¨ubile m¨a¨aratakse eksemplariks see
value-konstruktsioon. Kui n¨u¨ud millalgi on vaja selle uue t¨u¨ubi eksemplari
kasutada, siis v¨a¨artustatakse see value-konstruktsioon, mille k¨aigus v˜oetakse
salvestatud keskkonnast eksemplari v¨a¨artus.
T¨u¨ubiklasse saab kasutada ka eksistentsiaalsete t¨u¨upide korral. T¨u¨ubi-
klassiga kitsendatud olemasolukvantori avamisel (exists-n¨aidise abil) tuuak-
se analoogiliselt ¨uldisuskvantoriga sisse uus konstruktor, mis muudetakse
t¨u¨ubiklassi esindajaks, m¨a¨arates vastavaks eksemplariks selle eksistentsiaalse
v¨a¨artuse sees olnud eksemplari.
74
Kokkuv˜
ote
Selles t¨o¨os l˜oime uue funktsionaalse programmeerimiskeele Fumontrix ning
realiseerisime sellele interpretaatori. T¨o¨os v˜ordlesime muuhulgas selle keele
v˜oimalusi Haskelli (GHC) omadega.
Selles keeles realiseerisime enamiku olulisemaid Haskelli konstruktsioo-
ne, sealhulgas algebralised andmet¨u¨ubid, parameetriliselt pol¨umorfsed funkt-
sioonid ja t¨u¨ubiklassid. Sarnaselt GHC-ga realiseerisime impredikatiivse po-
l¨umorfismi. Impredikatiivse pol¨umorfismi v˜oimaluse korral ei pruugi funkt-
siooni rakendamise tulemus enam ¨uheselt m¨a¨aratud olla. Seet˜ottu on teatud
juhtudel vaja ¨uldisuskvantoreid k¨asitsi avada, mida Fumontrixis on oluliselt
mugavam teha kui GHC-s, kuna erinevalt GHC-st ei ole vaja kogu v¨a¨artuse
t¨u¨upi ¨umber kirjutada, piisab anda vaid avatava kvantoriga seotud t¨u¨ubi-
muutuja v¨a¨artustus.
T¨u¨ubiklassidest realiseerisime k¨ull lihtsama variandi kui Haskellis, kuid
nagu n¨agime, ei ole see v¨aga suur puudus, kuna Fumontrixis on olemas t¨u¨u-
bitaseme funktsioonid, mis on palju suuremate v˜oimalustega kui t¨u¨ubiklassid
ja enamasti kasutatavad ka t¨u¨ubiklasside asemel. T¨u¨ubiklassid osutusid va-
jalikuks ainult selleks, et teatud piiratud d¨unaamilise skoopimise elemente
sisse tuua. Mujal kasutatakse Fumontrixis leksilist skoopimist, kuna, nagu
n¨agime, v˜oimaldaks piiramatu d¨unaamiline skoopimine t¨u¨ubitasemel l˜opma-
tu rekursiooni tekitada.
Samuti n¨agime, et Fumontrixi t¨u¨ubitaseme funktsioonid pakuvad palju
suuremaid v˜oimalusi kui GHC t¨u¨ubiklassid ning on defineeritavad loomu-
likul viisil λ-abstraktsioonidena, samas kui GHC-s on nende defineerimine
v¨aga kohmakas, kuna GHC t¨u¨ubiklassid pole t¨u¨ubitaseme funktsioonide de-
fineerimiseks m˜oeldud. Fumontrixis saame t¨u¨ubitasemel arvutada ka v¨a¨ar-
tustega, seda k¨ull musta kastina, mille kohta on teada ainult selle v¨a¨artuse
t¨u¨up. V¨a¨artustega arvutamist saab kasutada ka t¨u¨ubiklasside eksemplaride
defineerimisel, kuna eksemplaride v¨a¨artused seatakse t¨u¨upidele vastavusse
t¨u¨ubitaseme funktsiooni abil.
T¨u¨ubitasemel rekursiooni kasutamiseks otsustasime Fumontrixis realisee-
rida ¨uldise rekursiooni asemel lihtrekursiooni, mis on enamiku kasulike t¨u¨u-
bitaseme funktsioonide realiseerimiseks piisav, kuid samas garanteerib t¨u¨u-
bikontrolli termineeruvuse, mis oli ¨uks Fumontrixi eesm¨arke. T¨o¨os vaatlesi-
me ka m˜oningaid t¨u¨ubitaseme funktsioonide rakendusi, n¨aiteks pol¨umorfse-
te funktsioonide realiseerimist ning erinevate kasulike operaatorite defineeri-
mist, mida GHC-s ei saa defineerida.
Fumontrixi ¨uheks p˜ohim˜otteks oli skoopide v˜ordv¨a¨arsus, seega t¨u¨ubiklas-
se, t¨u¨ubitaseme funktsioone, algebralisi andmet¨u¨upe jne v˜oimaldatakse defi-
neerida suvalises skoobis (nii peatasemel kui let-avaldistes), erinevalt Has-
75
kellist, kus neid saab defineerida vaid peataseme skoobis.
Fumontrixis realiseerisime ka m˜oned v˜oimalused imperatiivse program-
meerimisstiili kasutamiseks, n¨aiteks ST-monaadi, milles saab kasutada muu-
detavad viitasid ja massiive, kuid need arvutused saab l¨abi viia muust maa-
ilmast eraldatud l˜oimes, mist˜ottu arvutused on seal deterministlikud ja keel
j¨a¨ab puhtalt funktsionaalseks. Monaadiliste v¨a¨artuste mugavamaks kasuta-
miseks realiseerisime monaadiliste v¨a¨artuste pol¨umorfismi, mis v˜oimaldab
tavalisel funktsiooni rakendamisel kasutada erinevaid monaadilisi ja mitte-
monaadilisi v¨a¨artusi, erinevalt Haskellist, kus selleks tuleks defineerida palju
erinevaid funktsiooni rakendamise operaatoreid. Samuti realiseerisime s¨un-
taktilise suhkruna do-notatsiooni, mida erinevalt Haskellist saab kasutada
korraga ka mitme erineva monaadi jaoks.
T¨o¨os uurisime ka erinevaid pol¨umorfismi liike ning vaatlesime v˜oimalusi
nende kasutamiseks Fumontrixis — parameetrilist pol¨umorfismi, t¨u¨ubiklasse,
t¨u¨ubitaseme funktsioone ning monaadiliste v¨a¨artuste pol¨umorfismi.
T¨o¨os realiseerisime ka eksistentsiaalsed t¨u¨ubid, mida saab kasutada nii
parameetriliselt kui t¨u¨ubiklassiga kitsendatult, kuid need eksistentsiaalsed
t¨u¨ubid ei ole pol¨umorfsed. Erinevalt Haskellist saab olemasolukvantorit ka-
sutada suvalise t¨u¨ubikomponendi ¨umber (nagu ka ¨uldisuskvantorit), mitte
ainult seoses algebraliste andmet¨u¨upidega.
Interpretaatori realiseerimisel andsime s¨untaktilistele konstruktsioonide-
le semantika funktsionaalsel kujul, kasutades ainult puhtalt funktsionaalseid
andmestruktuure. Seega m¨a¨arab selle interpretaatori kood teatud liiki deno-
tatsioonilise semantika. Sellest semantikast andsime ka t¨o¨os ¨ulevaate.
76
Viited
[1] Haskell 98 Language and Libraries. The Revised Report, toimetanud
Simon Peyton Jones. 2002. http://www.haskell.org/onlinereport/
(viimati v¨aisatud 15.05.2008)
[2] The Glorious Glasgow Haskell Compilation System User’s Guide, Version
6.8.2. The GHC Team. 2007.
http://haskell.org/ghc/docs/6.8.2/html/users_guide/
(viimati
v¨aisatud 15.05.2008)
[3] Simon Peyton Jones.
Tackling the Awkward Squad: monadic in-
put/output, concurrency, exceptions, and foreign-language calls in
Haskell. Engineering theories of software construction, Marktoberdorf
Summer School, 2002.
[4] Luca Cardelli ja Peter Wegner. On Understanding Types, Data Abstrac-
tion, and Polymorphism. ACM Computing Surveys, Vol.17, No.4, 1985.
[5] Thomas Hallgren. Fun with Functional Dependencies. Proceedings of the
Joint CS/CE Winter Meeting, 2001.
[6] Happy User Guide, Version 1.17.
Simon Marlow ja Andy Gill.
2007.
http://www.haskell.org/happy/doc/html/ (viimati v¨aisatud
26.05.2008)
77
A Functional Programming Language and its
Semantics
Master Thesis
Martin Pettai
Resume
We have created a new functional programming language Fumontrix and
implemented an interpreter for it. In this thesis, we give an overview of its
features and their semantics and also compare the features to those of Haskell
(GHC).
We have implemented most of the standard Haskell constructions, includ-
ing algebraic data types, parametrically polymorphic functions, and type
classes. Similarly to GHC, we have implemented impredicative polymor-
phism. When impredicative polymorphism is allowed, the result of function
application is no longer guaranteed to be unique, thus it is often necessary to
explicitly specialize universally quantified types. Whereas GHC requires to
annotate the whole result type after specialization, Fumontrix allows to only
specify the type to be substituted for the quantified variable, which requires
less work from the programmer.
While we have implemented type classes, our version is more primitive
than that of Haskell (and especially GHC). As we see in the thesis, this is
not very restrictive, as we have implemented type-level functions, which are
much more powerful than type classes and in most cases can be used as an
alternative to type classes. Type classes were only introduced in Fumontrix
to have some limited elements of dynamic scoping. Elsewhere we use lexical
scoping, as unlimited dynamic scoping would allow infinite recursion to occur
at the type level.
Our type-level functions can be defined naturally as type-level λ-abstrac-
tions, whereas GHC type classes are not intended for general type-level pro-
gramming and, while usable for defining some type-level functions, are un-
natural to use and require ugly code. In Fumontrix, we can also use values
(in addition to types) in type-level computations, although only as a black
box for which only type is known. The black box value obtained as a result
of type-level computation can only be opened at the data level.
To allow recursion at the type level, we decided to implement only primi-
tive recursion, not general recursion. This is enough for most useful type-level
functions and also guarantees termination of type checking. In the thesis, we
78
also see some applications of type-level functions, such as polymorphic func-
tions or defining some useful operators that are not definable in GHC.
One of the principles of Fumontrix is the equivalence of scopes, therefore
type classes, type functions, algebraic data types, etc. can be defined in any
scope (including let-expressions), unlike in Haskell where these declarations
are restricted to the top level.
We have also implemented some features that allow using imperative pro-
gramming style, e.g. ST monad which allows to use mutable references and
arrays but in a thread separate from the outside world, thus retaining the
purely functional property. To make the use of monadic values less ugly, we
have implemented a polymorphism of monadic values, which allows us to use
the ordinary function application for different monadic and non-monadic val-
ues, unlike in Haskell where we would have to define many different function-
application operators for these cases, such as liftM and ap. We have also
implemented the do-notation (as syntactic sugar), which can also be used for
several different monads at a time, unlike in Haskell.
In this thesis we also investigate different kinds of polymorphism and the
possibilities of using them in Fumontrix.
We have also implemented existential types, which can be used both
parametrically and restricted by a type class, although the existential types
are not polymorphic. The existential quantification can be used around any
type component, not only at the top level.
Our implementation of the interpreter gives a semantics to syntactic con-
structions in a functional style, using only purely functional data structures.
This defines a certain kind of denotational semantics. In the thesis we also
give an overview of this semantics.
79
Dostları ilə paylaş: |