%% Presentation about Scheme Macros

%% Some useful variations of the document class
%%\documentclass[draft]{beamer}
%%\documentclass[handout]{beamer}
% silence hyperref warnings
\documentclass[hyperref={pdfpagelabels=false}]{beamer}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[ngerman]{babel}
\usepackage[babel,german=quotes]{csquotes}
\usepackage{minted}
%% get the smiley
\usepackage{wasysym}
\usepackage{ccbeamer}
\mode<presentation>{\usetheme{Copenhagen}}
\title{Makros in Scheme}
\author{Marek~Kubica}
\institute{TU~München}
\date{7.~Juni~2010}

%% get rid of navigation symbols
%\setbeamertemplate{navigation symbols}{}
\beamertemplatenavigationsymbolsempty

\usemintedstyle{trac}

\begin{document}

\frame{
  \titlepage
  \vfill
  \begin{center}
    \CcGroupBy{0.83}\\[2.5ex]
    {\tiny\CcNote{\CcLongnameBy}}
    \vspace*{-2.5ex}
  \end{center}
}

\AtBeginSection[]{
  \begin{frame}
    \frametitle{\insertsection}
    \tableofcontents[currentsection]
  \end{frame}
}

% define the logo after the title page
%\logo{\includegraphics[width=1.5cm]{tun}}

\begin{frame}{Über Scheme}
  \begin{block}{Unterschiede zu Common Lisp}
    \begin{itemize}
      \item Wesentlich kleinerer Standard (161 vs. 1029 Seiten)
      \item Scheme \enquote{akademisches} Lisp, CL \enquote{Industrie}"=Lisp
      \item Scheme eher funktional, CL hat u.a. Objektsystem
      \item nur ein Namespace für Funktionen, Variablen, etc.
    \end{itemize}
  \end{block}
  \begin{block}{Hygienisches Makrosystem}
    \begin{itemize}
      \item lange Zeit nicht standardisiert
      \item nutzt Pattern"=Matching
      \item zwei verschiedene Varianten: \texttt{syntax-rules}
        \& \texttt{syntax-case}
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}{Wozu Makros?}
  \begin{block}{Vorteile}
    \begin{itemize}
      \item Anpassung der Sprache an Anforderungen
      \item Assimilation von neuen Konzepten
        \begin{itemize}
          \item OOP
          \item Transactional Memory (STM)
          \item Actors
	\end{itemize}
    \end{itemize}
  \end{block}
  \begin{block}{Nachteile}
    \begin{itemize}
      \item Bildung von Dialekten
      \item Schwer zu Debuggen
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}[fragile]{Ein Beispielmakro}
  Nachbau von \texttt{for} aus Python
  \begin{block}{Aufruf mit einem Namen}
    \begin{minted}[gobble=6]{python}
      for x in [1, 2, 3]:
          print x
    \end{minted}
    \begin{minted}[gobble=6]{scheme}
      (py-for x in '(1 2 3)
              (display x))
    \end{minted}
  \end{block}
  \begin{block}{Aufruf mit einer Liste von Namen}
    \begin{minted}[gobble=6]{python}
      for x, y in [('a', 'b'), ('A', 'B'), (1, 2)]:
          print x, y
    \end{minted}
    \begin{minted}[gobble=6]{scheme}
      (py-for (x y) in '((a b) (A B) (1 2))
              (display x) (display y))
    \end{minted}
  \end{block}
\end{frame}

\begin{frame}[fragile]{Implementation von py-for}
  \begin{minted}[gobble=4,linenos]{scheme}
    (define-syntax py-for
      (syntax-rules (in)
        ((_ (?bindings ...) in ?collection body ...)
         (let ((code (lambda (?bindings ...) body ...)))
           (let loop ((collect ?collection))
             (unless (null? collect)
               (apply code (car collect))
               (loop (cdr collect))))))
        ((_ ?binding in ?collection body ...)
         (py-for (?binding) in (map list ?collection)
                 body ...))))
  \end{minted}
\end{frame}

