Binary file cws/cw01.pdf has changed
--- a/cws/cw01.tex Wed May 31 09:26:08 2017 +0100
+++ b/cws/cw01.tex Thu Nov 02 14:47:55 2017 +0000
@@ -7,7 +7,7 @@
\section*{Coursework 6 (Scala)}
This coursework is about Scala and is worth 10\%. The first and second
-part are due on 16 November at 11pm, and the third part on 23 November
+part are due on 16 November at 11pm, and the third part on ??? November
at 11pm. You are asked to implement three programs about list
processing and recursion. The third part is more advanced and might
include material you have not yet seen in the first lecture.
@@ -19,7 +19,7 @@
submissions! They are not needed. This means you cannot use
\texttt{ListBuffer}s, for example. Do not use \texttt{return} in your
code! It has a different meaning in Scala, than in Java.
-Do not use \texttt{var}! This declares a mutable variable. Make sure the
+Do not use \texttt{var}! This declares a mutable variable. ??? Make sure the
functions you submit are defined on the ``top-level'' of Scala, not
inside a class or object. Also note that the running time of
each part will be restricted to a maximum of 360 seconds on my laptop.
Binary file handouts/pep-ho.pdf has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/handouts/pep-ho.tex Thu Nov 02 14:47:55 2017 +0000
@@ -0,0 +1,836 @@
+\documentclass{article}
+\usepackage{../style}
+\usepackage{../langs}
+\usepackage{marvosym}
+
+%cheat sheet
+%http://worldline.github.io/scala-cheatsheet/
+
+\begin{document}
+
+\section*{A Crash-Course on Scala}
+
+\subsection*{The Very Basics}
+
+One advantage of Scala over Java is that it includes an interpreter (a
+REPL, or
+\underline{R}ead-\underline{E}val-\underline{P}rint-\underline{L}oop)
+with which you can run and test small code-snippets without the need
+of a compiler. This helps a lot with interactively developing
+programs. Once you installed Scala, you can start the interpreter by
+typing on the command line:
+
+\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
+$ scala
+Welcome to Scala 2.12.4 (Java HotSpot(TM) 64-Bit Server VM, Java 9).
+Type in expressions for evaluation. Or try :help.
+
+scala>
+\end{lstlisting}%$
+
+\noindent The precise response may vary depending
+on the version and platform where you installed Scala. At the Scala
+prompt you can type things like \code{2 + 3}\;\keys{Ret} and
+the output will be
+
+\begin{lstlisting}[numbers=none]
+scala> 2 + 3
+res0: Int = 5
+\end{lstlisting}
+
+\noindent indicating that the result of the addition is of
+type \code{Int} and the actual result is 5. Another classic
+example you can try out is
+
+\begin{lstlisting}[numbers=none]
+scala> print("hello world")
+hello world
+\end{lstlisting}
+
+\noindent Note that in this case there is no result. The
+reason is that \code{print} does not actually produce a result
+(there is no \code{resXX} and no type), rather it is a
+function that causes the \emph{side-effect} of printing out a
+string. Once you are more familiar with the functional
+programming-style, you will know what the difference is
+between a function that returns a result, like addition, and a
+function that causes a side-effect, like \code{print}. We
+shall come back to this point later, but if you are curious
+now, the latter kind of functions always has \code{Unit} as
+return type.
+
+You can try more examples with the Scala interpreter, but try
+first to guess what the result is (not all answers by Scala are obvious):
+
+\begin{lstlisting}[numbers=none]
+scala> 2 + 2
+scala> 1 / 2
+scala> 1.0 / 2
+scala> 1 / 2.0
+scala> 1 / 0
+scala> 1.0 / 0.0
+scala> true == false
+scala> true && false
+scala> 1 > 1.0
+scala> "12345".length
+\end{lstlisting}
+
+\subsection*{Stand-Alone Apps}
+
+If you want to write a stand-alone app in Scala, you can
+implement an object that is an instance of \code{App}, say
+
+\begin{lstlisting}[numbers=none]
+object Hello extends App {
+ println("hello world")
+}
+\end{lstlisting}
+
+\noindent save it in a file, say {\tt hello-world.scala}, and
+then run the compiler and runtime environment:
+
+\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
+$ scalac hello-world.scala
+$ scala Hello
+hello world
+\end{lstlisting}
+
+Like Java, Scala targets the JVM and consequently
+Scala programs can also be executed by the bog-standard Java
+Runtime. This only requires the inclusion of {\tt
+scala-library.jar}, which on my computer can be done as
+follows:
+
+\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
+$ scalac hello-world.scala
+$ java -cp /usr/local/src/scala/lib/scala-library.jar:. Hello
+hello world
+\end{lstlisting}
+
+\noindent You might need to adapt the path to where you have
+installed Scala.
+
+\subsection*{Values}
+
+In the lectures, I will try as much as possible to avoid the term
+\emph{variables} familiar from other programming languages. Scala
+has \emph{values}, which can be seen as abbreviations of larger
+expressions. For example
+
+\begin{lstlisting}[numbers=none]
+scala> val x = 42
+x: Int = 42
+
+scala> val y = 3 + 4
+y: Int = 7
+
+scala> val z = x / y
+z: Int = 6
+\end{lstlisting}
+
+\noindent
+Why the kerfuffle about values? Well, values are \emph{immutable}. You cannot
+change their value after you defined them. If you try to reassign, say,
+\code{z}, Scala will yell at you:
+
+\begin{lstlisting}[numbers=none]
+scala> z = 9
+error: reassignment to val
+ z = 9
+ ^
+\end{lstlisting}
+
+\noindent
+So it would be a bit absurd to call values as variables...you cannot
+change them. You might think you can re-assign them like
+
+\begin{lstlisting}[numbers=none]
+scala> val x = 42
+scala> val z = x / 7
+scala> val x = 70
+scala> println(z)
+\end{lstlisting}
+
+\noindent but try to guess what Scala will print out in the code above
+for \code{z}? Will it be \code{6} or \code{10}? A final word about
+values: Try to stick to the convention that names of values should be
+lower case, like \code{x}, \code{y}, \code{foo41} and so on.
+
+
+\subsection*{Function Definitions}
+
+A function \code{f} taking a single argument of type \code{Int} can be defined
+as follows:
+
+\begin{lstlisting}[numbers=none]
+def f(x: Int) : String = EXPR
+\end{lstlisting}
+
+\noindent
+It returns the value resulting from evaluating the expression
+\code{EXPR} (whatever is substituted for this). The result will be
+of type \code{String}. Simple examples of Scala functions are:
+
+\begin{lstlisting}[numbers=none]
+def incr(x: Int) : Int = x + 1
+def double(x: Int) : Int = x + x
+def square(x: Int) : Int = x * x
+\end{lstlisting}
+
+\noindent
+The general scheme for a function is
+
+\begin{lstlisting}[numbers=none]
+def fname(arg1: ty1, arg2: ty2,..., argn: tyn): rty = {
+ BODY
+}
+\end{lstlisting}
+
+\noindent
+where each argument requires its type and the result type of the
+function, \code{rty}, shoudl be given. If the body of the function
+is more complex, then it can be enclosed in braces; it it is just a
+simple expression, like \code{x + 1}, you can omit the braces. Very
+often functions are recursive (call themselves) like
+
+\begin{lstlisting}[numbers=none]
+def fact(n: Int): Int =
+ if (n == 0) 1 else n * fact(n - 1)
+\end{lstlisting}
+
+\subsection*{Loops, or better the Absence thereof}
+
+Coming from Java or 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
+build the list of squares. The list of numbers from 1 to 8
+can be constructed in Scala as follows:
+
+\begin{lstlisting}[numbers=none]
+scala> (1 to 8).toList
+res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)
+\end{lstlisting}
+
+\noindent Generating from this list, the list of squares in a
+programming language such as Java, you would assume the list
+is given as a kind of array. You would then iterate, or loop,
+an index over this array and replace each entry in the array
+by the square. Right? In Scala, and in other functional
+programming languages, you use maps to achieve the same.
+
+A map essentially takes a function that describes how each
+element is transformed (for example squared) and a list over
+which this function should work. There are two forms to
+express such maps in Scala. The first way is called a
+\emph{for-comprehension}. Squaring the numbers from 1 to 8
+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 The important keywords are \code{for} and
+\code{yield}. This for-comprehension roughly states that from
+the list of numbers we draw \code{n}s and compute the result
+of \code{n * n}. As you can see, we specified the list where
+each \code{n} comes from, namely \code{(1 to 8).toList}, and
+how each element needs to be transformed. This can also be
+expressed in a second way in Scala by using directly
+\code{map}s as follows:
+
+\begin{lstlisting}[numbers=none]
+scala> (1 to 8).toList.map(n => n * n)
+res3 = List(1, 4, 9, 16, 25, 36, 49, 64)
+\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). This expression for functions
+might remind you of your lessons about the lambda-calculus
+where this would have been written as $\lambda n.\,n * n$. It
+might not be obvious, but for-comprehensions are just
+syntactic sugar: when compiling, 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 as lists, sets, vectors, options and so on.
+For example if we instead compute the reminders modulo 3 of
+this list, we can write
+
+\begin{lstlisting}[numbers=none]
+scala> (1 to 8).toList.map(n => n % 3)
+res4 = List(1, 2, 0, 1, 2, 0, 1, 2)
+\end{lstlisting}
+
+\noindent If we, however, transform the numbers 1 to 8 not
+into a list, but into a set, and then compute the reminders
+modulo 3 we obtain
+
+\begin{lstlisting}[numbers=none]
+scala> (1 to 8).toSet[Int].map(n => n % 3)
+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
+
+\begin{lstlisting}[numbers=none]
+scala> for (n <- (1 to 8).toSet[Int]) yield n % 3
+res5 = Set(2, 1, 0)
+\end{lstlisting}
+
+For-comprehensions can also be nested and the selection of
+elements can be guarded. For example if we want to pair up
+the numbers 1 to 4 with the letters a to c, we can write
+
+\begin{lstlisting}[numbers=none]
+scala> for (n <- (1 to 4).toList;
+ m <- ('a' to 'c').toList) yield (n, m)
+res6 = List((1,a), (1,b), (1,c), (2,a), (2,b), (2,c),
+ (3,a), (3,b), (3,c), (4,a), (4,b), (4,c))
+\end{lstlisting}
+
+\noindent
+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 the for-comprehension
+filters out all pairs where the sum is not even.
+
+While hopefully this all 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
+reminders modulo 3). What happens if we just want to print out
+a list of integers? Then actually the for-comprehension
+needs to be modified. The reason is that \code{print}, you
+guessed it, does not produce any result, but only produces
+what is in the functional-programming-lingo called a
+side-effect. Printing out the list of numbers from 1 to 5
+would look as follows
+
+\begin{lstlisting}[numbers=none]
+scala> for (n <- (1 to 5).toList) print(n)
+12345
+\end{lstlisting}
+
+\noindent
+where you need to omit the keyword \code{yield}. You can
+also do more elaborate calculations such as
+
+\begin{lstlisting}[numbers=none]
+scala> for (n <- (1 to 5).toList) {
+ val square_n = n * n
+ println(s"$n * $n = $square_n")
+}
+1 * 1 = 1
+2 * 2 = 4
+3 * 3 = 9
+4 * 4 = 16
+5 * 5 = 25
+\end{lstlisting}%$
+
+\noindent In this code I use a variable assignment (\code{val
+square_n = ...} ) 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
+integer values \code{n} and \code{square\_n} inside a string.
+This is very convenient for printing out ``things''.
+
+The corresponding map construction for functions with
+side-effects is in Scala called \code{foreach}. So you
+could also write
+
+
+\begin{lstlisting}[numbers=none]
+scala> (1 to 5).toList.foreach(n => print(n))
+12345
+\end{lstlisting}
+
+
+\noindent or even just
+
+\begin{lstlisting}[numbers=none]
+scala> (1 to 5).toList.foreach(print)
+12345
+\end{lstlisting}
+
+\noindent Again I hope this reminds you a bit of your
+lambda-calculus lessons, where an explanation is given why
+both forms produce the same result.
+
+
+If you want to find out more about maps and functions with
+side-effects, you can ponder about the response Scala gives if
+you replace \code{foreach} by \code{map} in the expression
+above. Scala will still allow \code{map} with side-effect
+functions, but then reacts with a slightly interesting result.
+
+\subsection*{Types}
+
+In most functional programming languages, types play an
+important role. Scala is such a language. You have already
+seen built-in types, like \code{Int}, \code{Boolean},
+\code{String} and \code{BigInt}, but also user-defined ones,
+like \code{Rexp}. Unfortunately, types can be a thorny
+subject, especially in Scala. For example, why do we need to
+give the type to \code{toSet[Int]}, but not to \code{toList}?
+The reason is the power of Scala, which sometimes means it
+cannot infer all necessary typing information. At the
+beginning while getting familiar with Scala, I recommend a
+``play-it-by-ear-approach'' to types. Fully understanding
+type-systems, especially complicated ones like in Scala, can
+take a module on their own.\footnote{Still, such a study can
+be a rewarding training: If you are in the business of
+designing new programming languages, you will not be able to
+turn a blind eye to types. They essentially help programmers
+to avoid common programming errors and help with maintaining
+code.}
+
+In Scala, types are needed whenever you define an inductive
+datatype and also whenever you define functions (their
+arguments and their results need a type). Base types are types
+that do not take any (type)arguments, for example \code{Int}
+and \code{String}. Compound types take one or more arguments,
+which as seen earlier need to be given in angle-brackets, for
+example \code{List[Int]} or \code{Set[List[String]]} or
+\code{Map[Int, Int]}.
+
+There are a few special type-constructors that fall outside
+this pattern. One is for tuples, where the type is written
+with parentheses. For example
+
+\begin{lstlisting}[ numbers=none]
+(Int, Int, String)
+\end{lstlisting}
+
+\noindent is for a triple (a tuple with three components---two
+integers and a string). Tuples are helpful if you want to
+define functions with multiple results, say the function
+returning the quotient and reminder of two numbers. For this
+you might define:
+
+
+\begin{lstlisting}[ numbers=none]
+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)}.
+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
+
+\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
+
+\begin{lstlisting}[numbers=none]
+def mk_string(n: Int) : String = n match {
+ case 0 => "zero"
+ case 1 => "one"
+ case 2 => "two"
+ case _ => "many"
+}
+\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
+
+\begin{quote}
+\url{http://www.scala-lang.org/api/current/}
+\end{quote}
+
+The function arrow can also be iterated, as in
+\code{Int => String => Boolean}. This is the type for a function
+taking an integer as first argument and a string as second,
+and the result of the function is a boolean. Though silly, a
+function of this type would be
+
+
+\begin{lstlisting}[numbers=none]
+def chk_string(n: Int)(s: String) : Boolean =
+ mk_string(n) == s
+\end{lstlisting}
+
+
+\noindent which checks whether the integer \code{n}
+corresponds to the name \code{s} given by the function
+\code{mk\_string}. Notice the unusual way of specifying the
+arguments of this function: the arguments are given one after
+the other, instead of being in a pair (what would be the type
+of this function then?). This way of specifying the arguments
+can be useful, for example in situations like this
+
+\begin{lstlisting}[numbers=none]
+scala> List("one", "two", "three", "many").map(chk_string(2))
+res4 = List(false, true, false, false)
+
+scala> List("one", "two", "three", "many").map(chk_string(3))
+res5 = List(false, false, false, true)
+\end{lstlisting}
+
+\noindent In each case we can give to \code{map} a specialised
+version of \code{chk_string}---once specialised to 2 and once
+to 3. This kind of ``specialising'' a function is called
+\emph{partial application}---we have not yet given to this
+function all arguments it needs, but only some of them.
+
+Coming back to the type \code{Int => String => Boolean}. The
+rule about such function types is that the right-most type
+specifies what the function returns (a boolean in this case).
+The types before that specify how many arguments the function
+expects and what their type is (in this case two arguments,
+one of type \code{Int} and another of type \code{String}).
+Given this rule, what kind of function has type
+\mbox{\code{(Int => String) => Boolean}}? Well, it returns a
+boolean. More interestingly, though, it only takes a single
+argument (because of the parentheses). The single argument
+happens to be another function (taking an integer as input and
+returning a string). Remember that \code{mk_string} is just
+such a function. So how can we use it? For this define
+the somewhat silly function \code{apply_3}:
+
+\begin{lstlisting}[numbers=none]
+def apply_3(f: Int => String): Bool = f(3) == "many"
+
+scala> apply_3(mk_string)
+res6 = true
+\end{lstlisting}
+
+You might ask: Apart from silly functions like above, what is
+the point of having functions as input arguments to other
+functions? In Java there is indeed no need of this kind of
+feature: at least in the past it did not allow such
+constructions. I think, the point of Java 8 is 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
+\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
+numbers are printed.
+
+
+\begin{lstlisting}[numbers=none]
+scala> (1 to 5).toList.foreach(print)
+12345
+scala> (1 to 5).toList.foreach(println)
+1
+2
+3
+4
+5
+\end{lstlisting}
+
+
+\noindent This is actually one of the main design principles
+in functional programming. You have generic functions like
+\code{map} and \code{foreach} that can traverse data containers,
+like lists or sets. They then take a function to specify what
+should be done with each element during the traversal. This
+requires that the generic traversal functions can cope with
+any kind of function (not just functions that, for example,
+take as input an integer and produce a string like above).
+This means we cannot fix the type of the generic traversal
+functions, but have to keep them
+\emph{polymorphic}.\footnote{Another interestic 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}.
+
+
+\subsection*{Cool Stuff}
+
+The first wow-moment I had with Scala was when I came across
+the following code-snippet for reading a web-page.
+
+
+\begin{lstlisting}[ numbers=none]
+import io.Source
+val url = """http://www.inf.kcl.ac.uk/staff/urbanc/"""
+Source.fromURL(url)("ISO-8859-1").take(10000).mkString
+\end{lstlisting}
+
+
+\noindent These three lines return a string containing the
+HTML-code of my webpage. It actually already does something
+more sophisticated, namely only returns the first 10000
+characters of a webpage in case it is too large. Why is that
+code-snippet of any interest? Well, try implementing
+reading-from-a-webpage in Java. I also like the possibility of
+triple-quoting strings, which I have only seen in Scala so
+far. The idea behind this is that in such a string all
+characters are interpreted literally---there are no escaped
+characters, like \verb|\n| for newlines.
+
+My second wow-moment I had with a feature of Scala that other
+functional programming languages do not have. This feature is
+about implicit type conversions. If you have regular
+expressions and want to use them for language processing you
+often want to recognise keywords in a language, for example
+\code{for},{} \code{if},{} \code{yield} and so on. But the
+basic regular expression \code{CHAR} can only recognise a
+single character. In order to recognise a whole string, like
+\code{for}, you have to put many of those together using
+\code{SEQ}:
+
+
+\begin{lstlisting}[numbers=none]
+SEQ(CHAR('f'), SEQ(CHAR('o'), CHAR('r')))
+\end{lstlisting}
+
+\noindent This gets quickly unreadable when the strings and
+regular expressions get more complicated. In other functional
+programming languages, you can explicitly write a conversion
+function that takes a string, say \dq{\pcode{for}}, and
+generates the regular expression above. But then your code is
+littered with such conversion functions.
+
+In Scala you can do better by ``hiding'' the conversion
+functions. The keyword for doing this is \code{implicit} and
+it needs a built-in library called
+
+\begin{lstlisting}[numbers=none]
+scala.language.implicitConversions
+\end{lstlisting}
+
+\noindent
+Consider the code
+
+
+\begin{lstlisting}[language=Scala]
+import scala.language.implicitConversions
+
+def charlist2rexp(s: List[Char]) : Rexp = s match {
+ case Nil => EMPTY
+ case c::Nil => CHAR(c)
+ case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+
+implicit def string2rexp(s: String) : Rexp =
+ charlist2rexp(s.toList)
+\end{lstlisting}
+
+
+\noindent where the first seven lines implement a function
+that given a list of characters generates the corresponding
+regular expression. In Lines 9 and 10, this function is used
+for transforming a string into a regular expression. Since the
+\code{string2rexp}-function is declared as \code{implicit},
+the effect will be that whenever Scala expects a regular
+expression, but I only give it a string, it will automatically
+insert a call to the \code{string2rexp}-function. I can now
+write for example
+
+\begin{lstlisting}[numbers=none]
+scala> ALT("ab", "ac")
+res9 = ALT(SEQ(CHAR(a),CHAR(b)),SEQ(CHAR(a),CHAR(c)))
+\end{lstlisting}
+
+\noindent Recall that \code{ALT} expects two regular
+expressions as arguments, but I only supply two strings. The
+implicit conversion function will transform the string into a
+regular expression.
+
+Using implicit definitions, Scala allows me to introduce
+some further syntactic sugar for regular expressions:
+
+
+\begin{lstlisting}[ numbers=none]
+implicit def RexpOps(r: Rexp) = new {
+ def | (s: Rexp) = ALT(r, s)
+ def ~ (s: Rexp) = SEQ(r, s)
+ def % = STAR(r)
+}
+
+implicit def stringOps(s: String) = new {
+ def | (r: Rexp) = ALT(s, r)
+ def | (r: String) = ALT(s, r)
+ def ~ (r: Rexp) = SEQ(s, r)
+ def ~ (r: String) = SEQ(s, r)
+ def % = STAR(s)
+}
+\end{lstlisting}
+
+
+\noindent This might seem a bit overly complicated, but its effect is
+that I can now write regular expressions such as $ab + ac$
+simply as
+
+
+\begin{lstlisting}[numbers=none]
+scala> "ab" | "ac"
+res10 = ALT(SEQ(CHAR(a),CHAR(b)),SEQ(CHAR(a),CHAR(c)))
+\end{lstlisting}
+
+
+\noindent I leave you to figure out what the other
+syntactic sugar in the code above stands for.
+
+One more useful feature of Scala is the ability to define
+functions with varying argument lists. This is a feature that
+is already present in old languages, like C, but seems to have
+been forgotten in the meantime---Java does not have it. In the
+context of regular expressions this feature comes in handy:
+Say you are fed up with writing many alternatives as
+
+
+\begin{lstlisting}[numbers=none]
+ALT(..., ALT(..., ALT(..., ...)))
+\end{lstlisting}
+
+
+\noindent To make it difficult, you do not know how deep such
+alternatives are nested. So you need something flexible that
+can take as many alternatives as needed. In Scala one can
+achieve this by adding a \code{*} to the type of an argument.
+Consider the code
+
+
+\begin{lstlisting}[language=Scala]
+def Alts(rs: List[Rexp]) : Rexp = rs match {
+ case Nil => NULL
+ case r::Nil => r
+ case r::rs => ALT(r, Alts(rs))
+}
+
+def ALTS(rs: Rexp*) = Alts(rs.toList)
+\end{lstlisting}
+
+
+\noindent The function in Lines 1 to 5 takes a list of regular
+expressions and converts it into an appropriate alternative
+regular expression. In Line 7 there is a wrapper for this
+function which uses the feature of varying argument lists. The
+effect of this code is that I can write the regular
+expression for keywords as
+
+
+\begin{lstlisting}[numbers=none]
+ALTS("for", "def", "yield", "implicit", "if", "match", "case")
+\end{lstlisting}
+
+
+\noindent Again I leave it to you to find out how much this
+simplifies the regular expression in comparison with if I had
+to write this by hand using only the ``plain'' regular
+expressions from the inductive datatype.
+
+\subsection*{More Info}
+
+There is much more to Scala than I can possibly describe in
+this document. Fortunately there are a number of free books
+about Scala and of course lots of help online. For example
+
+\begin{itemize}
+\item \url{http://www.scala-lang.org/docu/files/ScalaByExample.pdf}
+\item \url{http://www.scala-lang.org/docu/files/ScalaTutorial.pdf}
+\item \url{https://www.youtube.com/user/ShadowofCatron}
+\item \url{http://docs.scala-lang.org/tutorials}
+\item \url{https://www.scala-exercises.org}
+\end{itemize}
+
+\noindent There is also a course at Coursera on Functional
+Programming Principles in Scala by Martin Odersky, the main
+developer of the Scala language. And a document that explains
+Scala for Java programmers
+
+\begin{itemize}
+\item \small\url{http://docs.scala-lang.org/tutorials/scala-for-java-programmers.html}
+\end{itemize}
+
+While I am quite enthusiastic about Scala, I am also happy to
+admit that it has more than its fair share of faults. The
+problem seen earlier of having to give an explicit type to
+\code{toSet}, but not \code{toList} is one of them. There are
+also many ``deep'' ideas about types in Scala, which even to
+me as seasoned functional programmer are puzzling. Whilst
+implicits are great, they can also be a source of great
+headaches, for example consider the code:
+
+\begin{lstlisting}[numbers=none]
+scala> List (1, 2, 3) contains "your mom"
+res1: Boolean = false
+\end{lstlisting}
+
+\noindent Rather than returning \code{false}, this code should
+throw a typing-error. There are also many limitations Scala
+inherited from the JVM that can be really annoying. For
+example a fixed stack size. One can work around this
+particular limitation, but why does one have to?
+More such `puzzles' can be found at
+
+\begin{center}
+ \url{http://scalapuzzlers.com} and
+ \url{http://latkin.org/blog/2017/05/02/when-the-scala-compiler-doesnt-help/}
+\end{center}
+
+Even if Scala has been a success in several high-profile
+companies, there is also a company (Yammer) that first used
+Scala in their production code, but then moved away from it.
+Allegedly they did not like the steep learning curve of Scala
+and also that new versions of Scala often introduced
+incompatibilities in old code. In the past two months
+there have also been two forks of the Scala compiler.
+It needs to be seen what the future brings for Scala.
+
+So all in all, Scala might not be a great teaching language,
+but I hope this is mitigated by the fact that I never require
+you to write any Scala code. You only need to be able to read
+it. In the coursework you can use any programming language you
+like. If you want to use Scala for this, then be my guest; if
+you do not want, stick with the language you are most familiar
+with.
+
+
+
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
Binary file handouts/scala-ho.pdf has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/handouts/scala-ho.tex Thu Nov 02 14:47:55 2017 +0000
@@ -0,0 +1,1016 @@
+\documentclass{article}
+\usepackage{../style}
+\usepackage{../langs}
+\usepackage{marvosym}
+
+%cheat sheet
+%http://worldline.github.io/scala-cheatsheet/
+
+\begin{document}
+
+\section*{A Crash-Course on Scala}
+
+Scala is a programming language that combines functional and
+object-oriented programming-styles. It has received quite a
+bit of attention in the last five years or so. One reason for
+this attention is that, like the Java programming language,
+Scala compiles to the Java Virtual Machine (JVM) and therefore
+Scala programs can run under MacOSX, Linux and
+Windows.\footnote{There are also experimental backends for
+Android and JavaScript; and also work is under way to have a
+native compiler, see \url{https://github.com/scala-native/scala-native}.} Unlike Java, however, Scala often
+allows programmers to write very concise and elegant code.
+Some therefore say: Scala is the much better Java. A number of
+companies, The Guardian, Twitter, Coursera, FourSquare,
+LinkedIn to name a few, either use Scala exclusively in
+production code, or at least to some substantial degree. It
+also seems to be useful in job-interviews (in Data Science)
+according to this annectotical report
+
+\begin{quote}
+\url{https://techcrunch.com/2016/06/14/scala-is-the-new-golden-child/}
+\end{quote}
+
+\noindent
+If you want to try out Scala yourself, the official Scala compiler can be
+downloaded from
+
+\begin{quote}
+\url{http://www.scala-lang.org}
+\end{quote}
+
+\noindent
+A ready-made bundle with the Eclipse IDE is at
+
+\begin{quote}
+\url{http://scala-ide.org/download/sdk.html}
+\end{quote}
+
+Why do I use Scala in the AFL module? Actually, you can do
+\emph{any} part of the coursework in \emph{any} programming
+language you like. I use Scala for showing you code during the
+lectures because its functional programming-style allows me to
+implement the functions we will discuss with very small
+code-snippets. If I had to do this in Java, I would first have
+to go through heaps of boilerplate code and the code-snippets
+would not look pretty. Since the Scala compiler is free, you
+can download the code-snippets and run every example I give.
+But if you prefer, you can also easily translate them into any
+other functional language, for example Haskell, Swift,
+Standard ML, F$^\#$, Ocaml and so on.
+
+Developing programs in Scala can be done with the Eclipse IDE
+and also with the IntelliJ IDE, but for the small programs I will
+develop the good old Emacs-editor is adequate for me and I
+will run the programs on the command line. One advantage of
+Scala over Java is that it includes an interpreter (a REPL, or
+\underline{R}ead-\underline{E}val-\underline{P}rint-\underline{L}oop)
+with which you can run and test small code-snippets without
+the need of the compiler. This helps a lot with interactively
+developing programs. Once you installed Scala, you can start
+the interpreter by typing on the command line:
+
+\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
+$ scala
+Welcome to Scala version 2.11.8 (Java HotSpot(TM) 64-Bit Server VM).
+Type in expressions for evaluation. Or try :help.
+
+scala>
+\end{lstlisting}
+
+\noindent Of course the precise response may vary due to the
+version and platform where you installed Scala. At the Scala
+prompt you can type things like \code{2 + 3} \keys{Ret} and
+the output will be
+
+\begin{lstlisting}[numbers=none]
+scala> 2 + 3
+res0: Int = 5
+\end{lstlisting}
+
+\noindent indicating that the result of the addition is of
+type \code{Int} and the actual result is 5. Another classic
+example you can try out is
+
+\begin{lstlisting}[numbers=none]
+scala> print("hello world")
+hello world
+\end{lstlisting}
+
+\noindent Note that in this case there is no result. The
+reason is that \code{print} does not actually produce a result
+(there is no \code{resXX} and no type), rather it is a
+function that causes the \emph{side-effect} of printing out a
+string. Once you are more familiar with the functional
+programming-style, you will know what the difference is
+between a function that returns a result, like addition, and a
+function that causes a side-effect, like \code{print}. We
+shall come back to this point later, but if you are curious
+now, the latter kind of functions always has \code{Unit} as
+return type.
+
+If you want to write a stand-alone app in Scala, you can
+implement an object that is an instance of \code{App}, say
+
+\begin{lstlisting}[numbers=none]
+object Hello extends App {
+ println("hello world")
+}
+\end{lstlisting}
+
+\noindent save it in a file, say {\tt hello-world.scala}, and
+then run the compiler and runtime environment:
+
+\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
+$ scalac hello-world.scala
+$ scala Hello
+hello world
+\end{lstlisting}
+
+As mentioned above, Scala targets the JVM and consequently
+Scala programs can also be executed by the bog-standard Java
+Runtime. This only requires the inclusion of {\tt
+scala-library.jar}, which on my computer can be done as
+follows:
+
+\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
+$ scalac hello-world.scala
+$ java -cp /usr/local/src/scala/lib/scala-library.jar:. Hello
+hello world
+\end{lstlisting}
+
+\noindent You might need to adapt the path to where you have
+installed Scala.
+
+\subsection*{Inductive Datatypes}
+
+The elegance and conciseness of Scala programs are often a
+result of inductive datatypes that can be easily defined in
+Scala. For example in ``every-day mathematics'' we define
+regular expressions simply by giving the grammar
+
+\begin{center}
+\begin{tabular}{r@{\hspace{2mm}}r@{\hspace{2mm}}l@{\hspace{13mm}}l}
+ $r$ & $::=$ & $\ZERO$ & null\\
+ & $\mid$ & $\ONE$ & empty string\\
+ & $\mid$ & $c$ & single character\\
+ & $\mid$ & $r_1 \cdot r_2$ & sequence\\
+ & $\mid$ & $r_1 + r_2$ & alternative / choice\\
+ & $\mid$ & $r^\star$ & star (zero or more)\\
+ \end{tabular}
+\end{center}
+
+\noindent This grammar specifies what regular expressions are
+(essentially a kind of tree-structure with three kinds of
+inner nodes---sequence, alternative and star---and three kinds
+of leave nodes---null, empty and character). If you are
+familiar with Java, it might be an instructive exercise to
+define this kind of inductive datatypes in Java\footnote{Happy
+programming! \Smiley} and then compare it with how it can be
+implemented in Scala.
+
+Implementing the regular expressions from above in Scala is
+actually very simple: It first requires an \emph{abstract
+class}, say, \code{Rexp}. This will act as the type for
+regular expressions. Second, it requires a case for each
+clause in the grammar. The cases for $\ZERO$ and $\ONE$ do not
+have any arguments, while in all the other cases we do have
+arguments. For example the character regular expression needs
+to take as an argument the character it is supposed to
+recognise. In Scala, the cases without arguments are called
+\emph{case objects}, whereas the ones with arguments are
+\emph{case classes}. The corresponding Scala code is as
+follows:
+
+\begin{lstlisting}[numbers=none]
+abstract class Rexp
+case object ZERO extends Rexp
+case object ONE extends Rexp
+case class CHAR (c: Char) extends Rexp
+case class SEQ (r1: Rexp, r2: Rexp) extends Rexp
+case class ALT (r1: Rexp, r2: Rexp) extends Rexp
+case class STAR (r: Rexp) extends Rexp
+\end{lstlisting}
+
+\noindent In order to be an instance of \code{Rexp}, each case
+object and case class needs to extend \code{Rexp}. Given the
+grammar above, I hope you can see the underlying pattern. If
+you want to play further with such definitions of inductive
+datatypes, feel free to define for example binary trees.
+
+Once you make a definition like the one above in Scala, you
+can represent the regular expression for $a + b$, for example,
+as \code{ALT(CHAR('a'), CHAR('b'))}. Expressions such as
+\code{'a'} stand for ASCII characters, though in the output
+syntax, as you can see below, the quotes are omitted. In a
+later section we will see how we can support the more
+mathematical infix notation for regular expression operators
+in Scala. If you want to assign this regular expression to a
+variable, you can use the keyword \code{val} and type
+
+\begin{lstlisting}[numbers=none]
+scala> val r = ALT(CHAR('a'), CHAR('b'))
+r: ALT = ALT(CHAR(a),CHAR(b))
+\end{lstlisting}
+
+\noindent As you can see, in order to make such assignments,
+no \code{new} or constructor is required in the class (as in
+Java). However, if there is the need for some non-standard
+initialisation, you can of course define such a constructor in
+Scala too. But we omit such ``tricks'' here.
+
+Note that Scala in its response says the variable \code{r} is
+of type \code{ALT}, not \code{Rexp}. This might be a bit
+unexpected, but can be explained as follows: Scala always
+tries to find the most general type that is needed for a
+variable or expression, but does not ``over-generalise''. In
+our definition the type \code{Rexp} is more general than
+\code{ALT}, since it is the abstract class for all regular
+expressions. But in this particular case there is no need to
+give \code{r} the more general type of \code{Rexp}. This is
+different if you want to form a list of regular expressions,
+for example
+
+\begin{lstlisting}[numbers=none]
+scala> val ls = List(ALT(CHAR('a'), CHAR('b')), ZERO)
+ls: List[Rexp] = List(ALT(CHAR(a),CHAR(b)), ZERO)
+\end{lstlisting}
+
+\noindent In this case, Scala needs to assign a common type to
+the regular expressions so that it is compatible with the
+fact that lists can only contain elements of a single type. In
+this case the first common type is \code{Rexp}.\footnote{If you
+type in this example, you will notice that the type contains
+some further information, but let us ignore this for the
+moment.}
+
+For compound types like \code{List[...]}, the general rule is
+that when a type takes another type as argument, then this
+argument type is written in angle-brackets. This can also
+contain nested types as in \code{List[Set[Rexp]]}, which is a
+list of sets each of which contains regular expressions.
+
+\subsection*{Functions and Pattern-Matching}
+
+I mentioned above that Scala is a very elegant programming
+language for the code we will write in this module. This
+elegance mainly stems from the fact that in addition to
+inductive datatypes, also functions can be implemented very
+easily in Scala. To show you this, let us first consider a
+problem from number theory, called the \emph{Collatz-series},
+which corresponds to a famous unsolved problem in
+mathematics.\footnote{See for example
+\url{http://mathworld.wolfram.com/CollatzProblem.html}.}
+Mathematicians define this series as:
+
+\[
+collatz_{n + 1} \dn
+\begin{cases}
+\frac{1}{2} * collatz_n & \text{if $collatz_n$ is even}\\
+3 * collatz_n + 1 & \text{if $collatz_n$ is odd}
+\end{cases}
+\]
+
+\noindent The famous unsolved question is whether this
+series started with any $n > 0$ as $collatz_0$ will always
+return to $1$. This is obvious when started with $1$, and also
+with $2$, but already needs a bit of head-scratching for the
+case of $3$.
+
+If we want to avoid the head-scratching, we could implement
+this as the following function in Scala:
+
+\lstinputlisting[numbers=none]{../progs/collatz.scala}
+
+\noindent The keyword for function definitions is \code{def}
+followed by the name of the function. After that you have a
+list of arguments (enclosed in parentheses and separated by
+commas). Each argument in this list needs its type to be
+annotated. In this case we only have one argument, which is of
+type \code{BigInt}. This type stands in Scala for arbitrary
+precision integers (in case you want to try out the function
+on really big numbers). After the arguments comes the type of
+what the function returns---a Boolean in this case for
+indicating that the function has reached 1. Finally, after the
+\code{=} comes the \emph{body} of the function implementing
+what the function is supposed to do. What the \code{collatz}
+function does should be pretty self-explanatory: the function
+first tests whether \code{n} is equal to 1 in which case it
+returns \code{true} and so on.
+
+Notice the quirk in Scala's syntax for \code{if}s: The condition
+needs to be enclosed in parentheses and the then-case comes
+right after the condition---there is no \code{then} keyword in
+Scala.
+
+The real power of Scala comes, however, from the ability to
+define functions by \emph{pattern matching}. In the
+\code{collatz} function above we need to test each case using a
+sequence of \code{if}s. This can be very cumbersome and brittle
+if there are many cases. If we wanted to define a function
+over regular expressions in Java, for example, which does not
+have pattern-matching, the resulting code would just be
+awkward.
+
+Mathematicians already use the power of pattern-matching when
+they define the function that takes a regular expression and
+produces another regular expression that can recognise the
+reversed strings. They define this function as follows:
+
+\begin{center}
+\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}
+$rev(\ZERO)$ & $\dn$ & $\ZERO$\\
+$rev(\ONE)$ & $\dn$ & $\ONE$\\
+$rev(c)$ & $\dn$ & $c$\\
+$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\
+$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
+$rev(r^*)$ & $\dn$ & $rev(r)^*$\\
+\end{tabular}
+\end{center}
+
+\noindent It is defined by recursion analysing each pattern of
+what the regular expression might look like. The corresponding
+Scala code looks very similar to this definition, thanks to
+pattern-matching.
+
+%%\lstinputlisting[language=Scala]{../progs/rev.scala}
+
+\noindent The keyword for starting a pattern-match is
+\code{match} followed by a list of \code{case}s. Before the
+match keyword can be another pattern, but often, as in the
+case above, it is just a variable you want to pattern-match
+(the \code{r} after \code{=} in Line 1).
+
+Each case in this definition follows the structure of how we
+defined regular expressions as inductive datatype. For example
+the case in Line 3 you can read as: if the regular expression
+\code{r} is of the form \code{EMPTY} then do whatever follows
+the \code{=>} (in this case just return \code{EMPTY}). Line 5
+reads as: if the regular expression \code{r} is of the form
+\code{ALT(r1, r2)}, where the left-branch of the alternative is
+matched by the variable \code{r1} and the right-branch by
+\code{r2} then do ``something''. The ``something'' can now use the
+variables \code{r1} and \code{r2} from the match.
+
+If you want to play with this function, call it for example
+with the regular expression $ab + ac$. This regular expression
+can recognise the strings $ab$ and $ac$. The function
+\code{rev} produces $ba + ca$, which can recognise the reversed
+strings $ba$ and $ca$.
+
+In Scala each pattern-match can also be guarded as in
+
+\begin{lstlisting}[ numbers=none]
+case Pattern if Condition => Do_Something
+\end{lstlisting}
+
+\noindent This allows us, for example, to re-write the
+\code{collatz}-function from above as follows:
+
+%%\lstinputlisting[language=Scala]{../progs/collatz2.scala}
+
+
+\noindent Although in this particular case the pattern-match
+does not improve the code in any way. In cases like
+\code{rev}, however, it is really crucial. The underscore in
+Line 4 indicates that we do not care what the pattern looks
+like. Thus this case acts like a default case whenever the
+cases above did not match. Cases are always tried out from top
+to bottom.
+
+\subsection*{Loops, or better the Absence thereof}
+
+Coming from Java or 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
+build the list of squares. The list of numbers from 1 to 8
+can be constructed in Scala as follows:
+
+\begin{lstlisting}[numbers=none]
+scala> (1 to 8).toList
+res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)
+\end{lstlisting}
+
+\noindent Generating from this list, the list of squares in a
+programming language such as Java, you would assume the list
+is given as a kind of array. You would then iterate, or loop,
+an index over this array and replace each entry in the array
+by the square. Right? In Scala, and in other functional
+programming languages, you use maps to achieve the same.
+
+A map essentially takes a function that describes how each
+element is transformed (for example squared) and a list over
+which this function should work. There are two forms to
+express such maps in Scala. The first way is called a
+\emph{for-comprehension}. Squaring the numbers from 1 to 8
+would look in this form 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 The important keywords are \code{for} and
+\code{yield}. This for-comprehension roughly states that from
+the list of numbers we draw \code{n}s and compute the result
+of \code{n * n}. As you can see, we specified the list where
+each \code{n} comes from, namely \code{(1 to 8).toList}, and
+how each element needs to be transformed. This can also be
+expressed in a second way in Scala by using directly
+\code{map}s as follows:
+
+\begin{lstlisting}[numbers=none]
+scala> (1 to 8).toList.map(n => n * n)
+res3 = List(1, 4, 9, 16, 25, 36, 49, 64)
+\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). This expression for functions
+might remind you of your lessons about the lambda-calculus
+where this would have been written as $\lambda n.\,n * n$. It
+might not be obvious, but for-comprehensions are just
+syntactic sugar: when compiling, 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 as lists, sets, vectors, options and so on.
+For example if we instead compute the reminders modulo 3 of
+this list, we can write
+
+\begin{lstlisting}[numbers=none]
+scala> (1 to 8).toList.map(n => n % 3)
+res4 = List(1, 2, 0, 1, 2, 0, 1, 2)
+\end{lstlisting}
+
+\noindent If we, however, transform the numbers 1 to 8 not
+into a list, but into a set, and then compute the reminders
+modulo 3 we obtain
+
+\begin{lstlisting}[numbers=none]
+scala> (1 to 8).toSet[Int].map(n => n % 3)
+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
+
+\begin{lstlisting}[numbers=none]
+scala> for (n <- (1 to 8).toSet[Int]) yield n % 3
+res5 = Set(2, 1, 0)
+\end{lstlisting}
+
+For-comprehensions can also be nested and the selection of
+elements can be guarded. For example if we want to pair up
+the numbers 1 to 4 with the letters a to c, we can write
+
+\begin{lstlisting}[numbers=none]
+scala> for (n <- (1 to 4).toList;
+ m <- ('a' to 'c').toList) yield (n, m)
+res6 = List((1,a), (1,b), (1,c), (2,a), (2,b), (2,c),
+ (3,a), (3,b), (3,c), (4,a), (4,b), (4,c))
+\end{lstlisting}
+
+\noindent
+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 the for-comprehension
+filters out all pairs where the sum is not even.
+
+While hopefully this all 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
+reminders modulo 3). What happens if we just want to print out
+a list of integers? Then actually the for-comprehension
+needs to be modified. The reason is that \code{print}, you
+guessed it, does not produce any result, but only produces
+what is in the functional-programming-lingo called a
+side-effect. Printing out the list of numbers from 1 to 5
+would look as follows
+
+\begin{lstlisting}[numbers=none]
+scala> for (n <- (1 to 5).toList) print(n)
+12345
+\end{lstlisting}
+
+\noindent
+where you need to omit the keyword \code{yield}. You can
+also do more elaborate calculations such as
+
+\begin{lstlisting}[numbers=none]
+scala> for (n <- (1 to 5).toList) {
+ val square_n = n * n
+ println(s"$n * $n = $square_n")
+}
+1 * 1 = 1
+2 * 2 = 4
+3 * 3 = 9
+4 * 4 = 16
+5 * 5 = 25
+\end{lstlisting}
+
+\noindent In this code I use a variable assignment (\code{val
+square_n = ...} ) 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
+integer values \code{n} and \code{square\_n} inside a string.
+This is very convenient for printing out ``things''.
+
+The corresponding map construction for functions with
+side-effects is in Scala called \code{foreach}. So you
+could also write
+
+
+\begin{lstlisting}[numbers=none]
+scala> (1 to 5).toList.foreach(n => print(n))
+12345
+\end{lstlisting}
+
+
+\noindent or even just
+
+\begin{lstlisting}[numbers=none]
+scala> (1 to 5).toList.foreach(print)
+12345
+\end{lstlisting}
+
+\noindent Again I hope this reminds you a bit of your
+lambda-calculus lessons, where an explanation is given why
+both forms produce the same result.
+
+
+If you want to find out more about maps and functions with
+side-effects, you can ponder about the response Scala gives if
+you replace \code{foreach} by \code{map} in the expression
+above. Scala will still allow \code{map} with side-effect
+functions, but then reacts with a slightly interesting result.
+
+\subsection*{Types}
+
+In most functional programming languages, types play an
+important role. Scala is such a language. You have already
+seen built-in types, like \code{Int}, \code{Boolean},
+\code{String} and \code{BigInt}, but also user-defined ones,
+like \code{Rexp}. Unfortunately, types can be a thorny
+subject, especially in Scala. For example, why do we need to
+give the type to \code{toSet[Int]}, but not to \code{toList}?
+The reason is the power of Scala, which sometimes means it
+cannot infer all necessary typing information. At the
+beginning while getting familiar with Scala, I recommend a
+``play-it-by-ear-approach'' to types. Fully understanding
+type-systems, especially complicated ones like in Scala, can
+take a module on their own.\footnote{Still, such a study can
+be a rewarding training: If you are in the business of
+designing new programming languages, you will not be able to
+turn a blind eye to types. They essentially help programmers
+to avoid common programming errors and help with maintaining
+code.}
+
+In Scala, types are needed whenever you define an inductive
+datatype and also whenever you define functions (their
+arguments and their results need a type). Base types are types
+that do not take any (type)arguments, for example \code{Int}
+and \code{String}. Compound types take one or more arguments,
+which as seen earlier need to be given in angle-brackets, for
+example \code{List[Int]} or \code{Set[List[String]]} or
+\code{Map[Int, Int]}.
+
+There are a few special type-constructors that fall outside
+this pattern. One is for tuples, where the type is written
+with parentheses. For example
+
+\begin{lstlisting}[ numbers=none]
+(Int, Int, String)
+\end{lstlisting}
+
+\noindent is for a triple (a tuple with three components---two
+integers and a string). Tuples are helpful if you want to
+define functions with multiple results, say the function
+returning the quotient and reminder of two numbers. For this
+you might define:
+
+
+\begin{lstlisting}[ numbers=none]
+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)}.
+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
+
+\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
+
+\begin{lstlisting}[numbers=none]
+def mk_string(n: Int) : String = n match {
+ case 0 => "zero"
+ case 1 => "one"
+ case 2 => "two"
+ case _ => "many"
+}
+\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
+
+\begin{quote}
+\url{http://www.scala-lang.org/api/current/}
+\end{quote}
+
+The function arrow can also be iterated, as in
+\code{Int => String => Boolean}. This is the type for a function
+taking an integer as first argument and a string as second,
+and the result of the function is a boolean. Though silly, a
+function of this type would be
+
+
+\begin{lstlisting}[numbers=none]
+def chk_string(n: Int)(s: String) : Boolean =
+ mk_string(n) == s
+\end{lstlisting}
+
+
+\noindent which checks whether the integer \code{n}
+corresponds to the name \code{s} given by the function
+\code{mk\_string}. Notice the unusual way of specifying the
+arguments of this function: the arguments are given one after
+the other, instead of being in a pair (what would be the type
+of this function then?). This way of specifying the arguments
+can be useful, for example in situations like this
+
+\begin{lstlisting}[numbers=none]
+scala> List("one", "two", "three", "many").map(chk_string(2))
+res4 = List(false, true, false, false)
+
+scala> List("one", "two", "three", "many").map(chk_string(3))
+res5 = List(false, false, false, true)
+\end{lstlisting}
+
+\noindent In each case we can give to \code{map} a specialised
+version of \code{chk_string}---once specialised to 2 and once
+to 3. This kind of ``specialising'' a function is called
+\emph{partial application}---we have not yet given to this
+function all arguments it needs, but only some of them.
+
+Coming back to the type \code{Int => String => Boolean}. The
+rule about such function types is that the right-most type
+specifies what the function returns (a boolean in this case).
+The types before that specify how many arguments the function
+expects and what their type is (in this case two arguments,
+one of type \code{Int} and another of type \code{String}).
+Given this rule, what kind of function has type
+\mbox{\code{(Int => String) => Boolean}}? Well, it returns a
+boolean. More interestingly, though, it only takes a single
+argument (because of the parentheses). The single argument
+happens to be another function (taking an integer as input and
+returning a string). Remember that \code{mk_string} is just
+such a function. So how can we use it? For this define
+the somewhat silly function \code{apply_3}:
+
+\begin{lstlisting}[numbers=none]
+def apply_3(f: Int => String): Bool = f(3) == "many"
+
+scala> apply_3(mk_string)
+res6 = true
+\end{lstlisting}
+
+You might ask: Apart from silly functions like above, what is
+the point of having functions as input arguments to other
+functions? In Java there is indeed no need of this kind of
+feature: at least in the past it did not allow such
+constructions. I think, the point of Java 8 is 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
+\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
+numbers are printed.
+
+
+\begin{lstlisting}[numbers=none]
+scala> (1 to 5).toList.foreach(print)
+12345
+scala> (1 to 5).toList.foreach(println)
+1
+2
+3
+4
+5
+\end{lstlisting}
+
+
+\noindent This is actually one of the main design principles
+in functional programming. You have generic functions like
+\code{map} and \code{foreach} that can traverse data containers,
+like lists or sets. They then take a function to specify what
+should be done with each element during the traversal. This
+requires that the generic traversal functions can cope with
+any kind of function (not just functions that, for example,
+take as input an integer and produce a string like above).
+This means we cannot fix the type of the generic traversal
+functions, but have to keep them
+\emph{polymorphic}.\footnote{Another interestic 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}.
+
+
+\subsection*{Cool Stuff}
+
+The first wow-moment I had with Scala was when I came across
+the following code-snippet for reading a web-page.
+
+
+\begin{lstlisting}[ numbers=none]
+import io.Source
+val url = """http://www.inf.kcl.ac.uk/staff/urbanc/"""
+Source.fromURL(url)("ISO-8859-1").take(10000).mkString
+\end{lstlisting}
+
+
+\noindent These three lines return a string containing the
+HTML-code of my webpage. It actually already does something
+more sophisticated, namely only returns the first 10000
+characters of a webpage in case it is too large. Why is that
+code-snippet of any interest? Well, try implementing
+reading-from-a-webpage in Java. I also like the possibility of
+triple-quoting strings, which I have only seen in Scala so
+far. The idea behind this is that in such a string all
+characters are interpreted literally---there are no escaped
+characters, like \verb|\n| for newlines.
+
+My second wow-moment I had with a feature of Scala that other
+functional programming languages do not have. This feature is
+about implicit type conversions. If you have regular
+expressions and want to use them for language processing you
+often want to recognise keywords in a language, for example
+\code{for},{} \code{if},{} \code{yield} and so on. But the
+basic regular expression \code{CHAR} can only recognise a
+single character. In order to recognise a whole string, like
+\code{for}, you have to put many of those together using
+\code{SEQ}:
+
+
+\begin{lstlisting}[numbers=none]
+SEQ(CHAR('f'), SEQ(CHAR('o'), CHAR('r')))
+\end{lstlisting}
+
+\noindent This gets quickly unreadable when the strings and
+regular expressions get more complicated. In other functional
+programming languages, you can explicitly write a conversion
+function that takes a string, say \dq{\pcode{for}}, and
+generates the regular expression above. But then your code is
+littered with such conversion functions.
+
+In Scala you can do better by ``hiding'' the conversion
+functions. The keyword for doing this is \code{implicit} and
+it needs a built-in library called
+
+\begin{lstlisting}[numbers=none]
+scala.language.implicitConversions
+\end{lstlisting}
+
+\noindent
+Consider the code
+
+
+\begin{lstlisting}[language=Scala]
+import scala.language.implicitConversions
+
+def charlist2rexp(s: List[Char]) : Rexp = s match {
+ case Nil => EMPTY
+ case c::Nil => CHAR(c)
+ case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+
+implicit def string2rexp(s: String) : Rexp =
+ charlist2rexp(s.toList)
+\end{lstlisting}
+
+
+\noindent where the first seven lines implement a function
+that given a list of characters generates the corresponding
+regular expression. In Lines 9 and 10, this function is used
+for transforming a string into a regular expression. Since the
+\code{string2rexp}-function is declared as \code{implicit},
+the effect will be that whenever Scala expects a regular
+expression, but I only give it a string, it will automatically
+insert a call to the \code{string2rexp}-function. I can now
+write for example
+
+\begin{lstlisting}[numbers=none]
+scala> ALT("ab", "ac")
+res9 = ALT(SEQ(CHAR(a),CHAR(b)),SEQ(CHAR(a),CHAR(c)))
+\end{lstlisting}
+
+\noindent Recall that \code{ALT} expects two regular
+expressions as arguments, but I only supply two strings. The
+implicit conversion function will transform the string into a
+regular expression.
+
+Using implicit definitions, Scala allows me to introduce
+some further syntactic sugar for regular expressions:
+
+
+\begin{lstlisting}[ numbers=none]
+implicit def RexpOps(r: Rexp) = new {
+ def | (s: Rexp) = ALT(r, s)
+ def ~ (s: Rexp) = SEQ(r, s)
+ def % = STAR(r)
+}
+
+implicit def stringOps(s: String) = new {
+ def | (r: Rexp) = ALT(s, r)
+ def | (r: String) = ALT(s, r)
+ def ~ (r: Rexp) = SEQ(s, r)
+ def ~ (r: String) = SEQ(s, r)
+ def % = STAR(s)
+}
+\end{lstlisting}
+
+
+\noindent This might seem a bit overly complicated, but its effect is
+that I can now write regular expressions such as $ab + ac$
+simply as
+
+
+\begin{lstlisting}[numbers=none]
+scala> "ab" | "ac"
+res10 = ALT(SEQ(CHAR(a),CHAR(b)),SEQ(CHAR(a),CHAR(c)))
+\end{lstlisting}
+
+
+\noindent I leave you to figure out what the other
+syntactic sugar in the code above stands for.
+
+One more useful feature of Scala is the ability to define
+functions with varying argument lists. This is a feature that
+is already present in old languages, like C, but seems to have
+been forgotten in the meantime---Java does not have it. In the
+context of regular expressions this feature comes in handy:
+Say you are fed up with writing many alternatives as
+
+
+\begin{lstlisting}[numbers=none]
+ALT(..., ALT(..., ALT(..., ...)))
+\end{lstlisting}
+
+
+\noindent To make it difficult, you do not know how deep such
+alternatives are nested. So you need something flexible that
+can take as many alternatives as needed. In Scala one can
+achieve this by adding a \code{*} to the type of an argument.
+Consider the code
+
+
+\begin{lstlisting}[language=Scala]
+def Alts(rs: List[Rexp]) : Rexp = rs match {
+ case Nil => NULL
+ case r::Nil => r
+ case r::rs => ALT(r, Alts(rs))
+}
+
+def ALTS(rs: Rexp*) = Alts(rs.toList)
+\end{lstlisting}
+
+
+\noindent The function in Lines 1 to 5 takes a list of regular
+expressions and converts it into an appropriate alternative
+regular expression. In Line 7 there is a wrapper for this
+function which uses the feature of varying argument lists. The
+effect of this code is that I can write the regular
+expression for keywords as
+
+
+\begin{lstlisting}[numbers=none]
+ALTS("for", "def", "yield", "implicit", "if", "match", "case")
+\end{lstlisting}
+
+
+\noindent Again I leave it to you to find out how much this
+simplifies the regular expression in comparison with if I had
+to write this by hand using only the ``plain'' regular
+expressions from the inductive datatype.
+
+\subsection*{More Info}
+
+There is much more to Scala than I can possibly describe in
+this document. Fortunately there are a number of free books
+about Scala and of course lots of help online. For example
+
+\begin{itemize}
+\item \url{http://www.scala-lang.org/docu/files/ScalaByExample.pdf}
+\item \url{http://www.scala-lang.org/docu/files/ScalaTutorial.pdf}
+\item \url{https://www.youtube.com/user/ShadowofCatron}
+\item \url{http://docs.scala-lang.org/tutorials}
+\item \url{https://www.scala-exercises.org}
+\end{itemize}
+
+\noindent There is also a course at Coursera on Functional
+Programming Principles in Scala by Martin Odersky, the main
+developer of the Scala language. And a document that explains
+Scala for Java programmers
+
+\begin{itemize}
+\item \small\url{http://docs.scala-lang.org/tutorials/scala-for-java-programmers.html}
+\end{itemize}
+
+While I am quite enthusiastic about Scala, I am also happy to
+admit that it has more than its fair share of faults. The
+problem seen earlier of having to give an explicit type to
+\code{toSet}, but not \code{toList} is one of them. There are
+also many ``deep'' ideas about types in Scala, which even to
+me as seasoned functional programmer are puzzling. Whilst
+implicits are great, they can also be a source of great
+headaches, for example consider the code:
+
+\begin{lstlisting}[numbers=none]
+scala> List (1, 2, 3) contains "your mom"
+res1: Boolean = false
+\end{lstlisting}
+
+\noindent Rather than returning \code{false}, this code should
+throw a typing-error. There are also many limitations Scala
+inherited from the JVM that can be really annoying. For
+example a fixed stack size. One can work around this
+particular limitation, but why does one have to?
+More such `puzzles' can be found at
+
+\begin{center}
+ \url{http://scalapuzzlers.com} and
+ \url{http://latkin.org/blog/2017/05/02/when-the-scala-compiler-doesnt-help/}
+\end{center}
+
+Even if Scala has been a success in several high-profile
+companies, there is also a company (Yammer) that first used
+Scala in their production code, but then moved away from it.
+Allegedly they did not like the steep learning curve of Scala
+and also that new versions of Scala often introduced
+incompatibilities in old code. In the past two months
+there have also been two forks of the Scala compiler.
+It needs to be seen what the future brings for Scala.
+
+So all in all, Scala might not be a great teaching language,
+but I hope this is mitigated by the fact that I never require
+you to write any Scala code. You only need to be able to read
+it. In the coursework you can use any programming language you
+like. If you want to use Scala for this, then be my guest; if
+you do not want, stick with the language you are most familiar
+with.
+
+
+
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
--- a/langs.sty Wed May 31 09:26:08 2017 +0100
+++ b/langs.sty Thu Nov 02 14:47:55 2017 +0000
@@ -39,13 +39,27 @@
otherkeywords={=,!=,:=,<,>,\%;*,/},
}[keywords,comments,strings]
+
+\newcommand{\code}[1]{{\lstinline{#1}}}
+\newcommand{\pcode}[1]{\mbox{\lstset{language={},keywordstyle=\color{black}}\lstinline!#1!}}
+\newcommand{\scode}[1]{\mbox{\lstset{language={},basicstyle=\ttfamily\color{codegreen}}\lstinline!#1!}}
+\makeatother
+
+%%\lstset{escapeinside={(*@}{@*)}}
+\lstset{escapeinside={/*@}{@*/}}
+
+%% stripy code
+\usepackage{lstlinebgrd}
+\definecolor{capri}{rgb}{0.0, 0.75, 1.0}
+
+
\lstdefinestyle{mystyle}
{basicstyle=\ttfamily,
keywordstyle=\color{codepurple}\bfseries,
stringstyle=\color{codegreen},
commentstyle=\color{codegreen},
morecomment=[s][\color{codedocblue}]{/**}{*/},
- numbers=left,
+ numbers=none,
numberstyle=\tiny\color{black},
stepnumber=1,
numbersep=10pt,
@@ -54,17 +68,9 @@
showstringspaces=false,
xleftmargin=8mm,
emphstyle=\color{codeblue}\bfseries,
- keepspaces
+ keepspaces,
+ linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}
}
\lstset{language=Scala,
style=mystyle}
-
-
-\newcommand{\code}[1]{{\lstinline{#1}}}
-\newcommand{\pcode}[1]{\mbox{\lstset{language={},keywordstyle=\color{black}}\lstinline!#1!}}
-\newcommand{\scode}[1]{\mbox{\lstset{language={},basicstyle=\ttfamily\color{codegreen}}\lstinline!#1!}}
-\makeatother
-
-%%\lstset{escapeinside={(*@}{@*)}}
-\lstset{escapeinside={/*@}{@*/}}
--- a/progs/collatz_sol.scala Wed May 31 09:26:08 2017 +0100
+++ b/progs/collatz_sol.scala Thu Nov 02 14:47:55 2017 +0000
@@ -1,6 +1,8 @@
// Part 1 about the 3n+1 conceture
//=================================
+
+
//(1) Complete the collatz function below. It should
// recursively calculate the number of steps needed
// until the collatz series reaches the number 1.
@@ -36,7 +38,7 @@
// some testing harness
-val bnds = List(2, 10, 100, 1000, 10000, 100000, 77000, 90000, 1000000)
+val bnds = List(2, 10, 100, 1000, 10000, 100000, 77000, 90000, 1000000, 5000000)
for (bnd <- bnds) {
val (max, steps) = collatz_max(bnd)
@@ -46,3 +48,6 @@
//val all = for (i <- (1 to 100000).toList) yield collatz1(i)
//println(all.sorted.reverse.take(10))
+
+
+
--- a/progs/lecture1.scala Wed May 31 09:26:08 2017 +0100
+++ b/progs/lecture1.scala Thu Nov 02 14:47:55 2017 +0000
@@ -2,11 +2,15 @@
//=================
// Value assignments
-// (variable names should be lower case)
-//======================================
+// (their names should be lower case)
+//===================================
val x = 42
val y = 3 + 4
+val z = x / y
+
+
+// (you cannot reassign values: z = 9 will give an error)
// Collections
@@ -66,7 +70,7 @@
List(1,2,3,4).sum
List(1,2,3,4).take(2).sum
List(1,2,3,4).drop(2).sum
-List(1,2,3,4,3).indexOf(3)
+List(1,2,3,4,3)indexOf(3)
"1,2,3,4,5".split(",").mkString("\n")
"1,2,3,4,5".split(",3,").mkString("\n")
@@ -144,7 +148,9 @@
// Function Definitions
//======================
-def square(x: Int): Int = x * x
+def incr(x: Int) : Int = x + 1
+def double(x: Int) : Int = x + x
+def square(x: Int) : Int = x * x
square(6)
@@ -159,8 +165,8 @@
-// If control structure
-//======================
+// If-Conditionals
+//=================
def fact(n: Int): Int =
if (n == 0) 1 else n * fact(n - 1)
@@ -190,12 +196,18 @@
//gcd - Euclid's algorithm
-def gcd(a: Int, b: Int): Int =
+def gcd(a: Int, b: Int) : Int =
if (b == 0) a else gcd(b, a % b)
gcd(48, 18)
+def power(x: Int, n: Int) : Int =
+ if (n == 0) 1 else x * power(x, n - 1)
+
+power(5, 5)
+
+
// String Interpolations
//=======================
@@ -206,7 +218,7 @@
-def gcd_db(a: Int, b: Int): Int = {
+def gcd_db(a: Int, b: Int) : Int = {
println(s"Function called with ${a} and ${b}.")
if (b == 0) a else gcd_db(b, a % b)
}
@@ -285,13 +297,13 @@
import io.Source
// obtaining a webpage
-val url = """http://www.inf.kcl.ac.uk/staff/urbanc/"""
+val url = """https://nms.kcl.ac.uk/christian.urban/"""
Source.fromURL(url)("ISO-8859-1").mkString
// function for looking up stockmarket data
def price_lookup(symbol: String): String = {
- val url = "http://finance.yahoo.com/d/quotes.csv?s=" + symbol + "&f=snl1"
+ val url = "https://download.finance.yahoo.com/d/quotes.csv?s=" + symbol + "&f=snl1"
Source.fromURL(url).mkString.drop(1).dropRight(2)
}
@@ -302,13 +314,14 @@
val companies =
List("GOOG", "AAPL", "MSFT", "IBM", "FB", "YHOO", "AMZN", "BIDU")
-for (s <- companies.par) println(price_lookup(s))
+for (s <- companies) println(price_lookup(s))
-// A Web Crawler
+// A Web Crawler
//===============
//
-// the idea is to look for dead links
+// the idea is to look for dead links using the
+// regular expression "https?://[^"]*"
import io.Source
import scala.util.matching.Regex
@@ -340,7 +353,7 @@
}
// some starting URLs for the crawler
-val startURL = """http://www.inf.kcl.ac.uk/staff/urbanc"""
+val startURL = """https://nms.kcl.ac.uk/christian.urban/"""
//val startURL = """http://www.inf.kcl.ac.uk/staff/mcburney"""
crawl(startURL, 2)
@@ -350,19 +363,67 @@
// Further Information
//=====================
-// Scala download
+// The Scala home page and general information is at
//
// http://www.scala-lang.org
-
-// Eclipse for Scala
+// http://docs.scala-lang.org
+//
+//
+// It should be fairly easy to install the Scala binary and
+// run Scala on the commandline. There are also at least
+// four IDEs you can use with Scala:
+//
+// (0) Some general information for setting up IDEs
+// with Scala support can be found at
+//
+// http://docs.scala-lang.org/getting-started.html
+//
+// (1) Eclipse for Scala (one big bundle)
+//
+// http://scala-ide.org/download/sdk.html
+//
+// (2) IntelliJ (needs additional Plugins)
+//
+// https://www.jetbrains.com/idea/
+// http://docs.scala-lang.org/getting-started-intellij-track/getting-started-with-scala-in-intellij.html
+//
+// (3) Sublime (not free, but unlimited trial period;
+// needs SublimeREPL plugin)
+//
+// https://www.sublimetext.com
+//
+// (4) Emacs (old-fashioned, but reliable)
+//
+// https://www.gnu.org/software/emacs/
//
-// http://scala-ide.org/download/sdk.html
+// I use the old scala-tool support for Emacs distributed at
+//
+// https://github.com/scala/scala-tool-support/tree/master/tool-support/emacs
+//
+// but there is also support for the newer Ensime Scala Mode
+//
+// http://ensime.org/editors/emacs/scala-mode/
+//
+// There is also Scala support in the Atom editor, but my
+// experience is mixed. People also use Scala with Vim and Jedit.
+//
+// All of the IDEs above support a REPL for Scala. Some of them have
+// the very nifty feature of a Scala Worksheet -- you just save your
+// file and it will be automatically evaluated and the result pasted
+// into your file. However, this way of writing Scala code never worked
+// for me. I just use the REPL.
+//
+//
+// Scala Library Docs
+//
+// http://www.scala-lang.org/api/current/
+//
+// Scala Tutorials
+//
+// http://docs.scala-lang.org/tutorials/
+//
+// There are also a massive number of Scala tutorials on youtube
+// and there are tons of books and free material.
+//
-// library docs
-//
-// http://www.scala-lang.org/api/current/
-
-// tutorials
-//
-// http://docs.scala-lang.org/tutorials/
Binary file slides/slides01.pdf has changed
--- a/slides/slides01.tex Wed May 31 09:26:08 2017 +0100
+++ b/slides/slides01.tex Thu Nov 02 14:47:55 2017 +0000
@@ -35,7 +35,7 @@
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
- Office: & S1.27 (1st floor Strand Building)\\
+ Office: & N7.07 (North Wing Bush House)\\
Slides \& Code: & KEATS
\end{tabular}
\end{center}
--- a/style.sty Wed May 31 09:26:08 2017 +0100
+++ b/style.sty Thu Nov 02 14:47:55 2017 +0000
@@ -1,14 +1,15 @@
\usepackage{xcolor}
+%%\usepackage{fontspec}
\usepackage[sc]{mathpazo}
\usepackage{fontspec}
\setmainfont[Ligatures=TeX]{Palatino Linotype}
\usepackage{amssymb}
\usepackage{amsmath}
-%%\usepackage{menukeys}
-
+\usepackage{menukeys}
\definecolor{darkblue}{rgb}{0,0,0.6}
\usepackage[colorlinks=true,urlcolor=darkblue,linkcolor=darkblue]{hyperref}
+%%% for regular expressions and values
\newcommand{\ZERO}{\mbox{\bf 0}}
\newcommand{\ONE}{\mbox{\bf 1}}
\newcommand{\Left}{\textit{Left}}
@@ -20,6 +21,30 @@
%%% for trees
%% http://anorien.csc.warwick.ac.uk/mirrors/CTAN/graphics/pgf/contrib/forest/forest.pdf
+\newcommand\grid[1]{%
+\begin{tikzpicture}[baseline=(char.base)]
+ \path[use as bounding box]
+ (0,0) rectangle (1em,1em);
+ \draw[red!50, fill=red!20]
+ (0,0) rectangle (1em,1em);
+ \node[inner sep=1pt,anchor=base west]
+ (char) at (0em,\gridraiseamount) {#1};
+\end{tikzpicture}}
+\newcommand\gridraiseamount{0.12em}
+
+\makeatletter
+\newcommand\Grid[1]{%
+ \@tfor\z:=#1\do{\grid{\z}}}
+\makeatother
+
+\newcommand\Vspace[1][.3em]{%
+ \mbox{\kern.06em\vrule height.3ex}%
+ \vbox{\hrule width#1}%
+ \hbox{\vrule height.3ex}}
+
+\def\VS{\Vspace[0.6em]}
+
+
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}
\newcommand{\defn}[1]{\textit{\textbf{#1}}}
\newcommand{\dq}[1]{\mbox{\tt{"}}#1\mbox{\tt{"}}}
@@ -30,3 +55,25 @@
\def\fnote{\gdef\@thefnmark{}\@footnotetext}
\makeatother
+\newcommand{\HEADER}{{\bf Please submit your solutions via email. Please submit
+only ASCII text or PDFs. Every solution should be preceeded by the corresponding
+question text, like:
+
+\begin{center}
+\begin{tabular}{ll}
+Q$n$: & \ldots a difficult question from me\ldots\\
+A: & \ldots an answer from you \ldots\\
+Q$n+1$ & \ldots another difficult question\ldots\\
+A: & \ldots another brilliant answer from you\ldots
+\end{tabular}
+\end{center}
+
+\noindent Solutions will only be accepted until 20th December! Please send only
+one homework per email.}\bigskip}
+
+\newcommand{\POSTSCRIPT}{
+{\bf (Optional)} This question is for you to provide
+regular feedback to me: for example
+what were the most interesting, least interesting, or confusing
+parts in this lecture? Any problems with my Scala code? Please
+feel free to share any other questions or concerns.}