% vim: set spelllang=nl:
\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 Context: het aannameprobleem (eerst aan de kant van de programmeur,
				dan aan de kant van de compiler designer).
			\item Korte opsomming van de voordelen van functioneel programmeren in
				deze context.
			\item Inhoudsopgave.
			\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, abort /
				run-time errors.  Waarschijnlijk met een onvolledig minimaal voorbeeld
				om het idee te laten zien.
			\item Error reporting met de \verb$Either$ monad.
			\item De implementatie (verkort).
			\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?}
			\item Suggestie voor een alternatieve AST met \verb$[Stm]$ (impliciete
				statementcompositie).
			\item Suggestie voor positionele errors door \verb$:: Token$ aan te
				passen met een locatie.
		\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}
