afl-material: comparison handouts/ho01.tex

equal deleted inserted replaced

-:e3c64f22dd31
+:14914b57e207
 %% http://beautifulracket.com
 % compiler explorer
 % https://gcc.godbolt.org
-%https://www.youtube.com/watch?v=gmhMQfFQu20
 % good article how languages have been influenced
 % 10 MOST(LY DEAD) INFLUENTIAL PROGRAMMING LANGUAGES
 % https://www.hillelwayne.com/post/influential-dead-languages/
 \begin{document}
 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018, 2019}
 \section*{Handout 1}
-The purpose of a compiler is to transform a program a human can read
+The purpose of a compiler is to transform a program a human can read and
-and write into code the machine can run as fast as
+write into code the machine can run as fast as possible. Developing a
-possible. Developping a compiler is an old craft going back to 1952
+compiler is an old craft going back to 1952 with the first compiler
-with the first compiler written by Grace Hopper.  Why studiying
+written by Grace Hopper.\footnote{Who many years ago was invited on a
-compilers nowadays?  An interesting answer is given by John Regher in
+talk show hosted by David Letterman, see
-his compiler
+\url{https://youtu.be/3N_ywhx6_K0?t=31}.} Why studying compilers
+nowadays?  An interesting answer is given by John Regher in his compiler
 blog:\footnote{\url{http://blog.regehr.org/archives/1419}}
 \begin{quote}\it{}``We can start off with a couple of observations
 about the role of compilers. First, hardware is getting weirder
 rather than getting clocked faster: almost all processors are
 and growing gap between increasingly high-level languages and
 increasingly wacky platforms. It’s effectively a perpetual
 employment act for solid compiler hackers.''
 \end{quote}
+\noindent
-The first part of this module is about text processing, be it for
+So the goal of this module is to become a solid (beginner) compiler
-compilers, dictionaries, DNA-data, spam-filters and so on.
+hacker and as part of the coursework to implement a small
-When looking for a particular string, say \pcode{"foobar"}, in a large
+compiler for a very small programming language.
-text we can use the Knuth-Morris-Pratt algorithm, which is currently the
-most efficient general string search algorithm. But often we do
+The first part of the module is about the problem of text processing,
-\emph{not} just look for a particular string, but for string patterns.
+which is needed for compilers, but also for dictionaries, DNA-data,
-For example, in program code we need to identify what are the keywords
+spam-filters and so on. When looking for a particular string, say
-(\texttt{if}, \texttt{then}, \texttt{while}, \texttt{for}, etc) and what
+\pcode{"foobar"}, in a large text we can use the Knuth-Morris-Pratt
-are the identifiers (variable names). A pattern for identifiers could be
+algorithm, which is currently the most efficient general string search
-stated as: they start with a letter, followed by zero or more letters,
+algorithm. But often we do \emph{not} just look for a particular string,
-numbers and underscores.
+but for string patterns. For example, in program code we need to
+identify what are the keywords (\texttt{if}, \texttt{then},
+\texttt{while}, \texttt{for}, etc) and what are the identifiers
+(variable names). A pattern for identifiers could be stated as: they
+start with a letter, followed by zero or more letters, numbers and
+underscores.
 %You might also be surprised what
 %constraints programming languages impose about numbers: for example
 %123 in JSON is OK, but 0123 is not.
 %
 \pcode{(re)}	& groups regular expressions and remembers
 matched text
 \end{tabular}
 \end{center}
-\noindent With this table you can figure out the purpose of
+\noindent With this table you can figure out the purpose of the regular
-the regular expressions in the web-crawlers shown Figures
+expressions in the web-crawlers shown Figures \ref{crawler1} and
-\ref{crawler1}, \ref{crawler2} and
+\ref{crawler3}. In in Figure~\ref{crawler1}, however, be careful with
-\ref{crawler3}. Note, however, the regular expression for
+the regular expression for http-addresses in Line~\ref{httpline}. It is
-http-addresses in web-pages in Figure~\ref{crawler1}, Line 15,
+intended to be
-is intended to be
 \[
 \pcode{"https?://[^"]*"}
 \]
-\noindent It specifies that web-addresses need to start with a
+\noindent specifying that http-addresses need to start with a double
-double quote, then comes \texttt{http} followed by an optional
+quote, then comes \texttt{http} followed by an optional \texttt{s} and
-\texttt{s} and so on until the closing double quote comes.
+so on\ldots{}until the closing double quote comes at the end of the
-Usually we would have to escape the double quotes in order to
+address. Normally we would have to escape the double quotes in order to
-make sure we interpret the double quote as character, not as
+make sure we interpret the double quote as character, not as double
-double quote for a string. But Scala's trick with triple
+quote for a string. But Scala's trick with triple quotes allows us to
-quotes allows us to omit this kind of escaping. As a result we
+omit this kind of ugly escaping. As a result we can just write:
-can just write:
 \[
 \pcode{""""https?://[^"]*"""".r}
 \]
 \begin{center}
 \url{https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019}
 \end{center}
 Such troublesome regular expressions are sometimes called \emph{evil
 regular expressions} because they have the potential to make regular
 expression matching engines to topple over, like in Python, Ruby,
 JavaScript and Java 8. This ``toppling over'' is also sometimes called
 \emph{catastrophic backtracking}.  I have also seen the term
 \emph{eternal matching} used for this.  The problem with evil regular
-expressions is that they can have some serious consequences, for
+expressions and catastrophic backtracking is that they can have some
-example, if you use them in your web-application. The reason is that
+serious consequences, for example, if you use them in your
-hackers can look for these instances where the matching engine behaves
+web-application. The reason is that hackers can look for these instances
-badly and then mount a nice DoS-attack against your application. These
+where the matching engine behaves badly and then mount a nice DoS-attack
-attacks are already have their own name: \emph{Regular Expression
+against your application. These attacks are already have their own name:
-Denial of Service Attacks (ReDoS)}.
+\emph{Regular Expression Denial of Service Attacks (ReDoS)}.
 It will be instructive to look behind the ``scenes'' to find out why
 Python and Ruby (and others) behave so badly when matching strings with
 evil regular expressions. But we will also look at a relatively simple
 algorithm that solves this problem much better than Python and Ruby
 \addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
 \end{axis}
 \end{tikzpicture}
 \end{center}
+\noindent
+You might have wondered above why I looked at the (now) old Java 8: the
+reason is that Java 9 and later versions are a bit better, but we will
+still beat them hands down with our regex matcher.
 \subsection*{Basic Regular Expressions}
 The regular expressions shown earlier for Scala, we
 will call \emph{extended regular expressions}. The ones we
 will mainly study in this module are \emph{basic regular
 \begin{figure}[p]\small
 \lstinputlisting[numbers=left,linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}]
 {../progs/crawler1.scala}
 \caption{The Scala code for a simple web-crawler that checks
-for broken links in a web-page. It uses the regular expression
+for broken links in web-pages. It uses the regular expression
 \texttt{http\_pattern} in Line~\ref{httpline} for recognising
 URL-addresses. It finds all links using the library function
-\texttt{findAllIn} in Line~\ref{findallline}.\label{crawler1}}
+\texttt{findAllIn} in Line~\ref{findallline} (this function
+is part of Scala's regular expression library).\label{crawler1}}
 \end{figure}
+%\begin{figure}[p]\small
+%  \lstinputlisting[numbers=left,linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}]
+%                  {../progs/crawler2.scala}
+%
+%\caption{A version of the web-crawler that only follows links
+%in ``my'' domain---since these are the ones I am interested in
+%to fix. It uses the regular expression \texttt{my\_urls} in
+%Line~\ref{myurlline} to check for my name in the links. The
+%main change is in
+%Lines~\ref{changestartline}--\ref{changeendline} where there
+%is a test whether URL is in ``my'' domain or
+%not.\label{crawler2}}
+%\end{figure}
 \begin{figure}[p]\small
 \lstinputlisting[numbers=left,linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}]
 {../progs/crawler2.scala}
-\caption{A version of the web-crawler that only follows links
-in ``my'' domain---since these are the ones I am interested in
-to fix. It uses the regular expression \texttt{my\_urls} in
-Line~\ref{myurlline} to check for my name in the links. The
-main change is in
-Lines~\ref{changestartline}--\ref{changeendline} where there
-is a test whether URL is in ``my'' domain or
-not.\label{crawler2}}
-\end{figure}
-\begin{figure}[p]\small
-\lstinputlisting[numbers=left,linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}]
-{../progs/crawler3.scala}
 \caption{A small email harvester---whenever we download a
 web-page, we also check whether it contains any email
 addresses. For this we use the regular expression
 \texttt{email\_pattern} in Line~\ref{emailline}. The main

changeset 722	14914b57e207
parent 716	df7d47a507f8
child 723	16db16950593