pep-material: comparison cws/cw03.tex

equal deleted inserted replaced

-:15f1fca879c5
+:94b11ac19b41
 \begin{center}
 \begin{tabular}{lcll}
 $r$ & $::=$ & $\ZERO$     & cannot match anything\\
 &   $|$ & $\ONE$      & can only match the empty string\\
-&   $|$ & $c$         & can match a character (in this case $c$)\\
+&   $|$ & $c$         & can match a single character (in this case $c$)\\
 &   $|$ & $r_1 + r_2$ & can match a string either with $r_1$ or with $r_2$\\
 &   $|$ & $r_1\cdot r_2$ & can match the first part of a string with $r_1$ and\\
 &  & & then the second part with $r_2$\\
 &   $|$ & $r^*$       & can match zero or more times $r$\\
 \end{tabular}
 \item[$\bullet$] \url{http://davidvgalbraith.com/how-i-fixed-atom/}
 \end{itemize}}
 \subsubsection*{Tasks (file re.scala)}
+The file \texttt{re.scala} has already a definition for regular
+expressions and also defines some handy shorthand notation for
+regular expressions. The notation in this document matches up
+with the code in the file as follows:
+\begin{center}
+\begin{tabular}{rcl@{\hspace{10mm}}l}
+& & code: & shorthand:\smallskip \\
+$\ZERO$ & $\mapsto$ & \texttt{ZERO}\\
+$\ONE$  & $\mapsto$ & \texttt{ONE}\\
+$c$     & $\mapsto$ & \texttt{CHAR(c)}\\
+$r_1 + r_2$ & $\mapsto$ & \texttt{ALT(r1, r2)} & \texttt{r1 | r2}\\
+$r_1 \cdot r_2$ & $\mapsto$ & \texttt{SEQ(r1, r2)} & \texttt{r1 $\sim$ r2}\\
+$r^*$ & $\mapsto$ &  \texttt{STAR(r)} & \texttt{r.\%}
+\end{tabular}
+\end{center}
 \begin{itemize}
 \item[(1a)] Implement a function, called \textit{nullable}, by
 recursion over regular expressions. This function tests whether a
 regular expression can match the empty string. This means given a
-regular expression it either returns true or false.
+regular expression it either returns true or false. The function
+\textit{nullable}
+is defined as follows:
 \begin{center}
 \begin{tabular}{lcl}
 $\textit{nullable}(\ZERO)$ & $\dn$ & $\textit{false}$\\
 $\textit{nullable}(\ONE)$  & $\dn$ & $\textit{true}$\\
 $\textit{nullable}(c)$     & $\dn$ & $\textit{false}$\\
 $\textit{nullable}(r_1 + r_2)$ & $\dn$ & $\textit{nullable}(r_1) \vee \textit{nullable}(r_2)$\\
 $\textit{nullable}(r_1 \cdot r_2)$ & $\dn$ & $\textit{nullable}(r_1) \wedge \textit{nullable}(r_2)$\\
 $\textit{nullable}(r^*)$ & $\dn$ & $\textit{true}$\\
 \end{tabular}
-\end{center}\hfill[1 Mark]
+\end{center}~\hfill[1 Mark]
 \item[(1b)] Implement a function, called \textit{der}, by recursion over
 regular expressions. It takes a character and a regular expression
 as arguments and calculates the derivative regular expression according
 to the rules:
 a regular expression that can match the empty string. You can test
 whether this is indeed the case using the function nullable, which is
 what your matcher is doing.
 The purpose of the $\textit{simp}$ function is to keep the regular
-expression small. Normally the derivative function makes the regular
+expressions small. Normally the derivative function makes the regular
 expression bigger (see the SEQ case and the example in (1b)) and the
 algorithm would be slower and slower over time. The $\textit{simp}$
 function counters this increase in size and the result is that the
 algorithm is fast throughout.  By the way, this algorithm is by Janusz
 Brzozowski who came up with the idea of derivatives in 1964 in his PhD
 \url{https://en.wikipedia.org/wiki/Janusz_Brzozowski_(computer_scientist)}
 \end{center}
 If you want to see how badly the regular expression matchers do in
-Java\footnote{Version 8 and below} and in Python with the `evil' regular
+Java\footnote{Version 8 and below; Version 9 does not seem to be as
+catastrophic, but still worse than the regular expression matcher
+based on derivatives.} and in Python with the `evil' regular
 expression $(a^*)^*\cdot b$, then have a look at the graphs below (you
 can try it out for yourself: have a look at the file
 \texttt{catastrophic.java} and \texttt{catastrophic.py} on
 KEATS). Compare this with the matcher you have implemented. How long
 can the string of $a$'s be in your matcher and still stay within the
 ymax=35,
 ytick={0,5,...,30},
 scaled ticks=false,
 axis lines=left,
 width=6cm,
-height=5.0cm,
+height=5.5cm,
 legend entries={Python, Java 8},
 legend pos=outer north east]
 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
 \end{axis}
 computer pioneer, who unfortunately died a few months ago. The main
 feature of brainf*** is its minimalistic set of instructions---just 8
 instructions in total and all of which are single characters. Despite
 the minimalism, this language has been shown to be Turing
 complete\ldots{}if this doesn't ring any bell with you: it roughly
