# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1415376110 0
# Node ID e8c0269c8ff508ff2adf8d14a8bf7db0246a6982
# Parent  08d99acd35e822b41b9c9b0a261426ef18be1805
update

diff -r 08d99acd35e8 -r e8c0269c8ff5 coursework/cw03.pdf
Binary file coursework/cw03.pdf has changed
diff -r 08d99acd35e8 -r e8c0269c8ff5 coursework/cw03.tex
--- a/coursework/cw03.tex	Fri Nov 07 15:34:28 2014 +0000
+++ b/coursework/cw03.tex	Fri Nov 07 16:01:50 2014 +0000
@@ -17,12 +17,12 @@
 \subsection*{Question 1 (marked with 1\%)}
 
 Design a grammar for the WHILE language and give the grammar 
-rules. The main categories of non-terminal will be:
+rules. The main categories of non-terminal should be:
 
 \begin{itemize}
 \item arithmetic expressions (with the operations from the
   previous coursework, such as \pcode{+}, \pcode{*} and so on)
-\item boolean expressions (such as \pcode{<}, \pcode{!=} and 
+\item boolean expressions (such as \pcode{<}, \code{!=} and 
   so on)
 \item single statements (such as \pcode{skip}, assignments, \pcode{if}s,
   \pcode{while}-loops and so on)
@@ -32,18 +32,18 @@
 
 \subsection*{Question 2 (marked with 2\%)}
 
-You should implement a parser based on parser combinators
-for the WHILE language. Be careful that the parser takes
-as input a stream of token generated by the tokenizer from
-the previous courswork. Your parser should be able to handle
+You should implement a parser for the WHILE language using
+parser combinators. Be careful that the parser takes as input
+a stream, or list, of tokens generated by the tokenizer from
+the previous coursework. Your parser should be able to handle
 the WHILE programs in Figures~\ref{fib} and \ref{loop}.
+In addition give the parse tree for the statement:
 
-Give the parse tree for the statement:
+\begin{lstlisting}[language=While,numbers=none]
+if (a < b) then skip else a := a * b + 1
+\end{lstlisting}
 
-\begin{center}
-\code{if (a < b) then skip else a := a * b + 1}
-\end{center}
-
+\noindent
 A (possibly incomplete) datatype for parse trees in Scala would
 look as in Figure~\ref{trees}.
 
@@ -68,15 +68,46 @@
 case object False extends BExp
 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp
 \end{lstlisting}
-\caption{The datatype for parse trees in Scala.}
+\caption{The datatype for parse trees in Scala.\label{trees}}
 \end{figure}
 
 \subsection*{Question 3 (marked with 2\%)}
 
-Implement an interpreter for the WHILE language you
-designed and parsed above. 
+Implement an interpreter for the WHILE language you designed
+and parsed in Question 1 and 2. This interpreter should take
+as input a parse tree. However be careful because programs
+contain variables and variable assignments. This means
+you need to maintain a kind of memory, or environment,
+where you can look up a value of a variable and also
+store a new value if it is assigned. Therefore an
+evaluation function (interpreter) needs to look roughly as 
+follows 
+
+\begin{lstlisting}[numbers=none]
+eval_stmt(stmt, env)
+\end{lstlisting}
 
+\noindent 
+where \pcode{stmt} corresponds to the parse tree
+of the program and \pcode{env} is an environment
+acting as a store for variable values. 
+Consider the Fibonacci program in Figure~\ref{fib}.
+At the beginning of the program this store will be 
+empty, but needs to be extended in line 3 and 4 where 
+the variables \pcode{minus1} and \pcode{minus2}
+are assigned values. These values need to be reassigned in
+lines 7 and 8. The program should  be interpreted
+according to straightforward rules: for example an
+if-statement will ``run'' the if-branch if the boolean
+evaluates to \pcode{true}, otherwise the else-branch.
+Loops should be run as long as the boolean is \pcode{true}.
 
+Give some time measurements for your interpreter
+and the loop program in Figure~\ref{loop}. For example
+how long does your interpreter take when \pcode{start}
+is initialised with 100, 500 and so on. How far can
+you scale this value if you are willing to wait, say
+1 Minute.
 
 \begin{figure}[p]
 \begin{center}