U L i k o o L matemaatika-informaatikateaduskond



Yüklə 0,53 Mb.

səhifə1/23
tarix13.11.2017
ölçüsü0,53 Mb.
  1   2   3   4   5   6   7   8   9   ...   23


T A R T U

¨

U L I K O O L



MATEMAATIKA-INFORMAATIKATEADUSKOND

Arvutiteaduse instituut

Informaatika eriala

Martin Pettai

Funktsionaalne

programmeerimiskeel

ja selle semantika

Magistrit¨

o (20 ap)



Juhendaja: teadur H. Nestra

Autor: ................................................... “.....” mai

2008

Juhendaja: ............................................ “.....” mai



2008

Lubada kaitsmisele

Professor: .............................................. “.....” mai

2008


TARTU 2008



Sisukord

1 Sissejuhatus

6

2 Fumontrixi ¨



uldised p˜

ohim˜


otted

8

2.1



¨

Ulalt alla loetavus . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.2 T¨u¨ubiinferents . . . . . . . . . . . . . . . . . . . . . . . . . . .



9

2.3 Skoopide v˜ordv¨a¨arsus . . . . . . . . . . . . . . . . . . . . . . . 10

2.4 K˜orvalefektid, erindid ja laiendatud t¨u¨ubid . . . . . . . . . . . 11

2.5 Imperatiivne stiil . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.6 Anon¨u¨umsed funktsioonid ka t¨u¨ubitasemel . . . . . . . . . . . 13

3 S¨


untaks

15

3.1 V˜ordlus Haskelliga . . . . . . . . . . . . . . . . . . . . . . . . 15



3.2 S¨untaksi ¨ulevaade . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2.1


S¨untaktilised kategooriad . . . . . . . . . . . . . . . . . 15

3.2.2


Kommentaarid . . . . . . . . . . . . . . . . . . . . . . 16

3.2.3


Muutujad ja konstruktorid . . . . . . . . . . . . . . . . 16

3.2.4


Avaldised . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.2.5


N¨aidised . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.2.6


T¨u¨ubiavaldised . . . . . . . . . . . . . . . . . . . . . . 18

3.2.7


T¨u¨ubin¨aidised . . . . . . . . . . . . . . . . . . . . . . . 18

3.2.8


Liigiavaldised . . . . . . . . . . . . . . . . . . . . . . . 18

3.2.9


Deklaratsioonid . . . . . . . . . . . . . . . . . . . . . . 19

4 T¨


ubis¨


usteemist

20

4.1 Fumontrixi t¨u¨ubis¨usteemist ¨uldiselt . . . . . . . . . . . . . . . 20



4.2 Baast¨u¨ubid . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.3 T¨u¨ubikonstruktorid . . . . . . . . . . . . . . . . . . . . . . . . 21

4.4 Universaalselt kvantifitseeritud t¨u¨ubid . . . . . . . . . . . . . 21

4.5 Eksistentsiaalsed t¨u¨ubid . . . . . . . . . . . . . . . . . . . . . 22

5 T¨



ubitaseme programmeerimine



24

5.1 T¨u¨ubitaseme funktsioonid Fumontrixis . . . . . . . . . . . . . 24

5.1.1

T¨u¨ubitaseme funktsioonid . . . . . . . . . . . . . . . . 24



5.1.2

V¨a¨artustega arvutamine t¨u¨ubitasemel . . . . . . . . . . 25

5.1.3

T¨u¨ubitaseme lihtrekursiivsed funktsioonid . . . . . . . 26



5.2 M˜oningaid t¨u¨ubitaseme funktsioonide rakendusi . . . . . . . . 29

5.2.1


T¨u¨ubitaseme funktsioonid ja ad-hoc-pol¨umorfism . . . 29

5.2.2


T¨u¨ubitaseme funktsioonid ja t¨u¨ubiinferents . . . . . . . 30

5.3 T¨u¨ubitaseme funktsioonid Haskellis . . . . . . . . . . . . . . . 32

3



