\documentclass[a4paper,halfparskip]{scrartcl}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[ngerman]{babel}
\usepackage[babel,german=quotes]{csquotes}
\usepackage{graphicx}
\usepackage{url}
\usepackage{hyperref}
\usepackage{lmodern}
\usepackage{minted}
\usepackage{textcomp}

\author{Marek Kubica \\ Technische Universität München}
\title{Programming Languages from Hell: Scheme}
\date{4.6.2010}

\usemintedstyle{trac}
\hypersetup{
    %% force hyperref to run even in draft mode
    %%final,
    %% blank the borders
    pdfborder = 0 0 0,
    %% set some metadata
    pdftitle={Programming Languages from Hell: Scheme},
    pdfsubject={Seminar Programming Languages From Hell},
    pdfauthor={Marek Kubica},
    pdfkeywords={Scheme, hygienic macro, phase separation},
}

\begin{document}

\maketitle

\begin{abstract}

Kurzer und verständlicher Programmcode ist ein wichtiger Aspekt der
Programmierung, da solcher Code vom Programmierer einfacher zu überblicken und
verstehen ist. Seit jeher werden daher in der Programmierung zusätzliche
Abstraktionen eingeführt, um die zunehmende Komplexität der Systeme
überschaubar zu kapseln. Eine mächtige Abstrationsmethode ist die
Metaprogrammierung, die Programmierung von Programmen. Scheme ermöglicht
Metaprogrammierung über sogenannte Makros, die es erlauben eigene
Syntaxkonstrukte einzuführen. Somit können neue Abstraktionen nahtlos in die
Sprache integriert werden.

\end{abstract}

\section{Über die Sprache Scheme}
\label{sec:about}

Scheme ist ein Dialekt der Lisp"=Familie, die sich hauptsächlich dadurch
auszeichnet, dass sie auf Listenoperationen ausgelegt sind sowie dass ihre
Syntax ebenfalls aus ineinander verschachtelten Listen besteht. Diese Listen
werden S"=Expressions genannt und haben die Form \texttt{(name parameter ...)}.
Dadurch besteht in Lisp"=Dialekten eine enge Verzahnung zwischen \emph{Code}
und \emph{Daten}. Lisp"=Dialekte haben üblicherweise ein starkes, dynamisches
Typsystem bei dem die Typen nicht implizit ineinander konvertiert werden,
jedoch findet keine statische Typprüfung statt. Typannotationen sind in
Lisp"=Dialekten ebenfalls unüblich.

Scheme ist ein nicht rein"=funktionaler Dialekt von Lisp der sowohl Konzepte
der funktionalen Programmierung als auch Konzepte der imperativen
Programmierung beinhaltet. Über die im folgenden diskutierten Makros lassen
sich eine Vielzahl anderer Paradigmen in die Sprache integrieren. 

\section{Makros}
\label{sec:macro}

Makros werden verwendet, um eigene Syntaxerweiterungen zu ermöglichen.
Gerade im Zuge von Domain Specific Languages ist es wünschenswert, dem
Programmierer die Freiheit zu geben, neben domänenspezifischen Datenstrukturen
und Funktionen auch domänenspezifische Syntax bereitzustellen.

Ein Beispiel für diese Art von DSLs ist objektorientierte Programmierung. Wie C
bringt Scheme keine syntaktische Unterstützung für Objektorientierung mit,
ermöglicht aber die Implementierung verschiedenartiger Objektsysteme, die durch
die Verwendung von Makros auch syntaktische Integration in den Sprachkern
bieten.

Ein Beispiel für Makros in anderen Sprachen ist die Programmiersprache C.
C"=Makros werden von Präprozessor ausgewertet, der den Quellcode nach
bestimmten Sequenzen durchsucht und sie substituiert. Dadurch ist es
kompliziert fehlerfreie Makros zu schreiben, die Abstraktion bewegt sich auf
niedrigem Abstraktionslevel und fehlerhafte Makros können zu ungültigem Code
expandieren.

Makros in Scheme operieren hingegen auf der Listenstruktur des Programmes. Der
Programmcode wird als Daten aufgefasst und kann daher von Scheme"=Code
verarbeitet werden ohne dass eine zusätzliche Template"=Sprache, wie der
C"=Präprozessor, notwendig wird. Diese Verarbeitung geschieht über spezielle
Funktionen, die Scheme"=Code als Listen entgegennehmen, verarbeiten und
wiederum Scheme"=Code aus Listen ausgeben.

