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

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

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

% In 1982, James or Jim Morris wrote:

%

% Functional languages are unnatural to use; but so are knives and

% forks, diplomatic protocols, double-entry bookkeeping, and a host of

% other things modern civilization has found useful.

%

% Real Programming in Functional Languages

% Xerox PARC technical report

% CSL·81·11 July 1,1981

\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 ten 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}, though this might

be outdated as latest versions of Java are catching up somewhat} 

A number of companies---the Guardian, Duolingo, 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

For PEP, 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=\{3,4\}$. Also the minor

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

using this newer version of Scala -- some hiccups can still 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 for 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

out there 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 do with \texttt{g++} in the second part of PEP). For

the lazybones among us, there are even online editors and environments

for developing and running Scala programs: for example \textit{Scastie}

is one of them. It requires zero setup

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

\begin{quote}

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

\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

soon will master C++ as well, you possibly know Python already\ldots{}

the world should be your oyster, no?  Well, as usual 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 say Java and 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---and we conveniently ignore how many cores are on modern

GPUs). In this situation \textit{mutable} variables like \texttt{i} in

the for-loop 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 will have to be extra careful with 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. If you want to watch a 5-minute video of horror stories, feel

free to follow \ldots{}

\hr{https://www.youtube.com/watch?v=LdLUgCJkiHY} (I love the fact, he

says at 4:02 that he does not understand how the JVM really

works\ldots{} I always assumed I am the only idiot who does not

understand how threads work on the JVM. Apparently not. \raisebox{-0.7mm}{\emoji{rofl}})\bigskip

\noindent

The central idea of functional programming is to eliminate any state

and mutable variables 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 two ``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