--- a/cws/cw04.tex Wed Nov 28 23:26:47 2018 +0000
+++ b/cws/cw04.tex Thu Nov 29 17:15:11 2018 +0000
@@ -46,6 +46,20 @@
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
@@ -79,16 +93,18 @@
% BF IDE
% https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5
-\section*{Coursework 8 (Regular Expressions and Brainf***)}
+\section*{Coursework 9 (Scala)}
-This coursework is worth 10\%. It is about regular expressions,
-pattern matching and an interpreter. The first part is due on 30
-November at 11pm; the second, more advanced part, is due on 21
-December at 11pm. In the first part, you are asked to implement a
+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 Java
-and Python can sometimes be extremely slow. The advanced part is about
-an interpreter for a very simple programming language.\bigskip
+expressions. The background is that regular expression matching in
+languages like Java, JavaScript and Python can sometimes be excruciatingly
+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
\IMPORTANT{}
@@ -98,6 +114,40 @@
\DISCLAIMER{}
+\subsection*{Reference Implementation}
+
+This Scala assignment comes with three reference implementations in form of
+\texttt{jar}-files. This allows you to run any test cases on your own
+computer. For example you can call Scala on the command line with the
+option \texttt{-cp re.jar} and then query any function from the
+\texttt{re.scala} template file. As usual you have to
+prefix the calls with \texttt{CW9a}, \texttt{CW9b} and \texttt{CW9c}.
+Since some tasks are time sensitive, you can check the reference
+implementation as follows: if you want to know how long it takes
+to match strings of $a$'s using the regular expression $(a^*)^*\cdot b$
+you can querry as follows:
+
+
+
+\begin{lstlisting}[language={},xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]
+$ scala -cp re.jar
+scala> import CW9a._
+scala> for (i <- 0 to 5000000 by 500000) {
+ | println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))) + "secs.")
+ | }
+0 0.00002 secs.
+500000 0.10608 secs.
+1000000 0.22286 secs.
+1500000 0.35982 secs.
+2000000 0.45828 secs.
+2500000 0.59558 secs.
+3000000 0.73191 secs.
+3500000 0.83499 secs.
+4000000 0.99149 secs.
+4500000 1.15395 secs.
+5000000 1.29659 secs.
+\end{lstlisting}%$
+
\subsection*{Part 1 (6 Marks)}
@@ -116,14 +166,13 @@
& $|$ & $r_1 + r_2$ & can match a string either with $r_1$ or with $r_2$\\
& $|$ & $r_1\cdot r_2$ & can match the first part of a string with $r_1$ and\\
& & & then the second part with $r_2$\\
- & $|$ & $r^*$ & can match zero or more times $r$\\
+ & $|$ & $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
+Why? Regular expressions are
+one of the 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
@@ -136,6 +185,10 @@
\item[$\bullet$] \url{http://davidvgalbraith.com/how-i-fixed-atom/}
\end{itemize}}
+% Knowing how to match regular expressions and strings will let you
+% solve a lot of problems that vex other humans.
+
+
\subsubsection*{Tasks (file re.scala)}
The file \texttt{re.scala} has already a definition for regular
@@ -157,7 +210,7 @@
\begin{itemize}
-\item[(1a)] Implement a function, called \textit{nullable}, by
+\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
@@ -175,7 +228,7 @@
\end{tabular}
\end{center}~\hfill[1 Mark]
-\item[(1b)] Implement a function, called \textit{der}, by recursion over
+\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:
@@ -198,7 +251,7 @@
\begin{center}
\begin{tabular}{lcll}
- $\textit{der}\;a\;r$ & $=$ & $(\ONE \cdot b)\cdot c$ & ($= r'$)\\
+ $\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}
@@ -210,7 +263,7 @@
\begin{center}
\begin{tabular}{lcll}
$\textit{der}\;a\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$ \\
- $\textit{der}\;b\;r'$ & $=$ & $((\ZERO \cdot b) + \ONE)\cdot c$ & ($= r''$)\\
+ $\textit{der}\;b\;r'$ & $=$ & $((\ZERO \cdot b) + \ONE)\cdot c$ & \quad($= r''$)\\
$\textit{der}\;c\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$
\end{tabular}
\end{center}
@@ -231,7 +284,7 @@
Note, the last derivative can match the empty string, that is it is \textit{nullable}.\\
\mbox{}\hfill\mbox{[1 Mark]}
-\item[(1c)] Implement the function \textit{simp}, which recursively
+\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
@@ -255,7 +308,9 @@
simplifies to just $r_1$. \textbf{Hint:} Regular expressions can be
seen as trees and there are several methods for traversing
trees. One of them corresponds to the inside-out traversal, which is
- sometimes also called post-order traversal. Furthermore,
+ 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
@@ -263,9 +318,9 @@
for example the $y \cdot 0$ by $0$, or $1\cdot x$ by $x$, and then
look whether more rules are applicable. If you organise the
simplification in an inside-out fashion, it is always clear which
- rule should be applied next.\hfill[2 Marks]
+ rule should be applied next.\hfill[1 Mark]
-\item[(1d)] Implement two functions: The first, called \textit{ders},
+\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:
@@ -288,7 +343,7 @@
true for the regular expression $(a\cdot b)\cdot c$ and the string
$abc$, but false if you give it the string $ab$. \hfill[1 Mark]
-\item[(1e)] Implement a function, called \textit{size}, by recursion
+\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:
@@ -309,6 +364,21 @@
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 here is that you will be marked for some ``power''
+ test cases. For example can your matcher decide within 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}
@@ -337,7 +407,7 @@
The purpose of the $\textit{simp}$ function is to keep the regular
expressions small. Normally the derivative function makes the regular
-expression bigger (see the SEQ case and the example in (1b)) and the
+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
@@ -350,15 +420,15 @@
If you want to see how badly the regular expression matchers do in
-Java\footnote{Version 8 and below; Version 9 does not seem to be as
- catastrophic, but still worse than the regular expression matcher
-based on derivatives.} and in Python with the `evil' regular
-expression $(a^*)^*\cdot b$, then have a look at the graphs below (you
-can try it out for yourself: have a look at the file
-\texttt{catastrophic.java} and \texttt{catastrophic.py} on
-KEATS). Compare this with the matcher you have implemented. How long
-can the string of $a$'s be in your matcher and still stay within the
-30 seconds time limit?
+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 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@{}}
@@ -380,10 +450,11 @@
axis lines=left,
width=6cm,
height=5.5cm,
- legend entries={Python, Java 8},
+ 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}
&
@@ -413,231 +484,109 @@
\subsection*{Part 2 (4 Marks)}
-Coming from Java or C++, you might think Scala is a quite esoteric
-programming language. But remember, some serious companies have built
-their business on
-Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}}
-And there are far, far more esoteric languages out there. One is
-called \emph{brainf***}. You are asked in this part to implement an
-interpreter for this language.
+The \emph{Shunting Yard Algorithm} has been developed by Edsger Dijkstra,
+an influential computer scientist who developed many well-known
+algorithms. This algorithm transforms the usual infix notation of
+arithmetic expressions into the postfix notation, sometimes also
+called reverse Polish notation.
-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
+Why on Earth do people use the postfix notation? It is much more
+convenient to work with the usual infix notation for arithmetic
+expressions. Most modern calculators (as opposed to the ones used 20
+years ago) understand infix notation. So why on Earth? \ldots{}Well,
+many computers under the hood, even nowadays, use postfix notation
+extensively. For example if you give to the Java compiler the
+expression $1 + ((2 * 3) + (4 - 3))$, it will generate for it the Java Byte
+code
+
+\begin{lstlisting}[language=JVMIS,numbers=none]
+ldc 1
+ldc 2
+ldc 3
+imul
+ldc 4
+ldc 3
+isub
+iadd
+iadd
+\end{lstlisting}
\noindent
-As mentioned above, brainf*** has 8 single-character commands, namely
-\texttt{'>'}, \texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'},
-\texttt{','}, \texttt{'['} and \texttt{']'}. Every other character is
-considered a comment. Brainf*** operates on memory cells containing
-integers. For this it uses a single memory pointer that points at each
-stage to one memory cell. This pointer can be moved forward by one
-memory cell by using the command \texttt{'>'}, and backward by using
-\texttt{'<'}. The commands \texttt{'+'} and \texttt{'-'} increase,
-respectively decrease, by 1 the content of the memory cell to which
-the memory pointer currently points to. The commands for input/output
-are \texttt{','} and \texttt{'.'}. Output works by reading the content
-of the memory cell to which the memory pointer points to and printing
-it out as an ASCII character. Input works the other way, taking some
-user input and storing it in the cell to which the memory pointer
-points to. The commands \texttt{'['} and \texttt{']'} are looping
-constructs. Everything in between \texttt{'['} and \texttt{']'} is
-repeated until a counter (memory cell) reaches zero. A typical
-program in brainf*** looks as follows:
-
-\begin{center}
-\begin{verbatim}
- ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
- ..+++.>>.<-.<.+++.------.--------.>>+.>++.
-\end{verbatim}
-\end{center}
+where the command \texttt{ldc} loads a constant onto a stack, and \texttt{imul},
+\texttt{isub} and \texttt{iadd} are commands acting on the stack. Clearly this
+is the arithmetic expression in postfix notation.\bigskip
\noindent
-This one prints out Hello World\ldots{}obviously.
-
-\subsubsection*{Tasks (file bf.scala)}
+The shunting yard algorithm processes an input token list using an
+operator stack and an output list. The input consists of numbers,
+operators ($+$, $-$, $*$, $/$) and parentheses, and for the purpose of
+the assignment we assume the input is always a well-formed expression
+in infix notation. The algorithm uses information about the
+precedences of the operators (given in the template file). The
+algorithm processes the input token list as follows:
\begin{itemize}
-\item[(2a)] Brainf*** memory is represented by a \texttt{Map} from
- integers to integers. The empty memory is represented by
- \texttt{Map()}, that is nothing is stored in the
- memory. \texttt{Map(0 -> 1, 2 -> 3)} clearly stores \texttt{1} at
- memory location \texttt{0}; at \texttt{2} it stores \texttt{3}. The
- convention is that if we query the memory at a location that is
- \emph{not} defined in the \texttt{Map}, we return \texttt{0}. Write
- a function, \texttt{sread}, that takes a memory (a \texttt{Map}) and
- a memory pointer (an \texttt{Int}) as argument, and safely reads the
- corresponding memory location. If the \texttt{Map} is not defined at
- the memory pointer, \texttt{sread} returns \texttt{0}.
-
- Write another function \texttt{write}, which takes a memory, a
- memory pointer and an integer value as argument and updates the
- \texttt{Map} with the value at the given memory location. As usual
- the \texttt{Map} is not updated `in-place' but a new map is created
- with the same data, except the value is stored at the given memory
- pointer.\hfill[1 Mark]
-
-\item[(2b)] Write two functions, \texttt{jumpRight} and
- \texttt{jumpLeft} that are needed to implement the loop constructs
- of brainf***. They take a program (a \texttt{String}) and a program
- counter (an \texttt{Int}) as argument and move right (respectively
- left) in the string in order to find the \textbf{matching}
- opening/closing bracket. For example, given the following program
- with the program counter indicated by an arrow:
-
- \begin{center}
- \texttt{--[\barbelow{.}.+>--],>,++}
- \end{center}
-
- then the matching closing bracket is in 9th position (counting from 0) and
- \texttt{jumpRight} is supposed to return the position just after this
-
- \begin{center}
- \texttt{--[..+>--]\barbelow{,}>,++}
- \end{center}
+\item If there is a number as input token, then this token is
+ transferred to the output list. Then the rest of the input is
+ processed.
+\item If there is an operator as input token, then you need to check
+ what is on top of the operator stack. If there are operators with
+ a higher or equal precedence, these operators are first popped off
+ the stack and moved to the output list. Then the operator from the input
+ is pushed onto the stack and the rest of the input is processed.
+\item If the input is a left-parenthesis, you push it on to the stack
+ and continue processing the input.
+\item If the input is a right-parenthesis, then you move all operators
+ from the stack to the output list until you reach the left-parenthesis.
+ Then you discharge the $($ and $)$ from the input and stack, and continue
+ processing.
+\item If the input is empty, then you move all remaining operators
+ from the stack to the output list.
+\end{itemize}
- meaning it jumps to after the loop. Similarly, if you are in 8th position
- then \texttt{jumpLeft} is supposed to jump to just after the opening
- bracket (that is jumping to the beginning of the loop):
-
- \begin{center}
- \texttt{--[..+>-\barbelow{-}],>,++}
- \qquad$\stackrel{\texttt{jumpLeft}}{\longrightarrow}$\qquad
- \texttt{--[\barbelow{.}.+>--],>,++}
- \end{center}
-
- Unfortunately we have to take into account that there might be
- other opening and closing brackets on the `way' to find the
- matching bracket. For example in the brainf*** program
-
- \begin{center}
- \texttt{--[\barbelow{.}.[+>]--],>,++}
- \end{center}
+\subsubsection*{Tasks (file postfix.scala)}
- we do not want to return the index for the \texttt{'-'} in the 9th
- position, but the program counter for \texttt{','} in 12th
- position. The easiest to find out whether a bracket is matched is by
- using levels (which are the third argument in \texttt{jumpLeft} and
- \texttt{jumpLeft}). In case of \texttt{jumpRight} you increase the
- level by one whenever you find an opening bracket and decrease by
- one for a closing bracket. Then in \texttt{jumpRight} you are looking
- for the closing bracket on level \texttt{0}. For \texttt{jumpLeft} you
- do the opposite. In this way you can find \textbf{matching} brackets
- in strings such as
-
- \begin{center}
- \texttt{--[\barbelow{.}.[[-]+>[.]]--],>,++}
- \end{center}
-
- for which \texttt{jumpRight} should produce the position:
-
- \begin{center}
- \texttt{--[..[[-]+>[.]]--]\barbelow{,}>,++}
- \end{center}
-
- It is also possible that the position returned by \texttt{jumpRight} or
- \texttt{jumpLeft} is outside the string in cases where there are
- no matching brackets. For example
+\begin{itemize}
+\item[(7)] Implement the shunting yard algorithm outlined above. The
+ function, called \texttt{syard}, takes a list of tokens as first
+ argument. The second and third arguments are the stack and output
+ list represented as Scala lists. The most convenient way to
+ implement this algorithm is to analyse what the input list, stack
+ and output look like in each step using pattern-matching. The
+ algorithm transforms for example the input
- \begin{center}
- \texttt{--[\barbelow{.}.[[-]+>[.]]--,>,++}
- \qquad$\stackrel{\texttt{jumpRight}}{\longrightarrow}$\qquad
- \texttt{--[..[[-]+>[.]]-->,++\barbelow{\;\phantom{+}}}
- \end{center}
- \hfill[1 Mark]
-
+ \[
+ \texttt{List(3, +, 4, *, (, 2, -, 1, ))}
+ \]
-\item[(2c)] Write a recursive function \texttt{run} that executes a
- brainf*** program. It takes a program, a program counter, a memory
- pointer and a memory as arguments. If the program counter is outside
- the program string, the execution stops and \texttt{run} returns the
- memory. If the program counter is inside the string, it reads the
- corresponding character and updates the program counter \texttt{pc},
- memory pointer \texttt{mp} and memory \texttt{mem} according to the
- rules shown in Figure~\ref{comms}. It then calls recursively
- \texttt{run} with the updated data.
+ into the postfix output
- 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
-
- \begin{center}
- \url{https://esolangs.org/wiki/Brainfuck}
- \end{center}\hfill[2 Marks]
+ \[
+ \texttt{List(3, 4, 2, 1, -, *, +)}
+ \]
- \begin{figure}[p]
- \begin{center}
- \begin{tabular}{|@{}p{0.8cm}|l|}
- \hline
- \hfill\texttt{'>'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
- $\bullet$ & $\texttt{pc} + 1$\\
- $\bullet$ & $\texttt{mp} + 1$\\
- $\bullet$ & \texttt{mem} unchanged
- \end{tabular}\\\hline
- \hfill\texttt{'<'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
- $\bullet$ & $\texttt{pc} + 1$\\
- $\bullet$ & $\texttt{mp} - 1$\\
- $\bullet$ & \texttt{mem} unchanged
- \end{tabular}\\\hline
- \hfill\texttt{'+'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
- $\bullet$ & $\texttt{pc} + 1$\\
- $\bullet$ & $\texttt{mp}$ unchanged\\
- $\bullet$ & \texttt{mem} updated with \texttt{mp -> mem(mp) + 1}\\
- \end{tabular}\\\hline
- \hfill\texttt{'-'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
- $\bullet$ & $\texttt{pc} + 1$\\
- $\bullet$ & $\texttt{mp}$ unchanged\\
- $\bullet$ & \texttt{mem} updated with \texttt{mp -> mem(mp) - 1}\\
- \end{tabular}\\\hline
- \hfill\texttt{'.'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
- $\bullet$ & $\texttt{pc} + 1$\\
- $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
- $\bullet$ & print out \,\texttt{mem(mp)} as a character\\
- \end{tabular}\\\hline
- \hfill\texttt{','} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
- $\bullet$ & $\texttt{pc} + 1$\\
- $\bullet$ & $\texttt{mp}$ unchanged\\
- $\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\
- \multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}}
- \end{tabular}\\\hline
- \hfill\texttt{'['} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
- \multicolumn{2}{@{}l}{if \texttt{mem(mp) == 0} then}\\
- $\bullet$ & $\texttt{pc = jumpRight(prog, pc + 1, 0)}$\\
- $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\
- \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) != 0} then}\\
- $\bullet$ & $\texttt{pc} + 1$\\
- $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
- \end{tabular}
- \\\hline
- \hfill\texttt{']'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
- \multicolumn{2}{@{}l}{if \texttt{mem(mp) != 0} then}\\
- $\bullet$ & $\texttt{pc = jumpLeft(prog, pc - 1, 0)}$\\
- $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\
- \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) == 0} then}\\
- $\bullet$ & $\texttt{pc} + 1$\\
- $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
- \end{tabular}\\\hline
- any other char & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
- $\bullet$ & $\texttt{pc} + 1$\\
- $\bullet$ & \texttt{mp} and \texttt{mem} unchanged
- \end{tabular}\\
- \hline
- \end{tabular}
- \end{center}
- \caption{The rules for how commands in the brainf*** language update the program counter \texttt{pc},
- memory pointer \texttt{mp} and memory \texttt{mem}.\label{comms}}
- \end{figure}
-\end{itemize}\bigskip
+ You can assume the input list is always a list representing
+ a well-formed infix arithmetic expression.\hfill[1 Mark]
+
+\item[(8)] Implement a compute function that takes a postfix expression
+ as argument and evaluates it generating an integer as result. It uses a
+ stack to evaluate the postfix expression. The operators $+$, $-$, $*$
+ are as usual; $/$ is division on integers, for example $7 / 3 = 2$.
+ \hfill[1 Mark]
+\end{itemize}
+
+\subsubsection*{Task (file postfix2.scala)}
+
+\begin{itemize}
+\item[(9)] Extend the code in (7) and (8) to include the power
+ operator. This requires proper account of associativity of
+ the operators. The power operator is right-associative, whereas the
+ other operators are left-associative. Left-associative operators
+ are popped off if the precedence is bigger or equal, while
+ right-associative operators are only popped off if the precedence is
+ bigger. The compute function in this task should use
+ \texttt{Long}s, rather than \texttt{Int}s.\hfill[2 Marks]
+\end{itemize}