afl-material: comparison handouts/ho01.tex

equal deleted inserted replaced

-:437e4f8d35d8
+:6ad0f63e1968
 % 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, 2020, 2021}
+\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2023}
 \section*{Handout 1}
 The purpose of a compiler is to transform a program a human can read and
 write into code machines can run as fast as possible. Developing a
 compiler is an old craft going back to 1952 with the first compiler
 written by Grace Hopper.\footnote{Who many years ago was invited on a
 talk show hosted by David Letterman.
 \here{https://youtu.be/3N_ywhx6_K0?t=31}} Why studying compilers
-nowadays?  An interesting answer is given by John Regher in his compiler
+nowadays?  An interesting answer is given by John Regehr in his compiler
 blog:\here{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
 \pcode{(re)}	& groups regular expressions and remembers
 matched text
 \end{tabular}
 \end{center}
-\noindent With this table you can figure out the purpose of the regular
+The syntax is pretty universal and can be found in many regular
-expressions in the web-crawlers shown Figures \ref{crawler1} and
+expression libraries. If you need a quick recap about regular
-\ref{crawler3}. In Figure~\ref{crawler1}, however, be careful with
+expressions and how the match strings, here is a quick video:
-the regular expression for http-addresses in Line~\ref{httpline}. It is
+\url{https://youtu.be/bgBWp9EIlMM}.
-intended to be
-\[
-\pcode{"https?://[^"]*"}
-\]
-\noindent specifying that http-addresses need to start with a double
-quote, then comes \texttt{http} followed by an optional \texttt{s} and
-so on\ldots{}until the closing double quote comes at the end of the
-address. Normally we would have to escape the double quotes in order to
-make sure we interpret the double quote as character, not as double
-quote for a string. But Scala's trick with triple quotes allows us to
-omit this kind of ugly escaping. As a result we can just write:
-\[
-\pcode{""""https?://[^"]*"""".r}
-\]
-\noindent The convention in Scala is that \texttt{.r} converts a string
-into a regular expression. I leave it to you to ponder whether this
-regular expression really captures all possible web-addresses. If you
-need a quick recap about regular expressions and how the match strings,
-here is a quick video: \url{https://youtu.be/bgBWp9EIlMM}.
 \subsection*{Why Study Regular Expressions?}
 Regular expressions were introduced by Kleene in the 1950ies and they
 have been object of intense study since then. They are nowadays pretty
 implementing regular expressions. I am sure you have come across them
 before (remember the PRA or PEP modules?).
 Why on earth then is there any interest in studying them again in depth
 in this module? Well, one answer is in the following two graphs about
-regular expression matching in Python, Ruby, JavaScript and Java
+regular expression matching in Python, Ruby, JavaScript, Swift and Java
 (Version 8).
 \begin{center}
 \begin{tabular}{@{\hspace{-1mm}}c@{\hspace{1.5mm}}c@{}}
 \begin{tikzpicture}
 ytick={0,5,...,30},
 scaled ticks=false,
 axis lines=left,
 width=5.5cm,
 height=4.5cm,
-legend entries={Python, Java 8, JavaScript},
+legend entries={Python, Java 8, JavaScript, Swift},
 legend pos=north west,
 legend cell align=left]
 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
 \addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
+\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
 \end{axis}
 \end{tikzpicture}
 &
 \begin{tikzpicture}
 \begin{axis}[
 \end{axis}
 \end{tikzpicture}
 \end{tabular}
 \end{center}
-\noindent The first graph shows that Python, JavaScript and Java 8 need
+\noindent The first graph shows that Python, JavaScript, Swift and Java 8 need
 approximately 30 seconds to find out that the regular expression
 $\texttt{(a*)*\,b}$ does not match strings of 28 \texttt{a}s. Similarly,
 the second shows that Python and Ruby need approximately 29 seconds for finding
 out whether a string of 28 \texttt{a}s matches the regular expression
 \texttt{a?\{28\}\,a\{28\}}.\footnote{In this
 \noindent
 and also when somebody tried to match web-addresses using a
 relatively simple regular expression
 \begin{center}
-\url{https://www.tutorialdocs.com/article/regex-trap.html}
+\url{https://archive.ph/W5Ogx#selection-141.1-141.36}
 \end{center}
 \noindent
 Finally, on 2 July 2019 Cloudflare had a global outage because of a
 regular expression (they had no outage for the 6 years before).  What
 regular expressions}. This notion allows one to do almost all
 calculations with regular expressions on the level of regular
 expressions, not needing any automata (you will see we only touch
 briefly on automata in lecture 3). Automata are usually the main
 object of study in formal language courses.  The avoidance of automata
-is crucial for me because automata are graphs and it is rather difficult to
+is crucial for me because automata are graphs and it is rather
-reason about graphs in theorem provers. In contrast, reasoning about
+difficult to reason about graphs in theorem provers. In contrast,
-regular expressions is easy-peasy in theorem provers. Is this
+reasoning about regular expressions is easy-peasy in theorem
-important? I think yes, because according to Kuklewicz nearly all
+provers. Is this important? I think yes, because according to
-POSIX-based regular expression matchers are
+Kuklewicz nearly all POSIX-based regular expression matchers are
 buggy.\footnote{\url{http://www.haskell.org/haskellwiki/Regex_Posix}}
-With my PhD student Fahad Ausaf I proved the correctness for one such
+With my PhD students Fahad Ausaf and Chengsong Tan, I proved the
-matcher that was proposed by Sulzmann and Lu in
+correctness for two such matchers that were proposed by Sulzmann and Lu
-2014.\footnote{\url{http://goo.gl/bz0eHp}} Hopefully we can prove that
+in 2014.\footnote{\url{http://goo.gl/bz0eHp}} A variant of which you have
-the machine code(!)  that implements this code efficiently is correct
+already seen in PEP as CW3 and you will see again in the CFL in the first
-also. Writing programs in this way does not leave any room for
+two CWs. What we have not yet figured out that our matchers are
-potential errors or bugs. How nice!
+universally fast, meaning they do not explode on any input.
+Hopefully we can also prove
+that the machine code(!)  that implements our matchers efficiently is
+correct also. Writing programs in this way does not leave any room for
+any errors or bugs. How nice!
 What also helped with my fascination with regular expressions
 is that we could indeed find out new things about them that
 have surprised some experts. Together with two colleagues from China, I was
 able to prove the Myhill-Nerode theorem by only using regular
 complementation, something which Bill Gasarch in his Computational Complexity
 blog\footnote{\url{http://goo.gl/2R11Fw}} assumed can only be
 shown via automata. So even somebody who has written a 700+-page
 book\footnote{\url{http://goo.gl/fD0eHx}} on regular
 expressions did not know better. Well, we showed it can also be
-done with regular expressions only.\footnote{\url{http://nms.kcl.ac.uk/christian.urban/Publications/posix.pdf}}
+done with regular expressions only.\footnote{\url{https://nms.kcl.ac.uk/christian.urban/Publications/rexp.pdf}}
 What a feeling when you are an outsider to the subject!
 To conclude: Despite my early ignorance about regular expressions, I
 find them now extremely interesting. They have practical importance
 (remember the shocking runtime of the regular expression matchers in
-Python, Ruby and Java in some instances and the problems in Stack
+Python, Ruby, Swift and Java in some instances and the problems in Stack
-Exchange and the Atom editor). They are used in tools like Snort and
+Exchange and the Atom editor---even regex libraries in more modern programming languages, like Rust, have their problems). They are used in tools like Snort and
 Zeek in order to monitor network traffic. They have a beautiful mathematical
 theory behind them, which can be sometimes quite deep and which
 sometimes contains hidden snares.  People who are not very familiar
 with the mathematical background of regular expressions get them
 consistently wrong (this is surprising given they are a supposed to be
 best solution is to use regular expressions; now you have two
 problems.''
 \end{quote}
-\begin{figure}[p]\small
+%\begin{figure}[p]\small
-\lstinputlisting[numbers=left,linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}]
+%  \lstinputlisting[numbers=left,linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}]
-{../progs/crawler1.scala}
+%                  {../progs/crawler1.scala}
+%
-\caption{The Scala code for a simple web-crawler that checks
+%\caption{The Scala code for a simple web-crawler that checks
-for broken links in web-pages. 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
+%\texttt{http\_pattern} in Line~\ref{httpline} for recognising
-URL-addresses. It finds all links using the library function
+%URL-addresses. It finds all links using the library function
-\texttt{findAllIn} in Line~\ref{findallline} (this function
+%\texttt{findAllIn} in Line~\ref{findallline} (this function
-is part of Scala's regular expression library).\label{crawler1}}
+%is part of Scala's regular expression library).\label{crawler1}}
+%
-\end{figure}
+%\end{figure}
 %\begin{figure}[p]\small
 %  \lstinputlisting[numbers=left,linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}]
 %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
+%\begin{figure}[p]\small
-\lstinputlisting[numbers=left,linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}]
+%  \lstinputlisting[numbers=left,linebackgroundcolor={\ifodd\value{lstnumber}\co%lor{capri!3}\fi}]
-{../progs/crawler2.scala}
+%                  {../progs/crawler2.scala}
+%
-\caption{A small email harvester---whenever we download a
+%\caption{A small email harvester---whenever we download a
-web-page, we also check whether it contains any email
+%web-page, we also check whether it contains any email
-addresses. For this we use the regular expression
+%addresses. For this we use the regular expression
-\texttt{email\_pattern} in Line~\ref{emailline}. The main
+%\texttt{email\_pattern} in Line~\ref{emailline}. The main
-change is in Line~\ref{mainline} where all email addresses
+%change is in Line~\ref{mainline} where all email addresses
-that can be found in a page are printed.\label{crawler3}}
+%that can be found in a page are printed.\label{crawler3}}
+%
-\end{figure}
+%\end{figure}
 \begin{figure}[p]
 \tiny
 \begin{center}
 \begin{minipage}{0.8\textwidth}

changeset 924	6ad0f63e1968
parent 905	15973df32613
child 925	ddb521b57e0c