--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/README Thu Dec 01 17:08:12 2016 +0000
@@ -0,0 +1,4 @@
+Calling ediff from the command line
+
+
+emacs --eval "(ediff-files \"k1502472/drumb.scala\" \"k1502752/drumb.scala\")"
--- a/TAs Thu Dec 01 13:50:36 2016 +0000
+++ b/TAs Thu Dec 01 17:08:12 2016 +0000
@@ -1,10 +1,10 @@
- daniil.baryshnikov@kcl.ac.uk,
- andrew.coles@kcl.ac.uk,
- oliver.hohn@kcl.ac.uk,
- fahad.ausaf@icloud.com,
- fares.alaboud@kcl.ac.uk,
- sara.boutamina@kcl.ac.uk,
- mark.ormesher@kcl.ac.uk,
+ daniil.baryshnikov@kcl.ac.uk
+ andrew.coles@kcl.ac.uk
+ oliver.hohn@kcl.ac.uk
+ fahad.ausaf@icloud.com
+ fares.alaboud@kcl.ac.uk
+ sara.boutamina@kcl.ac.uk
+ mark.ormesher@kcl.ac.uk
clarence.ji@kcl.ac.uk
andrei.nae_-_stroie@kcl.ac.uk
alexander.hanbury-Botherway@kcl.ac.uk
Binary file cws/cw01.pdf has changed
--- a/cws/cw01.tex Thu Dec 01 13:50:36 2016 +0000
+++ b/cws/cw01.tex Thu Dec 01 17:08:12 2016 +0000
@@ -12,7 +12,16 @@
processing and recursion. The third part is more advanced and might
include material you have not yet seen in the first lecture.
Make sure the files you submit can be processed by just calling
-\texttt{scala <<filename.scala>>}.
+\texttt{scala <<filename.scala>>}.\bigskip
+
+\noindent
+\textbf{Important:} Do not use any mutable data structures in your
+submissions! They are not needed. This excludes the use of
+\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.
\subsection*{Disclaimer}
@@ -195,7 +204,7 @@
Since the question about Mr Drumb's business acumen remains, let's do a
quick back-of-the-envelope calculation in Scala whether his claim has
any merit. Let's suppose we are given \$100 in 1978 and we follow a
-really dump investment strategy, namely:
+really dumb investment strategy, namely:
\begin{itemize}
\item We blindly choose a portfolio of stocks, say some Blue-Chip stocks
Binary file cws/cw02.pdf has changed
--- a/cws/cw02.tex Thu Dec 01 13:50:36 2016 +0000
+++ b/cws/cw02.tex Thu Dec 01 17:08:12 2016 +0000
@@ -20,9 +20,10 @@
backtracking. The first part is due on 23 November at 11pm; the
second, more advanced part, is due on 30 November at 11pm. You are
asked to implement Scala programs that solve various versions of the
-\textit{Knight's Tour Problem} on a chessboard. Make sure the files
-you submit can be processed by just calling \texttt{scala
- <<filename.scala>>}.\bigskip
+\textit{Knight's Tour Problem} on a chessboard. Note the second part
+might include material you have not yet seen in the first two
+lectures. 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
@@ -260,12 +261,17 @@
\]
\noindent That is, we want to find the first position where the
- result of $f$ is not \texttt{None}, if there is one.\mbox{}\hfill[1 Mark]
+ result of $f$ is not \texttt{None}, if there is one. Note that you
+ do not (need to) know anything about the function $f$ except its
+ type, namely \texttt{Pos => Option[Path]}. There is one additional
+ point however you should take into account when implementing
+ \textit{first}: you will need to calculate what the result of $f(x)$
+ is; your code should do this only \textbf{once}!\\\mbox{}\hfill[1 Mark]
\item[(2b)] Implement a first-tour function that uses the
first-function from (2a), and searches recursively for an open tour.
As there might not be such a tour at all, the first-tour function
- needs to return an \texttt{Option[Path]}.\hfill[2 Marks]
+ needs to return an \texttt{Option[Path]}.\\\mbox{}\hfill[2 Marks]
\end{itemize}
\noindent
Binary file cws/cw03.pdf has changed
--- a/cws/cw03.tex Thu Dec 01 13:50:36 2016 +0000
+++ b/cws/cw03.tex Thu Dec 01 17:08:12 2016 +0000
@@ -1,18 +1,17 @@
\documentclass{article}
\usepackage{../style}
-%%\usepackage{../langs}
+\usepackage{../langs}
\begin{document}
\section*{Coursework 8 (Scala, Regular Expressions}
-This coursework is worth 10\%. It is about regular expressions and
-pattern matching. The first part is due on 30 November at 11pm; the
-second, more advanced part, is due on 7 December at 11pm. The
-second part is not yet included. For the first part you are
-asked to implement a regular expression matcher. 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 polymorphism. The first part is due on 30
+November at 11pm; the second, more advanced part, is due on 7 December
+at 11pm. You are asked to implement a regular expression matcher. 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
@@ -66,7 +65,7 @@
\item[$\bullet$] \url{http://davidvgalbraith.com/how-i-fixed-atom/}
\end{itemize}}
-\subsection*{Tasks (file re.scala)}
+\subsubsection*{Tasks (file re.scala)}
\begin{itemize}
\item[(1a)] Implement a function, called \textit{nullable}, by recursion over
@@ -160,8 +159,17 @@
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$.
- \hfill[1 Mark]
+ simplifies to just $r_1$. \textbf{Hints:} Regular expressions can be
+ seen as trees and there are several methods for traversing
+ trees. One of them corresponds to the inside-out traversal. Also
+ remember numerical expressions from school: there you had exprssions
+ 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 if more rules are applicable. If you organise this
+ simplification in an inside-out fashion, it is always clear which
+ rule should applied next.\\\mbox{}\hfill[1 Mark]
\item[(1d)] Implement two functions: The first, called \textit{ders},
takes a list of characters and a regular expression as arguments, and
@@ -175,13 +183,16 @@
\end{tabular}
\end{center}
-The second, 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 given the
-regular expression $(a\cdot b)\cdot c$ and the string $abc$.
-\hfill[1 Mark]
+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 given the regular expression $(a\cdot b)\cdot c$ and the string
+$abc$.\\ \mbox{}\hfill[1 Mark]
\item[(1e)] Implement the function $\textit{replace}\;r\;s_1\;s_2$: it searches
(from the left to
@@ -194,45 +205,162 @@
\[(a \cdot a)^* + (b \cdot b)\]
\noindent the string $s_1 = aabbbaaaaaaabaaaaabbaaaabb$ and
-replacement string $s_2 = c$ yields the string
+replacement the string $s_2 = c$ yields the string
\[
ccbcabcaccc
\]
-\hfill[2 Mark]
+\hfill[2 Marks]
\end{itemize}
+
+
+
+\subsection*{Part 2 (4 Marks)}
+
+You need to copy all the code from \texttt{re.scala} into
+\texttt{re2.scala} in order to complete Part 2. Parts (2a) and (2b)
+give you another method and datapoints for testing the \textit{der}
+and \textit{simp} functions from Part~1.
+
+\subsubsection*{Tasks (file re2.scala)}
+
+\begin{itemize}
+\item[(2a)] Write a \textbf{polymorphic} function, called
+ \textit{iterT}, that is \textbf{tail-recursive}(!) and takes an
+ integer $n$, a function $f$ and an $x$ as arguments. This function
+ should iterate $f$ $n$-times starting with the argument $x$, like
+
+ \[\underbrace{f(\ldots (f}_{n\text{-times}}(x)))
+ \]
+
+ More formally that means \textit{iterT} behaves as follows:
+
+ \begin{center}
+ \begin{tabular}{lcl}
+ $\textit{iterT}(n, f, x)$ & $\dn$ &
+ $\begin{cases}
+ \;x & \textit{if}\;n = 0\\
+ \;f(\textit{iterT}(n - 1, f, x)) & \textit{otherwise}
+ \end{cases}$
+ \end{tabular}
+\end{center}
+
+ Make sure you write a \textbf{tail-recursive} version of
+ \textit{iterT}. If you add the annotation \texttt{@tailrec} (see
+ below) your code should not produce an error message.
+
+ \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
+ import scala.annotation.tailrec
+
+ @tailrec
+ def iterT[A](n: Int, f: A => A, x: A): A = ...
+ \end{lstlisting}
+
+ You can assume that \textit{iterT} will only be called for positive
+ integers $0 \le n$. Given the type variable \texttt{A}, the type of
+ $f$ is \texttt{A => A} and the type of $x$ is \texttt{A}. This means
+ \textit{iterT} can be used, for example, for functions from integers
+ to integers, or strings to strings, or regular expressions to
+ regular expressions. \\ \mbox{}\hfill[2 Marks]
+
+\item[(2b)] 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} and \textit{iterT} in order to test how much
+the 'evil' regular expression $(a^*)^* \cdot b$ grows when taking
+successive derivatives according the letter $a$ and then compare it to
+taking the derivative, but simlifying the derivative after each step.
+For example, the calls
+
+ \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
+ size(iterT(20, (r: Rexp) => der('a', r), EVIL))
+ size(iterT(20, (r: Rexp) => simp(der('a', r)), EVIL))
+ \end{lstlisting}
+
+ produce without simplification a regular expression of size of
+ 7340068 after 20 iterations, while the one with
+ simplification gives
+ just 8.\\ \mbox{}\hfill[1 Mark]
+
+
+\item[(2c)] Write a \textbf{polymorphic} function, called
+ \textit{fixpT}, that takes
+ a function $f$ and an $x$ as arguments. The purpose
+ of \textit{fixpT} is to calculate a fixpoint of the function $f$
+ starting from the argument $x$.
+ A fixpoint, say $y$, is when $f(y) = y$ holds.
+ That means \textit{fixpT} behaves as follows:
+
+ \begin{center}
+ \begin{tabular}{lcl}
+ $\textit{fixpT}(f, x)$ & $\dn$ &
+ $\begin{cases}
+ \;x & \textit{if}\;f(x) = x\\
+ \;\textit{fixpT}(f, f(x)) & \textit{otherwise}
+ \end{cases}$
+ \end{tabular}
+\end{center}
+
+ Make sure you calculate in the code of $\textit{fixpT}$ the result
+ of $f(x)$ only once. Given the type variable \texttt{A} in
+ $\textit{fixpT}$, the type of $f$ is \texttt{A => A} and the type of
+ $x$ is \texttt{A}. The file \texttt{re2.scala} gives two example
+ function where in one the fixpoint is 1 and in the other
+ it is the string $a$.\\ \mbox{}\hfill[1 Mark]
+\end{itemize}\bigskip
+
+
+
+\noindent
\textbf{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 $cs$). If you now take the
+a character $c$ and have some rest, or tail, $cs$). If you now take the
derivative of $r$ with respect to the character $c$, then you obtain a
regular expressions that can match all the strings $cs$. In other
-words the regular expression $\textit{der}\;c\;r$ can match the same
+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 der('c', der('b', der('a', r))), you obtain a regular
-expression that can match the empty string. You can test this using
-the function nullable, which is what your matcher is doing.
+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 this using the function nullable, which is what your matcher is
+doing.
-The purpose of the simp function is to keep the regular expression small. Normally the derivative function makes the regular expression bigger (see the SEQ case) and the algorithm would be slower and slower over time. The simp function counters this increase in size and the result is that the algorithm is fast throughout.
-By the way this whole idea is by Janusz Brzozowski who came up with this in 1964 in his PhD thesis.
-https://en.wikipedia.org/wiki/Janusz_Brzozowski_(computer_scientist)
-
+The purpose of the simp function is to keep the regular expression
+small. Normally the derivative function makes the regular expression
+bigger (see the SEQ case and the example in (2b)) and the algorithm
+would be slower and slower over time. The 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.
-
-\subsection*{Part 2 (4 Marks)}
-
-Coming soon.
+\begin{center}\small
+\url{https://en.wikipedia.org/wiki/Janusz_Brzozowski_(computer_scientist)}
+\end{center}
\end{document}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/re2.scala Thu Dec 01 17:08:12 2016 +0000
@@ -0,0 +1,68 @@
+// Part 2 about Regular Expression Matching
+//==========================================
+
+// copy over all code from re.scala
+
+// (2a) Complete the function iterT which needs to
+// be tail-recursive(!) and takes an integer n, a
+// function f and an x as arguments. This function
+// should iterate f n-times starting with the
+// argument x.
+
+import scala.annotation.tailrec
+
+@tailrec
+def iterT[A](n: Int, f: A => A, x: A): A = ...
+
+
+
+// (2b) Complete the size function for regular
+// expressions
+
+def size(r: Rexp): Int = ...
+
+// two testcases about the sizes of simplified and
+// un-simplified derivatives
+
+//val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+//size(iterT(20, (r: Rexp) => der('a', r), EVIL)) // should produce 7340068
+//size(iterT(20, (r: Rexp) => simp(der('a', r)), EVIL)) // should produce 8
+
+
+
+// (2c) Complete the fixpoint function below.
+
+@tailrec
+def fixpT[A](f: A => A, x: A): A = ...
+
+
+/* testcases
+
+//the Collatz function from CW 6 defined as fixpoint
+
+def ctest(n: Long): Long =
+ if (n == 1) 1 else
+ if (n % 2 == 0) n / 2 else 3 * n + 1
+
+// should all produce 1
+fixpT(ctest, 97L)
+fixpT(ctest, 871L)
+fixpT(ctest, 77031L)
+
+*/
+
+/*
+// the same function on strings using the regular expression
+// matcher
+
+def foo(s: String): String = {
+ if (matcher("a", s)) "a" else
+ if (matcher("aa" ~ STAR("aa"), s)) s.take(s.length / 2)
+ else "a" ++ s * 3
+}
+
+// should all produce "a"
+fixpT(foo, "a" * 97)
+fixpT(foo, "a" * 871)
+
+*/