65 |
62 |
66 \onslide<1->{ |
63 \onslide<1->{ |
67 \only<2>{ |
64 \only<2>{ |
68 \begin{itemize} |
65 \begin{itemize} |
69 \item {\bf Hardware is getting weirder |
66 \item {\bf Hardware is getting weirder |
70 rather than getting clocked faster} |
67 rather than getting clocked faster.} |
71 |
68 |
72 \begin{itemize} |
69 \begin{itemize} |
73 \item Almost all processors are |
70 \item[] ``Almost all processors are multicores nowadays and it looks |
74 multicores nowadays and it looks like there is increasing asymmetry in |
71 like there is increasing asymmetry in resources across cores. |
75 resources across cores. Processors come with vector units, crypto |
72 Processors come with vector units, crypto accelerators etc. We have |
76 accelerators etc. We have DSPs, GPUs, |
73 DSPs, GPUs, ARM big.little, and Xeon Phi. This is only scratching the |
77 ARM big.little, and Xeon Phi. This is only scratching the |
74 surface.'' |
78 surface. |
|
79 \end{itemize} |
75 \end{itemize} |
80 \end{itemize}} |
76 \end{itemize}} |
81 \only<3>{ |
77 \only<3>{ |
82 \begin{itemize} |
78 \begin{itemize} |
83 \item {\bf We’re getting tired of low-level languages and |
79 \item {\bf We’re getting tired of low-level languages and |
84 their associated security disasters} |
80 their associated security disasters.} |
85 |
81 |
86 \begin{itemize} |
82 \begin{itemize} |
87 \item |
83 \item [] ``We want to write new code, to whatever extent possible, in |
88 We want to write new code, to |
84 safer, higher-level languages. Compilers are caught right in the |
89 whatever extent possible, in safer, higher-level |
85 middle of these opposing trends: one of their main jobs is to help |
90 languages. Compilers are caught right in the middle of these |
86 bridge the large and growing gap between increasingly high-level |
91 opposing trends: one of their main jobs is to help bridge the large |
87 languages and increasingly wacky platforms.'' |
92 and growing gap between increasingly high-level languages and |
|
93 increasingly wacky platforms. |
|
94 \end{itemize} |
88 \end{itemize} |
95 \end{itemize}}} |
89 \end{itemize}}} |
96 |
90 |
97 \end{frame} |
91 \end{frame} |
98 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
92 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
93 |
|
94 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
95 \begin{frame}[t] |
|
96 \frametitle{What are Compilers?} |
|
97 |
|
98 \begin{center} |
|
99 \begin{tikzpicture}[] |
|
100 \node (0) at (-2.3,0) {\includegraphics[scale=0.3]{pics/csource.png}}; |
|
101 \node (1) [right=35mm] at (0) {\includegraphics[scale=0.3]{pics/cassmbl.png}}; |
|
102 \draw [->,line width=4mm, red] (0) -- (1); |
|
103 \end{tikzpicture} |
|
104 \end{center} |
|
105 |
|
106 \begin{textblock}{10}(1,13.5) |
|
107 Compiler explorers, e.g.: \url{https://gcc.godbolt.org} |
|
108 \end{textblock} |
|
109 |
|
110 \end{frame} |
|
111 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
112 |
|
113 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
114 \begin{frame}[c] |
|
115 \frametitle{\begin{tabular}{c}Why Bother?\\[-2mm] Compilers \& Boeings 777\end{tabular}} |
|
116 |
|
117 First flight in 1994. They want to achieve triple redundancy in hardware |
|
118 faults.\bigskip |
|
119 |
|
120 They compile 1 Ada program to\medskip |
|
121 |
|
122 \begin{itemize} |
|
123 \item Intel 80486 |
|
124 \item Motorola 68040 (old Macintosh's) |
|
125 \item AMD 29050 (RISC chips used often in laser printers) |
|
126 \end{itemize}\medskip\medskip |
|
127 |
|
128 using 3 independent compilers.\bigskip\pause |
|
129 |
|
130 \small Airbus uses C and static analysers. Recently started using CompCert. |
|
131 |
|
132 \end{frame} |
|
133 %%%%%%%%%%% |
99 |
134 |
100 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
135 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
101 \begin{frame}[c] |
136 \begin{frame}[c] |
102 \frametitle{Why Bother?} |
137 \frametitle{Why Bother?} |
103 |
138 |
189 \small\centering |
225 \small\centering |
190 matching \texttt{[a?]\{n\}[a]\{n\}} and \texttt{(a*)*b} |
226 matching \texttt{[a?]\{n\}[a]\{n\}} and \texttt{(a*)*b} |
191 against $\underbrace{\texttt{a}...\texttt{a}}_n$ |
227 against $\underbrace{\texttt{a}...\texttt{a}}_n$ |
192 \end{frame} |
228 \end{frame} |
193 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
229 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
194 |
230 |
|
231 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
232 \begin{frame}[c,fragile] |
|
233 \frametitle{Incidents} |
|
234 |
|
235 \begin{itemize} |
|
236 \item a global outage on 2 July 2019 at \textbf{Cloudflare} |
|
237 (first one for six years)\medskip |
|
238 |
|
239 \begin{center}\small\color{blue} |
|
240 \begin{verbatim} |
|
241 (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false| |
|
242 null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s |
|
243 |-|~|!|{}|\|\||\+)*.*(?:.*=.*))) |
|
244 \end{verbatim} |
|
245 \end{center}\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip |
|
246 |
|
247 \item on 20 July 2016 the \textbf{Stack Exchange} webpage went down |
|
248 because of an evil regular expression |
|
249 \end{itemize} |
|
250 |
|
251 \begin{textblock}{6}(9,7.6) |
|
252 \includegraphics[scale=0.14]{cloudflare.png}\\ |
|
253 \footnotesize |
|
254 It serves more web traffic than Twitter, Amazon, Apple, Instagram, Bing \& Wikipedia combined. |
|
255 \end{textblock} |
|
256 |
|
257 \end{frame} |
|
258 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
259 |
195 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
260 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
196 \begin{frame}[c] |
261 \begin{frame}[c] |
197 \frametitle{Evil Regular Expressions} |
262 \frametitle{Evil Regular Expressions} |
198 |
263 |
199 \begin{itemize} |
264 \begin{itemize} |
415 |
481 |
416 \end{frame} |
482 \end{frame} |
417 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
483 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
418 |
484 |
419 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
485 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
420 \begin{frame}[c] |
486 %\begin{frame}[c] |
421 \frametitle{Today} |
487 %\frametitle{Today} |
422 |
488 % |
423 \begin{itemize} |
489 %\begin{itemize} |
424 \item While the ultimate goal is to implement a small compiler for the JVM |
490 %\item While the ultimate goal is to implement a small compiler for the JVM |
425 \ldots\bigskip |
491 % \ldots\bigskip |
426 \end{itemize} |
492 %\end{itemize} |
427 |
493 % |
428 Let's start with: |
494 %Let's start with: |
429 |
495 % |
430 \begin{itemize} |
496 %\begin{itemize} |
431 \item a web-crawler |
497 %\item a web-crawler |
432 \item an email harvester |
498 %\item an email harvester |
433 %\item \textcolor{gray}{(a web-scraper)} |
499 %\item \textcolor{gray}{(a web-scraper)} |
434 \end{itemize} |
500 %\end{itemize} |
435 |
501 % |
436 \end{frame} |
502 %\end{frame} |
437 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
503 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
438 |
504 |
439 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
505 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
440 \begin{frame}[t] |
506 %\begin{frame}[t] |
441 \frametitle{A Web-Crawler} |
507 %\frametitle{A Web-Crawler} |
442 |
508 % |
443 \mbox{}\\[10mm] |
509 %\mbox{}\\[10mm] |
444 |
510 % |
445 \begin{enumerate} |
511 %\begin{enumerate} |
446 \item given an URL, read the corresponding webpage |
512 %\item given an URL, read the corresponding webpage |
447 \item extract all links from it |
513 %\item extract all links from it |
448 \item call the web-crawler again for all these links |
514 %\item call the web-crawler again for all these links |
449 \end{enumerate} |
515 %\end{enumerate} |
450 |
516 % |
451 \end{frame} |
517 %\end{frame} |
452 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
518 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
453 |
519 |
454 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
520 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
455 \begin{frame}[t] |
521 %\begin{frame}[t] |
456 \frametitle{A Web-Crawler} |
522 %\frametitle{A Web-Crawler} |
457 |
523 % |
458 \mbox{}\\[10mm] |
524 %\mbox{}\\[10mm] |
459 |
525 % |
460 |
526 % |
461 \begin{enumerate} |
527 %\begin{enumerate} |
462 \item given an URL, read the corresponding webpage |
528 %\item given an URL, read the corresponding webpage |
463 \item if not possible print, out a problem |
529 %\item if not possible print, out a problem |
464 \item if possible, extract all links from it |
530 %\item if possible, extract all links from it |
465 \item call the web-crawler again for all these links |
531 %\item call the web-crawler again for all these links |
466 \end{enumerate}\bigskip\pause |
532 %\end{enumerate}\bigskip\pause |
467 |
533 % |
468 \small (we need a bound for the number of recursive calls) |
534 %\small (we need a bound for the number of recursive calls) |
469 |
535 % |
470 \small (the purpose is to check all links on my own webpage) |
536 %\small (the purpose is to check all links on my own webpage) |
471 \end{frame} |
537 %\end{frame} |
472 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
538 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
473 |
539 |
474 |
540 |
475 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
541 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
476 \begin{frame}[c] |
542 %\begin{frame}[c] |
477 |
543 % |
478 \begin{textblock}{1}(2,5) |
544 %\begin{textblock}{1}(2,5) |
479 \begin{tabular}{c} |
545 %\begin{tabular}{c} |
480 \includegraphics[scale=0.15]{pics/servers.png}\\[-2mm] |
546 %\includegraphics[scale=0.15]{pics/servers.png}\\[-2mm] |
481 \small Server |
547 %\small Server |
482 \end{tabular} |
548 %\end{tabular} |
483 \end{textblock} |
549 %\end{textblock} |
484 |
550 % |
485 \begin{textblock}{1}(5.6,4) |
551 %\begin{textblock}{1}(5.6,4) |
486 \begin{tikzpicture}[scale=1.1] |
552 % \begin{tikzpicture}[scale=1.1] |
487 \draw[white] (0,1) node (X) {}; |
553 % \draw[white] (0,1) node (X) {}; |
488 \draw[white] (2,1) node (Y) {}; |
554 % \draw[white] (2,1) node (Y) {}; |
489 \draw[white] (0,0) node (X1) {}; |
555 % \draw[white] (0,0) node (X1) {}; |
490 \draw[white] (2,0) node (Y1) {}; |
556 % \draw[white] (2,0) node (Y1) {}; |
491 \draw[white] (0,-1) node (X2) {}; |
557 % \draw[white] (0,-1) node (X2) {}; |
492 \draw[white] (2,-1) node (Y2) {}; |
558 % \draw[white] (2,-1) node (Y2) {}; |
493 \draw[red, <-, line width = 2mm] (X) -- (Y); |
559 % \draw[red, <-, line width = 2mm] (X) -- (Y); |
494 \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {}; |
560 % \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {}; |
495 \draw[red, ->, line width = 2mm] (X1) -- (Y1); |
561 % \draw[red, ->, line width = 2mm] (X1) -- (Y1); |
496 \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X1)!.5!(Y1) $) {}; |
562 % \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X1)!.5!(Y1) $) {}; |
497 \draw[red, <-, line width = 2mm] (X2) -- (Y2); |
563 % \draw[red, <-, line width = 2mm] (X2) -- (Y2); |
498 \node [inner sep=7pt,label=above:\textcolor{black}{POST data}] at ($ (X2)!.5!(Y2) $) {}; |
564 % \node [inner sep=7pt,label=above:\textcolor{black}{POST data}] at ($ (X2)!.5!(Y2) $) {}; |
499 \end{tikzpicture} |
565 % \end{tikzpicture} |
500 \end{textblock} |
566 %\end{textblock} |
501 |
567 % |
502 |
568 % |
503 \begin{textblock}{1}(9,5.5) |
569 %\begin{textblock}{1}(9,5.5) |
504 \begin{tabular}{c} |
570 %\begin{tabular}{c} |
505 \includegraphics[scale=0.15]{pics/laptop.png}\\[-2mm] |
571 %\includegraphics[scale=0.15]{pics/laptop.png}\\[-2mm] |
506 \small Browser |
572 %\small Browser |
507 \end{tabular} |
573 %\end{tabular} |
508 \end{textblock} |
574 %\end{textblock} |
509 \end{frame} |
575 %\end{frame} |
510 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
576 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
511 |
577 |
512 |
578 |
513 |
579 |
514 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
580 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
515 \begin{frame}[c] |
581 %\begin{frame}[c] |
516 \frametitle{Scala} |
582 %\frametitle{Scala} |
517 |
583 % |
518 \small A simple Scala function for reading webpages: |
584 %\small A simple Scala function for reading webpages: |
519 \bigskip |
585 %\bigskip |
520 |
586 % |
521 \footnotesize |
587 %\footnotesize |
522 \lstinputlisting{../progs/app0.scala} |
588 %\lstinputlisting{../progs/app0.scala} |
523 \medskip\pause |
589 %\medskip\pause |
524 |
590 % |
525 \lstinline{get_page("""https://nms.kcl.ac.uk/christian.urban/""")} |
591 %\lstinline{get_page("""https://nms.kcl.ac.uk/christian.urban/""")} |
526 \bigskip\medskip\pause |
592 %\bigskip\medskip\pause |
527 |
593 % |
528 |
594 % |
529 \small A slightly more complicated version for handling errors: |
595 %\small A slightly more complicated version for handling errors: |
530 \smallskip |
596 %\smallskip |
531 |
597 % |
532 \footnotesize |
598 %\footnotesize |
533 \lstinputlisting[xleftmargin=-4mm]{../progs/app1.scala} |
599 %\lstinputlisting[xleftmargin=-4mm]{../progs/app1.scala} |
534 |
600 % |
535 |
601 % |
536 \end{frame} |
602 %\end{frame} |
537 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
603 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
538 |
604 |
539 |
605 |
540 |
606 |
541 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
607 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
583 |
649 |
584 \end{frame} |
650 \end{frame} |
585 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
651 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
586 |
652 |
587 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
653 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
588 \begin{frame}[c] |
654 %\begin{frame}[c] |
589 |
655 % |
590 \footnotesize |
656 %\footnotesize |
591 \lstinputlisting{../progs/app2.scala} |
657 %\lstinputlisting{../progs/app2.scala} |
592 |
658 % |
593 \end{frame} |
659 %\end{frame} |
594 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
660 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
595 |
661 |
596 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
662 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
597 \begin{frame}[c] |
663 %\begin{frame}[c] |
598 |
664 % |
599 \small |
665 %\small |
600 A version that only crawls links in ``my'' domain:\bigskip |
666 %A version that only crawls links in ``my'' domain:\bigskip |
601 |
667 % |
602 \footnotesize |
668 %\footnotesize |
603 \lstinputlisting{../progs/app3.scala} |
669 %\lstinputlisting{../progs/app3.scala} |
604 |
670 % |
605 \end{frame} |
671 %\end{frame} |
606 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
672 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
607 |
673 |
608 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
674 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
609 \begin{frame}[c] |
675 %\begin{frame}[c] |
610 \lstset{xleftmargin=-4mm} |
676 %\lstset{xleftmargin=-4mm} |
611 \small |
677 %\small |
612 A little email harvester: |
678 %A little email harvester: |
613 |
679 % |
614 \footnotesize |
680 %\footnotesize |
615 \lstinputlisting{../progs/app4.scala}\bigskip |
681 %\lstinputlisting{../progs/app4.scala}\bigskip |
616 |
682 % |
617 \tiny |
683 %\tiny |
618 \url{http://net.tutsplus.com/tutorials/other/8-regular-expressions-you-should-know/} |
684 %\url{http://net.tutsplus.com/tutorials/other/8-regular-expressions-you-should-know/} |
619 |
685 % |
620 \end{frame} |
686 %\end{frame} |
621 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
687 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
622 |
688 |
623 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
689 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
624 \begin{frame}[t] |
690 \begin{frame}[t] |
625 \frametitle{Regular Expressions} |
691 \frametitle{Regular Expressions} |
764 Ruby, Java) |
831 Ruby, Java) |
765 |
832 |
766 \end{frame} |
833 \end{frame} |
767 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
834 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
768 |
835 |
|
836 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
837 \begin{frame}[c] |
|
838 \frametitle{The Power Operation} |
|
839 |
|
840 \begin{itemize} |
|
841 \item The \alert{\textbf{\boldmath$n$th Power}} of a language: |
|
842 |
|
843 \begin{center} |
|
844 \begin{tabular}{lcl} |
|
845 \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
|
846 \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} |
|
847 \end{tabular} |
|
848 \end{center}\bigskip |
|
849 |
|
850 \item[] For example |
|
851 |
|
852 \begin{center} |
|
853 \begin{tabular}{lcl@{\hspace{10mm}}l} |
|
854 \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\ |
|
855 \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\ |
|
856 \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ |
|
857 \end{tabular} |
|
858 \end{center} |
|
859 |
|
860 \end{itemize} |
|
861 |
|
862 \end{frame} |
|
863 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
864 |
|
865 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
866 \begin{frame}[c] |
|
867 \frametitle{Questions} |
|
868 |
|
869 \begin{itemize} |
|
870 \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip |
|
871 |
|
872 \item[] |
|
873 How many strings are in \bl{$A^4$}\,? |
|
874 \bigskip\medskip\pause |
|
875 |
|
876 |
|
877 \item[] |
|
878 What if \bl{$A = \{[a],[b],[c],[]\}$};\\ |
|
879 how many strings are then in \bl{$A^4$}\,? |
|
880 \end{itemize} |
|
881 |
|
882 \end{frame} |
|
883 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
884 |
|
885 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
886 \begin{frame}[c] |
|
887 \frametitle{The Star Operation} |
|
888 |
|
889 \begin{itemize} |
|
890 \item The \alert{\bf Kleene Star} of a \underline{language}: |
|
891 \bigskip |
|
892 |
|
893 \begin{center} |
|
894 \begin{tabular}{c} |
|
895 \bl{$A\star \dn \bigcup_{0\le n} A^n$} |
|
896 \end{tabular} |
|
897 \end{center}\bigskip |
|
898 |
|
899 \item[] This expands to |
|
900 |
|
901 \[ |
|
902 \bl{A^0 \cup A^1 \cup A^2 \cup A^3 \cup A^4 \cup \ldots} |
|
903 \] |
|
904 |
|
905 or |
|
906 |
|
907 \small |
|
908 \[ |
|
909 \bl{\{[]\} \;\cup\; A \;\cup\; A\,@\,A \;\cup\; |
|
910 A\,@\,A\,@\,A \;\cup\; A\,@\,A\,@\,A\,@\,A \cup \ldots} |
|
911 \] |
|
912 |
|
913 \end{itemize} |
|
914 |
|
915 \end{frame} |
|
916 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
917 |
|
918 |
769 |
919 |
770 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
920 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
771 \begin{frame}[c] |
921 \begin{frame}[c] |
772 \frametitle{Written Exam} |
922 \frametitle{Written Exam} |
773 |
923 |
797 |
947 |
798 \begin{columns}[t] |
948 \begin{columns}[t] |
799 \begin{column}{.5\textwidth} |
949 \begin{column}{.5\textwidth} |
800 \underline{\bf Strand 1}\medskip |
950 \underline{\bf Strand 1}\medskip |
801 \begin{itemize} |
951 \begin{itemize} |
802 \item four programming tasks: |
952 \item 4 programming tasks: |
803 \begin{itemize} |
953 \begin{itemize} |
804 \item matcher (4\%, 12.10.) |
954 \item matcher (4\%, 11.10.) |
805 \item lexer (5\%, 02.11.) |
955 \item lexer (5\%, 04.11.) |
806 \item parser (5\%, 23.11.) |
956 \item parser (5\%, 22.11.) |
807 \item compiler (6\%, 14.12.) |
957 \item compiler (6\%, 13.12.) |
808 \end{itemize} |
958 \end{itemize} |
809 \item in any lang.~you like,\\ but I want to see the code |
959 \item in any lang.~you like,\\ but I want to see the\\ code |
810 \end{itemize} |
960 \end{itemize} |
811 \end{column} |
961 \end{column} |
812 |
962 |
813 \hspace{-45pt}\vrule{}\hspace{10pt} |
963 \hspace{-45pt}\vrule{}\hspace{10pt} |
814 \begin{column}{.5\textwidth} |
964 \begin{column}{.5\textwidth} |
815 \underline{\bf Strand 2}\smallskip\begin{itemize} |
965 \underline{\bf Strand 2}\smallskip\begin{itemize} |
816 \item one task: prove the correctness of a regular expression matcher in |
966 \item one task: prove the correctness of a regular expression matcher in |
817 the \underline{Isabelle} theorem prover |
967 the \underline{Isabelle} theorem prover |
818 \item 20\%, submission on~14.12.\hspace{-5mm}\mbox{} |
968 \item 20\%, submission on~13.12.\hspace{-5mm}\mbox{} |
819 \end{itemize} |
969 \end{itemize} |
820 \end{column} |
970 \end{column} |
821 \end{columns}\medskip |
971 \end{columns}\medskip |
822 |
972 |
823 \small |
973 \small |