diff -r 5ab45f3fee1c -r f211d9cb856e handouts/pep-ho.tex --- a/handouts/pep-ho.tex Sat Jun 16 20:55:51 2018 +0100 +++ b/handouts/pep-ho.tex Fri Jun 22 13:34:05 2018 +0100 @@ -32,7 +32,7 @@ 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: +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, LinkedIn, @@ -75,17 +75,17 @@ \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 keys -the \keys{Ctrl} \keys{Ret} to the action +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 your own editor for coding, it -is also painless to work with Scala completely on the command line (like you -might have done with \texttt{g++} in the earlier part of PEP). For 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 @@ -104,24 +104,30 @@ \end{quote} \noindent -Also IntelliJ includes plugins for Scala. \textbf{BUT}, I do not +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. ;o) +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 +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 deeply 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. +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 grades +in PEP, but functional programming could equally be taught with Haskell, +F\#, SML, Ocaml, Kotlin, 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 @@ -130,13 +136,13 @@ \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, -adding one to a variable and so on). The classic example for this style -of programming is a \texttt{for}-loop, say +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... + //...Do something interesting with i... } \end{lstlisting} @@ -144,11 +150,17 @@ 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 which contains its -current value\ldots\texttt{10} at the beginning, and then the content -will be updated, or replaced, by some new content in every iteration. -The main point here is that this kind of updating, or manipulating, -memory is \textbf{PURE EVIL}!! +dedicated space reserved for \texttt{i} in memory. This space of +typically 32 bits contains its 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 @@ -165,13 +177,13 @@ 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 core you have available (typically 4 in modern +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 write (update) -the variable \texttt{i}.\footnote{If you are of the belief that nothing +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 @@ -186,19 +198,19 @@ 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'' (computational -intensive) parts. 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. -Try the same in C++ or Java! +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} @@ -212,15 +224,26 @@ \bigskip -\begin{tabular}[t]{p{5cm}|p{5cm}} +\begin{tabular}{@{}p{6cm}|p{6cm}@{}} \includegraphics[scale=0.15]{../pics/mand4.png} & \includegraphics[scale=0.15]{../pics/mand3.png} \\ -\begin{minipage}{0.5\textwidth}\small -a -\begin{lstlisting}[numbers=none] -ww -\end{lstlisting} -\end{minipage} +\footnotesize +{\begin{lstlisting} +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}} & \\ \end{tabular} \end{center} @@ -229,15 +252,27 @@ \end{figure} But remember that this easy parallelisation of code requires that we -have no state in our program\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 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 good luck with Scala! - +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 good luck 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 always 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}