1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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
afleidingsboom 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 om het later wel in de output te kunnen tonen.
\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. Lukt
het wel, dan voegen we de boom en de transitie gevonden met \CI{step} samen.
|
