\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usepackage{marvosym}

\begin{document}

\section*{A Crash-Course on Scala}

Scala is a programming language that combines functional and

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

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

this attention is that, like the Java programming language,

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

Scala programs 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 very concise and elegant code.

Some therefore say Scala is the much better Java. A number of

\begin{quote}

\url{http://www.scala-lang.org}

\end{quote}

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

\emph{any} part of the 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 the functions we will discuss with very small

code-snippets. If I had to do this in Java, for example, I

would first have to go through heaps of boilerplate code and

the code-snippets would not look pretty. Since the Scala

compiler is free, you can download the code-snippets and run

every example I give. But if you prefer, you can also easily

translate them into any other functional language, for example

Haskell, Standard ML, F$^\#$, Ocaml and so on.

Developing programs in Scala can be done with the Eclipse IDE

and also with IntelliJ IDE, but for the small programs I will

develop the good old Emacs-editor is adequate for me and I

will run the programs on the command line. One advantage of

Scala over Java is that it includes an interpreter (a REPL, or

\underline{R}ead-\underline{E}val-\underline{P}rint-\underline{L}oop)

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

the need of the compiler. This helps a lot with interactively

developing programs. Once you installed Scala, you can start

the interpreter by typing on the command line:

\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]

$ scala

Welcome to Scala version 2.11.2 (Java HotSpot(TM) 64-Bit Server VM).

Type in expressions to have them evaluated.

Type :help for more information.

scala>

\end{lstlisting}

\noindent The precise response may vary due to the platform

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

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

\begin{lstlisting}[language=Scala,numbers=none]

scala> 2 + 3

res0: Int = 5

\end{lstlisting}

\noindent indicating that the result of the addition is of

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

example you can try out is

\begin{lstlisting}[language=Scala,numbers=none]

scala> print("hello world")

hello world

\end{lstlisting}

\noindent Note that in this case there is no result. The

reason is that \code{print} does not actually produce a result

(there is no \code{resXX} and no type), 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 \code{print}. We

shall come back to this point later, but if you are curious

now, the latter kind of functions always has as return type

\code{Unit}.

If you want to write a stand-alone app in Scala, you can

implement an object that is an instance of \code{App}, say

\begin{lstlisting}[language=Scala,numbers=none]

object Hello extends App {

    println ("hello world")

}

\end{lstlisting}

\noindent save it in a file, say {\tt hello-world.scala}, and

then run the compiler and runtime environment:

\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]

$ scalac hello-world.scala

$ scala Hello

hello world

\end{lstlisting}

As mentioned above, Scala targets the JVM and consequently

Scala programs can also be executed by the bog-standard Java

Runtime. This only requires the inclusion of {\tt

scala-library.jar}, which on my computer can be done as

follows:

\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]

$ scalac hello-world.scala

$ java -cp /usr/local/src/scala/lib/scala-library.jar:. Hello

hello world

\end{lstlisting}

\noindent You might need to adapt the path to where you have

installed Scala.

\subsection*{Inductive Datatypes}

The elegance and conciseness of Scala programs are often a

result of inductive datatypes that can be easily defined in

Scala. For example in ``every-day mathematics'' we define

regular expressions simply by giving the grammar

\begin{center}

\begin{tabular}{r@{\hspace{2mm}}r@{\hspace{2mm}}l@{\hspace{13mm}}l}

  $r$ & $::=$ &   $\varnothing$         & null\\

        & $\mid$ & $\epsilon$           & empty string\\

        & $\mid$ & $c$                  & single character\\

        & $\mid$ & $r_1 \cdot r_2$      & sequence\\

        & $\mid$ & $r_1 + r_2$          & alternative / choice\\

        & $\mid$ & $r^*$                & star (zero or more)\\

  \end{tabular}

\end{center}

\noindent This grammar specifies what regular expressions are

(essentially a kind of tree-structure with three kinds of

inner nodes---sequence, alternative and star---and three kinds

of leave nodes---null, empty and character). If you are

familiar with Java, it might be an instructive exercise to

