\subsection{Structurele operationele semantiek}
Bij natuurlijke semantiek(ns) ligt de nadruk op de relatie tussen de begin en
-de eind state. Het nadeel hiervan is dat programma’s die niet termineren geen
+de eind state. Het nadeel hiervan is dat programma's die niet termineren geen
bewijsbomen hebben. Hierdoor is het niet mogelijk om eigenschappen te bewijzen
-voor zulke programma’s. Bij structurele operationele semantiek(sos) ligt de
+voor zulke programma's. Bij structurele operationele semantiek(sos) ligt de
nadruk juist op de individuele stappen van de executie en zijn er w\'el
-bewijsrijen voor programma’s die niet termineren.\\
+bewijsrijen voor programma's die niet termineren.\\
Om deze redenen hebben we gekozen voor sos.\\
Een toestand in onze semantiek wordt beschreven door drie stacks; input, output
en programma. Respectievelijk benoemen we deze met $s_i, s_o, s$ en beschrijven
ze de STDIN, STDOUT en interne stack van het programma. Stacks worden
-gerepresenteerd als: $s=[e_0, e_1, \dots, e_n]$ waarbij $e_i\in\mathbb{Z}$\\
-Het transitie systeem zal twee verschillende transities kennen, namelijk:\\
+gerepresenteerd als: $s=[e_0, e_1, \dots, e_n]$ waarbij $e_i\in\mathbb{Z}$
+ en waarbij het bovenste element op de stack gerepresenteerd wordt door het
+ eerste element in de lijst.\\
+Het transitiesysteem zal twee verschillende transities kennen, namelijk:\\
$\langle S, s_i, s_o, s\rangle\Rightarrow\langle S', s_i', s_o', s'\rangle$ en\\
$\langle S, s_i, s_o, s\rangle\Rightarrow\langle s_i', s_o', s'\rangle$\\
-Waarbij de laatste transitie duidt op een terminerende transitie en de eerste
-op een niet terminerende transitie.\\
+Waarbij bij de eerste transitie de executie van S niet na een stap klaar is en waarbij
+de tweede transitie duidt op een terminerende transitie.\\
\subsection{Semantiekbeschrijving}
+Om de semantiekregels te kunnen beschrijven maken we gebruik van hulpfuncties.
+Hieronder staat het type van de functies en een korte beschrijving.
+De implementatie is gedaan in de vorm van een functioneel programma in de taal \textit{Clean}.
+De implementatie van de functies staat in de appendix.
+Elke functie wordt op de volgende manier aangegeven: \textit{naam functie} (\textit{naam in appendix}, r. \textit{regelnummer in appendix})\\
+
+delete functie (d, r. 5):\\
Om het bovenste element van een stack weg te kunnen gooien gebruiken we de volgende
functie:\\
$$\mathcal{D} : Stack \rightarrow Stack$$
-$$\mathcal{D} [\:] = [\:]$$
-$$\mathcal{D} [a:rest] = [rest] $$
-Deze functie haalt het bovenste element van de stack en gooit deze weg.\\
+Deze functie haalt het bovenste element van de stack en gooit dit weg.\\
+extend functie (e, r. 9):\\
Om een stack uit te kunnen breiden met een element gebruiken we de volgende
functie:\\
-$$\mathcal{E} : Stack\rightarrow (\mathbb{Z} \rightarrow Stack)$$\\
-Deze functie neemt een stack en een integer en voegt de integer toe bovenop de
+$$\mathcal{E} : \mathbb{Z}\rightarrow (Stack\rightarrow Stack)$$\\
+Deze functie neemt een integer en een stack en voegt de integer toe bovenop de
stack.\\
+add functie (add, r. 13):\\
Om de bovenste twee elementen van een stack op te tellen gebruiken we de volgende
functie:\\
$$\mathcal{ADD} : Stack \rightarrow Stack$$
-$$\mathcal{ADD} [\:] = [\:]$$
-$$\mathcal{ADD} [a] = [a] $$
-$$\mathcal{ADD} [a:b:rest] = [b+a:rest] $$\\
-Deze functie haalt de bovenste twee waarden van de stack, telt ze bij elkaar op, en stopt
+Deze functie haalt de bovenste twee waarden van de stack, telt ze bij elkaar op, en legt
het resultaat bovenop de stack.\\
+subtract functie (sub, r. 18)\\
Om de bovenste twee elementen van een stack van elkaar af te trekken gebruiken we
de volgende functie:\\
$$\mathcal{SUB} : Stack \rightarrow Stack$$
-$$\mathcal{SUB} [\:] = [\:]$$
-$$\mathcal{SUB} [a] = [a] $$
-$$\mathcal{SUB} [a:b:rest] = [b-a:rest] $$\\
Deze functie haalt de bovenste twee elementen van de stack, trekt de bovenste
-waarde van de tweede bovenste waarde af, en stopt het resultaat bovenop de stack.
+waarde van de tweede bovenste waarde af, en legt het resultaat bovenop de stack.\\
+multiply functie (mul, r. 23):\\
Om de bovenste twee elementen van een stack te vermenigvuldigen gebruiken we de
volgende functie:\\
$$\mathcal{MUL} : Stack \rightarrow Stack$$
-$$\mathcal{MUL} [\:] = [\:]$$
-$$\mathcal{MUL} [a] = [a] $$
-$$\mathcal{MUL} [a:b:rest] = [b*a:rest] $$\\
Deze functie haalt de bovenste twee elementen van de stack, vermenigvuldigt ze,
en stopt het resultaat bovenop de stack.\\
+division functie (div, r. 28):\\
Om de geheeltallige deling van de bovenste twee elementen van de stack bovenop de
stack te krijgen gebruiken we de volgende functie:\\
$$\mathcal{DIV} : Stack \rightarrow Stack$$
-$$\mathcal{DIV} [\:] = [\:]$$
-$$\mathcal{DIV} [a] = [a] $$
-$$\mathcal{DIV} [a:b:rest] = [b/a:rest] $$\\
Deze functie haalt de bovenste twee elementen van de stack, berekent de
geheeltallige deling van de tweede bovenste waarde door de bovenste waarde,
en stopt het resultaat bovenop de stack.\\
-Om gebruiken we de
-volgende functie:\\
+modulo functie (modc, r. 33):\\
+Om de tweede bovenste waarde modulo de bovenste waarde te berekenen
+gebruiken we de volgende functie:\\
$$\mathcal{MOD} : Stack \rightarrow Stack$$
-$$\mathcal{MOD} [\:] = [\:]$$
-$$\mathcal{MOD} [a] = [a] $$
-$$\mathcal{MOD} [a:b:rest] = [b \: mod \: a:rest] $$\\
-Deze functie haalt de bovenste twee elementen van de stack, berekent het resultaat van de tweede bovenste
-waarde modulo de bovenste waarde, en stopt dit bovenop de stack.\\
+Deze functie haalt de bovenste twee elementen van de stack, berekent het
+resultaat van de tweede bovenste waarde modulo de bovenste waarde, en
+stopt dit bovenop de stack.\\
+duplicate functie (dup, r. 38):\\
Om het bovenste element van een stack te dupliceren gebruiken we de
volgende functie:\\
$$\mathcal{DUP} : Stack \rightarrow Stack$$
-$$\mathcal{DUP} [\:] = [\:]$$
-$$\mathcal{DUP} [a:rest] = [a:a:rest] $$\\
-Deze functie haalt stopt een kopie van de bovenste waarde bovenop de stack.\\
+Deze functie haalt de bovenste waarde van de stack en stopt een kopie
+en de bovenste waarde bovenop de stack.\\
-Om de gebruiken we de
+not functie (notc, r. 42):\\
+Om te kijken of de bovenste waarde gelijk is aan 0 gebruiken we de
volgende functie:\\
-$$\mathcal{NOT} : Stack \rightarrow Stack$$
-$$\mathcal{NOT} [\:] = [\:]$$
-$$\mathcal{NOT} [0:rest] = [1:rest]$$
-$$\mathcal{NOT} [\_:rest] = [0:rest] $$\\
-
+$$\mathcal{NOT} : Stack \rightarrow Stack$$\\
Deze functie neemt het bovenste element van de stack en stopt 0 bovenaan de
stack als deze waarde niet gelijk is aan 0 en 1 als deze waarde gelijk is aan 0.\\
-Om gebruiken we de
-volgende functie:\\
-$$\mathcal{GRE} : Stack \rightarrow Stack$$
-$$\mathcal{GRE} [\:] = [\:]$$
-$$\mathcal{GRE} [a] = [a] $$
-$$\mathcal{GRE} [a:b:rest]$$
-$$\qquad \qquad | \: a \geq b = [0:rest]$$
-$$\qquad \qquad | \: a < b = [1:rest]$$\\
-
-$$\mathcal{ROLL} : Stack \rightarrow Stack$$
-$$\mathcal{ROLL} [\:] = [\:]$$
-$$\mathcal{ROLL} [a] = [a] $$
-$$\mathcal{ROLL} [a:b:rest]$$
-$$\qquad \qquad | modulo \: a \: b == 0 = rest$$
-$$\qquad \qquad | b <= 0 = rest$$
-$$\qquad \qquad | b > length rest = rest$$
-$$\qquad \qquad | a == 1 = roll1 [b:rest]$$
-$$\qquad \qquad | a > 0 = roll([a-1] ++ [b] ++ roll1 [b:rest]$$
-$$\qquad \qquad | a < 0 = roll(modulo \: a \: b] ++ [b:rest])$$
-
-$$\mathcal{ROLL}1 : Stack \rightarrow Stack$$
-$$\mathcal{ROLL}1 [1:rest] = [rest]$$
-$$\mathcal{ROLL}1 [b:c:d:rest] = [d] ++ \mathcal{ROLL}1 [b-1:c:rest]$$
-
-
-Deze functie haalt de bovenste twee elementen van de stack en stopt 1 bovenop
-de stack als het tweede bovenste element een hogere waarde heeft als dat van het
-bovenste element. Anders word 1 bovenop de stack gestopt.\\
-
-Met behulp van deze gedefinieerde functies kunnen we nu de volgende semantiekregels opstellen:\\
-
-$
-{[pop_{sos}]}\qquad
+greater functie (gre, r. 47):\\
+Om te kijken of de tweede bovenste waarde groter is dan de bovenste waarde
+gebruiken we de volgende functie:\\
+$$\mathcal{GRE} : Stack \rightarrow Stack$$\\
+Deze functie haalt de bovenste twee waarden van de stack en stopt een 1 bovenop
+de stack als de tweede bovenste waarde groter is dan de bovenste waarde. Anders
+wordt een 0 bovenop de stack gestopt.\\
+
+roll functie (roll, r. 54):\\
+Om de elementen op de stack te verschuiven gebruiken we de volgende functie:\\
+$$\mathcal{ROLL} : Stack \rightarrow Stack$$\\
+Deze functie haalt de bovenste twee elementen van de stack 'rolt' de rest van de stack tot een diepte die gelijk is aan de waarde van het tweede bovenste element. Een rol tot diepte \textit{n} verschuift de elementen 1 tot en met \textit{n} allemaal 1 plaats naar boven. Vervolgens wordt het eerste element van de stack op plaats \textit{n} neergelegd. Het aantal keren dat de stack gerold word is gelijk aan de waarde van het bovenste element. Als deze waarde negatief is word de stack in tegenovergestelde richting gerold. Dit houdt in dat bij elke rol het element op plaats \textit{n} bovenop de stack word gelegd, en de rest van de elementen (dat boven het element op plaats \textit{n} lagen) 1 plaats naar beneden wordt verschoven.\\
+
+out number (output stack) functie (outnum, r. 70):\\
+Deze functie past de output stack aan als er een integer naartoe geschreven wordt:\\
+$$\mathcal{OUTN_{SO}} : Stack \rightarrow Stack$$\\
+Deze functie haalt het bovenste element van de stack en stopt dit element bovenop de output stack.\\
+
+in number (stack) functie (innum, r. 75):\\
+Deze functie past de stack aan als er een integer naartoe geschreven wordt:\\
+$$\mathcal{INN_S} : Stack \rightarrow Stack$$\\
+Deze functie haalt het bovenste element van de input stack en stopt dit element bovenop de output stack.\\
+
+Met behulp van deze gedefinieerde functies kunnen we nu de semantiekregels opstellen.
+De meeste regels spreken redelijk voor zich: als een commando wordt uitgevoerd, zorgt dit voor een verandering in de bijbehorende stack. Deze verandering komt tot stand door het toepassen van de bijbehorende hulpfunctie op deze stack.
+
+Voor de semantiekregels voor de compositie halen we, in tegenstelling tot de normale gang van zaken bij sos, steeds een commando van het einde van de lijst af.
+Hiervoor is gekozen zodat de afleidingsrijen makkelijk te controleren zijn door bij de implementatie in \textit{Clean} de functies een voor een op een stack toe te passen.\\
+
+\begin{alignat*}{2}
+{[comp^1_{sos}]}\qquad &
+\frac{\langle S_2, s\rangle \Rightarrow \langle S'_2, s_i', s_o', s'\rangle}
+{\langle S_1 ;S_2, s\rangle \Rightarrow \langle S_1;S'_2, s_i', s_o', s'\rangle}\\
+{[comp^2_{sos}]}\qquad &
+\frac{\langle S_2, s\rangle \Rightarrow \langle s_i', s_o', s'\rangle}
+{\langle S_1 ;S_2, s\rangle \Rightarrow \langle S_1, s_i', s_o', s'\rangle}\\
+{[pop_{sos}]}\qquad &
\langle pop, s_i, s_o, s\rangle \Rightarrow
\langle s_i, s_o,\mathcal{D}(s)\rangle\\
{[add_{sos}]}\qquad
-\langle add, s_i, s_o, s\rangle \Rightarrow
+&\langle add, s_i, s_o, s\rangle \Rightarrow
\langle s_i, s_o, \mathcal{ADD}(s)\rangle\\
-{[subtract_{sos} ]}\qquad
+{[subtract_{sos} ]}\qquad &
\langle subtract, s_i, s_o, s\rangle \Rightarrow
\langle s_i, s_o, \mathcal{SUB}(s)\rangle\\
-{[multiply_{sos}]}\qquad
+{[multiply_{sos}]}\qquad &
\langle multiply, s_i, s_o, s\rangle \Rightarrow
\langle s_i, s_o, \mathcal{MUL}(s)\rangle\\
-{[divide_{sos}]} \qquad
+{[divide_{sos}]} \qquad &
\langle divide, s_i, s_o, s\rangle \Rightarrow
\langle s_i, s_o, \mathcal{DIV}(s)\rangle\\
-{[mod_{sos}]} \qquad\qquad
+{[mod_{sos}]} \qquad &
\langle mod, s_i, s_o, s\rangle \Rightarrow
\langle s_i, s_o, \mathcal{MOD}(s)\rangle\\
-{[duplicate_{sos}]} \qquad
+{[duplicate_{sos}]} \qquad &
\langle duplicate, s_i, s_o, s\rangle \Rightarrow
\langle s_i, s_o, \mathcal{DUP}(s)\rangle\\
-{[not_{sos}]}\qquad\qquad
+{[not_{sos}]} \qquad &
\langle not, s_i, s_o, s\rangle \Rightarrow
\langle s_i, s_o, \mathcal{NOT}(s)\rangle\\
-{[greater_{sos}]} \qquad
+{[greater_{sos}]} \qquad &
\langle greater, s_i, s_o, s\rangle \Rightarrow
\langle s_i, s_o, \mathcal{GRE}(s)\rangle\\
-{[push_{sos}]} \qquad
+{[pointer_{sos}]} \qquad &
+\langle pointer, s_i, s_o, s\rangle \Rightarrow
+\langle s_i, s_o, \mathcal{D}(s)\rangle\\
+{[switch_{sos}]} \qquad &
+\langle switch, s_i, s_o, s\rangle \Rightarrow
+\langle s_i, s_o, \mathcal{D}(s)\rangle\\
+{[push_{sos}]} \qquad &
\langle push \: n, s_i, s_o, s\rangle \Rightarrow
\langle s_i, s_o, \mathcal{E}(n,s)\rangle\\
-{[roll_{sos}]} \qquad
+{[roll_{sos}]} \qquad &
\langle roll, s_i, s_o, s\rangle \Rightarrow
\langle s_i, s_o, \mathcal{ROLL}(s)\rangle\\
-{[inchar_{sos}]} \qquad
-\langle inchar, s_i, s_o, s\rangle \Rightarrow
-\langle s_i, s_o, s\rangle\\
-{[innum_{sos}]} \qquad
+{[innum_{sos}]} \qquad &
\langle innum, s_i, s_o, s\rangle \Rightarrow
-\langle s_i, s_o, s\rangle\\
-{[outchar_{sos}]} \qquad
-\langle outchar, s_i, s_o, s\rangle \Rightarrow
-\langle s_i, s_o, s\rangle\\
-{[outnum_{sos}]} \qquad
+\langle \mathcal{D}(s_i), s_o, \mathcal{INN_S}(s)\rangle\\
+{[outnum_{sos}]} \qquad &
\langle outnum, s_i, s_o, s\rangle \Rightarrow
-\langle s_i, s_o, s\rangle\\
-$
+\langle s_i, \mathcal{OUTN_{SO}}(s_o),\mathcal{D}(s)\rangle\\
+\end{alignat*}
+
repositories / sec1415.git / blobdiff