876
+ − 1
% !TEX program = xelatex
+ − 2
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
+ − 3
\usepackage{../slides}
+ − 4
\usepackage{../graphicss}
+ − 5
\usepackage{../langs}
+ − 6
\usepackage{../data}
+ − 7
\usetikzlibrary{cd}
930
+ − 8
\usepackage{listings-rust}
876
+ − 9
+ − 10
+ − 11
\usepackage{tcolorbox}
+ − 12
\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}
+ − 13
\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}
+ − 14
\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}
+ − 15
+ − 16
+ − 17
+ − 18
\hfuzz=220pt
+ − 19
+ − 20
\lstset{language=Scala,
+ − 21
style=mystyle,
+ − 22
numbersep=0pt,
+ − 23
numbers=none,
+ − 24
xleftmargin=0mm}
+ − 25
+ − 26
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
+ − 27
+ − 28
% beamer stuff
+ − 29
\renewcommand{\slidecaption}{CFL 01, King's College London}
+ − 30
+ − 31
%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect1/main.pdf
+ − 32
%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect2/main.pdf
+ − 33
%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect3/main.pdf
+ − 34
929
+ − 35
876
+ − 36
\begin{document}
+ − 37
+ − 38
%\begin{frame}[t]
+ − 39
%
+ − 40
%\begin{mybox}
+ − 41
%A physical explanation the \emph{dynamic matrix}\\
+ − 42
%lots of text
+ − 43
%\end{mybox}
+ − 44
+ − 45
+ − 46
%\begin{mybox2}{Test}
+ − 47
%A physical explanation the \emph{dynamic matrix}\\
+ − 48
%lots of text
+ − 49
%\end{mybox2}
+ − 50
+ − 51
%\begin{mybox3}{Test}
+ − 52
%A physical explanation the \emph{dynamic matrix}\\
+ − 53
%lots of text
+ − 54
%\end{mybox3}
906
+ − 55
% \end{frame}
+ − 56
+ − 57
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
922
+ − 58
%\begin{frame}[t]
+ − 59
%\frametitle{%
+ − 60
% \begin{tabular}{@ {}c@ {}}
+ − 61
% \\[-3mm]
+ − 62
% \LARGE Lunch with a Lecturer (29 March)\\[5mm]
+ − 63
% \end{tabular}}
+ − 64
%
+ − 65
% I teach CFL (compilers) and PEP (Scala)\bigskip
+ − 66
%
+ − 67
% \begin{itemize}
+ − 68
% \item did undergraduate in Germany
+ − 69
% \item Master in St Andrews
+ − 70
% \item PhD in Cambridge
+ − 71
% \end{itemize}\bigskip\bigskip
+ − 72
%
+ − 73
% use mainly the Isabelle theorem prover in my work (see 6CCS3VER)
+ − 74
%
+ − 75
% write code in functional programming languages (Scala, SML, Ocaml, Haskell)
+ − 76
%\end{frame}
906
+ − 77
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 78
922
+ − 79
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 80
% \begin{frame}[c]
+ − 81
% \frametitle{Why Bother with Regexes?}
906
+ − 82
922
+ − 83
% \begin{columns}[t,onlytextwidth]
+ − 84
% \begin{column}{1.8cm}
+ − 85
% \mbox{}
+ − 86
% \end{column}
+ − 87
% \begin{column}{.5\textwidth}
+ − 88
% \small{}Ruby, Python, Java 8\medskip\\
+ − 89
% \begin{tikzpicture}\footnotesize
+ − 90
% \begin{axis}[
+ − 91
% xlabel={$n$},
+ − 92
% x label style={at={(1.05,0.0)}},
+ − 93
% ylabel={time in secs},
+ − 94
% enlargelimits=false,
+ − 95
% xtick={0,5,...,30},
+ − 96
% xmax=33,
+ − 97
% ymax=35,
+ − 98
% ytick={0,5,...,30},
+ − 99
% scaled ticks=false,
+ − 100
% axis lines=left,
+ − 101
% width=\textwidth,
+ − 102
% height=4cm,
+ − 103
% legend entries={Python,Ruby},
+ − 104
% legend pos=north west,
+ − 105
% legend cell align=left]
+ − 106
% \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
+ − 107
% \addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data};
+ − 108
% \end{axis}
+ − 109
% \end{tikzpicture}
+ − 110
% \begin{tikzpicture}\footnotesize
+ − 111
% \begin{axis}[
+ − 112
% xlabel={$n$},
+ − 113
% x label style={at={(1.05,0.0)}},
+ − 114
% ylabel={time in secs},
+ − 115
% enlargelimits=false,
+ − 116
% xtick={0,5,...,30},
+ − 117
% xmax=33,
+ − 118
% ymax=35,
+ − 119
% ytick={0,5,...,30},
+ − 120
% scaled ticks=false,
+ − 121
% axis lines=left,
+ − 122
% width=\textwidth,
+ − 123
% height=4cm,
+ − 124
% legend entries={Python, Java 8, JavaScript, Swift},
+ − 125
% legend pos=north west,
+ − 126
% legend cell align=left]
+ − 127
% \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
+ − 128
% \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+ − 129
% \addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
+ − 130
% \addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
+ − 131
% \end{axis}
+ − 132
% \end{tikzpicture}
+ − 133
% %
+ − 134
% \end{column}
+ − 135
% \begin{column}{.5\textwidth}
+ − 136
% \small{}In PEP \& CFL \medskip\\
+ − 137
% \begin{tikzpicture}\footnotesize
+ − 138
% \begin{axis}[
+ − 139
% xlabel={$n$},
+ − 140
% x label style={at={(1.07,0.0)}},
+ − 141
% ylabel={time in secs},
+ − 142
% enlargelimits=false,
+ − 143
% xtick={0,5000,...,10000},
+ − 144
% xmax=11000,
+ − 145
% ymax=35,
+ − 146
% ytick={0,5,...,30},
+ − 147
% scaled ticks=false,
+ − 148
% axis lines=left,
+ − 149
% width=\textwidth,
+ − 150
% height=4cm]
+ − 151
% \addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
+ − 152
% \addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
+ − 153
% \end{axis}
+ − 154
% \end{tikzpicture}
+ − 155
% \begin{tikzpicture}\footnotesize
+ − 156
% \begin{axis}[
+ − 157
% xlabel={$n$},
+ − 158
% x label style={at={(1.07,0.0)}},
+ − 159
% ylabel={time in secs},
+ − 160
% enlargelimits=false,
+ − 161
% ymax=35,
+ − 162
% ytick={0,5,...,30},
+ − 163
% scaled ticks=false,
+ − 164
% axis lines=left,
+ − 165
% width=\textwidth,
+ − 166
% height=4cm]
+ − 167
% \addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
+ − 168
% \end{axis}
+ − 169
% \end{tikzpicture}
+ − 170
% \end{column}
+ − 171
% \end{columns}
+ − 172
% \medskip
906
+ − 173
922
+ − 174
% \begin{textblock}{3}(-0.1,3.3)
+ − 175
% \small\hfill\bl{\texttt{[a?]\{n\}[a]\{n\}}}:
+ − 176
% \end{textblock}
906
+ − 177
922
+ − 178
% \begin{textblock}{3}(-0.1,8.7)
+ − 179
% \small\hfill\bl{\texttt{(a*)*b}}:
+ − 180
% \end{textblock}
906
+ − 181
922
+ − 182
% \begin{textblock}{3}(0.3,13)
+ − 183
% \small{}matching with strings
+ − 184
% \bl{$\underbrace{\texttt{a}...\texttt{a}}_n$}
+ − 185
% \end{textblock}
906
+ − 186
922
+ − 187
% \end{frame}
+ − 188
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
906
+ − 189
+ − 190
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
922
+ − 191
% \begin{frame}[c,fragile]
+ − 192
% \frametitle{Incidents}
906
+ − 193
922
+ − 194
% \begin{itemize}
+ − 195
% \item a global outage on 2 July 2019 at \textbf{Cloudflare}
+ − 196
% (first one for six years)\medskip
906
+ − 197
922
+ − 198
% \begin{center}\small\color{blue}
+ − 199
% \begin{verbatim}
+ − 200
% (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|
+ − 201
% null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s
+ − 202
% |-|~|!|{}|\|\||\+)*.*(?:.*=.*)))
+ − 203
% \end{verbatim}
+ − 204
% \end{center}\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
906
+ − 205
922
+ − 206
% \item on 20 July 2016 the \textbf{Stack Exchange} webpage went down
+ − 207
% because of an evil regular expression
+ − 208
% \here{https://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}
+ − 209
% \end{itemize}
906
+ − 210
922
+ − 211
% \begin{textblock}{6}(6,7.6)
+ − 212
% \includegraphics[scale=0.14]{../pics/cloudflare.png}\\
+ − 213
% \footnotesize
+ − 214
% It serves more web traffic than Twitter, Amazon, Apple,
+ − 215
% Instagram, Bing \& Wikipedia combined.
+ − 216
% \here{https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/}
+ − 217
% \end{textblock}
906
+ − 218
922
+ − 219
% \end{frame}
+ − 220
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
906
+ − 221
922
+ − 222
% %\begin{frame}[c]
+ − 223
% %
+ − 224
% %\frametitle{}
+ − 225
% %\begin{mybox3}{}\it
+ − 226
% ``This conversation is interesting to me, and I've researched it a little bit... I also disagree with Dr. Urban on the cost/benefit of non-GC languages...[..]\\
+ − 227
%
+ − 228
% But regardless, Scala is a lot slower than, say, C or Rust. To say it's not is basically wrong (imo)....[..]
+ − 229
% ''\\
+ − 230
%\mbox{}\hfill-- Oliver Iliffe, discussion this year in PEP
+ − 231
%\end{mybox3}\pause
+ − 232
%
+ − 233
%\end{frame}
906
+ − 234
922
+ − 235
%\begin{frame}<1-10>
+ − 236
%\end{frame}
876
+ − 237
+ − 238
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 239
\begin{frame}[t]
+ − 240
\frametitle{%
+ − 241
\begin{tabular}{@ {}c@ {}}
+ − 242
\\[-3mm]
+ − 243
\LARGE Compilers and \\[-1mm]
880
+ − 244
\LARGE Formal Languages\\[-5mm]
876
+ − 245
\end{tabular}}
+ − 246
880
+ − 247
%\begin{center}
876
+ − 248
%\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm}
+ − 249
%\includegraphics[scale=0.31]{pics/ante2.jpg}\\
+ − 250
%\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)}
880
+ − 251
%\end{center}
876
+ − 252
+ − 253
\normalsize
+ − 254
\begin{center}
+ − 255
\begin{tabular}{ll}
+ − 256
Email: & christian.urban at kcl.ac.uk\\
930
+ − 257
Office Hour: & Thurdays 15 -- 16\\
880
+ − 258
Location: & N7.07 (North Wing, Bush House)\\
876
+ − 259
Slides \& Progs: & KEATS\\
880
+ − 260
Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\
876
+ − 261
\end{tabular}
+ − 262
\end{center}
+ − 263
+ − 264
\begin{center}
+ − 265
\begin{tikzpicture}
+ − 266
\node[drop shadow,fill=white,inner sep=0pt]
+ − 267
{\footnotesize\rowcolors{1}{capri!10}{white}
+ − 268
\begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
+ − 269
\cellcolor{blue!50}
+ − 270
1 Introduction, Languages & 6 While-Language \\
+ − 271
2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
+ − 272
3 Automata, Regular Languages & 8 Compiling Functional Languages \\
+ − 273
4 Lexing, Tokenising & 9 Optimisations \\
+ − 274
5 Grammars, Parsing & 10 LLVM \\ \hline
+ − 275
\end{tabular}%
+ − 276
};
+ − 277
\end{tikzpicture}
+ − 278
\end{center}
+ − 279
+ − 280
\end{frame}
+ − 281
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 282
+ − 283
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 284
\begin{frame}<1-12>[c]
+ − 285
\frametitle{The Goal of this Module\ldots}
+ − 286
+ − 287
\begin{center}
+ − 288
\begin{tikzpicture}[scale=1,
+ − 289
node/.style={
+ − 290
rectangle,rounded corners=3mm,
+ − 291
very thick,draw=black!50,minimum height=18mm, minimum width=20mm,
+ − 292
top color=white,bottom color=black!20,drop shadow}]
+ − 293
+ − 294
\node at (3.05, 1.8) {\Large\bf \ldots{} you write a compiler};
+ − 295
+ − 296
\node (0) at (-2.3,0) {};
+ − 297
\node [above=5mm of 0]
+ − 298
{\makebox[0mm]{\footnotesize
+ − 299
\begin{tabular}{@{}l@{}}input\\[-1mm]program\end{tabular}}};
+ − 300
+ − 301
\node (A) at (0,0) [node] {};
+ − 302
\node [below right] at (A.north west) {lexer};
+ − 303
+ − 304
\node (B) at (3,0) [node] {};
+ − 305
\node [below right=1mm] at (B.north west) {\mbox{}\hspace{-1mm}parser};
+ − 306
+ − 307
\node (C) at (6,0) [node] {};
+ − 308
\node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen};
+ − 309
+ − 310
\node (1) at (8.4,0) {};
+ − 311
\node [above=5mm of 1]
+ − 312
{\makebox[0mm]{\footnotesize
+ − 313
\begin{tabular}{@{}r@{}}binary\\[-1mm]code\end{tabular}}};
+ − 314
929
+ − 315
\draw [->,line width=3mm] (0) -- (A);
+ − 316
\draw [->,line width=3mm] (A) -- (B);
+ − 317
\draw [->,line width=3mm] (B) -- (C);
+ − 318
\draw [->,line width=3mm] (C) -- (1);
876
+ − 319
\end{tikzpicture}
+ − 320
\end{center}
+ − 321
+ − 322
\only<2,3,4>{
+ − 323
\begin{textblock}{1}(1,2.1)
+ − 324
\begin{bubble}[9.8cm]
+ − 325
\normalsize
+ − 326
lexer input: a string\smallskip\\
+ − 327
\hspace{5mm}\code{"read(n);"}\medskip\\
+ − 328
lexer output: a sequence of tokens\smallskip\\
+ − 329
\hspace{5mm}\code{key(read) lpar id(n) rpar semi}
+ − 330
\end{bubble}
+ − 331
\end{textblock}}
+ − 332
+ − 333
\only<3,4>{
+ − 334
\begin{textblock}{1}(6,7.8)
+ − 335
\begin{tabular}{c}
+ − 336
\includegraphics[scale=0.2]{../pics/rosetta.jpg}\\[-2mm]
+ − 337
\footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta)
+ − 338
\end{tabular}
+ − 339
\end{textblock}}
+ − 340
+ − 341
\only<4>{
+ − 342
\begin{textblock}{1}(0.5,12)\small
+ − 343
\begin{tabular}{l@{}c@{}l}
+ − 344
\pcode{if} & $\;\Rightarrow\;$ & keyword\\
+ − 345
\pcode{iffoo} & $\;\Rightarrow\;$ & identifier\\
+ − 346
\end{tabular}
+ − 347
\end{textblock}}
+ − 348
+ − 349
\only<6>{
+ − 350
\begin{textblock}{1}(1,1.5)
+ − 351
\begin{bubble}[8.5cm]
+ − 352
\normalsize
+ − 353
parser input: a sequence of tokens\smallskip\\
+ − 354
+ − 355
{\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\
+ − 356
+ − 357
parser output: an abstract syntax tree\smallskip\\
+ − 358
\footnotesize
+ − 359
\hspace{2cm}\begin{tikzpicture}
+ − 360
\node {\code{read}}
+ − 361
child {node {\code{lpar}}}
+ − 362
child {node {\code{n}}}
+ − 363
child {node {\code{rpar}}};
+ − 364
\end{tikzpicture}
+ − 365
\end{bubble}
+ − 366
\end{textblock}}
+ − 367
+ − 368
\only<8,9>{
+ − 369
\begin{textblock}{1}(1,1.5)
+ − 370
\begin{bubble}[4cm]
+ − 371
\normalsize
+ − 372
code generation:\smallskip\\
+ − 373
\hspace{5mm}\code{istore 2}\\
+ − 374
\hspace{5mm}\code{iload 2}\\
+ − 375
\hspace{5mm}\code{ldc 10}\\
+ − 376
\hspace{5mm}\code{isub}\\
+ − 377
\hspace{5mm}\code{ifeq Label2}\\
+ − 378
\hspace{5mm}\code{iload 2}\\
+ − 379
\hspace{5mm}\code{...}\\
+ − 380
\end{bubble}
+ − 381
\end{textblock}}
+ − 382
+ − 383
\only<9>{
+ − 384
\begin{textblock}{6}(8.4,7)
+ − 385
\begin{bubble}[5cm]
+ − 386
\mbox{\begin{tikzpicture}[scale=0.58,rounded corners=0mm]
+ − 387
\begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs,
+ − 388
xlabel=n,
+ − 389
enlargelimits=0.05,
+ − 390
ybar interval=0.7, legend style=small]
+ − 391
\addplot file {interpreted2.data};
+ − 392
\addplot file {compiled2.data};
+ − 393
%\legend{interpreted, compiled}
+ − 394
\end{axis}
+ − 395
\end{tikzpicture}}
+ − 396
\end{bubble}
+ − 397
\end{textblock}}
+ − 398
+ − 399
\only<10>{
+ − 400
\begin{textblock}{6}(1,3)
+ − 401
\begin{bubble}[11cm]
+ − 402
Compiler explorers, e.g.: \url{https://gcc.godbolt.org} \;\video{https://youtu.be/ysaBmhMEyUg}
+ − 403
\begin{tikzpicture}[]
+ − 404
\node (0) at (-2.3,0) {\includegraphics[scale=0.3]{pics/csource.png}};
+ − 405
\node (1) [right=35mm] at (0) {\includegraphics[scale=0.3]{pics/cassmbl.png}};
+ − 406
\draw [->,line width=4mm, red] (0) -- (1);
+ − 407
\node (2) [below=20mm] at (0) {\LARGE\bf source};
+ − 408
\node (3) [right=40mm] at (2) {\LARGE\bf binary};
+ − 409
\draw [->,line width=1mm] (2) -- (3);
+ − 410
\end{tikzpicture}
+ − 411
\end{bubble}
+ − 412
+ − 413
\end{textblock}}
+ − 414
\only<11>{
+ − 415
\begin{textblock}{6}(1,3)
+ − 416
\begin{bubble}[11cm]
+ − 417
Compiler explorer for Java: \url{https://javap.yawk.at}
+ − 418
\begin{tikzpicture}[]
+ − 419
\node (0) at (-2.3,0) {\includegraphics[scale=0.4]{pics/jsource.png}};
+ − 420
\node (1) [right=35mm] at (0) {\includegraphics[scale=0.4]{pics/jassmbl.png}};
+ − 421
\draw [->,line width=4mm, red] (0) -- (1);
+ − 422
\node (2) [below=20mm] at (0) {\LARGE\bf source};
+ − 423
\node (3) [right=40mm] at (2) {\LARGE\bf byte code};
+ − 424
\draw [->,line width=1mm] (2) -- (3);
+ − 425
\end{tikzpicture}
+ − 426
\end{bubble}
+ − 427
\end{textblock}}
+ − 428
+ − 429
+ − 430
\end{frame}
+ − 431
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 432
+ − 433
+ − 434
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 435
\begin{frame}[t]
+ − 436
\frametitle{Why Study Compilers?}
+ − 437
+ − 438
+ − 439
John Regehr {\small(Univ.~Utah, LLVM compiler hacker)}
+ − 440
\here{https://blog.regehr.org/archives/1419}
+ − 441
\smallskip\\
+ − 442
+ − 443
\begin{bubble}[10.5cm]
+ − 444
\bf ``\ldots{}It’s effectively a perpetual
+ − 445
employment act for solid compiler hackers.''
+ − 446
\end{bubble}
+ − 447
+ − 448
\onslide<1->{
+ − 449
\only<2>{
+ − 450
\begin{itemize}
+ − 451
\item {\bf Hardware is getting weirder
+ − 452
rather than getting clocked faster.}
+ − 453
+ − 454
\begin{itemize}
+ − 455
\item[] ``Almost all processors are multicores nowadays and it looks
+ − 456
like there is increasing asymmetry in resources across cores.
+ − 457
Processors come with vector units, crypto accelerators etc. We have
+ − 458
DSPs, GPUs, ARM big.little, and Xeon Phi. This is only scratching the
+ − 459
surface.''
+ − 460
\end{itemize}
+ − 461
\end{itemize}}
+ − 462
\only<3>{
+ − 463
\begin{itemize}
+ − 464
\item {\bf We’re getting tired of low-level languages and
+ − 465
their associated security disasters.}
+ − 466
+ − 467
\begin{itemize}
+ − 468
\item [] ``We want to write new code, to whatever extent possible, in
+ − 469
safer, higher-level languages. Compilers are caught right in the
+ − 470
middle of these opposing trends: one of their main jobs is to help
+ − 471
bridge the large and growing gap between increasingly high-level
+ − 472
languages and increasingly wacky platforms.''
+ − 473
\end{itemize}
+ − 474
\end{itemize}}}
+ − 475
+ − 476
\end{frame}
+ − 477
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 478
879
+ − 479
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
930
+ − 480
% {
+ − 481
% \setbeamercolor{background canvas}{bg=cream}
+ − 482
% \begin{frame}[c]
879
+ − 483
930
+ − 484
% \frametitle{}
+ − 485
% \begin{mybox3}{}\it
+ − 486
% ``I enjoyed the module - it was genuinely the stand out academic
+ − 487
% experience of my undergraduate degree, and very much influenced my
+ − 488
% career interests. In fact I am currently working at ARM, in their Open
+ − 489
% Source Software group, on AArch64 specific optimisations for the
+ − 490
% Java/Kotlin compiler that forms part of the Android Runtime.''\\
+ − 491
% \mbox{}\hfill-- Hari Limaye in year 2021/22
+ − 492
% \end{mybox3}\pause
879
+ − 493
+ − 494
930
+ − 495
% Student numbers in CFL\medskip\\
+ − 496
% \begin{tabular}{ll}
+ − 497
% 2019: & 32\\
+ − 498
% 2020: & 59\\
+ − 499
% 2021: & 109\\
+ − 500
% 2022: & 121\\
+ − 501
% \end{tabular}
879
+ − 502
930
+ − 503
% \end{frame}
+ − 504
% }
879
+ − 505
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 506
+ − 507
+ − 508
876
+ − 509
+ − 510
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 511
\begin{frame}[c]
+ − 512
\frametitle{Why Bother with Compilers?}
+ − 513
+ − 514
\textbf{Boeing 777's}: First flight in 1994. They want to achieve
+ − 515
triple redundancy for potential hardware faults.
+ − 516
\here{http://www.citemaster.net/get/db3a81c6-548e-11e5-9d2e-00163e009cc7/R8.pdf}\bigskip
+ − 517
+ − 518
They compile 1 Ada program to\medskip
+ − 519
+ − 520
\begin{itemize}
+ − 521
\item Intel 80486
+ − 522
\item Motorola 68040 (old Macintosh's)
+ − 523
\item AMD 29050 (RISC chips used often in laser printers)
+ − 524
\end{itemize}\medskip\medskip
+ − 525
+ − 526
using 3 independent compilers.\bigskip\pause
+ − 527
+ − 528
\small Airbus uses C and static analysers. Recently started using CompCert.
+ − 529
+ − 530
\only<1->{%
+ − 531
\begin{textblock}{6}(8,4.5)
+ − 532
\includegraphics[scale=0.28]{../pics/777.png}
+ − 533
\end{textblock}}
+ − 534
+ − 535
\end{frame}
+ − 536
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 537
+ − 538
+ − 539
+ − 540
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 541
\begin{frame}[c]
+ − 542
\frametitle{What Do Compilers Do?}
+ − 543
+ − 544
Remember BF*** from PEP?
+ − 545
+ − 546
\begin{center}
+ − 547
\begin{tabular}{rcl}
+ − 548
\bl{\texttt{>}} & $\Rightarrow$ & move one cell right\\
+ − 549
\bl{\texttt{<}} & $\Rightarrow$ & move one cell left\\
+ − 550
\bl{\texttt{+}} & $\Rightarrow$ & increase cell by one\\
+ − 551
\bl{\texttt{-}} & $\Rightarrow$ & decrease cell by one\\
+ − 552
\bl{\texttt{.}} & $\Rightarrow$ & print current cell\\
+ − 553
\bl{\texttt{,}} & $\Rightarrow$ & input current cell\\
+ − 554
\bl{\texttt{[}} & $\Rightarrow$ & loop begin\\
+ − 555
\bl{\texttt{]}} & $\Rightarrow$ & loop end\medskip\\
+ − 556
& $\Rightarrow$ & everything else is a comment\\
+ − 557
\end{tabular}
+ − 558
\end{center}
+ − 559
+ − 560
\end{frame}
+ − 561
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 562
+ − 563
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 564
\begin{frame}[c]
+ − 565
\frametitle{A ``Compiler'' for BF*** to C}
+ − 566
+ − 567
\begin{center}
+ − 568
\begin{tabular}{rcl}
+ − 569
\bl{\texttt{>}} & $\Rightarrow$ & \texttt{ptr++}\\
+ − 570
\bl{\texttt{<}} & $\Rightarrow$ & \texttt{ptr--}\\
+ − 571
\bl{\texttt{+}} & $\Rightarrow$ & \texttt{(*ptr)++}\\
+ − 572
\bl{\texttt{-}} & $\Rightarrow$ & \texttt{(*ptr)--}\\
+ − 573
\bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\
+ − 574
\bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\
+ − 575
\bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\
+ − 576
\bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\
+ − 577
& $\Rightarrow$ & ignore everything else\\
+ − 578
\end{tabular}
+ − 579
\end{center}\bigskip
+ − 580
+ − 581
\texttt{char field[30000]\\ char *ptr = \&field[15000]}
+ − 582
+ − 583
\end{frame}
+ − 584
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 585
+ − 586
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 587
\begin{frame}[c]
+ − 588
\frametitle{Another~``Compiler''~for~BF~to~C}
+ − 589
+ − 590
\begin{center}
+ − 591
\begin{tabular}{rcl}
+ − 592
\bl{\texttt{>\ldots>}} & $\Rightarrow$ & \texttt{ptr += n}\\
+ − 593
\bl{\texttt{<\ldots<}} & $\Rightarrow$ & \texttt{ptr -= n}\\
+ − 594
\bl{\texttt{+\ldots+}} & $\Rightarrow$ & \texttt{(*ptr) += n}\\
+ − 595
\bl{\texttt{-\ldots-}} & $\Rightarrow$ & \texttt{(*ptr) -= n}\\
+ − 596
\bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\
+ − 597
\bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\
+ − 598
\bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\
+ − 599
\bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\
+ − 600
& $\Rightarrow$ & ignore everything else\\
+ − 601
\end{tabular}
+ − 602
\end{center}\bigskip
+ − 603
+ − 604
\texttt{char field[30000]\\ char *ptr = \&field[15000]}
+ − 605
+ − 606
\end{frame}
+ − 607
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 608
+ − 609
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 610
\begin{frame}[t]
+ − 611
\frametitle{A Brief Compiler History}
+ − 612
+ − 613
\bigskip
+ − 614
\begin{itemize}
+ − 615
\item Turing Machines, 1936 (a tape as memory)
+ − 616
\item Regular Expressions, 1956\\
+ − 617
\item The first compiler for COBOL, 1957\\ (Grace Hopper)\medskip
+ − 618
\item But surprisingly research papers are still published nowadays\\
+ − 619
\item ``Parsing: The Solved Problem That Isn't''
+ − 620
\here{https://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt.html}
+ − 621
\end{itemize}
+ − 622
+ − 623
+ − 624
\begin{textblock}{8.5}(5,7.6)
+ − 625
\begin{flushright}
+ − 626
\includegraphics[scale=0.3]{pics/hopper.jpg}\\
+ − 627
\footnotesize\textcolor{gray}{Grace Hopper}\smallskip\\
+ − 628
+ − 629
{\small\textcolor{gray}{(she made it to David Letterman's Tonight Show
+ − 630
\here{https://youtu.be/3N_ywhx6_K0?t=31})}}
+ − 631
\end{flushright}
+ − 632
\end{textblock}
+ − 633
+ − 634
\end{frame}
+ − 635
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 636
+ − 637
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 638
\begin{frame}[c]
+ − 639
\frametitle{Some Housekeeping}
+ − 640
930
+ − 641
\textbf{Exam will be computer-based, invigilated in some big examination hall:}\bigskip
876
+ − 642
+ − 643
\begin{itemize}
+ − 644
\item final exam in January (35\%)
+ − 645
\item five CWs (65\%)
+ − 646
\end{itemize}\bigskip\bigskip\pause
+ − 647
+ − 648
+ − 649
\textbf{Weekly Homework (optional):}
+ − 650
\begin{itemize}
+ − 651
\item uploaded on KEATS, send answers via email, (try to!) respond individually
+ − 652
\item \alert{\bf all} questions in the exam will be from the HWs!!
+ − 653
\end{itemize}
+ − 654
+ − 655
\end{frame}
+ − 656
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 657
879
+ − 658
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
930
+ − 659
{\definecolor{rred}{HTML}{C0504D}
+ − 660
\setbeamercolor{background canvas}{bg=cream}
+ − 661
\begin{frame}[c]
+ − 662
\frametitle{Students in CFL}
+ − 663
+ − 664
\begin{center}
+ − 665
\begin{tikzpicture}
+ − 666
\begin{axis}[symbolic x coords={2016,2017,2018,2019,2020,2021,2022,2023},
+ − 667
width = \textwidth,
+ − 668
height = 5cm,
+ − 669
bar width=8mm,
+ − 670
nodes near coords,
+ − 671
axis lines = left,
+ − 672
text=black,
+ − 673
ymin=0,
+ − 674
clip=false,
+ − 675
hide y axis,
+ − 676
axis line style={-},
+ − 677
name=mygraph
+ − 678
]
+ − 679
+ − 680
\addplot[ybar,style={rred,fill=rred!75,mark=none},text=black] coordinates {
+ − 681
(2023,183)
+ − 682
(2022,112)
+ − 683
(2021,98)
+ − 684
(2020,59)
+ − 685
(2019,38)
+ − 686
(2018,20)
+ − 687
(2017,22)
+ − 688
(2016,8)};
+ − 689
\end{axis}
+ − 690
\node[anchor=north, yshift=-10mm] at (mygraph.south) {\small{}Student numbers since the start of the compiler module.};
+ − 691
+ − 692
\end{tikzpicture}
+ − 693
\end{center}
+ − 694
+ − 695
+ − 696
\end{frame}
+ − 697
}
+ − 698
+ − 699
+ − 700
+ − 701
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
879
+ − 702
{
+ − 703
\setbeamercolor{background canvas}{bg=cream}
+ − 704
\begin{frame}[c]
+ − 705
\frametitle{Homework}
+ − 706
930
+ − 707
Until 2 years ago: I did not give out solutions; students
+ − 708
sent emails to me and I responded to them individually.\bigskip\\
879
+ − 709
+ − 710
922
+ − 711
Since last year: We will review the homework mainly during the SGTs.\bigskip\\\pause
879
+ − 712
+ − 713
I will still choose the questions from the HW for the exam, but there might be
+ − 714
some larger amount of deviation.
+ − 715
+ − 716
\end{frame}
+ − 717
}
+ − 718
876
+ − 719
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 720
\begin{frame}[c]
+ − 721
\frametitle{Some Housekeeping}
+ − 722
+ − 723
\textbf{Coursework (5 accounting for 65\%):}\bigskip
+ − 724
+ − 725
\begin{itemize}
+ − 726
\item matcher (5\%)
+ − 727
\item lexer (10\%)
+ − 728
\item parser / interpreter (10\%)
+ − 729
\item JVM compiler (15\%)
+ − 730
\item LLVM compiler (25\%)
+ − 731
\end{itemize}\bigskip\pause
+ − 732
930
+ − 733
you can use \alert{any} programming language you like (Haskell, Rust, Swift)\\\pause
876
+ − 734
you can use any code I show you and is uploaded to KEATS\ldots\textbf{BUT NOTHING ELSE!}
+ − 735
+ − 736
\end{frame}
+ − 737
930
+ − 738
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 739
{
+ − 740
\setbeamercolor{background canvas}{bg=cream}
+ − 741
\begin{frame}[c,fragile]
+ − 742
\frametitle{Ammonite \& Scala 3}
+ − 743
+ − 744
I will show you all my code in Amm / Scala 3
+ − 745
+ − 746
\begin{minipage}{1.4\textwidth}
+ − 747
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
+ − 748
$ amm
+ − 749
Loading...
+ − 750
Welcome to the Ammonite Repl 2.5.9 (Scala 3.2.2 Java 17.0.7)
+ − 751
scala> 1 + 2
+ − 752
res0: Int = 3
+ − 753
\end{lstlisting} %% $
+ − 754
\end{minipage}\medskip
+ − 755
\pause
+ − 756
+ − 757
Do not use Amm + Scala 2!
+ − 758
+ − 759
\begin{minipage}{1.4\textwidth}
+ − 760
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
+ − 761
$ amm2
+ − 762
Loading...
+ − 763
Welcome to the Ammonite Repl 2.5.9 (Scala 2.13.11 Java 17.0.7)
+ − 764
scala>
+ − 765
\end{lstlisting} %% $
+ − 766
\end{minipage}
+ − 767
\end{frame}
+ − 768
}
+ − 769
+ − 770
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 771
{
+ − 772
\setbeamercolor{background canvas}{bg=cream}
+ − 773
\begin{frame}[c]
+ − 774
\frametitle{For problems}
+ − 775
+ − 776
\begin{itemize}
+ − 777
\item Harry Dilnot
+ − 778
\item Meilai
+ − 779
\end{itemize}
+ − 780
+ − 781
\end{frame}
+ − 782
}
+ − 783
+ − 784
876
+ − 785
+ − 786
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 787
\begin{frame}[c]
+ − 788
\frametitle{Lectures 1 - 5}
+ − 789
+ − 790
transforming strings into structured data\\[10mm]
+ − 791
+ − 792
{\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\
+ − 793
\hspace{5mm}(recognising ``words'')\\[6mm]
+ − 794
+ − 795
{\LARGE\bf Parsing}\medskip\\
+ − 796
\hspace{5mm}(recognising ``sentences'')
+ − 797
+ − 798
\begin{textblock}{1}(10,9.1)
+ − 799
\begin{tabular}{c}
+ − 800
\includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm]
+ − 801
\footnotesize Stone of Rosetta
+ − 802
\end{tabular}
+ − 803
\end{textblock}
+ − 804
+ − 805
\end{frame}
+ − 806
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 807
+ − 808
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 809
\begin{frame}[c]
+ − 810
\frametitle{Lectures 1 - 5}
+ − 811
+ − 812
transforming strings into structured data\\[10mm]
+ − 813
+ − 814
{\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\
+ − 815
\hspace{5mm}(recognising ``words'')\\[6mm]
+ − 816
+ − 817
{\LARGE\bf Parsing}\medskip\\
+ − 818
\hspace{5mm}(recognising ``sentences'')
+ − 819
+ − 820
\begin{textblock}{1}(10,9.1)
+ − 821
\begin{tabular}{c}
+ − 822
\includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm]
+ − 823
\footnotesize Stone of Rosetta
+ − 824
\end{tabular}
+ − 825
\end{textblock}
+ − 826
+ − 827
\end{frame}
+ − 828
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 829
+ − 830
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 831
\begin{frame}[c]
+ − 832
\frametitle{Lectures 5 - 10}
+ − 833
+ − 834
code generation for a small imperative and a small functional language\\[10mm]
+ − 835
+ − 836
{\LARGE\bf Interpreters}\medskip\\
+ − 837
\hspace{5mm}(directly runs a program)\\[6mm]
+ − 838
+ − 839
{\LARGE\bf Compilers}\medskip\\
+ − 840
\hspace{5mm}(generate JVM code and LLVM-IR code)
+ − 841
+ − 842
\begin{textblock}{1}(8.8,8.1)
+ − 843
\begin{tabular}{c@{}c}
+ − 844
\includegraphics[scale=0.4]{../pics/javaduke.png} &
+ − 845
\includegraphics[scale=0.23]{../pics/llvmlogo.png}
+ − 846
\end{tabular}
+ − 847
\end{textblock}
+ − 848
+ − 849
\end{frame}
+ − 850
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 851
+ − 852
+ − 853
+ − 854
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 855
\begin{frame}[t]
+ − 856
\frametitle{Familiar Regular Expresssions}
+ − 857
\small
+ − 858
\begin{center}
+ − 859
\texttt{[a-z0-9\_$\backslash{}$.-]+ @ [a-z0-9$\backslash{}$.-]+ . [a-z$\backslash{}$.]\{2,6\}}
+ − 860
\end{center}\smallskip
+ − 861
+ − 862
\begin{center}
+ − 863
\begin{tabular}{@{}lp{8.5cm}@{}}
+ − 864
\pcode{re*} & matches 0 or more times\\
+ − 865
\pcode{re+} & matches 1 or more times\\
+ − 866
\pcode{re?} & matches 0 or 1 times\\
+ − 867
\pcode{re\{n\}} & matches exactly \pcode{n} number of times\\
+ − 868
\pcode{re\{n,m\}} & matches at least \pcode{n} and at most {\tt m} times\\
+ − 869
\pcode{[...]} & matches any single character inside the brackets\\
+ − 870
\pcode{[^...]} & matches any single character not inside the
+ − 871
brackets\\
+ − 872
\pcode{a-z A-Z} & character ranges\\
+ − 873
\pcode{\\d} & matches digits; equivalent to \pcode{[0-9]}\\
+ − 874
\pcode{.} & matches every character except newline\\
+ − 875
\pcode{(re)} & groups regular expressions and remembers
+ − 876
the matched text
+ − 877
\end{tabular}
+ − 878
\end{center}
+ − 879
+ − 880
\end{frame}
+ − 881
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
879
+ − 882
{
+ − 883
\setbeamercolor{background canvas}{bg=cream}
+ − 884
\begin{frame}[t]
+ − 885
\frametitle{Notation for REs}
+ − 886
+ − 887
+ − 888
+ − 889
+ − 890
\end{frame}
+ − 891
}
876
+ − 892
+ − 893
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 894
\begin{frame}[c]
+ − 895
\frametitle{Some ``innocent'' examples}
+ − 896
+ − 897
Let's try two examples
+ − 898
+ − 899
\begin{center}
+ − 900
\bl{\texttt{(a*)*b}}
+ − 901
\hspace{2cm}
+ − 902
\bl{\texttt{[a?]\{n\}[a]\{n\}}}
+ − 903
\end{center}\bigskip\pause
+ − 904
+ − 905
and match them with strings of the form
+ − 906
+ − 907
\begin{center}
+ − 908
\bl{\texttt{a}},
+ − 909
\bl{\texttt{aa}},
+ − 910
\bl{\texttt{aaa}},
+ − 911
\bl{\texttt{aaaa}},
+ − 912
\bl{\texttt{aaaaa}},
+ − 913
\bl{$\underbrace{\texttt{a}...\texttt{a}}_n$}
+ − 914
\end{center}
+ − 915
+ − 916
\end{frame}
+ − 917
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 918
+ − 919
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 920
\begin{frame}[c]
+ − 921
\frametitle{Why Bother with Regexes?}
+ − 922
+ − 923
\begin{columns}[t,onlytextwidth]
+ − 924
\begin{column}{1.8cm}
+ − 925
\mbox{}
+ − 926
\end{column}
+ − 927
\begin{column}{.5\textwidth}
+ − 928
\small{}Ruby, Python, Java 8\medskip\\
+ − 929
\begin{tikzpicture}\footnotesize
+ − 930
\begin{axis}[
+ − 931
xlabel={$n$},
+ − 932
x label style={at={(1.05,0.0)}},
+ − 933
ylabel={time in secs},
+ − 934
enlargelimits=false,
+ − 935
xtick={0,5,...,30},
+ − 936
xmax=33,
+ − 937
ymax=35,
+ − 938
ytick={0,5,...,30},
+ − 939
scaled ticks=false,
+ − 940
axis lines=left,
+ − 941
width=\textwidth,
+ − 942
height=4cm,
+ − 943
legend entries={Python,Ruby},
+ − 944
legend pos=north west,
+ − 945
legend cell align=left]
+ − 946
\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
+ − 947
\addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data};
+ − 948
\end{axis}
+ − 949
\end{tikzpicture}
+ − 950
\begin{tikzpicture}\footnotesize
+ − 951
\begin{axis}[
+ − 952
xlabel={$n$},
+ − 953
x label style={at={(1.05,0.0)}},
+ − 954
ylabel={time in secs},
+ − 955
enlargelimits=false,
+ − 956
xtick={0,5,...,30},
+ − 957
xmax=33,
+ − 958
ymax=35,
+ − 959
ytick={0,5,...,30},
+ − 960
scaled ticks=false,
+ − 961
axis lines=left,
+ − 962
width=\textwidth,
+ − 963
height=4cm,
+ − 964
legend entries={Python, Java 8, JavaScript, Swift},
+ − 965
legend pos=north west,
+ − 966
legend cell align=left]
+ − 967
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
+ − 968
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+ − 969
\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
+ − 970
\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
+ − 971
\end{axis}
+ − 972
\end{tikzpicture}
+ − 973
%
+ − 974
\end{column}
+ − 975
\begin{column}{.5\textwidth}
+ − 976
\small{}Us (after next lecture)\medskip\\
+ − 977
\begin{tikzpicture}\footnotesize
+ − 978
\begin{axis}[
+ − 979
xlabel={$n$},
+ − 980
x label style={at={(1.07,0.0)}},
+ − 981
ylabel={time in secs},
+ − 982
enlargelimits=false,
+ − 983
xtick={0,5000,...,10000},
+ − 984
xmax=11000,
+ − 985
ymax=35,
+ − 986
ytick={0,5,...,30},
+ − 987
scaled ticks=false,
+ − 988
axis lines=left,
+ − 989
width=\textwidth,
+ − 990
height=4cm]
+ − 991
\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
+ − 992
\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
+ − 993
\end{axis}
+ − 994
\end{tikzpicture}
+ − 995
\begin{tikzpicture}\footnotesize
+ − 996
\begin{axis}[
+ − 997
xlabel={$n$},
+ − 998
x label style={at={(1.07,0.0)}},
+ − 999
ylabel={time in secs},
+ − 1000
enlargelimits=false,
+ − 1001
ymax=35,
+ − 1002
ytick={0,5,...,30},
+ − 1003
scaled ticks=false,
+ − 1004
axis lines=left,
+ − 1005
width=\textwidth,
+ − 1006
height=4cm]
+ − 1007
\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
+ − 1008
\end{axis}
+ − 1009
\end{tikzpicture}
+ − 1010
\end{column}
+ − 1011
\end{columns}
+ − 1012
\medskip
+ − 1013
+ − 1014
\begin{textblock}{3}(-0.1,3.3)
+ − 1015
\small\hfill\bl{\texttt{[a?]\{n\}[a]\{n\}}}:
+ − 1016
\end{textblock}
+ − 1017
+ − 1018
\begin{textblock}{3}(-0.1,8.7)
+ − 1019
\small\hfill\bl{\texttt{(a*)*b}}:
+ − 1020
\end{textblock}
+ − 1021
+ − 1022
\begin{textblock}{3}(0.3,13)
+ − 1023
\small{}matching with strings
+ − 1024
\bl{$\underbrace{\texttt{a}...\texttt{a}}_n$}
+ − 1025
\end{textblock}
+ − 1026
+ − 1027
\end{frame}
+ − 1028
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1029
+ − 1030
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1031
\begin{frame}[c,fragile]
+ − 1032
\frametitle{Incidents}
+ − 1033
+ − 1034
\begin{itemize}
+ − 1035
\item a global outage on 2 July 2019 at \textbf{Cloudflare}
+ − 1036
(first one for six years)\medskip
+ − 1037
+ − 1038
\begin{center}\small\color{blue}
+ − 1039
\begin{verbatim}
+ − 1040
(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|
+ − 1041
null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s
+ − 1042
|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))
+ − 1043
\end{verbatim}
+ − 1044
\end{center}\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
+ − 1045
+ − 1046
\item on 20 July 2016 the \textbf{Stack Exchange} webpage went down
+ − 1047
because of an evil regular expression
+ − 1048
\here{https://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}
+ − 1049
\end{itemize}
+ − 1050
+ − 1051
\begin{textblock}{6}(6,7.6)
+ − 1052
\includegraphics[scale=0.14]{../pics/cloudflare.png}\\
+ − 1053
\footnotesize
+ − 1054
It serves more web traffic than Twitter, Amazon, Apple,
+ − 1055
Instagram, Bing \& Wikipedia combined.
+ − 1056
\here{https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/}
+ − 1057
\end{textblock}
+ − 1058
+ − 1059
\end{frame}
+ − 1060
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1061
+ − 1062
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1063
\begin{frame}[c]
+ − 1064
\frametitle{Evil Regular Expressions}
+ − 1065
+ − 1066
\begin{itemize}
+ − 1067
\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\medskip
+ − 1068
\item Some evil regular expressions:\medskip
+ − 1069
\begin{itemize}
+ − 1070
\item \bl{\texttt{[a?]\{n\}\;[a]\{n\}}}
+ − 1071
\item \bl{\texttt{(a*)*\;b}}
+ − 1072
\item \bl{\texttt{([a-z]+)*}}
+ − 1073
\item \bl{\texttt{(a + aa)*}}
+ − 1074
\item \bl{\texttt{(a + a?)*}}
+ − 1075
\end{itemize}
+ − 1076
+ − 1077
\item sometimes also called \alert{catastrophic backtracking}
+ − 1078
\item this is a problem for \alert{N}etwork \alert{I}ntrusion
+ − 1079
\alert{D}etection systems, Cloudflare, StackExchange, Atom editor
+ − 1080
\item \url{https://vimeo.com/112065252}
+ − 1081
\end{itemize}
+ − 1082
+ − 1083
\end{frame}
+ − 1084
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1085
930
+ − 1086
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1087
{
+ − 1088
\setbeamercolor{background canvas}{bg=cream}
+ − 1089
\begin{frame}[c]
+ − 1090
\frametitle{Rust vs.~Scala (from PEP)}
+ − 1091
+ − 1092
\mbox{}
+ − 1093
+ − 1094
\begin{minipage}{1.3\textwidth}
+ − 1095
\begin{mybox3}{}\it\small
+ − 1096
\textbf{Re: Another question of purely academic interest about regex implementation in cw3}
+ − 1097
+ − 1098
This conversation is interesting to me, and I've researched it a
+ − 1099
little bit [...] I also disagree with Dr.~Urban on the cost/benefit of
+ − 1100
non-GC languages [...]\smallskip
+ − 1101
+ − 1102
But regardless, Scala is a lot slower than, say, C or Rust. To say
+ − 1103
it's not is basically wrong (imo). Perhaps one could argue that some
+ − 1104
of the guarantees Scala has makes it easier to write multi-threaded
+ − 1105
programs that utilise more of the CPU... but, in my opinion, this is
+ − 1106
also a bit misleading. Most CPUs have something like 4 to 12 cores
+ − 1107
nowadays. It's very possible that a given Scala program runs 4-12x
+ − 1108
slower than its Rust equivalent. Would you rather have your program
+ − 1109
run quickly and use a single core, or have it run equally
+ − 1110
quickly... and... hog your entire CPU for its duration?\ldots{}
+ − 1111
+ − 1112
\mbox{}\hfill-- Oliver Iliffe, discussion from PEP
+ − 1113
\end{mybox3}
+ − 1114
\end{minipage}
+ − 1115
+ − 1116
\end{frame}
+ − 1117
}
+ − 1118
+ − 1119
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1120
{
+ − 1121
\setbeamercolor{background canvas}{bg=cream}
+ − 1122
\begin{frame}[c]
+ − 1123
\frametitle{Regex Lib in Rust}
+ − 1124
+ − 1125
\begin{center}
+ − 1126
\includegraphics[scale=0.34]{../pics/rust-regex.png}
+ − 1127
\end{center}
+ − 1128
+ − 1129
\end{frame}
+ − 1130
}
+ − 1131
+ − 1132
+ − 1133
+ − 1134
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1135
{
+ − 1136
\setbeamercolor{background canvas}{bg=cream}
+ − 1137
\begin{frame}[c,fragile]
+ − 1138
+ − 1139
\begin{columns}[t,onlytextwidth]
+ − 1140
\begin{column}{1\textwidth}
+ − 1141
\small re: \bl{$(abc)^{\{n\}}$}\quad str: \bl{$\underbrace{abc\ldots{}abc}_n$}\medskip\\
+ − 1142
\begin{tikzpicture}\footnotesize
+ − 1143
\begin{axis}[
+ − 1144
xlabel={$n$},
+ − 1145
x label style={at={(1.07,0.0)}},
+ − 1146
ylabel={time in secs},
+ − 1147
enlargelimits=false,
+ − 1148
xmax=65000,
+ − 1149
ymax=100,
+ − 1150
xtick={0,15000,...,60000},
+ − 1151
ytick={0,10,...,90},
+ − 1152
scaled ticks=false,
+ − 1153
axis lines=left,
+ − 1154
width=7cm,
+ − 1155
height=5cm]
+ − 1156
\addplot[black,mark=square*,mark options={fill=red}] table [x=x, y=y, col sep=comma, row sep=crcr]
+ − 1157
{x, y\\
+ − 1158
0, 0\\
+ − 1159
5000, 0.487\\
+ − 1160
10000, 1.650\\
+ − 1161
15000, 3.617\\
+ − 1162
20000, 6.462\\
+ − 1163
25000, 10.736\\
+ − 1164
30000, 17.665\\
+ − 1165
35000, 25.662\\
+ − 1166
40000, 36.422\\
+ − 1167
45000, 49.119\\
+ − 1168
50000, 62.058\\
+ − 1169
55000, 75.941\\
+ − 1170
60000, 93.022\\
+ − 1171
};
+ − 1172
\end{axis}
+ − 1173
\end{tikzpicture}
+ − 1174
\end{column}
+ − 1175
\end{columns}
+ − 1176
+ − 1177
\begin{textblock}{10}(8.4,3.8)
+ − 1178
\tiny
+ − 1179
\begin{lstlisting}[language=Rust]
+ − 1180
extern crate regex;
+ − 1181
+ − 1182
use regex::Regex;
+ − 1183
use std::time::Instant;
+ − 1184
+ − 1185
// bounded regular expression example
+ − 1186
+ − 1187
fn main() {
+ − 1188
for bound in (0..=60000).step_by(5000) {
+ − 1189
+ − 1190
let re = Regex::new(&format!("(abc){{{}}}", bound)).unwrap();
+ − 1191
let text = "abc".repeat(bound);
+ − 1192
+ − 1193
let start_time = Instant::now();
+ − 1194
let is_match = re.is_match(&text);
+ − 1195
let elapsed_time = start_time.elapsed().as_secs_f64();
+ − 1196
+ − 1197
println!("Bound: {}, Match: {}, Time: {} seconds", bound, is_match, elapsed_time);
+ − 1198
}
+ − 1199
}
+ − 1200
\end{lstlisting}
+ − 1201
\end{textblock}
+ − 1202
\end{frame}
+ − 1203
}
+ − 1204
+ − 1205
876
+ − 1206
+ − 1207
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1208
%\begin{frame}[c]
+ − 1209
%\frametitle{Today}
+ − 1210
%
+ − 1211
%\begin{itemize}
+ − 1212
%\item While the ultimate goal is to implement a small compiler for the JVM
+ − 1213
% \ldots\bigskip
+ − 1214
%\end{itemize}
+ − 1215
%
+ − 1216
%Let's start with:
+ − 1217
%
+ − 1218
%\begin{itemize}
+ − 1219
%\item a web-crawler
+ − 1220
%\item an email harvester
+ − 1221
%\item \textcolor{gray}{(a web-scraper)}
+ − 1222
%\end{itemize}
+ − 1223
%
+ − 1224
%\end{frame}
+ − 1225
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1226
+ − 1227
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1228
%\begin{frame}[t]
+ − 1229
%\frametitle{A Web-Crawler}
+ − 1230
%
+ − 1231
%\mbox{}\\[10mm]
+ − 1232
%
+ − 1233
%\begin{enumerate}
+ − 1234
%\item given an URL, read the corresponding webpage
+ − 1235
%\item extract all links from it
+ − 1236
%\item call the web-crawler again for all these links
+ − 1237
%\end{enumerate}
+ − 1238
%
+ − 1239
%\end{frame}
+ − 1240
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1241
+ − 1242
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1243
%\begin{frame}[t]
+ − 1244
%\frametitle{A Web-Crawler}
+ − 1245
%
+ − 1246
%\mbox{}\\[10mm]
+ − 1247
%
+ − 1248
%
+ − 1249
%\begin{enumerate}
+ − 1250
%\item given an URL, read the corresponding webpage
+ − 1251
%\item if not possible print, out a problem
+ − 1252
%\item if possible, extract all links from it
+ − 1253
%\item call the web-crawler again for all these links
+ − 1254
%\end{enumerate}\bigskip\pause
+ − 1255
%
+ − 1256
%\small (we need a bound for the number of recursive calls)
+ − 1257
%
+ − 1258
%\small (the purpose is to check all links on my own webpage)
+ − 1259
%\end{frame}
+ − 1260
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1261
+ − 1262
+ − 1263
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1264
%\begin{frame}[c]
+ − 1265
%
+ − 1266
%\begin{textblock}{1}(2,5)
+ − 1267
%\begin{tabular}{c}
+ − 1268
%\includegraphics[scale=0.15]{pics/servers.png}\\[-2mm]
+ − 1269
%\small Server
+ − 1270
%\end{tabular}
+ − 1271
%\end{textblock}
+ − 1272
%
+ − 1273
%\begin{textblock}{1}(5.6,4)
+ − 1274
% \begin{tikzpicture}[scale=1.1]
+ − 1275
% \draw[white] (0,1) node (X) {};
+ − 1276
% \draw[white] (2,1) node (Y) {};
+ − 1277
% \draw[white] (0,0) node (X1) {};
+ − 1278
% \draw[white] (2,0) node (Y1) {};
+ − 1279
% \draw[white] (0,-1) node (X2) {};
+ − 1280
% \draw[white] (2,-1) node (Y2) {};
+ − 1281
% \draw[red, <-, line width = 2mm] (X) -- (Y);
+ − 1282
% \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {};
+ − 1283
% \draw[red, ->, line width = 2mm] (X1) -- (Y1);
+ − 1284
% \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X1)!.5!(Y1) $) {};
+ − 1285
% \draw[red, <-, line width = 2mm] (X2) -- (Y2);
+ − 1286
% \node [inner sep=7pt,label=above:\textcolor{black}{POST data}] at ($ (X2)!.5!(Y2) $) {};
+ − 1287
% \end{tikzpicture}
+ − 1288
%\end{textblock}
+ − 1289
%
+ − 1290
%
+ − 1291
%\begin{textblock}{1}(9,5.5)
+ − 1292
%\begin{tabular}{c}
+ − 1293
%\includegraphics[scale=0.15]{pics/laptop.png}\\[-2mm]
+ − 1294
%\small Browser
+ − 1295
%\end{tabular}
+ − 1296
%\end{textblock}
+ − 1297
%\end{frame}
+ − 1298
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1299
+ − 1300
+ − 1301
+ − 1302
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1303
%\begin{frame}[c]
+ − 1304
%\frametitle{Scala}
+ − 1305
%
+ − 1306
%\small A simple Scala function for reading webpages:
+ − 1307
%\bigskip
+ − 1308
%
+ − 1309
%\footnotesize
+ − 1310
%\lstinputlisting{../progs/app0.scala}
+ − 1311
%\medskip\pause
+ − 1312
%
+ − 1313
%\lstinline{get_page("""https://nms.kcl.ac.uk/christian.urban/""")}
+ − 1314
%\bigskip\medskip\pause
+ − 1315
%
+ − 1316
%
+ − 1317
%\small A slightly more complicated version for handling errors:
+ − 1318
%\smallskip
+ − 1319
%
+ − 1320
%\footnotesize
+ − 1321
%\lstinputlisting[xleftmargin=-4mm]{../progs/app1.scala}
+ − 1322
%
+ − 1323
%
+ − 1324
%\end{frame}
+ − 1325
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1326
+ − 1327
+ − 1328
+ − 1329
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1330
%\begin{frame}[t]
+ − 1331
%\frametitle{A Regular Expression}
+ − 1332
%
+ − 1333
%\begin{itemize}
+ − 1334
%\item \ldots{} is a pattern or template for specifying strings
+ − 1335
%\end{itemize}\bigskip
+ − 1336
%
+ − 1337
%\begin{center}
+ − 1338
%\only<1>{\scode{"https?://[^"]*"}}%
+ − 1339
%\only<2>{\scode{""""https?://[^"]*"""".r}}
+ − 1340
%\end{center}\bigskip\bigskip
+ − 1341
%
+ − 1342
%matches for example\smallskip\\
+ − 1343
%\hspace{2mm}\code{"http://www.foobar.com"}\\
+ − 1344
%\hspace{2mm}\code{"https://www.tls.org"}\smallskip\\
+ − 1345
%
+ − 1346
%but not\smallskip\\
+ − 1347
%\hspace{2mm}\code{"http://www."foo"bar.com"}\\
+ − 1348
%
+ − 1349
%\end{frame}
+ − 1350
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1351
+ − 1352
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1353
%\begin{frame}[c]
+ − 1354
%\frametitle{Finding Operations in Scala}
+ − 1355
%
+ − 1356
%{\bf\code{rexp.findAllIn(string)}}\medskip
+ − 1357
%
+ − 1358
%returns a list of all (sub)strings that match the
+ − 1359
%regular expression
+ − 1360
%\bigskip\bigskip
+ − 1361
%
+ − 1362
%
+ − 1363
%{\bf\code{rexp.findFirstIn(string)}}\medskip
+ − 1364
%
+ − 1365
%returns either
+ − 1366
%
+ − 1367
%\begin{itemize}
+ − 1368
%\item \code{None} if no (sub)string matches or
+ − 1369
%\item \code{Some(s)} with the first (sub)string
+ − 1370
%\end{itemize}
+ − 1371
%
+ − 1372
%\end{frame}
+ − 1373
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1374
+ − 1375
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1376
%\begin{frame}[c]
+ − 1377
%
+ − 1378
%\footnotesize
+ − 1379
%\lstinputlisting{../progs/app2.scala}
+ − 1380
%
+ − 1381
%\end{frame}
+ − 1382
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1383
+ − 1384
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1385
%\begin{frame}[c]
+ − 1386
%
+ − 1387
%\small
+ − 1388
%A version that only crawls links in ``my'' domain:\bigskip
+ − 1389
%
+ − 1390
%\footnotesize
+ − 1391
%\lstinputlisting{../progs/app3.scala}
+ − 1392
%
+ − 1393
%\end{frame}
+ − 1394
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1395
+ − 1396
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1397
%\begin{frame}[c]
+ − 1398
%\lstset{xleftmargin=-4mm}
+ − 1399
%\small
+ − 1400
%A little email harvester:
+ − 1401
%
+ − 1402
%\footnotesize
+ − 1403
%\lstinputlisting{../progs/app4.scala}\bigskip
+ − 1404
%
+ − 1405
%\tiny
+ − 1406
%\url{http://net.tutsplus.com/tutorials/other/8-regular-expressions-you-should-know/}
+ − 1407
%
+ − 1408
%\end{frame}
+ − 1409
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1410
+ − 1411
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1412
\begin{frame}[t]
+ − 1413
\frametitle{(Basic) Regular Expressions}
+ − 1414
+ − 1415
Their inductive definition:
+ − 1416
+ − 1417
+ − 1418
\begin{textblock}{6}(2,7.5)
+ − 1419
\begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
+ − 1420
\bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\
+ − 1421
& \bl{$\mid$} & \bl{$\ONE$} & empty string / \pcode{""} / $[]$\\
+ − 1422
& \bl{$\mid$} & \bl{$c$} & character\\
+ − 1423
& \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\
+ − 1424
& \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\
+ − 1425
& \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\
+ − 1426
\end{tabular}
+ − 1427
\end{textblock}
+ − 1428
+ − 1429
+ − 1430
\only<2->{\footnotesize
+ − 1431
\begin{textblock}{9}(2,0.5)
+ − 1432
\begin{bubble}[9.8cm]
+ − 1433
\lstinputlisting{../progs/app01.scala}
+ − 1434
\end{bubble}
+ − 1435
\end{textblock}}
+ − 1436
+ − 1437
\end{frame}
+ − 1438
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1439
+ − 1440
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1441
%\begin{frame}[t]
+ − 1442
%\frametitle{Regular Expressions}
+ − 1443
%
+ − 1444
%\small
+ − 1445
%In Scala:\bigskip
+ − 1446
%
+ − 1447
%\footnotesize
+ − 1448
%\lstinputlisting{../progs/app51.scala}
+ − 1449
%
+ − 1450
%
+ − 1451
%\end{frame}
+ − 1452
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1453
+ − 1454
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1455
\begin{frame}[t]
+ − 1456
\frametitle{Strings}
+ − 1457
+ − 1458
\ldots are lists of characters. For example \code{"hello"}
+ − 1459
+ − 1460
\begin{center}
+ − 1461
\bl{$[h, e, l, l, o]$} or just \bl{$hello$}
+ − 1462
\end{center}
+ − 1463
+ − 1464
the empty string: \bl{$[]$} or \bl{\pcode{""}}\bigskip\\
+ − 1465
+ − 1466
the concatenation of two strings:
+ − 1467
+ − 1468
\begin{center}
+ − 1469
\bl{$s_1 \,@\, s_2$}
+ − 1470
\end{center}
+ − 1471
+ − 1472
\bl{\textit{foo $@$ bar = foobar}}\\
+ − 1473
\bl{\textit{baz $@\, []$ = baz}}
+ − 1474
+ − 1475
\end{frame}
+ − 1476
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1477
+ − 1478
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1479
\begin{frame}[c]
+ − 1480
\frametitle{Languages, Strings}
+ − 1481
+ − 1482
\begin{itemize}
+ − 1483
\item \alert{\bf Strings} are lists of characters, for example
+ − 1484
\begin{center}
+ − 1485
\bl{$[]$},\;\bl{$abc$} \hspace{2cm}(Pattern match: \bl{$c\!::\!s$})
+ − 1486
\end{center}\bigskip
+ − 1487
+ − 1488
+ − 1489
\item A \alert{\bf language} is a set of strings, for example\medskip
+ − 1490
\begin{center}
+ − 1491
\bl{$\{[], hello, \textit{foobar}, a, abc\}$}
+ − 1492
\end{center}\bigskip
+ − 1493
+ − 1494
\item \alert{\bf Concatenation} of strings and languages
+ − 1495
+ − 1496
\begin{center}
+ − 1497
\begin{tabular}{rcl}
+ − 1498
\bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\
+ − 1499
\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$}
+ − 1500
\end{tabular}
+ − 1501
\end{center}
+ − 1502
+ − 1503
%\item The \alert{\bf meaning} of a regular expression is a set of
+ − 1504
% strings, or language.
+ − 1505
\end{itemize}
+ − 1506
+ − 1507
\only<2>{
+ − 1508
\begin{textblock}{4}(10.5,8)
+ − 1509
\small
+ − 1510
Let
+ − 1511
+ − 1512
\bl{$A = \{foo, bar\}$} \bl{$B = \{a, b\}$}
+ − 1513
\[
+ − 1514
\bl{A \,@\, B = \{fooa, foob, bara, barb\}}
+ − 1515
\]
+ − 1516
\end{textblock}}
+ − 1517
+ − 1518
\end{frame}
+ − 1519
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1520
+ − 1521
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1522
\begin{frame}[c]
+ − 1523
\frametitle{Two Corner Cases}
+ − 1524
+ − 1525
\Large
+ − 1526
\begin{center}
+ − 1527
\bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\
+ − 1528
\bl{$A \,@\, \{\} = \;?$}
+ − 1529
\end{center}
+ − 1530
+ − 1531
\end{frame}
+ − 1532
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1533
+ − 1534
+ − 1535
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1536
\begin{frame}[c]
+ − 1537
\frametitle{The Meaning of a Regex}
+ − 1538
+ − 1539
...all the strings a regular expression can match.
+ − 1540
+ − 1541
\begin{center}
+ − 1542
\begin{tabular}{rcl}
+ − 1543
\bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\
+ − 1544
\bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
+ − 1545
\bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\
+ − 1546
\bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
+ − 1547
\bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\
+ − 1548
\bl{$L(r^*)$} & \bl{$\dn$} & \\
+ − 1549
\end{tabular}
+ − 1550
\end{center}
+ − 1551
+ − 1552
\begin{textblock}{14}(1.5,13.5)\small
+ − 1553
\bl{$L$} is a function from regular expressions to
+ − 1554
sets of strings (languages):\smallskip\\
+ − 1555
\bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
+ − 1556
\end{textblock}
+ − 1557
+ − 1558
\end{frame}
+ − 1559
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1560
+ − 1561
+ − 1562
+ − 1563
+ − 1564
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1565
\begin{frame}[c]
+ − 1566
\frametitle{The Power Operation}
+ − 1567
+ − 1568
\begin{itemize}
+ − 1569
\item The \alert{\textbf{\boldmath$n$th Power}} of a language:
+ − 1570
+ − 1571
\begin{center}
+ − 1572
\begin{tabular}{lcl}
+ − 1573
\bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
+ − 1574
\bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$}
+ − 1575
\end{tabular}
+ − 1576
\end{center}\bigskip
+ − 1577
+ − 1578
\item[] For example
+ − 1579
+ − 1580
\begin{center}
+ − 1581
\begin{tabular}{lcl@{\hspace{10mm}}l}
+ − 1582
\bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\
+ − 1583
\bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\
+ − 1584
\bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\
+ − 1585
\end{tabular}
+ − 1586
\end{center}
+ − 1587
+ − 1588
\end{itemize}
+ − 1589
+ − 1590
\end{frame}
+ − 1591
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1592
+ − 1593
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1594
\begin{frame}[c]
+ − 1595
\frametitle{The Meaning of a Regex}
+ − 1596
+ − 1597
\begin{textblock}{15}(1,4)
+ − 1598
\begin{tabular}{rcl}
+ − 1599
\bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\
+ − 1600
\bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
+ − 1601
\bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\
+ − 1602
\bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
+ − 1603
\bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\
+ − 1604
\bl{$L(r^*)$} & \bl{$\dn$} & \onslide<2->{\bl{$\bigcup_{0 \le n} L(r)^n$}}\\
+ − 1605
\end{tabular}\bigskip
+ − 1606
+ − 1607
%\onslide<2->{
+ − 1608
%\hspace{5mm}\bl{$L(r)^0 \;\dn\; \{[]\}$}\\
+ − 1609
%\bl{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}\hspace{9mm}\onslide<3->{\small\textcolor{gray}{(append on sets)}\\
+ − 1610
%\small\hspace{5cm}\textcolor{gray}{$\{ s_1 @ s_2 \;|\; s_1\in L(r) \wedge s_2 \in L(r)^n \}$}}
+ − 1611
%}
+ − 1612
\end{textblock}
+ − 1613
+ − 1614
\end{frame}
+ − 1615
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1616
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1617
\begin{frame}[c]
+ − 1618
\frametitle{The Star Operation}
+ − 1619
+ − 1620
\begin{itemize}
+ − 1621
\item The \alert{\bf Kleene Star} of a \underline{language}:
+ − 1622
\bigskip
+ − 1623
+ − 1624
\begin{center}
+ − 1625
\begin{tabular}{c}
+ − 1626
\bl{$A\star \dn \bigcup_{0\le n} A^n$}
+ − 1627
\end{tabular}
+ − 1628
\end{center}\bigskip
+ − 1629
+ − 1630
\item[] This expands to
+ − 1631
+ − 1632
\[
+ − 1633
\bl{A^0 \cup A^1 \cup A^2 \cup A^3 \cup A^4 \cup \ldots}
+ − 1634
\]
+ − 1635
+ − 1636
or
+ − 1637
+ − 1638
\small
+ − 1639
\[
+ − 1640
\bl{\{[]\} \;\cup\; A \;\cup\; A\,@\,A \;\cup\;
+ − 1641
A\,@\,A\,@\,A \;\cup\; A\,@\,A\,@\,A\,@\,A \cup \ldots}
+ − 1642
\]
+ − 1643
+ − 1644
\end{itemize}
+ − 1645
+ − 1646
\end{frame}
+ − 1647
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1648
+ − 1649
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1650
\begin{frame}[c]
+ − 1651
\frametitle{The Meaning of a Regex}
+ − 1652
+ − 1653
\begin{textblock}{15}(1,4)
+ − 1654
\begin{tabular}{rcl}
+ − 1655
\bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\
+ − 1656
\bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
+ − 1657
\bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\
+ − 1658
\bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
+ − 1659
\bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\
+ − 1660
\bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star$}\\
+ − 1661
\end{tabular}
+ − 1662
+ − 1663
\end{textblock}
+ − 1664
+ − 1665
\end{frame}
+ − 1666
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1667
+ − 1668
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1669
\begin{frame}[c]
+ − 1670
\frametitle{The Meaning of Matching}
+ − 1671
+ − 1672
\begin{bubble}[10cm]
+ − 1673
\large\bf
+ − 1674
A regular expression \bl{$r$} matches a string~\bl{$s$}
+ − 1675
provided
+ − 1676
+ − 1677
\begin{center}
+ − 1678
\bl{$s \in L(r)$}\\
+ − 1679
\end{center}
+ − 1680
\end{bubble}\bigskip\bigskip
+ − 1681
+ − 1682
\ldots and the point of the next lecture is
+ − 1683
to decide this problem as fast as possible (unlike Python,
+ − 1684
Ruby, Java)
+ − 1685
+ − 1686
\end{frame}
879
+ − 1687
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1688
+ − 1689
876
+ − 1690
+ − 1691
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1692
\begin{frame}[c]
+ − 1693
\frametitle{Questions}
+ − 1694
+ − 1695
\begin{itemize}
+ − 1696
\item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip
+ − 1697
+ − 1698
\item[]
+ − 1699
How many strings are in \bl{$A^4$}\,?
+ − 1700
\bigskip\medskip\pause
+ − 1701
+ − 1702
+ − 1703
\item[]
+ − 1704
What if \bl{$A = \{[a],[b],[c],[]\}$};\\
+ − 1705
how many strings are then in \bl{$A^4$}\,?
+ − 1706
\end{itemize}
+ − 1707
+ − 1708
\end{frame}
+ − 1709
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1710
+ − 1711
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
879
+ − 1712
\begin{frame}[c]
+ − 1713
\frametitle{Questions}
+ − 1714
+ − 1715
\begin{itemize}
+ − 1716
\item Assume a set $A$ contains 4 strings and a set $B$
+ − 1717
contains 7 strings. None of the strings is the empty
+ − 1718
string.
+ − 1719
+ − 1720
\item How many strings are in $A \,@\, B$?
+ − 1721
\end{itemize}
+ − 1722
+ − 1723
+ − 1724
\end{frame}
+ − 1725
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1726
930
+ − 1727
{
+ − 1728
\setbeamercolor{background canvas}{bg=cream}
+ − 1729
\begin{frame}[c]
+ − 1730
+ − 1731
\begin{minipage}{1.3\textwidth}
+ − 1732
+ − 1733
\end{minipage}
+ − 1734
\includegraphics[scale=0.4]{../pics/chatgpt.png}
+ − 1735
\end{frame}
+ − 1736
}
+ − 1737
+ − 1738
{
+ − 1739
\setbeamercolor{background canvas}{bg=cream}
+ − 1740
\begin{frame}[c]
+ − 1741
\frametitle{\dots{}for amusement}
+ − 1742
+ − 1743
\begin{minipage}{1.3\textwidth}
+ − 1744
\includegraphics[scale=0.4]{../pics/chatgpt1.png}
+ − 1745
\end{minipage}
+ − 1746
+ − 1747
\end{frame}
+ − 1748
}
+ − 1749
879
+ − 1750
+ − 1751
+ − 1752
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
876
+ − 1753
% \begin{frame}[c]
+ − 1754
% \frametitle{Languages (Sets of Strings)}
+ − 1755
+ − 1756
% \begin{itemize}
+ − 1757
+ − 1758
% \item A \alert{\bf Language} is a set of strings, for example\medskip
+ − 1759
% \begin{center}
+ − 1760
% \bl{$\{[], hello, foobar, a, abc\}$}
+ − 1761
% \end{center}\bigskip
+ − 1762
+ − 1763
% \item \alert{\bf Concatenation} for strings and languages
+ − 1764
+ − 1765
% \begin{center}
+ − 1766
% \begin{tabular}{rcl}
+ − 1767
% \bl{$foo\;@\;bar$} & \bl{$=$} & \bl{$foobar$}\medskip\\
+ − 1768
% \bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$}
+ − 1769
% \end{tabular}
+ − 1770
% \end{center}
+ − 1771
% \bigskip
+ − 1772
+ − 1773
% \small
+ − 1774
% \item [] For example \bl{$A = \{foo, bar\}$}, \bl{$B = \{a, b\}$}
+ − 1775
+ − 1776
% \[
+ − 1777
% \bl{A \,@\, B = \{fooa, foob, bara, barb\}}
+ − 1778
% \]
+ − 1779
+ − 1780
+ − 1781
+ − 1782
+ − 1783
% \end{itemize}
+ − 1784
% \end{frame}
+ − 1785
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1786
+ − 1787
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1788
% \begin{frame}[c]
+ − 1789
% \frametitle{Two Corner Cases}
+ − 1790
+ − 1791
% \Large
+ − 1792
% \begin{center}
+ − 1793
% \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\
+ − 1794
% \bl{$A \,@\, \{\} = \;?$}
+ − 1795
% \end{center}
+ − 1796
+ − 1797
% \end{frame}
+ − 1798
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1799
+ − 1800
+ − 1801
+ − 1802
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1803
% \begin{frame}[c]
+ − 1804
% \frametitle{The Meaning of a Regex}
+ − 1805
+ − 1806
% ...all the strings a regular expression can match.
+ − 1807
+ − 1808
% \begin{center}
+ − 1809
% \begin{tabular}{rcl}
+ − 1810
% \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\
+ − 1811
% \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
+ − 1812
% \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\
+ − 1813
% \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
+ − 1814
% \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\
+ − 1815
% \bl{$L(r^*)$} & \bl{$\dn$} & \\
+ − 1816
% \end{tabular}
+ − 1817
% \end{center}
+ − 1818
+ − 1819
% \begin{textblock}{14}(1.5,13.5)\small
+ − 1820
% \bl{$L$} is a function from regular expressions to
+ − 1821
% sets of strings (languages):\smallskip\\
+ − 1822
% \bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
+ − 1823
% \end{textblock}
+ − 1824
+ − 1825
% \end{frame}
+ − 1826
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1827
+ − 1828
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1829
% \begin{frame}[c]
+ − 1830
% \frametitle{The Power Operation}
+ − 1831
+ − 1832
% \begin{itemize}
+ − 1833
% \item The \alert{\textbf{\boldmath$n$th Power}} of a language:
+ − 1834
+ − 1835
% \begin{center}
+ − 1836
% \begin{tabular}{lcl}
+ − 1837
% \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
+ − 1838
% \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$}
+ − 1839
% \end{tabular}
+ − 1840
% \end{center}\bigskip
+ − 1841
+ − 1842
% \item[] For example
+ − 1843
+ − 1844
% \begin{center}
+ − 1845
% \begin{tabular}{lcl@{\hspace{10mm}}l}
+ − 1846
% \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\
+ − 1847
% \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\
+ − 1848
% \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\
+ − 1849
% \end{tabular}
+ − 1850
% \end{center}
+ − 1851
+ − 1852
% \end{itemize}
+ − 1853
+ − 1854
% \end{frame}
+ − 1855
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1856
+ − 1857
+ − 1858
+ − 1859
+ − 1860
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1861
% \begin{frame}[c]
+ − 1862
% \frametitle{Written Exam}
+ − 1863
+ − 1864
% \begin{itemize}
+ − 1865
% \item Accounts for 80\%.\bigskip
+ − 1866
+ − 1867
% \item The question ``\textit{Is this relevant for
+ − 1868
% the exam?}'' is very demotivating for the lecturer!\bigskip\\
+ − 1869
+ − 1870
% \item Deal: Whatever is in the homework (and is not marked
+ − 1871
% ``\textit{optional}'') is relevant for the exam.\bigskip
+ − 1872
+ − 1873
% \item Each lecture has also a handout. There are also handouts about
+ − 1874
% notation and Scala.
+ − 1875
% \end{itemize}
+ − 1876
+ − 1877
% \end{frame}
+ − 1878
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1879
+ − 1880
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1881
% \begin{frame}[t]
+ − 1882
% \frametitle{Coursework}
+ − 1883
+ − 1884
% \begin{itemize}
+ − 1885
% \item Accounts for 20\%. Two strands. Choose \alert{\bf one}!\bigskip
+ − 1886
% \end{itemize}
+ − 1887
+ − 1888
% \begin{columns}[t]
+ − 1889
% \begin{column}{.5\textwidth}
+ − 1890
% \underline{\bf Strand 1}\medskip
+ − 1891
% \begin{itemize}
+ − 1892
% \item 4 programming tasks:
+ − 1893
% \begin{itemize}
+ − 1894
% \item matcher (4\%, 11.10.)
+ − 1895
% \item lexer (5\%, 04.11.)
+ − 1896
% \item parser (5\%, 22.11.)
+ − 1897
% \item compiler (6\%, 13.12.)
+ − 1898
% \end{itemize}
+ − 1899
% \item in any lang.~you like,\\ but I want to see the\\ code
+ − 1900
% \end{itemize}
+ − 1901
% \end{column}
+ − 1902
+ − 1903
% \hspace{-45pt}\vrule{}\hspace{10pt}
+ − 1904
% \begin{column}{.5\textwidth}
+ − 1905
% \underline{\bf Strand 2}\smallskip\begin{itemize}
+ − 1906
% \item one task: prove the correctness of a regular expression matcher in
+ − 1907
% the \underline{Isabelle} theorem prover
+ − 1908
% \item 20\%, submission on~13.12.\hspace{-5mm}\mbox{}
+ − 1909
% \end{itemize}
+ − 1910
% \end{column}
+ − 1911
% \end{columns}\medskip
+ − 1912
+ − 1913
% \small
+ − 1914
% \begin{itemize}
+ − 1915
% \item Solving more than one strand will {\bf not} give you more
+ − 1916
% marks.
+ − 1917
+ − 1918
% \end{itemize}
+ − 1919
+ − 1920
% \end{frame}
+ − 1921
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1922
+ − 1923
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1924
%\begin{frame}[c]
+ − 1925
%\frametitle{Lecture Capture}
+ − 1926
%
+ − 1927
%\begin{itemize}
+ − 1928
%\item Hope it works\ldots\pause actually no, it does not!\medskip\pause
+ − 1929
%\item It is important to use lecture capture wisely\\ (it is only the ``baseline''):
+ − 1930
%\begin{itemize}
+ − 1931
%\item Lecture recordings are a study and revision aid.
+ − 1932
%\item Statistically, there is a clear and direct link between attendance and
+ − 1933
% attainment: students who do not attend lectures, do less well in exams.
+ − 1934
%\end{itemize}
+ − 1935
%
+ − 1936
%\item Attending a lecture is more than watching it online -- if you do not
+ − 1937
%attend, you miss out!
+ − 1938
%
+ − 1939
%\end{itemize}
+ − 1940
%
+ − 1941
%\end{frame}
+ − 1942
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1943
+ − 1944
+ − 1945
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1946
\begin{frame}[c]
929
+ − 1947
\frametitle{\begin{tabular}{c}\\[1cm]\alert{Questions?}\end{tabular}}
876
+ − 1948
+ − 1949
+ − 1950
\begin{tabular}{lll}
922
+ − 1951
SGT TAs: & Flavio Melinte Citea & (was a KURF last summer)\\
+ − 1952
& Krishi Wali \\
+ − 1953
& Meilai Ji \medskip\\
929
+ − 1954
Amm Helpers & Harry Dilnot & (harry.dilnot@kcl.ac.uk)\\
+ − 1955
& Meilai Ji & (meilai.ji@kcl.ac.uk)\medskip\\
876
+ − 1956
\end{tabular}
+ − 1957
\mbox{}
+ − 1958
\end{frame}
+ − 1959
+ − 1960
\begin{frame}[c]
+ − 1961
\end{frame}
+ − 1962
+ − 1963
\begin{frame}[c]
+ − 1964
\end{frame}
+ − 1965
+ − 1966
\begin{frame}[c]
+ − 1967
\end{frame}
+ − 1968
+ − 1969
\begin{frame}[c]
+ − 1970
\end{frame}
+ − 1971
+ − 1972
\begin{frame}[c]
+ − 1973
\end{frame}
+ − 1974
+ − 1975
\begin{frame}[c]
+ − 1976
\end{frame}
+ − 1977
+ − 1978
\begin{frame}[c]
+ − 1979
\end{frame}
+ − 1980
+ − 1981
\begin{frame}[c]
+ − 1982
\end{frame}
+ − 1983
+ − 1984
\begin{frame}[c]
+ − 1985
\end{frame}
+ − 1986
+ − 1987
\begin{frame}[c]
+ − 1988
\end{frame}
+ − 1989
+ − 1990
\begin{frame}[c]
+ − 1991
\end{frame}
+ − 1992
+ − 1993
\begin{frame}[c]
+ − 1994
\end{frame}
+ − 1995
+ − 1996
\begin{frame}[c]
+ − 1997
\end{frame}
+ − 1998
+ − 1999
\begin{frame}[c]
+ − 2000
\end{frame}
+ − 2001
+ − 2002
+ − 2003
\begin{frame}[c]
+ − 2004
\begin{mybox3}{Coursework}
+ − 2005
Do we need to provide instructions on running the coursework files
+ − 2006
if we're using languages other than Scala? Thanks
+ − 2007
\end{mybox3}\pause
+ − 2008
+ − 2009
\begin{mybox2}{Zip-File for Coursework}
+ − 2010
Please, please submit a zipfile that generates a subdirectory
+ − 2011
\begin{center}
+ − 2012
\texttt{NameFamilyName}
+ − 2013
\end{center}
+ − 2014
\end{mybox2}
+ − 2015
\end{frame}
+ − 2016
+ − 2017
+ − 2018
\begin{frame}[c]
+ − 2019
\begin{mybox3}{What is the trick?}\small
+ − 2020
What was the trick to improve the evil regular expressions matcher
+ − 2021
to have such good results compared to other programming languages?
+ − 2022
Is it working better on casual regular expressions (the ones that
+ − 2023
Python and Java handle pretty well), too? Or was it just optimised
+ − 2024
for these evil ones?
+ − 2025
\end{mybox3}
+ − 2026
\end{frame}
+ − 2027
+ − 2028
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 2029
\begin{frame}[c]
+ − 2030
\frametitle{Thanks to Martin Mikusovic}
+ − 2031
+ − 2032
\bigskip
+ − 2033
\begin{center}
+ − 2034
\begin{tikzpicture}
+ − 2035
\begin{axis}[
+ − 2036
xlabel={$n$},
+ − 2037
x label style={at={(1.05,0.0)}},
+ − 2038
ylabel={time in secs},
+ − 2039
enlargelimits=false,
+ − 2040
xtick={0,5,...,30},
+ − 2041
xmax=33,
+ − 2042
ymax=35,
+ − 2043
ytick={0,10,...,30},
+ − 2044
scaled ticks=false,
+ − 2045
axis lines=left,
+ − 2046
width=9cm,
+ − 2047
height=5.5cm,
+ − 2048
legend entries={Java 8, Python, JavaScript, Swift},
+ − 2049
legend pos=north west,
+ − 2050
legend cell align=left]
+ − 2051
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
+ − 2052
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+ − 2053
\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
+ − 2054
\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
+ − 2055
\end{axis}
+ − 2056
\end{tikzpicture}
+ − 2057
\end{center}
+ − 2058
+ − 2059
Regex: \bl{$(a^*)^* \cdot b$}
+ − 2060
+ − 2061
Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$}
+ − 2062
+ − 2063
\end{frame}
+ − 2064
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 2065
+ − 2066
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 2067
\begin{frame}[c]
+ − 2068
\frametitle{Same Example in Java 9+}
+ − 2069
+ − 2070
\begin{center}
+ − 2071
\begin{tikzpicture}
+ − 2072
\begin{axis}[
+ − 2073
xlabel={$n$},
+ − 2074
x label style={at={(1.09,-0.15)}},
+ − 2075
ylabel={time in secs},
+ − 2076
scaled x ticks=false,
+ − 2077
enlargelimits=false,
+ − 2078
xtick distance=10000,
+ − 2079
xmax=44000,
+ − 2080
ytick={0,10,...,30},
+ − 2081
ymax=35,
+ − 2082
axis lines=left,
+ − 2083
width=9cm,
+ − 2084
height=5cm,
+ − 2085
legend entries={Java \liningnums{9}+},
+ − 2086
legend pos=north west,
+ − 2087
legend cell align=left]
+ − 2088
\addplot[blue,mark=square*,mark options={fill=white}] table {re-java9.data};
+ − 2089
\end{axis}
+ − 2090
\end{tikzpicture}
+ − 2091
\end{center}
+ − 2092
+ − 2093
Regex: \bl{$(a^*)^* \cdot b$}
+ − 2094
+ − 2095
Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$}
+ − 2096
+ − 2097
\end{frame}
+ − 2098
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 2099
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 2100
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 2101
% Questions
+ − 2102
+ − 2103
+ − 2104
+ − 2105
+ − 2106
\begin{frame}[c]
+ − 2107
\end{frame}
+ − 2108
+ − 2109
\begin{frame}[c]
+ − 2110
\end{frame}
+ − 2111
+ − 2112
\begin{frame}[c]
+ − 2113
\end{frame}
+ − 2114
+ − 2115
\begin{frame}[c]
+ − 2116
\end{frame}
+ − 2117
879
+ − 2118
\begin{frame}[c]
876
+ − 2119
+ − 2120
\end{frame}
+ − 2121
+ − 2122
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 2123
\end{document}
+ − 2124
+ − 2125
%%% Local Variables:
+ − 2126
%%% mode: latex
+ − 2127
%%% TeX-master: t
+ − 2128
%%% End:
+ − 2129