% !TEX program = xelatex

\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usepackage{tikz}

\usepackage{pgf}

\usepackage{marvosym}

\usepackage{boxedminipage}

\lstset{escapeinside={/*!}{!*/}}

\newcommand{\annotation}[1]{\hfill\footnotesize{}#1}

\usepackage{menukeys}

%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 colouring 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/

% interesting talk about differences in Java and Scala

% Goto'19 conference ; about differences in type-system

% https://www.youtube.com/watch?v=e6n-Ci8V2CM

% Timing

%

% xs.map(x => (x, xs.count(_==x)))

%

% vs  xs.groupBy(identity)

%

% first is quadratic, while second is linear.

% contrast map with a for loop in imperative languages

%

% Let’s use a simple example of calculating sales tax on an array of

% prices.

%

%       const prices = [19.99, 4.95, 25, 3.50];

%       let new_prices = [];

%

%       for(let i=0; i < prices.length; i++) {

%          new_prices.push(prices[i] * 1.06);

%       }

%

% We can achieve the same results using .map():

%

% const prices = [19.99, 4.95, 25, 3.50]; 

% let new_prices = prices.map(price => price * 1.06);

%

% The syntax above is condensed so let’s walk through it a bit. The

% .map() method takes a callback, which can be thought of as a function.

% That’s what is between the parentheses. The variable price is the name

% that will be used to identify each value. Since there’s only one

% input, we can omit the usual parentheses around the parameters.

% potentially a worked example? Tetris in scala.js

%  

% https://medium.com/@michael.karen/learning-modern-javascript-with-tetris-92d532bcd057

%

% Scala videos

%    https://www.youtube.com/user/DrMarkCLewis

%% https://alvinalexander.com/downloads/HelloScala-FreePreview.pdf

%% 

%% Section 10 about strings; interpolations and multiline strings

% Easy installation

%https://alexarchambault.github.io/posts/2020-09-21-cs-setup.html

% Exact colors from NB

\usepackage[breakable]{tcolorbox}

\definecolor{incolor}{HTML}{303F9F}

\definecolor{outcolor}{HTML}{D84315}

\definecolor{cellborder}{HTML}{CFCFCF}

\definecolor{cellbackground}{HTML}{F7F7F7}

\begin{document}

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

%\begin{tcolorbox}[breakable,size=fbox,boxrule=1pt,pad at break*=1mm,colback=cellbackground,colframe=cellborder]

%  abd

%\end{tcolorbox}

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

Just make sure you are downloading the ``battle tested'' version of

Scala \textbf{2.13} This is the one I am going to use in the lectures and

in the coursework. The newer Scala 3.0 \& 3.1 still have some

features not fully implemented.\bigskip

\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{\ldots{}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 have 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 to be a \emph{source code editor}. Anybody knows 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

  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. I use the internal

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

As one might expect, 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 that we will write in this module. They are really meant to be used

when you have a million-lines codebase than with our small

``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.~\texttt{;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, matters are not as

simple as one might wish. 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 perhaps 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/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 is a \texttt{for}-loop in C/C++.

Consider the snippet:

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

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

      //...do something 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 

new content in every iteration. The main point here is that this kind of

updating, or overwriting, of 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. This is unlike previous generations of developers who could rely

upon the fact that approximately every 2 years their code would run

twice as fast  because the clock-speed of their CPUs got twice as fast.

Unfortunately this 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 or more in modern laptops

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

\textit{mutable} variables like \texttt{i} in the C-code above are evil,

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

the loop-iterations over several 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/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 very often your program

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/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]

    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 version of the 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}.

Automatic garbage collection was included in Java in 1995; the

functional language LISP had this already in 1958. Generics were added

to Java 5 in 2004; the functional language SML had it since 1990.

Higher-order functions were added to C\# in 2007, to Java 8 in

2014; again LISP had them since 1958. 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.}\medskip

\noindent

If you need any after-work distractions, you might have fun reading this

about FP (functional programming):

\begin{quote}

\url{https://medium.com/better-programming/fp-toy-7f52ea0a947e}

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

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