Binary file cws/cw04.pdf has changed
--- a/cws/cw04.tex Fri Nov 23 01:52:37 2018 +0000
+++ b/cws/cw04.tex Tue Nov 27 21:41:59 2018 +0000
@@ -1,184 +1,646 @@
\documentclass{article}
\usepackage{../style}
\usepackage{../langs}
+\usepackage{disclaimer}
+\usepackage{tikz}
+\usepackage{pgf}
+\usepackage{pgfplots}
+\usepackage{stackengine}
+%% \usepackage{accents}
+\newcommand\barbelow[1]{\stackunder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}}
+
+\begin{filecontents}{re-python2.data}
+1 0.033
+5 0.036
+10 0.034
+15 0.036
+18 0.059
+19 0.084
+20 0.141
+21 0.248
+22 0.485
+23 0.878
+24 1.71
+25 3.40
+26 7.08
+27 14.12
+28 26.69
+\end{filecontents}
+
+\begin{filecontents}{re-java.data}
+5 0.00298
+10 0.00418
+15 0.00996
+16 0.01710
+17 0.03492
+18 0.03303
+19 0.05084
+20 0.10177
+21 0.19960
+22 0.41159
+23 0.82234
+24 1.70251
+25 3.36112
+26 6.63998
+27 13.35120
+28 29.81185
+\end{filecontents}
+
+\begin{filecontents}{re-java9.data}
+1000 0.01410
+2000 0.04882
+3000 0.10609
+4000 0.17456
+5000 0.27530
+6000 0.41116
+7000 0.53741
+8000 0.70261
+9000 0.93981
+10000 0.97419
+11000 1.28697
+12000 1.51387
+14000 2.07079
+16000 2.69846
+20000 4.41823
+24000 6.46077
+26000 7.64373
+30000 9.99446
+34000 12.966885
+38000 16.281621
+42000 19.180228
+46000 21.984721
+50000 26.950203
+60000 43.0327746
+\end{filecontents}
+
\begin{document}
-\section*{Replacement Coursework 1 (Roman Numerals)}
+% BF IDE
+% https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5
+
+\section*{Coursework 8 (Regular Expressions and Brainf***)}
-This coursework is worth 10\%. It is about translating roman numerals
-into integers and also about validating roman numerals. The coursework
-is due on 2 February at 5pm. Make sure the files you submit can be
-processed by just calling \texttt{scala <<filename.scala>>}.\bigskip
+This coursework is worth 10\%. It is about regular expressions,
+pattern matching and an interpreter. The first part is due on 30
+November at 11pm; the second, more advanced part, is due on 21
+December at 11pm. In the first part, you are asked to implement a
+regular expression matcher based on derivatives of regular
+expressions. The reason is that regular expression matching in Java
+and Python can sometimes be extremely slow. The advanced part is about
+an interpreter for a very simple programming language.\bigskip
+
+\IMPORTANT{}
\noindent
-\textbf{Important:} Do not use any mutable data structures in your
-submission! They are not needed. This menas you cannot use
-\texttt{ListBuffer}s, for example. Do not use \texttt{return} in your
-code! It has a different meaning in Scala, than in Java. Do not use
-\texttt{var}! This declares a mutable variable. Make sure the
-functions you submit are defined on the ``top-level'' of Scala, not
-inside a class or object. Also note that the running time will be
-restricted to a maximum of 360 seconds on my laptop.
+Also note that the running time of each part will be restricted to a
+maximum of 30 seconds on my laptop.
+
+\DISCLAIMER{}
-\subsection*{Disclaimer}
+\subsection*{Part 1 (6 Marks)}
+
+The task is to implement a regular expression matcher that is based on
+derivatives of regular expressions. Most of the functions are defined by
+recursion over regular expressions and can be elegantly implemented
+using Scala's pattern-matching. The implementation should deal with the
+following regular expressions, which have been predefined in the file
+\texttt{re.scala}:
-It should be understood that the work you submit represents your own
-effort! You have not copied from anyone else. An exception is the
-Scala code I showed during the lectures or uploaded to KEATS, which
-you can freely use.\bigskip
-
+\begin{center}
+\begin{tabular}{lcll}
+ $r$ & $::=$ & $\ZERO$ & cannot match anything\\
+ & $|$ & $\ONE$ & can only match the empty string\\
+ & $|$ & $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}
+\end{center}
-\subsection*{Part 1 (Translation)}
+\noindent
+Why? Knowing how to match regular expressions and strings will let you
+solve a lot of problems that vex other humans. Regular expressions are
+one of the fastest and simplest ways to match patterns in text, and
+are endlessly useful for searching, editing and analysing data in all
+sorts of places (for example analysing network traffic in order to
+detect security breaches). However, you need to be fast, otherwise you
+will stumble over problems such as recently reported at
+
+{\small
+\begin{itemize}
+\item[$\bullet$] \url{http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}
+\item[$\bullet$] \url{https://vimeo.com/112065252}
+\item[$\bullet$] \url{http://davidvgalbraith.com/how-i-fixed-atom/}
+\end{itemize}}
+
+\subsubsection*{Tasks (file re.scala)}
-\noindent
-Roman numerals are strings consisting of the letters $I$, $V$, $X$,
-$L$, $C$, $D$, and $M$. Such strings should be transformed into an
-internal representation using the datatypes \texttt{RomanDigit} and
-\texttt{RomanNumeral} (defined in \texttt{roman.scala}), and then from
-this internal representation converted into Integers.
+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[(1)] First write a polymorphic function that recursively
- transforms a list of options into an option of a list. For example,
- if you have the lists on the left-hand side, they should be transformed into
- the options on the right-hand side:
+\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. 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]
- \begin{center}
- \begin{tabular}{lcl}
- \texttt{List(Some(1), Some(2), Some(3))} & $\Rightarrow$ &
- \texttt{Some(List(1, 2, 3))} \\
- \texttt{List(Some(1), None, Some(3))} & $\Rightarrow$ &
- \texttt{None} \\
- \texttt{List()} & $\Rightarrow$ & \texttt{Some(List())}
- \end{tabular}
- \end{center}
+\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:
- This means the function should produce \texttt{None} as soon
- as a \texttt{None} is inside the list. Otherwise it produces
- a list of all \texttt{Some}s. In case the list is empty, it
- produces \texttt{Some} of the empty list. \hfill[1 Mark]
+\begin{center}
+\begin{tabular}{lcl}
+$\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\
+$\textit{der}\;c\;(\ONE)$ & $\dn$ & $\ZERO$\\
+$\textit{der}\;c\;(d)$ & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;\ONE \; \textit{else} \;\ZERO$\\
+$\textit{der}\;c\;(r_1 + r_2)$ & $\dn$ & $(\textit{der}\;c\;r_1) + (\textit{der}\;c\;r_2)$\\
+$\textit{der}\;c\;(r_1 \cdot r_2)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r_1)$\\
+ & & $\textit{then}\;((\textit{der}\;c\;r_1)\cdot r_2) + (\textit{der}\;c\;r_2)$\\
+ & & $\textit{else}\;(\textit{der}\;c\;r_1)\cdot r_2$\\
+$\textit{der}\;c\;(r^*)$ & $\dn$ & $(\textit{der}\;c\;r)\cdot (r^*)$\\
+\end{tabular}
+\end{center}
+
+For example given the regular expression $r = (a \cdot b) \cdot c$, the derivatives
+w.r.t.~the characters $a$, $b$ and $c$ are
-
-\item[(2)] Write first a function that converts the characters $I$, $V$,
- $X$, $L$, $C$, $D$, and $M$ into an option of a \texttt{RomanDigit}.
- If it is one of the roman digits, it should produce \texttt{Some};
- otherwise \texttt{None}.
-
- Next write a function that converts a string into a
- \texttt{RomanNumeral}. Again, this function should return an
- \texttt{Option}: If the string consists of $I$, $V$, $X$, $L$, $C$,
- $D$, and $M$ only, then it produces \texttt{Some}; otherwise if
- there is any other character in the string, it should produce
- \texttt{None}. The empty string is just the empty
- \texttt{RomanNumeral}, that is the empty list of
- \texttt{RomanDigit}'s. You should use the function under Task (1)
- to produce the result. \hfill[2 Marks]
+\begin{center}
+ \begin{tabular}{lcll}
+ $\textit{der}\;a\;r$ & $=$ & $(\ONE \cdot b)\cdot c$ & ($= r'$)\\
+ $\textit{der}\;b\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$\\
+ $\textit{der}\;c\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$
+ \end{tabular}
+\end{center}
+
+Let $r'$ stand for the first derivative, then taking the derivatives of $r'$
+w.r.t.~the characters $a$, $b$ and $c$ gives
+
+\begin{center}
+ \begin{tabular}{lcll}
+ $\textit{der}\;a\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$ \\
+ $\textit{der}\;b\;r'$ & $=$ & $((\ZERO \cdot b) + \ONE)\cdot c$ & ($= r''$)\\
+ $\textit{der}\;c\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$
+ \end{tabular}
+\end{center}
-\item[(3)] Write a recursive function \texttt{RomanNumral2Int} that
- converts a \texttt{RomanNumeral} into an integer. You can assume the
- generated integer will be between 0 and 3999. The argument of the
- function is a list of roman digits. It should look how this list
- starts and then calculate what the corresponding integer is for this
- ``start'' and add it with the integer for the rest of the list. That
- means if the argument is of the form shown on the left-hand side, it
- should do the calculation on the right-hand side.
+One more example: Let $r''$ stand for the second derivative above,
+then taking the derivatives of $r''$ w.r.t.~the characters $a$, $b$
+and $c$ gives
+
+\begin{center}
+ \begin{tabular}{lcll}
+ $\textit{der}\;a\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$ \\
+ $\textit{der}\;b\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$\\
+ $\textit{der}\;c\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ONE$ &
+ (is $\textit{nullable}$)
+ \end{tabular}
+\end{center}
+
+Note, the last derivative can match the empty string, that is it is \textit{nullable}.\\
+\mbox{}\hfill\mbox{[1 Mark]}
+
+\item[(1c)] Implement the function \textit{simp}, which recursively
+ traverses a regular expression from the inside to the outside, and
+ on the way simplifies every regular expression on the left (see
+ below) to the regular expression on the right, except it does not
+ simplify inside ${}^*$-regular expressions.
\begin{center}
- \begin{tabular}{lcl}
- $M::r$ & $\Rightarrow$ & $1000 + \text{roman numeral of rest}\; r$\\
- $C::M::r$ & $\Rightarrow$ & $900 + \text{roman numeral of rest}\; r$\\
- $D::r$ & $\Rightarrow$ & $500 + \text{roman numeral of rest}\; r$\\
- $C::D::r$ & $\Rightarrow$ & $400 + \text{roman numeral of rest}\; r$\\
- $C::r$ & $\Rightarrow$ & $100 + \text{roman numeral of rest}\; r$\\
- $X::C::r$ & $\Rightarrow$ & $90 + \text{roman numeral of rest}\; r$\\
- $L::r$ & $\Rightarrow$ & $50 + \text{roman numeral of rest}\; r$\\
- $X::L::r$ & $\Rightarrow$ & $40 + \text{roman numeral of rest}\; r$\\
- $X::r$ & $\Rightarrow$ & $10 + \text{roman numeral of rest}\; r$\\
- $I::X::r$ & $\Rightarrow$ & $9 + \text{roman numeral of rest}\; r$\\
- $V::r$ & $\Rightarrow$ & $5 + \text{roman numeral of rest}\; r$\\
- $I::V::r$ & $\Rightarrow$ & $4 + \text{roman numeral of rest}\; r$\\
- $I::r$ & $\Rightarrow$ & $1 + \text{roman numeral of rest}\; r$
- \end{tabular}
- \end{center}
-
- The empty list will be converted to integer $0$.\hfill[1 Mark]
-
-\item[(4)] Write a function that takes a string and if possible
- converts it into the internal representation. If successful, it then
- calculates the integer (an option of an integer) according to the
- function in (3). If this is not possible, then return
- \texttt{None}.\hfill[1 Mark]
-
-
-\item[(5)] The file \texttt{roman.txt} contains a list of roman numerals.
- Read in these numerals, convert them into integers and then add them all
- up. The Scala function for reading a file is
-
- \begin{center}
- \texttt{Source.fromFile("filename")("ISO-8859-9")}
+\begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll}
+$r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\
+$\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\
+$r \cdot \ONE$ & $\mapsto$ & $r$\\
+$\ONE \cdot r$ & $\mapsto$ & $r$\\
+$r + \ZERO$ & $\mapsto$ & $r$\\
+$\ZERO + r$ & $\mapsto$ & $r$\\
+$r + r$ & $\mapsto$ & $r$\\
+\end{tabular}
\end{center}
- Make sure you process the strings correctly by ignoring whitespaces
- where needed.\\ \mbox{}\hfill[1 Mark]
+ For example the regular expression
+ \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\]
+
+ simplifies to just $r_1$. \textbf{Hint:} Regular expressions can be
+ seen as trees and there are several methods for traversing
+ trees. One of them corresponds to the inside-out traversal, which is
+ sometimes also called post-order traversal. Furthermore,
+ remember numerical expressions from school times: there you had expressions
+ like $u + \ldots + (1 \cdot x) - \ldots (z + (y \cdot 0)) \ldots$
+ and simplification rules that looked very similar to rules
+ above. You would simplify such numerical expressions by replacing
+ for example the $y \cdot 0$ by $0$, or $1\cdot x$ by $x$, and then
+ look whether more rules are applicable. If you organise the
+ simplification in an inside-out fashion, it is always clear which
+ rule should be applied next.\hfill[2 Marks]
+
+\item[(1d)] Implement two functions: The first, called \textit{ders},
+ takes a list of characters and a regular expression as arguments, and
+ builds the derivative w.r.t.~the list as follows:
+
+\begin{center}
+\begin{tabular}{lcl}
+$\textit{ders}\;(Nil)\;r$ & $\dn$ & $r$\\
+ $\textit{ders}\;(c::cs)\;r$ & $\dn$ &
+ $\textit{ders}\;cs\;(\textit{simp}(\textit{der}\;c\;r))$\\
+\end{tabular}
+\end{center}
+
+Note that this function is different from \textit{der}, which only
+takes a single character.
+
+The second function, called \textit{matcher}, takes a string and a
+regular expression as arguments. It builds first the derivatives
+according to \textit{ders} and after that tests whether the resulting
+derivative regular expression can match the empty string (using
+\textit{nullable}). For example the \textit{matcher} will produce
+true for the regular expression $(a\cdot b)\cdot c$ and the string
+$abc$, but false if you give it the string $ab$. \hfill[1 Mark]
+
+\item[(1e)] Implement a function, called \textit{size}, by recursion
+ over regular expressions. If a regular expression is seen as a tree,
+ then \textit{size} should return the number of nodes in such a
+ tree. Therefore this function is defined as follows:
+
+\begin{center}
+\begin{tabular}{lcl}
+$\textit{size}(\ZERO)$ & $\dn$ & $1$\\
+$\textit{size}(\ONE)$ & $\dn$ & $1$\\
+$\textit{size}(c)$ & $\dn$ & $1$\\
+$\textit{size}(r_1 + r_2)$ & $\dn$ & $1 + \textit{size}(r_1) + \textit{size}(r_2)$\\
+$\textit{size}(r_1 \cdot r_2)$ & $\dn$ & $1 + \textit{size}(r_1) + \textit{size}(r_2)$\\
+$\textit{size}(r^*)$ & $\dn$ & $1 + \textit{size}(r)$\\
+\end{tabular}
+\end{center}
+
+You can use \textit{size} in order to test how much the `evil' regular
+expression $(a^*)^* \cdot b$ grows when taking successive derivatives
+according the letter $a$ without simplification and then compare it to
+taking the derivative, but simplify the result. The sizes
+are given in \texttt{re.scala}. \hfill[1 Mark]
\end{itemize}
+\subsection*{Background}
+
+Although easily implementable in Scala, the idea behind the derivative
+function might not so easy to be seen. To understand its purpose
+better, assume a regular expression $r$ can match strings of the form
+$c\!::\!cs$ (that means strings which start with a character $c$ and have
+some rest, or tail, $cs$). If you take the derivative of $r$ with
+respect to the character $c$, then you obtain a regular expression
+that can match all the strings $cs$. In other words, the regular
+expression $\textit{der}\;c\;r$ can match the same strings $c\!::\!cs$
+that can be matched by $r$, except that the $c$ is chopped off.
+
+Assume now $r$ can match the string $abc$. If you take the derivative
+according to $a$ then you obtain a regular expression that can match
+$bc$ (it is $abc$ where the $a$ has been chopped off). If you now
+build the derivative $\textit{der}\;b\;(\textit{der}\;a\;r)$ you
+obtain a regular expression that can match the string $c$ (it is $bc$
+where $b$ is chopped off). If you finally build the derivative of this
+according $c$, that is
+$\textit{der}\;c\;(\textit{der}\;b\;(\textit{der}\;a\;r))$, you obtain
+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
+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
+thesis.
+
+\begin{center}\small
+\url{https://en.wikipedia.org/wiki/Janusz_Brzozowski_(computer_scientist)}
+\end{center}
+
-\subsection*{Part 2 (Validation)}
+If you want to see how badly the regular expression matchers do in
+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
+30 seconds time limit?
-As you can see the function under Task (3) can produce some unexpected
-results. For example for $XXCIII$ it produces 103. The reason for this
-unexpected result is that $XXCIII$ is actually not a valid roman
-number, neither is $IIII$ for 4 nor $MIM$ for 1999. Although actual
-Romans were not so fussy about this,\footnote{They happily used
- numbers like $XIIX$ or $IIXX$ for 18.} but modern times declared
-that there are precise rules for what a valid roman number is, namely:
+\begin{center}
+\begin{tabular}{@{}cc@{}}
+\multicolumn{2}{c}{Graph: $(a^*)^*\cdot b$ and strings
+ $\underbrace{a\ldots a}_{n}$}\bigskip\\
+
+\begin{tikzpicture}
+\begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
+ ylabel={time in secs},
+ y label style={at={(0.06,0.5)}},
+ enlargelimits=false,
+ xtick={0,5,...,30},
+ xmax=33,
+ ymax=45,
+ ytick={0,5,...,40},
+ scaled ticks=false,
+ axis lines=left,
+ width=6cm,
+ height=5.5cm,
+ legend entries={Python, Java 8},
+ legend pos=north west]
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+\end{axis}
+\end{tikzpicture}
+ &
+\begin{tikzpicture}
+\begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
+ ylabel={time in secs},
+ y label style={at={(0.06,0.5)}},
+ %enlargelimits=false,
+ %xtick={0,5000,...,30000},
+ xmax=65000,
+ ymax=45,
+ ytick={0,5,...,40},
+ scaled ticks=false,
+ axis lines=left,
+ width=6cm,
+ height=5.5cm,
+ legend entries={Java 9},
+ legend pos=north west]
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data};
+\end{axis}
+\end{tikzpicture}
+\end{tabular}
+\end{center}
+\newpage
+
+\subsection*{Part 2 (4 Marks)}
+
+Coming from Java or C++, you might think Scala is a quite esoteric
+programming language. But remember, some serious companies have built
+their business on
+Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}}
+And there are far, far more esoteric languages out there. One is
+called \emph{brainf***}. You are asked in this part to implement an
+interpreter for this language.
+
+Urban M\"uller developed brainf*** in 1993. A close relative of this
+language was already introduced in 1964 by Corado B\"ohm, an Italian
+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
+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
+As mentioned above, brainf*** has 8 single-character commands, namely
+\texttt{'>'}, \texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'},
+\texttt{','}, \texttt{'['} and \texttt{']'}. Every other character is
+considered a comment. Brainf*** operates on memory cells containing
+integers. For this it uses a single memory pointer that points at each
+stage to one memory cell. This pointer can be moved forward by one
+memory cell by using the command \texttt{'>'}, and backward by using
+\texttt{'<'}. The commands \texttt{'+'} and \texttt{'-'} increase,
+respectively decrease, by 1 the content of the memory cell to which
+the memory pointer currently points to. The commands for input/output
+are \texttt{','} and \texttt{'.'}. Output works by reading the content
+of the memory cell to which the memory pointer points to and printing
+it out as an ASCII character. Input works the other way, taking some
+user input and storing it in the cell to which the memory pointer
+points to. The commands \texttt{'['} and \texttt{']'} are looping
+constructs. Everything in between \texttt{'['} and \texttt{']'} is
+repeated until a counter (memory cell) reaches zero. A typical
+program in brainf*** looks as follows:
+
+\begin{center}
+\begin{verbatim}
+ ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
+ ..+++.>>.<-.<.+++.------.--------.>>+.>++.
+\end{verbatim}
+\end{center}
+
+\noindent
+This one prints out Hello World\ldots{}obviously.
+
+\subsubsection*{Tasks (file bf.scala)}
\begin{itemize}
-\item Repeatable roman digits are $I$, $X$, $C$ and $M$. The other ones
- are non-repeatable. Repeatable digits can be repeated upto 3 times in a
- number (for example $MMM$ is OK); non-repeatable digits cannot be
- repeated at all (for example $VV$ is excluded).
+\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 stores \texttt{1} at
+ memory location \texttt{0}; at \texttt{2} it stores \texttt{3}. The
+ convention is that if we query the memory at a location that is
+ \emph{not} defined in the \texttt{Map}, we return \texttt{0}. Write
+ a function, \texttt{sread}, that takes a memory (a \texttt{Map}) and
+ a memory pointer (an \texttt{Int}) as argument, and safely reads the
+ corresponding memory location. If the \texttt{Map} is not defined at
+ 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
+ \texttt{Map} with the value at the given memory location. As usual
+ the \texttt{Map} is not updated `in-place' but a new map is created
+ 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
+ left) in the string in order to find the \textbf{matching}
+ opening/closing bracket. For example, given the following program
+ with the program counter indicated by an arrow:
+
+ \begin{center}
+ \texttt{--[\barbelow{.}.+>--],>,++}
+ \end{center}
+
+ then the matching closing bracket is in 9th position (counting from 0) and
+ \texttt{jumpRight} is supposed to return the position just after this
-\item If a smaller digits precedes a bigger digit, then $I$ can precede $V$ and $X$; $X$ can preced
- $L$ and $C$; and $C$ can preced $D$ and $M$. No other combination is permitted in this case.
+ \begin{center}
+ \texttt{--[..+>--]\barbelow{,}>,++}
+ \end{center}
+
+ 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):
-\item If a smaller digit precedes a bigger digit (for example $IV$), then the smaller number
- must be either the first digit in the number, or follow a digit which is at least 10 times its value.
- So $VIV$ is excluded, because $I$ follows $V$ and $I * 10$ is bigger than $V$; but $XIV$ is
- allowed, because $I$ follows $X$ and $I * 10$ is equal to $X$.
+ \begin{center}
+ \texttt{--[..+>-\barbelow{-}],>,++}
+ \qquad$\stackrel{\texttt{jumpLeft}}{\longrightarrow}$\qquad
+ \texttt{--[\barbelow{.}.+>--],>,++}
+ \end{center}
+
+ Unfortunately we have to take into account that there might be
+ other opening and closing brackets on the `way' to find the
+ matching bracket. For example in the brainf*** program
+
+ \begin{center}
+ \texttt{--[\barbelow{.}.[+>]--],>,++}
+ \end{center}
-\item Let us say two digits are called a \emph{compound} roman digit
- when a smaller digit precedes a bigger digit (so $IV$, $XL$, $CM$
- for example). If a compound digit is followed by another digit, then
- this digit must be smaller than the first digit in the compound
- digit. For example $IXI$ is excluded, but $XLI$ is not.
+ we do not want to return the index for the \texttt{'-'} in the 9th
+ position, but the program counter for \texttt{','} in 12th
+ position. The easiest to find out whether a bracket is matched is by
+ using levels (which are the third argument in \texttt{jumpLeft} and
+ \texttt{jumpLeft}). In case of \texttt{jumpRight} you increase the
+ level by one whenever you find an opening bracket and decrease by
+ one for a closing bracket. Then in \texttt{jumpRight} you are looking
+ for the closing bracket on level \texttt{0}. For \texttt{jumpLeft} you
+ do the opposite. In this way you can find \textbf{matching} brackets
+ in strings such as
+
+ \begin{center}
+ \texttt{--[\barbelow{.}.[[-]+>[.]]--],>,++}
+ \end{center}
-\item The empty roman numeral is valid.
-\end{itemize}
+ for which \texttt{jumpRight} should produce the position:
+
+ \begin{center}
+ \texttt{--[..[[-]+>[.]]--]\barbelow{,}>,++}
+ \end{center}
+
+ It is also possible that the position returned by \texttt{jumpRight} or
+ \texttt{jumpLeft} is outside the string in cases where there are
+ no matching brackets. For example
+
+ \begin{center}
+ \texttt{--[\barbelow{.}.[[-]+>[.]]--,>,++}
+ \qquad$\stackrel{\texttt{jumpRight}}{\longrightarrow}$\qquad
+ \texttt{--[..[[-]+>[.]]-->,++\barbelow{\;\phantom{+}}}
+ \end{center}
+ \hfill[1 Mark]
-\noindent
-The tasks in this part are as follows:
-\begin{itemize}
-\item[(6)] Implement a recursive function \texttt{isValidNumeral} that
- takes a \texttt{RomanNumeral} as argument and produces true if \textbf{all}
- the rules above are satisfied, and otherwise false.
+\item[(2c)] Write a recursive function \texttt{run} that executes a
+ brainf*** program. It takes a program, a program counter, a memory
+ pointer and a memory as arguments. If the program counter is outside
+ the program string, the execution stops and \texttt{run} returns the
+ memory. If the program counter is inside the string, it reads the
+ corresponding character and updates the program counter \texttt{pc},
+ memory pointer \texttt{mp} and memory \texttt{mem} according to the
+ rules shown in Figure~\ref{comms}. It then calls recursively
+ \texttt{run} with the updated data.
+
+ Write another function \texttt{start} that calls \texttt{run} with a
+ given brainfu** program and memory, and the program counter and memory pointer
+ set to~$0$. Like \texttt{run} it returns the memory after the execution
+ of the program finishes. You can test your brainf**k interpreter with the
+ Sierpinski triangle or the Hello world programs or have a look at
- Hint: It might be more convenient to test when the rules fail and then return false;
- return true in all other cases.
- \mbox{}\hfill[2 Marks]
-
-\item[(7)] Write a recursive function that converts an Integer into a \texttt{RomanNumeral}.
- You can assume the function will only be called for integers between 0 and 3999.\mbox{}\hfill[1 Mark]
+ \begin{center}
+ \url{https://esolangs.org/wiki/Brainfuck}
+ \end{center}\hfill[2 Marks]
-\item[(8)] Write a function that reads a text file (for example \texttt{roman2.txt})
- containing valid and invalid roman numerals. Convert all valid roman numerals into
- integers, add them up and produce the result as a \texttt{RomanNumeral} (using the function
- from (7)). \hfill[1 Mark]
-\end{itemize}
-
+ \begin{figure}[p]
+ \begin{center}
+ \begin{tabular}{|@{}p{0.8cm}|l|}
+ \hline
+ \hfill\texttt{'>'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
+ $\bullet$ & $\texttt{pc} + 1$\\
+ $\bullet$ & $\texttt{mp} + 1$\\
+ $\bullet$ & \texttt{mem} unchanged
+ \end{tabular}\\\hline
+ \hfill\texttt{'<'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
+ $\bullet$ & $\texttt{pc} + 1$\\
+ $\bullet$ & $\texttt{mp} - 1$\\
+ $\bullet$ & \texttt{mem} unchanged
+ \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 -> mem(mp) + 1}\\
+ \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 -> 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\\
+ \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}{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\\
+ \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) != 0} then}\\
+ $\bullet$ & $\texttt{pc} + 1$\\
+ $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
+ \end{tabular}
+ \\\hline
+ \hfill\texttt{']'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
+ \multicolumn{2}{@{}l}{if \texttt{mem(mp) != 0} then}\\
+ $\bullet$ & $\texttt{pc = jumpLeft(prog, pc - 1, 0)}$\\
+ $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\
+ \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) == 0} then}\\
+ $\bullet$ & $\texttt{pc} + 1$\\
+ $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
+ \end{tabular}\\\hline
+ any other char & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
+ $\bullet$ & $\texttt{pc} + 1$\\
+ $\bullet$ & \texttt{mp} and \texttt{mem} unchanged
+ \end{tabular}\\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{The rules for how commands in the brainf*** language update the program counter \texttt{pc},
+ memory pointer \texttt{mp} and memory \texttt{mem}.\label{comms}}
+ \end{figure}
+\end{itemize}\bigskip
+
+
+
\end{document}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/cw07.tex Tue Nov 27 21:41:59 2018 +0000
@@ -0,0 +1,189 @@
+\documentclass{article}
+\usepackage{../style}
+\usepackage{../langs}
+
+\begin{document}
+
+\section*{Replacement Coursework 1 (Roman Numerals)}
+
+This coursework is worth 10\%. It is about translating roman numerals
+into integers and also about validating roman numerals. The coursework
+is due on 2 February at 5pm. Make sure the files you submit can be
+processed by just calling \texttt{scala <<filename.scala>>}.\bigskip
+
+\noindent
+\textbf{Important:} Do not use any mutable data structures in your
+submission! They are not needed. This menas you cannot use
+\texttt{ListBuffer}s, for example. Do not use \texttt{return} in your
+code! It has a different meaning in Scala, than in Java. Do not use
+\texttt{var}! This declares a mutable variable. Make sure the
+functions you submit are defined on the ``top-level'' of Scala, not
+inside a class or object. Also note that the running time will be
+restricted to a maximum of 360 seconds on my laptop.
+
+
+\subsection*{Disclaimer}
+
+It should be understood that the work you submit represents your own
+effort! You have not copied from anyone else. An exception is the
+Scala code I showed during the lectures or uploaded to KEATS, which
+you can freely use.\bigskip
+
+
+\subsection*{Part 1 (Translation)}
+
+\noindent
+Roman numerals are strings consisting of the letters $I$, $V$, $X$,
+$L$, $C$, $D$, and $M$. Such strings should be transformed into an
+internal representation using the datatypes \texttt{RomanDigit} and
+\texttt{RomanNumeral} (defined in \texttt{roman.scala}), and then from
+this internal representation converted into Integers.
+
+\begin{itemize}
+\item[(1)] First write a polymorphic function that recursively
+ transforms a list of options into an option of a list. For example,
+ if you have the lists on the left-hand side, they should be transformed into
+ the options on the right-hand side:
+
+ \begin{center}
+ \begin{tabular}{lcl}
+ \texttt{List(Some(1), Some(2), Some(3))} & $\Rightarrow$ &
+ \texttt{Some(List(1, 2, 3))} \\
+ \texttt{List(Some(1), None, Some(3))} & $\Rightarrow$ &
+ \texttt{None} \\
+ \texttt{List()} & $\Rightarrow$ & \texttt{Some(List())}
+ \end{tabular}
+ \end{center}
+
+ This means the function should produce \texttt{None} as soon
+ as a \texttt{None} is inside the list. Otherwise it produces
+ a list of all \texttt{Some}s. In case the list is empty, it
+ produces \texttt{Some} of the empty list. \hfill[1 Mark]
+
+
+\item[(2)] Write first a function that converts the characters $I$, $V$,
+ $X$, $L$, $C$, $D$, and $M$ into an option of a \texttt{RomanDigit}.
+ If it is one of the roman digits, it should produce \texttt{Some};
+ otherwise \texttt{None}.
+
+ Next write a function that converts a string into a
+ \texttt{RomanNumeral}. Again, this function should return an
+ \texttt{Option}: If the string consists of $I$, $V$, $X$, $L$, $C$,
+ $D$, and $M$ only, then it produces \texttt{Some}; otherwise if
+ there is any other character in the string, it should produce
+ \texttt{None}. The empty string is just the empty
+ \texttt{RomanNumeral}, that is the empty list of
+ \texttt{RomanDigit}'s. You should use the function under Task (1)
+ to produce the result. \hfill[2 Marks]
+
+\item[(3)] Write a recursive function \texttt{RomanNumral2Int} that
+ converts a \texttt{RomanNumeral} into an integer. You can assume the
+ generated integer will be between 0 and 3999. The argument of the
+ function is a list of roman digits. It should look how this list
+ starts and then calculate what the corresponding integer is for this
+ ``start'' and add it with the integer for the rest of the list. That
+ means if the argument is of the form shown on the left-hand side, it
+ should do the calculation on the right-hand side.
+
+ \begin{center}
+ \begin{tabular}{lcl}
+ $M::r$ & $\Rightarrow$ & $1000 + \text{roman numeral of rest}\; r$\\
+ $C::M::r$ & $\Rightarrow$ & $900 + \text{roman numeral of rest}\; r$\\
+ $D::r$ & $\Rightarrow$ & $500 + \text{roman numeral of rest}\; r$\\
+ $C::D::r$ & $\Rightarrow$ & $400 + \text{roman numeral of rest}\; r$\\
+ $C::r$ & $\Rightarrow$ & $100 + \text{roman numeral of rest}\; r$\\
+ $X::C::r$ & $\Rightarrow$ & $90 + \text{roman numeral of rest}\; r$\\
+ $L::r$ & $\Rightarrow$ & $50 + \text{roman numeral of rest}\; r$\\
+ $X::L::r$ & $\Rightarrow$ & $40 + \text{roman numeral of rest}\; r$\\
+ $X::r$ & $\Rightarrow$ & $10 + \text{roman numeral of rest}\; r$\\
+ $I::X::r$ & $\Rightarrow$ & $9 + \text{roman numeral of rest}\; r$\\
+ $V::r$ & $\Rightarrow$ & $5 + \text{roman numeral of rest}\; r$\\
+ $I::V::r$ & $\Rightarrow$ & $4 + \text{roman numeral of rest}\; r$\\
+ $I::r$ & $\Rightarrow$ & $1 + \text{roman numeral of rest}\; r$
+ \end{tabular}
+ \end{center}
+
+ The empty list will be converted to integer $0$.\hfill[1 Mark]
+
+\item[(4)] Write a function that takes a string and if possible
+ converts it into the internal representation. If successful, it then
+ calculates the integer (an option of an integer) according to the
+ function in (3). If this is not possible, then return
+ \texttt{None}.\hfill[1 Mark]
+
+
+\item[(5)] The file \texttt{roman.txt} contains a list of roman numerals.
+ Read in these numerals, convert them into integers and then add them all
+ up. The Scala function for reading a file is
+
+ \begin{center}
+ \texttt{Source.fromFile("filename")("ISO-8859-9")}
+ \end{center}
+
+ Make sure you process the strings correctly by ignoring whitespaces
+ where needed.\\ \mbox{}\hfill[1 Mark]
+\end{itemize}
+
+
+\subsection*{Part 2 (Validation)}
+
+As you can see the function under Task (3) can produce some unexpected
+results. For example for $XXCIII$ it produces 103. The reason for this
+unexpected result is that $XXCIII$ is actually not a valid roman
+number, neither is $IIII$ for 4 nor $MIM$ for 1999. Although actual
+Romans were not so fussy about this,\footnote{They happily used
+ numbers like $XIIX$ or $IIXX$ for 18.} but modern times declared
+that there are precise rules for what a valid roman number is, namely:
+
+\begin{itemize}
+\item Repeatable roman digits are $I$, $X$, $C$ and $M$. The other ones
+ are non-repeatable. Repeatable digits can be repeated upto 3 times in a
+ number (for example $MMM$ is OK); non-repeatable digits cannot be
+ repeated at all (for example $VV$ is excluded).
+
+\item If a smaller digits precedes a bigger digit, then $I$ can precede $V$ and $X$; $X$ can preced
+ $L$ and $C$; and $C$ can preced $D$ and $M$. No other combination is permitted in this case.
+
+\item If a smaller digit precedes a bigger digit (for example $IV$), then the smaller number
+ must be either the first digit in the number, or follow a digit which is at least 10 times its value.
+ So $VIV$ is excluded, because $I$ follows $V$ and $I * 10$ is bigger than $V$; but $XIV$ is
+ allowed, because $I$ follows $X$ and $I * 10$ is equal to $X$.
+
+\item Let us say two digits are called a \emph{compound} roman digit
+ when a smaller digit precedes a bigger digit (so $IV$, $XL$, $CM$
+ for example). If a compound digit is followed by another digit, then
+ this digit must be smaller than the first digit in the compound
+ digit. For example $IXI$ is excluded, but $XLI$ is not.
+
+\item The empty roman numeral is valid.
+\end{itemize}
+
+\noindent
+The tasks in this part are as follows:
+
+\begin{itemize}
+\item[(6)] Implement a recursive function \texttt{isValidNumeral} that
+ takes a \texttt{RomanNumeral} as argument and produces true if \textbf{all}
+ the rules above are satisfied, and otherwise false.
+
+ Hint: It might be more convenient to test when the rules fail and then return false;
+ return true in all other cases.
+ \mbox{}\hfill[2 Marks]
+
+\item[(7)] Write a recursive function that converts an Integer into a \texttt{RomanNumeral}.
+ You can assume the function will only be called for integers between 0 and 3999.\mbox{}\hfill[1 Mark]
+
+\item[(8)] Write a function that reads a text file (for example \texttt{roman2.txt})
+ containing valid and invalid roman numerals. Convert all valid roman numerals into
+ integers, add them up and produce the result as a \texttt{RomanNumeral} (using the function
+ from (7)). \hfill[1 Mark]
+\end{itemize}
+
+
+\end{document}
+
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
--- a/progs/lecture3.scala Fri Nov 23 01:52:37 2018 +0000
+++ b/progs/lecture3.scala Tue Nov 27 21:41:59 2018 +0000
@@ -7,7 +7,7 @@
//
// the idea is to look for links using the
// regular expression "https?://[^"]*" and for
-// email addresses using another regex.
+// email addresses using yet another regex.
import io.Source
import scala.util._
@@ -22,9 +22,8 @@
val http_pattern = """"https?://[^"]*"""".r
val email_pattern = """([a-z0-9_\.-]+)@([\da-z\.-]+)\.([a-z\.]{2,6})""".r
-//email_pattern.findAllIn
-// ("foo bla christian@kcl.ac.uk 1234567").toList
-
+// val s = "foo bla christian@kcl.ac.uk 1234567"
+// email_pattern.findAllIn(s).toList
// drops the first and last character from a string
def unquote(s: String) = s.drop(1).dropRight(1)
@@ -34,6 +33,7 @@
// naive version of crawl - searches until a given depth,
// visits pages potentially more than once
+
def crawl(url: String, n: Int) : Set[String] = {
if (n == 0) Set()
else {
@@ -41,36 +41,92 @@
val page = get_page(url)
val new_emails = email_pattern.findAllIn(page).toSet
new_emails ++
- (for (u <- get_all_URLs(page)) yield crawl(u, n - 1)).flatten
+ (for (u <- get_all_URLs(page).par) yield crawl(u, n - 1)).flatten
}
}
// some starting URLs for the crawler
val startURL = """https://nms.kcl.ac.uk/christian.urban/"""
-
crawl(startURL, 2)
// User-defined Datatypes and Pattern Matching
-//============================================
-
+//=============================================
abstract class Exp
-case class N(n: Int) extends Exp
+case class N(n: Int) extends Exp // for numbers
case class Plus(e1: Exp, e2: Exp) extends Exp
case class Times(e1: Exp, e2: Exp) extends Exp
+def string(e: Exp) : String = e match {
+ case N(n) => n.toString
+ case Plus(e1, e2) => "(" + string(e1) + " + " + string(e2) + ")"
+ case Times(e1, e2) => "(" + string(e1) + " * " + string(e2) + ")"
+}
+val e = Plus(N(9), Times(N(3), N(4)))
+println(string(e))
+
+def eval(e: Exp) : Int = e match {
+ case N(n) => n
+ case Plus(e1, e2) => eval(e1) + eval(e2)
+ case Times(e1, e2) => eval(e1) * eval(e2)
+}
+
+def simp(e: Exp) : Exp = e match {
+ case N(n) => N(n)
+ case Plus(e1, e2) => (simp(e1), simp(e2)) match {
+ case (N(0), e2s) => e2s
+ case (e1s, N(0)) => e1s
+ case (e1s, e2s) => Plus(e1s, e2s)
+ }
+ case Times(e1, e2) => (simp(e1), simp(e2)) match {
+ case (N(0), _) => N(0)
+ case (_, N(0)) => N(0)
+ case (N(1), e2s) => e2s
+ case (e1s, N(1)) => e1s
+ case (e1s, e2s) => Times(e1s, e2s)
+ }
+}
+
+println(eval(e))
-// string of an Exp
-// eval of an Exp
-// simp an Exp
-// Tokens
-// Reverse Polish Notation
-// compute RP
-// transform RP into Exp
-// process RP string and generate Exp
+val e2 = Times(Plus(N(0), N(1)), Plus(N(0), N(9)))
+println(string(e2))
+println(string(simp(e2)))
+
+// Tokens and Reverse Polish Notation
+abstract class Token
+case class T(n: Int) extends Token
+case object PL extends Token
+case object TI extends Token
+
+def rp(e: Exp) : List[Token] = e match {
+ case N(n) => List(T(n))
+ case Plus(e1, e2) => rp(e1) ::: rp(e2) ::: List(PL)
+ case Times(e1, e2) => rp(e1) ::: rp(e2) ::: List(TI)
+}
+println(string(e2))
+println(rp(e2))
+
+def comp(ls: List[Token], st: List[Int]) : Int = (ls, st) match {
+ case (Nil, st) => st.head
+ case (T(n)::rest, st) => comp(rest, n::st)
+ case (PL::rest, n1::n2::st) => comp(rest, n1 + n2::st)
+ case (TI::rest, n1::n2::st) => comp(rest, n1 * n2::st)
+}
+
+comp(rp(e), Nil)
+
+def proc(s: String) : Token = s match {
+ case "+" => PL
+ case "*" => TI
+ case _ => T(s.toInt)
+}
+
+comp("1 2 + 4 * 5 + 3 +".split(" ").toList.map(proc), Nil)
+
@@ -159,6 +215,11 @@
def fact(n: Long): Long =
if (n == 0) 1 else n * fact(n - 1)
+def factB(n: BigInt): BigInt =
+ if (n == 0) 1 else n * factB(n - 1)
+
+factB(100000)
+
fact(10) //ok
fact(10000) // produces a stackoverflow
@@ -166,7 +227,7 @@
if (n == 0) acc else factT(n - 1, n * acc)
factT(10, 1)
-factT(100000, 1)
+println(factT(100000, 1))
// there is a flag for ensuring a function is tail recursive
import scala.annotation.tailrec
@@ -192,6 +253,8 @@
// the first n prefixes of xs
// for 1 => include xs
+
+
def moves(xs: List[Int], n: Int) : List[List[Int]] = (xs, n) match {
case (Nil, _) => Nil
case (xs, 0) => Nil
@@ -204,7 +267,6 @@
moves(List(5,1,0), 5)
// checks whether a jump tour exists at all
-// in the second case it needs to be < instead of <=
def search(xs: List[Int]) : Boolean = xs match {
case Nil => true
@@ -235,14 +297,12 @@
case Nil => Nil
case (x::xs) => {
val children = moves(xs, x)
- val results = children.flatMap((cs) => jumps(cs).map(x :: _))
+ val results = children.map((cs) => jumps(cs).map(x :: _)).flatten
if (xs.length < x) List(x) :: results else results
}
}
-
-
-jumps(List(5,3,2,5,1,1))
+println(jumps(List(5,3,2,5,1,1)).minBy(_.length))
jumps(List(3,5,1,2,1,2,1))
jumps(List(3,5,1,2,3,4,1))
jumps(List(3,5,1,0,0,0,1))
@@ -315,7 +375,8 @@
//get_row(game0, 0)
//get_row(game0, 1)
-//get_box(game0, (3,1))
+//get_col(game0, 0)
+//get_box(game0, (3, 1))
// this is not mutable!!
@@ -326,20 +387,19 @@
(get_col(game, pos._1) ++ get_row(game, pos._2) ++ get_box(game, pos))
def candidates(game: String, pos: Pos): List[Char] =
- allValues.diff(toAvoid(game,pos))
+ allValues.diff(toAvoid(game, pos))
//candidates(game0, (0,0))
def pretty(game: String): String =
- "\n" + (game sliding (MaxValue, MaxValue) mkString "\n")
+ "\n" + (game.sliding(MaxValue, MaxValue).mkString("\n"))
-/////////////////////
-// not tail recursive
+
def search(game: String): List[String] = {
if (isDone(game)) List(game)
else {
val cs = candidates(game, emptyPosition(game))
- cs.map(c => search(update(game, empty(game), c))).toList.flatten
+ cs.par.map(c => search(update(game, empty(game), c))).toList.flatten
}
}
@@ -379,8 +439,6 @@
|9724...5.""".stripMargin.replaceAll("\\n", "")
-
-
search(game1).map(pretty)
search(game3).map(pretty)
search(game2).map(pretty)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/lecture4.scala Tue Nov 27 21:41:59 2018 +0000
@@ -0,0 +1,11 @@
+def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match {
+ case Nil => Nil
+ case (x::xs) => {
+ val res = f(x)
+ if (acc.contains(res)) distinctBy(xs, f, acc)
+ else x::distinctBy(xs, f, res::acc)
+ }
+}
+
+
+
Binary file slides/slides03.pdf has changed
--- a/slides/slides03.tex Fri Nov 23 01:52:37 2018 +0000
+++ b/slides/slides03.tex Tue Nov 27 21:41:59 2018 +0000
@@ -116,8 +116,8 @@
def process_ratings(lines: List[String]) = {
val values = List[(String,String)]()
- for(line <- lines){
- val splitList = line.split(",").toList
+ for(line <- lines) {
+ val splitList = ...
if(splitList(2).toInt >= 4){
val userID = splitList(0)
@@ -132,7 +132,7 @@
\end{lstlisting}
\normalsize
-What does this function always return?
+What does this function (always) return?
\end{frame}
--- a/solutions3/knight1.scala Fri Nov 23 01:52:37 2018 +0000
+++ b/solutions3/knight1.scala Tue Nov 27 21:41:59 2018 +0000
@@ -154,6 +154,7 @@
// 15 secs for 8 x 8
//val ts1 = time_needed(0,first_tour(8, List((0, 0))).get)
+val ts1 = time_needed(0,first_tour(8, List((1, 1))).get)
// no result for 4 x 4
//val ts2 = time_needed(0, first_tour(4, List((0, 0))))
--- a/testing1/collatz_test.sh Fri Nov 23 01:52:37 2018 +0000
+++ b/testing1/collatz_test.sh Tue Nov 27 21:41:59 2018 +0000
@@ -37,7 +37,7 @@
if (scala_vars collatz.scala)
then
- echo " --> fail (make triple-sure your program conforms to the required format)" >> $out
+ echo " --> FAIL (make triple-sure your program conforms to the required format)\n" >> $out
tsts0=$(( 0 ))
else
echo " --> success" >> $out
@@ -56,7 +56,7 @@
echo " --> success" >> $out
tsts=$(( 0 ))
else
- echo " --> scala did not run collatz.scala" >> $out
+ echo " --> SCALA DID NOT RUN COLLATZ.SCALA\n" >> $out
tsts=$(( 1 ))
fi
else
@@ -76,7 +76,7 @@
then
echo " --> success" >> $out
else
- echo " --> one of the tests failed" >> $out
+ echo " --> ONE OF THE TESTS FAILED\n" >> $out
fi
fi
@@ -95,7 +95,7 @@
then
echo " --> success" >> $out
else
- echo " --> one of the tests failed" >> $out
+ echo " --> ONE OF THE TESTS FAILED\n" >> $out
fi
fi
--- a/testing3-bak/mark Fri Nov 23 01:52:37 2018 +0000
+++ b/testing3-bak/mark Tue Nov 27 21:41:59 2018 +0000
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/bin/bash
###set -e
trap "exit" INT
--- a/testing3/knight_test2.scala Fri Nov 23 01:52:37 2018 +0000
+++ b/testing3/knight_test2.scala Tue Nov 27 21:41:59 2018 +0000
@@ -1,9 +1,7 @@
-assert(legal_moves(8, Nil, (2,2)) ==
- List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
+assert(legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
-assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
- List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
+assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
assert(legal_moves(1, Nil, (0,0)) == List())
assert(legal_moves(2, Nil, (0,0)) == List())
--- a/testing4/mark Fri Nov 23 01:52:37 2018 +0000
+++ b/testing4/mark Tue Nov 27 21:41:59 2018 +0000
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/bin/bash
###set -e
trap "exit" INT