afl-material: comparison handouts/ho01.tex

equal deleted inserted replaced

-:84b4bc6e8554
+:ce767ca23244
 are \pcode{x}, \pcode{foo}, \pcode{foo_bar_1}, \pcode{A_very_42_long_object_name},
 but not \pcode{_i} and also not \pcode{4you}.
 Many programming language offer libraries that can be used to
 validate such strings against regular expressions. Also there
-are some common, and I am sure very familiar, ways how to
+are some common, and I am sure very familiar, ways of how to
 construct regular expressions. For example in Scala we have:
 \begin{center}
 \begin{tabular}{lp{9cm}}
 \pcode{re*} & matches 0 or more occurrences of preceding
 the context of regular expressions, it is a particular pattern
 that can match the specified character. You should also be
 careful with our overloading of the star: assuming you have
 read the handout about our basic mathematical notation, you
 will see that in the context of languages (sets of strings)
-the star stands for an operation on languages. While here
+the star stands for an operation on languages. Here $r^*$
-$r^*$ stands for a regular expression, which is different from
+stands for a regular expression, which is different from the
-the operation on sets is defined as
+operation on sets is defined as
 \[
 A^* \dn \bigcup_{0\le n} A^n
 \]
 structure of regular expressions is always clear. But for
 writing them down in a more mathematical fashion, parentheses
 will be helpful. For example we will write $(r_1 + r_2)^*$,
 which is different from, say $r_1 + (r_2)^*$. The former means
 roughly zero or more times $r_1$ or $r_2$, while the latter
-means $r_1$ or zero or more times $r_2$. This will turn out
+means $r_1$ or zero or more times $r_2$. This will turn out to
-are two different patterns, which match in general different
+be two different patterns, which match in general different
 strings. We should also write $(r_1 + r_2) + r_3$, which is
 different from the regular expression $r_1 + (r_2 + r_3)$, but
 in case of $+$ and $\cdot$ we actually do not care about the
 order and just write $r_1 + r_2 + r_3$, or $r_1 \cdot r_2
 \cdot r_3$, respectively. The reasons for this will become
 which is much less readable than \eqref{email}. Similarly for
 the regular expression that matches the string $hello$ we
 should write
 \[
-{\it h} \cdot {\it e} \cdot {\it l} \cdot {\it l} \cdot {\it o}
+h \cdot e \cdot l \cdot l \cdot o
 \]
 \noindent
 but often just write {\it hello}.
 If you prefer to think in terms of the implementation
 of regular expressions in Scala, the constructors and
 classes relate as follows\footnote{More about Scala is
-in the handout about a crash-course on Scala.}
+in the handout about A Crash-Course on Scala.}
 \begin{center}
 \begin{tabular}{rcl}
 $\varnothing$ & $\mapsto$ & \texttt{NULL}\\
 $\epsilon$    & $\mapsto$ & \texttt{EMPTY}\\
 \noindent As a result we can now precisely state what the
 meaning, for example, of the regular expression $h \cdot
 e \cdot l \cdot l \cdot o$ is, namely
 \[
-L({\it h} \cdot {\it e} \cdot {\it l} \cdot {\it l} \cdot
+L(h \cdot e \cdot  l \cdot l \cdot o) = \{"hello"\}
-{\it o}) = \{"hello"\}
 \]
 \noindent This is expected because this regular expression
 is only supposed to match the ``$hello$''-string. Similarly if
 we have the choice-regular-expression $a + b$, its meaning is
 \]
 \noindent You can now also see why we do not make a difference
 between the different regular expressions $(r_1 + r_2) + r_3$
 and $r_1 + (r_2 + r_3)$\ldots they are not the same regular
-expression, but have the same meaning.
+expression, but they have the same meaning. For example
 \begin{eqnarray*}
 L((r_1 + r_2) + r_3) & = & L(r_1 + r_2) \cup L(r_3)\\
 & = & L(r_1) \cup L(r_2) \cup L(r_3)\\
 & = & L(r_1) \cup L(r_2 + r_3)\\
 \[
 r_1 \equiv r_2 \;\dn\; L(r_1) = L(r_2)
 \]
-\noindent That means two regular expressions are equivalent if
+\noindent That means two regular expressions are said to be
-they match the same set of strings. Therefore we do not really
+equivalent if they match the same set of strings. Therefore we
-distinguish between the different regular expression $(r_1 +
+do not really distinguish between the different regular
-r_2) + r_3$ and $r_1 + (r_2 + r_3)$, because they are
+expression $(r_1 + r_2) + r_3$ and $r_1 + (r_2 + r_3)$,
-equivalent. I leave you to the question whether
+because they are equivalent. I leave you to the question
+whether
 \[
 \varnothing^* \equiv \epsilon^*
 \]
