\documentclass{article}

\usepackage{hyperref}

\usepackage{amssymb}

\usepackage{alltt}

\usepackage{menukeys}

\usepackage{amsmath}

\usepackage{../langs}

\usepackage{mathpazo}

\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%

\definecolor{codegray}{gray}{0.9}

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

\begin{document}

\section*{A Crash-Course on Scala}

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, Scala

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

\begin{quote}

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

\end{quote}

\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 the functions we will

discuss with very small code-snippets. Since the compiler is

free, you can download them and run every example I give. But

if you prefer, you can also easily translate the code-snippets

Read-Eval-Print-Loop) 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 correctly, you can start the interpreter by typing

\begin{alltt}

$ scala\small

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.\normalsize

scala>

\end{alltt}

\noindent The precise response may vary due to the platform

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

\begin{alltt}

scala> 2 + 3

res0: Int = 5

\end{alltt}

\noindent indicating that the result of the addition is of

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

classic example you can try out is

\begin{alltt}

scala> print ("hello world")

hello world

\end{alltt}

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

(there is no {\tt resXX}), 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

\begin{quote}

object Hello extends App {

    println ("hello world")

}

\end{lstlisting}

\end{quote}

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

then run the compiler and runtime environment:

\begin{alltt}

$ scalac hello-world.scala

$ scala Hello

hello world

\end{alltt}

follows:

\begin{alltt}

$ scalac hello-world.scala

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

hello world

\end{alltt}

\subsection*{Inductive Datatypes}

The elegance and conciseness of Scala programs are often a

result of inductive datatypes that can be easily defined. For

example in ``every-day mathematics'' we would 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

Implementing the regular expressions from above in Scala is

\begin{quote}

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 In order to be an instance of {\tt Rexp}, each case

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

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

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

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

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

\begin{alltt}

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

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

\end{alltt}

\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

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

of type {\tt ALT}, not {\tt 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

\begin{alltt}

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

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

\end{alltt}

\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

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:

\begin{quote}

\end{quote}

\noindent The keyword for function definitions is {\tt 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 {\tt

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

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

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

Scala.

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

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

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

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

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

\begin{center}

$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}

\begin{quote}

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

\end{quote}

\noindent The keyword for starting a pattern-match is {\tt

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

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

\begin{quote}

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

case Pattern if Condition => Do_Something

\end{lstlisting}

\end{quote}

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

collatz}-function from above as follows:

\begin{quote}

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

\end{quote}

\noindent Although in this case the pattern-match does not

improve the code in any way. The underscore in the last case

indicates that we do not care what the pattern looks like. 

Thus Line 4 acts like a default case whenever the cases above 

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

\subsection*{Loops}

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 10 and want to

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

can be constructed in Scala as follows:

\begin{alltt}

scala> (1 to 10).toList

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

\end{alltt}

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

Maps essentially take a function that describes how each

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

which this function should work. There are two forms to

for}-construction. Squaring the numbers from 1 to 10 would

look in this form as follows:

\begin{alltt}

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

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

\end{alltt}

\noindent The keywords are {\tt for} and {\tt yield}. This

{\tt for}-construction roughly says that from the list of

numbers we draw {\tt n}s and compute the result of {\tt n *

comes from, namely {\tt (1 to 10).toList}, and how each

\begin{alltt}

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

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

\end{alltt}

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

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

The very charming feature of Scala is that such maps or {\tt

for}-constructions can be written for any kind of data

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

example if we instead compute the reminders modulo $3$ of this

list, we can write

\begin{alltt}

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

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

\end{alltt}

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

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

modulo $3$ we obtain

\begin{alltt}

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

res5 = Set(2, 1, 0)

\end{alltt}

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

numbers into a set of integers by explicitly annotating the

written as

\begin{alltt}

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

res5 = Set(2, 1, 0)

\end{alltt}

While hopefully this all looks reasonable, there is one