diff -r 9b1c15c3eb6f -r f618dd4de24a slides/slides01.tex --- a/slides/slides01.tex Wed Sep 25 11:24:34 2019 +0100 +++ b/slides/slides01.tex Wed Sep 25 23:56:36 2019 +0100 @@ -1,3 +1,4 @@ +% !TEX program = xelatex \documentclass[dvipsnames,14pt,t,xelatex]{beamer} \usepackage{../slides} \usepackage{../graphics} @@ -20,11 +21,6 @@ \begin{document} - - - - - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] \frametitle{% @@ -44,8 +40,9 @@ \begin{center} \begin{tabular}{ll} Email: & christian.urban at kcl.ac.uk\\ - Office: & N\liningnums{7.07} (North Wing, Bush House)\\ - Slides: & KEATS + Office Hours: & Thursdays 12 -- 14\\ + & N\liningnums{7.07} (North Wing, Bush House)\\ + Slides \& Progs: & KEATS\\ \end{tabular} \end{center} @@ -67,30 +64,27 @@ \only<2>{ \begin{itemize} \item {\bf Hardware is getting weirder - rather than getting clocked faster} + rather than getting clocked faster.} \begin{itemize} -\item Almost all processors are - multicores nowadays and it looks like there is increasing asymmetry in - resources across cores. Processors come with vector units, crypto - accelerators etc. We have DSPs, GPUs, - ARM big.little, and Xeon Phi. This is only scratching the - surface. +\item[] ``Almost all processors are multicores nowadays and it looks + like there is increasing asymmetry in resources across cores. + Processors come with vector units, crypto accelerators etc. We have + DSPs, GPUs, ARM big.little, and Xeon Phi. This is only scratching the + surface.'' \end{itemize} \end{itemize}} \only<3>{ \begin{itemize} \item {\bf We’re getting tired of low-level languages and - their associated security disasters} + their associated security disasters.} \begin{itemize} -\item - We want to write new code, to - whatever extent possible, in safer, higher-level - languages. Compilers are caught right in the middle of these - opposing trends: one of their main jobs is to help bridge the large - and growing gap between increasingly high-level languages and - increasingly wacky platforms. +\item [] ``We want to write new code, to whatever extent possible, in + safer, higher-level languages. Compilers are caught right in the + middle of these opposing trends: one of their main jobs is to help + bridge the large and growing gap between increasingly high-level + languages and increasingly wacky platforms.'' \end{itemize} \end{itemize}}} @@ -98,6 +92,47 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] + \frametitle{What are Compilers?} + +\begin{center} +\begin{tikzpicture}[] + \node (0) at (-2.3,0) {\includegraphics[scale=0.3]{pics/csource.png}}; + \node (1) [right=35mm] at (0) {\includegraphics[scale=0.3]{pics/cassmbl.png}}; + \draw [->,line width=4mm, red] (0) -- (1); +\end{tikzpicture} +\end{center} + +\begin{textblock}{10}(1,13.5) +Compiler explorers, e.g.: \url{https://gcc.godbolt.org} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Why Bother?\\[-2mm] Compilers \& Boeings 777\end{tabular}} + +First flight in 1994. They want to achieve triple redundancy in hardware +faults.\bigskip + +They compile 1 Ada program to\medskip + +\begin{itemize} + \item Intel 80486 + \item Motorola 68040 (old Macintosh's) + \item AMD 29050 (RISC chips used often in laser printers) +\end{itemize}\medskip\medskip + +using 3 independent compilers.\bigskip\pause + +\small Airbus uses C and static analysers. Recently started using CompCert. + +\end{frame} +%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{Why Bother?} @@ -139,11 +174,12 @@ axis lines=left, width=5.5cm, height=4cm, - legend entries={Python, Java 8}, + legend entries={Python, Java 8, JavaScript}, 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}; \end{axis} \end{tikzpicture} @@ -191,7 +227,36 @@ against $\underbrace{\texttt{a}...\texttt{a}}_n$ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c,fragile] + \frametitle{Incidents} + + \begin{itemize} + \item a global outage on 2 July 2019 at \textbf{Cloudflare} + (first one for six years)\medskip + + \begin{center}\small\color{blue} + \begin{verbatim} + (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false| + null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s + |-|~|!|{}|\|\||\+)*.*(?:.*=.*))) + \end{verbatim} + \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 + \end{itemize} + + \begin{textblock}{6}(9,7.6) + \includegraphics[scale=0.14]{cloudflare.png}\\ + \footnotesize + It serves more web traffic than Twitter, Amazon, Apple, Instagram, Bing \& Wikipedia combined. + \end{textblock} + + \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{Evil Regular Expressions} @@ -209,7 +274,7 @@ \item sometimes also called \alert{catastrophic backtracking} \item this is a problem for \alert{N}etwork \alert{I}ntrusion - \alert{D}etection systems, StackExchange, Atom editor + \alert{D}etection systems, Cloudflare, StackExchange, Atom editor \item \url{https://vimeo.com/112065252} \end{itemize} @@ -339,10 +404,11 @@ \begin{frame}[c] \frametitle{The Acad.~Subject is Mature} +\bigskip \begin{itemize} -\item Turing Machines, 1936 +\item Turing Machines, 1936 (a tape as memory) \item Regular Expressions, 1956\\ -\item The first compiler for COBOL, 1957\\ (Grace Hopper) +\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'' \end{itemize} @@ -417,123 +483,123 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Today} - -\begin{itemize} -\item While the ultimate goal is to implement a small compiler for the JVM - \ldots\bigskip -\end{itemize} - -Let's start with: - -\begin{itemize} -\item a web-crawler -\item an email harvester +%\begin{frame}[c] +%\frametitle{Today} +% +%\begin{itemize} +%\item While the ultimate goal is to implement a small compiler for the JVM +% \ldots\bigskip +%\end{itemize} +% +%Let's start with: +% +%\begin{itemize} +%\item a web-crawler +%\item an email harvester %\item \textcolor{gray}{(a web-scraper)} -\end{itemize} - -\end{frame} +%\end{itemize} +% +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{A Web-Crawler} - -\mbox{}\\[10mm] - -\begin{enumerate} -\item given an URL, read the corresponding webpage -\item extract all links from it -\item call the web-crawler again for all these links -\end{enumerate} - -\end{frame} +%\begin{frame}[t] +%\frametitle{A Web-Crawler} +% +%\mbox{}\\[10mm] +% +%\begin{enumerate} +%\item given an URL, read the corresponding webpage +%\item extract all links from it +%\item call the web-crawler again for all these links +%\end{enumerate} +% +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{A Web-Crawler} - -\mbox{}\\[10mm] - - -\begin{enumerate} -\item given an URL, read the corresponding webpage -\item if not possible print, out a problem -\item if possible, extract all links from it -\item call the web-crawler again for all these links -\end{enumerate}\bigskip\pause - -\small (we need a bound for the number of recursive calls) - -\small (the purpose is to check all links on my own webpage) -\end{frame} +%\begin{frame}[t] +%\frametitle{A Web-Crawler} +% +%\mbox{}\\[10mm] +% +% +%\begin{enumerate} +%\item given an URL, read the corresponding webpage +%\item if not possible print, out a problem +%\item if possible, extract all links from it +%\item call the web-crawler again for all these links +%\end{enumerate}\bigskip\pause +% +%\small (we need a bound for the number of recursive calls) +% +%\small (the purpose is to check all links on my own webpage) +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - -\begin{textblock}{1}(2,5) -\begin{tabular}{c} -\includegraphics[scale=0.15]{pics/servers.png}\\[-2mm] -\small Server -\end{tabular} -\end{textblock} - -\begin{textblock}{1}(5.6,4) - \begin{tikzpicture}[scale=1.1] - \draw[white] (0,1) node (X) {}; - \draw[white] (2,1) node (Y) {}; - \draw[white] (0,0) node (X1) {}; - \draw[white] (2,0) node (Y1) {}; - \draw[white] (0,-1) node (X2) {}; - \draw[white] (2,-1) node (Y2) {}; - \draw[red, <-, line width = 2mm] (X) -- (Y); - \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {}; - \draw[red, ->, line width = 2mm] (X1) -- (Y1); - \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X1)!.5!(Y1) $) {}; - \draw[red, <-, line width = 2mm] (X2) -- (Y2); - \node [inner sep=7pt,label=above:\textcolor{black}{POST data}] at ($ (X2)!.5!(Y2) $) {}; - \end{tikzpicture} -\end{textblock} - - -\begin{textblock}{1}(9,5.5) -\begin{tabular}{c} -\includegraphics[scale=0.15]{pics/laptop.png}\\[-2mm] -\small Browser -\end{tabular} -\end{textblock} -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +% +%\begin{textblock}{1}(2,5) +%\begin{tabular}{c} +%\includegraphics[scale=0.15]{pics/servers.png}\\[-2mm] +%\small Server +%\end{tabular} +%\end{textblock} +% +%\begin{textblock}{1}(5.6,4) +% \begin{tikzpicture}[scale=1.1] +% \draw[white] (0,1) node (X) {}; +% \draw[white] (2,1) node (Y) {}; +% \draw[white] (0,0) node (X1) {}; +% \draw[white] (2,0) node (Y1) {}; +% \draw[white] (0,-1) node (X2) {}; +% \draw[white] (2,-1) node (Y2) {}; +% \draw[red, <-, line width = 2mm] (X) -- (Y); +% \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {}; +% \draw[red, ->, line width = 2mm] (X1) -- (Y1); +% \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X1)!.5!(Y1) $) {}; +% \draw[red, <-, line width = 2mm] (X2) -- (Y2); +% \node [inner sep=7pt,label=above:\textcolor{black}{POST data}] at ($ (X2)!.5!(Y2) $) {}; +% \end{tikzpicture} +%\end{textblock} +% +% +%\begin{textblock}{1}(9,5.5) +%\begin{tabular}{c} +%\includegraphics[scale=0.15]{pics/laptop.png}\\[-2mm] +%\small Browser +%\end{tabular} +%\end{textblock} +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Scala} - -\small A simple Scala function for reading webpages: -\bigskip - -\footnotesize -\lstinputlisting{../progs/app0.scala} -\medskip\pause - -\lstinline{get_page("""https://nms.kcl.ac.uk/christian.urban/""")} -\bigskip\medskip\pause - - -\small A slightly more complicated version for handling errors: -\smallskip - -\footnotesize -\lstinputlisting[xleftmargin=-4mm]{../progs/app1.scala} - - -\end{frame} +%\begin{frame}[c] +%\frametitle{Scala} +% +%\small A simple Scala function for reading webpages: +%\bigskip +% +%\footnotesize +%\lstinputlisting{../progs/app0.scala} +%\medskip\pause +% +%\lstinline{get_page("""https://nms.kcl.ac.uk/christian.urban/""")} +%\bigskip\medskip\pause +% +% +%\small A slightly more complicated version for handling errors: +%\smallskip +% +%\footnotesize +%\lstinputlisting[xleftmargin=-4mm]{../progs/app1.scala} +% +% +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -585,39 +651,39 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - -\footnotesize -\lstinputlisting{../progs/app2.scala} - -\end{frame} +%\begin{frame}[c] +% +%\footnotesize +%\lstinputlisting{../progs/app2.scala} +% +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - -\small -A version that only crawls links in ``my'' domain:\bigskip - -\footnotesize -\lstinputlisting{../progs/app3.scala} - -\end{frame} +%\begin{frame}[c] +% +%\small +%A version that only crawls links in ``my'' domain:\bigskip +% +%\footnotesize +%\lstinputlisting{../progs/app3.scala} +% +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\lstset{xleftmargin=-4mm} -\small -A little email harvester: - -\footnotesize -\lstinputlisting{../progs/app4.scala}\bigskip - -\tiny -\url{http://net.tutsplus.com/tutorials/other/8-regular-expressions-you-should-know/} - -\end{frame} +%\begin{frame}[c] +%\lstset{xleftmargin=-4mm} +%\small +%A little email harvester: +% +%\footnotesize +%\lstinputlisting{../progs/app4.scala}\bigskip +% +%\tiny +%\url{http://net.tutsplus.com/tutorials/other/8-regular-expressions-you-should-know/} +% +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -681,7 +747,8 @@ \bl{$s_1 \,@\, s_2$} \end{center} -\bl{\textit{foo $@$ bar = foobar}, \textit{baz $@\, []$ = baz}} +\bl{\textit{foo $@$ bar = foobar}}\\ +\bl{\textit{baz $@\, []$ = baz}} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -766,6 +833,89 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{The Power Operation} + + \begin{itemize} + \item The \alert{\textbf{\boldmath$n$th Power}} of a language: + + \begin{center} + \begin{tabular}{lcl} + \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ + \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} + \end{tabular} + \end{center}\bigskip + + \item[] For example + + \begin{center} + \begin{tabular}{lcl@{\hspace{10mm}}l} + \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\ + \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\ + \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ + \end{tabular} + \end{center} + + \end{itemize} + + \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{Questions} + + \begin{itemize} + \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip + + \item[] + How many strings are in \bl{$A^4$}\,? + \bigskip\medskip\pause + + + \item[] + What if \bl{$A = \{[a],[b],[c],[]\}$};\\ + how many strings are then in \bl{$A^4$}\,? + \end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{The Star Operation} + + \begin{itemize} + \item The \alert{\bf Kleene Star} of a \underline{language}: + \bigskip + + \begin{center} + \begin{tabular}{c} + \bl{$A\star \dn \bigcup_{0\le n} A^n$} + \end{tabular} + \end{center}\bigskip + + \item[] This expands to + + \[ + \bl{A^0 \cup A^1 \cup A^2 \cup A^3 \cup A^4 \cup \ldots} + \] + + or + + \small + \[ + \bl{\{[]\} \;\cup\; A \;\cup\; A\,@\,A \;\cup\; + A\,@\,A\,@\,A \;\cup\; A\,@\,A\,@\,A\,@\,A \cup \ldots} + \] + + \end{itemize} + + \end{frame} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -799,14 +949,14 @@ \begin{column}{.5\textwidth} \underline{\bf Strand 1}\medskip \begin{itemize} -\item four programming tasks: +\item 4 programming tasks: \begin{itemize} -\item matcher (4\%, 12.10.) -\item lexer (5\%, 02.11.) -\item parser (5\%, 23.11.) -\item compiler (6\%, 14.12.) +\item matcher (4\%, 11.10.) +\item lexer (5\%, 04.11.) +\item parser (5\%, 22.11.) +\item compiler (6\%, 13.12.) \end{itemize} -\item in any lang.~you like,\\ but I want to see the code +\item in any lang.~you like,\\ but I want to see the\\ code \end{itemize} \end{column} @@ -815,7 +965,7 @@ \underline{\bf Strand 2}\smallskip\begin{itemize} \item one task: prove the correctness of a regular expression matcher in the \underline{Isabelle} theorem prover -\item 20\%, submission on~14.12.\hspace{-5mm}\mbox{} +\item 20\%, submission on~13.12.\hspace{-5mm}\mbox{} \end{itemize} \end{column} \end{columns}\medskip