\documentclass{article}\usepackage{../style}\usepackage{../langs}\usepackage{marvosym}%cheat sheet%http://worldline.github.io/scala-cheatsheet/% case class, apply, unappy% see https://medium.com/@thejasbabu/scala-pattern-matching-9c9e73ba9a8a\begin{document} \section*{A Crash-Course on Scala}Scala is a programming language that combines functional andobject-oriented programming-styles. It has received quite a bit ofattention in the last five or so years. One reason for this attentionis that, like the Java programming language, Scala compiles to theJava Virtual Machine (JVM) and therefore Scala programs can run underMacOSX, 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 andelegant code. Some therefore say: ``Scala is the betterJava''.\footnote{\url{https://www.slideshare.net/maximnovak/joy-of-scala}}Also a number of companies (the Guardian, Twitter, Coursera,FourSquare, LinkedIn to name a few) either use Scala exclusively inproduction code, or at least to some substantial degree. Scala seemsalso to be useful in job-interviews (in Data Science) according tothis anecdotal report\begin{quote}\url{https://techcrunch.com/2016/06/14/scala-is-the-new-golden-child/}\end{quote}\noindentIf you want to try out Scala yourself, the official Scala compiler can bedownloaded from\begin{quote}\url{http://www.scala-lang.org}\end{quote}\noindentA ready-made bundle with the Eclipse IDE is at\begin{quote}\url{http://scala-ide.org/download/sdk.html}\end{quote}\noindentWhen developing Scala programs, I personally prefer to use Emacsor Sublime as my environment, since they provide an easy accessto the Scala REPL (see below). But it is also possible to workcompletely on the command line and also with heavy-duty IDEslike Eclipse of IntelliJ. There is even an online editor andenvironment for developing Scala programs called ScalaFiddle\begin{quote}\url{https://scalafiddle.io}\end{quote}Why do I use Scala in the AFL module? Actually, you can do\emph{any} part of the coursework in \emph{any} programminglanguage you like. I use Scala for showing you code during thelectures because its functional programming-style allows me toimplement the functions we will discuss with very smallcode-snippets. If I had to do this in Java, I would first haveto go through heaps of boilerplate code and the code-snippetswould not look pretty. Since the Scala compiler is free, youcan download the code-snippets and run every example I give.But if you prefer, you can also easily translate them into anyother functional language, for example Haskell, Swift,Standard ML, F$^\#$, Ocaml and so on.Developing programs in Scala can be done with the Eclipse IDEand also with the IntelliJ IDE, but for the small programs I willdevelop the good old Emacs-editor is adequate for me and Iwill run the programs on the command line. One advantage ofScala 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 withoutthe need of the compiler. This helps a lot with interactivelydeveloping programs. Once you installed Scala, you can startthe interpreter by typing on the command line:\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]$ scalaWelcome 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 theversion and platform where you installed Scala. At the Scalaprompt you can type things like \code{2 + 3} \keys{Ret} andthe output will be\begin{lstlisting}[numbers=none]scala> 2 + 3res0: Int = 5\end{lstlisting}\noindent indicating that the result of the addition is oftype \code{Int} and the actual result is 5. Another classicexample 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. Thereason is that \code{print} does not actually produce a result(there is no \code{resXX} and no type), rather it is afunction that causes the \emph{side-effect} of printing out astring. Once you are more familiar with the functionalprogramming-style, you will know what the difference isbetween a function that returns a result, like addition, and afunction that causes a side-effect, like \code{print}. Weshall come back to this point later, but if you are curiousnow, the latter kind of functions always has \code{Unit} asreturn type.If you want to write a stand-alone app in Scala, you canimplement 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}, andthen run the compiler and runtime environment:\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]$ scalac hello-world.scala$ scala Hellohello world\end{lstlisting}As mentioned above, Scala targets the JVM and consequentlyScala programs can also be executed by the bog-standard JavaRuntime. This only requires the inclusion of {\ttscala-library.jar}, which on my computer can be done asfollows:\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]$ scalac hello-world.scala$ java -cp /usr/local/src/scala/lib/scala-library.jar:. Hellohello world\end{lstlisting}\noindent You might need to adapt the path to where you haveinstalled Scala.\subsection*{Inductive Datatypes}The elegance and conciseness of Scala programs are often aresult of inductive datatypes that can be easily defined inScala. For example in ``every-day mathematics'' we defineregular 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 ofinner nodes---sequence, alternative and star---and three kindsof leave nodes---null, empty and character). If you arefamiliar with Java, it might be an instructive exercise todefine this kind of inductive datatypes in Java\footnote{Happyprogramming! \Smiley} and then compare it with how it can beimplemented in Scala.Implementing the regular expressions from above in Scala isactually very simple: It first requires an \emph{abstractclass}, say, \code{Rexp}. This will act as the type forregular expressions. Second, it requires a case for eachclause in the grammar. The cases for $\ZERO$ and $\ONE$ do nothave any arguments, while in all the other cases we do havearguments. For example the character regular expression needsto take as an argument the character it is supposed torecognise. 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 asfollows:\begin{lstlisting}[numbers=none]abstract class Rexp case object ZERO extends Rexpcase object ONE extends Rexpcase class CHAR (c: Char) extends Rexpcase 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 caseobject and case class needs to extend \code{Rexp}. Given thegrammar above, I hope you can see the underlying pattern. Ifyou want to play further with such definitions of inductivedatatypes, feel free to define for example binary trees.Once you make a definition like the one above in Scala, youcan 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 outputsyntax, as you can see below, the quotes are omitted. In alater section we will see how we can support the moremathematical infix notation for regular expression operatorsin Scala. If you want to assign this regular expression to avariable, 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 inJava). However, if there is the need for some non-standardinitialisation, you can of course define such a constructor inScala too. But we omit such ``tricks'' here. Note that Scala in its response says the variable \code{r} isof type \code{ALT}, not \code{Rexp}. This might be a bitunexpected, but can be explained as follows: Scala alwaystries to find the most general type that is needed for avariable or expression, but does not ``over-generalise''. Inour definition the type \code{Rexp} is more general than\code{ALT}, since it is the abstract class for all regularexpressions. But in this particular case there is no need togive \code{r} the more general type of \code{Rexp}. This isdifferent 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 tothe regular expressions so that it is compatible with thefact that lists can only contain elements of a single type. Inthis case the first common type is \code{Rexp}.\footnote{If youtype in this example, you will notice that the type containssome further information, but let us ignore this for themoment.} For compound types like \code{List[...]}, the general rule isthat when a type takes another type as argument, then thisargument type is written in angle-brackets. This can alsocontain nested types as in \code{List[Set[Rexp]]}, which is alist of sets each of which contains regular expressions.\subsection*{Functions and Pattern-Matching}I mentioned above that Scala is a very elegant programminglanguage for the code we will write in this module. Thiselegance mainly stems from the fact that in addition toinductive datatypes, also functions can be implemented veryeasily in Scala. To show you this, let us first consider aproblem from number theory, called the \emph{Collatz-series},which corresponds to a famous unsolved problem inmathematics.\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 thisseries started with any $n > 0$ as $collatz_0$ will alwaysreturn to $1$. This is obvious when started with $1$, and alsowith $2$, but already needs a bit of head-scratching for thecase of $3$.If we want to avoid the head-scratching, we could implementthis 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 alist of arguments (enclosed in parentheses and separated bycommas). Each argument in this list needs its type to beannotated. In this case we only have one argument, which is oftype \code{BigInt}. This type stands in Scala for arbitraryprecision integers (in case you want to try out the functionon really big numbers). After the arguments comes the type ofwhat the function returns---a Boolean in this case forindicating that the function has reached 1. Finally, after the\code{=} comes the \emph{body} of the function implementingwhat the function is supposed to do. What the \code{collatz}function does should be pretty self-explanatory: the functionfirst tests whether \code{n} is equal to 1 in which case itreturns \code{true} and so on.Notice the quirk in Scala's syntax for \code{if}s: The conditionneeds to be enclosed in parentheses and the then-case comesright after the condition---there is no \code{then} keyword inScala.The real power of Scala comes, however, from the ability todefine functions by \emph{pattern matching}. In the\code{collatz} function above we need to test each case using asequence of \code{if}s. This can be very cumbersome and brittleif there are many cases. If we wanted to define a functionover regular expressions in Java, for example, which does nothave pattern-matching, the resulting code would just beawkward.Mathematicians already use the power of pattern-matching whenthey define the function that takes a regular expression andproduces another regular expression that can recognise thereversed 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 ofwhat the regular expression might look like. The correspondingScala code looks very similar to this definition, thanks topattern-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 thematch keyword can be another pattern, but often, as in thecase 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 wedefined regular expressions as inductive datatype. For examplethe case in Line 3 you can read as: if the regular expression\code{r} is of the form \code{EMPTY} then do whatever followsthe \code{=>} (in this case just return \code{EMPTY}). Line 5reads as: if the regular expression \code{r} is of the form\code{ALT(r1, r2)}, where the left-branch of the alternative ismatched by the variable \code{r1} and the right-branch by\code{r2} then do ``something''. The ``something'' can now use thevariables \code{r1} and \code{r2} from the match. If you want to play with this function, call it for examplewith the regular expression $ab + ac$. This regular expressioncan recognise the strings $ab$ and $ac$. The function \code{rev} produces $ba + ca$, which can recognise the reversedstrings $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-matchdoes not improve the code in any way. In cases like\code{rev}, however, it is really crucial. The underscore inLine 4 indicates that we do not care what the pattern lookslike. Thus this case acts like a default case whenever thecases above did not match. Cases are always tried out from topto bottom.\subsection*{Loops, or better the Absence thereof}Coming from Java or C, you might be surprised that Scala doesnot really have loops. It has instead, what is in functionalprogramming called, \emph{maps}. To illustrate how they work,let us assume you have a list of numbers from 1 to 8 and want tobuild 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).toListres1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)\end{lstlisting}\noindent Generating from this list, the list of squares in aprogramming language such as Java, you would assume the listis given as a kind of array. You would then iterate, or loop,an index over this array and replace each entry in the arrayby the square. Right? In Scala, and in other functionalprogramming languages, you use maps to achieve the same. A map essentially takes a function that describes how eachelement is transformed (for example squared) and a list overwhich this function should work. There are two forms toexpress such maps in Scala. The first way is called a\emph{for-comprehension}. Squaring the numbers from 1 to 8would look in this form as follows:\begin{lstlisting}[numbers=none]scala> for (n <- (1 to 8).toList) yield n * nres2: 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 fromthe list of numbers we draw \code{n}s and compute the resultof \code{n * n}. As you can see, we specified the list whereeach \code{n} comes from, namely \code{(1 to 8).toList}, andhow each element needs to be transformed. This can also beexpressed 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} standsfor the function that calculates the square (this is how the\code{n}s are transformed). This expression for functionsmight remind you of your lessons about the lambda-calculuswhere this would have been written as $\lambda n.\,n * n$. Itmight not be obvious, but for-comprehensions are justsyntactic sugar: when compiling, Scala translatesfor-comprehensions into equivalent maps. This even workswhen for-comprehensions get more complicated (see below).The very charming feature of Scala is that such maps orfor-comprehensions can be written for any kind of datacollection, such as lists, sets, vectors, options and so on.For example if we instead compute the reminders modulo 3 ofthis 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 notinto a list, but into a set, and then compute the remindersmodulo 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 areonly three equivalence classes of integers modulo 3. Note thatin this example we need to ``help'' Scala to transform thenumbers into a set of integers by explicitly annotating thetype \code{Int}. Since maps and for-comprehensions arejust syntactic variants of each other, the latter can also bewritten as\begin{lstlisting}[numbers=none]scala> for (n <- (1 to 8).toSet[Int]) yield n % 3res5 = 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 upthe 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 3where 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-comprehensionfilters out all pairs where the sum is not even.While hopefully this all looks reasonable, there is onecomplication: In the examples above we always wanted totransform one list into another list (e.g.~list of squares),or one set into another set (set of numbers into set ofreminders modulo 3). What happens if we just want to print outa list of integers? Then actually the for-comprehensionneeds to be modified. The reason is that \code{print}, youguessed it, does not produce any result, but only produceswhat is in the functional-programming-lingo called aside-effect. Printing out the list of numbers from 1 to 5would look as follows\begin{lstlisting}[numbers=none]scala> for (n <- (1 to 5).toList) print(n)12345\end{lstlisting}\noindentwhere you need to omit the keyword \code{yield}. You canalso 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 = 12 * 2 = 43 * 3 = 94 * 4 = 165 * 5 = 25\end{lstlisting}\noindent In this code I use a variable assignment (\code{valsquare_n = ...} ) and also what is called in Scala a\emph{string interpolation}, written \code{s"..."}. The latteris for printing out an equation. It allows me to refer to theinteger 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 yourlambda-calculus lessons, where an explanation is given whyboth forms produce the same result.If you want to find out more about maps and functions withside-effects, you can ponder about the response Scala gives ifyou replace \code{foreach} by \code{map} in the expressionabove. Scala will still allow \code{map} with side-effectfunctions, but then reacts with a slightly interesting result.\subsection*{Types}In most functional programming languages, types play animportant role. Scala is such a language. You have alreadyseen 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 thornysubject, especially in Scala. For example, why do we need togive the type to \code{toSet[Int]}, but not to \code{toList}?The reason is the power of Scala, which sometimes means itcannot infer all necessary typing information. At thebeginning while getting familiar with Scala, I recommend a``play-it-by-ear-approach'' to types. Fully understandingtype-systems, especially complicated ones like in Scala, cantake a module on their own.\footnote{Still, such a study canbe a rewarding training: If you are in the business ofdesigning new programming languages, you will not be able toturn a blind eye to types. They essentially help programmersto avoid common programming errors and help with maintainingcode.}In Scala, types are needed whenever you define an inductivedatatype and also whenever you define functions (theirarguments and their results need a type). Base types are typesthat 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, forexample \code{List[Int]} or \code{Set[List[String]]} or \code{Map[Int, Int]}.There are a few special type-constructors that fall outsidethis pattern. One is for tuples, where the type is writtenwith parentheses. For example \begin{lstlisting}[ numbers=none](Int, Int, String)\end{lstlisting}\noindent is for a triple (a tuple with three components---twointegers and a string). Tuples are helpful if you want todefine functions with multiple results, say the functionreturning the quotient and reminder of two numbers. For thisyou 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, itsreturn 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 asthe arrow \code{=>}. For example, the type \code{Int =>String} is for a function that takes an integer as inputargument and produces a string as result. A function of thistype 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 astring. Unlike other functional programming languages, thereis in Scala no easy way to find out the types of existingfunctions, 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 functiontaking an integer as first argument and a string as second,and the result of the function is a boolean. Though silly, afunction 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 thearguments of this function: the arguments are given one afterthe other, instead of being in a pair (what would be the typeof this function then?). This way of specifying the argumentscan 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 specialisedversion of \code{chk_string}---once specialised to 2 and onceto 3. This kind of ``specialising'' a function is called\emph{partial application}---we have not yet given to thisfunction all arguments it needs, but only some of them.Coming back to the type \code{Int => String => Boolean}. Therule about such function types is that the right-most typespecifies what the function returns (a boolean in this case).The types before that specify how many arguments the functionexpects 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 aboolean. More interestingly, though, it only takes a singleargument (because of the parentheses). The single argumenthappens to be another function (taking an integer as input andreturning a string). Remember that \code{mk_string} is just such a function. So how can we use it? For this definethe 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 isthe point of having functions as input arguments to otherfunctions? In Java there is indeed no need of this kind offeature: at least in the past it did not allow suchconstructions. I think, the point of Java 8 is to lift thisrestriction. But in all functional programming languages,including Scala, it is really essential to allow functions asinput 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, fivenumbers are printed.\begin{lstlisting}[numbers=none]scala> (1 to 5).toList.foreach(print)12345scala> (1 to 5).toList.foreach(println)12345\end{lstlisting}\noindent This is actually one of the main design principlesin 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 whatshould be done with each element during the traversal. Thisrequires that the generic traversal functions can cope withany 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 traversalfunctions, but have to keep them\emph{polymorphic}.\footnote{Another interestic topic abouttypes, but we omit it here for the sake of brevity.} There is one more type constructor that is rather special. Itis called \code{Unit}. Recall that \code{Boolean} has twovalues, namely \code{true} and \code{false}. This can be used,for example, to test something and decide whether the testsucceeds or not. In contrast the type \code{Unit} has only asingle value, written \code{()}. This seems like a completelyuseless type and return value for a function, but is actuallyquite useful. It indicates when the function does not returnany result. The purpose of these functions is to causesomething 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 somenew data in a file. Scala uses the \code{Unit} type to indicatethat a function does not have a result, but potentially causessome 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 acrossthe following code-snippet for reading a web-page. \begin{lstlisting}[ numbers=none]import io.Sourceval 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 theHTML-code of my webpage. It actually already does somethingmore sophisticated, namely only returns the first 10000characters of a webpage in case it is too large. Why is thatcode-snippet of any interest? Well, try implementingreading-from-a-webpage in Java. I also like the possibility oftriple-quoting strings, which I have only seen in Scala sofar. The idea behind this is that in such a string allcharacters are interpreted literally---there are no escapedcharacters, like \verb|\n| for newlines.My second wow-moment I had with a feature of Scala that otherfunctional programming languages do not have. This feature isabout implicit type conversions. If you have regularexpressions and want to use them for language processing youoften want to recognise keywords in a language, for example\code{for},{} \code{if},{} \code{yield} and so on. But thebasic regular expression \code{CHAR} can only recognise asingle 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 andregular expressions get more complicated. In other functionalprogramming languages, you can explicitly write a conversionfunction that takes a string, say \dq{\pcode{for}}, andgenerates the regular expression above. But then your code islittered with such conversion functions.In Scala you can do better by ``hiding'' the conversionfunctions. The keyword for doing this is \code{implicit} andit needs a built-in library called \begin{lstlisting}[numbers=none]scala.language.implicitConversions\end{lstlisting}\noindentConsider the code\begin{lstlisting}[language=Scala]import scala.language.implicitConversionsdef 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 functionthat given a list of characters generates the correspondingregular expression. In Lines 9 and 10, this function is usedfor 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 regularexpression, but I only give it a string, it will automaticallyinsert a call to the \code{string2rexp}-function. I can nowwrite 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 regularexpressions as arguments, but I only supply two strings. Theimplicit conversion function will transform the string into aregular expression.Using implicit definitions, Scala allows me to introducesome 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 isthat 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 othersyntactic sugar in the code above stands for.One more useful feature of Scala is the ability to definefunctions with varying argument lists. This is a feature thatis already present in old languages, like C, but seems to havebeen forgotten in the meantime---Java does not have it. In thecontext 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 suchalternatives are nested. So you need something flexible thatcan take as many alternatives as needed. In Scala one canachieve 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 regularexpressions and converts it into an appropriate alternativeregular expression. In Line 7 there is a wrapper for thisfunction which uses the feature of varying argument lists. Theeffect of this code is that I can write the regularexpression 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 thissimplifies the regular expression in comparison with if I hadto write this by hand using only the ``plain'' regularexpressions from the inductive datatype.\subsection*{More Info}There is much more to Scala than I can possibly describe inthis document. Fortunately there are a number of free booksabout 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 FunctionalProgramming Principles in Scala by Martin Odersky, the maindeveloper of the Scala language. And a document that explainsScala 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 toadmit that it has more than its fair share of faults. Theproblem seen earlier of having to give an explicit type to\code{toSet}, but not \code{toList} is one of them. There arealso many ``deep'' ideas about types in Scala, which even tome as seasoned functional programmer are puzzling. Whilstimplicits are great, they can also be a source of greatheadaches, 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 shouldthrow a typing-error. There are also many limitations Scalainherited from the JVM that can be really annoying. Forexample a fixed stack size. One can work around thisparticular 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-profilecompanies, there is also a company (Yammer) that first usedScala in their production code, but then moved away from it.Allegedly they did not like the steep learning curve of Scalaand also that new versions of Scala often introducedincompatibilities in old code. In the past two monthsthere 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 requireyou to write any Scala code. You only need to be able to readit. In the coursework you can use any programming language youlike. If you want to use Scala for this, then be my guest; ifyou do not want, stick with the language you are most familiarwith.\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: