an_faculteit.tex

   1 \subsection{Faculteit}
   2 Als we de analyse op een compleet programma toepassen komt er een \textit{Piet}
   3 programma uit dat behoorlijk fors is maar netjes zijn werk doet. Dit programma
   4 berekent de faculteit van $x$ en stopt dat uiteindelijk in $y$.
   5 \begin{lstlisting}[title=Faculteit in \textit{While}]
   6 x:=5;
   7 y:=1;
   8 while $\neg$(x=1)
   9 do (
  10     y:=y*x;
  11     x:=x-1
  12 )
  13 \end{lstlisting}
  14
  15 In \textit{Piet} ziet dit er als volgt uit...
  16 \begin{lstlisting}[title=Faculteit in \textit{Piet'}]
  17 push 10     // x:=5
  18 push 1      // y:=1
  19
  20 MARKERING A:
  21             // Un(2)
  22             // $\neg$(x=1) $\equiv$ \neg(x-1)>0)
  23
  24
  25             // x-1
  26             // Un(2)
  27 push 2      //
  28 push 1      //
  29 roll        //
  30 dup         //
  31 push 3      //
  32 push 1      //
  33 roll        //
  34 push 1      //
  35 sub         //
  36 not         // $\neg(x-1)$
  37
  38 push 1      // zet $0$ op de stack
  39 push 1
  40 sub
  41
  42 gre         // $\neg(x-1)>0$ oftewel x=1
  43
  44 pointer     // als x=0 dan draait de DP niet en gaat het programma naar pad B
  45             // als x$\neq$ dan draait de DP en gaat het programma naar pad A
  46
  47 PAD A:
  48 skip        // een oneindig aantal witte blokken, y is nu x!
  49             // evt een outchar om $y$ naar standardout te printen
  50
  51 PAD B:
  52             // y:=y*x
  53             // Bin(1, 2)
  54 dup         // Un(1)
  55 push 3      // Un(2+1)
  56 push 2      //
  57 roll        //
  58 dup         //
  59 push 4      //
  60 push 1      //
  61 roll        //
  62 mul         // x*y
  63 push 2      // Ass(1)
  64 push 1
  65 roll
  66 pop
  67
  68             // x:=x-1
  69 push 2      // Un(2)
  70 push 1
  71 roll
  72 dup
  73 push 3
  74 push 1
  75 roll
  76
  77
  78 push 1      //
  79 sub         // x-1
  80 push 3      // Ass(2)
  81 push 2
  82 roll
  83 pop
  84 push 2
  85 push 1
  86 roll
  87             // nu gaat het programma weer via een wit pad naar markering A
  88 \end{lstlisting}
  89
  90 Wat in piet er uit zit als in \ref{fig:img3}
  91 \begin{figure}[H]
  92         \caption{Factulteit vanuit \textit{While} naar \textit{Piet}}
  93         \label{fig:img3}
  94         \centering
  95         \fbox{\includegraphics[natheight=320px, natwidth=256px, height=320px,
  96         width=256px]{img3.png}}
  97 \end{figure}
  98
  99 \begin{landscape}
 100 De afleidingsrij voor 1! ziet er als volgt uit:\\
 101 $
 102 \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\\
 103 \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\\
 104 \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\\
 105 \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\\
 106 \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\\
 107 \langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1;roll;push \: 1;push \: 3;dup, [\:], [\:], [1,1]\rangle \Rightarrow\\
 108 \langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1;roll;push \: 1;push \: 3, [\:], [\:], [1,1,1]\rangle \Rightarrow\\
 109 \langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1;roll;push \: 1, [\:], [\:], [3,1,1,1]\rangle \Rightarrow\\
 110 \langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1;roll, [\:], [\:], [1,3,1,1,1]\rangle \Rightarrow\\
 111 \langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;push \: 1, [\:], [\:], [1,1,1]\rangle \Rightarrow\\
 112 \langle pointer; not;greater;subtract;push\:1;push \: 1;not;subtract;, [\:], [\:], [1,1,1,1]\rangle \Rightarrow\\
 113 \langle pointer; not;greater;subtract;push\:1;push \: 1;not, [\:], [\:], [1,1,1]\rangle \Rightarrow\\
 114 \langle pointer; not;greater;subtract;push\:1;push \: 1, [\:], [\:], [1,1,1]\rangle \Rightarrow\\
 115 \langle pointer; not;greater;subtract;push\:1, [\:], [\:], [1,1,1,1]\rangle \Rightarrow\\
 116 \langle pointer; not;greater;subtract, [\:], [\:], [1,1,1,1,1]\rangle \Rightarrow\\
 117 \langle pointer; not;greater, [\:], [\:], [0,1,1,1]\rangle \Rightarrow\\
 118 \langle pointer; not, [\:], [\:], [1,1,1]\rangle \Rightarrow\\
 119 \langle pointer [\:], [\:], [0,1,1]\rangle \Rightarrow\\
 120 \langle [\:], [\:], [1,1]\rangle\\
 121 \\
 122 $
 123 Eerst worden x en y op de stack gestopt zodat de stack [y,x] = [1,1].
 124 Deze stack is gelijk aan de stack in de termineerende configuratie: 1 = 1! dus y = x!.
 125 Als bewijs dat de wiskundige operaties op de stack goed zijn uitgevoerd staat in
 126 de appendix onder het kopje voorbeelden een stukje code.  In het programma
 127 eenfaculteit worden alle wiskundige operaties die bij de commando's horen
 128 achter elkaar uitgevoerd op de stack, waarbij het resultaat [1,1] is.\\
 129 Bij de voorbeelden staan ook nog de programma's tweefaculteit en
 130 vijffaculteit die respectievelijk 2! en 5! uitrekenen.
 131 \end{landscape}