1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
\documentclass[a4paper]{article}
\usepackage[dutch]{babel}
\usepackage{geometry}
\usepackage[hidelinks]{hyperref}
\usepackage[utf8]{inputenc}
\title{Academisch Schrijven\\\large{Opdracht 8}}
\author{Camil Staps}
\def\NB#1{[\textbf{NB}: #1]}
\def\opt#1{(\textbf{Optioneel}: #1)}
\begin{document}
\maketitle
\section*{Globale aanpak}
Een bottom-up-aanpak is over het algemeen meer geschikt om de gebruiker door de
ontwikkeling van een programma heen te loodsen. Alleen in specifieke gevallen
(bijvoorbeeld wanneer de aanpak op hoger niveau invloed heeft op de
implementatie op lager niveau) is een top-down-aanpak praktisch. Een
bottom-up-aanpak heeft echter als voordeel dat de lezer stukken voorbeeldcode
direct kan uitproberen. Ik zal dus een bottom-up-aanpak gebruiken.
Aan de hand van voorbeelden zal ik de voordelen van een functionele
programmeerstijl bij het schrijven van een interpreter voor een imperatieve
taal laten zien. Dit betekent dat we globaal drie stappen doorlopen: lexen,
parsen, interpreteren. Het ligt voor de hand iedere stap een eigen sectie te
geven.
We zullen een klein uitstapje moeten maken om het evalueren van expressies, wat
enigszins losstaat van het interpreteren, te bekijken.
Aan het eind van ieder onderdeel zal ik even stilstaan om alternatieve
(gelijkwaardige) oplossingen en eventuele uitbreidingen te bespreken. Ook al
wijk ik daarmee af van het standaardstramien voor een wetenschappelijk artikel,
lijkt dat logischer aangezien lexen, parsen en interpreteren duidelijk
verschillende dingen zijn.
Aan het eind van het artikel zal ik de voordelen van de functionele aanpak
opsommen en met eerder behandelde voorbeelden beargumenteren.
\section*{Indeling in secties en paragrafen}
\begin{enumerate}
\item Inleiding
\begin{itemize}
\item Streven naar leesbare code en gebruiksvriendelijke programma's,
niet efficiëntie.
\item De voorbeeldtaal While (Nielson \& Nielson): beschrijving van de
syntax.
\end{itemize}
\item Lexen
\begin{itemize}
\item Eén zin over wat lexen is. Welke types en functies hebben we nodig?
\item Naïeve aanpak: recursief een \verb$[Char]$
doorlopen, run-time errors als we iets onbekends tegenkomen.
Waarschijnlijk met een onvolledig minimaal voorbeeld om het idee te
laten zien.
\item Error reporting met de \verb$Either$ monad.
\item De implementatie.
\item Suggestie voor een uitbreiding: positionele errors.
\end{itemize}
\item Parsen
\begin{itemize}
\item Eén zin over wat parsen is. Welke types en functies hebben we
nodig?
\item Voordelen van het overloaden van de \verb$parse$-functie: meerdere
types mogelijk voor de AST. Korte noot waarom dit niet nodig is voor
\verb$lex$ (de syntax ligt vast onafhankelijk van de implementatie).
Deze opmerking past niet in de vorige sectie omdat overloading dan nog
niet als mogelijk idee is besproken.
\item Parser monads: algemene idee van G. Hutton en E. Meijer, 1996;
specifiek over Yard de scriptie van P. Jager, 2014.
\item Parserdefinities afleiden van grammatica's.
\item Links-recursieve expressies: herschrijven naar een
niet-links-recursieve grammatica (zie T. Norvell, 1999) (met voorbeeld)
en de klassieke oplossing met extra nonterminals. \NB{Valt dit nog
binnen de scope? --- Waarschijnlijk wel, anders komen lezers dit
probleem zelf tegen.}
\item Suggestie voor een alternatieve AST met \verb$[Stm]$ (impliciete
statementcompositie).
\end{itemize}
\item Expressies evalueren
Dit is een apart onderdeel (van interpreteren) omdat het onafhankelijk is
van de interpretatiemethode (gebaseerd op SOS, NS, \dots).
\begin{itemize}
\item Twee implementaties voor de state: \verb$[(Var,Val)]$ en
\verb$Var -> Val$. Voor- en nadelen. Complexiteit is hetzelfde (functie
is te vergelijken met een linked list).
\item Wederom: error reporting met de \verb$Either$ monad;
\verb$Var -> Either Error Val$.
\item Implementaties van \verb$eval$ voor \verb$AExpr$ en \verb$BExpr$.
\end{itemize}
\item Interpreteren
\begin{itemize}
\item Eén zin over wat interpreteren is. Welke types en functies hebben
we nodig?
\item Voordelen van het overloaden van de \verb$run$-functie: meerdere
types voor de AST, meerdere interpretatiemethodes (gebaseerd op SOS,
NS, \dots).
\item Van natuurlijke semantiek naar een interpreter: de implementatie.
\item De implementatie nader bekeken: voordelen van monadische
interpretatie van een imperatieve taal om volgorde van executie aan te
geven; bv. in de \verb$While$-regel.
\item \opt{wat verandert er als we structurele operationele semantiek
gebruiken?}
\end{itemize}
\item Alles samenvoegen
\begin{itemize}
\item Genieten van de \verb$Either$ monad:
\verb$interpret :== lex >>= parse >>= run$. \NB{Helaas breekt
overloading dit, waardoor we tussenstappen moeten maken en de types
expliciet moeten opschrijven. Het idee blijft hetzelfde.}
\end{itemize}
\item Conclusies: de voordelen van de functionele aanpak
\begin{itemize}
\item Error reporting met de \verb$Either$ monad.
\item Hogere-orde functies (de state).
\item Simpele vertaalslag van semantiekregels naar implementatie van
\verb$run$.
\item Monadische \verb$run$ om de volgorde van executie vast te leggen.
\end{itemize}
\end{enumerate}
\end{document}
|
