Mercurial Mercurial > hg > afl-material / changeset
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | raw | gz | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
updated
authorChristian Urban <christian.urban@kcl.ac.uk>
Fri, 30 Sep 2022 06:03:46 +0100
changeset 879 ad9d4a01e072
parent 878 6722cd24c784
child 880 bc04fc576896
updated
progs/matcher/re1.sc file | annotate | diff | comparison | revisions
progs/matcher/re2.sc file | annotate | diff | comparison | revisions
progs/matcher/re3.sc file | annotate | diff | comparison | revisions
slides/slides01.pdf file | annotate | diff | comparison | revisions
slides/slides01.tex file | annotate | diff | comparison | revisions 
--- 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
--- 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
--- 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
Binary file slides/slides01.pdf has changed
--- 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}
afl-material