# HG changeset patch # User Christian Urban # Date 1630406949 -3600 # Node ID dbf9d710ce6589a629e2a42b72b40d4a85e50546 # Parent dc3c35673e94a5f44eb477c9f6ec83ec1a76fa6e updated diff -r dc3c35673e94 -r dbf9d710ce65 handouts/amm-ho.pdf Binary file handouts/amm-ho.pdf has changed diff -r dc3c35673e94 -r dbf9d710ce65 handouts/amm-ho.tex --- a/handouts/amm-ho.tex Mon Aug 30 15:50:27 2021 +0100 +++ b/handouts/amm-ho.tex Tue Aug 31 11:49:09 2021 +0100 @@ -13,14 +13,20 @@ For the coursework in this module you are free to use any programming language you like, but I will show you all my code using Scala---I -hope you have fond memories of Scala from PEP. But as said, you do not -need to use Scala for your own code.\footnote{Haskell, Rust, Ocaml - were other languages that have been used previously in CFL. I - recommend to not use Java or C for writing a compiler, but if you - insist, feel free.} I will use the current stable version of -Scala, which is 2.13.3. If you need a reminder of the Scala handouts -for PEP have a look -\hr{http://talisker.nms.kcl.ac.uk/cgi-bin/repos.cgi/pep-material/raw-file/tip/handouts/pep-ho.pdf}\bigskip +hope you have fond memories of Scala from PEP. If you need a reminder +of the Scala handouts for PEP have a look +\hr{http://talisker.nms.kcl.ac.uk/cgi-bin/repos.cgi/pep-material/raw-file/tip/handouts/pep-ho.pdf} + + +But as said, you do not need to use Scala for your own +code.\footnote{Haskell, Rust, Ocaml were other languages that have + been used previously in CFL. I recommend to not use Java or C for + writing a compiler, but if you insist, feel free. It has been done +before.} I will use the +current stable version of Scala, which is 2.13.6. For various reasons, +I am NOT GOING TO USE THE LATEST VERSION OF SCALA 3.0! Please be +aware of this when you run my code. +\bigskip \noindent The main difference to the Scala I showed you in PEP is that in CFL @@ -37,8 +43,8 @@ \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] $ amm Loading... -Welcome to the Ammonite Repl 2.2.0 (Scala 2.13.3 Java 9) -scala> 1 + 2 +Welcome to the Ammonite Repl 2.3.8 (Scala 2.13.3 Java 9) +scala> 1 + 2 res0: Int = 3 \end{lstlisting} %% $ diff -r dc3c35673e94 -r dbf9d710ce65 handouts/ho01.pdf Binary file handouts/ho01.pdf has changed diff -r dc3c35673e94 -r dbf9d710ce65 handouts/ho01.tex --- a/handouts/ho01.tex Mon Aug 30 15:50:27 2021 +0100 +++ b/handouts/ho01.tex Tue Aug 31 11:49:09 2021 +0100 @@ -42,13 +42,13 @@ \begin{document} -\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018, 2019, 2020} +\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021} \section*{Handout 1} The purpose of a compiler is to transform a program a human can read and -write into code the machine can run as fast as possible. Developing a +write into code machines can run as fast as possible. Developing a compiler is an old craft going back to 1952 with the first compiler written by Grace Hopper.\footnote{Who many years ago was invited on a talk show hosted by David Letterman. @@ -344,7 +344,7 @@ \noindent Finally, on 2 July 2019 Cloudflare had a global outage because of a -regular expression (they had no outage for the last 6 years). What +regular expression (they had no outage for the 6 years before). What happened is nicely explained in the blog: \begin{center} @@ -531,7 +531,7 @@ If you prefer to think in terms of the implementation of regular expressions in Scala, the constructors and classes relate as follows\footnote{More about Scala is -in the handout about \emph{A Crash-Course on Scala}.} +in the handout about \emph{A Crash-Course on Scala} from PEP.} \begin{center} \begin{tabular}{rcl} @@ -621,6 +621,8 @@ & = & L(r_1 + (r_2 + r_3)) \end{eqnarray*} +\noindent +That means both languages are the same. The point of the definition of $L$ is that we can use it to precisely specify when a string $s$ is matched by a regular expression $r$, namely if and only if $s \in L(r)$. In fact we @@ -715,7 +717,7 @@ expressions and the notion of derivatives. Earlier versions of this theorem used always automata in the proof. Using this theorem we can show that regular languages are closed under -complementation, something which Gasarch in his +complementation, something which Bill Gasarch in his Computational Complexity blog\footnote{\url{http://goo.gl/2R11Fw}} assumed can only be shown via automata. So even somebody who has written a 700+-page book\footnote{\url{http://goo.gl/fD0eHx}} on regular diff -r dc3c35673e94 -r dbf9d710ce65 handouts/notation.pdf Binary file handouts/notation.pdf has changed diff -r dc3c35673e94 -r dbf9d710ce65 handouts/notation.tex --- a/handouts/notation.tex Mon Aug 30 15:50:27 2021 +0100 +++ b/handouts/notation.tex Tue Aug 31 11:49:09 2021 +0100 @@ -1,7 +1,7 @@ \documentclass{article} \usepackage{../style} \usepackage{../langs} - +\usepackage{../graphics} \begin{document} @@ -232,7 +232,7 @@ \ldots \] -\noindent but using the big union notation is more concise. +\noindent but using the big union notation is more concise.\medskip As an aside: While this stuff about sets might all look trivial or even needlessly pedantic, \emph{Nature} is never simple. If you want @@ -253,7 +253,9 @@ \end{center} \noindent -contain actually the same amount of elements. Does this make sense? +contain actually the same amount of elements. Does this make sense to you? +If yes, good. If not, then something to learn about. + Though this might all look strange, infinite sets will be a topic that is very relevant to the material of this module. It tells us what we can compute with a computer (actually an algorithm) and what