\definecolor{codegray}{gray}{0.9}

\newcommand{\code}[1]{\colorbox{codegray}{\texttt{#1}}}

object-oriented programming-styles, and has received in the

last five years quite a bit of attention. One reason for this

attention is that, like the Java programming language, it

compiles to the Java Virtual Machine (JVM) and therefore can

run under MacOSX, Linux and Windows.\footnote{There are also

experimental backends for Android and JavaScript.} Unlike

Java, however, Scala often allows programmers to write concise

and elegant code; some therefore say Scala is the much better

Java. If you want to try it out, the Scala compiler can be

Why do I use Scala in the AFL course? Actually, you can do

\emph{any} part of the programming coursework in \emph{any}

programming language you like. I use Scala for showing you

code during the lectures because its functional

programming-style allows me to implement some of the functions

we will discuss with very small and elegant code. Since the

compiler is free, you can download it and run every example I

give. But if you prefer, you can also translate the examples

into any other functional language, for example Haskell, ML,

F\# and so on.

Writing programs in Scala can be done with the Eclipse IDE and

also with IntelliJ, but for the small programs we will look at

the Emacs-editor id good for me and I will run programs on the

command line. One advantage of Scala over Java is that it

includes an interpreter (a REPL, or Read-Eval-Print-Loop) with

which you can run and test small code-snippets without the

need of the compiler. This helps a lot for interactively

\noindent The precise output may vary due to the platform

where you installed Scala. At the scala prompt you can type

things like {\tt 2 + 3} \keys{Ret} and the output will be

\noindent indicating that the result of the addition is of

type {\tt Int} and the actual result is {\tt 5}. Another

example you can type in is

actually produce a result (there is no {\tt res\_}), rather it

is a function that causes the \emph{side-effect} of printing

out a string. Once you are more familiar with the functional

programming-style, you will know what the difference is

between a function that returns a result, like addition, and a

function that causes a side-effect, like {\tt print}. We shall

come back to this later, but if you are curious, the latter

kind of functions always have as return type {\tt Unit}.

For example in ``every-day Mathematics'' we would define

regular expressions simply by the grammar

inner nodes and three kinds of leave nodes). If you are

familiar with Java, it might be an instructive exercise to

define this kind of inductive datatypes in

Java.\footnote{Happy programming! ;o)}

Implementing the regular expressions from above in Scala is

very simple: It first requires an \emph{abstract class}, say,

{\tt Rexp}. This will act as type for regular expressions.

Second, it requires some instances. The cases for

$\varnothing$ and $\epsilon$ do not have any arguments, while

in the other cases we do have arguments. For example the

character regular expression needs to take as an argument the

character it is supposed to recognise. In Scala, the cases

without arguments are called \emph{case objects}, while the

ones with arguments are \emph{case classes}. The corresponding

code is as follows:

\begin{quote}

\begin{lstlisting}[language=Scala]

abstract class Rexp 

case object NULL extends Rexp

case object EMPTY extends Rexp

case class CHAR (c: Char) extends Rexp

case class SEQ (r1: Rexp, r2: Rexp) extends Rexp 

case class ALT (r1: Rexp, r2: Rexp) extends Rexp 

case class STAR (r: Rexp) extends Rexp 

\end{lstlisting}

\end{quote}

\noindent Given the grammar above, I hope you can see the

underlying pattern. In order to be an instance of {\tt Rexp},

each case object or case class needs to extend {\tt Rexp}. If

you want to play with such definitions, feel free to define

for example binary trees.

Once you make a definition like the one above, you can 

represent, say, the regular expression for $a + b$ as

{\tt ALT(CHAR('a'), CHAR('b'))}. If you want to assign 

this regular expression to a variable, you can just type

\begin{alltt}

scala> val r = ALT(CHAR('a'), CHAR('b'))

r: ALT = ALT(CHAR(a),CHAR(b))

\end{alltt}

\noindent In order to make such assignments there is no

constructor need in the class (like in Java). However, if

there is the need, you can of course define such a constructor

in Scala. 

Note that Scala says the variable {\tt r} is of type {\tt

ALT}, not {\tt Rexp}. Scala always tries to find the most

general type that is needed for a variable, but does not

``over-generalise''. In this case there is no need to give

{\tt r} the more general type of {\tt Rexp}. This is different

if you want to form a list of regular expressions, for example

\begin{alltt}

scala> val ls = List(ALT(CHAR('a'), CHAR('b')), NULL)

ls: List[Rexp] = List(ALT(CHAR(a),CHAR(b)), NULL)

\end{alltt}

\noindent In this case Scala needs to assign a type to the

regular expressions, so that it is compatible with the fact

that list can only contain elements of a single type, in this

case this is {\tt Rexp}.\footnote{If you type in this example,

you will notice that the type contains some further

information, but lets ignore this for the moment.} Note that if a type takes another

type as argument, this is written for example as

{\tt List[Rexp]}.

\subsection*{Functions and Pattern-Matching}

\subsection*{Types}

\subsection*{Cool Stuff}