# HG changeset patch # User Christian Urban # Date 1569452196 -3600 # Node ID f618dd4de24aecbdcc4eb5d2f3a553e0693838db # Parent 9b1c15c3eb6f410f512d32d76cd6cd5eb15820b6 updated diff -r 9b1c15c3eb6f -r f618dd4de24a hws/hw01.pdf Binary file hws/hw01.pdf has changed diff -r 9b1c15c3eb6f -r f618dd4de24a hws/hw01.tex --- a/hws/hw01.tex Wed Sep 25 11:24:34 2019 +0100 +++ b/hws/hw01.tex Wed Sep 25 23:56:36 2019 +0100 @@ -1,3 +1,4 @@ +% !TEX program = xelatex \documentclass{article} \usepackage{../style} diff -r 9b1c15c3eb6f -r f618dd4de24a progs/re1.scala --- a/progs/re1.scala Wed Sep 25 11:24:34 2019 +0100 +++ b/progs/re1.scala Wed Sep 25 23:56:36 2019 +0100 @@ -38,7 +38,7 @@ } // the main matcher function -def matches(r: Rexp, s: String) : Boolean = +def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) @@ -79,7 +79,7 @@ val start = System.nanoTime() for (j <- 1 to i) code val end = System.nanoTime() - "%.5f".format((end - start) / (i * 1.0e9)) + (end - start) / (i * 1.0e9) } @@ -87,14 +87,14 @@ println("Test (a?{n}) (a{n})") for (i <- 0 to 20 by 2) { - println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}") + println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f") } // test: (a*)* b println("Test (a*)* b") for (i <- 0 to 20 by 2) { - println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}") + println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") } @@ -137,5 +137,5 @@ size(ders(("ab" * 200).toList, BIG)) // 366808 for (i <- 0 to 200 by 10) { - println(s"$i: ${time_needed(2, matches(BIG, "ab" * i))}") + println(f"$i: ${time_needed(2, matcher(BIG, "ab" * i))}%.5f") } diff -r 9b1c15c3eb6f -r f618dd4de24a progs/re2.scala --- a/progs/re2.scala Wed Sep 25 11:24:34 2019 +0100 +++ b/progs/re2.scala Wed Sep 25 23:56:36 2019 +0100 @@ -41,7 +41,7 @@ case c::s => ders(s, der(c, r)) } -def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) +def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) // the optional regular expression: one or zero times @@ -59,19 +59,19 @@ val start = System.nanoTime() for (j <- 1 to i) code val end = System.nanoTime() - "%.5f".format((end - start) / (i * 1.0e9)) + (end - start) / (i * 1.0e9) } // test: (a?{n}) (a{n}) for (i <- 0 to 1000 by 100) { - println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}") + println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f") } // test: (a*)* b -for (i <- 1 to 21) { - println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}") +for (i <- 0 to 20) { + println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") } diff -r 9b1c15c3eb6f -r f618dd4de24a progs/re3.scala --- a/progs/re3.scala Wed Sep 25 11:24:34 2019 +0100 +++ b/progs/re3.scala Wed Sep 25 23:56:36 2019 +0100 @@ -63,21 +63,10 @@ case c::s => ders(s, simp(der(c, r))) } -// the derivative w.r.t. a string (iterates der) -def dersp(s: List[Char], r: Rexp) : Rexp = s match { - case Nil => r - case c::s => dersp(s, der(c, r)) -} - // the main matcher function def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) -// tests -val q = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z')) -dersp("x".toList, q) -dersp("xy".toList, q) -dersp("xyz".toList, q) // one or zero def OPT(r: Rexp) = ALT(r, ONE) @@ -99,21 +88,13 @@ //test: (a?{n}) (a{n}) -for (i <- 1 to 7001 by 1000) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i)))) -} - -for (i <- 1 to 7001 by 1000) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i)))) +for (i <- 0 to 7000 by 1000) { + println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f") } //test: (a*)* b -for (i <- 1 to 6000001 by 500000) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i)))) -} - -for (i <- 1 to 6000001 by 500000) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i)))) +for (i <- 0 to 6000000 by 500000) { + println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") } diff -r 9b1c15c3eb6f -r f618dd4de24a progs/re4.scala --- a/progs/re4.scala Wed Sep 25 11:24:34 2019 +0100 +++ b/progs/re4.scala Wed Sep 25 23:56:36 2019 +0100 @@ -33,7 +33,7 @@ else SEQ(der(c, r1), r2) case STAR(r1) => SEQ(der(c, r1), STAR(r1)) case NTIMES(r1, i) => - if (i == 0) ZERO else der(c, SEQ(r1, NTIMES(r1, i - 1))) + if (i == 0) ZERO else SEQ(der(c, r1), NTIMES(r1, i - 1)) } def simp(r: Rexp) : Rexp = r match { @@ -72,7 +72,8 @@ } // the main matcher function -def matches(r: Rexp, s: String) : Boolean = nullable(ders2(s.toList, r)) +def matcher(r: Rexp, s: String) : Boolean = + nullable(ders2(s.toList, r)) // one or zero @@ -89,19 +90,19 @@ val start = System.nanoTime() for (j <- 1 to i) code val end = System.nanoTime() - "%.5f".format((end - start) / (i * 1.0e9)) + (end - start) / (i * 1.0e9) } // test: (a?{n}) (a{n}) for (i <- 0 to 7000000 by 500000) { - println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}") + println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f") } // test: (a*)* b -for (i <- 1 to 7000001 by 500000) { - println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}") +for (i <- 0 to 7000000 by 500000) { + println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") } @@ -135,7 +136,7 @@ val EVIL3 = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))) // test: ("" | "a" | "aa")* -val EVIL3 = STAR(ALT(ONE, ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a'))))) +val EVIL4 = STAR(ALT(ONE, ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a'))))) val t1 = ders2("a".toList, EVIL3) val t1s = simp(t1) diff -r 9b1c15c3eb6f -r f618dd4de24a slides/pics/cassmbl.png Binary file slides/pics/cassmbl.png has changed diff -r 9b1c15c3eb6f -r f618dd4de24a slides/pics/csource.png Binary file slides/pics/csource.png has changed diff -r 9b1c15c3eb6f -r f618dd4de24a slides/slides01.pdf Binary file slides/slides01.pdf has changed 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