-that means every algorithm we know can, in principle, be implemented in
+means that every algorithm we know can, in principle, be implemented in
 brainf***. It just takes a lot of determination and quite a lot of
 memory resources. Some relatively sophisticated sample programs in
 brainf*** are given in the file \texttt{bf.scala}.\bigskip
 \noindent
 \begin{itemize}
 \item[(2a)] Brainf*** memory is represented by a \texttt{Map} from
 integers to integers. The empty memory is represented by
 \texttt{Map()}, that is nothing is stored in the
-memory. \texttt{Map(0 -> 1, 2 -> 3)} clearly has stored \texttt{1}
+memory. \texttt{Map(0 -> 1, 2 -> 3)} clearly stores \texttt{1} at
-at memory location \texttt{0}; at \texttt{2} it stores
+memory location \texttt{0}; at \texttt{2} it stores \texttt{3}. The
-\texttt{3}. The convention is that if we query the memory at a
+convention is that if we query the memory at a location that is
-location that is not defined in the \texttt{Map}, we return
+\emph{not} defined in the \texttt{Map}, we return \texttt{0}. Write
-\texttt{0}. Write a function, \texttt{sread}, that takes a memory (a
+a function, \texttt{sread}, that takes a memory (a \texttt{Map}) and
-\texttt{Map}) and a memory pointer (an \texttt{Int}) as argument,
+a memory pointer (an \texttt{Int}) as argument, and safely reads the
-and safely reads the corresponding memory location. If the map is not
+corresponding memory location. If the \texttt{Map} is not defined at
-defined at the memory pointer, \texttt{sread} returns \texttt{0}.
+the memory pointer, \texttt{sread} returns \texttt{0}.
 Write another function \texttt{write}, which takes a memory, a
-memory pointer and an integer value as argument and updates the map
+memory pointer and an integer value as argument and updates the
-with the value at the given memory location. As usual the map is not
+\texttt{Map} with the value at the given memory location. As usual
-updated `in-place' but a new map is created with the same data,
+the \texttt{Map} is not updated `in-place' but a new map is created
-except the value is stored at the given memory pointer.\hfill[1 Mark]
+with the same data, except the value is stored at the given memory
+pointer.\hfill[1 Mark]
 \item[(2b)] Write two functions, \texttt{jumpRight} and
 \texttt{jumpLeft} that are needed to implement the loop constructs
 of brainf***. They take a program (a \texttt{String}) and a program
 counter (an \texttt{Int}) as argument and move right (respectively
 \begin{center}
 \texttt{--[..+>--]\barbelow{,}>,++}
 \end{center}
-meaning it jumps to after the loop. Similarly, if you in 8th position
+meaning it jumps to after the loop. Similarly, if you are in 8th position
 then \texttt{jumpLeft} is supposed to jump to just after the opening
 bracket (that is jumping to the beginning of the loop):
 \begin{center}
 \texttt{--[..+>-\barbelow{-}],>,++}
 $\bullet$ & \texttt{mem} updated with \texttt{mp -> mem(mp) - 1}\\
 \end{tabular}\\\hline
 \hfill\texttt{'.'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
 $\bullet$ & $\texttt{pc} + 1$\\
 $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
-$\bullet$ & print out\texttt{mem(mp)} as a character\\
+$\bullet$ & print out \,\texttt{mem(mp)} as a character\\
 \end{tabular}\\\hline
 \hfill\texttt{','} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
 $\bullet$ & $\texttt{pc} + 1$\\
 $\bullet$ & $\texttt{mp}$ unchanged\\
 $\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\
-\multicolumn{2}{@{}l}{input given by \texttt{Console.in.read().toByte}}
+\multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}}
 \end{tabular}\\\hline
 \hfill\texttt{'['} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
 \multicolumn{2}{@{}l}{if \texttt{mem(mp) == 0} then}\\
 $\bullet$ & $\texttt{pc = jumpRight(prog, pc + 1, 0)}$\\
 $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\

changeset 158	94b11ac19b41
parent 157	15f1fca879c5
child 159	92c31cbb1952