-\noindent holds. Such equivalences will be important for out
+\noindent holds. Such equivalences will be important for our
 matching algorithm, because we can use them to simplify
 regular expressions.
 \subsection*{My Fascination for Regular Expressions}
 compilers, which invariably need regular expression in some
 form or shape.
 To understand my fascination nowadays with regular
 expressions, you need to know that my main scientific interest
-for the last 14 years has been with in theorem provers. I am a
+for the last 14 years has been with theorem provers. I am a
 core developer of one of
 them.\footnote{\url{http://isabelle.in.tum.de}} Theorem
 provers are systems in which you can formally reason about
 mathematical concepts, but also about programs. In this way
 they can help with writing bug-free code. Theorem provers have
 theorem provers. Is this important? I think yes, because
 according to 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 am currently working on
-proving the correctness for one such algorithm that was
+proving the correctness for one such matcher that was
 proposed by Sulzmann and Lu in
 2014.\footnote{\url{http://goo.gl/bz0eHp}} This would be an
 attractive results since we will be able to prove that the
 algorithm is really correct, but also that the machine code(!)
 that implements this code efficiently is correct. Writing
 complementation, something which Gasarch in his
 blog\footnote{\url{http://goo.gl/2R11Fw}} assumed can only be
 shown via automata. Even sombody who has written a 700+-page
 book\footnote{\url{http://goo.gl/fD0eHx}} on regular
 exprssions did not know better. Well, we showed it can also be
-done with regular expressions only. What a feeling if you
+done with regular expressions only.\footnote{\url{http://www.inf.kcl.ac.uk/staff/urbanc/Publications/rexp.pdf}}
-are an outsider to the subject!
+What a feeling if you are an outsider to the subject!
 To conclude: Despite my early ignorance about regular
 expressions, I find them now quite interesting. They have a
 beautiful mathematical theory behind them. They have practical
 importance (remember the shocking runtime of the regular
 expression matchers in Python and Ruby in some instances).
 People who are not very familiar with the mathematical
-background get them consistently wrong. The hope is that we
+background of regular expressions get them consistently wrong.
-can do better in the future---for example by proving that the
+The hope is that we can do better in the future---for example
-algorithms actually satisfy their specification and that the
+by proving that the algorithms actually satisfy their
-corresponding implementations do not contain any bugs. We are
+specification and that the corresponding implementations do
-close, but not yet quite there.
+not contain any bugs. We are close, but not yet quite there.
 Despite my fascination, I am also happy to admit that regular
 expressions have their shortcomings. There are some well-known
-``theoretical shortcomings'', for example recognising strings
+``theoretical'' shortcomings, for example recognising strings
 of the form $a^{n}b^{n}$. I am not so bothered by them. What I
 am bothered about is when regular expressions are in the way
 of practical programming. For example, it turns out that the
 regular expression for email addresses shown in \eqref{email}
 is hopelessly inadequate for recognising all of them (despite
 being touted as something every computer scientist should know
 about). The W3 Consortium (which standardises the Web)
 proposes to use the following, already more complicated
-regular expressions:
+regular expressions for email addresses:
 {\small\begin{lstlisting}[language={},keywordstyle=\color{black},numbers=none]
 [a-zA-Z0-9.!#$%&'*+/=?^_`{|}~-]+@[a-zA-Z0-9-]+(?:\.[a-zA-Z0-9-]+)*
 \end{lstlisting}}
 the syntax of email addresses. With their proposed regular
 expression they are too strict in some cases and too lax in
 others. Not a good situation to be in. A regular expression
 that is claimed to be closer to the standard is shown in
 Figure~\ref{monster}. Whether this claim is true or not, I
-would not know---the only thing I can say it is a monstrosity.
+would not know---the only thing I can say to this regular
-However, this might actually be an argument against the
+expression is it is a monstrosity. However, this might
-standard, rather than against regular expressions. Still it
+actually be an argument against the RFC standard, rather than
-is good to know that some tasks in text processing just
+against regular expressions. Still it is good to know that
-cannot be achieved by using regular expressions.
+some tasks in text processing just cannot be achieved by using
+regular expressions.
 \begin{figure}[p]
 \lstinputlisting{../progs/crawler1.scala}
 \caption{The Scala code for a simple web-crawler that checks

changeset 248	ce767ca23244
parent 245	a5fade10c207
child 250	b79e704acb72