# HG changeset patch # User Christian Urban # Date 1572611965 0 # Node ID c3b33c709696c3fd181a646a713645142b992d04 # Parent 72688efdf17c9453ed2aa01825e05252b67c90e3 updated diff -r 72688efdf17c -r c3b33c709696 cws/cw01.pdf Binary file cws/cw01.pdf has changed diff -r 72688efdf17c -r c3b33c709696 cws/cw02.pdf Binary file cws/cw02.pdf has changed diff -r 72688efdf17c -r c3b33c709696 cws/cw02.tex --- 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, diff -r 72688efdf17c -r c3b33c709696 cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r 72688efdf17c -r c3b33c709696 cws/cw04.pdf Binary file cws/cw04.pdf has changed diff -r 72688efdf17c -r c3b33c709696 cws/cw05.pdf Binary file cws/cw05.pdf has changed diff -r 72688efdf17c -r c3b33c709696 cws/cw05.tex --- 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{} diff -r 72688efdf17c -r c3b33c709696 cws/cw06.pdf Binary file cws/cw06.pdf has changed diff -r 72688efdf17c -r c3b33c709696 handouts/pep-ho.pdf Binary file handouts/pep-ho.pdf has changed diff -r 72688efdf17c -r c3b33c709696 handouts/pep-ho.tex --- 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} diff -r 72688efdf17c -r c3b33c709696 progs/sudoku.scala --- 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 +