# HG changeset patch # User Christian Urban # Date 1529670845 -3600 # Node ID f211d9cb856e5fcc555e2c561c8caf768eab9a01 # Parent 5ab45f3fee1c2b94c217ea9b04727e159f78cdf7 updated diff -r 5ab45f3fee1c -r f211d9cb856e handouts/pep-ho.pdf Binary file handouts/pep-ho.pdf has changed 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} diff -r 5ab45f3fee1c -r f211d9cb856e pics/root-of-all-evil.png Binary file pics/root-of-all-evil.png has changed diff -r 5ab45f3fee1c -r f211d9cb856e progs/mandelbrot.scala --- a/progs/mandelbrot.scala Sat Jun 16 20:55:51 2018 +0100 +++ b/progs/mandelbrot.scala Fri Jun 22 13:34:05 2018 +0100 @@ -6,89 +6,105 @@ import javax.swing.JFrame import javax.swing.JPanel import javax.swing.WindowConstants +import scala.language.implicitConversions // complex numbers -case class Complex(val a: Double, val b: Double) { - // represents the complex number a + b * i - def +(that: Complex) = Complex(this.a + that.a, this.b + that.b) - def -(that: Complex) = Complex(this.a - that.a, this.b - that.b) - def *(that: Complex) = Complex(this.a * that.a - this.b * that.b, - this.a * that.b + that.a * this.b) - def *(that: Double) = Complex(this.a * that, this.b * that) - def abs() = Math.sqrt(this.a * this.a + this.b * this.b) +case class Complex(val re: Double, val im: Double) { + // represents the complex number re + im * i + def +(that: Complex) = Complex(this.re + that.re, this.im + that.im) + def -(that: Complex) = Complex(this.re - that.re, this.im - that.im) + def *(that: Complex) = Complex(this.re * that.re - this.im * that.im, + this.re * that.im + that.re * this.im) + def *(that: Double) = Complex(this.re * that, this.im * that) + def abs() = Math.sqrt(this.re * this.re + this.im * this.im) } -// some customn colours +object i extends Complex(0, 1) + +implicit def double2complex(re: Double): Complex = Complex(re, 0) + +// some customn colours for the "sliding effect" val colours = List( - new Color(66, 30, 15), new Color(25, 7, 26), - new Color(9, 1, 47), new Color(4, 4, 73), - new Color(0, 7, 100), new Color(12, 44, 138), - new Color(24, 82, 177), new Color(57, 125, 209), - new Color(134, 181, 229), new Color(211, 236, 248), - new Color(241, 233, 191), new Color(248, 201, 95), - new Color(255, 170, 0), new Color(204, 128, 0), - new Color(153, 87, 0), new Color(106, 52, 3)) + new Color(66, 30, 15), new Color(25, 7, 26), + new Color(9, 1, 47), new Color(4, 4, 73), + new Color(0, 7, 100), new Color(12, 44, 138), + new Color(24, 82, 177), new Color(57, 125, 209), + new Color(134, 181, 229), new Color(211, 236, 248), + new Color(241, 233, 191), new Color(248, 201, 95), + new Color(255, 170, 0), new Color(204, 128, 0), + new Color(153, 87, 0), new Color(106, 52, 3)) -// the viewer panel +// the viewer panel with a canvas class Viewer(width: Int, height: Int) extends JPanel { - val canvas = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB) - clearCanvas(Color.black) - - override def paintComponent(g: Graphics) = - g.asInstanceOf[Graphics2D].drawImage(canvas, null, null) + val canvas = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB) + + override def paintComponent(g: Graphics) = + g.asInstanceOf[Graphics2D].drawImage(canvas, null, null) + + override def getPreferredSize() = + new Dimension(width, height) - override def getPreferredSize() = - new Dimension(width, height) - - def clearCanvas(color: Color) = { - for(x <- 0 to width - 1; - y <- 0 to height - 1) canvas.setRGB(x, y, color.getRGB()) - repaint() - } - + def clearCanvas(color: Color) = { + for (x <- 0 to width - 1; y <- 0 to height - 1) + canvas.setRGB(x, y, color.getRGB()) + repaint() + } } -def openViewer(width: Int, height: Int) = { - val frame = new JFrame("XYPlane") - val viewer = new Viewer(width, height) - frame.add(viewer) - frame.pack() - frame.setVisible(true) - frame.setResizable(false) - frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE) - viewer +// initialising the viewer +def openViewer(width: Int, height: Int) : Viewer = { + val frame = new JFrame("XYPlane") + val viewer = new Viewer(width, height) + frame.add(viewer) + frame.pack() + frame.setVisible(true) + frame.setResizable(false) + frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE) + viewer } -val W = 900 -val H = 800 +// some hardcoded data +val W = 900 // width +val H = 800 // height val black = Color.black val viewer = openViewer(W, H) - +// drawing a pixel on the canvas def pixel(x: Int, y: Int, color: Color) = viewer.canvas.setRGB(x, y, color.getRGB()) - + -def mandelbrot(start: Complex, end: Complex, level: Int) : Unit = { +// calculating the number of iterations using lazy streams +// the iteration goes on for a maximum of max steps, +// but might leave early when the pred is satisfied +def iterations(c: Complex, max: Int) : Int = { + def next(z: Complex) = z * z + c + def pred(z: Complex) = z.abs < 2 // exit condition + Stream.iterate(0.0 * i, max)(next).takeWhile(pred).size +} + +// main function +def mandelbrot(start: Complex, end: Complex, max: Int) : Unit = { viewer.clearCanvas(black) - - val delta_x = (end.a - start.a) / W - val delta_y = (end.b - start.b) / H + + // deltas for each grid step + val d_x = (end.re - start.re) / W + val d_y = (end.im - start.im) / H - for (y0 <- (0 until H)) { - for (x0 <- (0 until W)) { + for (y <- (0 until H).par) { + for (x <- (0 until W).par) { - val c = start + Complex(x0 * delta_x, y0 * delta_y) + 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) - def iters(z: Complex, it: Int) : Color = { - if (it < level && z.abs < 2) iters(z * z + c, it + 1) else - if (it == level) black else colours(it % 16) - } - - pixel(x0, y0, iters(Complex(0, 0), 0)) + pixel(x, y, col) } viewer.updateUI() - } + } } // Examples @@ -104,43 +120,38 @@ // example 1 -val exa1 = Complex(-2.0, -1.5) -val exa2 = Complex( 1.0, 1.5) +val exa1 = -2.0 + -1.5 * i +val exa2 = 1.0 + 1.5 * i time_needed(mandelbrot(exa1, exa2, 1000)) // example 2 -val exb1 = Complex(-0.37465401, 0.659227668) -val exb2 = Complex(-0.37332410, 0.66020767) +val exb1 = -0.37465401 + 0.659227668 * i +val exb2 = -0.37332410 + 0.66020767 * i -time_needed(mandelbrot(exb1, exb2, 1000)) +//time_needed(mandelbrot(exb1, exb2, 1000)) // example 3 -val exc1 = Complex(0.435396403, 0.367981352) -val exc2 = Complex(0.451687191, 0.380210061) +val exc1 = 0.435396403 + 0.367981352 * i +val exc2 = 0.451687191 + 0.380210061 * i //time_needed(mandelbrot(exc1, exc2, 1000)) // some more computations with example 3 + val delta = (exc2 - exc1) * 0.0333 + time_needed( - for (i <- (0 to 12)) - mandelbrot(exc1 + delta * i, - exc2 - delta * i, 1000)) - -val exc1 = Complex(0.435396403, 0.367981352) -val exc2 = Complex(0.451687191, 0.380210061) + for (n <- (0 to 12)) + mandelbrot(exc1 + delta * n, + exc2 - delta * n, 100)) -//time_needed(mandelbrot(exc1, exc2, 1000)) - -// some more computations with example 3 -val delta = (exc2 - exc1) * 0.0333 - +/* time_needed( - for (i <- (0 to 12)) - mandelbrot(exc1 + delta * i, - exc2 - delta * i, 1000)) + for (n <- (0 to 12)) + mandelbrot(exc1 + delta * n, + exc2 - delta * n, 1000)) +*/ -