define this kind of inductive datatypes in Java\footnote{Happy

programming! \Smiley} and then compare it with how it can be

defined in Scala.

Implementing the regular expressions from above in Scala is

actually very simple: It first requires an \emph{abstract

class}, say, \code{Rexp}. This will act as the type for

regular expressions. Second, it requires a case for each

clause in the grammar. The cases for $\varnothing$ and

$\epsilon$ do not have any arguments, while in all 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 Scala code is as

follows:

\begin{lstlisting}[language=Scala,numbers=none]

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}

\noindent In order to be an instance of \code{Rexp}, each case

object and case class needs to extend \code{Rexp}. Given the

grammar above, I hope you can see the underlying pattern. If

you want to play further with such definitions of inductive

datatypes, feel free to define for example binary trees.

Once you make a definition like the one above in Scala, you

can represent the regular expression for $a + b$, for example,

as \code{ALT(CHAR('a'), CHAR('b'))}. Expressions such as

\code{'a'} stand for ASCII characters, though in the output

syntax, as you can see below, the quotes are omitted. In a

later section we will see how we can support the more

mathematical infix notation for regular expression operators

in Scala. If you want to assign this regular expression to a

variable, you can use the keyword \code{val} and type

\begin{lstlisting}[language=Scala,numbers=none]

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

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

\end{lstlisting}

\noindent As you can see, in order to make such assignments,

no constructor is required in the class (as in Java). However,

if there is the need for some non-standard initialisation, you

can of course define such a constructor in Scala too. But we

omit such ``tricks'' here. 

Note that Scala in its response says the variable \code{r} is

of type \lstinline[emph={ALT}]!ALT!, not \code{Rexp}. This

might be a bit unexpected, but can be explained as follows:

Scala always tries to find the most general type that is

needed for a variable or expression, but does not

``over-generalise''. In our definition the type \code{Rexp} is

more general than \lstinline[emph={ALT}]!ALT!, since it is the

abstract class. But in this case there is no need to give

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

different if you want to form a list of regular expressions,

for example

\begin{lstlisting}[language=Scala,numbers=none]

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

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

\end{lstlisting}

\noindent In this case, Scala needs to assign a common type to

the regular expressions so that it is compatible with the

fact that lists can only contain elements of a single type. In

this case the first common type is \code{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.} 

For compound types like \code{List[...]}, the general rule is

that when a type takes another type as argument, then this

argument type is written in angle-brackets. This can also

contain nested types as in \code{List[Set[Rexp]]}, which is a

list of sets each of which contains regular expressions.

\subsection*{Functions and Pattern-Matching}

I mentioned above that Scala is a very elegant programming

language for the code we will write in this module. This

elegance mainly stems from the fact that in addition to

inductive datatypes, also functions can be implemented very

easily in Scala. To show you this, lets first consider a

problem from number theory, called the \emph{Collatz-series},

which corresponds to a famous unsolved problem in

