30 for generating JavaScript code to build browser applications |
30 for generating JavaScript code to build browser applications |
31 \url{(https://www.scala-js.org)}; and there is work under way to |
31 \url{(https://www.scala-js.org)}; and there is work under way to |
32 have a native Scala compiler generating X86-code |
32 have a native Scala compiler generating X86-code |
33 (\url{http://www.scala-native.org}).} Because of this it has also access to |
33 (\url{http://www.scala-native.org}).} Because of this it has also access to |
34 the myriads of Java libraries. Unlike Java, however, Scala often allows |
34 the myriads of Java libraries. Unlike Java, however, Scala often allows |
35 programmers to write very concise and elegant code. Some therefore say: |
35 programmers to write very concise and elegant code. Some therefore say |
36 ``Scala is the better Java''.\footnote{from |
36 ``Scala is the better Java''.\footnote{from |
37 \url{https://www.slideshare.net/maximnovak/joy-of-scala}} A number |
37 \url{https://www.slideshare.net/maximnovak/joy-of-scala}} A number |
38 of companies---the Guardian, Twitter, Coursera, FourSquare, LinkedIn, |
38 of companies---the Guardian, Twitter, Coursera, FourSquare, LinkedIn, |
39 Netflix to name a few---either use Scala exclusively in production code, |
39 Netflix to name a few---either use Scala exclusively in production code, |
40 or at least to some substantial degree. Scala seems also useful in |
40 or at least to some substantial degree. Scala seems also useful in |
73 \begin{center} |
73 \begin{center} |
74 \includegraphics[scale=0.15]{../pics/vscode.png}\\[-10mm]\mbox{} |
74 \includegraphics[scale=0.15]{../pics/vscode.png}\\[-10mm]\mbox{} |
75 \end{center} |
75 \end{center} |
76 \caption{My personal installation of VS Code includes the following |
76 \caption{My personal installation of VS Code includes the following |
77 packages from Marketplace: Scala Syntax (official), Code Runner, Code |
77 packages from Marketplace: Scala Syntax (official), Code Runner, Code |
78 Spell Checker, Rewrap and Subtle Match Brackets. I have also bound keys |
78 Spell Checker, Rewrap and Subtle Match Brackets. I have also bound |
79 the \keys{Ctrl} \keys{Ret} to the action |
79 the keys \keys{Ctrl} \keys{Ret} to the action |
80 ``Run-Selected-Text-In-Active-Terminal'' in order to quickly evaluate |
80 ``Run-Selected-Text-In-Active-Terminal'' in order to quickly evaluate |
81 small code snippets in the Scala REPL.\label{vscode}} |
81 small code snippets in the Scala REPL.\label{vscode}} |
82 \end{boxedminipage} |
82 \end{boxedminipage} |
83 \end{figure} |
83 \end{figure} |
84 |
84 |
85 What I like most about VS Code is that it provides easy access to the |
85 What I like most about VS Code is that it provides easy access to the |
86 Scala REPL. But if you prefer your own editor for coding, it |
86 Scala REPL. But if you prefer another editor for coding, it is also |
87 is also painless to work with Scala completely on the command line (like you |
87 painless to work with Scala completely on the command line (as you might |
88 might have done with \texttt{g++} in the earlier part of PEP). For the |
88 have done with \texttt{g++} in the earlier part of PEP). For the |
89 lazybones among us, there is even an online editor and environment for |
89 lazybones among us, there is even an online editor and environment for |
90 developing and running Scala programs called \textit{ScalaFiddle}, which |
90 developing and running Scala programs called \textit{ScalaFiddle}, which |
91 requires zero setup (assuming you have a browser handy). You can access |
91 requires zero setup (assuming you have a browser handy). You can access |
92 it from: |
92 it from: |
93 |
93 |
102 \begin{quote} |
102 \begin{quote} |
103 \url{http://scala-ide.org/download/sdk.html} |
103 \url{http://scala-ide.org/download/sdk.html} |
104 \end{quote} |
104 \end{quote} |
105 |
105 |
106 \noindent |
106 \noindent |
107 Also IntelliJ includes plugins for Scala. \textbf{BUT}, I do not |
107 Also IntelliJ includes plugins for Scala. \textbf{BUT}, I do \textbf{not} |
108 recommend the usage of either Eclipse or IntelliJ for PEP: these IDEs |
108 recommend the usage of either Eclipse or IntelliJ for PEP: these IDEs |
109 seem to make your life harder, rather than easier, for the small |
109 seem to make your life harder, rather than easier, for the small |
110 programs we will write in this module. They are really meant to be used |
110 programs we will write in this module. They are really meant to be used |
111 when you have a million-lines codebase, rather than our |
111 when you have a million-lines codebase, rather than our |
112 ``toy-programs''\ldots{}for example why on earth am I required to create a |
112 ``toy-programs''\ldots{}for example why on earth am I required to create a |
113 completely new project with several subdirectories when I just want to |
113 completely new project with several subdirectories when I just want to |
114 try out 20-lines of Scala code? Your mileage may vary. ;o) |
114 try out 20-lines of Scala code? Your mileage may vary though. ;o) |
115 |
115 |
116 \subsection*{Why Functional Programming?} |
116 \subsection*{Why Functional Programming?} |
117 |
117 |
118 Before we go on, let me explain a bit more why we want to inflict |
118 Before we go on, let me explain a bit more why we want to inflict upon |
119 upon you another programming language. You hopefully have mastered Java and |
119 you another programming language. You hopefully have mastered Java and |
120 C++\ldots{}the world should be your oyster, no? Well, it is not that |
120 C++\ldots{}the world should be your oyster, no? Well, it is not that |
121 easy. We do require Scala in PEP, but actually we do not deeply care |
121 easy. We do require Scala in PEP, but actually we do not religiously |
122 whether you learn Scala---after all it is just a programming language |
122 care whether you learn Scala---after all it is just a programming |
123 (albeit a nifty one IMHO). What we do care about is that you learn about |
123 language (albeit a nifty one IMHO). What we do care about is that you |
124 \textit{functional programming}. Scala is just the vehicle for that. |
124 learn about \textit{functional programming}. Scala is just the vehicle |
|
125 for that. Still you need to learn Scala well enough to get good grades |
|
126 in PEP, but functional programming could equally be taught with Haskell, |
|
127 F\#, SML, Ocaml, Kotlin, Scheme, Elm and many other functional |
|
128 programming languages. %Your friendly lecturer just happens to like Scala |
|
129 %and the Department agreed that it is a good idea to inflict Scala upon |
|
130 %you. |
125 |
131 |
126 Very likely writing programs in a functional programming language is |
132 Very likely writing programs in a functional programming language is |
127 quite different from what you are used to in your study so far. It |
133 quite different from what you are used to in your study so far. It |
128 might even be totally alien to you. The reason is that functional |
134 might even be totally alien to you. The reason is that functional |
129 programming seems to go against the core principles of |
135 programming seems to go against the core principles of |
130 \textit{imperative programming} (which is what you do in Java and C++ |
136 \textit{imperative programming} (which is what you do in Java and C++ |
131 for example). The main idea of imperative programming is that you have |
137 for example). The main idea of imperative programming is that you have |
132 some form of ``state'' in your program and you continuously change this |
138 some form of ``state'' in your program and you continuously change this |
133 state by issuing some commands (e.g.~updating a field in an array, |
139 state by issuing some commands (e.g.~updating a field in an array or |
134 adding one to a variable and so on). The classic example for this style |
140 object, adding one to a variable and so on). The classic example for |
135 of programming is a \texttt{for}-loop, say |
141 this style of programming are \texttt{for}-loops, for example |
136 |
142 |
137 \begin{lstlisting}[language=C,numbers=none] |
143 \begin{lstlisting}[language=C,numbers=none] |
138 for (int i = 10; i < 20; i++) { |
144 for (int i = 10; i < 20; i++) { |
139 ...Do something interesting with i... |
145 //...Do something interesting with i... |
140 } |
146 } |
141 \end{lstlisting} |
147 \end{lstlisting} |
142 |
148 |
143 \noindent Here the integer variable \texttt{i} embodies the state, which |
149 \noindent Here the integer variable \texttt{i} embodies the state, which |
144 is first set to \texttt{10} and then increased by one in each |
150 is first set to \texttt{10} and then increased by one in each |
145 loop-iteration until it reaches \texttt{20} at which point the loop |
151 loop-iteration until it reaches \texttt{20} at which point the loop |
146 exits. When this code is compiled and actually runs, there will be some |
152 exits. When this code is compiled and actually runs, there will be some |
147 dedicated space reserved for \texttt{i} in memory which contains its |
153 dedicated space reserved for \texttt{i} in memory. This space of |
148 current value\ldots\texttt{10} at the beginning, and then the content |
154 typically 32 bits contains its current value\ldots\texttt{10} at the |
149 will be updated, or replaced, by some new content in every iteration. |
155 beginning, and then the content will be updated by, or overwritten with, |
150 The main point here is that this kind of updating, or manipulating, |
156 some new content in every iteration. The main point here is that this |
151 memory is \textbf{PURE EVIL}!! |
157 kind of updating, or manipulating, memory is 25.806\ldots or \textbf{THE |
|
158 ROOT OF ALL EVIL}!! |
|
159 |
|
160 \begin{center} |
|
161 \includegraphics[scale=0.25]{../pics/root-of-all-evil.png} |
|
162 \end{center} |
|
163 |
152 |
164 |
153 \noindent |
165 \noindent |
154 \ldots{}Well, it is perfectly benign if you have a sequential program |
166 \ldots{}Well, it is perfectly benign if you have a sequential program |
155 that gets run instruction by instruction...nicely one after another. |
167 that gets run instruction by instruction...nicely one after another. |
156 This kind of running code uses a single core of your CPU and goes as |
168 This kind of running code uses a single core of your CPU and goes as |
163 fast. This unfortunately does not happen any more nowadays. To get you |
175 fast. This unfortunately does not happen any more nowadays. To get you |
164 out of this dreadful situation, CPU producers pile more and more |
176 out of this dreadful situation, CPU producers pile more and more |
165 cores into CPUs in order to make them more powerful and potentially make |
177 cores into CPUs in order to make them more powerful and potentially make |
166 software faster. The task for you as developer is to take somehow |
178 software faster. The task for you as developer is to take somehow |
167 advantage of these cores by running as much of your code as possible in |
179 advantage of these cores by running as much of your code as possible in |
168 parallel on as many core you have available (typically 4 in modern |
180 parallel on as many cores you have available (typically 4 in modern |
169 laptops and sometimes much more on high-end machines). In this |
181 laptops and sometimes much more on high-end machines). In this |
170 situation, \textit{mutable} variables like \texttt{i} above are evil, or |
182 situation, \textit{mutable} variables like \texttt{i} above are evil, or |
171 at least a major nuisance: Because if you want to distribute some of the |
183 at least a major nuisance: Because if you want to distribute some of the |
172 loop-iterations over the cores that are currently idle in your system, |
184 loop-iterations over the cores that are currently idle in your system, |
173 you need to be extremely careful about who can read and write (update) |
185 you need to be extremely careful about who can read and overwrite |
174 the variable \texttt{i}.\footnote{If you are of the belief that nothing |
186 the variable \texttt{i}.\footnote{If you are of the mistaken belief that nothing |
175 nasty can happen to \texttt{i} inside the \texttt{for}-loop, then you |
187 nasty can happen to \texttt{i} inside the \texttt{for}-loop, then you |
176 need to go back over the C++ material.} Especially the writing operation |
188 need to go back over the C++ material.} Especially the writing operation |
177 is critical because you do not want that conflicting writes mess about |
189 is critical because you do not want that conflicting writes mess about |
178 with \texttt{i}. Take my word: an untold amount of misery has arisen |
190 with \texttt{i}. Take my word: an untold amount of misery has arisen |
179 from this problem. The catch is that if you try to solve this problem in |
191 from this problem. The catch is that if you try to solve this problem in |
184 first place. If you are less defensive, then usually all hell breaks |
196 first place. If you are less defensive, then usually all hell breaks |
185 loose by seemingly obtaining random results. And forget the idea of |
197 loose by seemingly obtaining random results. And forget the idea of |
186 being able to debug such code. |
198 being able to debug such code. |
187 |
199 |
188 The central idea of functional programming is to eliminate any state |
200 The central idea of functional programming is to eliminate any state |
189 from programs---or at least from the ``interesting'' (computational |
201 from programs---or at least from the ``interesting bits''. Because then |
190 intensive) parts. Because then it is easy to parallelize the resulting |
202 it is easy to parallelize the resulting programs: if you do not have any |
191 programs: if you do not have any state, then once created, all memory |
203 state, then once created, all memory content stays unchanged and reads |
192 content stays unchanged and reads to such memory are absolutely safe |
204 to such memory are absolutely safe without the need of any |
193 without the need of any synchronisation. An example is given in |
205 synchronisation. An example is given in Figure~\ref{mand} where in the |
194 Figure~\ref{mand} where in the absence of the annoying state, Scala |
206 absence of the annoying state, Scala makes it very easy to calculate the |
195 makes it very easy to calculate the Mandelbrot set on as many cores of |
207 Mandelbrot set on as many cores of your CPU as possible. Why is it so |
196 your CPU as possible. Why is it so easy in this example? Because each |
208 easy in this example? Because each pixel in the Mandelbrot set can be |
197 pixel in the Mandelbrot set can be calculated independently and the |
209 calculated independently and the calculation does not need to update any |
198 calculation does not need to update any variable. It is so easy in fact |
210 variable. It is so easy in fact that going from the sequential version |
199 that going from the sequential version of the Mandelbrot program to the |
211 of the Mandelbrot program to the parallel version can be achieved by |
200 parallel version can be achieved by adding just eight characters. |
212 adding just eight characters---in two places you have to add |
201 Try the same in C++ or Java! |
213 \texttt{.par}. Try the same in C++ or Java! |
202 |
214 |
203 \begin{figure}[p] |
215 \begin{figure}[p] |
204 \begin{boxedminipage}{\textwidth} |
216 \begin{boxedminipage}{\textwidth} |
205 \begin{center} |
217 \begin{center} |
206 \begin{tabular}{c} |
218 \begin{tabular}{c} |
210 Wellknown Mandelbrot program for generating pretty pictures due to |
222 Wellknown Mandelbrot program for generating pretty pictures due to |
211 Benoit Mandelbrot. (\url{https://en.wikipedia.org/wiki/Mandelbrot_set}) |
223 Benoit Mandelbrot. (\url{https://en.wikipedia.org/wiki/Mandelbrot_set}) |
212 \bigskip |
224 \bigskip |
213 |
225 |
214 |
226 |
215 \begin{tabular}[t]{p{5cm}|p{5cm}} |
227 \begin{tabular}{@{}p{6cm}|p{6cm}@{}} |
216 \includegraphics[scale=0.15]{../pics/mand4.png} & |
228 \includegraphics[scale=0.15]{../pics/mand4.png} & |
217 \includegraphics[scale=0.15]{../pics/mand3.png} \\ |
229 \includegraphics[scale=0.15]{../pics/mand3.png} \\ |
218 \begin{minipage}{0.5\textwidth}\small |
230 \footnotesize |
219 a |
231 {\begin{lstlisting} |
220 \begin{lstlisting}[numbers=none] |
232 for (y <- (0 until H)) { |
221 ww |
233 for (x <- (0 until W)) { |
222 \end{lstlisting} |
234 |
223 \end{minipage} |
235 val c = start + |
|
236 (x * d_x + y * d_y * i) |
|
237 val iters = iterations(c, max) |
|
238 val col = |
|
239 if (iters == max) black |
|
240 else colours(iters % 16) |
|
241 |
|
242 pixel(x, y, col) |
|
243 } |
|
244 viewer.updateUI() |
|
245 } |
|
246 \end{lstlisting}} |
224 & \\ |
247 & \\ |
225 \end{tabular} |
248 \end{tabular} |
226 \end{center} |
249 \end{center} |
227 \caption{Test \label{mand}} |
250 \caption{Test \label{mand}} |
228 \end{boxedminipage} |
251 \end{boxedminipage} |
229 \end{figure} |
252 \end{figure} |
230 |
253 |
231 But remember that this easy parallelisation of code requires that we |
254 But remember that this easy parallelisation of code requires that we |
232 have no state in our program\ldots{} that is no counters like \texttt{i} |
255 have no state in our programs\ldots{} that is no counters like |
233 in \texttt{for}-loops. You might then ask, how do I write loops without |
256 \texttt{i} in \texttt{for}-loops. You might then ask, how do I write |
234 such counters? Well, teaching you that this is possible is one of the main |
257 loops without such counters? Well, teaching you that this is possible is |
235 points of the Scala-part in PEP. I can assure you it is possible, but you |
258 one of the main points of the Scala-part in PEP. I can assure you it is |
236 have to get your head around it. Once you mastered this, it will be fun |
259 possible, but you have to get your head around it. Once you have |
237 to have no state in your programs (a side product is that it much easier |
260 mastered this, it will be fun to have no state in your programs (a side |
238 to debug state-less code and also more often than not easier to understand). |
261 product is that it much easier to debug state-less code and also more |
239 So good luck with Scala! |
262 often than not easier to understand). So good luck with |
240 |
263 Scala!\footnote{If you are still not convinced about the function |
|
264 programming ``thing'', there are a few more arguments: a lot of research |
|
265 in programming languages happens to take place in functional programming |
|
266 languages. This has resulted in ultra-useful features such as |
|
267 pattern-matching, strong type-systems, lazyness, implicits, algebraic |
|
268 datatypes to name a few. Imperative languages seem to always lag behind |
|
269 in adopting them: I know, for example, that Java will at some point in |
|
270 the future support pattern-matching, which has been used in SML for at |
|
271 least 40(!) years. See |
|
272 \url{http://cr.openjdk.java.net/~briangoetz/amber/pattern-match.html}. |
|
273 Also Rust, a C-like programming language that has been developed since |
|
274 2010 and is gaining quite some interest, borrows many ideas from |
|
275 functional programming from yesteryear.} |
241 |
276 |
242 \subsection*{The Very Basics} |
277 \subsection*{The Very Basics} |
243 |
278 |
244 One advantage of Scala over Java is that it includes an interpreter (a |
279 One advantage of Scala over Java is that it includes an interpreter (a |
245 REPL, or |
280 REPL, or |