U L i k o o L matemaatika-informaatikateaduskond



Yüklə 0,53 Mb.

səhifə23/23
tarix13.11.2017
ölçüsü0,53 Mb.
1   ...   15   16   17   18   19   20   21   22   23

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





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ş:
1   ...   15   16   17   18   19   20   21   22   23


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2019
rəhbərliyinə müraciət

    Ana səhifə