% !TEX program = xelatex\documentclass{article}\usepackage{../styles/style}\usepackage{../styles/langs}\usepackage{tikz}\usepackage{pgf}\usepackage{marvosym}\usepackage{boxedminipage}\lstset{escapeinside={/*!}{!*/}}\newcommand{\annotation}[1]{\hfill\footnotesize{}#1}\usepackage{menukeys}%cheat sheet%http://worldline.github.io/scala-cheatsheet/% case class, apply, unapply% see https://medium.com/@thejasbabu/scala-pattern-matching-9c9e73ba9a8a% the art of programming% https://www.youtube.com/watch?v=QdVFvsCWXrA% functional programming in Scala%https://www.amazon.com/gp/product/1449311032/ref=as_li_ss_tl?ie=UTF8&tag=aleottshompag-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=1449311032% functional programming in C%https://www.amazon.com/gp/product/0201419505/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0201419505&linkCode=as2&tag=aleottshompag-20%speeding through haskell%https://openlibra.com/en/book/download/speeding-through-haskell% fp books --- ocaml% http://courses.cms.caltech.edu/cs134/cs134b/book.pdf% http://alexott.net/en/fp/books/%John Hughes’ simple words:%A combinator is a function which builds program fragments%from program fragments.%explain graph colouring program (examples from)%https://www.metalevel.at/prolog/optimization% nice example for map and reduce using Harry potter characters% https://www.matthewgerstman.com/map-filter-reduce/% interesting talk about differences in Java and Scala% Goto'19 conference ; about differences in type-system% https://www.youtube.com/watch?v=e6n-Ci8V2CM% Timing%% xs.map(x => (x, xs.count(_==x)))%% vs xs.groupBy(identity)%% first is quadratic, while second is linear.% contrast map with a for loop in imperative languages%% Let’s use a simple example of calculating sales tax on an array of% prices.%% const prices = [19.99, 4.95, 25, 3.50];% let new_prices = [];%% for(let i=0; i < prices.length; i++) {% new_prices.push(prices[i] * 1.06);% }%% We can achieve the same results using .map():%% const prices = [19.99, 4.95, 25, 3.50]; % let new_prices = prices.map(price => price * 1.06);%% The syntax above is condensed so let’s walk through it a bit. The% .map() method takes a callback, which can be thought of as a function.% That’s what is between the parentheses. The variable price is the name% that will be used to identify each value. Since there’s only one% input, we can omit the usual parentheses around the parameters.% potentially a worked example? Tetris in scala.js% % https://medium.com/@michael.karen/learning-modern-javascript-with-tetris-92d532bcd057%% Scala videos% https://www.youtube.com/user/DrMarkCLewis%% https://alvinalexander.com/downloads/HelloScala-FreePreview.pdf%% %% Section 10 about strings; interpolations and multiline strings% Easy installation%https://alexarchambault.github.io/posts/2020-09-21-cs-setup.html% scala libraries%https://index.scala-lang.org% Learning functional programming is an opportunity to discover a new% way to represent programs, to approach problems, and to think about% languages. While programming with a functional language is still% fundamentally similar to programming with any other type of language% (examples of others being imperative or logic), it represents% programs and algorithms through distinct forms of abstraction and% gives you a new toolset with which to solve programming% problems. Additionally, many of the techniques of functional% programming are beginning to permeate new mainstream languages, so% taking the time now to develop a thorough understanding of them is% an investment which will pay great dividends.% Exact colors from NB\usepackage[breakable]{tcolorbox}\definecolor{incolor}{HTML}{303F9F}\definecolor{outcolor}{HTML}{D84315}\definecolor{cellborder}{HTML}{CFCFCF}\definecolor{cellbackground}{HTML}{F7F7F7}\begin{document}\fnote{\copyright{} Christian Urban, King's College London, 2017, 2018, 2019, 2020, 2021, 2022}%\begin{tcolorbox}[breakable,size=fbox,boxrule=1pt,pad at break*=1mm,colback=cellbackground,colframe=cellborder]% abd%\end{tcolorbox}\section*{A Crash-Course in Scala}\mbox{}\hfill\textit{``Scala --- \underline{S}lowly \underline{c}ompiled \underline{a}cademic \underline{la}nguage''}\smallskip\\\mbox{}\hfill\textit{ --- a joke(?) found on Twitter}\bigskip\subsection*{Introduction}\noindentScala 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 attention isthat, like the Java programming language, Scala compiles to the JavaVirtual Machine (JVM) and therefore Scala programs can run under MacOSX,Linux and Windows. Because of this it has also access tothe myriads of Java libraries. Unlike Java, however, Scala often allowsprogrammers to write very concise and elegant code. Some therefore say``Scala is the better Java''.\footnote{from\url{https://www.slideshare.net/maximnovak/joy-of-scala}} A number of companies---the Guardian, Twitter, Coursera, FourSquare,Netflix, LinkedIn, ITV to name a few---either use Scala exclusively inproduction code, or at least to some substantial degree. Scala seemsalso useful in job-interviews (especially in data science) according tothis anecdotal report\begin{quote}\url{http://techcrunch.com/2016/06/14/scala-is-the-new-golden-child}\end{quote}\noindentThe official Scala compiler can be downloaded from\begin{quote}\url{http://www.scala-lang.org}\medskip\end{quote}\noindent\alertJust make sure you are downloading the ``battle tested'' version ofScala \textbf{2.13} This is the one I am going to use in the lectures andin the coursework. The newer Scala 3.1 \& 3.2 still have somefeatures not fully implemented.\bigskip\noindentIf you are interested, there are also experimental backends of Scalafor producing code under Android (\url{http://scala-android.org}); forgenerating JavaScript code (\url{https://www.scala-js.org}); and thereis work under way to have a native Scala compiler generating X86-code(\url{http://www.scala-native.org}). Though be warned these backendsare still rather beta or even alpha.\subsection*{VS Code and Scala}I found a convenient IDE for writing Scala programs is Microsoft's\textit{Visual Studio Code} (VS Code) which runs under MacOSX, Linux andobviously Windows.\footnote{\ldots{}unlike \emph{Microsoft Visual Studio}---notethe minuscule difference in the name---which is a heavy-duty,Windows-only IDE\ldots{}jeez, with all their money could they not have comeup with a completely different name for a complete different project?For the pedantic, Microsoft Visual Studio is an IDE, whereas VisualStudio Code is considered to be a \emph{source code editor}. Anybody knows what thedifference is?} It can be downloaded for free from\begin{quote}\url{https://code.visualstudio.com}\end{quote}\noindentand should already come pre-installed in the Department (together withthe Scala compiler). Being a project that just started in 2015, VS Code isrelatively new and thus far from perfect. However it includes a\textit{Marketplace} from which a multitude of extensions can bedownloaded that make editing and running Scala code a little easier (seeFigure~\ref{vscode} for my setup).\begin{figure}[t]\begin{boxedminipage}{\textwidth} \begin{center} \includegraphics[scale=0.15]{../pics/vscode.png}\\[-10mm]\mbox{}\end{center}\caption{My installation of VS Code includes the following packages from Marketplace: \textbf{Scala Syntax (official)} 0.5.4, \textbf{Code Runner} 0.11.6, \textbf{Code Spell Checker} 2.0.12, \textbf{Rewrap} 1.14.0 and \textbf{Subtle Match Brackets} 3.0.0. I have also bound the keys \keys{Ctrl} \keys{Ret} to the action ``Run-Selected-Text-In-Active-Terminal'' in order to quickly evaluate small code snippets in the Scala REPL. I use the internal terminal to run Scala 2.13.6.\label{vscode}}\end{boxedminipage}\end{figure} Actually \alert last year I switched to VS Codium, which is VS Code minusall the telemetry that is normally sent to Microsoft. Apart from the telemetry, it works pretty much the same as the original but is drivenby a dedicated community, rather than a big company. You can downloadVS Codium from\begin{quote}\url{https://vscodium.com}\end{quote}What I like most about VS Code/Codium is that it provides easy access to theScala REPL. But if you prefer another editor for coding, it is alsopainless to work with Scala completely on the command line (as you mighthave done with \texttt{g++} in the earlier part of PEP). For thelazybones among us, there are even online editors and environments fordeveloping and running Scala programs: \textit{ScalaFiddle}and \textit{Scastie} are two of them. They require zero setup (assuming you have a browser handy). You can access them at \begin{quote} \url{https://scalafiddle.io}\\ \url{https://scastie.scala-lang.org}\medskip\end{quote}\noindentBut you should be careful if you use them for your coursework: theyare meant to play around, not really for serious work. As one might expect, Scala can be used with the heavy-duty IDEsEclipse and IntelliJ. A ready-made Scala bundle for Eclipse isavailable from\begin{quote}\url{http://scala-ide.org/download/sdk.html}\end{quote}\noindentAlso IntelliJ includes plugins for Scala. \underline{\textbf{BUT}}, I do \textbf{not} recommend the usage of either Eclipse or IntelliJ for PEP: these IDEsseem to make your life harder, rather than easier, for the smallprograms that we will write in this module. They are really meant to be usedwhen you have a million-lines codebase than with our small``toy-programs''\ldots{}for example why on earth am I required to create acompletely new project with several subdirectories when I just want totry out 20-lines of Scala code? Your mileage may vary though.~\texttt{;o)}\subsection*{Why Functional Programming?}Before we go on, let me explain a bit more why we want to inflict uponyou another programming language. You hopefully have mastered Java andC++\ldots{}the world should be your oyster, no? Well, matters are not assimple as one might wish. We do require Scala in PEP, but actually we donot religiously care whether you learn Scala---after all it is just aprogramming language (albeit a nifty one IMHO). What we do care about isthat you learn about \textit{functional programming}. Scala is just thevehicle for that. Still, you need to learn Scala well enough to get goodmarks in PEP, but functional programming could perhaps equally be taughtwith Haskell, F\#, SML, Ocaml, Kotlin, Clojure, Scheme, Elm and manyother functional programming languages. %Your friendly lecturer just%happens to like Scala and the Department agreed that it is a good idea%to inflict Scala upon you.Very likely writing programs in a functional programming language isquite different from what you are used to in your study so far. Itmight even be totally alien to you. The reason is that functionalprogramming seems to go against the core principles of\textit{imperative programming} (which is what you do in Java and C/C++for example). The main idea of imperative programming is that you havesome form of \emph{state} in your program and you continuously changethis state by issuing some commands---for example for updating a fieldin an array or for adding one to a variable and so on. The classicexample for this style of programming is a \texttt{for}-loop in C/C++.Consider the snippet:\begin{lstlisting}[language=C,numbers=none]for (int i = 10; i < 20; i++) { //...do something with i...}\end{lstlisting}\noindent Here the integer variable \texttt{i} embodies the state, whichis first set to \texttt{10} and then increased by one in eachloop-iteration until it reaches \texttt{20} at which point the loopexits. When this code is compiled and actually runs, there will be somededicated space reserved for \texttt{i} in memory. This space oftypically 32 bits contains \texttt{i}'s current value\ldots\texttt{10}at the beginning, and then the content will be overwritten with new content in every iteration. The main point here is that this kind ofupdating, or overwriting, of memory is 25.806\ldots or \textbf{THE ROOT OFALL EVIL}!!\begin{center}\includegraphics[scale=0.25]{../pics/root-of-all-evil.png}\end{center} \noindent\ldots{}Well, it is perfectly benign if you have a sequential programthat gets run instruction by instruction...nicely one after another.This kind of running code uses a single core of your CPU and goes asfast as your CPU frequency, also called clock-speed, allows. The problemis that this clock-speed has not much increased over the past decade andno dramatic increases are predicted for any time soon. So you are a bitstuck. This is unlike previous generations of developers who could relyupon the fact that approximately every 2 years their code would runtwice as fast because the clock-speed of their CPUs got twice as fast.Unfortunately this does not happen any more nowadays. To get you out ofthis dreadful situation, CPU producers pile more and more cores intoCPUs in order to make them more powerful and potentially make softwarefaster. The task for you as developer is to take somehow advantage ofthese cores by running as much of your code as possible in parallel onas many cores you have available (typically 4 or more in modern laptopsand sometimes much more on high-end machines). In this situation\textit{mutable} variables like \texttt{i} in the C-code above are evil,or at least a major nuisance: Because if you want to distribute some ofthe loop-iterations over several cores that are currently idle in yoursystem, you need to be extremely careful about who can read andoverwrite the variable \texttt{i}.\footnote{If you are of the mistakenbelief that nothing nasty can happen to \texttt{i} inside the\texttt{for}-loop, then you need to go back over the C++ material.}Especially the writing operation is critical because you do not wantthat conflicting writes mess about with \texttt{i}. Take my word: anuntold amount of misery has arisen from this problem. The catch is thatif you try to solve this problem in C/C++ or Java, and be as defensiveas possible about reads and writes to \texttt{i}, then you need tosynchronise access to it. The result is that very often your programwaits more than it runs, thereby defeating the point of trying to runthe program in parallel in the first place. If you are less defensive,then usually all hell breaks loose by seemingly obtaining randomresults. And forget the idea of being able to debug such code.The central idea of functional programming is to eliminate any statefrom programs---or at least from the ``interesting bits'' of theprograms. Because then it is easy to parallelise the resultingprograms: if you do not have any state, then once created, all memorycontent stays unchanged and reads to such memory are absolutely safewithout the need of any synchronisation. An example is given inFigure~\ref{mand} where in the absence of the annoying state, Scalamakes it very easy to calculate the Mandelbrot set on as many cores ofyour CPU as possible. Why is it so easy in this example? Because eachpixel in the Mandelbrot set can be calculated independently and thecalculation does not need to update any variable. It is so easy infact that going from the sequential version of the Mandelbrot programto the parallel version can be achieved by adding just eightcharacters---in two places you have to add \texttt{.par}. Try the samein C/C++ or Java!\begin{figure}[p]\begin{boxedminipage}{\textwidth}A Scala program for generating pretty pictures of the Mandelbrot set.\smallskip\\ (See \url{https://en.wikipedia.org/wiki/Mandelbrot_set} or\\\phantom{(See }\url{https://www.youtube.com/watch?v=aSg2Db3jF_4}):\begin{center} \begin{tabular}{c} \includegraphics[scale=0.11]{../pics/mand1.png}\\[-8mm]\mbox{}\end{tabular}\end{center}\begin{center}\begin{tabular}{@{}p{0.45\textwidth}|p{0.45\textwidth}@{}} \bf sequential version: & \bf parallel version on 4 cores:\smallskip\\ {\hfill\includegraphics[scale=0.11]{../pics/mand4.png}\hfill} & {\hfill\includegraphics[scale=0.11]{../pics/mand3.png}\hfill} \\{\footnotesize\begin{lstlisting}[xleftmargin=-1mm]for (y <- (0 until H)) { for (x <- (0 until W)) { val c = start + (x * d_x + y * d_y * i) val iters = iterations(c, max) val colour = if (iters == max) black else colours(iters % 16) pixel(x, y, colour) } viewer.updateUI()} \end{lstlisting}} & {\footnotesize\begin{lstlisting}[xleftmargin=0mm]for (y <- (0 until H).par) { for (x <- (0 until W).par) { val c = start + (x * d_x + y * d_y * i) val iters = iterations(c, max) val colour = if (iters == max) black else colours(iters % 16) pixel(x, y, colour) } viewer.updateUI()} \end{lstlisting}}\\[-2mm]\centering\includegraphics[scale=0.5]{../pics/cpu2.png} &\centering\includegraphics[scale=0.5]{../pics/cpu1.png}\end{tabular}\end{center}\caption{The code of the ``main'' loops in my version of the mandelbrot program.The parallel version differs only in \texttt{.par} being added to the``ranges'' of the x and y coordinates. As can be seen from the CPU loads, inthe sequential version there is a lower peak for an extended period,while in the parallel version there is a short sharp burst foressentially the same workload\ldots{}meaning you get more work done in a shorter amount of time. This easy \emph{parallelisation} only works reliably with an immutable program.\label{mand}} \end{boxedminipage}\end{figure} But remember this easy parallelisation of code requires that we have nostate in our programs\ldots{}that is no counters like \texttt{i} in\texttt{for}-loops. You might then ask, how do I write loops withoutsuch counters? Well, teaching you that this is possible is one of themain points of the Scala-part in PEP. I can assure you it is possible,but you have to get your head around it. Once you have mastered this, itwill be fun to have no state in your programs (a side product is that itmuch easier to debug state-less code and also more often than not easierto understand). So have fun with Scala!\footnote{If you are still notconvinced about the function programming ``thing'', there are a few morearguments: a lot of research in programming languages happens to takeplace in functional programming languages. This has resulted inultra-useful features such as pattern-matching, strong type-systems,laziness, implicits, algebraic datatypes to name a few. Imperativelanguages seem to often lag behind in adopting them: I know, forexample, that Java will at some point in the future supportpattern-matching, which has been used for example in SML for at least40(!) years. See\url{https://openjdk.org/projects/amber/design-notes/patterns/pattern-matching-for-java}.Automatic garbage collection was included in Java in 1995; thefunctional language LISP had this already in 1958. Generics were addedto Java 5 in 2004; the functional language SML had it since 1990.Higher-order functions were added to C\# in 2007, to Java 8 in2014; again LISP had them since 1958. Also Rust, a C-like programminglanguage that has been developed since 2010 and is gaining quite someinterest, borrows many ideas from functional programming fromyesteryear.}\medskip\noindentIf you need any after-work distractions, you might have fun readingthis about FP (functional programming) --- youmight have to disable your browser cookies though if you want to readit for free. And spoiler alert: This is tongue-in-cheek \texttt{;o)}\begin{quote}\url{https://betterprogramming.pub/fp-toy-7f52ea0a947e}\end{quote}\subsection*{The Very Basics}One advantage of Scala over Java is that it includes an interpreter (aREPL, 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 needof a compiler. This helps a lot with interactively developingprograms. It is my preferred way of writing small Scalaprograms. Once you installed Scala, you can start the interpreter bytyping on the command line:\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]$ scalaWelcome to Scala 2.13.9 (OpenJDK 64-Bit Server VM, Java 17.0.1).Type in expressions for evaluation. Or try :help.scala>\end{lstlisting}%$\noindent The precise response may vary dependingon the version 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 The answer means that he result of the addition is of type\code{Int} and the actual result is 5; \code{res0} is a name thatScala gives automatically to the result. You can reuse this name lateron, for example\begin{lstlisting}[numbers=none]scala> res0 + 4res1: Int = 9\end{lstlisting}\noindentAnother 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. Thereason is that \code{print} does not actually produce a result(there is no \code{resX} 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. It is just not printed by Scala. You can try more examples with the Scala REPL, but feel free tofirst guess what the result is (not all answers by Scala are obvious):\begin{lstlisting}[numbers=none]scala> 2 + 2scala> 1 / 2scala> 1.0 / 2scala> 1 / 2.0scala> 1 / 0scala> 1.0 / 0.0scala> true == falsescala> true && falsescala> 1 > 1.0scala> "12345".lengthscala> List(1,2,1).sizescala> Set(1,2,1).sizescala> List(1) == List(1)scala> Array(1) == Array(1)scala> Array(1).sameElements(Array(1))\end{lstlisting}\noindentAlso observe carefully what Scala responds in the following three instances involving the constant \lstinline!1!---can you explain the differences?\begin{lstlisting}[numbers=none]scala> 1scala> 1Lscala> 1F\end{lstlisting}\smallskip\noindentPlease take the Scala REPL seriously: If you want to take advantage of myreference implementation for the assignments, you will need to beable to ``play around'' with it!\subsection*{Standalone Scala Apps}If you want to write a standalone app in Scala, you canimplement an object that is an instance of \code{App}. For examplewrite\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 (\texttt{scalac}) and start the runtimeenvironment (\texttt{scala}):\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]$ scalac hello-world.scala$ scala Hellohello world\end{lstlisting}\noindentLike Java, 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*{Values}In the lectures I will try to avoid as much as possible the term\emph{variables} familiar from other programming languages. The reasonis that Scala has \emph{values}, which can be seen as abbreviations oflarger expressions. The keyword for defining values is \code{val}.For example\begin{lstlisting}[numbers=none]scala> val x = 42x: Int = 42scala> val y = 3 + 4y: Int = 7scala> val z = x / yz: Int = 6\end{lstlisting}\noindentAs can be seen, we first define \code{x} and {y} with admittedly some sillyexpressions, and then reuse these values in the definition of \code{z}.All easy, right? Why the kerfuffle about values? Well, values are\emph{immutable}. You cannot change their value after you defined them.If you try to reassign \code{z} above, Scala will yell at you:\begin{lstlisting}[numbers=none]scala> z = 9error: reassignment to val z = 9 ^\end{lstlisting}\noindentSo it would be a bit absurd to call values as variables...you cannotchange them; they cannot vary. You might think you can reassign them like\begin{lstlisting}[numbers=none]scala> val x = 42scala> val z = x / 7scala> val x = 70scala> println(z) \end{lstlisting}\noindent but try to guess what Scala will print out for \code{z}? Will it be \code{6} or \code{10}? A final word aboutvalues: Try to stick to the convention that names of values should belower case, like \code{x}, \code{y}, \code{foo41} and so on. Upper-casenames you should reserve for what is called \emph{constructors}. And forgive me when I call values as variables\ldots{}it is just something thathas been in imprinted into my developer-DNA during my early days andis difficult to get rid of.~\texttt{;o)} \subsection*{Function Definitions}We do functional programming! So defining functions will be our main occupation.As an example, a function named \code{f} taking a single argument of type \code{Int} can be defined in Scala as follows:\begin{lstlisting}[numbers=none]def f(x: Int) : String = ...EXPR...\end{lstlisting} \noindentThis function returns the value resulting from evaluating the expression\code{EXPR} (whatever is substituted for this). Since we declared\code{String}, the result of this function will be of type\code{String}. It is a good habit to always include this informationabout the return type, while it is only strictly necessary to give thistype in recursive functions. Simple examples of Scala functions are:\begin{lstlisting}[numbers=none]def incr(x: Int) : Int = x + 1def double(x: Int) : Int = x + xdef square(x: Int) : Int = x * x\end{lstlisting}\noindentThe general scheme for a function is\begin{lstlisting}[numbers=none]def fname(arg1: ty1, arg2: ty2,..., argn: tyn): rty = { ...BODY...}\end{lstlisting}\noindentwhere each argument, \texttt{arg1}, \texttt{arg2} and so on, requires its type and the result type of thefunction, \code{rty}, should also be given. If the body of the function ismore complex, then it can be enclosed in braces, like above. If it itis just a simple expression, like \code{x + 1}, you can omit thebraces. Very often functions are recursive (that is call themselves),like the venerable factorial function:\begin{lstlisting}[numbers=none]def fact(n: Int) : Int = if (n == 0) 1 else n * fact(n - 1)\end{lstlisting}\noindentWe could also have written this with braces as\begin{lstlisting}[numbers=none]def fact(n: Int) : Int = { if (n == 0) 1 else n * fact(n - 1)} \end{lstlisting}\noindentbut this seems a bit overkill for a small function like \code{fact}.Note that Scala does not have a \code{then}-keyword in an\code{if}-statement. Also important is that there should be always an\code{else}-branch. Never write an \code{if} without an \code{else},unless you know what you are doing! While \code{def} is the mainmechanism for defining functions, there are a few other ways for doingthis. We will see some of them in the next sections.Before we go on, let me explain one tricky point in functiondefinitions, especially in larger definitions. What does a Scalafunction return as result? Scala has a \code{return} keyword, but it isused for something different than in Java (and C/C++). Therefore pleasemake sure no \code{return} slips into your Scala code.So in the absence of \code{return}, what value does a Scala functionactually produce? A rule-of-thumb is whatever is in the last line of thefunction is the value that will be returned. Consider the followingexample:\footnote{We could have written this function in just one line,but for the sake of argument lets keep the two intermediate values.}\begin{lstlisting}[numbers=none]def average(xs: List[Int]) : Int = { val s = xs.sum val n = xs.length s / n} \end{lstlisting}\noindent In this example the expression \code{s / n} is in the lastline of the function---so this will be the result the functioncalculates. The two lines before just calculate intermediate values.This principle of the ``last-line'' comes in handy when you need toprint out values, for example, for debugging purposes. Suppose you wantrewrite the function as\begin{lstlisting}[numbers=none]def average(xs: List[Int]) : Int = { val s = xs.sum val n = xs.length val h = xs.head println(s"Input $xs with first element $h") s / n} \end{lstlisting}\noindentHere the function still only returns the expression in the last line.The \code{println} before just prints out some information about theinput of this function, but does not contribute to the result of thefunction. Similarly, the value \code{h} is used in the \code{println}but does not contribute to what integer is returned. A caveat is that the idea with the ``last line'' is only a roughrule-of-thumb. A better rule might be: the last expression that isevaluated in the function. Consider the following version of\code{average}:\begin{lstlisting}[numbers=none]def average(xs: List[Int]) : Int = { if (xs.length == 0) 0 else xs.sum / xs.length} \end{lstlisting}\noindentWhat does this function return? Well there are two possibilities: eitherthe result of \code{xs.sum / xs.length} in the last line provided thelist \code{xs} is nonempty, \textbf{or} if the list is empty, then itwill return \code{0} from the \code{if}-branch (which is technically notthe last line, but the last expression evaluated by the function in theempty-case).Summing up, do not use \code{return} in your Scala code! A functionreturns what is evaluated by the function as the last expression. Thereis always only one such last expression. Previous expressions mightcalculate intermediate values, but they are not returned. If yourfunction is supposed to return multiple things, then one way in Scala isto use tuples. For example returning the minimum, average and maximumcan be achieved by\begin{lstlisting}[numbers=none]def avr_minmax(xs: List[Int]) : (Int, Int, Int) = { if (xs.length == 0) (0, 0, 0) else (xs.min, xs.sum / xs.length, xs.max)} \end{lstlisting}\noindentwhich still satisfies the rule-of-thumb.\subsection*{Loops, or Better the Absence Thereof}Coming from Java or C/C++, you might be surprised that Scala 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 corresponding 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 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 each element istransformed (in this example the function is $n \rightarrow n * n$) anda list over which this function should work. Pictorially you can thinkof the idea behind maps as follows:\begin{center}\begin{tikzpicture} \node (A0) at (1.2,0) {\texttt{List(}}; \node (A1) at (2.0,0) {\texttt{1\makebox[0mm]{ ,}}}; \node (A2) at (2.9,0) {\texttt{2\makebox[0mm]{ ,}}}; \node (A3) at (3.8,0) {\texttt{3\makebox[0mm]{ ,}}}; \node (A4) at (4.7,0) {\texttt{4\makebox[0mm]{ ,}}}; \node (A5) at (5.6,0) {\texttt{5\makebox[0mm]{ ,}}}; \node (A6) at (6.5,0) {\texttt{6\makebox[0mm]{ ,}}}; \node (A7) at (7.4,0) {\texttt{7\makebox[0mm]{ ,}}}; \node (A8) at (8.3,0) {\texttt{8)}}; \node (B0) at (1.2,-3) {\texttt{List(}}; \node (B1) at (2.0,-3) {\texttt{1\makebox[0mm]{ ,}}}; \node (B2) at (3.0,-3) {\texttt{4\makebox[0mm]{ ,}}}; \node (B3) at (4.1,-3) {\texttt{9\makebox[0mm]{ ,}}}; \node (B4) at (5.2,-3) {\texttt{16\makebox[0mm]{ ,}}}; \node (B5) at (6.3,-3) {\texttt{25\makebox[0mm]{ ,}}}; \node (B6) at (7.4,-3) {\texttt{36\makebox[0mm]{ ,}}}; \node (B7) at (8.4,-3) {\texttt{49\makebox[0mm]{ ,}}}; \node (B8) at (9.4,-3) {\texttt{64\makebox[0mm]{ )}}}; \draw [->,line width=1mm] (A1.south) -- (B1.north); \draw [->,line width=1mm] (A2.south) -- (B2.north); \draw [->,line width=1mm] (A3.south) -- (B3.north); \draw [->,line width=1mm] (A4.south) -- (B4.north); \draw [->,line width=1mm] (A5.south) -- (B5.north); \draw [->,line width=1mm] (A6.south) -- (B6.north); \draw [->,line width=1mm] (A7.south) -- (B7.north); \draw [->,line width=1mm] (A8.south) -- (B8.north); \node [red] (Q0) at (-0.3,-0.3) {\large\texttt{n}}; \node (Q1) at (-0.3,-0.4) {}; \node (Q2) at (-0.3,-2.5) {}; \node [red] (Q3) at (-0.3,-2.65) {\large\texttt{n\,*\,n}}; \draw [->,red,line width=1mm] (Q1.south) -- (Q2.north); \node [red] at (-1.3,-1.5) {\huge{}\it\textbf{map}}; \end{tikzpicture}\end{center}\noindentOn top is the ``input'' list we want to transform; on the left is the``map'' function for how to transform each element in the input list(the square function in this case); at the bottom is the result list ofthe map. This means that a map generates a \emph{new} list, unlike afor-loop in Java or C/C++ which would most likely just update theexisting list/array.Now there are two ways for expressing such maps in Scala. The first way iscalled a \emph{for-comprehension}. The keywords are \code{for} and\code{yield}. Squaring the numbers from 1 to 8 with a for-comprehensionwould look 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 This for-comprehension states that from the list of numberswe draw some elements. We use the name \code{n} to range over theseelements (whereby the name is arbitrary; we could use something moredescriptive if we wanted to). Using \code{n} we compute the result of\code{n * n} after the \code{yield}. This way of writing a map resemblesa bit the for-loops from imperative languages, even though the ideasbehind for-loops and for-comprehensions are quite different. Also, thisis a simple example---what comes after \code{yield} can be a complexexpression enclosed in \texttt{\{...\}}. A more complicated examplemight be\begin{lstlisting}[numbers=none]scala> for (n <- (1 to 8).toList) yield { val i = n + 1 val j = n - 1 i * j + 1 }res3: List[Int] = List(1, 4, 9, 16, 25, 36, 49, 64)\end{lstlisting}As you can see in for-comprehensions above, we specified the list whereeach \code{n} comes from, namely \code{(1 to 8).toList}, and how eachelement needs to be transformed. This can also be expressed in a secondway in Scala by using directly the function \code{map} 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 thefunction that calculates the square (this is how the \code{n}s aretransformed by the map). It might not be obvious, butthe for-comprehensions above are just syntactic sugar: when compiling suchcode, Scala translates for-comprehensions into equivalent maps. Thiseven works when 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 data collection, suchas lists, sets, vectors, options and so on. For example if we insteadcompute the remainders 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 notinto a list, but into a set, and then compute the remaindersmodulo 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\footnote{This returns actually \code{HashSet(2, 1, 3)},but this is just an implementation detail of how sets are implemented inScala.} is the correct result for sets, as there are only threeequivalence classes of integers modulo 3. Note that in this example weneed to ``help'' Scala to transform the numbers into a set of integersby explicitly annotating the type \code{Int}. Since maps andfor-comprehensions are just syntactic variants of each other, the lattercan also be written 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 In this example the for-comprehension ranges over two lists, andproduces a list of pairs as output. Or, if we want to find all pairs ofnumbers between 1 and 3 where the sum is an even number, we can write\begin{lstlisting}[numbers=none]scala> for (n <- (1 to 3).toList; m <- (1 to 3).toList; if (n + m) % 2 == 0) yield (n, m)res7 = List((1,1), (1,3), (2,2), (3,1), (3,3))\end{lstlisting}\noindent The \code{if}-condition in this for-comprehension filters outall pairs where the sum is not even (therefore \code{(1, 2)}, \code{(2,1)} and \code{(3, 2)} are not in the result because their sum is odd). To summarise, maps (or for-comprehensions) transform one collection intoanother. For example a list of \code{Int}s into a list of squares, andso on. There is no need for for-loops in Scala. But please do not betempted to write anything like\begin{lstlisting}[numbers=none]scala> val cs = ('a' to 'h').toListscala> for (n <- (0 until cs.length).toList) yield cs(n).capitalizeres8: List[Char] = List(A, B, C, D, E, F, G, H)\end{lstlisting}\noindentThis is accepted Scala-code, but utterly bad style (it is more likeJava). It can be written much clearer as:\begin{lstlisting}[numbers=none]scala> val cs = ('a' to 'h').toListscala> for (c <- cs) yield c.capitalizeres9: List[Char] = List(A, B, C, D, E, F, G, H)\end{lstlisting}\subsection*{Results and Side-Effects}While hopefully all this about maps looks reasonable, there is onecomplication: In the examples above we always wanted to transform onelist into another list (e.g.~list of squares), or one set into anotherset (set of numbers into set of remainders modulo 3). What happens if wejust want to print out a list of integers? In these cases thefor-comprehensions need to be modified. The reason is that \code{print},you guessed it, does not produce any result, but only produces what isin the functional-programming-lingo called a \emph{side-effect}\ldots itprints something out on the screen. Printing out the list of numbersfrom 1 to 5 would 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 println(s"$n * $n = $square") }1 * 1 = 12 * 2 = 43 * 3 = 94 * 4 = 165 * 5 = 25\end{lstlisting}%$\noindent In this code I use a value assignment (\code{valsquare = ...} ) 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} 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 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*{Aggregates}There is one more usage of for-loops in Java, C/C++ and the like:sometimes you want to \emph{aggregate} something about a list, forexample summing up all its elements. In this case you cannot use maps,because maps \emph{transform} one data collection into another datacollection. They cannot be used to generate a single integerrepresenting an aggregate. So how is this kind of aggregation done inScala? Let us suppose you want to sum up all elements from a list. Youmight be tempted to write something like\begin{lstlisting}[numbers=none]var cnt = 0for (n <- (1 to 8).toList) { cnt += n}print(cnt)\end{lstlisting}\noindentand indeed this is accepted Scala code and produces the expected result,namely \code{36}, \textbf{BUT} this is imperative style and notpermitted in PEP. If you submit this kind of code, you get 0 marks. Thecode uses a \code{var} and therefore violates the immutability propertyI ask for in your code. Sorry!So how to do that same thing without using a \code{var}? Well there areseveral ways. One way is to define the following recursive\code{sum}-function:\begin{lstlisting}[numbers=none]def sum(xs: List[Int]) : Int = if (xs.isEmpty) 0 else xs.head + sum(xs.tail)\end{lstlisting} \noindentYou can then call \code{sum((1 to 8).toList)} and obtain the same resultwithout a mutable variable and without a for-loop. Obviously for simple things likesum, you could have written \code{xs.sum} in the first place. But notall aggregate functions are pre-defined and often you have to write yourown recursive function for this.%\subsection*{Always Produce a Result! No Exceptions!}%%Function should always produce a value. Exception is not thrown.%Whenever there is a possibility of non-value result (exception, void,%undefined, null, etc.), it should be incorporated in the result type.%Such types include but not limited to%%Option[T]%TBD\subsection*{Higher-Order Functions}Functions obviously play a central role in functional programming. Two simpleexamples are\begin{lstlisting}[numbers=none]def even(x: Int) : Boolean = x % 2 == 0def odd(x: Int) : Boolean = x % 2 == 1\end{lstlisting} \noindentMore interestingly, the concept of functions is really pushed to thelimit in functional programming. Functions can take other functions asarguments and can return a function as a result. This is actuallyquite important for making code generic. Assume a list of 10 elements:\begin{lstlisting}[numbers=none]val lst = (1 to 10).toList \end{lstlisting} \noindent Say, we want to filter out all even numbers. For this we can use \begin{lstlisting}[numbers=none]scala> lst.filter(even)List(2, 4, 6, 8, 10)\end{lstlisting} \noindentwhere \code{filter} expects a function as argument specifying whichelements of the list should be kept and which should be left out. Byallowing \code{filter} to take a function as argument, we can alsoeasily filter out odd numbers as well.\begin{lstlisting}[numbers=none]scala> lst.filter(odd)List(1, 3, 5, 7, 9)\end{lstlisting} \noindentSuch function arguments are quite frequently used for ``generic'' functions.For example it is easy to count odd elements in a list or find the firsteven number in a list:\begin{lstlisting}[numbers=none]scala> lst.count(odd)5scala> lst.find(even)Some(2)\end{lstlisting} \noindentRecall that the return type of \code{even} and \code{odd} are booleans.Such function are sometimes called predicates, because they determinewhat should be true for an element and what false, and then performingsome operation according to this boolean. Such predicates are quite useful. Say you want to sort the \code{lst}-list in ascending and descending order. For this you can write\begin{lstlisting}[numbers=none]lst.sortWith(_ < _)lst.sortWith(_ > _)\end{lstlisting} \noindent where \code{sortWith} expects a predicate as argument. Theconstruction \code{_ < _} stands for a function that takes two argumentsand returns true when the first one is smaller than the second. You canthink of this as elegant shorthand notation for \begin{lstlisting}[numbers=none]def smaller(x: Int, y: Int) : Boolean = x < ylst.sortWith(smaller)\end{lstlisting} \noindentSay you want to find in \code{lst} the first odd number greater than 2.For this you need to write a function that specifies exactly thiscondition. To do this you can use a slight variant of the shorthandnotation above\begin{lstlisting}[numbers=none]scala> lst.find(n => odd(n) && n > 2)Some(3)\end{lstlisting} \noindentHere \code{n => ...} specifies a function that takes \code{n} asargument and uses this argument in whatever comes after the doublearrow. If you want to use this mechanism for looking for an element thatis both even and odd, then of course you out of luck.\begin{lstlisting}[numbers=none]scala> lst.find(n => odd(n) && even(n))None\end{lstlisting} While functions taking functions as arguments seems a rather usefulfeature, the utility of returning a function might not be so clear. I admit the following example is a bit contrived, but believe mesometims functions produce other functions in a very meaningful way.Say we want to generate functions according to strings, as in\begin{lstlisting}[numbers=none]def mkfn(s: String) : (Int => Boolean) = if (s == "even") even else odd\end{lstlisting}\noindentWith this we can generate the required function for \code{filter}according to a string:\begin{lstlisting}[numbers=none]scala> lst.filter(mkfn("even"))List(2, 4, 6, 8, 10)scala> lst.filter(mkfn("foo"))List(1, 3, 5, 7, 9)\end{lstlisting}\noindentAs said, this is example is a bit contrived---I was not able to thinkof anything simple, but for example in the Compiler module next year Ishow a compilation functions that needs to generate functions asintermediate result. Anyway, notice the interesting type we had toannotate to \code{mkfn}. Types of Scala are described next.\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} (see coursework). 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 remainder 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, its\emph{return type} needs to be of type \code{(Int, Int)}. Incidentally,this is also the \emph{input type} of this function. For this notice\code{quo_rem} 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}\noindentThis uses another special type-constructor, written as the arrow\code{=>}. This is sometimes also called \emph{function arrow}. Forexample, the type \code{Int => String} is for a function that takes aninteger as input argument and produces a string as result. A functionof 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 astring. The type of the function generated in \code{mkfn} above, is\code{Int => Boolean}.Unfortunately, unlike other functional programming languages, there isin Scala no easy way to find out the types of existing functions, exceptby 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 and successors was to lift thisrestriction. But in all functional programming languages,including Scala, it is really essential to allow functions asinput argument. Above you have already seen \code{map} and\code{foreach} which need this feature. Consider the functions\code{print} and \code{println}, which both print out strings,but the latter adds a line break. You can call \code{foreach}with either of them and thus changing how, for example, 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 interesting topic abouttypes, but we omit it here for the sake of brevity.} There is one more type constructor that is rather special. It iscalled \code{Unit}. Recall that \code{Boolean} has two values, namely\code{true} and \code{false}. This can be used, for example, to testsomething and decide whether the test succeeds or not. In contrast thetype \code{Unit} has only a single value, written \code{()}. Thisseems like a completely useless type and return value for a function,but is actually quite useful. It indicates when the function does notreturn any result. The purpose of these functions is to causesomething being written on the screen or written into a file, forexample. This is what is called they cause a \emph{side-effect}, forexample new content displayed on the screen or some new data in afile. Scala uses the \code{Unit} type to indicate that a function doesnot have a result, but potentially causes a side-effect. Typicalexamples are the printing functions, like \code{print}.%%\subsection*{User-Defined Types}% \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.%\bigskip\noindent%\textit{More TBD.}%\subsection*{Coursework}\begin{figure}[p]\begin{boxedminipage}{\textwidth} \textbf{Scala Syntax for Java Developers}\bigskip\noindentScala compiles to the JVM, like the Java language. Because of this,it can re-use many libraries. Here are a few hints how some Java codetranlsates to Scala code:\bigskip\noindentVariable declaration:\begin{lstlisting}[language=Java]Drink coke = getCoke();/*!\annotation{Java}!*/\end{lstlisting}\begin{lstlisting}[language=Scala]val coke : Drink = getCoke()/*!\annotation{Scala}!*/\end{lstlisting}\noindentor even\begin{lstlisting}[language=Scala]val coke = getCoke()/*!\annotation{Scala}!*/\end{lstlisting}\bigskip\noindentUnit means void:\begin{lstlisting}[language=Java]public void output(String s) {/*!\annotation{Java}!*/ System.out.println(s);}\end{lstlisting}\begin{lstlisting}[language=Scala]def output(s: String): Unit = println(s)/*!\annotation{Scala}!*/\end{lstlisting}\bigskip\noindentType for list of Strings:\begin{lstlisting}[language=Java]List<String>/*!\annotation{Java}!*/\end{lstlisting}\begin{lstlisting}[language=Scala]List[String]/*!\annotation{Scala}!*/\end{lstlisting}\bigskip\noindentString interpolations\begin{lstlisting}[language=Java]System.out.println("Hello, "+ first + " "+ last + "!");/*!\annotation{Java}!*/\end{lstlisting}\begin{lstlisting}[language=Scala]println(s"Hello, $first $last!")/*!\annotation{Scala}!*/\end{lstlisting}\bigskip\noindentJava provides some syntactic sugar when constructing anonymous functions:\begin{lstlisting}[language=Java]list.foreach(item -> System.out.println("* " + item));/*!\annotation{Java}!*/\end{lstlisting}\noindentIn Scala, we use the \code{=>} symbol for the same:\begin{lstlisting}[language=Scala]list.foreach(item => println(s"* $item"))/*!\annotation{Scala}!*/\end{lstlisting}%$\end{boxedminipage}\end{figure}%%new / vs case classes\subsection*{More Info}There is much more to Scala than I can possibly describe inthis document and teach in the lectures. 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}\item \url{https://twitter.github.io/scala_school}\end{itemize}\noindent There is also an online 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-profile companies,there is also a company (Yammer) that first used Scala in theirproduction code, but then moved away from it. Allegedly they did notlike the steep learning curve of Scala and also that new versions ofScala often introduced incompatibilities in old code. Also the Javalanguage is lately developing at lightening speed (in comparison to the past) taking on manyfeatures of Scala and other languages, and it seems it even introducesnew features on its own.Scala is deep: After many years, I still continue to learn new techniquefor writing more elegant code. Unfortunately, I have not yet managed toswitch over my code to Scala 3.0 due to time constraints. Scala 3 seemsto iron out a number of snags from Scala 2, but why on earth are theyintroducing Python-esque indentation and why on earth are theyre-introducing the \texttt{then}-keyword in Scala 3, when I just about gotcomfortable without it? %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.\subsection*{Conclusion}I hope you liked the short journey through the Scala language---but remember we like you to take on board the functional programming point of view,rather than just learning another language. There is an interestingblog article about Scala by a convert:\begin{center}\url{https://www.skedulo.com/tech-blog/technology-scala-programming/}\end{center} \noindentHe makes pretty much the same arguments about functional programming andimmutability (one section is teasingly called \textit{``Where Did allthe Bugs Go?''}). If you happen to moan about all the idiotic featuresof Scala, well, I guess this is part of the package according to thisquote:\bigskip%\begin{itemize}%\item no exceptions....there two kinds, one ``global'' exceptions, like%out of memory (not much can be done about this by the ``individual''%programmer); and ``local one'' open a file that might not exists - in%the latter you do not want to use exceptions, but Options%\end{itemize}\begin{flushright}\itThere are only two kinds of languages: the ones people complain about\\ and the ones nobody uses.\smallskip\\\mbox{}\hfill\small{}---Bjarne Stroustrup (the inventor of C++)\end{flushright}\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: