pep-material: comparison handouts/pep-ho.tex

equal deleted inserted replaced

-:52faee6d0be2
+:acaf2099406a
 \begin{center}
 \includegraphics[scale=0.15]{../pics/vscode.png}\\[-10mm]\mbox{}
 \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
 evaluate small code snippets in the Scala REPL. I use the internal
 terminal to run Scala.\label{vscode}}
 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++
 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
+some form of \emph{state} in your program and you continuously change
-state by issuing some commands---for example for updating a field in an
+this state by issuing some commands---for example for updating a field
-array or for adding one to a variable and so on. The classic
+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
+example for this style of programming is a \texttt{for}-loop in C/C++.
-the snippet:
+Consider the snippet:
 \begin{lstlisting}[language=C,numbers=none]
 for (int i = 10; i < 20; i++) {
 //...do something with i...
 }
 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 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}
 \includegraphics[scale=0.25]{../pics/root-of-all-evil.png}
 \end{center}
 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, unlike previous generations of developers who could rely upon the
+stuck. This is unlike previous generations of developers who could rely
-fact that every 2 years or so their code would run twice as fast (in
+upon the fact that every 2 years or so their code would run twice as
-ideal circumstances) because the clock-speed of their CPUs got twice as
+fast  because the clock-speed of their CPUs got twice as fast.
-fast. This unfortunately does not happen any more nowadays. To get you
+Unfortunately this does not happen any more nowadays. To get you out of
-out of this dreadful situation, CPU producers pile more and more
+this dreadful situation, CPU producers pile more and more cores into
-cores into CPUs in order to make them more powerful and potentially make
+CPUs in order to make them more powerful and potentially make software
-software faster. The task for you as developer is to take somehow
+faster. The task for you as developer is to take somehow advantage of
-advantage of these cores by running as much of your code as possible in
+these cores by running as much of your code as possible in parallel on
-parallel on as many cores you have available (typically 4 in modern
+as many cores you have available (typically 4 in modern laptops and
-laptops and sometimes much more on high-end machines). In this
+sometimes much more on high-end machines). In this situation,
-situation, \textit{mutable} variables like \texttt{i} above are evil, or
+\textit{mutable} variables like \texttt{i} above are evil, or at least a
-at least a major nuisance: Because if you want to distribute some of the
+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
+you need to be extremely careful about who can read and overwrite the
-the variable \texttt{i}.\footnote{If you are of the mistaken belief that nothing
+variable \texttt{i}.\footnote{If you are of the mistaken belief that
-nasty can happen to \texttt{i} inside the \texttt{for}-loop, then you
+nothing nasty can happen to \texttt{i} inside the \texttt{for}-loop,
-need to go back over the C++ material.} Especially the writing operation
+then you need to go back over the C++ material.} Especially the writing
-is critical because you do not want that conflicting writes mess about
+operation is critical because you do not want that conflicting writes
-with \texttt{i}. Take my word: an untold amount of misery has arisen
+mess about with \texttt{i}. Take my word: an untold amount of misery has
-from this problem. The catch is that if you try to solve this problem in
+arisen from this problem. The catch is that if you try to solve this
-C/C++ or Java, and be as defensive as possible about reads and writes to
+problem in C/C++ or Java, and be as defensive as possible about reads
-\texttt{i}, then you need to synchronise access to it. The result is that
+and writes to \texttt{i}, then you need to synchronise access to it. The
-very often your program waits more than it runs, thereby
+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.
 40(!) years. See
 \url{http://cr.openjdk.java.net/~briangoetz/amber/pattern-match.html}.
 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}
 One advantage of Scala over Java is that it includes an interpreter (a
 REPL, or
 reference implementation for the assignments, you will need to be
 able to ``play around'' with it!
 \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
 \begin{lstlisting}[numbers=none]
 object Hello extends App {
 function is the value that will be returned. Consider the following
 example:\footnote{We could have written this function in just one line,
 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
 }
 \end{lstlisting}
 \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
 println(s"Input $xs with first element $h")
 s / n
 The \code{println} before just prints out some information about the
 input of this function, but does not contribute to the result of the
 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
 }
 \end{lstlisting}
 empty-case).
 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
-\subsection*{Loops, or better the Absence thereof}
+to use tuples. For example returning the minimum, average and maximum
+can be achieved by
+\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
 programming called, \emph{maps}. To illustrate how they work,
 let us assume you have a list of numbers from 1 to 8 and want to
 \draw [->,line width=1mm] (A5.south) -- (B5.north);
 \draw [->,line width=1mm] (A6.south) -- (B6.north);
 \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 [red] (Q0) at (-0.3,-0.3) {\large\texttt{n}};
-\node (Q1) at (-0.3,-0.1) {};
+\node (Q1) at (-0.3,-0.4) {};
-\node (Q2) at (-0.3,-2.8) {};
+\node (Q2) at (-0.3,-2.5) {};
-\node [red] (Q3) at (-0.3,-2.95) {\large\texttt{n\,*\,n}};
+\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}};
 \end{tikzpicture}
 \end{center}
 \noindent
 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:
 \begin{lstlisting}[numbers=none]
 scala> for (n <- (1 to 8).toList) yield n * n
 res2: List[Int] = List(1, 4, 9, 16, 25, 36, 49, 64)
 \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