5.3.1

Ad-hoc-pol¨umorfsed funktsioonid . . . . . . . . . . . . 32

5.3.2

Ad-hoc-pol¨umorfism tulemuse t¨u¨ubi jaoks . . . . . . . 33



5.3.3

Rekursioon tulemuse t¨u¨ubi leidmiseks . . . . . . . . . . 33

5.3.4

Hargnemine t¨u¨ubi struktuuri j¨argi . . . . . . . . . . . . 34



5.3.5

Vaikevariandid hargnemisel . . . . . . . . . . . . . . . 36

5.3.6

GHC t¨u¨ubitaseme funktsioonide puudusi . . . . . . . . 38



6 Pol¨

umorfism


40

6.1


¨

Uldiselt pol¨umorfismist . . . . . . . . . . . . . . . . . . . . . . 40

6.2 Pol¨umorfism ja t¨u¨ubitaseme funktsioonid . . . . . . . . . . . . 40

6.3 Pol¨umorfism ja d¨unaamilise skoopimise elemendid . . . . . . . 41

6.3.1

Veel ¨uks pol¨umorfismi liik . . . . . . . . . . . . . . . . 41



6.3.2

D¨unaamilise skoopimise elemendid Haskellis . . . . . . 42

6.3.3

D¨unaamilise skoopimise elemendid Fumontrixis . . . . 43



6.3.4

D¨unaamilise skoopimise elemendid ja objektorienteeritus 44

6.4 Pol¨umorfsed v¨a¨artused funktsiooni argumendina . . . . . . . . 45

6.4.1


Pol¨umorfsed v¨a¨artused . . . . . . . . . . . . . . . . . . 45

6.4.2


Impredikatiivne pol¨umorfism . . . . . . . . . . . . . . . 46

6.4.3


Pol¨umorfsed v¨a¨artused Fumontrixi t¨u¨ubitasemel . . . . 48

6.5 Monaadilised v¨a¨artused ja pol¨umorfism . . . . . . . . . . . . . 50

6.5.1

Monaadilised v¨a¨artused ja funktsiooni rakendamine . . 50



6.5.2

do-notatsioon . . . . . . . . . . . . . . . . . . . . . . . 54

6.5.3

Mitme monaadi korraga kasutamine . . . . . . . . . . . 56



6.5.4

Monaadiliste v¨a¨artuste pol¨umorfismi piiramine . . . . . 58

7 Semantika kirjeldamisest

60

7.1 Fumontrixi interpretaatori realiseerimisest . . . . . . . . . . . 60



7.2 Interpretaatori koodi struktuur . . . . . . . . . . . . . . . . . 60

7.3 Fumontrixi semantika kirjeldamisest . . . . . . . . . . . . . . . 61

7.3.1

Semantika tasemed . . . . . . . . . . . . . . . . . . . . 61



7.3.2

Seosed semantika tasemete vahel . . . . . . . . . . . . 61

7.3.3

Monaadid semantika esitamisel . . . . . . . . . . . . . 63



7.3.4

Andmestruktuurid semantika esitamisel . . . . . . . . . 63

7.4 Lihtsamate konstruktsioonide semantikast . . . . . . . . . . . 63

7.4.1


Avaldised . . . . . . . . . . . . . . . . . . . . . . . . . 63

7.4.2


T¨u¨ubiavaldised . . . . . . . . . . . . . . . . . . . . . . 65

7.4.3


N¨aidised . . . . . . . . . . . . . . . . . . . . . . . . . . 65

7.4.4


Algebralised andmet¨u¨ubid . . . . . . . . . . . . . . . . 66

7.4.5


Deklaratsioonid . . . . . . . . . . . . . . . . . . . . . . 66

7.5 Funktsiooni rakendamise semantikast . . . . . . . . . . . . . . 67

7.5.1

Funktsiooni rakendamine . . . . . . . . . . . . . . . . . 67



4




Dostları ilə paylaş:
  1   2   3   4   5   6   7   8   9   ...   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ə