Mercurial Mercurial > hg > afl-material / diff
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
slides01.tex
changeset 3 df423d3b7fa1
parent 2 6e7da958ba8c
child 4 27c0abdb39d5 
--- a/slides01.tex	Wed Sep 26 02:50:44 2012 +0100
+++ b/slides01.tex	Wed Sep 26 08:07:21 2012 +0100
@@ -196,25 +196,7 @@
 \frametitle{\begin{tabular}{c}This Course\end{tabular}}
 
 \begin{itemize}
-\item regular expression / regular expression matching
-\item a bit of sets (of strings)
-\item automata
-\item the Myhill-Nerode theorem
-\item parsing
-\item grammars
-\item a small interpreter / webbrowser
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}This Course\end{tabular}}
-
-\begin{itemize}
-\item the ultimate goal is to implement a small web-browser (really small)\bigskip
+\item the ultimate goal is to implement a small web-browser (really small one)\bigskip
 \end{itemize}
 
 Let's start with:
@@ -230,9 +212,11 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
-\begin{frame}[c]
+\begin{frame}[t]
 \frametitle{\begin{tabular}{c}A Web Crawler\end{tabular}}
 
+\mbox{}\\[10mm]
+
 \begin{enumerate}
 \item given an URL, read the corresponding webpage
 \item extract all links from it
@@ -244,9 +228,12 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
-\begin{frame}[c]
+\begin{frame}[t]
 \frametitle{\begin{tabular}{c}A Web Crawler\end{tabular}}
 
+\mbox{}\\[10mm]
+
+
 \begin{enumerate}
 \item given an URL, read the corresponding webpage
 \item if not possible print, out a problem
@@ -254,7 +241,7 @@
 \item call the web-crawler again for all these links
 \end{enumerate}\bigskip\pause
 
-\small (we need to bound the number of recursive calls)
+\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}}
@@ -268,9 +255,12 @@
 \footnotesize a simple Scala function for reading webpages\\[-3mm]
 
 {\lstset{language=Scala}\fontsize{8}{10}\selectfont
-\texttt{\lstinputlisting{app0.scala}}}\pause\bigskip
+\texttt{\lstinputlisting{app0.scala}}}\pause
+{\lstset{language=Scala}\fontsize{8}{10}\selectfont
+\texttt{\lstinline{get_page("""http://www.inf.kcl.ac.uk/staff/urbanc/""")}}}\pause\bigskip
 
