deliverables/p1/p1.tex

   1 %&p1
   2 \begin{document}
   3 \frame{\titlepage}
   4
   5 \section{Introduction}
   6 \begin{frame}
   7         \frametitle{\textsc{SPL}}
   8         \framesubtitle{Acronym for: \textsc{SPL}: Parser and Lexer}
   9         \begin{block}{Features}
  10                 \begin{itemize}
  11                         \item Implementation language:
  12                                 Clean ({\tiny\url{http://clean.cs.ru.nl}})
  13                                 \pause
  14                                 \begin{itemize}
  15                                         \item Pure language
  16                                         \item Higher order functions
  17                                         \item Monads
  18                                         \item Using parser combinator library \textsc{Yard}
  19                                 \end{itemize}
  20                         \pause
  21                         \item Positional data available for easy locating of errors.
  22                         \pause
  23                         \item Standardized parser errors. This means you can set it as
  24                                 \texttt{buildprg} in \texttt{vim} and you can then use the
  25                                 quickfix window!
  26                 \end{itemize}
  27         \end{block}
  28 \end{frame}
  29
  30 \begin{frame}[fragile]
  31         \frametitle{\textsc{YARD}}
  32         \framesubtitle{A minimal home grown monadic parser combinator library}
  33         \begin{itemize}
  34                 \item Inspired by \textsc{parsec}: $1pc=3.375\cdot10^{16}yd$~\footnote{
  35                                 A yard is exactly $36$ inch and an inch is exactly the length
  36                                 of $3$ barleycorns}.
  37                 \item Definitons:
  38                         \begin{lstlisting}
  39 :: Error = PositionalError Int Int String | Error String
  40 :: Parser a b = Parser ([a] -> (Either Error b, [a]))
  41                         \end{lstlisting}
  42                 \pause
  43                 \item Matches longest left-most parser
  44                 \pause
  45                 \item Stops immediately on error\pause\\
  46                         By design!
  47         \end{itemize}
  48 \end{frame}
  49
  50 \begin{frame}[fragile]
  51         \frametitle{\textsc{YARD} Combinators}
  52         \begin{lstlisting}
  53 instance Functor (Parser a)
  54 instance Applicative (Parser a)
  55 instance Monad (Parser a)
  56 instance Alternative (Parser a)
  57
  58 runParser :: (Parser a b) [a] -> (Either Error b, [a])
  59 (<?>) :: (Parser a b) Error -> Parser a b
  60 fail :: Parser a b
  61 top :: Parser a a
  62 peek :: Parser a a
  63 satisfy :: (a -> Bool) -> Parser a a
  64 check :: (a -> Bool) -> Parser a a
  65 (until) infix 2 :: (Parser a b) (Parser a c) -> Parser a [b]
  66 item :: a -> Parser a a | Eq a
  67 list :: [a] -> Parser a [a] | Eq a
  68 eof :: Parser a Void
  69         \end{lstlisting}
  70 \end{frame}
  71
  72 \section{Design choices}
  73 \begin{frame}
  74         \frametitle{Adapting the grammar}
  75         \begin{itemize}
  76                 \item Remove left recursion
  77                 \item Fixing associativity
  78                 \item Added small features such as escape characters \texttt{
  79                         \textbackslash n\textbackslash b}
  80                 \pause
  81                 \item Show grammar now\ldots
  82         \end{itemize}
  83 \end{frame}
  84
  85 \begin{frame}
  86         \frametitle{Two-phase design}
  87         \framesubtitle{Lexing}
  88         Also done with \textsc{YARD} because
  89         \begin{itemize}
  90                 \item Multiline comments
  91                 \item Alternatives
  92                 \item Positions
  93         \end{itemize}
  94 \end{frame}
  95
  96 \begin{frame}[fragile]
  97         \frametitle{Two-phase design}
  98         \framesubtitle{Parsing}
  99         Read from stdin, write to stdout\\
 100         Added some handy primitives
 101         \begin{lstlisting}
 102 parseBlock :: Parser Token [Stmt]
 103
 104 parseOpR :: (Parser Token Op2) (Parser Token Expr) -> Parser Token Expr
 105 parseOpL :: (Parser Token Op2) (Parser Token Expr) -> Parser Token Expr
 106
 107 trans2 :: TokenValue (TokenValue -> a) -> Parser Token a
 108 trans1 :: TokenValue a -> Parser Token a
 109
 110 peekPos :: Parser Token Pos
 111         \end{lstlisting}
 112 \end{frame}
 113
 114 \begin{frame}[fragile]
 115         \frametitle{Statistics}
 116         \framesubtitle{Lines of code}
 117         \lstinputlisting{|"wc -l ../../*.[di]cl"}
 118         \pause
 119         \begin{block}{}
 120                 \emph{``Measuring programming progress by lines of code is like
 121                 measuring aircraft building progress by weight.''}\\
 122                 {---} Bill Gates
 123         \end{block}
 124 \end{frame}
 125
 126 \begin{frame}
 127         \frametitle{Statistics}
 128         \framesubtitle{Hours of work}
 129         We have no clue how much time we have worked on it\ldots
 130         \pause
 131         \begin{block}{}
 132                 \emph{``Choose a job you love, and you will never have to work a day in
 133                 your life.''}\\
 134                 {---} Confucius
 135         \end{block}
 136 \end{frame}
 137
 138 \section{Examples}
 139 \begin{frame}
 140         \frametitle{Wierd inputs}
 141         \begin{itemize}
 142                 \item \pause Heap full
 143                         \pause\ldots Increase heap\\
 144                         \texttt{\$ ./spl -h 2000M}
 145                 \item \pause Stack full
 146                         \pause\ldots Increase stack\\
 147                         \texttt{\$ ./spl -s 200M}
 148                 \item \pause Segmentation fault
 149                         \pause\ldots Enable memory overcommitting\\
 150                                 \texttt{\# echo 1 > /proc/sys/vm/overcommit\_memory}
 151                 \item \pause Still segmentation fault
 152                         \pause\ldots Buy more \textsc{RAM}
 153                 \item \pause Still segmentation fault?
 154                         \pause\ldots Divide into modules and parse separatly~\footnote{To be
 155                         implemented}
 156                 \item \pause Thus, we are only limited by hardware\ldots
 157         \end{itemize}
 158 \end{frame}
 159
 160 \begin{frame}
 161         \frametitle{Learned lessons}
 162         \begin{itemize}
 163                 \item \pause Parser combinators are elegant!
 164                 \item \pause Positional errors are a must!
 165                 \item \ldots
 166         \end{itemize}
 167 \end{frame}
 168 \end{document}