Zuletzt geändert: Do, 04.08.2005

«11C» Anatomie eines Compilers am Beispiel von Pugs.latex «PDF», «POD»



Download
\documentclass{beamer}
\usepackage{amsmath}
\usepackage{url}
\usepackage{ucs}
\usepackage[utf8]{inputenc}
\usepackage[ngerman]{babel}
% This is a not yet finished (German) talk I'll hold at the next meeting of the
% Linux User Group Augsburg (LUGA) (on 2005-08-04).
% 
% Compile to PDF using...
%   $ pdflatex Anatomie_eines_Compilers_am_Beispiel_von_Pugs.latex
% 
% Feel free to add/change contents (don't forget to add you to the author
% list)!
% 
% As this talk is German, the following comments are German, too.

% Manual syntax highlighting
\newcommand{\synfunc}   [1]{\color{blue!50!black}#1\color{black}}
\newcommand{\synstr}    [1]{\color{red!50!black}#1\color{black}}
\newcommand{\synvar}    [1]{\color{purple!50!black}#1\color{black}}
\newcommand{\synclass}  [1]{\color{green!50!black}#1\color{black}}
\newcommand{\syncomment}[1]{\color{blue!20!black}#1\color{black}}
\newcommand{\syncool}   [1]{\color{beamer@blendedblue}#1\color{black}}
\newcommand{\synoder}      {\ \ \color{black}$\vee$\ \ }
\newcommand{\hr}        {\rule[4pt]{\textwidth}{0.1pt}\\}

\title{Anatomie eines Compilers am Beispiel von Pugs}
\author{Ingo Blechschmidt \\\texttt{<iblech@web.de>}}
\institute{LUGA}
\date{3. August 2005}

\usetheme{Warsaw}
\usecolortheme{seahorse}
\setbeamercovered{transparent}

\begin{document}

\frame{\titlepage}

\section{}
\frame{
  \frametitle{Inhalt}
  \tableofcontents
}

\section{Pugs}
\frame[t]{
  \frametitle{Pugs}

  \begin{itemize}
    \item Pugs: Prototyp des Perl 6-Compilers
    \item "`Perl 6 ist ja schön und gut, aber das dauert doch noch Jahre,
          bis es fertig ist!"'
    \item "`Die Entwickeln doch schon seit Jahren dran!"'
    \item Nur tote Produkte sind "`fertig"'.
    \item Seit dem 1. Februar gibt es Pugs. Heute kann man vernünfig in Perl 6
          programmieren.
  \end{itemize}
}

\subsection{"Ubersicht}
\frame[t]{
  \frametitle{Pugs}
  
  \begin{itemize}
    \item Ursprünglich Haskell-Projekt von Autrijus Tang "`als Übung"'
    \item Projektbeginn: 1. Februar 2005
    \item Nun 130 Entwickler
    \item Version 6.2.8: Beinahe Alles (!), mehrere Backends (direkte
          Ausführung, Kompilierung zu Haskell, zu Perl 5, zu JavaScript, etc.)
  \end{itemize}
}

\subsection{Entwicklung}
\frame[t]{
  \frametitle{Entwicklung}

  \begin{itemize}
    \item Test-driven development --
    \item Camelfolk: Schreiben von Tests in Perl 6 für noch nicht
	  implementierte Features \\
	  \texttt{%
	    \ \ \synfunc{is}\ 23 + 42, 64, "\synstr{Einfache Rechnungen funzen.}";\\
            \ \\
            \ \ \synfunc{my}\ \synvar{@array}\ = <\synstr{a b c}>;\\
            \ \ \synfunc{is}\ +\synvar{@array}, 3,\\
            \ \ \ \ "\synstr{Unser Array enthält drei Elemente.}";
	  }
    \pause
    \item Lambdafolk: Implementierung dieser Features
    \item Ergebnis der Zusammenarbeit: \\
	  Über 7.700 funktionierende Tests
  \end{itemize}
}

\subsection{Pl"ane}
\frame[t]{
  \frametitle{Pläne}

  \begin{tabbing}
    Pugs 6.283185aaa \= ... \kill
    \color{beamer@blendedblue}Pugs 6.0 \> Erstes Release \\
    \color{beamer@blendedblue}Pugs 6.2 \> Grundlegende IO- und Kontrollflusselemente, \\\> veränderbare Variablen \\
    \color{beamer@blendedblue}Pugs 6.28 \> Klassen \\
    \color{beamer@blendedblue}Pugs 6.283 \> Rules und Grammars \\
    \color{beamer@blendedblue}Pugs 6.2831 \> Rollen \\
    \color{beamer@blendedblue}Pugs 6.28318 \> Makros \\
    \color{beamer@blendedblue}Pugs 6.283185 \> Portierung von Pugs von Haskell nach Perl 6 \\
    \color{beamer@blendedblue}Pugs $2\pi$ \> Vollendung
  \end{tabbing}
}

\subsection{Beteiligungsm"oglichkeiten}
\frame[t]{
  \frametitle{Beteiligungsmöglichkeiten}

  \begin{itemize}
    \item Mailinglisten: \\
          \texttt{perl6-language@perl.org}, \\
          \texttt{perl6-compiler@perl.org}, \\
          \texttt{gmane.comp.lang.perl.perl6.language}, \\
          \texttt{gmane.comp.lang.perl.perl6.compiler}
    \item IRC: \texttt{\#perl6} auf Freenode
    \item Auch Newbies sehr gern gesehen!
    \item Schreiben von Tests (Perl 6), Implementierung (Haskell), Schreiben
	  von Dokumentation, Portierung von
	  Perl~5\texttt{|}Python\texttt{|}Ruby\texttt{|}\ldots-Modulen nach
	  Perl 6, \ldots
    \item Weitere Informationen: \url{http://www.pugscode.org/}
  \end{itemize}
}

\section{Compiler}
\subsection{Arbeitsschritte}
\frame[t]{
  \frametitle{Arbeitsschritte}

  \begin{enumerate}
    \item Parsen: Umwandlung des Sourcecode in einen Parse Tree
    \item Kleinere Optimierungen
    \item Umwandlung des Parse Tree in einen einfacheren Tree
    \item Größere Optimierungen, Argumentieren über den Code (z.B. Verbot von
          \texttt{3 = 4} zur Compile-Zeit)
    \item Umwandlung ins Zielformat
    \item Kleinere Optimierungen
    \item Ausgabe
  \end{enumerate}
}

\subsection{Beispiel: Perl 6 $\to$ JavaScript-Compiler}
\frame[t]{
  \frametitle{Beispiel: Perl 6 $\to$ JavaScript-Compiler}

  \begin{itemize}
    \item PIL2JS: Spiel-Projekt von mir, Projektbeginn: 16.7.2005
    \item $\approx$ 4.000 Zeilen Perl 5, Perl 6 und JavaScript
    \item "`Perl 6 überall"' (Browser, PDFs, Flash, \ldots)
  \end{itemize}

  \vfill\pause
  \begin{enumerate}
    \item Einlesen und Parsen von Perl 6 durch Pugs
    \item Ausgabe von Pugs Intermediate Language (PIL) durch Pugs
    \item Einlesen des PIL-Trees durch PIL2JS
    \item Kleinere Umwandlungen
    \item Ausgabe als JavaScript
  \end{enumerate}
}

\section{Perl 6 $\to$ JavaScript}
\subsection{Perl 6 $\to$ PIL}
\frame[t]{
  \frametitle{Parsen von Perl 6-Sourcecode (Perl 6 $\to$ PIL)}

  \begin{itemize}
    \item Perl 6 ist eine umfangreiche Sprache.
    \item Wenn jedes Backend Perl 6 selbst parsen müsste, wäre das viel
          doppelte Arbeit.
    \item Stattdessen: Parsen von Perl 6 durch Pugs, Ausgabe des Codes in einer
          Zwischen-Sprache, Pugs Intermediate Language (PIL)
    \item Einlesen des PIL durch die einzelnen Backends -- Kümmern ums
          Parsen unnötig
  \end{itemize}
}

\frame[t]{
  \frametitle{Beispiel}

  \texttt{%
    \syncomment{\# Perl 6:}\\
    \synvar{\$foo}\ = 19; \\
    \synfunc{say}\ 4 + \synvar{\$foo};\\
  }

  \vfill
  \texttt{%
    \syncomment{-- PIL (vereinfacht):}\\
    \synfunc{PAssign}\ (\synfunc{PVar}\ "\synvar{\$foo}") (\synfunc{PLit}\ 19)\\
    \synfunc{PApp}\ (\synfunc{PVar}\ "\synvar{\&say}") [\\
    \ \ \synfunc{PApp}\ (\synfunc{PVar}\ "\synvar{\&infix:<+>}") [\\
    \ \ \ \ \synfunc{PLit}\ 4, \synfunc{PVar}\ "\synvar{\$foo}"\\
    \ \ ]\\
    ]
  }
}

\subsection{PIL $\to$ JavaScript}
\frame[t]{
  \frametitle{Kompilieren des PIL zu JavaScript}

  \begin{itemize}
    \item "`Sowohl Perl 6 als auch JavaScript sind Turing-vollständig, wo also
          liegt das Problem? (:D)"'
    \item JavaScript: weniger mächtig als Perl 6
    \item Also: Herunterkompilation vieler Features erforderlich
  \end{itemize}
}

\subsection{Probleme}
\frame[t]{
  \frametitle{Problem: Signaturen von Subroutinen}

  \begin{itemize}
    \item Perl 6: Reiche Möglichkeiten zur Spezifikation von Signaturen
          (Parameter-Listen; ähnlich wie Ruby oder Python):

          \texttt{\small%
            \synfunc{sub}\ \synvar{foo}\ (\synclass{Grtz}\ \synvar{\$grtz}, \synclass{Bool}\ ?\synvar{\$verbose}\ = \synvar{false}) \{...\}\\
            \ \\
            \syncomment{\# Ok:}\\
            \synvar{foo}\ \synvar{\$irgendein\_grtz\_objekt};\\
            \synvar{foo}\ \synvar{\$irgendein\_grtz\_objekt}, \synvar{true};\\
            \synvar{foo}\ \synvar{\$irgendein\_grtz\_objekt}, :\synstr{verbose};\\
            \synvar{foo}\ \synvar{\$irgendein\_grtz\_objekt}, :\synstr{verbose}(\synvar{true});\\
            \synvar{foo}\ \synvar{\$irgendein\_grtz\_objekt}, \synstr{verbose}\ => \synvar{true};\\
            \ \\
            \syncomment{\# Fehler:}\\
            \synvar{foo}\ "\synstr{Zu}", <\synstr{viele}>, \synvar{\$parameter};\\
            \synvar{foo}();
          }
  \end{itemize}
}

\frame[t]{
  \frametitle{Problem: Signaturen von Subroutinen}

  \begin{itemize}
    \item JavaScript (vor Version 2): Weit weniger umfangreiche
          Möglichkeiten, Ignorieren von zu vielen/zu wenigen Parametern
          (ähnlich wie PHP):

          \texttt{%
            \synfunc{function}\ \synvar{foo}\ (\synvar{grtz}, \synvar{verbose}) \{...\}\\
            \ \\
            \syncomment{// Ok:}\\
            \synvar{foo}(\synvar{irgendein\_grtz\_objekt});\\
            \synvar{foo}(\synvar{irgendein\_grtz\_objekt}, \synvar{true});\\
            \ \\
            \syncomment{// Ebenfalls ok (!):}\\
            \synvar{foo}();\\
            \synvar{foo}("\synstr{Zu}", \synvar{viele}, \synclass{Para}.\synvar{meter});
          }
  \end{itemize}
}

\frame[t]{
  \frametitle{Problem: Lexikale Variablen}

  \begin{itemize}
    \item Perl 6: Lexikale Variablen (wie bei Ruby, Python, C und vielen
          anderen Sprachen):

          \texttt{%
            \{ \synfunc{say}\ \synvar{\$a}\ \}\ \ \ \ \ \ \ \ \ \ \ \ \ \syncomment{\# Fehler}\\
            \{
              \synfunc{my}\ \synvar{\$a};
              \synfunc{say}\ \synvar{\$a}\ 
            \}\ \ \ \ \ \ \syncomment{\# Ok}\\
            \{
              \synfunc{say}\ \synvar{\$a};
              \synfunc{my}\ \synvar{\$a}\
            \}\ \ \ \ \ \ \syncomment{\# Fehler}\\
          }
    \item JavaScript (ähnlich wie bei Bash oder PHP):

          \texttt{%
            \{ \synfunc{alert}(\synvar{a}) \}\ \ \ \ \ \ \ \ \ \ \ \syncomment{// Fehler}\\
            \{
              \synfunc{var}\ \synvar{a};
              \synfunc{alert}(\synvar{a})
            \}\ \ \ \ \syncomment{// Ok}\\
            \{
              \synfunc{alert}(\synvar{a});
              \synfunc{var}\ \synvar{a}\ 
            \}\ \ \ \ \syncomment{// Kein (!) Fehler}\\
          }
    \item Daher, leider: Durchnummerieren aller lexikalen Variablen
          (\texttt{\synvar{\$a\_1}}, \texttt{\synvar{\$a\_2}}, \ldots) und dann
          Deklaration als globale JavaScript-Variablen
  \end{itemize}
}

\frame[t]{
  \frametitle{Problem: Objekt-Metamodell}

  \begin{block}{Objekt-Metamodell}
    "`Was ist eine Klasse?"' --
    "`Was ist ein Objekt?"' --
    "`Ist eine Klasse auch ein Objekt?"' --
    \ldots
  \end{block}

  \begin{itemize}
    \item Perl 6: Mächtiges Objekt-Metamodell, mit Features u.a. von Smalltalk
          und CLOS
    \item JavaScript: Weniger mächtiges Modell
  \end{itemize}

  \vfill
  \begin{itemize}
    \item Viele Backends haben dieses Problem.
    \item Daher: Exzellente Arbeit von Stevan Little: \\
          Perl 6-Metamodell für Perl 5, Perl 6, JavaScript, Java, C\#, \ldots
  \end{itemize}
}

\frame[t]{
  \frametitle{Weitere Probleme}

  \begin{itemize}
    \item Firefox: langsame JavaScript-Ausführung
    \item Wichtiger noch: Ausführung von Seiten-JavaScripts im gleichen Thread
          wie die UI (Hänger!)
    \item Aber: Exzellente JavaScript-Implementation
  \end{itemize}
}

\frame[t]{
  \frametitle{"`Never do any live demos!"'}

  \begin{itemize}
    \item Hello, World!
    \item \texttt{mandel.p6}
    \item Testsuite
  \end{itemize}
}

\section{Fazit}
\frame[t]{
  \frametitle{Fazit}

  \begin{itemize}
    \item Compiler-Schreiben ist leichter als man denkt. :D
    \item Besonders leicht wird es, wenn einem viel Arbeit abgenommen wird. :)
  \end{itemize}

  \setbeamercovered{invisible}
  \vfill\pause
  \begin{center}
    \Huge Join the fun! \\
    \normalsize \url{http://www.pugscode.org/}
  \end{center}
}

\end{document}