\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usepackage{marvosym}

%cheat sheet

%http://worldline.github.io/scala-cheatsheet/

% case class, apply, unappy

% see https://medium.com/@thejasbabu/scala-pattern-matching-9c9e73ba9a8a

\begin{document}

\section*{A Crash-Course in Scala}

Scala is a programming language that combines functional and

object-oriented programming-styles. It has received quite a bit of

attention in the last five or so years. 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; and also work is under way to

  have a native compiler, see

  \url{https://github.com/scala-native/scala-native}.} Unlike Java,

however, Scala often allows programmers to write very concise and

elegant code.  Some therefore say: ``Scala is the better

Java''.\footnote{\url{https://www.slideshare.net/maximnovak/joy-of-scala}}

Also a number of companies (the Guardian, Twitter, Coursera,

FourSquare, LinkedIn to name a few) either use Scala exclusively in

production code, or at least to some substantial degree. Scala seems

also to be useful in job-interviews (in Data Science) according to

this anecdotal report

\begin{quote}\small

\url{https://techcrunch.com/2016/06/14/scala-is-the-new-golden-child/}

\end{quote}

\noindent

The official Scala compiler can be downloaded from

\begin{quote}

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

\end{quote}

\noindent

A ready-made bundle with the Eclipse IDE is at

\begin{quote}

\url{http://scala-ide.org/download/sdk.html}

\end{quote}

\noindent

When developing Scala programs, I personally prefer to use Emacs

or Sublime as my environment, since they provide an easy access

to the Scala REPL (see below).  But it is also possible to work

completely on the command line and also with heavy-duty IDEs

like Eclipse of IntelliJ. There is even an online editor and

environment for developing Scala programs called ScalaFiddle

\begin{quote}

\url{https://scalafiddle.io}

\end{quote}

\subsection*{The Very Basics}

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 a compiler. This helps a lot with interactively developing

programs. This is really the preferred way of writing small Scala

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 2.12.4 (Java HotSpot(TM) 64-Bit Server VM, Java 9).

Type in expressions for evaluation. Or try :help.

scala>

\end{lstlisting}%$

\noindent The precise response may vary depending

on the version and 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}[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; \code{res0} is a name that

Scala gives automatically to the result. You can reuse this name later

on. Another classic example you can try out is

\begin{lstlisting}[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{resX} 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 \code{Unit} as

return type. It is just not printed.

You can try more examples with the Scala interpreter, but try

first to guess what the result is (not all answers by Scala are obvious):

\begin{lstlisting}[numbers=none]

scala> 2 + 2

scala> 1 / 2

scala> 1.0 / 2

scala> 1 / 2.0

scala> 1 / 0

scala> 1.0 / 0.0

scala> true == false

scala> true && false

scala> 1 > 1.0

scala> "12345".length

\end{lstlisting}

\subsection*{Stand-Alone Scala Apps}

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}[numbers=none]

object Hello extends App {

    println("hello world")

}

\end{lstlisting}

\noindent save it in a file, for example {\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}

\noindent

Like Java, 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*{Values}

In the lectures I will try to avoid as much as possible the term

\emph{variables} familiar from other programming languages. The reason

is that Scala has \emph{values}, which can be seen as abbreviations of

larger expressions. For example

\begin{lstlisting}[numbers=none]

scala> val x = 42

x: Int = 42

scala> val y = 3 + 4

y: Int = 7

scala> val z = x / y

z: Int = 6

\end{lstlisting}

\noindent

Why the kerfuffle about values? Well, values are \emph{immutable}. You cannot

change their value after you defined them. If you try to reassign

\code{z} above, Scala will yell at you:

\begin{lstlisting}[numbers=none]

scala> z = 9

error: reassignment to val

       z = 9

         ^

\end{lstlisting}

\noindent

So it would be a bit absurd to call values as variables...you cannot

change them. You might think you can re-assign them like

\begin{lstlisting}[numbers=none]

scala> val x = 42

scala> val z = x / 7

scala> val x = 70

scala> println(z) 

\end{lstlisting}

\noindent but try to guess what Scala will print out 

for \code{z}?  Will it be \code{6} or \code{10}? A final word about

values: Try to stick to the convention that names of values should be

lower case, like \code{x}, \code{y}, \code{foo41} and so on.

\subsection*{Function Definitions}

We do functional programming. So defining functions will be our main occupation.

A function \code{f} taking a single argument of type \code{Int} can be defined in Scala

as follows:

\begin{lstlisting}[numbers=none]

def f(x: Int) : String = EXPR

\end{lstlisting} 

\noindent

This function returns the value resulting from evaluating the expression

\code{EXPR} (whatever is substituted for this). The result will be

of type \code{String}. It is a good habbit to include this information

about the return type always. Simple examples of Scala functions are:

\begin{lstlisting}[numbers=none]

def incr(x: Int) : Int = x + 1

def double(x: Int) : Int = x + x

def square(x: Int) : Int = x * x

\end{lstlisting}

\noindent

The general scheme for a function is

\begin{lstlisting}[numbers=none]

def fname(arg1: ty1, arg2: ty2,..., argn: tyn): rty = {

  BODY

}

\end{lstlisting}

\noindent

where each argument requires its type and the result type of the

function, \code{rty}, should be given. If the body of the function is

more complex, then it can be enclosed in braces, like above. If it it

is just a simple expression, like \code{x + 1}, you can omit the

braces. Very often functions are recursive (call themselves) like

the venerable factorial function.

\begin{lstlisting}[numbers=none]

def fact(n: Int): Int = 

  if (n == 0) 1 else n * fact(n - 1)

\end{lstlisting}

\subsection*{Loops, or better the Absence thereof}

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,

let us 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}[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 as follows:

\begin{lstlisting}[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}[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}[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}[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}[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}[numbers=none]

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

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

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

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

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

what is in the functional-programming-lingo called a

side-effect. Printing out the list of numbers from 1 to 5

would look as follows

\begin{lstlisting}[numbers=none]

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

12345

\end{lstlisting}

\noindent

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

also do more elaborate calculations such as

\begin{lstlisting}[numbers=none]

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{lstlisting}%$

\noindent In this code I use a variable assignment (\code{val

square_n = ...} ) and also what is called in Scala a

\emph{string interpolation}, written \code{s"..."}. The latter

is for printing out an equation. It allows me to refer to the

integer values \code{n} and \code{square\_n} inside a string.

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

The corresponding map construction for functions with 

side-effects is in Scala called \code{foreach}. So you 

could also write

\begin{lstlisting}[numbers=none]

scala> (1 to 5).toList.foreach(n => print(n))

12345

\end{lstlisting}

\noindent or even just

\begin{lstlisting}[numbers=none]

scala> (1 to 5).toList.foreach(print)

12345

\end{lstlisting}

\noindent Again I hope this reminds you a bit of your

lambda-calculus lessons, where an explanation is given why

both forms produce the same result.

If you want to find out more about maps and functions with

side-effects, you can ponder about the response Scala gives if

you replace \code{foreach} by \code{map} in the expression

above. Scala will still allow \code{map} with side-effect

functions, but then reacts with a slightly interesting result.

\subsection*{Types}

In most functional programming languages, types play an

important role. Scala is such a language. You have already

seen built-in types, like \code{Int}, \code{Boolean},

\code{String} and \code{BigInt}, but also user-defined ones,

like \code{Rexp}. Unfortunately, types can be a thorny

subject, especially in Scala. For example, why do we need to

give the type to \code{toSet[Int]}, but not to \code{toList}?

The reason is the power of Scala, which sometimes means it

cannot infer all necessary typing information. At the

beginning while getting familiar with Scala, I recommend a

``play-it-by-ear-approach'' to types. Fully understanding

type-systems, especially complicated ones like in Scala, can

take a module on their own.\footnote{Still, such a study can

be a rewarding training: If you are in the business of

designing new programming languages, you will not be able to

turn a blind eye to types. They essentially help programmers

to avoid common programming errors and help with maintaining

code.}

In Scala, types are needed whenever you define an inductive

datatype and also whenever you define functions (their

arguments and their results need a type). Base types are types

that do not take any (type)arguments, for example \code{Int}

and \code{String}. Compound types take one or more arguments,

which as seen earlier need to be given in angle-brackets, for

example \code{List[Int]} or \code{Set[List[String]]} or 

\code{Map[Int, Int]}.

There are a few special type-constructors that fall outside

this pattern. One is for tuples, where the type is written

with parentheses. For example 

\begin{lstlisting}[ numbers=none]

(Int, Int, String)

\end{lstlisting}

\noindent is for a triple (a tuple with three components---two

integers and a string). Tuples are helpful if you want to

define functions with multiple results, say the function

returning the quotient and reminder of two numbers. For this

you might define:

\begin{lstlisting}[ numbers=none]

def quo_rem(m: Int, n: Int) : (Int, Int) = (m / n, m % n)

\end{lstlisting}

\noindent Since this function returns a pair of integers, its

return type needs to be of type \code{(Int, Int)}.

Incidentally, this is also the input type of this function.

Notice this function takes \emph{two} arguments, namely

\code{m} and \code{n}, both of which are integers. They are

``packaged'' in a pair. Consequently the complete type of

\code{quo_rem} is

\begin{lstlisting}[ numbers=none]

(Int, Int) => (Int, Int)

\end{lstlisting}

Another special type-constructor is for functions, written as

the arrow \code{=>}. For example, the type \code{Int =>

String} is for a function that takes an integer as input

argument and produces a string as result. A function of this

type is for instance

\begin{lstlisting}[numbers=none]

def mk_string(n: Int) : String = n match {

  case 0 => "zero"

  case 1 => "one"