diff options
Diffstat (limited to 'cleansmurf-trees.tex')
-rw-r--r-- | cleansmurf-trees.tex | 40 |
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. |