-\footnotesize slightly more complicated for handling errors:\\[-3mm]
+
+\footnotesize slightly more complicated for handling errors properly:\\[-3mm]
 
 \footnotesize
 {\lstset{language=Scala}\fontsize{8}{10}\selectfont
@@ -282,9 +272,43 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}A Regular Expression\end{tabular}}
+
+\begin{itemize}
+\item \ldots{} is a pattern or template for specifying strings
+\end{itemize}\bigskip
+  
+\begin{center}  
+\only<1>{{\lstset{language=Scala}\fontsize{18}{19}\selectfont\bf
+\texttt{"https?://[$\hat{\hspace{2mm}}$"]*"}}}%
+\only<2>{{\lstset{language=Scala}\fontsize{18}{19}\selectfont\bf
+\texttt{"""\textbackslash{}"https?://[$\hat{\hspace{2mm}}$\textbackslash{}"]*\textbackslash{}"""".r}}}
+\end{center}\bigskip\bigskip
+
+matches for example\\  
+\;{\lstset{language=Scala}\fontsize{12}{14}\selectfont\bf
+\texttt{"http://www.foobar.com"}}\\
+\;{\lstset{language=Scala}\fontsize{12}{14}\selectfont\bf
+\texttt{"https://www.tls.org"}}\\
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
 \begin{frame}[c]
 
-
+{\lstset{language=Scala}\fontsize{18}{19}\selectfont\bf
+\texttt{rexp.findAllIn(string)}}\medskip
+  
+returns a list of all (sub)strings that match the regular expression\bigskip\bigskip  
+  
+{\lstset{language=Scala}\fontsize{18}{19}\selectfont\bf
+\texttt{rexp.findFirstIn(string)}}\medskip
+  
+returns either {\bf\texttt{None}} if no (sub)string matches 
+or {\bf\texttt{Some(s)}} with the first (sub)string
   
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -292,146 +316,25 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Cookies\end{tabular}}
 
-
-\begin{textblock}{1}(1.5,5)
-\begin{tabular}{c}
-%\includegraphics[scale=0.15]{pics/servers.png}\\[-2mm]
-\small Servers from\\[-2mm] 
-\small Dot.com Inc.
-\end{tabular}
-\end{textblock}
-
-\begin{textblock}{1}(5.6,5.6)
-  \begin{tikzpicture}[scale=2.5]
-  \draw[white] (0,0) node (X) {};
-  \draw[white] (1,0) node (Y) {};
-  \draw[white] (0.05,-0.3) node (X1) {};
-  \draw[white] (0.95,-0.3) node (Y1) {};
-  \only<1-2>{\draw[red, <-, line width = 2mm] (X) -- (Y);
-  \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {};}
-  \only<1>{\draw[white, <-, line width = 1mm] (X1) -- (Y1);
-  \node [inner sep=2pt,label=below:\textcolor{white}{read a cookie}] at ($ (X1)!.5!(Y1) $) {};}
-  \only<2>{\draw[red, <-, line width = 1mm] (X1) -- (Y1);
-  \node [inner sep=2pt,label=below:\textcolor{black}{read a cookie}] at ($ (X1)!.5!(Y1) $) {};}
-  \only<3->{\draw[red, ->, line width = 2mm] (X) -- (Y);
-  \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X)!.5!(Y) $) {};}
-  \only<3->{\draw[red, ->, line width = 1mm] (X1) -- (Y1);
-  \node [inner sep=2pt,label=below:\textcolor{black}{write a cookie}] at ($ (X1)!.5!(Y1) $) {};}
-  \end{tikzpicture}
-\end{textblock}
+{\lstset{language=Scala}\fontsize{8}{10}\selectfont
+\texttt{\lstinputlisting{app2.scala}}}\medskip
 
+{\lstset{language=Scala}\fontsize{8}{10}\selectfont
+\texttt{crawl(some\_start\_URL, 2)}}\
 
-\begin{textblock}{1}(9.5,5.5)
-\begin{tabular}{c}
-%\includegraphics[scale=0.15]{pics/laptop.png}\\[-2mm]
-\small Client
-\end{tabular}
-\end{textblock}
-  
-\only<4->{  
-\begin{textblock}{13}(1,11)  
-\small\begin{itemize}
-\item cookies: max 4KB data\\[-2mm]
-\item cookie theft, cross-site scripting attacks\\[-2mm]
-\item session cookies, persistent cookies, HttpOnly cookies, third-party cookies, zombie cookies 
-\end{itemize}  
-\end{textblock}}
-
-\only<5>{
-\begin{textblock}{11}(1,3)
-\begin{tikzpicture}
-\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 
-{\normalsize\color{darkgray}
-\begin{minipage}{10cm}\raggedright\small
-{\bf EU Privacy Directive about Cookies:}\smallskip\\
-``In May 2011, a European Union law was passed stating that websites that leave non-essential cookies on visitors' devices have to alert the visitor and get acceptance from them. This law applies to both individuals and businesses based in the EU regardless of the nationality of their website's visitors or the location of their web host. It is not enough to simply update a website's terms and conditions or privacy policy. The deadline to comply with the new EU cookie law was 26th May 2012 and failure to do so could mean a fine of up to \pounds{}500,000.''
-\hfill\small\textcolor{gray}{$\rightarrow$BBC News}
-\end{minipage}};
-\end{tikzpicture}
-\end{textblock}}
-  
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
-\begin{frame}[t]
-\begin{itemize}
-\item While cookies are per web-page, this can be easily circumvented.
-\end{itemize}
-
-\begin{textblock}{1}(1.5,4.5)
-\begin{tabular}{c}
-%\includegraphics[scale=0.07]{pics/servers.png}\\[-2mm]
-\small Pet Store\\[-2mm] 
-\small Dot.com\\[-2mm] 
-\end{tabular}
-\end{textblock}
-  
-\begin{textblock}{1}(1.5,8)
-\begin{tabular}{c}
-%\includegraphics[scale=0.07]{pics/servers.png}\\[-2mm]
-\small Dating.com
-\end{tabular}
-\end{textblock}  
-
-\begin{textblock}{1}(10.5,7.5)
-\begin{tabular}{c}
-%\includegraphics[scale=0.07]{pics/servers.png}\\[-2mm]
-\small Evil-Ad-No\\[-2mm]
-\small Privacy.com
-\end{tabular}
-\end{textblock}  
-
-\begin{textblock}{1}(6,10.5)
-\begin{tabular}{c}
-%\includegraphics[scale=0.16]{pics/rman.png}\\[-1mm]
-\small you
-\end{tabular}
-\end{textblock}  
+\begin{frame}[c]
 
-\begin{textblock}{1}(4,5)
-  \begin{tikzpicture}[scale=1]
-  \draw[white] (0,0.5) node (X) {};
-  \draw[white] (5.7,-1) node (Y) {};
-  \draw[red, ->, line width = 0.5mm] (X) -- (Y);
-  \node [inner sep=5pt,label=above:\textcolor{black}{}] at ($ (X)!.5!(Y) $) {};
-  \end{tikzpicture}
-\end{textblock}
-
-\begin{textblock}{1}(4,7.9)
-  \begin{tikzpicture}[scale=1]
-  \draw[white] (0,0) node (X) {};
-  \draw[white] (5.7,0) node (Y) {};
-  \draw[red, ->, line width = 0.5mm] (X) -- (Y);
-  \node [inner sep=5pt,label=above:\textcolor{black}{}] at ($ (X)!.5!(Y) $) {};
-  \end{tikzpicture}
-\end{textblock}
+\footnotesize
+a version that only ``crawls'' links in my domain:
 
-\begin{textblock}{1}(3.3,9.3)
-  \begin{tikzpicture}[scale=1.2]
-  \draw[white] (0,0) node (X) {};
-  \draw[white] (1.5,-1) node (Y) {};
-  \draw[red, <->, line width = 2mm] (X) -- (Y);
-  \node [inner sep=5pt,label=above:\textcolor{black}{}] at ($ (X)!.5!(Y) $) {};
-  \draw[white] (0.9,0.3) node (X1) {};
-  \draw[white] (1.9,-1) node (Y1) {};
-  \draw[red, <->, line width = 2mm] (X1) -- (Y1);
-  \node [inner sep=5pt,label=above:\textcolor{black}{}] at ($ (X1)!.5!(Y1) $) {};
-  \end{tikzpicture}
-\end{textblock}  
-
-\begin{textblock}{1}(8.6,10.1)
-  \begin{tikzpicture}[scale=0.9]
-  \draw[white] (0,0) node (X) {};
-  \draw[white] (-2,-1) node (Y) {};
-  \draw[red, <->, line width = 0.5mm] (X) -- (Y);
-  \node [inner sep=5pt,label=above:\textcolor{black}{}] at ($ (X)!.5!(Y) $) {};
-  \end{tikzpicture}
-\end{textblock}
-
+{\lstset{language=Scala}\fontsize{8}{10}\selectfont
+\texttt{\lstinputlisting{app3.scala}}}
 
 
 \end{frame}}
@@ -440,39 +343,91 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}My First Webapp\end{tabular}}
+
+\footnotesize
+a little email ``harvester'':
+
+{\lstset{language=Scala}\fontsize{8}{10}\selectfont
+\texttt{\lstinputlisting{app4.scala}}}\bigskip
+
+\tiny
+\textcolor{gray}{\url{http://net.tutsplus.com/tutorials/other/8-regular-expressions-you-should-know/}}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+\newcommand{\bl}[1]{\textcolor{blue}{#1}}       
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}
 
-{\bf GET request:}\smallskip
-\begin{enumerate}
-\item read the cookie from client
-\item if none is present, set \texttt{visits} to \textcolor{blue}{$0$}
-\item if cookie is present, extract \texttt{visits} counter
-\item if \texttt{visits} is greater or equal \textcolor{blue}{$10$}, \\
-print a valued customer message\\
-otherwise just a normal message
-\item increase \texttt{visits} by \textcolor{blue}{$1$} and store new cookie with client
-\end{enumerate}
+\begin{textblock}{6}(2,4)
+  \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
+  \bl{r} & \bl{$::=$}  & \bl{$\varnothing$}  & null\\
+         & \bl{$\mid$} & \bl{$\epsilon$}        & empty string / ""\\
+         & \bl{$\mid$} & \bl{c}                         & character\\
+         & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$} & sequence\\
+         & \bl{$\mid$} & \bl{r$_1$ + r$_2$}  & alternative / choice\\
+         & \bl{$\mid$} & \bl{r$^*$}                   & star (zero or more)\\
+  \end{tabular}
+  \end{textblock}
+  
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}
+
+{\lstset{language=Scala}\fontsize{8}{10}\selectfont
+\texttt{\lstinputlisting{app4.scala}}}
 
   
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-
+\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-\mbox{}\\[-9mm]
-
-%{\lstset{language=Scala}\fontsize{8}{10}\selectfont
-%\texttt{\lstinputlisting{app2.scala}}}
+\frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}}
 
