\usepackage[scaled=.9]{helvet}

attention is that, like the Java programming language, Scala

and elegant code. Some therefore say Scala is the much better

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

can be downloaded from

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

also with IntelliJ, 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

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

\noindent The precise response may vary due to the platform

classic example you can try out is

\noindent Note that in this case there is no result: the

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

point in due course, but if you are curious now, the latter

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

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

\begin{quote}

\begin{lstlisting}[language=Scala]

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}

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{alltt}

$ scalac hello-world.scala

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

hello world

\end{alltt}

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

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

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

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

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

\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

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

define for example binary trees.

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

{\tt 'a'} stand for ASCII characters. If you want to assign

this regular expression to a variable, you can use the keyword

{\tt val} and type

\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. But we omit

this here. 

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

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

\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 type 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.} 

For types like {\tt List[...]} the general rule is that when a

type takes another type as argument, then this is written in

angle-brackets. This can also contain nested types as in {\tt

List[Set[Rexp]]}, which is a list of sets each of which

contains regular expressions.

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 functions can be

implemented very easily in Scala. 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:

\begin{quote}

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

\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

BigInt}. This type stands for arbitrary precision integers.

After the arguments comes the type of what the function

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

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

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

is supposed to do. What the {\tt collatz} function does should

be pretty self-explanatory: the function first tests whether

{\tt n} is equal to $1$ in which case it returns {\tt true}

and so on.

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

over regular expressions in say Java, which does not have

pattern-matching, the resulting code would just be awkward.

Mathematicians already use the power of pattern-matching, for

example, 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{1mm}}c@{\hspace{1mm}}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 The corresponding Scala code looks very similar

to this definition, thanks to pattern-matching.

\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

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

it is just a variable you want to pattern-match.

In the {\tt rev}-function above, each case 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 {\tt r} is of the form {\tt EMPTY} then

do whatever follows the {\tt =>} (in this case just return

{\tt EMPTY}). Line 5 reads as: if the regular expression

{\tt r} is of the form {\tt ALT(r1, r2)}, where the

left-branch of the alternative is matched by the variable {\tt

r1} and the right-branch by {\tt r2} then do ``something''.

The ``something'' can now use the variables {\tt r1} and {\tt

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 {\tt rev} produces the result $ba + ca$, which

can recognise the reversed strings $ba$ and $ca$.

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

non-functional language (e.g.~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. 

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

express maps in Scala. The first way is in a {\tt

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 *

n}. In consequence we specified the list where each {\tt n}

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

element needs to be transformed. This can also be expressed

in a second way by using directly {\tt map} as follows:

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

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

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

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

remind you on your lessons about the lambda-calculus where

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

It might not be obvious, but {\tt for}-constructions are just

syntactic sugar: when compiling, Scala translates them into

equivalent maps.

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

only 3 equivalence classes of integers modulo 3. Note that we

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

numbers into a set of integers by explicitly annotating the

type {\tt Int}. Since maps and {\tt for}-construction are just

syntactic variants of each other, the latter can also be

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

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 {\tt for}-construction

needs to be modified. The reason is that {\tt print}, you

guessed it, does not produce any result, but only produces, in

the functional-programming-lingo, a side-effect. Printing out

the list of numbers from 1 to 5 would look as follows

\begin{alltt}

scala> for (n <- (1 to 5).toList) println(n)

1

2

3

4

5

\end{alltt}

\noindent

where you need to omit the keyword {\tt yield}. You can

also do more elaborate calculations such as

\begin{alltt}

scala> for (n <- (1 to 5).toList) \{

  val square_n = n * n

  println(s"$n * $n = $square_n") 

\}

1 * 1 = 1

2 * 2 = 4

3 * 3 = 9

4 * 4 = 16

5 * 5 = 25

\end{alltt}

\noindent

In this code I use a \emph{string interpolation},

written {\tt s"..."} in order to print out an equation.

This string interpolation allows me to refer to the integer 

values {\tt n} and {\tt square\_n} inside a string. This

is very convenient for printing out ``things''. 

The corresponding map construction for functions with 

side-effexts is in Scala called {\tt foreach}. So you 

could also write

\begin{alltt}