%% Some useful variations of the document class
%%\documentclass[draft]{beamer}
%%\documentclass[handout]{beamer}
% silence hyperref warnings
\documentclass[hyperref={pdfpagelabels=false}]{beamer}
%\documentclass{beamer}
\usepackage[T1]{fontenc}
\usepackage{minted}
\usepackage[utf8]{inputenc}
\usepackage[ngerman]{babel}
\usepackage[autostyle]{csquotes}
\usepackage{wasysym}
\usepackage{lmodern}
\usepackage{units}
\mode<presentation>{\usetheme{Copenhagen}}
\title{A Caml Light Compiler for the JVM}
\author[Hupel, Kubica, Schulze Frielinghaus, Müller, Traytel]{Lars Hupel, Marek Kubica, Stefan Schulze Frielinghaus, \\Edgar Müller, Dmitriy Traytel}
\institute{TU~München}
\date{20.~August~2010}

\beamertemplatenavigationsymbolsempty

\definecolor{slowest}{RGB}{255, 0, 0}
\definecolor{fastest}{RGB}{0, 255, 0}
\usemintedstyle{trac}

\begin{document}

\frame{\titlepage}

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

\begin{frame}{Übersicht}
	\begin{enumerate}
		\item Eingabe: CamlLight (mit leichter Modifikation)
		\item Scanning mit JFlex
		\item Parsing mit CUP2
		\item Magic
		\item Code-Generierung nach MaMA (ebenfalls modifiziert)
		\item Übersetzung nach JVM
	\end{enumerate}
\end{frame}

\begin{frame}{Ablauf}
	\begin{itemize}
		\item für den Compiler steht ein komplettes Ant-Skript zur Verfügung:\\
			\texttt{ant jar}
		\item Aufruf über Shell-Skript:\\
			\texttt{bin/compiler prog.cl -o foo}
	\end{itemize}
\end{frame}

\begin{frame}{Lexer}
  \begin{block}{Technisches}
    \begin{itemize}
      \item JFlex
      \item Kommentare: \texttt{(* foo (* bar *) baz *)}
      \item Identifier: \texttt{foo\_bar\_42}
      \item Integer-Literale: \texttt{-0x42}; \texttt{0b101010}; \texttt{0o52}
      \item Floating-point-Literale: nicht existent
      \item Character-Literale: \texttt{'a'}; \texttt{'\textbackslash 042'}
      \item String-Literale: \texttt{"foo"}; \texttt{"bar \textbackslash 023"}
      \item Keywords: einige...
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}{Parser}
  \begin{block}{Technisches}
    \begin{itemize}
      \item CUP2 + Scala-Layer
      \item Caml Light"=Syntax
      \item pro Reduce-Schritt werden die Zeilen- und Spaltennummern hinterlegt
      \item Post-processing: Normalisierung
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}{Typinferenz}
  \begin{block}{Constraint based typing nach Hindley-Milner}
    \begin{itemize}
      \item ca. 700 LOC, $\approx$ 50 Tests
      \item Lambda-Kalkül + \texttt{let}-Ausdrücke: easy \smiley
      \item Unterstützung von \texttt{match}, \texttt{let rec}, Records, Record-Zugriff, Tupel, Tupel-Zugriff, binäre/unäre Operatoren, if-then-else
      \item Pattern Matching für 
        \begin{itemize}
	  \item Literale
	  \item Underscore
	  \item Listen (Cons, Nil)
	  \item Tupel
	  \item Records
        \end{itemize}
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}[fragile]{Typinferenz}
  \begin{block}{Beispiel: Record Pattern}
      \begin{minted}[gobble=12]{ocaml}
            let { foo = (_,(x,y)); bar = z::zs } =
                { foo = ('a',(1,2::[])); bar = [true;false;true] }
             in (x + (hd y) == 3) == z
      \end{minted}
  \end{block}
  \begin{block}{Beispiel: sum}
      \begin{minted}[gobble=12,mathescape=true]{ocaml}
            let rec foldr = fun
               f acc []    -> acc
            $|$  f acc x::xs -> f x (foldr f acc xs);;
            let rec add = fun x y -> x + y;;
            let xs = [1;2;3] in foldr add 0 xs
      \end{minted}
  \end{block}
\end{frame}

\begin{frame}[fragile]{Typinferenz}
  \begin{block}{Weiteres Beispiel}
      \begin{minted}[gobble=12]{ocaml}
            let x = 3 in let y = 4 in (x,y) + 5
      \end{minted}
  \end{block}
  \begin{alertblock}{Fehlermeldungen}
  \begin{verbatim}
