% !TEX program = xelatex

\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

% the art of programming

% https://www.youtube.com/watch?v=QdVFvsCWXrA

% functional programming in Scala

%https://www.amazon.com/gp/product/1449311032/ref=as_li_ss_tl?ie=UTF8&tag=aleottshompag-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=1449311032

% functional programming in C

%https://www.amazon.com/gp/product/0201419505/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0201419505&linkCode=as2&tag=aleottshompag-20

%speeding through haskell

%https://openlibra.com/en/book/download/speeding-through-haskell

% fp books --- ocaml

% http://courses.cms.caltech.edu/cs134/cs134b/book.pdf

% http://alexott.net/en/fp/books/

%John Hughes’ simple words:

%A combinator is a function which builds program fragments

%from program fragments.

%explain graph coloring program (examples from)

%https://www.metalevel.at/prolog/optimization

% nice example for map and reduce using Harry potter characters

% https://www.matthewgerstman.com/map-filter-reduce/

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

\mbox{}\hfill\textit{ --- a joke(?) found on Twitter}\bigskip

\subsection*{Introduction}

\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. 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, ITV 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}\medskip

\end{quote}

\noindent

If you are interested, there are also experimental backends of Scala

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

generating JavaScript code (\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}). Though be warned these backends

are still rather beta or even alpha.

\subsection*{VS Code and Scala}

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.\footnote{unlike \emph{Microsoft Visual Studio}---note

the minuscule difference in the name---which is a heavy-duty,

Windows-only IDE\ldots{}jeez, with all their money could they not come

up with a completely different name for a complete different project?

For the pedantic, Microsoft Visual Studio is an IDE, whereas Visual

Studio Code is considered as a source code editor. Anybody knows the what the

difference is?} 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). Being a project that just started in 2015, VS Code is

relatively new and thus 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 installation of VS Code includes the following

  packages from Marketplace: \textbf{Scala Syntax (official)} 0.2.0,

  \textbf{Code Runner} 0.9.5, \textbf{Code Spell Checker} 1.6.10,

  \textbf{Rewrap} 1.9.1 and \textbf{Subtle Match

  Brackets} 3.0.0. 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 are even online editors and environments for

developing and running Scala programs: \textit{ScalaFiddle}

and \textit{Scastie} are two of them. They require zero setup 

(assuming you have a browser handy). You can access them at 

\begin{quote}

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

  \url{https://scastie.scala-lang.org}\medskip

\end{quote}

\noindent

But you should be careful if you use them for your coursework: they

are meant to play around, not really for serious work. 

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. \underline{\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'' we will write in PEP\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 \emph{state} in your program and you continuously change this

state by issuing some commands---for example for updating a field in an

array or for adding one to a variable and so on. The classic

example for this style of programming are \texttt{for}-loops in C:

\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 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'' of the

programs. Because then it is easy to parallelise 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.\smallskip\\ 

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

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

\begin{center}    

\begin{tabular}{c}  

\includegraphics[scale=0.11]{../pics/mand1.png}\\[-8mm]\mbox{}

\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.11]{../pics/mand4.png}\hfill} &

  {\hfill\includegraphics[scale=0.11]{../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 colour = 

      if (iters == max) black 

      else colours(iters % 16)

    pixel(x, y, colour)

  }

  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 colour = 

      if (iters == max) black 

      else colours(iters % 16)

    pixel(x, y, colour)

  }

  viewer.updateUI()

}   

\end{lstlisting}}\\[-2mm]

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

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

\end{tabular}

\end{center}

\caption{The code of the ``main'' loops in my Mandelbrot program.

The parallel version differs only in \texttt{.par} being added to the

``ranges'' of the x and y coordinates. As can be seen from the CPU loads, in

the sequential version 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\ldots{}meaning you get more work done 

in a shorter amount of time. This easy \emph{parallelisation} 

only works reliably with an immutable program.

\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, laziness, 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 for example 

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.7 (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

scala> List(1) == List(1)

scala> Array(1) == Array(1)

scala> Array(1).sameElements(Array(1))

\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}. For example

write

\begin{lstlisting}[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 (\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]