diff -r 34f77b976b88 -r f9686b22db7e slides/slides01.tex --- a/slides/slides01.tex Tue Sep 29 21:52:52 2020 +0100 +++ b/slides/slides01.tex Sat Oct 03 00:51:47 2020 +0100 @@ -1453,8 +1453,265 @@ \begin{frame}[c] \frametitle{\begin{tabular}{c}\\[3cm]\alert{Questions?}\end{tabular}} + +\begin{tabular}{lll} + TAs: & Anton Luca-Dorin & (took the module last year)\\ + & Chengsong Tan & (PhD student working on derivatives) +\end{tabular} \mbox{} \end{frame} + +\begin{frame}[c] +\begin{mybox3}{Coursework} + Do we need to provide instructions on running the coursework files + if we're using languages other than Scala? Thanks +\end{mybox3}\pause + +\begin{mybox2}{Zip-File for Coursework} + Please, please submit a zipfile that generates a subdirectory + \begin{center} + \texttt{NameFamilyName} + \end{center} +\end{mybox2} +\end{frame} + + +\begin{frame}[c] +\begin{mybox3}{Coursework} + What is the purpose of the workshop session on the timetable? + + Slightly confused about how to undertake cw1 and what exactly we + should be implementing. This is more for clarification of the cw1 + structure, including the implementation and questions present in + cw1. +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{What is the trick?}\small + What was the trick to improve the evil regular expressions matcher + to have such good results compared to other programming languages? + Is it working better on casual regular expressions (the ones that + Python and Java handle pretty well), too? Or was it just optimised + for these evil ones? +\end{mybox3} + +\begin{mybox3}{}\small + It was shown in the lectures that the pattern matching algorithms + currently implemented in popular programming languages (Python, JS, + Java, etc) are far slower than the algorithm we are going to be + implementing in this module. My question is why do these programming + languages not implement the algorithm that we are going to implement + in this module? +\end{mybox3} +\end{frame} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{Thanks to Martin Mikusovic} + +\bigskip +\begin{center} +\begin{tikzpicture} + \begin{axis}[ + xlabel={$n$}, + x label style={at={(1.05,0.0)}}, + ylabel={time in secs}, + enlargelimits=false, + xtick={0,5,...,30}, + xmax=33, + ymax=35, + ytick={0,10,...,30}, + scaled ticks=false, + axis lines=left, + width=9cm, + height=5.5cm, + legend entries={Java 8, Python, JavaScript, Swift}, + legend pos=north west, + legend cell align=left] +\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; +\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; +\addplot[red,mark=*, mark options={fill=white}] table {re-js.data}; +\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data}; +\end{axis} +\end{tikzpicture} +\end{center} + +Regex: \bl{$(a^*)^* \cdot b$} + +Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Same Example in Java 9+} + +\begin{center} +\begin{tikzpicture} + \begin{axis}[ + xlabel={$n$}, + x label style={at={(1.09,-0.15)}}, + ylabel={time in secs}, + scaled x ticks=false, + enlargelimits=false, + xtick distance=10000, + xmax=44000, + ytick={0,10,...,30}, + ymax=35, + axis lines=left, + width=9cm, + height=5cm, + legend entries={Java \liningnums{9}+}, + legend pos=north west, + legend cell align=left] +\addplot[blue,mark=square*,mark options={fill=white}] table {re-java9.data}; +\end{axis} +\end{tikzpicture} +\end{center} + +Regex: \bl{$(a^*)^* \cdot b$} + +Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\begin{frame}[c] +\begin{mybox3}{} + Are there any (common) languages that have a built-in regex + implementation matching the set of functions of a formal 'simple' + regular expression, as opposed to an 'extended' regular expression + implemented in most regex-supporting languages? +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{Passing Mark} + I believe the assessment is 70\% coursework (broken into 10\% weekly + stuff, 15\% mid term exam and 45\% CW in any programming language) + and 30\% January exam. However, I would like to know if we just need + 40\% overall to pass the module or pass the each component + individually? +\end{mybox3} + +\hfill$\Rightarrow$ 40\% overall +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{Regexes} + Can we determine all the possible regular expressions matching a + certain string? If we take into account all the possible ways to + combine the operations: \bl{$\ZERO$}, \bl{$\ONE$}, + \bl{$r_1 + r_2$}, \bl{$r_1 \cdot r_2$}, \bl{$r^*$}? +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{\bl{$L$} + Equivalence} + When we explain why two regular expressions are not equivalent, what + method is better for us, using mathematics formulas or making an + example? +\end{mybox3} +\begin{mybox3}{} + Meaning of Regex and Operations +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{\bl{$L$}} + Can the function L be applied to anything other than regular + expressions? For example would L(L(c)) return anything? +\end{mybox3} + +\hfill $\Rightarrow$ No +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{\bl{$(a?)\{n\} \cdot a\{n\}$}} + In the evil regexes section, is there any reason why in the regex + \texttt{[a?]\{n\}[a]\{n\}} the square brackets are used? It is defined as a + single character from the square brackets, however there is just one + character, so it seems like it is not necessary. Maybe it is just + necessary for the first part, because ? is a token instead of a + character and we need to refer to a? as a ``unit''? Could regular + brackets be used instead? Is there any difference apart from the + fact that it would create a group? Also, are the regexes + \texttt{[a?]\{n\}} and + \texttt{a\{0,3\}} equivalent? +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{Python + Parser Combinators (CW3)}\small + Hi Christian, + + I don’t see a problem: you certainly have higher order functions and + it is easy to implement algebraic data types using classes. As far + as I can see that’s all you need. You don’t get the static types but + that should be obvious. Basically if you can do it in LISP you can + do it in Python. The only problem could be stack overflows due to a + lack of tail recursion optimisation. On the other hand you can + simulate laziness using generators. + + Cheers, + Thorsten +\end{mybox3} + +Trees \url{https://youtu.be/7tCNu4CnjVc} + +Laziness \url{https://youtu.be/5jwV3zxXc8E} + +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{} + What suggestions do you have for us to get the most out of this + module, especially in the online format? I.e. form discussion + groups, will you have office hours? +\end{mybox3} + +\small +\hfill $\Rightarrow$\mbox{} Discussion Forum on KEATS + +\hfill online tutorial sessions + +\hfill ??? + +\hfill PL-groups for ``exotic'' langs +\end{frame} + +\begin{frame}[c] + \small +\begin{mybox3}{} +Where do most students struggle with this module? What will the format +of the exam be? What is the most efficient way of studying for the +exam? There are plenty of resources available on KEATS, but is there +anything else you'd recommend us to study? Although (just by skimming +the headings) the module seems to be a combination of practical and +theoretical matters, exactly in what field would the syllabus be +applied? Besides these questions and the ones other students asked, is +there anything else we should know? Thank you! +\end{mybox3} +\end{frame} + + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}