deliverables/p1/p1.tex

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