\begin{listing}[H]
  \begin{minted}[gobble=4,linenos]{scheme}
    (define-syntax postfixed
      (syntax-rules ()
          ((_ (operands ... operator)) (operator (postfixed operands) ...))
          ((_ atom) atom)))
  \end{minted}
  \caption{Das \texttt{postfixed}"=Makro}
  \label{lst:postfixed}
\end{listing}

Ein Beispiel der Makro"=Syntax in Scheme ist das Makro in
Listing~\ref{lst:postfixed}. Dieses Makro ermöglicht die Verwendung von
Postfix"=Notation in Scheme, indem es Postfix"=Notation in Prefix"=Notation
transformiert.

In Zeile 1 wird ausgesagt, dass ein Makro mit dem Namen \texttt{postfixed}
definiert werden soll. Die zweite Zeile weist dem Makro"=Namen einen
Syntax"=Transformer zu -- dieser wird von \texttt{syntax-rules} zurückgegeben.
Dies ist die eigentliche Funktion, die Scheme"=Code transformiert, sie wird in
diesem Fall von \texttt{syntax-rules} aus den Regeln generiert.
\texttt{syntax-rules} nimmt als ersten Parameter eine Liste von Keywords (im
Fall von \texttt{postscheme} werden keine Keywords genutzt). Die folgenden
Listen bestehen jeweils aus Paaren von \texttt{((muster) (expansion))}. Auf den
Mustern wird Pattern"=Matching ausgeführt, ähnlich zu Sprachen aus der
ML"=Familie. Das vorliegende Makro definiert in Zeile 3 ein Muster das aus dem
Makronamen besteht (dieser wird als \texttt{\_} abgekürzt) und darauffolgend
einer Liste von beliebig vielen Argumenten. Die \texttt{...} bedeuten, dass
alle Elemente dieser Liste in eine neue, an \texttt{operands} gebundene Liste
gesetzt werden. Das letzte Element der ursprünglichen Liste erhält eine
Sonderbehandlung, es wird an den Namen \texttt{operator} gebunden. Danach ist
der Muster"=Teil der ersten Regel zu Ende, es folgt die Expansion. Diese
konstruiert eine neue Liste mit \texttt{operator} an der ersten Stelle. Darauf
folgen rekursive Aufrufe des Makros auf die einzelnen Elemente der
\texttt{operands}"=Liste die durch die \texttt{...} ausgelöst werden.
\texttt{...} wechselt die Bedeutung, je nachdem ob es im Muster"=Teil oder im
Expansions"=Teil der Regel ist. Zeile 4 fährt mit der Trivialregel fort, die
ein Element zu sich selbst expandiert, wenn es nicht Teil einer Liste ist.

Listing~\ref{lst:postexpand} zeigt, wie die Schritte einer möglichen Expansion
aussehen könnten, die exakte Expansionsreihenfolge der Makros ist der
Implementation überlassen. In der letzten Zeile ist kein Makro"=Aufruf mehr
vorhanden -- dieser Code wird letztendlich ausgeführt.

\begin{listing}[H]
  \begin{minted}[gobble=4]{scheme}
    (+ (postfixed (1 (7 5 +) +)) (postfixed (4 6 +)))
    (+ (+ (postfixed 1) (postfixed (7 5 +))) (postfixed (4 6 +)))))
    (+ (+ 1 (postfixed (7 5 +))) (postfixed (4 6 +)))))
    (+ (+ 1 (+ (postfixed 7) (postfixed 5))) (postfixed (4 6 +)))))
    (+ (+ 1 (+ 7 (postfixed 5))) (postfixed (4 6 +)))))
    (+ (+ 1 (+ 7 5)) (postfixed (4 6 +)))))
    (+ (+ 1 (+ 7 5)) (+ (postfixed 4) (postfixed 6)))))
    (+ (+ 1 (+ 7 5)) (+ 4 (postfixed 6)))
    (+ (+ 1 (+ 7 5)) (+ 4 6))
  \end{minted}
  \caption{Eine mögliche Expansion des \texttt{postfixed}"=Makros}
  \label{lst:postexpand}
\end{listing}

\subsection{Hygienische Makros}

Angenommen man möchte ein \texttt{swap!}"=Makro implementieren, dass zwei Werte
vertauscht. Dieses Makro muss einen dritten, temporären Zwischenspeicher
einführen, wie Listing~\ref{lst:swap1} demonstriert.

\begin{listing}[H]
  \begin{minted}[gobble=4]{scheme}
    (swap! x y)
    ;; expandiert zu
    (let ((VALUE x))
      (set! x y)
      (set! y VALUE))
  \end{minted}
  \caption{Ansatz, ein \texttt{swap!}"=Makro zu implementieren}
  \label{lst:swap1}
\end{listing}

Ein solches Makro funktioniert jedoch nur solange nicht versucht wird
\texttt{(swap! VALUE y)} oder \texttt{(swap! x VALUE)} zu evaluieren -- in
diesem Fall würden sich die Werte überschreiben. Dieses Verhalten ist in der
Lisp"=Welt als \emph{capture} bekannt. Eine Möglichkeit ist es, eine spezielle
Funktion namens \texttt{gensym} zu verwenden, die sicherstellt, dass ein neuer
Identifier generiert wird, von dem die Implementation garantiert, dass er nicht
im Programm benutzt wird\footnote{R\textsuperscript{6}RS"=Scheme standardisiert
\texttt{gensym} nicht, jedoch bieten viele Implementationen diese
Funktionalität an}. Listing~\ref{lst:swap2} zeigt, wie \texttt{gensym}
verwendet werden könnte, um das Makro gegen den Fall abzusichern, dass sich
Variablen überdecken.

\begin{listing}[H]
  \begin{minted}[gobble=4]{scheme}
    (let ((value-name (gensym)))
      (let ((value-name x))
        (set! x y)
        (set! y value-name)))
  \end{minted}
  \caption{Verbesserter Ansatz eines \texttt{swap!}"=Makros}
  \label{lst:swap2}
\end{listing}

Jedoch ist auch dieses Makro noch nicht fehlerfrei; für den Fall dass jemand
\texttt{set!} im umgebenden Namensraum umdefiniert schlägt es fehl, wie
Listing~\ref{lst:swap3} demonstriert. Statt die Werte zu vertauschen, zeigt das
\texttt{swap!}"=Makro die Werte nur an.

\begin{listing}[H]
  \begin{minted}[gobble=4]{scheme}
    (let ((set! display))
      (swap! x y))
    ;; expandiert zu
    (let ((set! display))
      (let ((value-name (gensym)))
        (let ((value-name x))
          (set! x y)
          (set! y value-name))))
    ;; set! substituieren
    (let ((value-name (gensym)))
      (let ((value-name x))
        (display x y)
        (display y value-name))))
  \end{minted}
  \caption{Der verbesserte \texttt{swap!}"=Ansatz ist immer noch fehlerhaft}
  \label{lst:swap3}
\end{listing}

% http://groups.google.com/group/clojure/browse_thread/thread/160fd4fea945f39a 

Diese Art von Makrosystem ist als \enquote{unhygienisches} Makrosystem bekannt
und ist in einigen Lisp"=Dialekten wie Common Lisp oder Clojure in Verwendung. Scheme führt
hingegen \emph{hygienische Makros} ein, bei denen die genutzten Identifier sich
auf den Namensraum des Makros zur \emph{Definitionszeit} und nicht zur
\emph{Laufzeit} beziehen. Somit ist das in Listing~\ref{lst:swap4} dargestellte
Makro sicher gegen die Eingabe von \texttt{VALUE} sowie dem Neubinden von
\texttt{set!}.

\begin{listing}[H]
  \begin{minted}[gobble=4,linenos]{scheme}
    (define-syntax swap!
      (syntax-rules ()
	((_ x y) (let ((VALUE x))
		   (set! x y)
		   (set! y VALUE)))))
  \end{minted}
  \caption{Ein hygienisches \texttt{swap!}"=Makro}
  \label{lst:swap4}
\end{listing}

Um hygienische Makros zu implementieren, wurde in Scheme das Konzept der
Syntax"=Objekte eingeführt. Diese Objekte sind der Listenstruktur von
Lisp"=Programmen sehr ähnlich, enthalten darüber hinaus aber Metainformationen
über den Code, wie etwa die Position an der der Code in der Datei steht, sowie
der lexikalische Scope der Identifier. Der genaue Aufbau von Syntax"=Objekten
ist implementationsspezifisch. Jedoch ist es möglich Scheme"=Code mittels
\texttt{datum->syntax} in Syntax"=Objekte zu konvertieren. Die Gegenrichtung
von Syntax"=Objekt zu Scheme"=Code ist über \texttt{syntax->datum} ebenfalls
möglich, wobei die Metainformationen verworfen werden.

Makros sind somit eigentlich nur Syntax"=Transformer. Die Implementation
konvertiert den zu transformierenden Code implizit in ein Syntax"=Objekt mit
entsprechenden Metainformationen über den lexikalischen Scope. Dieses Objekt
wird dem Makro als Parameter übergeben und nach den Regeln, die im Makro
definiert worden sind, modifiziert. Heraus kommt wiederum ein Syntax"=Objekt,
das entweder wieder in Scheme"=Code überführt und ausgeführt wird, oder weitere
Makroexpansionen durchläuft.

\begin{listing}[H]
  \begin{minted}[gobble=4,linenos]{scheme}
    (define-syntax capture-swap!
      (lambda (stx)
	(syntax-case stx ()
	  ((capture-swap! x y)
	   #`(let-syntax ((set! (syntax-rules ()
				  ((_ name val)
				   (#,(datum->syntax #'capture-swap! 'set!)
				    name val)))))
	       (let ((value x))
		 (set! x y)
		 (set! y value)))))))
  \end{minted}
  \caption{Eine \enquote{unhygienische} Variante des
    \texttt{swap!}"=Makros aus Listing~\ref{lst:swap4}}
  \label{lst:captureswap}
\end{listing}

Man kann dieses Vorgehen gut am \texttt{capture-swap!}"=Makro in
Listing~\ref{lst:captureswap} nachvollziehen: Es wird mittels
\texttt{define-syntax} ein neues Makro definiert, das von einer anonymen
Funktion \texttt{lambda} mit einem Argument \texttt{stx} abgearbeitet wird.
Die Funktion gibt einen von \texttt{syntax-case} erzeugten Syntax"=Transformer
zurück, der die Syntax"=Objekte nach den Regeln des Makros verarbeitet und
zurückgibt.

Das \texttt{capture-swap!}"=Makro entspricht von der Funktionsweise dem in
Listing~\ref{lst:swap4} vorgestellten \texttt{swap!}"=Makro. Es ist jedoch
nicht hygienisch und übernimmt die Definition von \texttt{set!} aus dem lokalen
Scope, so dass ein lokal definiertes \texttt{set!} sich auch auf das Makro
auswirkt. Es fällt auf, dass statt \texttt{syntax-rules} in diesem Makro
\texttt{syntax-case} genutzt wird. Beide Ausdrücke generieren aus den ihnen
übergebenen Satz von Mustern und Regeln Syntax"=Transformer, die wiederum auf
der implementationsspezifischen Repräsentation der Syntax"=Objekte operieren.
Dadurch muss der Makro"=Autor sich nicht mit den Interna der jeweiligen
Implementation beschäftigen. Der Unterschied zwischen \texttt{syntax-rules} und
\texttt{syntax-case} besteht darin, dass \texttt{syntax-rules} keinen Zugriff
auf die Syntax"=Objekte bietet, wohingegen jede Regel in \texttt{syntax-case}
ein Syntax"=Objekt zurückgeben muss.

In Listing~\ref{lst:captureswap} wird mit \texttt{\#\textasciigrave} eine
Spezialsyntax genutzt, die statt Listenliteralen direkt Syntax"=Objekte
konstruiert. In dieser Syntax wird mit \texttt{\#,} eine Art Escapesequenz
eingesetzt, mit der man den Aufruf von \texttt{datum->syntax} einbinden kann.
Dieser Aufruf ermöglicht das Einbinden von \texttt{set!} aus der
\emph{run}"=Phase. Dieses \enquote{externe} \texttt{set!} wird im in Zeile 5
neu definierten, lokalen \texttt{set!}"=Makro verwendet um dem restlichen Makro
ab Zeile 9 ein nicht"=hygienisches \texttt{set!} bereitzustellen.

Der Aufruf des Makros bezeugt, dass das Makro tatsächlich unhygienisch ist. Der
erste Makro"=Aufruf in Listing~\ref{lst:captureswapcall} führt wie erwartet zum
Vertauschen der Werte von \texttt{a} und \texttt{b} da \texttt{set!} sich auf
das von Scheme bereitgestellte \texttt{set!} bezieht. Der zweite Aufruf von
\texttt{capture-swap!} findet in einer Umgebung statt, in der \texttt{set!}
durch \texttt{+} überschrieben ist. In diesem Fall werden die Werte nicht
vertauscht, stattdessen bleiben sie gleich und das Makro gibt die Summe von
\texttt{a} und \texttt{b}, also 65, zurück.

\begin{listing}[H]
  \begin{minted}[gobble=4]{scheme}
    (define a 42)
    (define b 23)
    (capture-swap! a b)
    (let ((set! +))
      (display (capture-swap! a b)))
  \end{minted}
  \caption{Aufruf des \texttt{capture-swap!}"=Makros}
  \label{lst:captureswapcall}
\end{listing}

Zusammenfassend kann man sagen, dass das hygienische Makrosystem von Scheme
durchdacht ist. Es sichert den Makro"=Autor gegen unabsichtliches
\emph{capturing}, ermöglicht ihm aber dennoch auf verlangen Werte aus dem
lokalen Scope zu lesen. Die Verwendung der Template"=Syntax in den Makros ist
zwar anfangs ungewohnt, erweist sich aber für viele Makros als kurz und
elegant.

\subsection{Phasenseparation}

Um Scheme"=Code auszuführen, müssen erst die Makros ausgewertet werden. Dabei
gibt es verschiedene Ansätze, \emph{wann} man Makros expandiert und \emph{wie}
man den Makros die benutzten Identifier bekannt macht. Der
R\textsuperscript{6}RS"=Standard spezifiziert mehrere Phasen mit jeweils
eigenen, getrennten Namensräumen, die der Scheme"=Code durchläuft, bietet
jedoch genug Implementationsfreiraum, so dass mehrere Ansätze entstanden sind,
wie die Identifier an Phasen gebunden werden. Der folgende Abschnitt führt
zunächst in die Phasenseparation ein und beleuchtet danach die konkurrierenden
Ansätze die sicherstellen, dass jede Phase Zugriff auf die benötigten
Identifier hat.

\subsubsection{Expand- und Runtime}

Es ist in Scheme generell so, dass Makros und Funktionen zu verschiedenen
Zeiten definiert und evaluiert werden. Daher kann es sein, dass ein Makro auf
eine Funktion zuzugreifen versucht, die aber dem System noch nicht bekannt ist,
da Makrodefinitionen vor Funktionsdefinitionen kommen können.  Die Phase in der
Makros expandiert werden, wird \emph{expand} genannt. Der Code wird hingegen in
einer Phase namens \emph{run} ausgeführt. Der einfachste Ausführungsmodus ist
es, erst in die \emph{expand}"=Phase zu gehen, alle Makros des Programmes zu
expandieren, danach in die \emph{run}"=Phase zu wechseln und in dieser den Code
auszuführen.

Komplexer wird es wenn das Scheme"=System eine REPL (Read"=Eval"=Print"=Loop)
bereitstellen soll. Scheme"=Implementationen haben oftmals einen interaktiven
Modus. Jeder vom Programmierer neu eingegebene Code muss auch die
\emph{expand}"=Phase durchlaufen, um eventuelle Makros zu expandieren, bevor er
ausgeführt werden kann.

\begin{enumerate}
  \item \emph{Batch"=Compiler}: Der Code wird komplett durchlaufen, wobei alle
    Makro- und Funktionsdefinitionen gelesen werden. Die Makros werden
    in einer \emph{expand}"=Phase expandiert. Die Funktionen werden zur
    Laufzeit nur noch aufgerufen.
  \item \emph{Inkrementeller Compiler}: Der Code wird wie bei dem
    Batch"=Compiler gelesen und die \emph{expand}"=Phase durchlaufen, bevor es
    zur \emph{run}"=Phase kommt. Jedoch ist es immer wieder möglich die
    \emph{expand}"=Phase zu durchlaufen, etwa wenn neue Funktionen in der REPL
    definiert werden -- diese müssen erst eine \emph{expand}"=Phase
    durchlaufen, um eventuell vorkommende Makros zu definieren oder sie im
    eingegebenen Code zu evaluieren.
  \item \emph{Interpreter}: Es gibt keine Unterscheidung zwischen den Phasen,
    Makros werden zur Laufzeit expandiert, wenn die Programmausführung an den
    Aufruf eines Makros ankommt.
\end{enumerate}

Ein wichtiger Unterschied zwischen den einzelnen Phasen ist, welche Identifier
in der jeweiligen Phase definiert sind. Man kann aus der \emph{expand}"=Phase
nicht auf Identifier zugreifen, die erst in der \emph{run}"=Phase
gültig werden. Trotzdem muss in bestimmen Fällen, wie in
Listing~\ref{lst:assert} gezeigt, eine Funktion in der
\emph{expand}"=Phase verfügbar sein, diese lässt sich mittels speziellen
Syntaxkonstrukten einbinden.

Ein Problem ist an dieser Stelle, dass der R\textsuperscript{6}RS"=Standard es
offen lässt, ob der Autor angeben muss, in welcher Phase er den Identifier
nutzen will oder ob er diese Deklaration weglassen kann. Der erstere Ansatz ist
als \emph{explicit phasing} bekannt, der letztere wird \emph{implicit phasing}
bezeichnet. Bei \emph{explicit phasing} wird der Identifier in die vom Autor
angegebene Phase importiert, wodurch er nun für allen Code, der in dieser Phase
abläuft, sichtbar wird. Falls keine Phase beim Import angegeben ist, wird die
\emph{run}"=Phase angenommen. Der Ansatz über \emph{implicit phasing} fordert
von der Scheme"=Implementation, dass sie die notwendigen Phasendefinitionen aus
der Nutzung der zu importierenden Identifier ableitet -- wenn ein Identifier
nur in der \emph{expand}"=Phase verwendet wird, dann wird dies von der
Implementation erkannt.

Daraus folgt, dass Programme die explizites Phasing verwenden, in
Implementationen mit \emph{implicit phasing} funktionieren, nicht aber
umgekehrt. Ein Beispiel dafür ist die \texttt{distinct?}"=Funktion aus der
\texttt{distinct}"=Bibliothek in Listing~\ref{lst:distinct}. Diese Funktion
überprüft, ob die Elemente einer Liste paarweise unterschiedlich sind.

\begin{listing}[H]
  \begin{minted}[gobble=4,linenos]{scheme}
    (library (distinct)
             (export distinct?)
             (import (rnrs))

    (define (distinct? eq? items)
      (if (null? items) #t
          (let* ((first (car items))
                 (rest (cdr items)))
            (cond
              ((or (exists (lambda (element) (eq? first element)) rest)
                   (not (distinct? eq? rest))) #f)
              (else #t))))))
  \end{minted}
  \caption{Die \texttt{distinct}"=Bibliothek}
  \label{lst:distinct}
\end{listing}

Mit \texttt{distinct?} lässt sich ein neues Makro definieren,
\texttt{assert-distinct}, welches zusichert, dass alle übergebenen Identifier
paarweise verschieden sind. Ein Aufruf von \texttt{(assert-distinct a b)} ist
gültig, wohingegen \texttt{(assert-distinct a a)} nicht gültig ist, da beide
Identifier gleich sind. Für die Makrodefinition in Listing~\ref{lst:assert}
wird die \texttt{distinct}"=Bibliothek eingebunden. Mit dieser wird in der
Makrodefinition geprüft, ob die Identifier unterschiedlich sind, andernfalls
wird ein Syntaxfehler signalisiert. Dieses Makro bietet den Vorteil, dass der
Nutzer des Makros schon zur Compilezeit mitgeteilt bekommt, dass es ein
Syntaxfehler ist, denselben Identifier mehrmals zu verwenden.

\begin{listing}[H]
  \begin{minted}[gobble=4,linenos]{scheme}
    (import (rnrs)
            (distinct))

    (define-syntax assert-distinct
      (lambda (stx)
        (syntax-case stx ()
          ((_ args ...) (distinct? bound-identifier=? #'(args ...))
	                #'(args ...))
          ((_ args ...) (syntax-violation 'assert-distinct "Duplicate name"
                                          #'(args ...))))))

    (let ((a display) (b 42))
      (assert-distinct a b)
      (assert-distinct a a))
  \end{minted}
  \caption{Das \texttt{assert-distinct}"=Makro}
  \label{lst:assert}
\end{listing}

Dieses Makro funktioniert in Implementationen mit \emph{implicit phasing}
(Tabelle~\ref{tbl:phasing} listet entsprechende Implementationen auf). Eine
R\textsuperscript{6}RS"=Implementation mit \emph{explicit phasing} signalisiert
den Fehler, dass \texttt{distinct?} nicht bekannt ist. Dies liegt daran, dass
der Import von \texttt{distinct} nur in der \emph{run}"=Phase gültig ist, da
diese Phase implizit angenommen wird. Damit \texttt{distinct?} gefunden werden
kann, muss man der Implementation mitteilen, dass der Import von
\texttt{distinct} für die \emph{expand}"=Phase gilt.
Listing~\ref{lst:explicitimport} zeigt eine Variante, die in allen
R\textsuperscript{6}RS"=Implementationen lauffähig ist.

\begin{listing}[H]
  \begin{minted}[gobble=4]{scheme}
    (import (rnrs)
            (for (distinct) expand)) ; neuer Code, gibt die Phase explizit an
            ;;(distinct)) ; alter Code, funktioniert nur mit implicit phasing 
  \end{minted}
  \caption{Eine portablere Variante der Import"=Instruktion aus
    Listing~\ref{lst:assert}}
  \label{lst:explicitimport}
\end{listing}

\begin{table*}
  \centering
  \begin{tabular}{l|l}
    \emph{implicit phasing} & \emph{explicit phasing} \\
    \hline
    Ikarus & PLT \\
    Ypsilon & Larceny \\
    Mosh & \\
    Chez & \\
  \end{tabular}
  \caption{Übersicht der R\textsuperscript{6}RS"=Implementationen nach
    unterstützter Phasing"=Variante}
  \label{tbl:phasing}
\end{table*}

\subsubsection{Metalevel}

Es gibt Fälle, in denen man möchte, dass ein Makro wiederum zu einem Makro
expandiert.  Ein Beispiel hierfür ist das \texttt{static-map}"=Makro aus
Listing~\ref{lst:staticmap}. Das Makro expandiert zu einem weiteren, nun
anonymen Makro, welches die dem \texttt{static-map}"=Makro übergebenen
Schlüssel"=Werte"=Paare zurückgibt. Damit kann ein Dictionary (Hashmap,
assoziatives Array) zur Compilezeit definiert werden.

\begin{listing}[H]
  \begin{minted}[gobble=4,linenos]{scheme}
    (library (static-map)
             (export static-map)
             (import (rnrs)
                     (for (rnrs) (meta -1)))

    (define-syntax static-map
      (syntax-rules ()
        ((_ (name value) ...)
         (syntax-rules (<names> name ...)
           ((_ <names>) '(name ...))
           ((_ name) value) ...)))))
  \end{minted}
  \caption{Makro, dass zu einem Makro expandiert}
  \label{lst:staticmap}
\end{listing}

Wenn man versucht dieses Makro naiv zu implementieren, melden Implementationen
mit \emph{explicit phasing} einen Fehler, der besagt, dass \texttt{quote} nicht
bekannt sei. In Scheme wird \texttt{quote} verwendet, um einen Wert zu escapen
-- in diesem Fall \texttt{'(name ...)}. Um dem Programm \texttt{quote} bekannt
zu machen muss es in die entsprechende Phase importiert werden. Ein Versuch es
in die \emph{expand}"=Phase zu importieren scheitert, da sich das innere,
anonyme Makro nicht in der \emph{expand}"=Phase befindet, sondern in einer
Phase, die Meta"=Level -1 bezeichnet wird. Tatsächlich ist es so, dass
\emph{expand} und \emph{run} nur Aliase für die Meta"=Level 1 und 0 sind, daher
muss bei verschachtelten Makros darauf geachtet werden, die Identifier in die
richtigen Meta"=Level zu importieren.

Meta"=Level sind die Bezeichner für die zusätzlichen Phasen, die durchlaufen
werden müssen, um Scheme"=Programme mit verschachtelten Makros auszuführen. Wie
die bereits bekannten \emph{run} und \emph{expand}"=Phasen verfügen sie über
einen eigenen Namensraum sowie einen definierten Zeitpunkt, wann sie durchlaufen
werden.

Die Verwendung des in Listing~\ref{lst:staticmap} definierten Makros ist trotz
der Meta"=Level nicht kompliziert, solange bedacht wird dass
\texttt{static-map} ein anonymes Makro zurückgibt. Im
Listing~\ref{lst:usestaticmap} wird ein Makro definiert, dass den Namen einer
Farbe auf den Anfangsbuchstaben abbildet.

\begin{listing}[H]
  \begin{minted}[gobble=4,linenos]{scheme}
    (import (rnrs)
            (for (static-map) expand))

    (define-syntax color
      (static-map (red #\R) (green #\G) (yellow #\Y)))

    (display "Available colors: ")
    (display (color <names>))
    (display (list (color red) (color green) (color yellow)))
    (newline)
  \end{minted}
  \caption{Das anonyme Makro aus \texttt{static-map} wird \texttt{color} genannt}
  \label{lst:usestaticmap}
\end{listing}

Wenn ein Makro zu neuen Makros expandiert wird der Meta"=Level dekrementiert.
Analog dazu gibt es auch Fälle, bei denen der Meta"=Level inkrementiert wird:
wenn in der Definition des Makros wiederum ein Makro definiert wird.
Listing~\ref{lst:meta2} definiert ein Makro \texttt{m}, in dessen
\emph{Definition} (nicht in dessen \emph{Expansion}, wie in
Listing~\ref{lst:staticmap}) ein weiteres Makro \texttt{m2} definiert wird. Die
Phase von \texttt{m} ist \emph{expand}, die Phase von \emph{m2} ist hingegen
die Phase von \texttt{m} + 1, also \texttt{(meta 2)}. In \texttt{m2} wird auf
\texttt{begin}, \texttt{lambda} und \texttt{display} zugegriffen, also müssen
diese Identifier auch in \texttt{(meta 2)} existieren -- daher wird in der
Import"=Deklaration explizit angegeben, dass diese drei Identifier in
Meta"=Level 2 importiert werden sollen.

\begin{listing}[H]
  \begin{minted}[gobble=4,linenos]{scheme}
    (import (rnrs)
            (for (only (rnrs) begin lambda display) (meta 2)))

    (define-syntax m
      (let ()
        (define-syntax m2
          (begin
            (display "at metalevel 2\n")
            (lambda (x) "expanded-m\n")))
        (define _ (display "at metalevel 1\n"))
        (lambda (x) (m2))))

    (display (m))
  \end{minted}
  \caption{Makros mit Meta"=Level $\geq$ 1}
  \label{lst:meta2}
\end{listing}

Im Gegensatz dazu benötigen Implementationen mit \emph{implicit phasing}
(siehe Tabelle~\ref{tbl:phasing}) keinerlei zusätzliche \texttt{(meta
n)}"=Definitionen, sondern inferieren den benötigten Meta"=Level.

\section{Zusammenfassung}
\label{sec:conclusion}

Das Makrosystem, welches in R\textsuperscript{6}RS"=Scheme standardisiert wurde,
bietet mit \texttt{syntax-rules} sowohl eine Möglichkeit einfache, sowie mit
\texttt{syntax-case} komplexere Makros zu bauen. Beide Systeme nehmen dem
Makro"=Autor im Vergleich zu anderen Sprachen viel Arbeit ab, insbesondere bei
Verwendung einer Implementation mit \emph{implicit phasing}. Es bleibt zu
hoffen, dass sich dieses System in Zukunft durchsetzt und zukünftige
Sprachstandards dieses Verfahren favorisieren werden.

Ob so mächtige Makros in einer Programmiersprache sinnvoll sind, kann nicht
abschließend geklärt werden. Makros in Scheme bieten die Möglichkeit, elegant
Abstraktionen etwa für die parallele Programmierung wie Aktoren oder STM in die
Sprache zu integrieren ohne an der Scheme"=Implementation selbst editieren zu
müssen. Jedoch kann übermäßiger Einsatz von Makros zu schwer zu verständlichem
Code und einer Zersplitterung der Sprache in verschiedene Dialekte führen. Dies
beweist die Existenz von mindestens 14 inkompatiblen, nicht"=standardisierten
Objektsystemen\footnote{TinyCLOS, Swindle, Gauche, GOOPS, STklos, MIT"=Scheme-SOS,
Meroon, YASOS, Protobj, Prometheus, TinyTalk, OakLisp, ClosureTalk,
LispMeObjects}, deren Syntax und Semantik der Programmierer jeweils
immer neu lernen muss.

\nocite{*}

\bibliographystyle{plain}
\bibliography{hellprog}
\end{document}