Type checking failed
ERROR: Couldn't unify types: 
   TypeTuple(List(TypeInt(), TypeInt()))
   TypeInt() in expression: 
(((x),(y)))+(5)
  \end{verbatim}
  \end{alertblock}
\end{frame}

\begin{frame}{Codegenerierung: MaMa}
  \begin{block}{Übersetzung AST $\Longrightarrow$ MaMa}
    \begin{itemize}
      \item Vorgehen wie in
        \begin{center}
          \emph{[Wilhelm, Seidl -- Übersetzerbau: Virtuelle Maschinen]}
        \end{center}
    \end{itemize}
  \end{block}
  \begin{block}{Erweiterungen}
    \begin{itemize}
      \item Records        
        \begin{itemize}
          \item Implementierung als namenlose Tupel
          \item Feldnamensauflösung mit Hilfe der Typinferenz
        \end{itemize}
	 \item Pattern matching mit beliebigen Patterns        
        \begin{itemize}
          \item \pause kompliziert$\ldots$
        \end{itemize}
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}{Codegenerierung: MaMa -- Pattern Matching}
  \begin{block}{Pattern Matching im AST}
  	\texttt{match} $e_0$ \texttt{with} $p_1$ \texttt{->} $e_1$ \texttt{|} $\ldots$ \texttt{|} $p_n$ \texttt{->} $e_n$
  \end{block}
  \begin{block}{Idee}
    \begin{itemize}
  	\item Generiere rekursiv sogenannten \emph{matching code} für jedes einzelne Pattern $p_i$.
  	\item Invariante: nach Ausführung des \emph{matching code} liegt auf dem Stack eine 1, falls $e_0$ $p_i$ matcht, sonst 0.
  	\item Zusammengesetzte Patterns (wie z.B. Tupel) generieren den \emph{matching code} rekursiv und führen \texttt{AND}-Instruktionen aus.  
  	\item Dabei wird der Code für $e_0$ nur einmal generiert.
  	\end{itemize}
  \end{block}
\end{frame}

\begin{frame}[fragile]{Codegenerierung: MaMa -- Fehlermeldungen}
\begin{block}{\texttt{let hd = fun x::xs -> x in hd []}}
\begin{itemize}
\item Für jedes Pattern Matching lege auf den Stack:
\begin{enumerate}
\item Den Match-Ausdruck
\item Zeilen- und Spaltenangaben
\end{enumerate}
\item Virtuelle MaMa-Maschine produziert Ausgaben von der Form:
\begin{small}
\begin{verbatim}
Exception in thread "main" java.lang.RuntimeException: 
Pattern match failure in the expression
	"match (427 @ 0) with [(4212);(_)] -> (4212)"
in line 1 and column 24
unlucky you!
\end{verbatim}
\end{small}
\end{itemize}
\end{block}
\end{frame}

\begin{frame}{Codegenerierung: JVM"=Bytecode}
  \begin{block}{Idee}
    \begin{itemize}
      \item Verarbeitet erweiterten MaMa"=Code: deineMaMa
        \begin{itemize}
          \item Instruktionen die PC lesen, nehmen stattdessen Label als Parameter
          \item Instruktionen die PC modifizieren, geben stattdessen Label aus
        \end{itemize}
      \item Verwendung des JVM"=Heaps
      \item Verwendung von \texttt{java.util.Stack}
      \item Instruktionen in Java geschrieben
    \end{itemize}
  \end{block}
  \begin{block}{ASM}
    \begin{itemize}
      \item Library für Bytecodeinspektion und Modifikation
      \item Wird genutzt um unsere eigene \texttt{main()} einzuschleusen
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}[fragile]{Codegenerierung: Generierter Bytecode}
  \begin{block}{\texttt{main()} nach Java übersetzt}
    \begin{minted}[gobble=6]{java}
      Machine m = new Machine();
      boolean terminate = false;
      int _goto = 0;
      while(!terminate) {
        switch(_goto) {
          case 0:
          case 1:
            _goto = m.eval(2);
            continue;
          case 2:
            m.loadc(0);
          case 3:
            terminate = true;
        }
      }
    \end{minted}
  \end{block}
\end{frame}

