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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
% vim: set spelllang=nl:
\subsubsection{Het recursieve binnenste programma}
Het binnenste programma draait strings van lengte $n\ge1$ om. Hiervoor krijgt het
twee ``argumenten'' mee als $\StmPush$-commando's. Het eerste argument is een string in zijn
oorspronkelijke volgorde, die elke recursieve aanroep \'{e}\'{e}n karakter
kleiner wordt. Het tweede argument is een string die initieel de lege
string is, maar bij elke recursieve aanroep \'{e}\'{e}n karakter groter wordt
en de omgekeerde string voorstelt.
De reden dat dit programma niet voor de lege string werkt is de volgende: het
testen van waarden kost zoals we eerder hebben gezien een programma-aanroep. We
hebben ervoor gekozen om eerst de string te verkleinen en daarna te kijken of
we de lege string hebben bereikt (de hele string is omgedraaid) om te bepalen
of we dit programma nog eens moeten uitvoeren met nieuwe argumenten. Als je zou
willen bepalen of je inputstring leeg was voordat je deze verkleint zou je twee
recursieve programma's nodig hebben die elkaar telkens aanroepen: \'{e}\'{e}n
die als eerste test of de input leeg en op basis daarvan \'{o}f het andere
programma aanroept \'{o}f output geeft en eindigt, en een ander programma dat
de string verkleint en dan het eerste programma aanroept om weer de waarde te
testen. Dit is echter onnodig complex. Het leek ons beter om aan het einde te
testen of we door moeten gaan en het geval van de lege string op te vangen in
het buitenste programma.
Het recursieve omdraaiprogramma ziet er zo uit:
\begin{center}
\makebox{
\parbox{60mm}{
\begin{smurf}
\footnotesize
\emph{x-string} \emph{y-string}\\
"\textbackslash"program\textbackslash"p\textbackslash"grow\textbackslash"p\textbackslash"shrink\textbackslash"p\\
\textbackslash"shrink\textbackslash"gh\textbackslash"grow\textbackslash"g+\textbackslash"grow\textbackslash"p\\
\textbackslash"shrink\textbackslash"gt\textbackslash"shrink\textbackslash"p\textbackslash"shrink\textbackslash"g\\
\textbackslash"grow\textbackslash"gq\textbackslash"o\textbackslash"+\textbackslash"shrink\textbackslash"gq\\
\textbackslash"grow\textbackslash"gq\textbackslash"program\textbackslash"gq++\textbackslash"program\\
\textbackslash"g+\textbackslash"shrink\textbackslash"gp\textbackslash"\textbackslash"pgx"\\
\vspace{\baselineskip}
"program" p\\
"grow" p\\
"shrink" p\\
\vspace{\baselineskip}
"shrink" g h\\
"grow" g + "grow" p\\
"shrink" g t "shrink" p\\
\vspace{\baselineskip}
"shrink" g\\
\vspace{\baselineskip}
"grow" g q "o" +\\
\vspace{\baselineskip}
"shrink" g q "grow" g q\\
"program" g q + +\\
"program" g +\\
\vspace{\baselineskip}
"shrink" g p\\
\vspace{\baselineskip}
"" p\\
\vspace{\baselineskip}
g x
\end{smurf}
}
\parbox{8mm}{
\begin{smurf}
\footnotesize
(1)\\
(2)\\
~\\
~\\
~\\
~\\
~\\
~\\
(3)\\
~\\
~\\
~\\
(4)\\
~\\
(5)\\
~\\
(6)\\
~\\
(7)\\
~\\
(8)\\
~\\
~\\
~\\
(9)\\
~\\
(10)\\
~\\
(11)
\end{smurf}
}}
\end{center}
De programmaonderdelen worden hieronder toegelicht.
\begin{enumerate}
\item De argumenten worden er de eerste keer opgezet door het buitenste
programma. Merk op dat het y-argument in het buitenste programma
\smurfinline{"\textbackslash"\textbackslash""} is, wat de gequotifyde
versie is van de lege string. Het x-argument is dan de niet-lege input.
\item Hierna wordt de string van de rest van het programma (vanaf (3)) op de
stack gezet. Dit zorgt ervoor dat recursie mogelijk is.
\item Het programma en de argumenten worden in variabelen opgeslagen:
\smurfinline{program} voor het programma, \smurfinline{grow} voor het
rechterargument en \smurfinline{shrink} voor het linkerargument.
\item De waarde van \smurfinline{shrink} wordt opgehaald en vervangen door
zijn eerste karakter. Daarna wordt \smurfinline{grow} opgehaald en het
eerste karakter van \smurfinline{shrink} wordt eraan toegevoegd. Het
resultaat hiervan wordt weggeschreven naar \smurfinline{grow}.
\item Hier wordt \smurfinline{shrink} vervangen door alles behalve zijn
eerste karakter. Het eerste karakter van \smurfinline{shrink} is dus
verplaatst naar het einde van \smurfinline{grow}.
\item De nieuwe waarde van \smurfinline{shrink} wordt nu alvast op de stack
gezet, voor dezelfde reden dat dit in het buitenste programma met
\smurfinline{input} gebeurde. Wanneer we hem later nodig hebben hebben we
niet de garantie dat de variabelenaam niet overschreven is, dus we zetten
hem er nu al op.
\item De nieuwe waarde van \smurfinline{grow} wordt opgehaald en gequotifyed.
Ook voegen we \smurfinline{o} er aan toe. Zo vormt het een programmastring
die die waarde zou outputten wanneer uitgevoerd. Dit moeten we doen als
\smurfinline{shrink} leeg is geworden. Merk op dat het programma dat moet
worden uitgevoerd wanneer de string leeg is geworden in tegenstelling tot
in het buitenste programma hier v\'{o}\'{o}r het andere programma wordt
aangemaakt. Dit doen we omdat we hier een waarde van een variabele
gebruiken en we niet weten of de variabele straks overschreven wordt. We
bouwen deze programmastring dus alvast, maar laten hem nog gewoon op de
stack staan.
\item \smurfinline{shrink} en \smurfinline{grow} worden opgehaald en
gequotifyed. Ook \smurfinline{program} wordt opgehaald en gequotifyed. Dit
alles concateneren we. De variabele \smurfinline{program} wordt nog eens
opgehaald, niet gequotifyed en aan de eerdere string toegevoegd. Nu is deze
hele string gelijk aan het hele programma, maar met de nieuwe waarden van
\smurfinline{grow} en \smurfinline{shrink} als argumenten.
\item Nu komt het deel waar we de waarde van \smurfinline{shrink} testen om
te kiezen of we output moeten geven, of nog een recursiestap moeten
uitvoeren. De waarde van \smurfinline{shrink} wordt opgehaald en gebruikt
als variabelenaam om het programma dat we in (8) hadden gebouwd naar weg te
schrijven. Vanaf dit punt kunnen we geen van onze variabelen meer
gebruiken, omdat de waarde van \smurfinline{shrink} toevallig gelijk zou
kunnen zijn geweest aan de naam van een van onze variabelen
\item Nu schrijven we het programma dat we in (7) hadden gebouwd en nog op de
stack stond weg naar de variabele $lambda$.
\item We halen de waarde op van de variabele met als naam de waarde van
\smurfinline{shrink} die we in (6) al op de stack hadden gezet. Als
\smurfinline{shrink} leeg was vinden we het programma uit (7). Anders
vinden we het programma uit (8). We voeren het gevonden programma uit.
\end{enumerate}
|
