1 files changed, 40 insertions, 0 deletions
diff --git a/cleansmurf-trees.tex b/cleansmurf-trees.tex
new file mode 100644
index 0000000..6264697
--- /dev/null
+++ b/cleansmurf-trees.tex
@@ -0,0 +1,40 @@
+% vim: set spelllang=nl:
+\subsection{Afleidingsbomen}
+Door herhaaldelijk gebruik te maken van \CI{step} kunnen we gemakkelijk een
+afleidingsboom genereren. We maken hierbij gebruik van een aantal handige
+eigenschappen van afleidingsbomen voor Smurf:
+
+\begin{itemize}
+	\item Alle semantiekregels hebben ten hoogste één premisse, waardoor we een
+		boom als lijst van transities kunnen representeren.
+	\item Ieder commando heeft precies één regel. Hierdoor is aan het eerste
+		statement van een programma te herkennen welke regel wordt toegepast. Dit
+		hoeven we dus niet in de types \CI{Transition} en \CI{DerivationTree} op te
+		slaan.
+	\item Doordat condities van de semantiekregels enkel afhangen van de
+		linkerkant van de conclusie (het programma, de input en de toestand), en
+		deze informatie beschikbaar is op het moment dat de boom gemaakt wordt,
+		hoeven we geen backtracking toe te passen. Wanneer het niet lukt de regel
+		die bij het eerste commando van het programma hoort toe te passen, weten we
+		zeker dat er geen afleidingsboom bestaat.
+\end{itemize}
+
+De functie \CI{tree} is als volgt geïmplementeerd:
+
+\lstinputlisting[firstline=274]{CleanSmurf/Smurf.icl}
+
+Bij het genereren van bomen leggen we de input van te voren vast in een lijst.
+We slaan de output op in een andere lijst. Dit is wat het type \CI{ListIO}
+inhoudt --- de implementatie hiervan is irrelevant hier.
+
+Het eerste dat \CI{tree} doet is het berekenen van de volgende stap. Lukt dat
+niet (\CI{isNothing mbPgmSt}), dan kunnen we ook geen boom maken.
+
+Omdat \CI{step} voor een leeg programma een nieuw leeg programma oplevert,
+moeten we in deze functie controleren of het nieuwe programma leeg is. Is dit
+het geval, dan zetten we de $\lambda$-regel zelf in de boom als \CI{([],
+io.input, st) --> (io.input, [], st)}.
+
+Is dit niet het geval, dan maken we recursief een boom voor de premisse
+(\CI{tree pgm st io iof}). Lukt dit niet, dan kunnen we geen boom maken.
+Anders, dan voegen we de boom en de transitie gevonden met \CI{step} samen.