mathematics.\footnote{See for example

\url{http://mathworld.wolfram.com/CollatzProblem.html}.}

Mathematician define this series as:

\[

collatz_{n + 1} \dn 

\begin{cases}

\frac{1}{2} * collatz_n & \text{if $collatz_n$ is even}\\

3 * collatz_n + 1 & \text{if $collatz_n$ is odd}

\end{cases}

\]

\noindent The famous unsolved question is whether this

series started with any $n > 0$ as $collaz_0$ will always

return to $1$. This is obvious when started with $1$, and also

with $2$, but already needs a bit of head-scratching for the

case of $3$.

If we want to avoid the head-scratching, we could implement

this as the following function in Scala:

\lstinputlisting[language=Scala,numbers=none]{../progs/collatz.scala}

\noindent The keyword for function definitions is \code{def}

followed by the name of the function. After that you have a

list of arguments (enclosed in parentheses and separated by

commas). Each argument in this list needs its type annotated.

In this case we only have one argument, which is of type 

\code{BigInt}. This type stands in Scala for arbitrary precision

integers (in case you want to try out the function on really

big numbers). After the arguments comes the type of what the

function returns---a Boolean in this case for indicating that

the function has reached 1. Finally, after the \code{=}

comes the \emph{body} of the function implementing what the

function is supposed to do. What the \code{collatz} function

does should be pretty self-explanatory: the function first

tests whether \code{n} is equal to 1 in which case it returns

\code{true} and so on.

Notice a quirk in Scala's syntax for \code{if}s: The condition

needs to be enclosed in parentheses and the then-case comes

right after the condition---there is no \code{then} keyword in

Scala.

The real power of Scala comes, however, from the ability to

define functions by \emph{pattern matching}. In the

\code{collatz} function above we need to test each case using a

sequence of \code{if}s. This can be very cumbersome and brittle

if there are many cases. If we wanted to define a function

over regular expressions in Java, for example, which does not

have pattern-matching, the resulting code would be just

awkward.

Mathematicians already use the power of pattern-matching when

they define the function that takes a regular expression and

produces another regular expression that can recognise the

reversed strings. The resulting recursive function is often

defined as follows:

\begin{center}

\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}

$rev(\varnothing)$   & $\dn$ & $\varnothing$\\

$rev(\epsilon)$      & $\dn$ & $\epsilon$\\

$rev(c)$             & $\dn$ & $c$\\

$rev(r_1 + r_2)$     & $\dn$ & $rev(r_1) + rev(r_2)$\\

$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\

$rev(r^*)$                   & $\dn$ & $rev(r)^*$\\

\end{tabular}

\end{center}

\noindent This function is defined by recursion analysing each

pattern of what the regular expression could look like. The

corresponding Scala code looks very similar to this

definition, thanks to pattern-matching.

\lstinputlisting[language=Scala]{../progs/rev.scala}

\noindent The keyword for starting a pattern-match is

\code{match} followed by a list of \code{case}s. Before the match

keyword can be another pattern, but often as in the case

above, it is just a variable you want to pattern-match

(the \code{r} after \code{=} in Line 1).

Each case in this definition follows the structure of how we

defined regular expressions as inductive datatype. For example

the case in Line 3 you can read as: if the regular expression

\code{r} is of the form \code{EMPTY} then do whatever follows

the \code{=>} (in this case just return \code{EMPTY}). Line 5

reads as: if the regular expression \code{r} is of the form

\code{ALT(r1, r2)}, where the left-branch of the alternative is

matched by the variable \code{r1} and the right-branch by

\code{r2} then do ``something''. The ``something'' can now use the

variables \code{r1} and \code{r2} from the match. 

If you want to play with this function, call it for example

with the regular expression $ab + ac$. This regular expression

can recognise the strings $ab$ and $ac$. The function 

\code{rev} produces $ba + ca$, which can recognise the reversed

strings $ba$ and $ca$.

In Scala each pattern-match can also be guarded as in

\begin{lstlisting}[language=Scala, numbers=none]

case Pattern if Condition => Do_Something

\end{lstlisting}

\noindent This allows us, for example, to re-write the 

\code{collatz}-function from above as follows:

\lstinputlisting[language=Scala]{../progs/collatz2.scala}

\noindent Although in this particular case the pattern-match

does not improve the code in any way. In cases like \code{rev}

it is really crucial. The underscore in Line 4 indicates that

we do not care what the patter8n looks like. Thus this case

acts like a default case whenever the cases above did not

match. Cases are always tried out from top to bottom.

\subsection*{Loops, or the Absence of}

Coming from Java or C, you might be surprised that Scala does

not really have loops. It has instead, what is in functional

programming called \emph{maps}. To illustrate how they work,

lets assume you have a list of numbers from 1 to 8 and want to

build the list of squares. The list of numbers from 1 to 8 

can be constructed in Scala as follows:

\begin{lstlisting}[language=Scala,numbers=none]

scala> (1 to 8).toList

res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)

\end{lstlisting}

\noindent Generating from this list the list of squares in a

programming language such as Java, you would assume the list

is given as a kind of array. You would then iterate, or loop,

an index over this array and replace each entry in the array

by the square. Right? In Scala, and in other functional

programming languages, you use maps to achieve the same. 

