290 \end{itemize} |
289 \end{itemize} |
291 \end{itemize}}} |
290 \end{itemize}}} |
292 |
291 |
293 \end{frame} |
292 \end{frame} |
294 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
293 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
294 |
|
295 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
296 { |
|
297 \setbeamercolor{background canvas}{bg=cream} |
|
298 \begin{frame}[c] |
|
299 |
|
300 \frametitle{} |
|
301 \begin{mybox3}{}\it |
|
302 ``I enjoyed the module - it was genuinely the stand out academic |
|
303 experience of my undergraduate degree, and very much influenced my |
|
304 career interests. In fact I am currently working at ARM, in their Open |
|
305 Source Software group, on AArch64 specific optimisations for the |
|
306 Java/Kotlin compiler that forms part of the Android Runtime.''\\ |
|
307 \mbox{}\hfill-- Hari Limaye in year 2021/22 |
|
308 \end{mybox3}\pause |
|
309 |
|
310 |
|
311 Student numbers in CFL\medskip\\ |
|
312 \begin{tabular}{ll} |
|
313 2019: & 32\\ |
|
314 2020: & 59\\ |
|
315 2021: & 109\\ |
|
316 2022: & 121\\ |
|
317 \end{tabular} |
|
318 |
|
319 \end{frame} |
|
320 } |
|
321 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
322 |
|
323 |
295 |
324 |
296 |
325 |
297 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
326 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
298 \begin{frame}[c] |
327 \begin{frame}[c] |
299 \frametitle{Why Bother with Compilers?} |
328 \frametitle{Why Bother with Compilers?} |
440 \end{itemize} |
469 \end{itemize} |
441 |
470 |
442 \end{frame} |
471 \end{frame} |
443 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
472 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
444 |
473 |
|
474 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
475 { |
|
476 \setbeamercolor{background canvas}{bg=cream} |
|
477 \begin{frame}[c] |
|
478 \frametitle{Homework} |
|
479 |
|
480 Last year(s): I did not give out solutions; students sent emails to me and I marked them individually\bigskip\\ |
|
481 |
|
482 |
|
483 This year: We will do homework mainly during the Labs (TAs have the solutions)\bigskip\\\pause |
|
484 |
|
485 I will still choose the questions from the HW for the exam, but there might be |
|
486 some larger amount of deviation. |
|
487 |
|
488 \end{frame} |
|
489 } |
|
490 |
445 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
491 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
446 \begin{frame}[c] |
492 \begin{frame}[c] |
447 \frametitle{Some Housekeeping} |
493 \frametitle{Some Housekeeping} |
448 |
494 |
449 \textbf{Coursework (5 accounting for 65\%):}\bigskip |
495 \textbf{Coursework (5 accounting for 65\%):}\bigskip |
1254 how many strings are then in \bl{$A^4$}\,? |
1310 how many strings are then in \bl{$A^4$}\,? |
1255 \end{itemize} |
1311 \end{itemize} |
1256 |
1312 |
1257 \end{frame} |
1313 \end{frame} |
1258 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1314 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1315 |
|
1316 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1317 \begin{frame}[c] |
|
1318 \frametitle{Questions} |
|
1319 |
|
1320 \begin{itemize} |
|
1321 \item Assume a set $A$ contains 4 strings and a set $B$ |
|
1322 contains 7 strings. None of the strings is the empty |
|
1323 string. |
|
1324 |
|
1325 \item How many strings are in $A \,@\, B$? |
|
1326 \end{itemize} |
|
1327 |
|
1328 |
|
1329 \end{frame} |
|
1330 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1331 |
|
1332 |
1259 |
1333 |
1260 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1334 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1261 % \begin{frame}[c] |
1335 % \begin{frame}[c] |
1262 % \frametitle{Languages (Sets of Strings)} |
1336 % \frametitle{Languages (Sets of Strings)} |
1263 |
1337 |
1519 \end{mybox2} |
1594 \end{mybox2} |
1520 \end{frame} |
1595 \end{frame} |
1521 |
1596 |
1522 |
1597 |
1523 \begin{frame}[c] |
1598 \begin{frame}[c] |
1524 \begin{mybox3}{Coursework} |
|
1525 What is the purpose of the workshop session on the timetable? |
|
1526 |
|
1527 Slightly confused about how to undertake cw1 and what exactly we |
|
1528 should be implementing. This is more for clarification of the cw1 |
|
1529 structure, including the implementation and questions present in |
|
1530 cw1. |
|
1531 \end{mybox3} |
|
1532 \end{frame} |
|
1533 |
|
1534 \begin{frame}[c] |
|
1535 \begin{mybox3}{What is the trick?}\small |
1599 \begin{mybox3}{What is the trick?}\small |
1536 What was the trick to improve the evil regular expressions matcher |
1600 What was the trick to improve the evil regular expressions matcher |
1537 to have such good results compared to other programming languages? |
1601 to have such good results compared to other programming languages? |
1538 Is it working better on casual regular expressions (the ones that |
1602 Is it working better on casual regular expressions (the ones that |
1539 Python and Java handle pretty well), too? Or was it just optimised |
1603 Python and Java handle pretty well), too? Or was it just optimised |
1540 for these evil ones? |
1604 for these evil ones? |
1541 \end{mybox3} |
|
1542 |
|
1543 \begin{mybox3}{}\small |
|
1544 It was shown in the lectures that the pattern matching algorithms |
|
1545 currently implemented in popular programming languages (Python, JS, |
|
1546 Java, etc) are far slower than the algorithm we are going to be |
|
1547 implementing in this module. My question is why do these programming |
|
1548 languages not implement the algorithm that we are going to implement |
|
1549 in this module? |
|
1550 \end{mybox3} |
1605 \end{mybox3} |
1551 \end{frame} |
1606 \end{frame} |
1552 |
1607 |
1553 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1608 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1554 \begin{frame}[c] |
1609 \begin{frame}[c] |
1623 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1678 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1624 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1679 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1625 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1680 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1626 % Questions |
1681 % Questions |
1627 |
1682 |
1628 \begin{frame}[c] |
1683 |
1629 \begin{mybox3}{} |
1684 |
1630 Are there any (common) languages that have a built-in regex |
1685 |
1631 implementation matching the set of functions of a formal 'simple' |
1686 \begin{frame}[c] |
1632 regular expression, as opposed to an 'extended' regular expression |
1687 \end{frame} |
1633 implemented in most regex-supporting languages? |
1688 |
1634 \end{mybox3} |
1689 \begin{frame}[c] |
1635 \end{frame} |
1690 \end{frame} |
1636 |
1691 |
1637 \begin{frame}[c] |
1692 \begin{frame}[c] |
1638 \begin{mybox3}{Regexes} |
1693 \end{frame} |
1639 Can we determine all the possible regular expressions matching a |
1694 |
1640 certain string? If we take into account all the possible ways to |
1695 \begin{frame}[c] |
1641 combine the operations: \bl{$\ZERO$}, \bl{$\ONE$}, |
1696 \end{frame} |
1642 \bl{$r_1 + r_2$}, \bl{$r_1 \cdot r_2$}, \bl{$r^*$}? |
1697 |
1643 \end{mybox3} |
1698 \begin{frame}[c] |
1644 \end{frame} |
|
1645 |
|
1646 \begin{frame}[c] |
|
1647 \begin{mybox3}{\bl{$L$} + Equivalence} |
|
1648 When we explain why two regular expressions are not equivalent, what |
|
1649 method is better for us, using mathematics formulas or making an |
|
1650 example? |
|
1651 \end{mybox3} |
|
1652 \begin{mybox3}{} |
|
1653 Meaning of Regex and Operations |
|
1654 \end{mybox3} |
|
1655 \end{frame} |
|
1656 |
|
1657 \begin{frame}[c] |
|
1658 \begin{mybox3}{\bl{$L$}} |
|
1659 Can the function L be applied to anything other than regular |
|
1660 expressions? For example would L(L(c)) return anything? |
|
1661 \end{mybox3} |
|
1662 |
|
1663 \hfill $\Rightarrow$ No |
|
1664 \end{frame} |
|
1665 |
|
1666 \begin{frame}[c] |
|
1667 \begin{mybox3}{\bl{$(a?)\{n\} \cdot a\{n\}$}} |
|
1668 In the evil regexes section, is there any reason why in the regex |
|
1669 \texttt{[a?]\{n\}[a]\{n\}} the square brackets are used? It is defined as a |
|
1670 single character from the square brackets, however there is just one |
|
1671 character, so it seems like it is not necessary. Maybe it is just |
|
1672 necessary for the first part, because ? is a token instead of a |
|
1673 character and we need to refer to a? as a ``unit''? Could regular |
|
1674 brackets be used instead? Is there any difference apart from the |
|
1675 fact that it would create a group? Also, are the regexes |
|
1676 \texttt{[a?]\{n\}} and |
|
1677 \texttt{a\{0,3\}} equivalent? |
|
1678 \end{mybox3} |
|
1679 \end{frame} |
|
1680 |
|
1681 \begin{frame}[c] |
|
1682 \begin{mybox3}{Python + Parser Combinators (CW3)}\small |
|
1683 Hi Christian, |
|
1684 |
|
1685 I don’t see a problem: you certainly have higher order functions and |
|
1686 it is easy to implement algebraic data types using classes. As far |
|
1687 as I can see that’s all you need. You don’t get the static types but |
|
1688 that should be obvious. Basically if you can do it in LISP you can |
|
1689 do it in Python. The only problem could be stack overflows due to a |
|
1690 lack of tail recursion optimisation. On the other hand you can |
|
1691 simulate laziness using generators. |
|
1692 |
|
1693 Cheers, |
|
1694 Thorsten |
|
1695 \end{mybox3} |
|
1696 |
|
1697 Trees \url{https://youtu.be/7tCNu4CnjVc} |
|
1698 |
|
1699 Laziness \url{https://youtu.be/5jwV3zxXc8E} |
|
1700 |
|
1701 \end{frame} |
|
1702 |
|
1703 \begin{frame}[c] |
|
1704 \begin{mybox3}{} |
|
1705 What suggestions do you have for us to get the most out of this |
|
1706 module, especially in the online format? I.e. form discussion |
|
1707 groups, will you have office hours? |
|
1708 \end{mybox3} |
|
1709 |
|
1710 \small |
|
1711 \hfill $\Rightarrow$\mbox{} Discussion Forum on KEATS |
|
1712 |
|
1713 \hfill online tutorial sessions |
|
1714 |
|
1715 \end{frame} |
|
1716 |
|
1717 \begin{frame}[c] |
|
1718 \small |
|
1719 \begin{mybox3}{} |
|
1720 Where do most students struggle with this module? What will the format |
|
1721 of the exam be? What is the most efficient way of studying for the |
|
1722 exam? There are plenty of resources available on KEATS, but is there |
|
1723 anything else you'd recommend us to study? Although (just by skimming |
|
1724 the headings) the module seems to be a combination of practical and |
|
1725 theoretical matters, exactly in what field would the syllabus be |
|
1726 applied? Besides these questions and the ones other students asked, is |
|
1727 there anything else we should know? Thank you! |
|
1728 \end{mybox3} |
|
1729 \end{frame} |
|
1730 |
|
1731 |
|
1732 \begin{frame}[c] |
|
1733 \end{frame} |
|
1734 |
|
1735 \begin{frame}[c] |
|
1736 \end{frame} |
|
1737 |
|
1738 \begin{frame}[c] |
|
1739 \end{frame} |
|
1740 |
|
1741 \begin{frame}[c] |
|
1742 \end{frame} |
|
1743 |
|
1744 \begin{frame}[c,fragile] |
|
1745 |
1699 |
1746 \end{frame} |
1700 \end{frame} |
1747 |
1701 |
1748 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1702 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1749 \end{document} |
1703 \end{document} |