diff -r 99c5916d9a8f -r 7dc3643a0cc5 slides/slides01.tex --- a/slides/slides01.tex Mon Aug 17 17:42:37 2020 +0100 +++ b/slides/slides01.tex Sun Aug 23 23:44:44 2020 +0100 @@ -259,8 +259,9 @@ \begin{frame}[c] \frametitle{Why Bother with Compilers?} -\textbf{Boeings 777}: First flight in 1994. They want to achieve -triple redundancy in hardware faults.\bigskip +\textbf{Boeing 777's}: First flight in 1994. They want to achieve +triple redundancy for potential hardware faults. +\here{http://www.citemaster.net/get/db3a81c6-548e-11e5-9d2e-00163e009cc7/R8.pdf}\bigskip They compile 1 Ada program to\medskip @@ -273,17 +274,25 @@ using 3 independent compilers.\bigskip\pause \small Airbus uses C and static analysers. Recently started using CompCert. - + +\only<1->{% +\begin{textblock}{6}(8,4.5) +\includegraphics[scale=0.28]{../pics/777.png} +\end{textblock}} + \end{frame} %%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Why Bother?} +\frametitle{Why Bother with Regexes?} -\begin{columns}[t] -\begin{column}{.4\textwidth} -Ruby, Python, Java 8\medskip\\ +\begin{columns}[t,onlytextwidth] +\begin{column}{1.8cm} +\mbox{} +\end{column} +\begin{column}{.5\textwidth} +\small{}Ruby, Python, Java 8\medskip\\ \begin{tikzpicture}\footnotesize \begin{axis}[ xlabel={$n$}, @@ -296,7 +305,7 @@ ytick={0,5,...,30}, scaled ticks=false, axis lines=left, - width=5.5cm, + width=\textwidth, height=4cm, legend entries={Python,Ruby}, legend pos=north west, @@ -317,7 +326,7 @@ ytick={0,5,...,30}, scaled ticks=false, axis lines=left, - width=5.5cm, + width=\textwidth, height=4cm, legend entries={Python, Java 8, JavaScript}, legend pos=north west, @@ -327,10 +336,10 @@ \addplot[red,mark=*, mark options={fill=white}] table {re-js.data}; \end{axis} \end{tikzpicture} - +% \end{column} -\begin{column}{.4\textwidth} -Us (after next lecture)\medskip\\ +\begin{column}{.5\textwidth} +\small{}Us (after next lecture)\medskip\\ \begin{tikzpicture}\footnotesize \begin{axis}[ xlabel={$n$}, @@ -343,7 +352,7 @@ ytick={0,5,...,30}, scaled ticks=false, axis lines=left, - width=5.5cm, + width=\textwidth, height=4cm] \addplot[green,mark=square*,mark options={fill=white}] table {re2.data}; \addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; @@ -359,17 +368,28 @@ ytick={0,5,...,30}, scaled ticks=false, axis lines=left, - width=5.5cm, + width=\textwidth, height=4cm] \addplot[black,mark=square*,mark options={fill=white}] table {re3a.data}; \end{axis} \end{tikzpicture} \end{column} -\end{columns}\bigskip +\end{columns} +\medskip + +\begin{textblock}{3}(-0.1,3.3) +\small\hfill\bl{\texttt{[a?]\{n\}[a]\{n\}}}: +\end{textblock} -\small\centering -matching \bl{\texttt{[a?]\{n\}[a]\{n\}}} and \bl{\texttt{(a*)*b}} -against \bl{$\underbrace{\texttt{a}...\texttt{a}}_n$} +\begin{textblock}{3}(-0.1,8.7) +\small\hfill\bl{\texttt{(a*)*b}}: +\end{textblock} + +\begin{textblock}{3}(0.3,13) +\small{}matching with strings +\bl{$\underbrace{\texttt{a}...\texttt{a}}_n$} +\end{textblock} + \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -390,13 +410,16 @@ \end{center}\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip \item on 20 July 2016 the \textbf{Stack Exchange} webpage went down - because of an evil regular expression + because of an evil regular expression + \here{https://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016} \end{itemize} - \begin{textblock}{6}(9,7.6) + \begin{textblock}{6}(6,7.6) \includegraphics[scale=0.14]{../pics/cloudflare.png}\\ \footnotesize - It serves more web traffic than Twitter, Amazon, Apple, Instagram, Bing \& Wikipedia combined. + It serves more web traffic than Twitter, Amazon, Apple, + Instagram, Bing \& Wikipedia combined. + \here{https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/} \end{textblock} \end{frame} @@ -408,13 +431,13 @@ \begin{itemize} \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\medskip -\item Evil regular expressions\medskip +\item Some evil regular expressions:\medskip \begin{itemize} -\item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$} -\item \bl{$(a^*)^*\cdot b$} -\item \bl{$([a-z]^+)^*$} -\item \bl{$(a + a \cdot a)^*$} -\item \bl{$(a + a^?)^*$} +\item \bl{\texttt{[a?]\{n\}\;[a]\{n\}}} +\item \bl{\texttt{(a*)*\;b}} +\item \bl{\texttt{([a-z]+)*}} +\item \bl{\texttt{(a + aa)*}} +\item \bl{\texttt{(a + a?)*}} \end{itemize} \item sometimes also called \alert{catastrophic backtracking} @@ -427,7 +450,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] +\begin{frame}[t] \frametitle{The Acad.~Subject is Mature} \bigskip @@ -437,26 +460,28 @@ \item The first compiler for COBOL, 1957\\ (Grace Hopper)\medskip \item But surprisingly research papers are still published nowadays\\ \item ``Parsing: The Solved Problem That Isn't'' + \here{https://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt.html} \end{itemize} + +\begin{textblock}{8.5}(5,7.6) \begin{flushright} \includegraphics[scale=0.3]{pics/hopper.jpg}\\ -\footnotesize\textcolor{gray}{Grace Hopper} -\end{flushright} - +\footnotesize\textcolor{gray}{Grace Hopper}\smallskip\\ -\begin{flushright} -\mbox{}\\[-6mm] -{\footnotesize\textcolor{gray}{(she made it to David Letterman's Tonight Show,\\[-2mm] - \url{https://youtu.be/3N_ywhx6_K0?t=31})}} +{\small\textcolor{gray}{(she made it to David Letterman's Tonight Show + \here{https://youtu.be/3N_ywhx6_K0?t=31})}} \end{flushright} +\end{textblock} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Remember BF*** from PEP?} +\frametitle{What Do Compilers Do?} + +Remember BF*** from PEP? \begin{center} \begin{tabular}{lcl} @@ -477,7 +502,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] - \frametitle{A ``Compiler'' for BF***} + \frametitle{A ``Compiler'' for BF*** to C} \begin{center} \begin{tabular}{lcl} @@ -525,17 +550,18 @@ \begin{frame}[c] \frametitle{Lectures 5 - 10} - code generation for a small imperative and a small functional languages\\[10mm] + code generation for a small imperative and a small functional language\\[10mm] {\LARGE\bf Interpreters}\medskip\\ \hspace{5mm}(directly runs a program)\\[6mm] {\LARGE\bf Compilers}\medskip\\ - \hspace{5mm}(generates JVM code) + \hspace{5mm}(generate JVM code and LLVM-IR code) - \begin{textblock}{1}(10,8.1) - \begin{tabular}{c} - \includegraphics[scale=0.4]{../pics/javaduke.png} + \begin{textblock}{1}(8.8,8.1) + \begin{tabular}{c@{}c} + \includegraphics[scale=0.4]{../pics/javaduke.png} & + \includegraphics[scale=0.23]{../pics/llvmlogo.png} \end{tabular} \end{textblock} @@ -879,10 +905,8 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] - Regular Expression\end{tabular}} +\frametitle{The Meaning of a Regex} \begin{textblock}{15}(1,4) \begin{tabular}{rcl} @@ -901,7 +925,7 @@ } \end{textblock} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -1023,9 +1047,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{ - The Meaning of a\\[-2mm] - Regular Expression} +\frametitle{The Meaning of a Regex} ...all the strings a regular expression can match. @@ -1177,24 +1199,24 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Lecture Capture} - -\begin{itemize} -\item Hope it works\ldots\pause actually no, it does not!\medskip\pause -\item It is important to use lecture capture wisely\\ (it is only the ``baseline''): -\begin{itemize} -\item Lecture recordings are a study and revision aid. -\item Statistically, there is a clear and direct link between attendance and - attainment: students who do not attend lectures, do less well in exams. -\end{itemize} - -\item Attending a lecture is more than watching it online -- if you do not -attend, you miss out! - -\end{itemize} - -\end{frame} +%\begin{frame}[c] +%\frametitle{Lecture Capture} +% +%\begin{itemize} +%\item Hope it works\ldots\pause actually no, it does not!\medskip\pause +%\item It is important to use lecture capture wisely\\ (it is only the ``baseline''): +%\begin{itemize} +%\item Lecture recordings are a study and revision aid. +%\item Statistically, there is a clear and direct link between attendance and +% attainment: students who do not attend lectures, do less well in exams. +%\end{itemize} +% +%\item Attending a lecture is more than watching it online -- if you do not +%attend, you miss out! +% +%\end{itemize} +% +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%