\chapter{Lambdakalk"ul im Fortsetzungsstil als Zwischensprache} \label{TML}


Aufgrund der gro\3en semantischen L"ucke zwischen
Konstrukten von Hochsprachen und den
ausf"uhrbaren Maschinenbefehlen werden beim "Ubersetzungsvorgang
Transformationen "uber mehrere Zwischenrepr"asentationen durchgef"uhrt. Eine der 
Zwischenstufen dient als Repr"asentation f"ur Optimierungsalgorithmen, wobei diese 
je nach Quellsprache, Grad der \mbox{erw"unschten} Maschinen\-un\-ab\-h"angig\-keit und
erhofftem Optimierungserfolg mehr oder weniger in der \mbox{Mitte} der semantischen
L"ucke angesiedelt sein kann. Eine h"aufig verwendete Zwischen\-sprache f"ur
"Ubersetzer imperativer Sprachen ist der sogenannte \glqq Drei-Adre\3-Code\grqq,
dessen einzelne Instruktionen aus Tupeln der Form 
{\sf $<$Operation, Zielvariable, Quellvariable1, Quellvariable2$>$}
bestehen. 
Die Vorz"uge dieser Repr"asentation f"ur imperative Sprachen
liegen in der ein\-fachen Generierbarkeit
aus dem abstrakten Syntaxbaum  und in
der Freilegung aller Register\-anforderungen. Ferner dient
sie  als Grundlage vieler Optimierungs- und Daten\-flu\3\-algorithmen,
die in \cite{Dragonbook} beschrieben sind. Ein gutes Beispiel
f"ur einen optimierenden "Ubersetzer, der auf Drei-Adre\3-Code
Optimierungen durchf"uhrt, ist der PL.8-"Ubersetzer
f"ur verschiedene Quell- und Zielsprachen \cite{Auslander82}.



Drei-Adre\3-Code ist f"ur das Tycoon-System aus folgenden Gr"unden
allerdings weniger gut geeignet:

\begin{itemize}

\item
Die semantische Ebene des klassischen Drei-Adre\3-Codes ist, gemessen an den
Anforderungen des Tycoon-Systems, zu nahe an realem imperativen Maschinencode.
In der Zwischensprache sollten Funktionen gleichberechtigte Werte
sein. Da TooL und TL  Sprachen h"oherer Ordnung und von einer sehr hohen
Funktions\-aufruf\-dichte (oder Methoden\-aufruf\-dichte) gekennzeichnet
sind, mu\3 eine Zwischensprache  gerade die Mani\-pulation und Elimination von
Funktionen und Funktionsaufrufen erm"oglichen.


\item
Optimierungsalgorithmen f"ur Drei-Adre\3-Code setzen aufwendige Datenflu\3analysen
voraus und zielen in der Regel auf die Optimierung einzelner
Funktionen ab. Der von TooL und TL gef"orderte Programmierstil
f"uhrt zu vielen kurzen Funktionen, die 
von den Abstraktionsh"urden der modularen Programmierung
voneinander getrennt sind und somit
 wenig Angriffsfl"ache
f"ur datenflu\3gesteuerte Optimierungen bieten.
 Die Haupt\-aufgabe
eines Optimierers f"ur TooL mu\3  darin liegen, die  Abstraktionsh"urden der Methoden-
und Funktionsaufrufe zu "uberwinden.

\end{itemize}


Die erweiterte Variante des Lambdakalk"uls CPS ({\em Continuation Passing Style}), die sich als
Zwischensprache in vielen "Ubersetzern, unter anderem f"ur Scheme
\cite{Steele78,BartleyJensen86,ORBIT,HARE}, ML \cite{Appel89},
Pascal und BASIC \cite{Kelsey89a}, Smalltalk \cite{Gawecki91} und
TL \cite{GaMa94,Kira94}, bew"ahrt hat, erf"ullt obige Kriterien
und
bietet sich als Optimierungsrepr"asentation f"ur TooL an, wie sich im
folgenden
Abschnitt zeigen wird.

\section{TML} \label{TMLSection}

\begin{figure}[bth]
\include{tmlast}
\caption{Abstrakte Syntax der Zwischensprache TML (aus [Gawecki, Matthes 94])}
\label{TMLAST}
\end{figure} 

Die Zwischensprache TML (Tycoon Machine Language), die
den  Kern des Tycoon-Backends  stark
pr"agt, besitzt folgende Eigenschaften:

\begin{itemize}
\item 
Die abstrakte Syntax von TML f"allt einfach aus; in Abbildung \ref{TMLAST}
ist die gesamte Syntax aufgef"uhrt. 
Wie im Lambdakalk"ul wird zwischen Applikationen und Abs\-traktionen
unterschieden. Applikationen ({\em app}) sind Funktionsaufrufe, 
Anwendungen primitiver Operationen und reduzierbare Lambda-Terme.
Abstraktionen  ({\em abs}, Lambda-Terme in Normal\-form) sind
Funktionsobjekte, die sich wie  gew"ohnliche Werte manipulieren lassen.
Damit sind Funktionen in TML gleichberechtigte Werte.
\item
Funktionsaufrufe und Anwendungen primitiver Operationen unterliegen einer
Fort\-setzungssemantik. Jede Funktion und jede primitive Operation
erwartet bis zu zwei
zus"atzliche Parameter, eine normale Fortsetzung und eine Ausnahmefortsetzung.
Eine Fortsetzung ({\em continuation}) ist eine spezielle Funktion, 
die den Rest einer Berechnung beschreibt, 
wobei die normale Fortsetzung den Berechnungsverlauf ohne Auftritt eines
Fehlers oder einer Ausnahme beinhaltet und die Ausnahmefortsetzung die Reaktion auf
Ausnahmen oder Fehler
festlegt. Fortsetzungen werden implizit nach einem Funktionsaufruf oder
einer primitiven Operation aufgerufen und stellen im Gegensatz zu
Abstraktionen keine Objekte erster Klasse dar. Dieses kommt dadurch
zum Ausdruck, da\3 Fortsetzungen niemals  Fortsetzungen als Argumente
"ubernehmen k"onnen, nicht gespeichert und nicht als Ergebnis
zur"uckgegeben werden k"onnen.
\item
Der R"ucksprung einer Funktion ({\sf return}) an die Aufrufstelle
erfolgt "uber eine R"ucksprungfortsetzung.
\item
Neben Primitiven zur Manipulation und Erzeugung von Feldern und 
zur Berechnung von Werten 
existieren Operationen f"ur die Steuerung des Kontrollflusses, zur Definition 
von rekursiven Funktionen und f"ur den dynamischen Methodenaufruf.
Einige der  primitiven Operationen sind in Abbildung \ref{TMLPrimOps} zusammengefa\3t.

\item
Die Auswertung erfolgt strikt und die Auswertungsreihenfolge liegt fest,
da  Appli\-kationen  keine Argumente sein k"onnen. Somit treten keine
geschachtelten Aufrufe mehr auf, und alle Berechnungen sind linearisiert.
\end{itemize}



\begin{figure}[tbh]
\fbox{\vbox{
\begin{tabular}{ll}
(send $sel$ $r$ \pvec{arg} $c$) & Aufruf der Botschaft $sel$ mit Empf"anger $r$ \\
(sendSuper $sel$ $self$ \pvec{arg} $c$) & Aufruf der Botschaft $sel$ an eine Superklasse \\
(== $x$                      & Konditional, beruhend auf Objektidentit"at, mit  \\
 \hspace{5mm}\pvec{v}      & $\;\;\;$ Werten und             \\
 \hspace{5mm}\pvec{c} [$c_{n+1}$]) & $\;\;\;$ Verzweigungen (optionaler {\em else}-Zweig)  \\

(classTest $v$  & Konditional, beruhend auf \\
\hspace{5mm} \pvec{class} & $\;\;\;$ Klassenzugeh"origkeit von $v$ \\
\hspace{5mm} \pvec{c} [$c_{n+1}$]) & \\
 
(Y $\lambda({\,c\;\pvec{v}})\,{app}$)	   &  Y-Kombinator f"ur rekursive Definitionen\\
($p\:x\:y\:c_e\:c_c$)         & Ganzzahlige Arithmetik, $p \in \{+, -, *, /, \%\}$ \\
($p\:x\:y\:c_1\:c_2$)         & Vergleichsoperationen,
				    $p \in \{<, >, <=,>=\}$ \\
($p\:x\:y\:c$)          & Bit-Operationen,
			     $p \in \{<<, >>, \&, |, \hat{~}, \tilde{~}\}$ \\
(array \pvec{val} $c$)  & Anlegen eines ver"anderlichen Feldes \\
                        &  $\;\;\;$ mit $n$ Eintr"agen \\
(classnew $class$ $n$ $c$)       & Anlegen eines Exemplars der Klasse $class$ mit $n$ slots \\
(\arrayget{} $x\:i\:c$)               & Feldzugriff    \\
(\arrayset{} $x\:i\:v\:c$)            & Feldzuweisung \\
(ccall {\it fmt cfn $c_1\:c_2$})      & C-Funktionsaufruf \\
\end{tabular}
}}
\caption{Einige primitive TML Operationen (aus [Gawecki,Mattes 94])}
\label{TMLPrimOps}
\end{figure} 


In Textdarstellungen werden Abstraktionen durch das Schl"usselwort
{\sf proc}, Lambda-Applikationen durch {\sf lambda} und
Fortsetzungen durch {\sf cont} gekennzeichnet.
Am Beispiel des TML-Codes f"ur die Fakult"atfunktion lassen sich
 die Mechanismen des Fortsetzungsstils illustrieren:


\begin{xple}
\begin{tabular}{ll}
(Y \k{proc}(c\_1 fac)             &; {\rm Y-Kombinator zur Definition der rekursiven Funktion } fac\\
 (c\_1    &        \\            
    \k{cont}() & \\
      (fac 10 \k{cont}(t\_1)      &; {\rm Aufruf von {\sf fac}  mit 10} \\
      (cc t\_1))                  &; {\rm Ergebnis (Fakult"at von 10) an die Aufrufumgebung} \\
    \k{proc}(n ce c)              &; {\rm Beginn des Rumpfes von} fac\\
      (== n 1 &\\
          \k{cont}()&\\
            (c 1)&\\
          \k{cont}()&\\
            (- n 1 ce \k{cont}(t\_2)&\\
            (fac t\_2 ce \k{cont}(t\_3) &; {\rm rekursiver Aufruf von} fac\\
            (* n t\_3 ce \k{cont}(t\_4)&\\
            (c t\_4)))))&\\
\end{tabular}
\label{factorial}
\end{xple}



Das Y-Primitiv (benannt nach dem Y-Kombinator des Lambdakalk"uls)
dient der \mbox{Definition} von rekursiven Funktionen, die w"ahrend
der Codegenerierung einer gesonderten Behandlung unterliegen.
Ein Y-Primitiv (Y $\lambda({\,c\;\pvec{v}})\,$ ($c\;cont() \ldots \pvec{proc}$)
teilt dem Code\-generator mit, da\3 die Bezeichner \pvec{v} an die
m"oglicherweise wechselseitig
rekursiven Abstraktionen \pvec{proc} gebunden werden, und da\3 die Berechnung
mit  $cont()$ fortgesetzt wird.
Auf das Beispiel der Fakult"atfunktion
  "ubertragen, bedeutet dieses: der Bezeichner {\sf fac}
wird an die rekursive Funktion  {\sf proc(n ce c) ($\ldots$)} gebunden
und der weitere Verlauf der Berechung wird  durch {\sf cont() (fac 10 $\ldots$)}
beschrieben.

In diesem Beispiel besteht der weitere Verlauf der Berechnung aus
dem Aufruf der durch das Y-Primitiv definierten Funktion {\sf fac} mit 10.
Das Ergebnis des Aufrufs wird an {\sf t\_1} \mbox{gebunden} durch die
Fortsetzungsapplikation {\sf cont(t\_1)($\ldots$)} und an die 
 R"ucksprung-Fortsetzung
der Aufruf\-umgebung des Y-Primitivs ({\sf cc}) in dem Term
{\sf  (cc t\_1)}  "ubergeben.

Die zus"atzlichen Fortsetzungsargumente {\sf c} 
(R"ucksprung-Fortsetzung f"ur {\sf fac}) und {\sf ce}
(Ausnahme-Behandlung f"ur {\sf fac}) werden
in dem Funktionskopf {\sf proc(n ce c)}  
neben dem Argument {\sf n} der Fakult"atfunktion aufgef"uhrt.

Das folgende Konditional im  Rumpf der Fakult"atfunktion dr"uckt 
den Sachverhalt \glqq{\em wenn {\sf n} eins ist, ist das Ergebnis eins, sonst
{\sf n} multipliziert mit Fakult"at von {\sf n} minus eins}\backq aus:

\begin{xple}
\begin{tabular}{ll}
      (== n 1                           &; {\rm ist} n {\rm gleich 1 ?}\\   
          \k{cont}()                       &; {\rm  - Ja,} \\
            (c 1)                          &; {\rm    das Ergebnis ist 1}\\
          \k{cont}()                       &; {\rm  - Nein,} \\
            (- n 1 ce \k{cont}(t\_2)    &;     t\_2 $\leftarrow$ n - 1\\
            (fac t\_2 ce \k{cont}(t\_3) &;     t\_3 $\leftarrow$ fac(t\_2) \\    
            (* n t\_3 ce \k{cont}(t\_4) &;     t\_4  $\leftarrow$ n * t\_3\\
            (c t\_4)))))                   &; {\rm    das Ergebnis ist} t\_4 \\
\end{tabular}
\end{xple}

Die Aufrufe {\sf (c 1)} und {\sf (c t\_4)} der R"ucksprungfortsetzung
k"onnen als {\sf return}-Operationen verstanden werden; im Vorgriff auf
Kapitel \ref{CodeGen} sei an dieser Stelle erw"ahnt, da\3  der Codegenerator
dementsprechend {\tt return}-Bytecodes f"ur solche Applikationen erzeugt.


\section{Die Transformation von TooL nach TML}

\begin {figure}[tbh]
\centering
{\sf
\begin{tabular}{| lll |} \hline
{\rm Class} &  $::=$ & class {\rm {\em identifier}} \\
  &  &    public \\
  &  &    {\rm slots} \\
  &  &     {\rm methods}  \\
  &  &       private \\
  &  &    {\rm  slots} \\
  &  &    {\rm methods} \\

{\rm slots} &  $::=$ & {\rm slots} {\rm{\em identifier}} $|$ $\epsilon$ \\

{\rm methods} &  $::=$ & {\rm methods} {\rm{\em identifier}}({\rm parameters}) {\rm
bindings} $|$ $\epsilon$ \\

{\rm parameters} &$::=$ & {\rm parameters} {\rm{\em identifier}} $|$ $\epsilon$ \\

{\rm bindings}& $::=$ & {\rm bindings} {\rm{\em identifier}}={\rm value} $|$
{\rm bindings} \anonymous={\rm value} $|$ $\epsilon$ \\

{\rm value} & $::=$ & const $|$ {\rm{\em identifier}} $|$ self $|$ super $|$
fun({\rm parameters}) {\rm bindings} $|$ \\
     &  &  send({\rm{\em identifier}}, {\rm value}, {\rm bindings}) \\ \hline
\end{tabular}
}
\caption{Vereinfachte abstrakte Syntax von TooL}

\label{TooLAST}
\end {figure}


Da TooL eine rein objektorientierte Sprache ist, besitzt die abstrakte Syntax 
von TooL, abgesehen von den Produktionen des Typsystems, nur wenige
Konstrukte, denn f"ur Ausdr"ucke und f"ur den Kontrollflu\3 existiert
nur der Methodenaufruf ({\em message send}).
Die wesentlichen Sprach\-elemente sind in einer vereinfachten abstrakten
Syntax ohne Produktionen des Typ\-systems zusammengefa\3t,
die in Abbildung \ref{TooLAST} dargestellt ist.
Die Abbildung dieser Konstrukte soll im folgenden 
erl"autert werden. Hierzu werden der TooL-Code,
der abstrakte Syntaxbaum und der TML-Code der Methode {\sf while}
gegen"ubergestellt:


\begin{xple}
\begin{tabbing}
while(cond :Fun():Bool, statement :Fun():Void):Void \\
   \{ cond[$\:$] \\
     ? \{ statement[$\:$],\\
         while(cond, statement) \\
        \} \\
   \}\\
\end{tabbing}   
\end{xple}

Aus dem TooL-Quelltext erzeugt der TooL-Parser einen abstrakten Syntaxbaum,
in dem alle Bindungen und alle Methodenaufrufe explizit aufgef"uhrt
sind. Anonyme Bindungen ohne Bezeichner werden durch \sfrontq{\sf
\anonymous=$\ldots$}\sbackq  dargestellt.
Gem"a\3 der Syntax in Abbildung \ref{TooLAST} sieht dieser f"ur
{\sf while} wie folgt aus:

\begin{xple}
\begin{tabbing}
while(cond,statement) \\
  \anonymous = send(?,send([$\:$],cond,$\epsilon$),\\
               \anonymous = fun()\\
                        \anonymous = send([$\:$],statement,$\epsilon$)\\
                        \anonymous = send(while,self,\\
                                     \anonymous = cond\\
                                     \anonymous = statement))\\
\end{tabbing}   
\end{xple}
					     

Die wesentlichen Punkte der Transformation des abstrakten Syntaxbaums in
folgende TML-Repr"asentation werden anschlie\3end erl"autert:


\begin{xple}
\begin{tabular}{l}
\k{proc}(self cond statement e c)\\
  (send ``[$\:$]'' cond e \k{cont}(t\_1)\\
  (send ``?'' t\_1\\
     \k{proc}(e\_2 c\_3)\\
      (send ``[$\:$]'' statement e\_2 \k{cont}(t\_4)\\
      (send ``while'' self cond statement e\_2 \k{cont}(t\_5)\\
      (c\_3 t\_5)))\\
     \k{cont}(t\_6)\\
       (c t\_6)))\\
\end{tabular}   
\end{xple}


\begin{enumerate}
\item
Methodendefinitionen werden auf Abstraktionen (Funktionen) abgebildet, \mbox{wobei}
die Liste der formalen Parameter um eine R"ucksprungfortsetzung
{\sf c}, eine Ausnahme\-fortsetzung\footnote{
Ein getrennter Lauf, der ausf"uhrlich in \cite{Kira94}
beschrieben ist, wandelt vor der Codegenerierung Definitionen von
Ausnahmefortsetzungen in
Aufrufe an das TML-Primitiv
{\sf pushHandler} um. Beim Ende eines Blocks,
f"ur den eine Ausnahmefortsetzung gilt, wird eine {\sf
popHandler}-Anweisung eingef"ugt.
Nach diesem Lauf treten Ausnahmefortsetzungen nur
noch bei primitiven arithmetischen Operationen explizit auf.
Aus diesem Grund werden
Ausnahmefortsetzungen in den meisten Beispielen fortan weggelassen.}
 {\sf e}
und  einen Parameter
{\sf self} f"ur das Objekt selbst  erweitert wird.
Die Notwendigkeit des {\sf self}-Parameters ist durch 
m"ogliche Selbstreferenzen (Botschaften an {\sf self}) in dem Rumpf der
Methode  gegeben. 
Auf diese Weise werden zum Beispiel  Exemplarvariablen ({\em slots}) eines Objekts 
referenziert, denn ein Objekt besteht aus \mbox{einer} Referenz auf die Klasse und
dem Feld der Exemplarvariablen. 
In dem Beispiel der {\sf while}-Methode besteht der Rumpf aus einer  anonymen Bindung.

\item
Bindungen k"onnen auf drei Weisen nach TML transformiert werden: 
\begin{enumerate}
\item
Bindungen an berechnete Werte (in TooL sind berechnete Werte Ergebnisse von 
{\sf send}-Ausdr"ucken)  erfolgen in TML durch den Aufruf von
Fortsetzungen.
Durch die Konversion in den Fortsetzungsstil  werden geschachtelte
Berechnungen linearisiert und tempor"are Variablen eingef"uhrt, die
ebenfalls durch Fortsetzungen gebunden werden.
In dem Code f"ur {\sf while} geschieht dies f"ur das Ergebnis {\sf
t\_1} von
{\sf (send ``[$\:$]'' cond  $ \ldots $)}.
\item 
Bindungen an konstante Werte (Zahlen, Zeichenketten und Funktionen) werden durch 
anonyme Lambda-Applikationen durchgef"uhrt. In dem {\sf while}-Code
treten derartige Bindungen nicht auf.
Ein Beispiel ist:

\begin{xple}
\begin{tabbing}
                          (\k{lambda}(x)\\
x =  3, $ \ldots $  $ \longrightarrow $    ( $ \cdots $  )  \\
                          3) \\
\end{tabbing}
\end{xple}
\item
Von anonymen Bindungen in Argumentlisten eines {\sf send}-Aufrufs werden in dem TML-Code
nur Werte "ubernommen, zum Beispiel:
\begin{xple}
\begin{tabbing}
send(while,self, \\
      \anonymous = cond      $ \longrightarrow $ (send ``while'' self cond statement e\_2 $\ldots$)\\
      \anonymous = statement))\\
\end{tabbing}
\end{xple}
\end{enumerate}
\item
Funktionen in TooL (im abstrakten Syntax-Baum  sind diese durch
das Schl"usselwort {\sf fun()} gekennzeichnet)
werden auf Abstraktionen in TML abgebildet.
Die parameterlose Funktion, die im {\sf while}-Beispiel an den Aufruf der {\sf ?}-Methode
"ubergeben wird, liegt in dem TML-Code als Abstraktion 
{\sf {\bf proc}(e\_2 c\_3) ( $\ldots$)} vor. Diese Abstraktion birgt
durch den Mechanismus des Methodenaufrufs die  Rekursion  an {\sf while}.


\end{enumerate}

\section{Reduktion als grundlegendes Optimierungprinzip von CPS}

Die Reduktionsregeln des Lambdakalk"uls, die zur Auswertung von Lambda-Ausdr"ucken
dienen, bilden das Grundprinzip des TML-Optimierers, der in \cite{Kira94}
beschrieben ist. In diesen Regeln finden die  Mechanismen der Bindung an Bezeichner,
der Substitution von gebundenen Werten und der Applikation von Lambda-Termen 
eine Formalisierung. 

\subsection{Beta-Reduktion}

In der folgenden Variante des Lambdakalk"uls bestehen Lambda-Terme aus dem Symbol $ \lambda $, einem
Parameter und dem Rumpf (der
wiederum ein Lambda-Term ist), aus  Applikationen von Lambda-Termen, oder
einfach aus Bezeichnern:

\begin{eqnarray*} \lambda \mbox{-Term} &:=& \lambda(v) E_{1} \; | \; (E_{1} \; E_{2}) \; |
\; x \\
E &:=& \lambda \mbox{-Term}
\end{eqnarray*}


Der Parameter $ v $ gilt in dem Ausdruck 
$ \lambda(v)E_{1} $ als  gebunden. Treten Bezeichner im Rumpf auf, die
nicht als Parameter eingef"uhrt wurden, hei\3en diese  {\em frei}.
Eine Applikation eines Lambda-Terms auf ein Argument bedeutet im Lambdakalk"ul,
da\3 das Argument f"ur alle
Vorkommen des Parameters im Rumpf des Lambda-Terms substituiert
werden  und das "au\3ere $ \lambda $ wegf"allt (Beta-Reduktion):


\begin{eqnarray*} (\lambda(v)E_{1})E_{2} &
\stackrel{\beta}{\longrightarrow} &
              E_{1}[E_{2}/v] \end{eqnarray*}

Der Ausdruck $E_{1}[E_{2}/v]$ steht f"ur den Lambda-Term $E_{1}$, in
dem alle Vorkommen von $v$ durch $E_{2}$ ersetzt sind.
Bei dem Vorgang der Substitution mu\3 angesichts der Aufteilung in
gebundene und freie Variablen unterschiedlich verfahren werden. Freie Variablen
in dem zu substituierenden Wert k"onnen durch  Substitution in einen
Lambda-Term gebunden werden, wenn dieser gleichnamige formale Parameter 
besitzt (Namenskollision). Zum Beispiel w"urde die freie Variable
$y$ des Terms $\lambda(x)(y \; x)$ bei folgender Substitution eingefangen werden:
\begin{eqnarray*}
(\lambda(y)(f \; y))[\lambda(x)(y \; x)/f]
\end{eqnarray*}
Um dies zu vermeiden, m"ussen alle Vorkommen des kollidierenden
Bezeichners in dem Lambda-Term vor der Substitution umbenannt werden
(alpha-Konversion). Die F"alle der Substitution sind die folgenden (nach
\cite{Reade89}):


\begin{eqnarray*}
v[E/v] & = & E \\
x[E/v] & = & x \; ; x \neq v \\
(E_{1}E_{2})[E/v] & = & (E_{1}[E/v])(E_{2}[E/v]) \\
(\lambda(v)E_{1})[E/v] & = & (\lambda(v)E_{1}) \\
(\lambda(x)E_{1})[E/v] & = & \lambda(x)(E_{1}[E/v]) \; ; \; x \neq v  \;\wedge  \;
\neg freeIn(E,x) \\
                 & = & \lambda(y)((E_{1}[y/x])[E/v]) \; ; \; x \neq v  \;
 \wedge   \;
freeIn(E,x) \; \wedge \; \neg freeIn(E_{1}E,y)\\
\end{eqnarray*}



Mit Hilfe der folgenden Regel (Eta-Reduktion) kann eine Abstraktion vereinfacht werden, 
wenn der formale Parameter lediglich an eine Applikation weitergereicht wird:

\begin{eqnarray*} \lambda(v)(E\;v)  & \stackrel{\eta}{\longrightarrow} & E\;  ; \; \neg freeIn(E,v) \end{eqnarray*}

Die Reduktionsregeln des Lambdakalk"uls gelten auch f"ur CPS.
In Verbindung mit Meta-Evaluierungsfunktionen, die primitive Operationen
auf konstante Argumente anwenden, \mbox{lassen}
sich durch Beta-Eta-Reduktion eine Reihe von Standardoptimierungen
verwirklichen:
\begin{itemize}
\item
Das Falten konstanter Ausdr"ucke ({\em constant folding}) erfolgt durch die 
Meta-Evaluierung von TML-Termen,
z.B.:
\begin{xple}
\begin{tabbing}
(+  2  3 \k{cont}(t) $ \cdots $)   $\longrightarrow $   (\k{lambda}(t) $ \cdots $) 5
\end{tabbing}
\end{xple}

\item
Die Verbreitung von Konstanten und Kopien ({\em copy propagation}) erfordert
in TML keine Seiteneffektanalyse, weil alle Bezeichner an unver"anderliche Werte
gebunden sind. Ver"anderliche Variablen werden wie in der denotationalen
Semantik \cite{Stoy77} in zwei Komponenten aufgeteilt: eine unver"anderliche Bindung an
eine Speicherzelle und explizite Zugriffsoperationen auf die Speicherzelle.
Die eigentliche Verbreitung von Werten  erfolgt durch Beta-Reduktion;
beispielsweise:
\begin{xple}
\begin{tabbing}
(\k{lambda}(x)\\
    (+  x  1 \k{cont}(t) $ \cdots $)   $\longrightarrow $   (+ 3 1 \k{cont}(t) $ \cdots $)\\
3) \\
\end{tabbing}
\end{xple}
\item
Die Funktionsexpansion ({\em inlining}) stellt f"ur Sprachen mit sehr hohem
Funktionsaufkommen vielleicht die wichtigste Optimierung dar. Die Strukurierung
eines Programms in Klassen oder abstrakte Datentypen
wirkt sich in einer hohen Aufrufdichte aus, da m"oglichst viel Funktionalit"at
und h"aufig vorkommende Codemuster wie Iterationen, Selektionen, Listenoperationen
usw. geerbt oder "uber generische Bibliotheken importiert werden.
Codevereinfachungen und Optimierungen k"onnen nicht "uber Funktions\-aufrufe hinweg
erfolgen. Erst durch Funktionsexpansion entstehen gr"o\3ere Sequenzen von 
primitiven Operationen, an denen obige Vereinfachungen greifen k"onnen.
Zus"atzlich entf"allt der Zusatzaufwand des Funktionsaufrufs,
und in manchen F"allen er"ubrigt sich auch die
Erzeugung eines Funktionsobjekts.
Auch die Funktionsexpansion l"a\3t sich als Beta-Reduktion realisieren:
\begin{xple}
\begin{tabbing}
(\k{lambda}(f) \\
    (f 2 \k{cont}(t) $ \cdots $)   $ \longrightarrow $ (\k{lambda}(x c) (c x) 2 \k{cont}(t) $ \cdots $)\\
\k{proc}(x c)(c x))\\
\end{tabbing}
\end{xple}

\end{itemize}

Die in diesem Abschnitt geschilderten Optimierungsverfahren werden in dem
TooL-Optimierer eingesetzt. Der TML-Code, der direkt aus dem TooL-Syntaxbaum
gewonnen wird, eignet sich aber nicht ohne weitere Verfahren f"ur obige Transformationen,
da jede einzige Operation als Methodenaufruf codiert ist.
Weitere Mechanismen, die den in  Kapitel \ref{History} beschriebenen
"ahneln, m"ussen eingesetzt werden, um
die Abstraktionsh"urden der dynamischen Methodenaufrufe zu "uberwinden.
Diese Verfahren werden im n"achsten Kapitel beschrieben.