\begin{frame}{Zustand}
  \begin{exampleblock}{Was funktioniert}
    \begin{itemize}
      \item Caml Light Syntax, mit (passenden) Fehlermeldungen
      \item Lambdas, Match, Tupel, Records, Strings, Listen
      \item Ausgabe von Java"=Bytecode
    \end{itemize}
  \end{exampleblock}
  \begin{alertblock}{Was nicht funktioniert}
    \begin{itemize}
      \item Typkonstruktoren
      \item Seiteneffekte, Exceptions
      \item Threads
    \end{itemize}
  \end{alertblock}
\end{frame}

\begin{frame}{Testing}
  \begin{itemize}
    \item eigene Testing-Umgebung, ähnlich zu ScalaTest
    \item $\approx 50$ Testcases für Scanner/Parser
    \item $\approx 50$ Testcases für Typinferenz
    \item $\approx 150$ Zeilen Caml Light"=Programme
  \end{itemize}
\end{frame}

\begin{frame}{Benchmarks}
  \begin{block}{Ackermann(3, 5)}
    Zweifaches Pattern Matching

    \begin{tabular}{l|l|l|l}
       & Caml Light & Scala & TUM \\
      \hline
      Kompilieren & \textcolor{fastest}{\unit[0.0]{s}} & \textcolor{slowest}{\unit[9.3]{s}} & \unit[4.1]{s} \\
      Ausführen & \textcolor{fastest}{\unit[0.00]{s}} & \unit[1.03]{s} & \textcolor{slowest}{\unit[1.69]{s}} \\
    \end{tabular}
  \end{block}
  \begin{block}{Factorial(10)}
    Rekursiv

    \begin{tabular}{l|l|l|l}
       & Caml Light & Scala & TUM \\
      \hline
      Kompilieren & \textcolor{fastest}{\unit[0.0]{s}} & \textcolor{slowest}{\unit[9.1]{s}} & \unit[3.9]{s} \\
      Ausführen & \textcolor{fastest}{\unit[0.00]{s}} & \textcolor{slowest}{\unit[0.98]{s}} & \unit[0.13]{s} \\
    \end{tabular}
  \end{block}
  System: Core2~Duo @ 1.5~GHz x86\_64; OpenJDK~1.6.0\_18; Scala~2.8.0; Caml Light~0.75
\end{frame}

\begin{frame}{Spaß}
  \begin{block}{Code}
    $\approx 3.300$ LOC Scala, $\approx 650$ LOC Java, $> 325$ commits
  \end{block}
  \begin{block}{Best of Commit"=Messages}\footnotesize
    \begin{itemize}
      %\item \enquote{Write the bytes in, you know, a correct way}
      \item \enquote{Whee, the machine can actually run more complicated code without failing}
      %\item \enquote{Look at me mom, I made a jQuery"=like chainable DSL for generating bytecode}
      %\item \enquote{Maching of tuples works but is REALLY ugly}
      %\item \enquote{fixed REALLY stupid bug with CUP2/Scala layer}
      \item \enquote{Get out of the JAR, *.mama. You're not even bytecode!}
      \item \enquote{Case classes should not inherit other case classes, you know? We have so much syntactic sugar, use that instead!}
      \item \enquote{Hey ., you should really consider matching newlines, too!}
      %\item \enquote{fixed \enquote{closures vs getbasic}}
      %\item \enquote{Changed order of generated code instruction so that the code is actually valid}
      \item \enquote{Scala supports some mad syntactic sugar. Mad! I tell you.}
      \item \enquote{Marek goes insane and after that, realizes that bipush handles only +127 and then wraps around.}
      %\item \enquote{I can haz right order of valyooz?}
      \item \enquote{I heard you want to know where exactly the typo in your souce code is. Here you are!}
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}{Rückblick}
  \begin{exampleblock}{Was war gut}
    \begin{itemize}
      \item Scalas Pattern Matching
	  \item Verwendung von Git (Branching!)
      \item Betreuung \smiley
    \end{itemize}
  \end{exampleblock}
  \begin{alertblock}{Was war weniger gut}
    \begin{itemize}
      \item NetBeans
      \item Compilezeiten von \texttt{scalac}
      \item Rollo ging täglich um 14:30 rauf \frownie
    \end{itemize}
  \end{alertblock}
\end{frame}

\begin{frame}{Zukunft}
  \begin{block}{Mögliche Erweiterungen}
    \begin{itemize}
      \item Stdlib bereitstellen
      \item Verwendung des JVM"=Stacks
      \item Threads
      \item Optimierungen: TCO
    \end{itemize}
  \end{block}
\end{frame}

\end{document}
