X-Git-Url: https://git.martlubbers.net/?a=blobdiff_plain;f=an_faculteit.tex;h=59fd9214cb5cbdf928d1e196b7c3f06e8e834726;hb=d5eb78db13b8b04fdf0a3edf3e636dd9006948af;hp=eab5607d6615a9ea9a1086f0a8aa5017eab93d24;hpb=e9e87a8181b11d95c08171886cd625eafc34fdf0;p=sec1415.git diff --git a/an_faculteit.tex b/an_faculteit.tex index eab5607..59fd921 100644 --- a/an_faculteit.tex +++ b/an_faculteit.tex @@ -14,35 +14,118 @@ do ( In \textit{Piet} ziet dit er als volgt uit... \begin{lstlisting}[title=Faculteit in \textit{Piet'}] -push 5 // x is vanaf nu variabele 1 -push 1 // y is vanaf nu variabele 2 +push 10 // x:=5 +push 1 // y:=1 MARKERING A: -Un(1) // variabele x wordt klaargezet -push 1 // de waarde 1 wordt klaargezet -sub // subtractie om straks gelijkheid te kunnen bepalen -push 1 // de waarde 1 word gepushed om 0 te maken -dup // de waarde 1 staat er nu twee keer op -sub // 0 staat op de stack om groterdan relatie te bepalen -push 2 // klaarmaken om de bovenste twee te swappen -push 1 // idem -roll // swappen -gre // als x>0 dan ligt 1 op de stack anders 0 -not // als x=0 dan ligt 1 op de stack anders 0 -pointer // als x=0 dan draait de DP niet en gaat het programma naar pad A - // als x$\neq$ dan draait de DP en gaat het programma naar pad B + // Un(2) + // $\neg$(x=1) $\equiv$ \neg(x-1)>0) + + + // x-1 + // Un(2) +push 2 // +push 1 // +roll // +dup // +push 3 // +push 1 // +roll // +push 1 // +sub // +not // $\neg(x-1)$ + +push 1 // zet $0$ op de stack +push 1 +sub + +gre // $\neg(x-1)>0$ oftewel x=1 + +pointer // als x=0 dan draait de DP niet en gaat het programma naar pad B + // als x$\neq$ dan draait de DP en gaat het programma naar pad A PAD A: -skip //een oneindig aantal witte blokken, y is nu x! +skip // een oneindig aantal witte blokken, y is nu x! + // evt een outchar om $y$ naar standardout te printen PAD B: -Bin(1, 2) // x en y worden klaargezet om y opnieuw te assignen -mul // x*y ligt boven op de stack -Ass(2) // x*y wordt geassigned aan y -Un(1) // x wordt klaargezet -push 1 // 1 wordt klaargezet -sub // x-1 ligt op de stack -Ass(1) // x-1 wordt geassigned aan x - // nu gaat het programma weer via een wit pad naar markering A + // y:=y*x + // Bin(1, 2) +dup // Un(1) +push 3 // Un(2+1) +push 2 // +roll // +dup // +push 4 // +push 1 // +roll // +mul // x*y +push 2 // Ass(1) +push 1 +roll +pop + // x:=x-1 +push 2 // Un(2) +push 1 +roll +dup +push 3 +push 1 +roll + + +push 1 // +sub // x-1 +push 3 // Ass(2) +push 2 +roll +pop +push 2 +push 1 +roll + // nu gaat het programma weer via een wit pad naar markering A \end{lstlisting} + +Wat in piet er uit zit als in \ref{fig:img3} +\begin{figure}[H] + \caption{Factulteit vanuit \textit{While} naar \textit{Piet}} + \label{fig:img3} + \centering + \fbox{\includegraphics[natheight=320px, natwidth=256px, height=320px, + width=256px]{img3.png}} +\end{figure} + +\begin{landscape} +De afleidingsrij voor 1! ziet er als volgt uit:\\ +$ +\langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1;roll;push \: 1;push \: 3;dup;roll;push \: 1;push \: 2;push \: 1;push \: 1, [\:], [\:], [\:]\rangle \Rightarrow\\ +\langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1;roll;push \: 1;push \: 3;dup;roll;push \: 1;push \: 2;push \: 1, [\:], [\:], [1]\rangle \Rightarrow\\ +\langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1;roll;push \: 1;push \: 3;dup;roll;push \: 1;push \: 2, [\:], [\:], [1,1]\rangle \Rightarrow\\ +\langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1;roll;push \: 1;push \: 3;dup;roll;push \: 1, [\:], [\:], [2,1,1]\rangle \Rightarrow\\ +\langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1;roll;push \: 1;push \: 3;dup;roll, [\:], [\:], [1,2,1,1]\rangle \Rightarrow\\ +\langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1;roll;push \: 1;push \: 3;dup, [\:], [\:], [1,1]\rangle \Rightarrow\\ +\langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1;roll;push \: 1;push \: 3, [\:], [\:], [1,1,1]\rangle \Rightarrow\\ +\langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1;roll;push \: 1, [\:], [\:], [3,1,1,1]\rangle \Rightarrow\\ +\langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1;roll, [\:], [\:], [1,3,1,1,1]\rangle \Rightarrow\\ +\langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1, [\:], [\:], [1,1,1]\rangle \Rightarrow\\ +\langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;, [\:], [\:], [1,1,1,1]\rangle \Rightarrow\\ +\langle pointer; not;greater;subtract;push\:1;push \: 1;not, [\:], [\:], [1,1,1]\rangle \Rightarrow\\ +\langle pointer; not;greater;subtract;push\:1;push \: 1, [\:], [\:], [1,1,1]\rangle \Rightarrow\\ +\langle pointer; not;greater;subtract;push\:1, [\:], [\:], [1,1,1,1]\rangle \Rightarrow\\ +\langle pointer; not;greater;subtract, [\:], [\:], [1,1,1,1,1]\rangle \Rightarrow\\ +\langle pointer; not;greater, [\:], [\:], [0,1,1,1]\rangle \Rightarrow\\ +\langle pointer; not, [\:], [\:], [1,1,1]\rangle \Rightarrow\\ +\langle pointer [\:], [\:], [0,1,1]\rangle \Rightarrow\\ +\langle [\:], [\:], [1,1]\rangle\\ +\\ +$ +Eerst worden x en y op de stack gestopt zodat de stack [y,x] = [1,1]. +Deze stack is gelijk aan de stack in de termineerende configuratie: 1 = 1! dus y = x!. +Als bewijs dat de wiskundige operaties op de stack goed zijn uitgevoerd staat in +de appendix onder het kopje voorbeelden een stukje code. In het programma +eenfaculteit worden alle wiskundige operaties die bij de commando's horen +achter elkaar uitgevoerd op de stack, waarbij het resultaat [1,1] is.\\ +Bij de voorbeelden staan ook nog de programma's tweefaculteit en +vijffaculteit die respectievelijk 2! en 5! uitrekenen. +\end{landscape} \ No newline at end of file