\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usepackage{marvosym}

\usepackage{boxedminipage}

%cheat sheet

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

% case class, apply, unapply

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

\begin{document}

\fnote{\copyright{} Christian Urban, King's College London, 2017, 2018}

\section*{A Crash-Course in Scala}

\mbox{}\hfill\textit{``Scala --- \underline{S}lowly \underline{c}ompiled 

\underline{a}cademic \underline{la}nguage''}\smallskip\\

\noindent

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 of

Scala for producing code under Android (\url{http://scala-android.org});

for generating JavaScript code to build browser applications

\url{(https://www.scala-js.org)}; and there is work under way to

have a native Scala compiler generating X86-code

(\url{http://www.scala-native.org}).} Because of this it has also access to

the myriads of Java libraries. Unlike Java, however, Scala often allows

programmers to write very concise and elegant code.  Some therefore say

``Scala is the better Java''.\footnote{from

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

A number of companies---the Guardian, Twitter, Coursera, FourSquare, Netflix,

LinkedIn to name a few---either use Scala exclusively in

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

also useful in job-interviews (especially in data science) according to

this anecdotal report

\begin{quote}

\url{http://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

I found a convenient IDE for writing Scala programs is Microsoft's

\textit{Visual Studio Code} (VS Code) which runs under MacOSX, Linux and

obviously Windows. It can be downloaded for free from

\begin{quote}

\url{https://code.visualstudio.com}

\end{quote}

\noindent

and should already come pre-installed in the Department (together with

the Scala compiler). VS Code is far from perfect, however it includes a

\textit{Marketplace} from which a multitude of extensions can be

downloaded that make editing and running Scala code a little easier (see

Figure~\ref{vscode} for my setup).

\begin{figure}[t]

\begin{boxedminipage}{\textwidth}  

\begin{center}  

\includegraphics[scale=0.15]{../pics/vscode.png}\\[-10mm]\mbox{}

\end{center}

\caption{My personal installation of VS Code includes the following

packages from Marketplace: Scala Syntax (official), Code Runner, Code

Spell Checker, Rewrap and Subtle Match Brackets. I have also bound 

the keys \keys{Ctrl} \keys{Ret} to the action

``Run-Selected-Text-In-Active-Terminal'' in order to quickly evaluate

small code snippets in the Scala REPL.\label{vscode}}

\end{boxedminipage}

\end{figure}  

What I like most about VS Code is that it provides easy access to the

Scala REPL. But if you prefer another editor for coding, it is also

painless to work with Scala completely on the command line (as you might

have done with \texttt{g++} in the earlier part of PEP). For the

lazybones among us, there is even an online editor and environment for

developing and running Scala programs called \textit{ScalaFiddle}, which

requires zero setup (assuming you have a browser handy). You can access

it from: 

\begin{quote}

\url{https://scalafiddle.io}\medskip

\end{quote}

Scala can be used with the heavy-duty IDEs Eclipse and IntelliJ.

A ready-made Scala bundle for Eclipse is available from

\begin{quote}

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

\end{quote}

\noindent

Also IntelliJ includes plugins for Scala. \textbf{BUT}, I do \textbf{not}

recommend the usage of either Eclipse or IntelliJ for PEP: these IDEs

seem to make your life harder, rather than easier, for the small

programs we will write in this module. They are really meant to be used

when you have a million-lines codebase, rather than our

``toy-programs''\ldots{}for example why on earth am I required to create a

completely new project with several subdirectories when I just want to

try out 20-lines of Scala code? Your mileage may vary though. ;o)

\subsection*{Why Functional Programming?}

Before we go on, let me explain a bit more why we want to inflict upon

you another programming language. You hopefully have mastered Java and

C++\ldots{}the world should be your oyster, no? Well, it is not that

easy. We do require Scala in PEP, but actually we do not religiously

care whether you learn Scala---after all it is just a programming

language (albeit a nifty one IMHO). What we do care about is that you

learn about \textit{functional programming}. Scala is just the vehicle

for that. Still, you need to learn Scala well enough to get good marks

in PEP, but functional programming could equally be taught with Haskell,

F\#, SML, Ocaml, Kotlin, Clojure, Scheme, Elm and many other functional

programming languages. %Your friendly lecturer just happens to like Scala

%and the Department agreed that it is a good idea to inflict Scala upon

%you.

Very likely writing programs in a functional programming language is

quite different from what you are  used to in your study so far. It

might even be totally alien to you. The reason is that functional

programming seems to go against the core principles of

\textit{imperative programming} (which is what you do in Java and C++

for example). The main idea of imperative programming  is that you have

some form of ``state'' in your program and you continuously change this

state by issuing some commands (e.g.~updating a field in an array or

object, adding one to a variable and so on). The classic example for

this style of programming are \texttt{for}-loops, for example

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

for (int i = 10; i < 20; i++) { 

      //...Do something interesting with i...

}

\end{lstlisting}

\noindent Here the integer variable \texttt{i} embodies the state, which

is first set to \texttt{10} and then increased by one in each

loop-iteration until it reaches \texttt{20} at which point the loop

exits. When this code is compiled and actually runs, there will be some

dedicated space reserved for \texttt{i} in memory. This space of

typically 32 bits contains \texttt{i}'s current value\ldots\texttt{10}

at the beginning, and then the content will be updated by, or

overwritten with, some new content in every iteration. The main point

here is that this kind of updating, or manipulating, memory is

25.806\ldots or \textbf{THE ROOT OF ALL EVIL}!!

\begin{center}

\includegraphics[scale=0.25]{../pics/root-of-all-evil.png}

\end{center}  

\noindent

\ldots{}Well, it is perfectly benign if you have a sequential program

that gets run instruction by instruction...nicely one after another.

This kind of running code uses a single core of your CPU and goes as

fast as your CPU frequency, also called clock-speed, allows. The problem

is that this clock-speed has not much increased over the past decade and

no dramatic increases are predicted for any time soon. So you are a bit

stuck, unlike previous generations of developers who could rely upon the

fact that every 2 years or so their code would run twice as fast (in

ideal circumstances) because the clock-speed of their CPUs got twice as

fast. This unfortunately does not happen any more nowadays. To get you

out of this dreadful situation, CPU producers pile more and more

cores into CPUs in order to make them more powerful and potentially make

software faster. The task for you as developer is to take somehow

advantage of these cores by running as much of your code as possible in

parallel on as many cores you have available (typically 4 in modern

laptops and sometimes much more on high-end machines). In this

situation, \textit{mutable} variables like \texttt{i} above are evil, or

at least a major nuisance: Because if you want to distribute some of the

loop-iterations over the cores that are currently idle in your system,

you need to be extremely careful about who can read and overwrite

the variable \texttt{i}.\footnote{If you are of the mistaken belief that nothing

nasty can happen to \texttt{i} inside the \texttt{for}-loop, then you

need to go back over the C++ material.} Especially the writing operation

is critical because you do not want that conflicting writes mess about

with \texttt{i}. Take my word: an untold amount of misery has arisen

from this problem. The catch is that if you try to solve this problem in

C++ or Java, and be as defensive as possible about reads and writes to

\texttt{i}, then you need to synchronise access to it. The result is that

your program more often than not waits more than it runs, thereby

defeating the point of trying to run the program in parallel in the

first place. If you are less defensive, then usually all hell breaks

loose by seemingly obtaining random results. And forget the idea of

being able to debug such code.

The central idea of functional programming is to eliminate any state

from programs---or at least from the ``interesting bits''. Because then

it is easy to parallelize the resulting programs: if you do not have any

state, then once created, all memory content stays unchanged and reads

to such memory are absolutely safe without the need of any

synchronisation. An example is given in Figure~\ref{mand} where in the

absence of the annoying state, Scala makes it very easy to calculate the

Mandelbrot set on as many cores of your CPU as possible. Why is it so

easy in this example? Because each pixel in the Mandelbrot set can be

calculated independently and the calculation does not need to update any

variable. It is so easy in fact that going from the sequential version

of the Mandelbrot program to the parallel version can be achieved by

adding just eight characters---in two places you have to add

\texttt{.par}. Try the same in C++ or Java!

\begin{figure}[p]

\begin{boxedminipage}{\textwidth}

A Scala program for generating pretty pictures of the Mandelbrot set 

(\url{https://en.wikipedia.org/wiki/Mandelbrot_set},

\url{https://www.youtube.com/watch?v=aSg2Db3jF_4}):

\begin{center}    

\begin{tabular}{c}  

\includegraphics[scale=0.12]{../pics/mand1.png}

\end{tabular}

\end{center}

\begin{center}

\begin{tabular}{@{}p{0.45\textwidth}|p{0.45\textwidth}@{}}

  \bf sequential version: & \bf parallel version (on 4 cores):\smallskip\\

  {\hfill\includegraphics[scale=0.12]{../pics/mand4.png}\hfill} &

  {\hfill\includegraphics[scale=0.12]{../pics/mand3.png}\hfill} \\

{\footnotesize\begin{lstlisting}[xleftmargin=-1mm]

for (y <- (0 until H)) {

  for (x <- (0 until W)) {

    val c = start + 

      (x * d_x + y * d_y * i)

    val iters = iterations(c, max) 

    val col = 

      if (iters == max) black 

      else colours(iters % 16)

    pixel(x, y, col)

  }

  viewer.updateUI()

}   

\end{lstlisting}}   

& 

{\footnotesize\begin{lstlisting}[xleftmargin=0mm]

for (y <- (0 until H)/*@\keys{\texttt{.par}}@*/) {

  for (x <- (0 until W)/*@\keys{\texttt{.par}}@*/) {

    val c = start + 

      (x * d_x + y * d_y * i)

    val iters = iterations(c, max) 

    val col = 

      if (iters == max) black 

      else colours(iters % 16)

    pixel(x, y, col)

  }

  viewer.updateUI()

}   

\end{lstlisting}}\\

\centering\includegraphics[scale=0.5]{../pics/cpu2.png} &

\centering\includegraphics[scale=0.5]{../pics/cpu1.png}

\end{tabular}

\end{center}

\caption{The main ``loops'' creating the picture of the Mandelbrot set. The parallel version

only differs in \texttt{.par} added to the ``ranges'' of the x-y-coordinates. As can be

seen from the CPU loads: in the sequential versions there is a lower peak for an

extended period, while in the parallel version there is a short sharp burst for 

essentially the same workload.

\label{mand}} 

\end{boxedminipage}

\end{figure}  

But remember this easy parallelisation of code requires that we

have no state in our programs\ldots{}that is no counters like

\texttt{i} in \texttt{for}-loops. You might then ask, how do I write

loops without such counters? Well, teaching you that this is possible is

one of the main points of the Scala-part in PEP. I can assure you it is

possible, but you have to get your head around it. Once you have

mastered this, it will be fun to have no state in your programs (a side

product is that it much easier to debug state-less code and also more

often than not easier to understand). So have fun with

Scala!\footnote{If you are still not convinced about the function

programming ``thing'', there are a few more arguments: a lot of research

in programming languages happens to take place in functional programming

languages. This has resulted in ultra-useful features such as

pattern-matching, strong type-systems, lazyness, implicits, algebraic

datatypes  to name a few. Imperative languages seem to often lag behind

in adopting them: I know, for example, that Java will at some point in

the future support pattern-matching, which has been used in SML for at

least 40(!) years. See

\url{http://cr.openjdk.java.net/~briangoetz/amber/pattern-match.html}.

Also Rust, a C-like programming language that has been developed since

2010 and is gaining quite some interest, borrows many ideas from

functional programming from yesteryear.}

\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. It is my 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.6 (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 The answer means that he 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, for example

\begin{lstlisting}[numbers=none]

scala> res0 + 4

res1: Int = 9

\end{lstlisting}

\noindent

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 by Scala. 

You can try more examples with the Scala REPL, but feel free to

first 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

scala> List(1,2,1).size

scala> Set(1,2,1).size

\end{lstlisting}\smallskip

\noindent

Please take the Scala REPL seriously: If you want to take advantage of my

reference implementation for the assignments, you will need to be

able to ``play around'' with it!

\subsection*{Standalone 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 (\texttt{scalac}) and start the runtime

environment (\texttt{scala}):

\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; they cannot vary. 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. Upper-case

names you should reserve for what is called \emph{constructors}.

\subsection*{Function Definitions}

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

As an example, a function named \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 habit 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