% !TEX program = xelatex

\documentclass{article}

\usepackage{../styles/style}

\usepackage{../styles/langs}

\usepackage{tikz}

\usepackage{pgf}

\usepackage{marvosym}

\usepackage{boxedminipage}

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

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

\usepackage{menukeys}

\usepackage{emoji}

%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

% scala libraries

%https://index.scala-lang.org

% Learning functional programming is an opportunity to discover a new

% way to represent programs, to approach problems, and to think about

% languages. While programming with a functional language is still

% fundamentally similar to programming with any other type of language

% (examples of others being imperative or logic), it represents

% programs and algorithms through distinct forms of abstraction and

% gives you a new toolset with which to solve programming

% problems. Additionally, many of the techniques of functional

% programming are beginning to permeate new mainstream languages, so

% taking the time now to develop a thorough understanding of them is

% an investment which will pay great dividends.

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

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

\mbox{}\hfill\textit{``Life is too short for \texttt{malloc}.''}\smallskip\\

\mbox{}\hfill\textit{ --- said Neal Ford at Oscon'13}\;\hr{https://www.youtube.com/watch?v=7aYS9PcAITQ}\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

A number of companies---the Guardian, Dualingo, 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 web-page is here:

\begin{quote}

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

\end{quote}

\noindent\alert

Just make sure you are using the version 3(!) of Scala. This is

the version I am going to use in the lectures and in the coursework. This

can be any version of Scala 3.X where $X=\{1,2,3\}$. Also the minor

number does not matter. Note that this will be the first year I am

using this newer version -- so some hiccups are bound to happen. Apologies

in advance!\bigskip

\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black]

  I will be using the \textbf{\texttt{scala-cli}} REPL for Scala 3, rather

  than the ``plain'' Scala REPL. This is a batteries included version of

  Scala 3 and is easier to use and install. In fact

  \texttt{scala-cli} is designated to replace

  the ``plain'' Scala REPL in future versions of Scala.

  So why not using it now?

  It can be downloaded from:

  \begin{center}

  \url{https://scala-cli.virtuslab.org}  

  \end{center}  

\end{tcolorbox}\medskip  

\noindent

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

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}). There are also some

tricks for Scala programs to run as a native

GraalVM~\hr{https://scala-cli.virtuslab.org/docs/cookbooks/native-images/}

image.  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 therefore 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 / Codium includes the 

  package  \textbf{Scala Syntax (official)} 0.5.7 from Marketplace.

  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 Codium's internal

  terminal to run \texttt{scala-cli} version 1.0.5 which

  uses Scala 3.3.1.\label{vscode}}

\end{boxedminipage}

\end{figure}  

Actually \alert last year I switched to VS Codium as IDE for writing Scala programs. VS Codium is VS Code

minus all the telemetry that is normally sent to Microsoft. Apart from

the telemetry (and Copilot, which you are not supposed to use anyway),

it works pretty much the same way as the original but is driven by a

dedicated community, rather than a big company. You can download VS

Codium from

\begin{quote}

\url{https://vscodium.com}

\end{quote}

What I like most about VS Code/Codium is that it provides easy access

to any 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{Scastie} and

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

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

\begin{quote}

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

  \url{https://scalafiddle.io}\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. Make

sure your \texttt{scala-cli} works on your own machine ASAP!

As one might expect, Scala can be used with the heavy-duty IDEs

Eclipse and IntelliJ. For example IntelliJ includes plugins for

Scala

\begin{quote}

\url{https://scalacenter.github.io/bloop/docs/ides/intellij}

\end{quote}

\noindent

\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 instead of 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++, possibly Python\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++). 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

stored in memory 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 part of the

state of the program, 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-8 or even 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]

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

  for (x <- (0 until W).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 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