--- a/LINKS Sat Dec 01 15:09:37 2018 +0000
+++ b/LINKS Thu Dec 06 13:15:28 2018 +0000
@@ -5,7 +5,9 @@
Race Track game
Game of life
-
+
+===================
+https://meta.plasm.us/posts/2013/03/28/better-scala-syntax-highlighting-for-hakyll/
===================
CS quotes
--- a/README Sat Dec 01 15:09:37 2018 +0000
+++ b/README Thu Dec 06 13:15:28 2018 +0000
@@ -11,7 +11,10 @@
five-in-a-row as a spiral
(Tic-Tac-Toe on steriods or Go for the weak mind)
+----------
+for serving locally a directory
+python -m SimpleHTTPServer 8000
----------
CokeBottle cokeBottle = new CokeBottle();
--- a/TAs Sat Dec 01 15:09:37 2018 +0000
+++ b/TAs Thu Dec 06 13:15:28 2018 +0000
@@ -28,16 +28,16 @@
CW7, Part 1 + 2
- late
-192 => 6 163
-14 => 5 28
-12 => 4 4
-0 => 3 12
-6 => 2 4
-21 => 1 0
-12 => 0 23
+ late (234)
+192 => 6 191
+16 => 5 17
+7 => 4 7
+2 => 3 2
+6 => 2 5
+1 => 1 2
+9 => 0 10
--------
-260 submissions
+233 submissions
Binary file cws/cw05.pdf has changed
--- a/cws/cw05.tex Sat Dec 01 15:09:37 2018 +0000
+++ b/cws/cw05.tex Thu Dec 06 13:15:28 2018 +0000
@@ -9,84 +9,6 @@
%% \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-js.data}
-5 0.061
-10 0.061
-15 0.061
-20 0.070
-23 0.131
-25 0.308
-26 0.564
-28 1.994
-30 7.648
-31 15.881
-32 32.190
-\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}
@@ -95,16 +17,10 @@
\section*{Coursework 9 (Scala)}
-This coursework is worth 10\%. It is about a regular expression
-matcher and the shunting yard algorithm by Dijkstra. The first part is
-due on 6 December 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
-languages like Java, JavaScipt and Python can sometimes be extremely
-slow. The advanced part is about the shunting yard algorithm that
-transforms the usual infix notation of arithmetic expressions into the
-postfix notation, which is for example used in compilers.\bigskip
+This coursework is worth 10\%. It is about a small programming
+language called brainf***. The first part is due on 13 December at
+11pm; the second, more advanced part, is due on 20 December at
+11pm.\bigskip
\IMPORTANT{}
@@ -115,357 +31,28 @@
\DISCLAIMER{}
-\subsection*{Part 1 (6 Marks, Regular Expression Matcher)}
-
-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}:
-
-\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 a string with zero or more copies of $r$\\
-\end{tabular}
-\end{center}
-
-\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)}
-
-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)] 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]
-
-\item[(2)] 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:
-
-\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
-
-\begin{center}
- \begin{tabular}{lcll}
- $\textit{der}\;a\;r$ & $=$ & $(\ONE \cdot b)\cdot c$ & \quad($= 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$ & \quad($= r''$)\\
- $\textit{der}\;c\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$
- \end{tabular}
-\end{center}
-
-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[(3)] 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}{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}
-
- 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'' you traverse inside the
- tree and on the way up, you apply simplification rules.
- 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[1 Mark]
-
-\item[(4)] 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[(5)] 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]
-
-\item[(6)] You do not have to implement anything specific under this
- task. The purpose is that you will be marked for some ``power''
- test cases. For example can your matcher decide withing 30 seconds
- whether the regular expression $(a^*)^*\cdot b$ matches strings of the
- form $aaa\ldots{}aaaa$, for say 1 Million $a$'s. And does simplification
- simplify the regular expression
-
- \[
- \texttt{SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)}
- \]
-
- \noindent correctly to just \texttt{ONE}, where \texttt{SEQ} is nested
- 50 or more times.\\
- \mbox{}\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.
+\subsection*{Part 1 (6 Marks)}
-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 (2)) 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}
-
-
-If you want to see how badly the regular expression matchers do in
-Java\footnote{Version 8 and below; Version 9 and above does not seem to be as
- catastrophic, but still much worse than the regular expression
- matcher based on derivatives.}, JavaScript 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{catastrophic9.java}, \texttt{catastrophic.js} 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?
-
-\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, JavaScript},
- 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};
-\addplot[red,mark=*, mark options={fill=white}] table {re-js.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
+Coming from Java or C++, you might think Scala is a rather 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.
+interpreter and compiler 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
+computer pioneer. 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}, including
+a brainf*** program for the Sierpinski triangle and Mandelbot set.\bigskip
\noindent
As mentioned above, brainf*** has 8 single-character commands, namely
@@ -500,15 +87,21 @@
\subsubsection*{Tasks (file bf.scala)}
\begin{itemize}
-\item[(2a)] Brainf*** memory is represented by a \texttt{Map} from
+\item[(1)] Write a function that takes a file name as argument and
+ and requests the corresponding file from disk. It returns the
+ content of the file as a String. If the file does not exists,
+ the function should return the empty string.\\
+ \mbox{}\hfill[1 Mark]
+
+\item[(2)] 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
+ memory; \texttt{Map(0 -> 1, 2 -> 3)} stores \texttt{1} at
+ memory location \texttt{0}, and 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
+ 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}.
@@ -519,7 +112,7 @@
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
+\item[(3)] 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
@@ -586,10 +179,10 @@
\qquad$\stackrel{\texttt{jumpRight}}{\longrightarrow}$\qquad
\texttt{--[..[[-]+>[.]]-->,++\barbelow{\;\phantom{+}}}
\end{center}
- \hfill[1 Mark]
+ \hfill[2 Marks]
-\item[(2c)] Write a recursive function \texttt{run} that executes a
+\item[(4)] 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
@@ -597,13 +190,17 @@
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.
+ \texttt{run} with the updated data. The most convenient way to
+ implement the rules in \texttt{run} is to use pattern-matching
+ and calculating a triple consisting of the new \texttt{pc},
+ \texttt{mp} and \texttt{mem}.
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
+ Sierpinski triangle or the Hello world programs (they seem to be particularly
+ useful for debugging purposes), or have a look at
\begin{center}
\url{https://esolangs.org/wiki/Brainfuck}
@@ -673,7 +270,10 @@
\end{figure}
\end{itemize}\bigskip
+\subsection*{Part 2 (4 Marks)}
+While it is fun to look at bf-programs, like the Sierpinski triangle or the Mandelbrot
+program, being interpreted, it is much more fun to write a compiler for the bf-language.
\end{document}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/marking1/compare Thu Dec 06 13:15:28 2018 +0000
@@ -0,0 +1,18 @@
+#!/bin/sh
+###set -e
+
+trap "exit" INT
+
+files=${1:-assignment20187-*}
+
+for sd in $files; do
+ cd $sd
+ #cp output output1
+ cmp -s output output1 > /dev/null
+ if [ $? -eq 1 ]; then
+ echo $sd + "is different"
+ fi
+ cd ..
+done
+
+
--- a/marking2/danube_test.sh Sat Dec 01 15:09:37 2018 +0000
+++ b/marking2/danube_test.sh Thu Dec 06 13:15:28 2018 +0000
@@ -44,8 +44,6 @@
then
echo " --> test failed" | tee -a $out
tsts0=$(( 1 ))
- echo " --> fail (make triple-sure your program conforms to the required format)" | tee -a $out
- tsts0=$(( 0 ))
else
echo " --> success" | tee -a $out
tsts0=$(( 0 ))
--- a/slides/slides04.tex Sat Dec 01 15:09:37 2018 +0000
+++ b/slides/slides04.tex Thu Dec 06 13:15:28 2018 +0000
@@ -248,7 +248,7 @@
\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-7mm]
def is_legal(dim: Int, p: Path, x: Pos): Boolean =
- ......some_really_long_condition.....
+ !......some_really_long_condition.....
\end{lstlisting}\pause
--- a/solutions1/drumb.scala Sat Dec 01 15:09:37 2018 +0000
+++ b/solutions1/drumb.scala Thu Dec 06 13:15:28 2018 +0000
@@ -105,6 +105,7 @@
for (j <- (0 until (data(0).length)).toList) yield get_delta(data(i)(j), data(i + 1)(j))
+
// test case using the prices calculated above
//val d = get_deltas(p)
//val ttd = get_deltas(tt)
@@ -125,6 +126,10 @@
}
+yearly_yield(get_prices(rstate_portfolio, 2016 to 2018), 100, 2)
+get_prices(rstate_portfolio, 2016 to 2018)(2).flatten.sum
+
+
// (7) Write a function compound_yield that calculates the overall balance for a
// range of years where in each year the yearly profit is compounded to the new
// balances and then re-invested into our portfolio. For this use the function and
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/solutions5/bf.scala Thu Dec 06 13:15:28 2018 +0000
@@ -0,0 +1,224 @@
+// Part 1 about an Interpreter for the Brainf*** language
+//========================================================
+
+object CW10a {
+
+
+type Mem = Map[Int, Int]
+
+
+import io.Source
+import scala.util._
+
+// (1) Write a function that takes a file name as argument and
+// and requests the corresponding file from disk. It returns the
+// content of the file as a String. If the file does not exists,
+// the function should return the empty string.
+
+def load_bff(name: String) : String =
+ Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("")
+
+
+// (2) Complete the functions for safely reading
+// and writing brainf*** memory. Safely read should
+// Return the value stored in the Map for a given memory
+// pointer, provided it exists; otherwise it Returns 0. The
+// writing function generates a new Map with the
+// same data, except at the given memory pointer the
+// value v is stored.
+
+
+def sread(mem: Mem, mp: Int) : Int =
+ mem.getOrElse(mp, 0)
+
+def write(mem: Mem, mp: Int, v: Int) : Mem =
+ mem.updated(mp, v)
+
+
+// (3) Implement the two jumping instructions in the
+// brainf*** language. In jumpRight, given a program and
+// a program counter move the program counter to the right
+// until after the *matching* ]-command. Similarly,
+// jumpLeft implements the move to the left to just after
+// the *matching* [-command.
+
+def jumpRight(prog: String, pc: Int, level: Int) : Int = {
+ if (prog.length <= pc) pc
+ else (prog(pc), level) match {
+ case (']', 0) => pc + 1
+ case (']', l) => jumpRight(prog, pc + 1, l - 1)
+ case ('[', l) => jumpRight(prog, pc + 1, l + 1)
+ case (_, l) => jumpRight(prog, pc + 1, l)
+ }
+}
+
+def jumpLeft(prog: String, pc: Int, level: Int) : Int = {
+ if (pc < 0) pc
+ else (prog(pc), level) match {
+ case ('[', 0) => pc + 1
+ case ('[', l) => jumpLeft(prog, pc - 1, l - 1)
+ case (']', l) => jumpLeft(prog, pc - 1, l + 1)
+ case (_, l) => jumpLeft(prog, pc - 1, l)
+ }
+}
+
+// test cases
+//jumpRight("""--[..+>--],>,++""", 3, 0) // => 10
+//jumpLeft("""--[..+>--],>,++""", 8, 0) // => 3
+//jumpRight("""--[..[+>]--],>,++""", 3, 0) // => 12
+//jumpRight("""--[..[[-]+>[.]]--],>,++""", 3, 0) // => 18
+//jumpRight("""--[..[[-]+>[.]]--,>,++""", 3, 0) // => 22 (outside)
+//jumpLeft("""[******]***""", 7, 0) // => -1 (outside)
+
+// (4) Complete the compute function that interpretes (runs) a brainf***
+// program: the arguments are a program (represented as a string), a program counter,
+// a memory counter and a brainf*** memory. It Returns the
+// memory at the stage when the excution of the brainf*** program
+// finishes. The interpretation finishes once the program counter
+// pc is pointing to something outside the program string.
+// If the pc points to a character inside the program, the pc,
+// memory pointer and memory need to be updated according to
+// rules of the brainf*** language. Then, recursively, run
+// function continues with the command at the new program
+// counter.
+// Implement the run function that calls compute with the program
+// counter and memory counter set to 0.
+
+def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = {
+ if (0 <= pc && pc < prog.length) {
+ val (new_pc, new_mp, new_mem) = prog(pc) match {
+ case '>' => (pc + 1, mp + 1, mem)
+ case '<' => (pc + 1, mp - 1, mem)
+ case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
+ case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
+ case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
+ case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte))
+ case '[' =>
+ if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem)
+ case ']' =>
+ if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem)
+ case _ => (pc + 1, mp, mem)
+ }
+ compute(prog, new_pc, new_mp, new_mem)
+ }
+ else mem
+}
+
+def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m)
+
+
+/*
+
+// some sample bf-programs collected from the Internet
+//=====================================================
+
+
+// first some contrived (small) programs
+
+// clears the 0-cell
+run("[-]", Map(0 -> 100)) // Map will be 0 -> 0
+
+// copies content of the 0-cell to 1-cell
+run("[->+<]", Map(0 -> 10)) // Map will be 0 -> 0, 1 -> 10
+
+
+// copies content of the 0-cell to 2-cell and 4-cell
+run("[>>+>>+<<<<-]", Map(0 -> 42))
+
+
+// prints out numbers 0 to 9
+run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
+
+
+// some more "useful" programs
+
+// hello world program 1
+run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
+ ..+++.>>.<-.<.+++.------.--------.>>+.>++.""")
+
+// hello world program 2
+run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+
+ +.<<+++++++++++++++.>.+++.------.--------.>+.>.""")
+
+
+// draws the Sierpinski triangle
+run("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[
+ ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<
+ ]>.>+[>>]>+]""")
+
+run(load_bff("sierpinski.bf"))
+
+
+//fibonacci numbers below 100
+run("""+++++++++++
+ >+>>>>++++++++++++++++++++++++++++++++++++++++++++
+ >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>
+ +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-
+ <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<
+ -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]
+ >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++
+ +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++
+ ++++++++++++++++++++++++++++++++++++++++++++.[-]<<
+ <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<
+ [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""")
+
+
+//outputs the square numbers up to 10000
+run("""++++[>+++++<-]>[<+++++>-]+<+[
+ >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+
+ >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]
+ <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""")
+
+//collatz numbers (needs a number to be typed in)
+run(""">,[[----------[
+ >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<]
+ ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[
+ <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>]
+ >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]]
+ >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>>
+ ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""")
+
+
+// infinite collatz (never stops)
+run(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[<
+ <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++
+ +<-]>.<++++++[>--------<-]+<<]>>[>>]+[>>>>[<<+>+>-]<-[>+<-]+<
+ [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>->
+ [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[
+ <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+
+ ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<
+ +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<-
+ ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<-
+ >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>
+ -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++
+ +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[<
+ <]]++++++[>+++++++<-]>++.------------.[-]>[>>]<<[+++++[>+++++
+ +++<-]>.<++++++[>--------<-]+<<]+<]>[<+>-]<]>>>[>>]<<[>[-]<-<
+ <]++++++++++.[-]<<<[<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<+>-[<+>-
+ [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""")
+
+
+
+// a Mandelbrot set generator in brainf*** written by Erik Bosman
+run(load_bff("mandelbrot.bf"))
+
+
+// a benchmark program (counts down from 'Z' to 'A')
+val b1 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++
+ [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++
+ ++++++++[>++++++++++[>++++++++++[>++++++++++[>+
+ +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++."""
+
+
+def time_needed[T](n: Int, code: => T) = {
+ val start = System.nanoTime()
+ for (i <- 0 until n) code
+ val end = System.nanoTime()
+ (end - start)/1.0e9
+}
+
+time_needed(1, run(b1))
+*/
+
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/solutions5/mandelbrot.bf Thu Dec 06 13:15:28 2018 +0000
@@ -0,0 +1,145 @@
+ A mandelbrot set fractal viewer in brainf*** written by Erik Bosman
++++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[
+>>>>>>>>>]+[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-]>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+
+<<<<<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>>+>>>>>>>>>>>>>>>>>>>>>>>>>>
+>+<<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+[>>>>>>[>>>>>>>[-]>>]<<<<<<<<<[<<<<<<<<<]>>
+>>>>>[-]+<<<<<<++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<+++++++[-[->>>
+>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[[-]>>>>>>[>>>>>
+>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>
+[>>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<
+<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>+++++++++++++++[[
+>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[
+>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[
+-<<+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<
+<<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<
+[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>
+>>>>[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+
+<<<<<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>
+>>>>>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<
++>>>>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<
+<]<+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>
+>>>>>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>
+>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<
+<<<]>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<
+<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->
+>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<
+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]<<<<<<<[->+>>>-<<<<]>>>>>>>>>+++++++++++++++++++
++++++++>>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>[<<<<<<<+<[-<+>>>>+<<[-]]>[-<<[->+>>>-
+<<<<]>>>]>>>>>>>>>>>>>[>>[-]>[-]>[-]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>>>>>>[>>>>>
+[-<<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>[-<<<<<<<<
+<+>>>>>>>>>]>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>>]+>[-
+]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>>>>>>>]<<<
+<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+>>]<
+<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[->>>>
+>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-]<->>>
+[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[>>>>>>[-<
+<<<<+>>>>>]<<<<<[->>>>>+<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>+>>>>>>>>
+]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+
+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>
+[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-
+]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>>
+[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>++++++++
++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-<<<<<<<+
+>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[
+-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>>]>[-<<<<<<[->>>>>+<++<<<<]>>>>>[-<
+<<<<+>>>>>]<->+>]<[->+<]<<<<<[->>>>>+<<<<<]>>>>>>[-]<<<<<<+>>>>[-<<<<->>>>]+<<<<
+[->>>>->>>>>[>>[-<<->>]+<<[->>->[-<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]
++>>>>>>[>>>>>>>>>]>+<]]+>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<<<<<<<<<<[<<<<<
+<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<
+[<<<<<<<<<]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<
+<<<+<[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<
+<<<<<+>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<
+<<<<<<<<<<]>>>>[-]<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+<]>>>>>>>>]<<<
+<<<<<+<[>[->>>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>[->>>>+<<<<]>]<[->>>>-<<<<<<<
+<<<<<<<+>>>>>>>>>>]<]>>[->>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>>+<<<<
+]<<<<<<<<<<<]>>>>>>+<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>>>>>>>>>]<<<<<<<<<
+[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<<<<<<
++>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<<<<<<
+<<<<<]]>[-]>>[-]>[-]>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<
+<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[
+[>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+
+[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>
+[-<<+>>]<<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<
+<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[
+>[-]<->>>[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[
+>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>
+>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>[-]>>>>+++++++++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<
+<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<
+<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-
+<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>
+>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>>>
+[-<<<->>>]<<<[->>>+<<<]>>>>>>>>]<<<<<<<<+<[>[->+>[-<-<<<<<<<<<<+>>>>>>>>>>>>[-<<
++>>]<]>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<<<]>>[-<+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<]>
+[-<<+>>]<<<<<<<<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>
+>>>>>>]<<<<<<<<+<[>[->+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>[-<+>]>]<[-<-<<<<<<<<<<+>>>>
+>>>>>>>]<<]>>>[-<<+>[-<-<<<<<<<<<<+>>>>>>>>>>>]>]<[-<+>]<<<<<<<<<<<<]>>>>>+<<<<<
+]>>>>>>>>>[>>>[-]>[-]>[-]>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>>>[-<<<<<
+<+>>>>>>]<<<<<<[->>>>>>+<<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>
+>]>>[-<<<<<<<[->>>>>+<++<<<<]>>>>>[-<<<<<+>>>>>]<->+>>]<<[->>+<<]<<<<<[->>>>>+<<
+<<<]+>>>>[-<<<<->>>>]+<<<<[->>>>->>>>>[>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<
+<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>[-<<->>]+<<[->>->[-<<<+>>>]<
+<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<
+<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+
+<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>[->>>+<<<]>]<[->>>-
+<<<<<<<<<<<<<+>>>>>>>>>>]<]>>[->>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>+<<<
+]<<<<<<<<<<<]>>>>>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]]>>>>[-<<<<+>
+>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<<[->>>-
+<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[
+->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<<<<<]]>>>>[-]<<<<]>>>>[-<<<<+>>
+>>]<<<<[->>>>+>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>[>>>>>>
+>>>]<<<<<<<<<[>[->>>>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<
+<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<
+<<<<]]>>>>>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>[-<<<<+
+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<+>>>>>
+]<<<<<[->>>>>+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>
+>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>
+>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[-<<+
+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>
+[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-
+]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>>
+[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<
+<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>
+>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<+>>>
+>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+
+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>
+>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>
+>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<<<<]
+>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<<<<<
+]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->>>+<
+<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>
+>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>->>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>]<<+>>>>[-<<<<
+->>>>]+<<<<[->>>>-<<<<<<.>>]>>>>[-<<<<<<<.>>>>>>>]<<<[-]>[-]>[-]>[-]>[-]>[-]>>>[
+>[-]>[-]>[-]>[-]>[-]>[-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-]>>>>]<<<<<<<<<
+[<<<<<<<<<]>+++++++++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+>>>>>>>>>+<<<<<<<<
+<<<<<<[<<<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+[-]>>[>>>>>>>>>]<<<<<
+<<<<[>>>>>>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<[<<<<<<<<<]>>>>>>>[-]+>>>]<<<<
+<<<<<<]]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+>>[>+>>>>[-<<<<->>>>]<<<<[->>>
+>+<<<<]>>>>>>>>]<<+<<<<<<<[>>>>>[->>+<<]<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<
+<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<<<<<[->>>>>>+<<<<<<]<
++<<<<<<<<<]>>>>>>>-<<<<[-]+<<<]+>>>>>>>[-<<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>->>[>>
+>>>[->>+<<]>>>>]<<<<<<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<
+<<<<[->>>>>>+<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+<<<
+<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<<<<<->>>>>]+<<<<<[->>>>>->>[-<<<<<<<+>>>>>>>]<<<<
+<<<[->>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>[-<
+<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>-<<[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<<<<<<<<<[<<<
+<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<
+<<[<<<<<<<<<]>>>>[-]<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>-<<<<<[<<<<<<<
+<<]]>>>]<<<<.>>>>>>>>>>[>>>>>>[-]>>>]<<<<<<<<<[<<<<<<<<<]>++++++++++[-[->>>>>>>>
+>+<<<<<<<<<]>>>>>>>>>]>>>>>+>>>>>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-<<<<<<
+<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+[-]>[>>>>>>>>>]<<<<<<<<<[>>>>>>>>[-<<<<<<<+>>>>>>
+>]<<<<<<<[->>>>>>>+<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+>>]<<<<<<<<<<]]>>>>>>>>[-<<<<<
+<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+>[>+>>>>>[-<<<<<->>>>>]<<<<<[->>>>>+<<<<<]>>>>>>
+>>]<+<<<<<<<<[>>>>>>[->>+<<]<<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[-]<-
+>>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<
+<<<]>>>>>>>>-<<<<<[-]+<<<]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>->[>>>
+>>>[->>+<<]>>>]<<<<<<<<<[>[-]<->>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<
+<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>
++>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<<->>>>>>]+<
+<<<<<[->>>>>>->>[-<<<<<<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+<<<<<<<<<<<<<<<<<[<<<<<<<
+<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>
+-<<[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>
+>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>[-]<<<++++
++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>->>>>>>>>>>>>>>>>>>>>>>>>>>>-<<<<<<[<<<<
+<<<<<]]>>>]
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/solutions5/sierpinski.bf Thu Dec 06 13:15:28 2018 +0000
@@ -0,0 +1,3 @@
+++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[
+->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<
+]>.>+[>>]>+]
--- a/testing4/re.scala Sat Dec 01 15:09:37 2018 +0000
+++ b/testing4/re.scala Thu Dec 06 13:15:28 2018 +0000
@@ -1,20 +1,22 @@
// Part 1 about Regular Expression Matching
//==========================================
+//object CW9a {
+
// Regular Expressions
abstract class Rexp
case object ZERO extends Rexp
case object ONE extends Rexp
case class CHAR(c: Char) extends Rexp
-case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative
-case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence
-case class STAR(r: Rexp) extends Rexp // star
-
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
+case class STAR(r: Rexp) extends Rexp
-// some convenience for typing regular expressions
+// some convenience for typing in regular expressions
-import scala.language.implicitConversions
-import scala.language.reflectiveCalls
+import scala.language.implicitConversions
+import scala.language.reflectiveCalls
+
def charlist2rexp(s: List[Char]): Rexp = s match {
case Nil => ONE
@@ -38,190 +40,116 @@
}
// (1) Complete the function nullable according to
-// the definition given in the coursework; this
+// the definition given in the coursework; this
// function checks whether a regular expression
// can match the empty string and Returns a boolean
// accordingly.
-def nullable (r: Rexp) : Boolean = r match{
+def nullable (r: Rexp) : Boolean = r match {
case ZERO => false
case ONE => true
case CHAR(_) => false
- case ALT(a,b)=>nullable(a)||nullable(b)
- case SEQ(a,b) => nullable(a) && nullable(b)
+ case ALT(r1, r2) => nullable(r1) || nullable(r2)
+ case SEQ(r1, r2) => nullable(r1) && nullable(r2)
case STAR(_) => true
}
-
-/*val rex = "1~0.%|11"
-
-assert(der('1',rex) == SEQ(ONE,SEQ(CHAR(~),SEQ(CHAR(0),SEQ(CHAR(.),SEQ(CHAR(%),SEQ(CHAR(|),SEQ(CHAR(1),CHAR(1)))))))))
-
-assert(der('1',der('1',rex)) ==
- ALT(SEQ(ZERO,SEQ(CHAR(~),SEQ(CHAR(0),SEQ(CHAR(.),SEQ(CHAR(%),SEQ(CHAR(|),
- SEQ(CHAR(1),CHAR(1)))))))),SEQ(ZERO,SEQ(CHAR(0),SEQ(CHAR(.),SEQ(CHAR(%),
- SEQ(CHAR(|),SEQ(CHAR(1),CHAR(1))))))))*/
-
// (2) Complete the function der according to
// the definition given in the coursework; this
-// function calculates the derivative of a
+// function calculates the derivative of a
// regular expression w.r.t. a character.
-def der (c: Char, r: Rexp) : Rexp = r match{
+def der (c: Char, r: Rexp) : Rexp = r match {
case ZERO => ZERO
case ONE => ZERO
- case CHAR(d) => if (c==d) ONE else ZERO
- case ALT(a,b) => der(c,a)|der(c,b)
- case SEQ(a,b) => if(nullable(a)) {(der(c,a)~b)|der(c,b)}
- else der(c,a)~b
- case STAR(a) => der(c,a)~STAR(a)
+ case CHAR(d) => if (c == d) ONE else ZERO
+ case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
+ case SEQ(r1, r2) =>
+ if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
+ else SEQ(der(c, r1), r2)
+ case STAR(r1) => SEQ(der(c, r1), STAR(r1))
}
-println(der('a', ZERO | ONE))// == (ZERO | ZERO)
-println(der('a', (CHAR('a') | ONE) ~ CHAR('a')))// ==ALT((ONE | ZERO) ~ CHAR('a'), ONE)
-println(der('a', STAR(CHAR('a'))))// == (ONE ~ STAR(CHAR('a')))
-println(der('b', STAR(CHAR('a'))))// == (ZERO ~ STAR(CHAR('a'))))
-
-
-//ALT(SEQ(ZERO,ZERO),ZERO)
-//ALT(ALT(ZERO,ZERO),ALT(ZERO,ZERO))
-
-// * == |
-// + == ~
// (3) Complete the simp function according to
// the specification given in the coursework; this
// function simplifies a regular expression from
-// the inside out, like you would simplify arithmetic
-// expressions; however it does not simplify inside
+// the inside out, like you would simplify arithmetic
+// expressions; however it does not simplify inside
// STAR-regular expressions.
-/*
-def simp(r: Rexp) : Rexp = r match{
- case SEQ(ZERO,_) => ZERO
- case SEQ(_,ZERO) => ZERO
- case SEQ(ONE,a) => simp(a)
- case SEQ(a,ONE) => simp(a)
- case ALT(ZERO,a) => simp(a)
- case ALT(a,ZERO) => simp(a)
- case ALT(a,b) => if(a == b) simp(a) else r
- case _ => r
-}*/
-
-def simp(r: Rexp) : Rexp = r match{
- case SEQ(a,b) =>{ val sa = simp(a)
- val sb = simp(b)
- if(sa == ZERO || sb == ZERO) ZERO
- else if(sa == ONE) sb
- else if(sb == ONE) sa
- else SEQ(sa,sb)
- }
- case ALT(a,b) =>{ val sa = simp(a)
- val sb = simp(b)
- if(sa == ONE || sb == ONE) ONE
- else if(sa == ZERO) sb
- else if(sb == ZERO) sa
- else if(sa == sb) sa
- else ALT(sa,sb)
- }
- //case STAR(STAR(a)) => simp(STAR(a))
- //case STAR(a) => STAR(simp(a))
- case _ => r
- /*
- case SEQ(ZERO,_) => ZERO
- case SEQ(_,ZERO) => ZERO
- case SEQ(ONE,a) => simp(a)
- case SEQ(a,ONE) => simp(a)
- case SEQ(a,b) => SEQ(simp(a),simp(b))
- //case ALT(ZERO,a) => simp(a)
- case ALT(a,ZERO) => simp(a)
- case ALT(ONE,_) => ONE
- case ALT(_,ONE) => ONE
- case ALT(a,b) => {val sa = simp(a)
- if(sa == simp(b)) sa else r
- }
- case STAR(STAR(a)) => simp(STAR(a))
- case STAR(a) => STAR(simp(a))
- case _ => r*/
+def simp(r: Rexp) : Rexp = r match {
+ case ALT(r1, r2) => (simp(r1), simp(r2)) match {
+ case (ZERO, r2s) => r2s
+ case (r1s, ZERO) => r1s
+ case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s)
+ }
+ case SEQ(r1, r2) => (simp(r1), simp(r2)) match {
+ case (ZERO, _) => ZERO
+ case (_, ZERO) => ZERO
+ case (ONE, r2s) => r2s
+ case (r1s, ONE) => r1s
+ case (r1s, r2s) => SEQ(r1s, r2s)
+ }
+ case r => r
}
-/*val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
-println("TEST: " + simp(der('a', der('a', EVIL))))
-println(simp(ONE))
-val r1 = ALT(ZERO,ONE)
-val r2 = SEQ(ONE,ZERO)
-val r3 = SEQ(r1,SEQ(r2,r1))
-println("R1 = " + simp(r1))
-println(simp(r2))
-println(simp(r3))
-*/
-
-// (4) Complete the two functions below; the first
+// (4) Complete the two functions below; the first
// calculates the derivative w.r.t. a string; the second
// is the regular expression matcher taking a regular
// expression and a string and checks whether the
-// string matches the regular expression
+// string matches the regular expression.
-def ders (s: List[Char], r: Rexp ="") : Rexp = s match{
+def ders (s: List[Char], r: Rexp) : Rexp = s match {
case Nil => r
- case a::z => ders(z,simp(der(a,r)))
+ case c::s => ders(s, simp(der(c, r)))
}
-def matcher(r: Rexp, s: String): Boolean = {
- val derivatives = simp(ders(s.toList,r))
- nullable(derivatives)
-}
+// main matcher function
+def matcher(r: Rexp, s: String) = nullable(ders(s.toList, r))
// (5) Complete the size function for regular
-// expressions according to the specification
+// expressions according to the specification
// given in the coursework.
-def size(r: Rexp): Int = r match{
+
+def size(r: Rexp): Int = r match {
case ZERO => 1
case ONE => 1
case CHAR(_) => 1
- case SEQ(a,b) => 1 + size(a) + size(b)
- case ALT(a,b) => 1 + size(a) + size(b)
- case STAR(a) => 1 + size(a)
+ case ALT(r1, r2) => 1 + size(r1) + size (r2)
+ case SEQ(r1, r2) => 1 + size(r1) + size (r2)
+ case STAR(r1) => 1 + size(r1)
}
-println(der('a', ZERO | ONE))// == (ZERO | ZERO)
-println(der('a', (CHAR('a') | ONE) ~ CHAR('a')))// ==ALT((ONE | ZERO) ~ CHAR('a'), ONE)
-println(der('a', STAR(CHAR('a'))))// == (ONE ~ STAR(CHAR('a')))
-println(der('b', STAR(CHAR('a'))))// == (ZERO ~ STAR(CHAR('a'))))
-// some testing data
-/*
-
-assert(matcher(("a" ~ "b") ~ "c", "abc") == true) // => true
-assert(matcher(("a" ~ "b") ~ "c", "ab") == false) // => false
-
-
-// the supposedly 'evil' regular expression (a*)* b
-//val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
-assert(matcher(EVIL, "a" * 1000 ++ "b") == true) // => true
-assert(matcher(EVIL, "a" * 1000) == false) // => false
+// some testing data
+/*
+matcher(("a" ~ "b") ~ "c", "abc") // => true
+matcher(("a" ~ "b") ~ "c", "ab") // => false
+
+// the supposedly 'evil' regular expression (a*)* b
+val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+
+matcher(EVIL, "a" * 1000 ++ "b") // => true
+matcher(EVIL, "a" * 1000) // => false
// size without simplifications
-assert("28 " + size(der('a', der('a', EVIL))) ==28)// => 28
-assert("58 " + size(der('a', der('a', der('a', EVIL)))) ==58)// => 58
+size(der('a', der('a', EVIL))) // => 28
+size(der('a', der('a', der('a', EVIL)))) // => 58
// size with simplification
-assert("8 " + size(simp(der('a', der('a', EVIL)))) ==8)// => 8
-assert("8 " + size(simp(der('a', der('a', der('a', EVIL))))) ==8) // => 8
-
-*/
-
+size(simp(der('a', der('a', EVIL)))) // => 8
+size(simp(der('a', der('a', der('a', EVIL))))) // => 8
-/*
-// Python needs around 30 seconds for matching 28 a's with EVIL.
+// Python needs around 30 seconds for matching 28 a's with EVIL.
// Java 9 and later increase this to an "astonishing" 40000 a's in
-// 30 seconds.
+// around 30 seconds.
//
-// Lets see how long it really takes to match strings with
-// 5 Million a's...it should be in the range of a couple
-// of seconds.
+// Lets see how long it takes to match strings with
+// 5 Million a's...it should be in the range of a
+// couple of seconds.
def time_needed[T](i: Int, code: => T) = {
val start = System.nanoTime()
@@ -234,13 +162,15 @@
println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))))
}
-// another "power" test case
-simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE
+// another "power" test case
+simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(100).next) == ONE
// the Iterator produces the rexp
//
// SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)
//
-// where SEQ is nested 50 times.
+// where SEQ is nested 100 times.
+
+*/
-*/
+//}