A map essentially takes a function that describes how each

element is transformed (for example squared) and a list over

which this function should work. There are two forms to

express such maps in Scala. The first way is called a

\emph{for-comprehension}. Squaring the numbers from 1 to 8

would look in this form as follows:

\begin{lstlisting}[language=Scala,numbers=none]

scala> for (n <- (1 to 8).toList) yield n * n

res2: List[Int] = List(1, 4, 9, 16, 25, 36, 49, 64)

\end{lstlisting}

\noindent The important keywords are \code{for} and

\code{yield}. This for-comprehension roughly states that from

the list of numbers we draw \code{n}s and compute the result

of \code{n * n}. As you can see, we specified the list where

each \code{n} comes from, namely \code{(1 to 8).toList}, and

how each element needs to be transformed. This can also be

expressed in a second way in Scala by using directly

\code{map}s as follows:

\begin{lstlisting}[language=Scala,numbers=none]

scala> (1 to 8).toList.map(n => n * n)

res3 = List(1, 4, 9, 16, 25, 36, 49, 64)

\end{lstlisting}

\noindent In this way, the expression \code{n => n * n} stands

for the function that calculates the square (this is how the

\code{n}s are transformed). This expression for functions

might remind you of your lessons about the lambda-calculus

where this would have been written as $\lambda n.\,n * n$. It

might not be obvious, but for-comprehensions are just

syntactic sugar: when compiling, Scala translates

for-comprehensions into equivalent maps. This even works

when for-comprehensions get more complicated (see below).

The very charming feature of Scala is that such maps or

for-comprehensions can be written for any kind of data

collection, such as lists, sets, vectors, options and so on.

For example if we instead compute the reminders modulo 3 of

this list, we can write

\begin{lstlisting}[language=Scala,numbers=none]

scala> (1 to 8).toList.map(n => n % 3)

res4 = List(1, 2, 0, 1, 2, 0, 1, 2)

\end{lstlisting}

\noindent If we, however, transform the numbers 1 to 8 not

into a list, but into a set, and then compute the reminders

modulo 3 we obtain

\begin{lstlisting}[language=Scala,numbers=none]

scala> (1 to 8).toSet[Int].map(n => n % 3)

res5 = Set(2, 1, 0)

\end{lstlisting}

\noindent This is the correct result for sets, as there are

only three equivalence classes of integers modulo 3. Note that

in this example we need to ``help'' Scala to transform the

numbers into a set of integers by explicitly annotating the

type \code{Int}. Since maps and for-comprehensions are

just syntactic variants of each other, the latter can also be

written as

\begin{lstlisting}[language=Scala,numbers=none]

scala> for (n <- (1 to 8).toSet[Int]) yield n % 3

res5 = Set(2, 1, 0)

\end{lstlisting}

For-comprehensions can also be nested and the selection of 

elements can be guarded. For example if we want to pair up

the numbers 1 to 4 with the letters a to c, we can write

\begin{lstlisting}[language=Scala,numbers=none]

scala> for (n <- (1 to 4).toList; 

            l <- ('a' to 'c').toList) yield (n, l)

res6 = List((1,a), (1,b), (1,c), (2,a), (2,b), (2,c), 

            (3,a), (3,b), (3,c), (4,a), (4,b), (4,c))

\end{lstlisting}

\noindent 

Or if we want to find all pairs of numbers between 1 and 3

where the sum is an even number, we can write

\begin{lstlisting}[language=Scala,numbers=none]

scala> for (n <- (1 to 3).toList; 

            m <- (1 to 3).toList;

            if (n + m) % 2 == 0) yield (n, m)

res7 = List((1,1), (1,3), (2,2), (3,1), (3,3))

\end{lstlisting}

\noindent The \code{if}-condition in the for-comprehension

filters out all pairs where the sum is not even.

While hopefully this all looks reasonable, there is one

complication: In the examples above we always wanted to

transform one list into another list (e.g.~list of squares),

or one set into another set (set of numbers into set of

reminders modulo 3). What happens if we just want to print out

a list of integers? Then actually the for-comprehension