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¨
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¨
u¨
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¨
u¨
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