-\footnotesize
-\begin{itemize}
-\item cookie value encoded as hash
-\end{itemize}
+\begin{textblock}{6}(2,4)
+ \begin{tabular}{@ {}rcl}
+ \bl{$L$($\varnothing$)}  & \bl{$\dn$} & \bl{$\varnothing$}\\
+ \bl{$L$($\epsilon$)}        & \bl{$\dn$} & \bl{$\{$""$\}$}\\
+ \bl{$L$(c)}                         & \bl{$\dn$} & \bl{$\{$"c"$\}$}\\
+ \bl{$L$(r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{$L$(r$_1$) $\cup$ $L$(r$_2$)}\\
+ \bl{$L$(r$_1$ $\cdot$ r$_2$)}  & \bl{$\dn$} & \bl{$\{$ s$_1$ @ s$_2$ $|$ s$_1$ $\in$ }\\
+ \bl{$L$(r$^*$)}                   & \bl{$\dn$} \\
+  \end{tabular}
+  \end{textblock}
+  
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}This Course\end{tabular}}
+
+We will have a look at
+
+\begin{itemize}
+\item regular expression / regular expression matching
+\item a bit of sets (of strings)
+\item automata
+\item the Myhill-Nerode theorem
+\item parsing
+\item grammars
+\item a small interpreter / webbrowser
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
afl-material