% 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}