% !TEX program = xelatex
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../styles/slides}
\usepackage{../styles/mygraphs}
\usepackage{../styles/langs}
%%\usepackage{../data}
%%\usepackage[export]{adjustbox}
\usetikzlibrary{shapes,arrows,shadows}
% Swift, example (a*)*b
\begin{filecontents}{re-swift.data}
5 0.001
10 0.001
15 0.009
20 0.178
23 1.399
24 2.893
25 5.671
26 11.357
27 22.430
\end{filecontents}
% Dart, example (a*)*b
\begin{filecontents}{re-dart.data}
20 0.042
21 0.084
22 0.190
23 0.340
24 0.678
25 1.369
26 2.700
27 5.462
28 10.908
29 21.725
30 43.492
\end{filecontents}
\begin{filecontents}{re3a.data}
1 0.00003
500001 0.22527
1000001 0.62752
1500001 0.88485
2000001 1.39815
2500001 1.68619
3000001 1.94957
3500001 2.15878
4000001 2.59918
4500001 5.90679
5000001 13.11295
5500001 19.15376
6000001 40.16373
\end{filecontents}
\begin{filecontents}{re-python2.data}
1 0.033
5 0.036
10 0.034
15 0.036
18 0.059
19 0.084
20 0.141
21 0.248
22 0.485
23 0.878
24 1.71
25 3.40
26 7.08
27 14.12
28 26.69
\end{filecontents}
\begin{filecontents}{re-js.data}
5 0.061
10 0.061
15 0.061
20 0.070
23 0.131
25 0.308
26 0.564
28 1.994
30 7.648
31 15.881
32 32.190
\end{filecontents}
\begin{filecontents}{re-java.data}
5 0.00298
10 0.00418
15 0.00996
16 0.01710
17 0.03492
18 0.03303
19 0.05084
20 0.10177
21 0.19960
22 0.41159
23 0.82234
24 1.70251
25 3.36112
26 6.63998
27 13.35120
28 29.81185
\end{filecontents}
\begin{filecontents}{re-java9.data}
1000 0.01410
2000 0.04882
3000 0.10609
4000 0.17456
5000 0.27530
6000 0.41116
7000 0.53741
8000 0.70261
9000 0.93981
10000 0.97419
11000 1.28697
12000 1.51387
14000 2.07079
16000 2.69846
20000 4.41823
24000 6.46077
26000 7.64373
30000 9.99446
34000 12.966885
38000 16.281621
42000 19.180228
46000 21.984721
50000 26.950203
60000 43.0327746
\end{filecontents}
\hfuzz=220pt
%\setmonofont[Scale=.88]{Consolas}
%\newfontfamily{\consolas}{Consolas}
\lstset{language=Scala,
style=mystyle,
numbersep=0pt,
numbers=none,
xleftmargin=0mm}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
% beamer stuff
\renewcommand{\slidecaption}{PEP (Scala) 05, King's College London}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[5mm]
\huge PEP Scala (5)
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
%Office: & N\liningnums{7.07} (North Wing, Bush House)\bigskip\\
Slides \& Code: & KEATS\bigskip\\
Office Hour: & Fridays 11:00 -- 12:00\\
Location: & N7.07 (North Wing, Bush House)\bigskip\\
Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\ \\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Housekeeping}
\mbox{}\medskip
\begin{minipage}{1.2\textwidth}
\begin{itemize}
\item SGTs still ongoing next week
\item LGT next week online Ask-Me-Anything (will be recorded, TEAMS link will be emailed and published on KEATS)
\item tests might break over Christmas
\end{itemize}\bigskip
\begin{center}
\raisebox{-9mm}{\includegraphics[scale=0.15]{../pics/thanks.jpeg}} Junhuai Hou \quad Chin Wan
\end{center}
\end{minipage}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Main 3: Regexes}
\begin{center}
\mbox{Graphs: regex \alert{\texttt{(a*)*b}} and strings $\underbrace{\;\texttt{a}\ldots \texttt{a}\;}_{n}$}\bigskip
\small
\begin{tabular}[t]{@{\hspace{-8mm}}c@{\hspace{-0mm}}c@{}}
\only<1>{\raisebox{6mm}{\begin{tikzpicture}
\begin{axis}[
xlabel={$n$},
x label style={at={(1.05,0.0)}},
ylabel={time in secs},
enlargelimits=false,
xtick={0,5,...,30},
xmax=33,
ymax=35,
ytick={0,5,...,30},
scaled ticks=false,
axis lines=left,
width=5.5cm,
height=5cm,
legend entries={Java 8,Python,JavaScript,Swift,Dart},
%legend entries={\small{}Python, \small{}Java 8, \small{}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};
\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
\addplot[brown,mark=*, mark options={fill=white}] table {re-dart.data};
\end{axis}
\end{tikzpicture}}}%
\only<2>{\raisebox{0mm}{\begin{tikzpicture}
\begin{axis}[
xlabel={$n$},
x label style={at={(1.05,0.0)}},
ylabel={time in secs},
%y label style={at={(0.06,0.5)}},
enlargelimits=false,
%xtick={0,30000,...,60000},
xmax=65000,
ymax=35,
ytick={0,5,...,30},
scaled ticks=true,
axis lines=left,
width=5.5cm,
height=5cm,
legend entries={\small{}Java 9},
legend pos=north west]
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data};
\end{axis}
\end{tikzpicture}}}
&
\onslide<1-2>{\begin{tikzpicture}
\begin{axis}[
xlabel={$n$},
x label style={at={(1.05,0.0)}},
ylabel={time in secs},
enlargelimits=false,
ymax=35,
ytick={0,5,...,30},
axis lines=left,
legend entries={You in M3},
%%scaled ticks=false,
width=5.5cm,
height=5cm]
%%\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data};
\addplot[magenta,mark=square*,mark options={fill=white}] table {re3a.data};
\end{axis}
\end{tikzpicture}}
\end{tabular}
\end{center}
\hfill\small\url{https://vimeo.com/112065252}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Marks for Preliminary 8}
%
%Raw marks (265 submissions):\bigskip
%
%\begin{itemize}
%\item 4\%: \hspace{4mm}211
%\item 3\%: \hspace{4mm}11
%\item 2\%: \hspace{4mm}14
%\item 1\%: \hspace{4mm}8
%\item 0\%: \hspace{4mm}21
%\end{itemize}\bigskip\bigskip
%
%\footnotesize
%(plagiarism/collusion interviews ongoing again!)
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Plan for Today}
\begin{itemize}
\item Implicits
\item Polymorphic Types
\item Immutable OOP
\item Making Fun about Scala
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c,fragile]
%\frametitle{How To calcululate 100 Mio Collatz Series?}
%
%\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=1mm]
%(1L to 100_000_000).map(collatz).max
%\end{lstlisting}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Polyorphic Types}
%To be avoided:\bigskip\bigskip
\small
\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-6mm]
def length_string_list(lst: List[String]): Int =
lst match {
case Nil => 0
case x::xs => 1 + length_string_list(xs)
}
def length_int_list(lst: List[Int]): Int =
lst match {
case Nil => 0
case x::xs => 1 + length_int_list(xs)
}
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Polyorphic Types}
\small
\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-6mm]
def length[A](lst: List[A]): Int = lst match {
case Nil => 0
case x::xs => 1 + length(xs)
}
length(List("1", "2", "3", "4"))
length(List(1, 2, 3, 4))
def map[A, B](lst: List[A], f: A => B): List[B] =
lst match {
case Nil => Nil
case x::xs => f(x)::map(xs, f)
}
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{DFAs}
\begin{center}
\begin{tikzpicture}[>=stealth',very thick,auto,
every state/.style={minimum size=0pt,inner sep=2pt,
draw=blue!50,very thick,fill=blue!20},]
\only<1,3->{\node[state,initial] (Q_0) {$\mbox{Q}_0$};}
\only<2>{\node[state,initial,fill=red] (Q_0) {$\mbox{Q}_0$};}
\only<1,2,4->{\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};}
\only<3>{\node[state,fill=red] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};}
\only<-3,5->{\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};}
\only<4>{\node[state,fill=red] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};}
\only<-4,6->{\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};}
\only<5>{\node[state,fill=red] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};}
\only<-5>{\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};}
\only<6->{\node[state, accepting,fill=red] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};}
\path[->] (Q_0) edge node [above] {\alert{$a$}} (Q_1);
\path[->] (Q_1) edge node [above] {\alert{$a$}} (Q_4);
\path[->] (Q_4) edge [loop right] node {\alert{$a, b$}} ();
\path[->] (Q_3) edge node [right] {\alert{$a$}} (Q_4);
\path[->] (Q_2) edge node [above] {\alert{$a$}} (Q_3);
\path[->] (Q_1) edge node [right] {\alert{$b$}} (Q_2);
\path[->] (Q_0) edge node [above] {\alert{$b$}} (Q_2);
\path[->] (Q_2) edge [loop left] node {\alert{$b$}} ();
\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (Q_0);
\end{tikzpicture}
\end{center}
\begin{textblock}{10}(4,12)
\LARGE{}\phantom{b}
\only<-2>{\boldmath\textcolor{gray}{$a$}}\only<3->{\boldmath\alert{$a$}}%
\only<-3>{\boldmath\textcolor{gray}{$b$}}\only<4->{\boldmath\alert{$b$}}%
\only<-4>{\boldmath\textcolor{gray}{$a$}}\only<5->{\boldmath\alert{$a$}}%
\only<-5>{\boldmath\textcolor{gray}{$a$}}\only<6->{\boldmath\alert{$a$}}%
\only<-6>{\boldmath\textcolor{gray}{$a$}}\only<7->{\boldmath\alert{$a\quad\Rightarrow \textbf{yes}$}}%
\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{DFAs}
A \alert{\bf deterministic finite automaton} (DFA) consists of
5 things:
\begin{itemize}
\item an alphabet \bl{$\varSigma$}
\item a set of states \bl{$\mbox{Qs}$}
\item one of these states is the start state \bl{$\mbox{Q}_0$}
\item some states are accepting states \bl{$F$}, and
\item there is transition function \bl{$\delta$}\bigskip
\small
which takes a state and a character as arguments and produces a
new state; this function might not be everywhere defined
\end{itemize}
\begin{center}
\bl{$A(\varSigma, \mbox{Qs}, \mbox{Q}_0, F, \delta)$}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{NFAs}
\begin{center}
\begin{tikzpicture}[>=stealth',very thick, auto,
every state/.style={minimum size=0pt,inner sep=3pt,
draw=blue!50,very thick,fill=blue!20},scale=2]
\node[state,initial] (Q_0) {$\mbox{Q}_0$};
\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
\node[state, accepting] (Q_2) [right=of Q_1] {$\mbox{Q}_2$};
\path[->] (Q_0) edge [loop above] node {\alert{$b$}} ();
\path[<-] (Q_0) edge node [below] {\alert{$b$}} (Q_1);
\path[->] (Q_0) edge [bend left] node [above] {\alert{$a$}} (Q_1);
\path[->] (Q_0) edge [bend right=45,looseness=1.3] node [below] {\alert{$a$}} (Q_2);
\path[->] (Q_1) edge [loop above] node {\alert{$a,b$}} ();
\path[->] (Q_1) edge node [above] {\alert{$a$}} (Q_2);
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Where to go on from here?}
\begin{itemize}
\item Martin Odersky (EPFL) developed now Scala 3\medskip
\item I use Ammonite by Haoji Li\medskip
\item Elm (\url{http://elm-lang.org})\ldots web applications with style\medskip
\item Haskell, Ocaml, Standard ML, Scheme, \ldots
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{\alert{Questions?}}
{\tiny
\begin{verbatim}
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
\end{verbatim}}
\begin{textblock}{6}(8.5,3.5)
\begin{bubble}[5cm]
\footnotesize
\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
++++++++[>+>++++<<-]>++>>
+<[-[>>+<<-]+>>]>+[-<<<[-
>[+[-]+>++>>>-<<]<[<]>>++
++++[<<+++++>>-]+<<++.[-]
<<]>.>+[>>]>+]
\end{lstlisting}
\end{bubble}
\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: