summaryrefslogtreecommitdiff
path: root/cleansmurf-trees.tex
diff options
context:
space:
mode:
Diffstat (limited to 'cleansmurf-trees.tex')
-rw-r--r--cleansmurf-trees.tex40
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.