--- a/handouts/pep-ho.tex Fri Aug 16 06:51:06 2019 +0100
+++ b/handouts/pep-ho.tex Fri Aug 16 08:45:21 2019 +0100
@@ -121,7 +121,7 @@
\end{center}
\caption{My installation of VS Code includes the following
packages from Marketplace: \textbf{Scala Syntax (official)} 0.3.4,
- \textbf{Code Runner} 0.9.12, \textbf{Code Spell Checker} 1.7.17,
+ \textbf{Code Runner} 0.9.13, \textbf{Code Spell Checker} 1.7.17,
\textbf{Rewrap} 1.9.1 and \textbf{Subtle Match
Brackets} 3.0.0. I have also bound the keys \keys{Ctrl} \keys{Ret} to the
action ``Run-Selected-Text-In-Active-Terminal'' in order to quickly
@@ -189,11 +189,11 @@
programming seems to go against the core principles of
\textit{imperative programming} (which is what you do in Java and C/C++
for example). 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 and so on. The classic
-example for this style of programming is \texttt{for}-loops in C/C++. Consider
-the snippet:
+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 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++) {
@@ -209,7 +209,7 @@
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 manipulating, memory is 25.806\ldots or \textbf{THE ROOT OF
+updating, or overwriting, of memory is 25.806\ldots or \textbf{THE ROOT OF
ALL EVIL}!!
\begin{center}
@@ -224,29 +224,29 @@
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, unlike previous generations of developers who could rely upon the
-fact that every 2 years or so their code would run twice as fast (in
-ideal circumstances) because the clock-speed of their CPUs got twice as
-fast. This unfortunately 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 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
+stuck. This is unlike previous generations of developers who could rely
+upon the fact that every 2 years or so 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 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 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
+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
@@ -359,12 +359,19 @@
Automatic garbage collection was included in Java in 1995; the
functional language LISP had this already in 1958. Generics were added
to Java 5 in 2004; the functional language SML had it since 1990.
-Higher-order functions were added to C$\sharp$ in 2007, to Java 8 in
+Higher-order functions were added to C\# in 2007, to Java 8 in
2014; again LISP had them since 1958. 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.}
+yesteryear.}\medskip
+\noindent
+If you need any after-work distractions, you might have fun reading this
+about FP (functional programming):
+
+\begin{quote}
+\url{https://medium.com/better-programming/fp-toy-7f52ea0a947e}
+\end{quote}
\subsection*{The Very Basics}
@@ -453,7 +460,7 @@
\subsection*{Standalone Scala Apps}
-If you want to write a stand-alone app in Scala, you can
+If you want to write a standalone app in Scala, you can
implement an object that is an instance of \code{App}. For example
write
@@ -619,7 +626,7 @@
but for the sake of argument lets keep the two intermediate values.}
\begin{lstlisting}[numbers=none]
-def iaverage(xs: List[Int]) : Int = {
+def average(xs: List[Int]) : Int = {
val s = xs.sum
val n = xs.length
s / n
@@ -629,12 +636,12 @@
\noindent In this example the expression \code{s / n} is in the last
line of the function---so this will be the result the function
calculates. The two lines before just calculate intermediate values.
-This principle of the `last-line' comes in handy when you need to print
+This principle of the ``last-line'' comes in handy when you need to print
out values, for example, for debugging purposes. Suppose you want
rewrite the function as
\begin{lstlisting}[numbers=none]
-def iaverage(xs: List[Int]) : Int = {
+def average(xs: List[Int]) : Int = {
val s = xs.sum
val n = xs.length
val h = xs.head
@@ -650,11 +657,11 @@
function. Similarly, the value \code{h} is used in the \code{println}
but does not contribute to what integer is returned. However note that
the idea with the ``last line'' is only a rough rule-of-thumb. A better
-rule is probably, the last expression that is evaluated in the function.
+rule might be: the last expression that is evaluated in the function.
Consider the following version of \code{iaverage}:
\begin{lstlisting}[numbers=none]
-def iaverage(xs: List[Int]) : Int = {
+def average(xs: List[Int]) : Int = {
if (xs.length == 0) 0
else xs.sum / xs.length
}
@@ -671,9 +678,23 @@
Summing up, do not use \code{return} in your Scala code! A function
returns what is evaluated by the function as the last expression. There
is always only one such last expression. Previous expressions might
-calculate intermediate values, but they are not returned.
+calculate intermediate values, but they are not returned. If your
+function is supposed to return multiple things, then one way in Scala is
+to use tuples. For example returning the minimum, average and maximum
+can be achieved by
-\subsection*{Loops, or better the Absence thereof}
+\begin{lstlisting}[numbers=none]
+def avr_minmax(xs: List[Int]) : (Int, Int, Int) = {
+ if (xs.length == 0) (0, 0, 0)
+ else (xs.min, xs.sum / xs.length, xs.max)
+}
+\end{lstlisting}
+
+\noindent
+which still satisfies the rule-of-thumb.
+
+
+\subsection*{Loops, or Better the Absence Thereof}
Coming from Java or C/C++, you might be surprised that Scala does
not really have loops. It has instead, what is in functional
@@ -731,10 +752,10 @@
\draw [->,line width=1mm] (A7.south) -- (B7.north);
\draw [->,line width=1mm] (A8.south) -- (B8.north);
- \node [red] (Q0) at (-0.3,0) {\large\texttt{n}};
- \node (Q1) at (-0.3,-0.1) {};
- \node (Q2) at (-0.3,-2.8) {};
- \node [red] (Q3) at (-0.3,-2.95) {\large\texttt{n\,*\,n}};
+ \node [red] (Q0) at (-0.3,-0.3) {\large\texttt{n}};
+ \node (Q1) at (-0.3,-0.4) {};
+ \node (Q2) at (-0.3,-2.5) {};
+ \node [red] (Q3) at (-0.3,-2.65) {\large\texttt{n\,*\,n}};
\draw [->,red,line width=1mm] (Q1.south) -- (Q2.north);
\node [red] at (-1.3,-1.5) {\huge{}\it\textbf{map}};
@@ -745,11 +766,11 @@
On top is the ``input'' list we want to transform; on the left is the
``map'' function for how to transform each element in the input list
(the square function in this case); at the bottom is the result list of
-the map. This means that a map produces a \emph{new} list, unlike a
+the map. This means that a map generates a \emph{new} list, unlike a
for-loop in Java or C/C++ which would most likely just update the
-existing list.
+existing list/array.
-Now there are two ways to express such maps in Scala. The first way is
+Now there are two ways for expressing such maps in Scala. The first way is
called a \emph{for-comprehension}. The keywords are \code{for} and
\code{yield}. Squaring the numbers from 1 to 8 with a for-comprehension
would look as follows:
@@ -760,13 +781,15 @@
\end{lstlisting}
\noindent This for-comprehension states that from the list of numbers
-we draw elements that are given the name \code{n} (which can be
-arbitrary, not just \code{n}) and compute the result of \code{n * n}.
-This way of writing a map resembles a bit the for-loops from imperative
-languages, even though the idea behind for-loops and for-comprehensions
-is quite different. Also, this is a simple example---what comes after
-\code{yield} can be a complex expression enclosed in \texttt{\{...\}}.
-A more complicated example might be
+we draw some elements. We use the name \code{n} to range over these
+elements (whereby the name is arbitrary; we could use something more
+descriptive if we wanted to). Using \code{n} we compute the result of
+\code{n * n} after the \code{yield}. This way of writing a map resembles
+a bit the for-loops from imperative languages, even though the ideas
+behind for-loops and for-comprehensions are quite different. Also, this
+is a simple example---what comes after \code{yield} can be a complex
+expression enclosed in \texttt{\{...\}}. A more complicated example
+might be
\begin{lstlisting}[numbers=none]
scala> for (n <- (1 to 8).toList) yield {
@@ -790,7 +813,7 @@
\noindent In this way, the expression \code{n => n * n} stands for the
function that calculates the square (this is how the \code{n}s are
transformed by the map). It might not be obvious, but
-for-comprehensions above are just syntactic sugar: when compiling such
+the for-comprehensions above are just syntactic sugar: when compiling such
code, Scala translates for-comprehensions into equivalent maps. This
even works when for-comprehensions get more complicated (see below).
@@ -839,7 +862,7 @@
\noindent
In this example the for-comprehension ranges over two lists, and
-produces a list of pairs as output. Or if we want to find all pairs of
+produces a list of pairs as output. Or, if we want to find all pairs of
numbers between 1 and 3 where the sum is an even number, we can write
\begin{lstlisting}[numbers=none]
@@ -850,8 +873,8 @@
\end{lstlisting}
\noindent The \code{if}-condition in this for-comprehension filters out
-all pairs where the sum is not even (therefore \code{(1, 2)} is not in
-the result because the sum is odd).
+all pairs where the sum is not even (therefore \code{(1, 2)}, \code{(2,
+1)} and \code{(3, 2)} are not in the result because their sum is odd).
To sum up, maps (or for-comprehensions) transform one collection into
another. For example a list of \code{Int}s into a list of squares, and
@@ -866,8 +889,8 @@
\end{lstlisting}
\noindent
-This is accepted Scala-code, but utterly bad style. It can be written
-much clearer as:
+This is accepted Scala-code, but utterly bad style (it is more like
+Java). It can be written much clearer as:
\begin{lstlisting}[numbers=none]
scala> val cs = ('a' to 'h').toList
@@ -945,7 +968,7 @@
There is one more usage of for-loops in Java, C/C++ and the like:
sometimes you want to \emph{aggregate} something about a list, for
-example to sum up all its elements. In this case you cannot use map,
+example summing up all its elements. In this case you cannot use map,
because maps \emph{transform} one data collection into another data
collection. They cannot be used to generate a single integer
representing an aggregate. So how is this done in Scala? Let us
@@ -961,10 +984,10 @@
\end{lstlisting}
\noindent
-and indeed is accepted Scala code and produces the expected result,
+and indeed this is accepted Scala code and produces the expected result,
namely \code{36}, \textbf{BUT} this is imperative style and not
-permitted. It uses a \code{var} and therefore violates the immutability
-property I ask for in your code.
+permitted in PEP. It uses a \code{var} and therefore violates the
+immutability property I ask for in your code. Sorry.
So how to do that same thing without using a \code{var}? Well there are
several ways. One way is to define the following recursive
@@ -977,10 +1000,10 @@
\noindent
You can then call \code{sum((1 to 8).toList)} and obtain the same result
-without a mutable for-loop. Obviously for simple things like sum, you
-could have written \code{xs.sum} in the first place. But not all
-aggregate functions are pre-defined and often you have to write your own
-recursive function for this.
+without a mutable variable or for-loop. Obviously for simple things like
+sum, you could have written \code{xs.sum} in the first place. But not
+all aggregate functions are pre-defined and often you have to write your
+own recursive function for this.
\subsection*{Higher-Order Functions}
@@ -1038,22 +1061,20 @@
\noindent Since this function returns a pair of integers, its
-return type needs to be of type \code{(Int, Int)}.
-Incidentally, this is also the input type of this function.
-Notice this function takes \emph{two} arguments, namely
-\code{m} and \code{n}, both of which are integers. They are
-``packaged'' in a pair. Consequently the complete type of
-\code{quo_rem} is
+\emph{return type} needs to be of type \code{(Int, Int)}. Incidentally,
+this is also the \emph{input type} of this function. For this notice
+\code{quo_rem} takes \emph{two} arguments, namely \code{m} and \code{n},
+both of which are integers. They are ``packaged'' in a pair.
+Consequently the complete type of \code{quo_rem} is
\begin{lstlisting}[ numbers=none]
(Int, Int) => (Int, Int)
\end{lstlisting}
-Another special type-constructor is for functions, written as
-the arrow \code{=>}. For example, the type \code{Int =>
-String} is for a function that takes an integer as input
-argument and produces a string as result. A function of this
-type is for instance
+This uses another special type-constructor, written as the arrow
+\code{=>}. For example, the type \code{Int => String} is for a function
+that takes an integer as input argument and produces a string as result.
+A function of this type is for instance
\begin{lstlisting}[numbers=none]
def mk_string(n: Int) : String = n match {
@@ -1065,9 +1086,11 @@
\end{lstlisting}
\noindent It takes an integer as input argument and returns a
-string. Unlike other functional programming languages, there
-is in Scala no easy way to find out the types of existing
-functions, except by looking into the documentation
+string.
+
+Unfortunately, unlike other functional programming languages, there is
+in Scala no easy way to find out the types of existing functions, except
+by looking into the documentation
\begin{quote}
\url{http://www.scala-lang.org/api/current/}