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 Result is either Error or \texttt{b}, not a \texttt{[b]} as
  43                                 described Hutton \& Meijer \footnote{G. Hutton and E. Meijer.
  44                                 Monadic parser combinators. 1996.}
  45                 \pause
  46                 \item Matches longest left-most parser
  47                 \pause
  48                 \item Stops immediately on error\pause\\
  49                         By design!
  50         \end{itemize}
  51 \end{frame}
  52
  53 \begin{frame}[fragile]
  54         \frametitle{\textsc{YARD} Combinators}
  55         \framesubtitle{Designed to be minimal, just 14 parsers/combinators}
  56         YARD is designed to be minimal and defines just 14 primitives:
  57         \begin{columns}[t]
  58                 \begin{column}{0.5\textwidth}
  59                         \begin{CleanCode}
  60 top :: Parser a a
  61 peek :: Parser a a
  62 fail :: Parser a b
  63 eof :: Parser a Void
  64 (until) :: (Parser a b)
  65         (Parser a c)
  66         -> Parser a [b]
  67 satisfy :: (a -> Bool)
  68         -> Parser a a
  69 check :: (a -> Bool)
  70         -> Parser a a
  71 item :: a -> Parser a a
  72 list :: [a] -> Parser a [a]
  73                         \end{CleanCode}
  74                 \end{column}
  75                 \begin{column}{0.5\textwidth}
  76                         \begin{CleanCode}
  77 (>>=) :: (Parser a b)
  78        (b -> Parser a c)
  79         -> Parser a c
  80 (<|>) :: (Parser a b)
  81        (Parser a b)
  82        -> Parser a b
  83 some :: (Parser a b)
  84        -> Parser a [b]
  85 many :: (Parser a b)
  86        -> Parser a [b]
  87 optional :: (Parser a b)
  88       -> Parser a (Maybe b)
  89                         \end{CleanCode}
  90                 \end{column}
  91         \end{columns}
  92 \end{frame}
  93
  94 \begin{frame}[fragile]
  95         \frametitle{\textsc{YARD} Combinators}
  96         \framesubtitle{Designed to be minimal, just \textbf{7} parsers/combinators}
  97         Actually, scrap that, just \textbf{7} primitives:
  98         \begin{columns}[t]
  99                 \begin{column}{0.5\textwidth}
 100                         \begin{CleanCode}
 101 top :: Parser a a
 102 peek :: Parser a a
 103 fail :: Parser a b
 104 eof :: Parser a Void
 105                         \end{CleanCode}
 106                 \end{column}
 107                 \begin{column}{0.5\textwidth}
 108                         \begin{CleanCode}
 109 (>>=) :: (Parser a b)
 110        (b -> Parser a c)
 111         -> Parser a c
 112 (<|>) :: (Parser a b)
 113        (Parser a b)
 114        -> Parser a b
 115                         \end{CleanCode}
 116                 \end{column}
 117         \end{columns}
 118         All others can be (and are) derived from these. e.g.
 119         \begin{lstlisting}
 120 satisfy :: (a -> Bool) -> Parser a a
 121 satisfy f = top >>= \c -> if (f c) (return c) fail
 122         \end{lstlisting}
 123 \end{frame}
 124
 125 \section{Design choices}
 126 \begin{frame}
 127         \frametitle{Adapting the grammar}
 128         \begin{itemize}
 129                 \item Remove left recursion
 130                 \item Fixing associativity
 131                 \item Added small features such as escape characters \texttt{
 132                         \textbackslash n\textbackslash b}
 133                 \pause
 134                 \item Show grammar now\ldots
 135         \end{itemize}
 136 \end{frame}
 137
 138 \begin{frame}
 139         \frametitle{Two-phase design}
 140         \framesubtitle{Lexing}
 141         Also done with \textsc{YARD} because
 142         \begin{itemize}
 143                 \item Multiline comments
 144                 \item Alternatives
 145                 \item Positions
 146         \end{itemize}
 147 \end{frame}
 148
 149 \begin{frame}[fragile]
 150         \frametitle{Two-phase design}
 151         \framesubtitle{Parsing}
 152         Read from stdin, write to stdout\\
 153         Added some handy primitives
 154         \begin{CleanCode}
 155 parseBlock :: Parser Token [Stmt]
 156
 157 parseOpR :: (Parser Token Op2) (Parser Token Expr) -> Parser Token Expr
 158 parseOpL :: (Parser Token Op2) (Parser Token Expr) -> Parser Token Expr
 159
 160 trans2 :: TokenValue (TokenValue -> a) -> Parser Token a
 161 trans1 :: TokenValue a -> Parser Token a
 162
 163 peekPos :: Parser Token Pos
 164         \end{CleanCode}
 165 \end{frame}
 166
 167 \begin{frame}[fragile]
 168         \frametitle{Statistics}
 169         \framesubtitle{Lines of code}
 170         \lstinputlisting{|"wc -l ../../*.[di]cl"}
 171         \pause
 172         \begin{block}{}
 173                 \emph{``Measuring programming progress by lines of code is like
 174                 measuring aircraft building progress by weight.''}\\
 175                 {---} Bill Gates
 176         \end{block}
 177 \end{frame}
 178
 179 \begin{frame}
 180         \frametitle{Statistics}
 181         \framesubtitle{Hours of work}
 182         We have no clue how much time we have worked on it\ldots
 183         \pause
 184         \begin{block}{}
 185                 \emph{``Choose a job you love, and you will never have to work a day in
 186                 your life.''}\\
 187                 {---} Confucius
 188         \end{block}
 189 \end{frame}
 190
 191 \section{Examples}
 192 \begin{frame}
 193         \frametitle{Weird inputs}
 194         \begin{itemize}
 195                 \item \pause Heap full
 196                         \pause\ldots Increase heap\\
 197                         \texttt{\$ ./spl -h 2000M}
 198                 \item \pause Stack full
 199                         \pause\ldots Increase stack\\
 200                         \texttt{\$ ./spl -s 200M}
 201                 \item \pause Segmentation fault
 202                         \pause\ldots Enable memory overcommitting\\
 203                                 \texttt{\# echo 1 > /proc/sys/vm/overcommit\_memory}
 204                 \item \pause Still segmentation fault
 205                         \pause\ldots Buy more \textsc{RAM}
 206                 \item \pause Still segmentation fault?
 207                         \pause\ldots Divide into modules and parse separatly~\footnote{To be
 208                         implemented}
 209                 \item \pause Thus, we are only limited by hardware\ldots
 210         \end{itemize}
 211 \end{frame}
 212
 213 \begin{frame}
 214         \frametitle{Learned lessons}
 215         \begin{itemize}
 216                 \item \pause Parser combinators are elegant!
 217                 \item \pause Positional errors are a must!
 218                 \item \ldots
 219         \end{itemize}
 220 \end{frame}
 221 \end{document}