# HG changeset patch # User Christian Urban # Date 1664514226 -3600 # Node ID ad9d4a01e072f55d18dc569bed01eaf8dbdbe950 # Parent 6722cd24c78451e32d1a468909b5119dc2b13da0 updated diff -r 6722cd24c784 -r ad9d4a01e072 progs/matcher/re1.sc --- a/progs/matcher/re1.sc Thu Sep 29 22:07:21 2022 +0100 +++ b/progs/matcher/re1.sc Fri Sep 30 06:03:46 2022 +0100 @@ -179,47 +179,3 @@ @arg(doc = "All tests.") @main def all() = { test1(); test2() ; test3() } - - - -// runs with amm2 and amm3 - -def pp(r: Rexp): String = r match { - case SEQ(CHAR(a1), SEQ(r1, r2)) => s"${a1}${pp(r1)}${pp(r2)}" - case SEQ(ONE, SEQ(r1, r2)) => s"1${pp(r1)}${pp(r2)}" - case SEQ(ZERO, SEQ(r1, r2)) => s"0${pp(r1)}${pp(r2)}" - case SEQ(CHAR(a1), CHAR(a2)) => s"${a1}${a2}" - case SEQ(ONE, CHAR(a2)) => s"1${a2}" - case SEQ(ZERO, CHAR(a2)) => s"0${a2}" - case ZERO => "0" - case ONE => "1" - case CHAR(a) => a.toString - case ALT(r1, r2) => s"(${pp(r1)} + ${pp(r2)})" - case SEQ(r1, r2) => s"(${pp(r1)} o ${pp(r2)})" - case STAR(r1) => s"(${pp(r1)})*" -} - - -val REG = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))) - -print(pp(ders("".toList, REG))) -print(pp(ders("a".toList, REG))) -print(pp(ders("aa".toList, REG))) -print(pp(ders("aaa".toList, REG))) - -size(ders("".toList, REG)) // 6 -size(ders("a".toList, REG)) // 12 -size(ders("aa".toList, REG)) // 27 -size(ders("aaa".toList, REG)) // 55 -size(ders("aaaa".toList, REG)) // 98 -size(ders("aaaaa".toList, REG)) // 169 -size(ders("aaaaaa".toList, REG)) // 283 -size(ders(("a" * 7).toList, REG)) // 468 -size(ders(("a" * 8).toList, REG)) // 767 -size(ders(("a" * 9).toList, REG)) // 1251 -size(ders(("a" * 10).toList, REG))// 2034 -size(ders(("a" * 11).toList, REG))// 3301 - -for (i <- (0 to 40)) { - println(s"$i:" + size(ders(("a" * i).toList, REG))) -} \ No newline at end of file diff -r 6722cd24c784 -r ad9d4a01e072 progs/matcher/re2.sc --- a/progs/matcher/re2.sc Thu Sep 29 22:07:21 2022 +0100 +++ b/progs/matcher/re2.sc Fri Sep 30 06:03:46 2022 +0100 @@ -145,7 +145,3 @@ @main def all() = { test1(); test2() } - - - -// runs with amm2 and amm3 diff -r 6722cd24c784 -r ad9d4a01e072 progs/matcher/re3.sc --- a/progs/matcher/re3.sc Thu Sep 29 22:07:21 2022 +0100 +++ b/progs/matcher/re3.sc Fri Sep 30 06:03:46 2022 +0100 @@ -186,44 +186,3 @@ def fail() = { test3(); test4() } -// runs with amm2 and amm3 - -def pp(r: Rexp): String = r match { - case SEQ(CHAR(a1), SEQ(r1, r2)) => s"${a1}${pp(r1)}${pp(r2)}" - case SEQ(ONE, SEQ(r1, r2)) => s"1${pp(r1)}${pp(r2)}" - case SEQ(ZERO, SEQ(r1, r2)) => s"0${pp(r1)}${pp(r2)}" - case SEQ(CHAR(a1), CHAR(a2)) => s"${a1}${a2}" - case SEQ(ONE, CHAR(a2)) => s"1${a2}" - case SEQ(ZERO, CHAR(a2)) => s"0${a2}" - case ZERO => "0" - case ONE => "1" - case CHAR(a) => a.toString - case ALT(r1, r2) => s"(${pp(r1)} + ${pp(r2)})" - case SEQ(r1, r2) => s"(${pp(r1)} o ${pp(r2)})" - case STAR(r1) => s"(${pp(r1)})*" -} - - -val REG = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))) - -print(pp(ders("".toList, REG))) -print(pp(ders("a".toList, REG))) -print(pp(ders("aa".toList, REG))) -print(pp(ders("aaa".toList, REG))) - -size(ders("".toList, REG)) // 6 -size(ders("a".toList, REG)) // 12 -size(ders("aa".toList, REG)) // 27 -size(ders("aaa".toList, REG)) // 55 -size(ders("aaaa".toList, REG)) // 8 -size(ders("aaaaa".toList, REG)) // 169 -size(ders("aaaaaa".toList, REG)) // 283 -size(ders(("a" * 7).toList, REG)) // 468 -size(ders(("a" * 8).toList, REG)) // 767 -size(ders(("a" * 9).toList, REG)) // 1251 -size(ders(("a" * 10).toList, REG))// 2034 -size(ders(("a" * 11).toList, REG))// 3301 - -for (i <- (0 to 40)) { - println(s"$i:" + size(ders(("a" * i).toList, REG))) -} \ No newline at end of file diff -r 6722cd24c784 -r ad9d4a01e072 slides/slides01.pdf Binary file slides/slides01.pdf has changed diff -r 6722cd24c784 -r ad9d4a01e072 slides/slides01.tex --- a/slides/slides01.tex Thu Sep 29 22:07:21 2022 +0100 +++ b/slides/slides01.tex Fri Sep 30 06:03:46 2022 +0100 @@ -247,7 +247,6 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] \frametitle{Why Study Compilers?} @@ -293,6 +292,36 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +{ +\setbeamercolor{background canvas}{bg=cream} +\begin{frame}[c] + +\frametitle{} +\begin{mybox3}{}\it + ``I enjoyed the module - it was genuinely the stand out academic +experience of my undergraduate degree, and very much influenced my +career interests. In fact I am currently working at ARM, in their Open +Source Software group, on AArch64 specific optimisations for the +Java/Kotlin compiler that forms part of the Android Runtime.''\\ +\mbox{}\hfill-- Hari Limaye in year 2021/22 +\end{mybox3}\pause + + +Student numbers in CFL\medskip\\ +\begin{tabular}{ll} +2019: & 32\\ +2020: & 59\\ +2021: & 109\\ +2022: & 121\\ +\end{tabular} + +\end{frame} +} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -442,6 +471,23 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +{ +\setbeamercolor{background canvas}{bg=cream} +\begin{frame}[c] +\frametitle{Homework} + +Last year(s): I did not give out solutions; students sent emails to me and I marked them individually\bigskip\\ + + +This year: We will do homework mainly during the Labs (TAs have the solutions)\bigskip\\\pause + +I will still choose the questions from the HW for the exam, but there might be +some larger amount of deviation. + +\end{frame} +} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{Some Housekeeping} @@ -460,8 +506,6 @@ you can use any code I show you and is uploaded to KEATS\ldots\textbf{BUT NOTHING ELSE!} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -560,6 +604,16 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +{ +\setbeamercolor{background canvas}{bg=cream} +\begin{frame}[t] +\frametitle{Notation for REs} + + + + +\end{frame} +} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -1235,7 +1289,9 @@ Ruby, Java) \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -1258,6 +1314,24 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{Questions} + + \begin{itemize} + \item Assume a set $A$ contains 4 strings and a set $B$ + contains 7 strings. None of the strings is the empty + string. + + \item How many strings are in $A \,@\, B$? + \end{itemize} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \begin{frame}[c] % \frametitle{Languages (Sets of Strings)} @@ -1456,8 +1530,9 @@ \begin{tabular}{lll} - TAs: & Finley Warman & (took the module last year)\\ - & Chengsong Tan & (PhD student working on derivatives) + TAs: & Huang Linh & (took the module last year)\\ + & Alfredo Musumeci \\ + & Issa Kabir \\ \end{tabular} \mbox{} \end{frame} @@ -1521,17 +1596,6 @@ \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? @@ -1539,15 +1603,6 @@ 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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -1625,108 +1680,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Questions -\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}{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 - -\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] @@ -1741,7 +1695,7 @@ \begin{frame}[c] \end{frame} -\begin{frame}[c,fragile] +\begin{frame}[c] \end{frame}