# HG changeset patch # User Christian Urban # Date 1544102128 0 # Node ID 5549016ab10f573166c48826f4d843e0a7db2eaf # Parent 33c2655be47d93b7ff3a653a332f266c9af3c16f updated diff -r 33c2655be47d -r 5549016ab10f LINKS --- 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 diff -r 33c2655be47d -r 5549016ab10f README --- 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(); diff -r 33c2655be47d -r 5549016ab10f TAs --- 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 diff -r 33c2655be47d -r 5549016ab10f cws/cw05.pdf Binary file cws/cw05.pdf has changed diff -r 33c2655be47d -r 5549016ab10f cws/cw05.tex --- 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} diff -r 33c2655be47d -r 5549016ab10f marking1/compare --- /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 + + diff -r 33c2655be47d -r 5549016ab10f marking2/danube_test.sh --- 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 )) diff -r 33c2655be47d -r 5549016ab10f slides/slides04.tex --- 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 diff -r 33c2655be47d -r 5549016ab10f solutions1/drumb.scala --- 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 diff -r 33c2655be47d -r 5549016ab10f solutions5/bf.scala --- /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)) +*/ + + +} diff -r 33c2655be47d -r 5549016ab10f solutions5/mandelbrot.bf --- /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 ++++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[ +>>>>>>>>>]+[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-]>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+ +<<<<<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>>+>>>>>>>>>>>>>>>>>>>>>>>>>> +>+<<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+[>>>>>>[>>>>>>>[-]>>]<<<<<<<<<[<<<<<<<<<]>> +>>>>>[-]+<<<<<<++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<+++++++[-[->>> +>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[[-]>>>>>>[>>>>> +>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>> +[>>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<< +<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>+++++++++++++++[[ +>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[ +>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[ +-<<+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<< +<<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<< +[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>> +>>>>[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+ +<<<<<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>> +>>>>>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<< ++>>>>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<< +<]<+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>> +>>>>>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>> +>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<< +<<<]>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<< +<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[-> +>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<< +<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]<<<<<<<[->+>>>-<<<<]>>>>>>>>>+++++++++++++++++++ ++++++++>>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>[<<<<<<<+<[-<+>>>>+<<[-]]>[-<<[->+>>>- +<<<<]>>>]>>>>>>>>>>>>>[>>[-]>[-]>[-]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>>>>>>[>>>>> +[-<<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>[-<<<<<<<< +<+>>>>>>>>>]>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>>]+>[- +]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>>>>>>>]<<< +<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+>>]< +<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[->>>> +>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-]<->>> +[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[>>>>>>[-< +<<<<+>>>>>]<<<<<[->>>>>+<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>+>>>>>>>> +]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+ +>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[> +[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[- +]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>> +[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> +]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+> +>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>++++++++ ++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-<<<<<<<+ +>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[ +-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>>]>[-<<<<<<[->>>>>+<++<<<<]>>>>>[-< +<<<<+>>>>>]<->+>]<[->+<]<<<<<[->>>>>+<<<<<]>>>>>>[-]<<<<<<+>>>>[-<<<<->>>>]+<<<< +[->>>>->>>>>[>>[-<<->>]+<<[->>->[-<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-] ++>>>>>>[>>>>>>>>>]>+<]]+>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<<<<<<<<<<[<<<<< +<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<< +[<<<<<<<<<]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<< +<<<+<[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<< +<<<<<+>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<< +<<<<<<<<<<]>>>>[-]<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+<]>>>>>>>>]<<< +<<<<<+<[>[->>>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>[->>>>+<<<<]>]<[->>>>-<<<<<<< +<<<<<<<+>>>>>>>>>>]<]>>[->>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>>+<<<< +]<<<<<<<<<<<]>>>>>>+<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>>>>>>>>>]<<<<<<<<< +[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<<<<<< ++>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<<<<<< +<<<<<]]>[-]>>[-]>[-]>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-< +<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[ +[>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+ +[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->> +[-<<+>>]<<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<< +<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[ +>[-]<->>>[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[ +>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]> +>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>[-]>>>>+++++++++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<< +<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<< +<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[- +<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>> +>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>>> +[-<<<->>>]<<<[->>>+<<<]>>>>>>>>]<<<<<<<<+<[>[->+>[-<-<<<<<<<<<<+>>>>>>>>>>>>[-<< ++>>]<]>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<<<]>>[-<+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<]> +[-<<+>>]<<<<<<<<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>> +>>>>>>]<<<<<<<<+<[>[->+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>[-<+>]>]<[-<-<<<<<<<<<<+>>>> +>>>>>>>]<<]>>>[-<<+>[-<-<<<<<<<<<<+>>>>>>>>>>>]>]<[-<+>]<<<<<<<<<<<<]>>>>>+<<<<< +]>>>>>>>>>[>>>[-]>[-]>[-]>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>>>[-<<<<< +<+>>>>>>]<<<<<<[->>>>>>+<<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>> +>]>>[-<<<<<<<[->>>>>+<++<<<<]>>>>>[-<<<<<+>>>>>]<->+>>]<<[->>+<<]<<<<<[->>>>>+<< +<<<]+>>>>[-<<<<->>>>]+<<<<[->>>>->>>>>[>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<< +<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>[-<<->>]+<<[->>->[-<<<+>>>]< +<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]< +<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+ +<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>[->>>+<<<]>]<[->>>- +<<<<<<<<<<<<<+>>>>>>>>>>]<]>>[->>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>+<<< +]<<<<<<<<<<<]>>>>>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]]>>>>[-<<<<+> +>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<<[->>>- +<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[ +->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<<<<<]]>>>>[-]<<<<]>>>>[-<<<<+>> +>>]<<<<[->>>>+>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>[>>>>>> +>>>]<<<<<<<<<[>[->>>>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<< +<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<< +<<<<]]>>>>>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>[-<<<<+ +>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<+>>>>> +]<<<<<[->>>>>+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>> +>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>> +>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[-<<+ +>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[> +[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[- +]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>> +[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<< +<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>> +>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<+>>> +>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+ +<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>> +>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>> +>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<<<<] +>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<<<<< +]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->>>+< +<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]> +>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>->>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>]<<+>>>>[-<<<< +->>>>]+<<<<[->>>>-<<<<<<.>>]>>>>[-<<<<<<<.>>>>>>>]<<<[-]>[-]>[-]>[-]>[-]>[-]>>>[ +>[-]>[-]>[-]>[-]>[-]>[-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-]>>>>]<<<<<<<<< +[<<<<<<<<<]>+++++++++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+>>>>>>>>>+<<<<<<<< +<<<<<<[<<<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+[-]>>[>>>>>>>>>]<<<<< +<<<<[>>>>>>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<[<<<<<<<<<]>>>>>>>[-]+>>>]<<<< +<<<<<<]]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+>>[>+>>>>[-<<<<->>>>]<<<<[->>> +>+<<<<]>>>>>>>>]<<+<<<<<<<[>>>>>[->>+<<]<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<< +<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<<<<<[->>>>>>+<<<<<<]< ++<<<<<<<<<]>>>>>>>-<<<<[-]+<<<]+>>>>>>>[-<<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>->>[>> +>>>[->>+<<]>>>>]<<<<<<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<< +<<<<[->>>>>>+<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+<<< +<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<<<<<->>>>>]+<<<<<[->>>>>->>[-<<<<<<<+>>>>>>>]<<<< +<<<[->>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>[-< +<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>-<<[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<<<<<<<<<[<<< +<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<< +<<[<<<<<<<<<]>>>>[-]<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>-<<<<<[<<<<<<< +<<]]>>>]<<<<.>>>>>>>>>>[>>>>>>[-]>>>]<<<<<<<<<[<<<<<<<<<]>++++++++++[-[->>>>>>>> +>+<<<<<<<<<]>>>>>>>>>]>>>>>+>>>>>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-<<<<<< +<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+[-]>[>>>>>>>>>]<<<<<<<<<[>>>>>>>>[-<<<<<<<+>>>>>> +>]<<<<<<<[->>>>>>>+<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+>>]<<<<<<<<<<]]>>>>>>>>[-<<<<< +<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+>[>+>>>>>[-<<<<<->>>>>]<<<<<[->>>>>+<<<<<]>>>>>> +>>]<+<<<<<<<<[>>>>>>[->>+<<]<<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[-]<- +>>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<<]<+<<<<<< +<<<]>>>>>>>>-<<<<<[-]+<<<]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>->[>>> +>>>[->>+<<]>>>]<<<<<<<<<[>[-]<->>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<< +<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>> ++>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<<->>>>>>]+< +<<<<<[->>>>>>->>[-<<<<<<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+<<<<<<<<<<<<<<<<<[<<<<<<< +<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>> +-<<[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>> +>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>[-]<<<++++ ++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>->>>>>>>>>>>>>>>>>>>>>>>>>>>-<<<<<<[<<<< +<<<<<]]>>>] diff -r 33c2655be47d -r 5549016ab10f solutions5/sierpinski.bf --- /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 @@ +++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[ +->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<< +]>.>+[>>]>+] diff -r 33c2655be47d -r 5549016ab10f testing4/re.scala --- 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. + +*/ -*/ +//}