Binary file cws/cw01.pdf has changed

Binary file cws/cw02.pdf has changed

--- a/cws/cw02.tex	Thu Oct 31 12:01:56 2019 +0000
+++ b/cws/cw02.tex	Fri Nov 01 12:39:25 2019 +0000
@@ -72,7 +72,7 @@
 \noindent
 \textbf{For Part 2:} use \texttt{.split(",").toList} for splitting
 strings according to commas (similarly $\backslash$\texttt{n}),
-\texttt{.getOrElse(..,..)} allows to querry a Map, but also gives a
+\texttt{.getOrElse(..,..)} allows to query a Map, but also gives a
 default value if the Map is not defined, a Map can be `updated' by
 using \texttt{+}, \texttt{.contains} and \texttt{.filter} can test whether
 an element is included in a list, and respectively filter out elements in a list,

Binary file cws/cw03.pdf has changed

Binary file cws/cw04.pdf has changed

Binary file cws/cw05.pdf has changed

--- a/cws/cw05.tex	Thu Oct 31 12:01:56 2019 +0000
+++ b/cws/cw05.tex	Fri Nov 01 12:39:25 2019 +0000
@@ -15,14 +15,14 @@
 
 \section*{Coursework 10 (Scala)}
 
-\mbox{}\hfill\textit{``What one programmer can do in one month,}\\
-\mbox{}\hfill\textit{two programmers can do in two months.''}\smallskip\\
-\mbox{}\hfill\textit{ --- Frederick P.~Brooks (author of The Mythical Man-Month)}\bigskip\medskip
+%\mbox{}\hfill\textit{``What one programmer can do in one month,}\\
+%\mbox{}\hfill\textit{two programmers can do in two months.''}\smallskip\\
+%\mbox{}\hfill\textit{ --- Frederick P.~Brooks (author of The Mythical Man-Month)}\bigskip\medskip
 
 
 \noindent
 This coursework is about a small programming
-language called brainf***. The courswork is worth 10\% and you need to 
+language called brainf***. The coursework is worth 10\% and you need to 
 submit on \cwTEN{} at 4pm.\bigskip
 
 \IMPORTANT{}

Binary file cws/cw06.pdf has changed

Binary file handouts/pep-ho.pdf has changed

--- a/handouts/pep-ho.tex	Thu Oct 31 12:01:56 2019 +0000
+++ b/handouts/pep-ho.tex	Fri Nov 01 12:39:25 2019 +0000
@@ -35,7 +35,7 @@
 %from program fragments.
 
 
-%explain graph coloring program (examples from)
+%explain graph colouring program (examples from)
 %https://www.metalevel.at/prolog/optimization
 
 % nice example for map and reduce using Harry potter characters
@@ -386,7 +386,7 @@
 
 \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
 $ scala
-Welcome to Scala 2.13.0 (Java HotSpot(TM) 64-Bit Server VM, Java 9).
+Welcome to Scala 2.13.1 (Java HotSpot(TM) 64-Bit Server VM, Java 9).
 Type in expressions for evaluation. Or try :help.
 
 scala>
@@ -609,9 +609,11 @@
 
 \noindent
 but this seems a bit overkill for a small function like \code{fact}.
-Note that Scala does not have a \code{then}-keyword in an \code{if}-statement.
-Note also that there are a few other ways of how to define a function. We 
-will see some of them in the next sections.
+Note that Scala does not have a \code{then}-keyword in an
+\code{if}-statement; and there should be always an \code{else}-branch.
+Never write an \code{if} without an \code{else}, unless you know what
+you are doing! Note also that there are a few other ways of how to
+define a function. We will see some of them in the next sections.
 
 Before we go on, let me explain one tricky point in function
 definitions, especially in larger definitions. What does a Scala function
@@ -836,13 +838,14 @@
 res5 = Set(2, 1, 0)
 \end{lstlisting}
 
-\noindent This is the correct result for sets, as there are
-only three equivalence classes of integers modulo 3. Note that
-in this example we need to ``help'' Scala to transform the
-numbers into a set of integers by explicitly annotating the
-type \code{Int}. Since maps and for-comprehensions are
-just syntactic variants of each other, the latter can also be
-written as
+\noindent This\footnote{This returns actually \code{HashSet(2, 1, 3)},
+but this is just an implementation detail of how sets are implemented in
+Scala.} is the correct result for sets, as there are only three
+equivalence classes of integers modulo 3. Note that in this example we
+need to ``help'' Scala to transform the numbers into a set of integers
+by explicitly annotating the type \code{Int}. Since maps and
+for-comprehensions are just syntactic variants of each other, the latter
+can also be written as
 
 \begin{lstlisting}[numbers=none]
 scala> for (n <- (1 to 8).toSet[Int]) yield n % 3
@@ -900,7 +903,7 @@
 
 \subsection*{Results and Side-Effects}
 
-While hopefully this all about maps looks reasonable, there is one
+While hopefully all this about maps looks reasonable, there is one
 complication: In the examples above we always wanted to transform one
 list into another list (e.g.~list of squares), or one set into another
 set (set of numbers into set of remainders modulo 3). What happens if we
@@ -932,7 +935,7 @@
 5 * 5 = 25
 \end{lstlisting}%$
 
-\noindent In this code I use a variable assignment (\code{val
+\noindent In this code I use a value assignment (\code{val
 square = ...} ) and also what is called in Scala a
 \emph{string interpolation}, written \code{s"..."}. The latter
 is for printing out an equation. It allows me to refer to the
@@ -986,8 +989,9 @@
 \noindent
 and indeed this is accepted Scala code and produces the expected result,
 namely \code{36}, \textbf{BUT} this is imperative style and not
-permitted in PEP. It uses a \code{var} and therefore violates the
-immutability property I ask for in your code. Sorry!
+permitted in PEP. If you submit this kind of code, you get 0 marks. The
+code 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
@@ -1005,10 +1009,131 @@
 all aggregate functions are pre-defined and often you have to write your
 own recursive function for this.
 
-
 \subsection*{Higher-Order Functions}
 
-TBD
+Functions obviously play a central role in functional programming. Two simple
+examples are
+
+\begin{lstlisting}[numbers=none]
+def even(x: Int) : Boolean = x % 2 == 0
+def odd(x: Int) : Boolean = x % 2 == 1
+\end{lstlisting} 
+
+\noindent
+More interestingly, the concept of functions is really pushed to the
+limit in functional programming. Functions can take other functions as
+arguments and can return a function as a result. This is actually
+quite important for making code generic. Assume a list of 10 elements:
+
+\begin{lstlisting}[numbers=none]
+val lst = (1 to 10).toList  
+\end{lstlisting} 
+
+\noindent 
+Say, we want to filter out all even numbers. For this we can use 
+
+\begin{lstlisting}[numbers=none]
+scala> lst.filter(even)
+List(2, 4, 6, 8, 10)
+\end{lstlisting} 
+
+\noindent
+where \code{filter} expects a function as argument specifying which
+elements of the list should be kept and which should be left out. By
+allowing \code{filter} to take a function as argument, we can also
+easily filter out odd numbers as well.
+
+\begin{lstlisting}[numbers=none]
+scala> lst.filter(odd)
+List(1, 3, 5, 7, 9)
+\end{lstlisting} 
+
+\noindent
+Such function arguments are quite frequently used for ``generic'' functions.
+For example it is easy to count odd elements in a list or find the first
+even number in a list:
+
+\begin{lstlisting}[numbers=none]
+scala> lst.count(odd)
+5
+scala> lst.find(even)
+Some(2)
+\end{lstlisting} 
+
+\noindent
+Recall that the return type of \code{even} and \code{odd} are booleans.
+Such function are sometimes called predicates, because they determine
+what should be true for an element and what false, and then performing
+some operation according to this boolean. Such predicates are quite useful. 
+Say you want to sort the \code{lst}-list in ascending and descending order. 
+For this you can write
+
+\begin{lstlisting}[numbers=none]
+lst.sortWith(_ < _)
+lst.sortWith(_ > _)
+\end{lstlisting} 
+
+\noindent where \code{sortWith} expects a predicate as argument. The
+construction \code{_ < _} stands for a function that takes two arguments
+and returns true when the first one is smaller than the second. You can
+think of this as elegant shorthand notation for 
+
+\begin{lstlisting}[numbers=none]
+def smaller(x: Int, y: Int) : Boolean = x < y
+lst.sortWith(smaller)
+\end{lstlisting} 
+
+\noindent
+Say you want to find in \code{lst} the first odd number greater than 2.
+For this you need to write a function that specifies exactly this
+condition. To do this you can use a slight variant of the shorthand
+notation above
+
+\begin{lstlisting}[numbers=none]
+scala> lst.find(n => odd(n) && n > 2)
+Some(3)
+\end{lstlisting} 
+
+\noindent
+Here \code{n => ...} specifies a function that takes \code{n} as
+argument and uses this argument in whatever comes after the double
+arrow. If you want to use this mechanism for looking for an element that
+is both even and odd, then of course you out of luck.
+
+\begin{lstlisting}[numbers=none]
+scala> lst.find(n => odd(n) && even(n))
+None
+\end{lstlisting} 
+
+While functions taking functions as arguments seems a rather useful
+feature, the utility of returning a function might not be so clear. 
+I admit the following example is a bit contrived, but believe me
+sometims functions produce other functions in a very meaningful way.
+Say we want to generate functions according to strings, as in
+
+\begin{lstlisting}[numbers=none]
+def mkfn(s: String) : (Int => Boolean) =
+  if (s == "even") even else odd
+\end{lstlisting}
+
+\noindent
+With this we can generate the required function for \code{filter}
+according to a string:
+
+\begin{lstlisting}[numbers=none]
+scala> lst.filter(mkfn("even"))
+List(2, 4, 6, 8, 10)
+scala> lst.filter(mkfn("foo"))
+List(1, 3, 5, 7, 9)
+\end{lstlisting}
+
+\noindent
+As said, this is example is a bit contrived---I was not able to think
+of anything simple, but for example in the Compiler module next year I
+show a compilation functions that needs to generate functions as
+intermediate result. Anyway, notice the interesting type we had to
+annotate to \code{mkfn}. Types of Scala are described next.
+
 
 \subsection*{Types}
 
@@ -1056,10 +1181,10 @@
 
 
 \begin{lstlisting}[ numbers=none]
-def quo_rem(m: Int, n: Int) : (Int, Int) = (m / n, m % n)
+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
 \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
@@ -1071,10 +1196,12 @@
 (Int, Int) => (Int, Int)
 \end{lstlisting}
 
+\noindent
 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
+\code{=>}. This is sometimes also called \emph{function arrow}.  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 {
@@ -1086,7 +1213,8 @@
 \end{lstlisting}
 
 \noindent It takes an integer as input argument and returns a
-string. 
+string. The type of the function generated in \code{mkfn} above, is
+\code{Int => Boolean}.
 
 Unfortunately, unlike other functional programming languages, there is
 in Scala no easy way to find out the types of existing functions, except
@@ -1160,8 +1288,8 @@
 constructions. I think, the point of Java 8 and successors was to lift this
 restriction. But in all functional programming languages,
 including Scala, it is really essential to allow functions as
-input argument. Above you already seen \code{map} and
-\code{foreach} which need this. Consider the functions
+input argument. Above you have already seen \code{map} and
+\code{foreach} which need this feature. Consider the functions
 \code{print} and \code{println}, which both print out strings,
 but the latter adds a line break. You can call \code{foreach}
 with either of them and thus changing how, for example, five
@@ -1193,24 +1321,23 @@
 \emph{polymorphic}.\footnote{Another interesting topic about
 types, but we omit it here for the sake of brevity.} 
 
-There is one more type constructor that is rather special. It
-is called \code{Unit}. Recall that \code{Boolean} has two
-values, namely \code{true} and \code{false}. This can be used,
-for example, to test something and decide whether the test
-succeeds or not. In contrast the type \code{Unit} has only a
-single value, written \code{()}. This seems like a completely
-useless type and return value for a function, but is actually
-quite useful. It indicates when the function does not return
-any result. The purpose of these functions is to cause
-something being written on the screen or written into a file,
-for example. This is what is called they cause some effect on 
-the side, namely a new content displayed on the screen or some
-new data in a file. Scala uses the \code{Unit} type to indicate
-that a function does not have a result, but potentially causes
-some side-effect. Typical examples are the printing functions, 
-like \code{print}.
+There is one more type constructor that is rather special. It is
+called \code{Unit}. Recall that \code{Boolean} has two values, namely
+\code{true} and \code{false}. This can be used, for example, to test
+something and decide whether the test succeeds or not. In contrast the
+type \code{Unit} has only a single value, written \code{()}. This
+seems like a completely useless type and return value for a function,
+but is actually quite useful. It indicates when the function does not
+return any result. The purpose of these functions is to cause
+something being written on the screen or written into a file, for
+example. This is what is called they cause a \emph{side-effect}, for
+example new content displayed on the screen or some new data in a
+file. Scala uses the \code{Unit} type to indicate that a function does
+not have a result, but potentially causes a side-effect. Typical
+examples are the printing functions, like \code{print}.
 
-\subsection*{User-Defined Types}
+
+%%\subsection*{User-Defined Types}
 
 % \subsection*{Cool Stuff}
 

--- a/progs/sudoku.scala	Thu Oct 31 12:01:56 2019 +0000
+++ b/progs/sudoku.scala	Fri Nov 01 12:39:25 2019 +0000
@@ -1,6 +1,12 @@
 // Sudoku
 //========
 
+// call parallel version with
+//
+// scala -cp scala-parallel-collections_2.13-0.2.0.jar sudoku.scala 
+//
+// java -cp .:scala-library-2.13.0.jar:scala-parallel-collections_2.13-0.2.0.jar Sudoku
+
 object Sudoku extends App { 
 
 import scala.collection.parallel.CollectionConverters._
@@ -31,10 +37,6 @@
 }         
 
 
-//get_row(game0, 0)
-//get_row(game0, 1)
-//get_box(game0, (3,1))
-
 def update(game: String, pos: Int, value: Char): String = 
   game.updated(pos, value)
 
@@ -44,11 +46,6 @@
 def candidates(game: String, pos: Pos): List[Char] = 
   allValues.diff(toAvoid(game, pos))
 
-//candidates(game0, (0, 0))
-
-//def pretty(game: String): String = 
-//  "\n" ++ (game.sliding(maxValue, maxValue).mkString("\n"))
-
 def search(game: String): List[String] = {
   if (isDone(game)) List(game)
   else 
@@ -56,52 +53,21 @@
       map(c => search(update(game, empty(game), c))).toList.flatten
 }
 
-// two easy games
-val game0 = """.14.6.3..
-              |62...4..9
-              |.8..5.6..
-              |.6.2....3
-              |.7..1..5.
-              |5....9.6.
-              |..6.2..3.
-              |1..5...92
-              |..7.9.41.""".stripMargin.replaceAll("\\n", "")
-
-val game1 = """23.915...
-              |...2..54.
-              |6.7......
-              |..1.....9
-              |89.5.3.17
-              |5.....6..
-              |......9.5
-              |.16..7...
-              |...329..1""".stripMargin.replaceAll("\\n", "")
-
-
-// a game that is in the sligtly harder category
-val game2 = """8........
-              |..36.....
-              |.7..9.2..
-              |.5...7...
-              |....457..
-              |...1...3.
-              |..1....68
-              |..85...1.
-              |.9....4..""".stripMargin.replaceAll("\\n", "")
-
-// a game with multiple solutions
-val game3 = """.8...9743
-              |.5...8.1.
-              |.1.......
-              |8....5...
-              |...8.4...
-              |...3....6
-              |.......7.
-              |.3.5...8.
-              |9724...5.""".stripMargin.replaceAll("\\n", "")
+// a list of hard games according to Andrew Coles and Peter Norvig
 
 val hard_games = 
-  List("85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.",
+  List("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......",
+       "52...6.........7.13...........4..8..6......5...........418.........3..2...87.....",
+       "6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....",
+       "48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....",
+       "....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...",
+       "......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.",
+       "6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6.....",
+       ".524.........7.1..............8.2...3.....6...9.5.....1.6.3...........897........",
+       "6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....",
+       ".923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....",
+
+       "85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.",
        "..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..",
        "12..4......5.69.1...9...5.........7.7...52.9..3......2.9.6...5.4..9..8.1..3...9.4",
        "...57..3.1......2.7...234......8...4..7..4...49....6.5.42...3.....7..9....18.....",
@@ -209,28 +175,30 @@
        "3...8.......7....51..............36...2..4....7...........6.13..452...........8..")
 
 
-
-//search(game0).map(pretty)
-//search(game1).map(pretty)
-
 // for measuring time
 def time_needed[T](i: Int, code: => T) = {
   val start = System.nanoTime()
   for (j <- 1 to i) code
   val end = System.nanoTime()
-  s"${(end - start) / i / 1.0e9} secs"
+  (end - start) / i / 1.0e9
 }
 
-//search(game2).map(pretty)
-//search(game3).distinct.length
-println(time_needed(10, search(game0)))
-println(time_needed(10, search(game1)))
-println(time_needed(4, search(game2)))
-println(time_needed(8, search(game3)))
 
-for (i <- 0 until hard_games.length) {
-    println("   " ++ hard_games(i))
-    println(s"$i: ${time_needed(1, search(hard_games(i)))}")
+val total = 
+  (for ((game, i) <- hard_games.zipWithIndex) yield {
+    val secs = time_needed(1, search(game))
+    println(f"${i}%2.0f: ${game} |${secs}%2.3f secs")
+    secs
+  }).sum
+
+println(f"\ntotal: ${total}%.3f secs")
+
 }
 
-}
\ No newline at end of file
+
+
+// 1 single thread version 800 secs
+// 4 cores parallel version on moderate laptop 400 secs
+// 8 cores (4 physical + 4 hyperthread): 290 secs
+// 36 cores (18 physical + 18 hyperthread): 142 secs
+