+we draw some elements. We use the name \code{n} to range over these
-arbitrary, not just \code{n}) and compute the result of \code{n * n}.
+elements (whereby the name is arbitrary; we could use something more
-This way of writing a map resembles a bit the for-loops from imperative
+descriptive if we wanted to). Using \code{n} we compute the result of
-languages, even though the idea behind for-loops and for-comprehensions
+\code{n * n} after the \code{yield}. This way of writing a map resembles
-is quite different. Also, this is a simple example---what comes after
+a bit the for-loops from imperative languages, even though the ideas
-\code{yield} can be a complex expression enclosed in \texttt{\{...\}}.
+behind for-loops and for-comprehensions are quite different. Also, this
-A more complicated example might be
+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 {
 val i = n + 1
 val j = n - 1
 \end{lstlisting}
 \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).
 The very charming feature of Scala is that such maps or
 for-comprehensions can be written for any kind of data collection, such
 (3,a), (3,b), (3,c), (4,a), (4,b), (4,c))
 \end{lstlisting}
 \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]
 scala> for (n <- (1 to 3).toList;
 m <- (1 to 3).toList;
 if (n + m) % 2 == 0) yield (n, m)
 res7 = List((1,1), (1,3), (2,2), (3,1), (3,3))
 \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
+all pairs where the sum is not even (therefore \code{(1, 2)}, \code{(2,
-the result because the sum is odd).
+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
 so on. There is no need for for-loops in Scala. But please do not be
 tempted to write anything like
 yield cs(n).capitalize
 res8: List[Char] = List(A, B, C, D, E, F, G, H)
 \end{lstlisting}
 \noindent
-This is accepted Scala-code, but utterly bad style. It can be written
+This is accepted Scala-code, but utterly bad style (it is more like
-much clearer as:
+Java). It can be written much clearer as:
 \begin{lstlisting}[numbers=none]
 scala> val cs = ('a' to 'h').toList
 scala> for (c <- cs) yield c.capitalize
 res9: List[Char] = List(A, B, C, D, E, F, G, H)
 \subsection*{Aggregates}
 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
 suppose you want to sum up all elements from a list. You might
 be tempted to write something like
 }
 print(cnt)
 \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
+permitted in PEP. It uses a \code{var} and therefore violates the
-property I ask for in your code.
+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
 \code{sum}-function:
 if (xs.isEmpty) 0 else xs.head + sum(xs.tail)
 \end{lstlisting}
 \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
+without a mutable variable or for-loop. Obviously for simple things like
-could have written \code{xs.sum} in the first place. But not all
+sum, you could have written \code{xs.sum} in the first place. But not
-aggregate functions are pre-defined and often you have to write your own
+all aggregate functions are pre-defined and often you have to write your
-recursive function for this.
+own recursive function for this.
 \subsection*{Higher-Order Functions}
 TBD
 def quo_rem(m: Int, n: Int) : (Int, Int) = (m / n, m % n)
 \end{lstlisting}
 \noindent Since this function returns a pair of integers, its
-return type needs to be of type \code{(Int, Int)}.
+\emph{return type} needs to be of type \code{(Int, Int)}. Incidentally,
-Incidentally, this is also the input type of this function.
+this is also the \emph{input type} of this function. For this notice
-Notice this function takes \emph{two} arguments, namely
+\code{quo_rem} takes \emph{two} arguments, namely \code{m} and \code{n},
-\code{m} and \code{n}, both of which are integers. They are
+both of which are integers. They are ``packaged'' in a pair.
-``packaged'' in a pair. Consequently the complete type of
+Consequently the complete type of \code{quo_rem} is
-\code{quo_rem} is
 \begin{lstlisting}[ numbers=none]
 (Int, Int) => (Int, Int)
 \end{lstlisting}
-Another special type-constructor is for functions, written as
+This uses another special type-constructor, written as the arrow
-the arrow \code{=>}. For example, the type \code{Int =>
+\code{=>}. For example, the type \code{Int => String} is for a function
-String} is for a function that takes an integer as input
+that takes an integer as input argument and produces a string as result.
-argument and produces a string as result. A function of this
+A function of this type is for instance
-type is for instance
 \begin{lstlisting}[numbers=none]
 def mk_string(n: Int) : String = n match {
 case 0 => "zero"
 case 1 => "one"
 case _ => "many"
 }
 \end{lstlisting}
 \noindent It takes an integer as input argument and returns a
-string. Unlike other functional programming languages, there
+string.
-is in Scala no easy way to find out the types of existing
-functions, except by looking into the documentation
+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/}
 \end{quote}

changeset 277	acaf2099406a
parent 275	eb1b4ad23941
child 278	0c2481cd8b1c