diff options
Diffstat (limited to 'opdracht8/opdracht8.tex')
| -rw-r--r-- | opdracht8/opdracht8.tex | 133 |
1 files changed, 133 insertions, 0 deletions
diff --git a/opdracht8/opdracht8.tex b/opdracht8/opdracht8.tex new file mode 100644 index 0000000..5422b83 --- /dev/null +++ b/opdracht8/opdracht8.tex @@ -0,0 +1,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} |