\begin{frame}[fragile]{Unhygienische Makros}
  \begin{block}{Das Problem}
    \begin{minted}[gobble=6]{scheme}
      (swap! x y) ;; expandiert zu
      (let ((VALUE x))
        (set! x y)
        (set! y VALUE))
    \end{minted}
    % Scheitert beim Aufruf von \texttt{(swap! x VALUE)}
  \end{block}
  \begin{block}{Umbenennen}
    \begin{minted}[gobble=6]{scheme}
      (let ((value-name (gensym)))
        (let ((value-name x))
          (set! x y)
          (set! y value-name)))
    \end{minted}
    % Schlägt fehl, wenn \texttt{set!} umdefiniert wird
  \end{block}
\end{frame}

\begin{frame}{Lösung: Hygienische Makros}
  \begin{block}{Lexikalisches Scoping für Makros}
    \begin{itemize}
      \item Makros können nur auf die Identifier zugreifen,
        die zur \emph{Definitionszeit} verfügbar sind
      \item Die Implementation kümmert sich um die Details
      \item analog wie bei Funktionen
    \end{itemize}
  \end{block}
  \begin{block}{Vorteile}
    \begin{itemize}
      \item Robust
      \item Einfach(er) zu schreiben
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}{Metalevel}
  \begin{block}{Das Problem}
    \begin{itemize}
      \item Makros werden vor der Laufzeit ausgeführt
      \item Makros haben einen eigenen \enquote{Namensraum}
      \item Makros können zu Makros expandieren
      \item Was ist im Namensraum von geschachtelten Makros?\\
        $\Rightarrow$ Notwendigkeit Identifier richtig zu importieren
    \end{itemize}
  \end{block}
  \begin{block}{Lösungen in R\textsuperscript{6}RS"=Scheme}
    \begin{enumerate}
      \item Explizites Phasing: Der Programmierer gibt an, welche
        Identifier in welcher Phase verwendet werden
      \item Implizites Phasing: Die Implementation inferiert
        diese Information
    \end{enumerate}
  \end{block}
\end{frame}

\begin{frame}[fragile]{Beispiel für Metalevel}
  \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}
\end{frame}

\begin{frame}{Damenproblem}
  \begin{block}{Schelog}
    \begin{itemize}
      \item Prolog eingebettet in Scheme
      \item ermöglicht Kombination funktionaler mit logischer Programmierung
      \item hat mich Prolog gelehrt \smiley
    \end{itemize}
  \end{block}
  \begin{block}{Algorithmus}
    \begin{itemize}
      \item Datenstruktur: Liste. Position stellt Zeile dar, Zahl stellt Spalte dar
      \item Bildung von Permutationen der Liste
      \item Prüfen ob die Permutationen gültige Lösungen darstellen
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}[fragile]{Prolog vs. Schelog}
  \begin{block}{Prolog}
    \begin{minted}[gobble=6]{prolog}
      do_insert(X,Y,[X|Y]).
      do_insert(X,[Y1|Y2],[Y1|Z]) :- do_insert(X,Y2,Z).
    \end{minted}
  \end{block}
  \begin{block}{Schelog}
    \begin{minted}[gobble=6]{scheme}
      (define do-insert
        (%rel (x y y1 y2 z)
              ((x y (cons x y)))
              ((x (cons y1 y2) (cons y1 z))
               (do-insert x y2 z))))
    \end{minted}
  \end{block}
\end{frame}

\begin{frame}{Ressourcen}
  \begin{block}{Standards}
    \begin{itemize}
      \item R\textsuperscript{6}RS: aktueller Standard, komplizierter, geringe
        Verbreitung
      \item R\textsuperscript{5}RS: vorheriger Standard, einige wichtige
        Elemente nicht spezifiziert
    \end{itemize}
  \end{block}
  \begin{block}{Nützliche Ressourcen}
    \begin{itemize}
      \item The Scheme Programming Language, 4\textsuperscript{th} Edition
      \item The Adventures of a Pythonista in Schemeland
      \item Meine Ausarbeitung \smiley
    \end{itemize}
  \end{block}
  Danke fürs Zuhören.
\end{frame}

\end{document}
