# HG changeset patch # User Christian Urban # Date 1647909378 0 # Node ID 94b84d880c2b905c9f381eb8da244c816d1b6e22 # Parent 739039774ceeb89d0df4171c9fd39a1675a4dabd updated diff -r 739039774cee -r 94b84d880c2b cws/cw01.pdf Binary file cws/cw01.pdf has changed diff -r 739039774cee -r 94b84d880c2b cws/cw02.pdf Binary file cws/cw02.pdf has changed diff -r 739039774cee -r 94b84d880c2b cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r 739039774cee -r 94b84d880c2b cws/cw04.pdf Binary file cws/cw04.pdf has changed diff -r 739039774cee -r 94b84d880c2b cws/cw05.pdf Binary file cws/cw05.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/amm-ho.pdf Binary file handouts/amm-ho.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/graphs.pdf Binary file handouts/graphs.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/ho01.pdf Binary file handouts/ho01.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/ho01.tex --- a/handouts/ho01.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/handouts/ho01.tex Tue Mar 22 00:36:18 2022 +0000 @@ -2,7 +2,7 @@ \documentclass{article} \usepackage{../style} \usepackage{../langs} -\usepackage{../graphics} +\usepackage{../graphicss} \usepackage{../data} \usepackage{lstlinebgrd} \definecolor{capri}{rgb}{0.0, 0.75, 1.0} diff -r 739039774cee -r 94b84d880c2b handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/ho04.pdf Binary file handouts/ho04.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/ho05-bak.tex --- a/handouts/ho05-bak.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/handouts/ho05-bak.tex Tue Mar 22 00:36:18 2022 +0000 @@ -22,7 +22,7 @@ be written in this language as follows: \begin{center} -\mbox{\lstinputlisting[language=while]{../progs/fib.while}} +\mbox{\lstinputlisting[language=while]{../progs/while-tests/fib.while}} \end{center} \noindent diff -r 739039774cee -r 94b84d880c2b handouts/ho05.pdf Binary file handouts/ho05.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/ho06.pdf Binary file handouts/ho06.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/ho07.pdf Binary file handouts/ho07.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/ho08.pdf Binary file handouts/ho08.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/ho09.pdf Binary file handouts/ho09.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/ho10.pdf Binary file handouts/ho10.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/ho10.tex --- a/handouts/ho10.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/handouts/ho10.tex Tue Mar 22 00:36:18 2022 +0000 @@ -584,12 +584,12 @@ interpreter, though the implementation is admittedly no frills. -\begin{figure}[t] -\small -\lstinputlisting[language=Scala]{../progs/inter.scala} -\caption{The entire code of the interpreter for our -idealised programming language.\label{code}} -\end{figure} +%\begin{figure}[t] +%\small +%\lstinputlisting[language=Scala]{../progs/inter.scala} +%\caption{The entire code of the interpreter for our +%idealised programming language.\label{code}} +%\end{figure} \subsubsection*{Static Analysis} diff -r 739039774cee -r 94b84d880c2b handouts/notation.pdf Binary file handouts/notation.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/scala-ho.pdf Binary file handouts/scala-ho.pdf has changed diff -r 739039774cee -r 94b84d880c2b handouts/scala-ho.tex --- a/handouts/scala-ho.tex Mon Jan 24 00:14:02 2022 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1016 +0,0 @@ -\documentclass{article} -\usepackage{../style} -\usepackage{../langs} -\usepackage{marvosym} - -%cheat sheet -%http://worldline.github.io/scala-cheatsheet/ - -\begin{document} - -\section*{A Crash-Course on Scala} - -Scala is a programming language that combines functional and -object-oriented programming-styles. It has received quite a -bit of attention in the last five years or so. One reason for -this attention is that, like the Java programming language, -Scala compiles to the Java Virtual Machine (JVM) and therefore -Scala programs can run under MacOSX, Linux and -Windows.\footnote{There are also experimental backends for -Android and JavaScript; and also work is under way to have a -native compiler, see \url{https://github.com/scala-native/scala-native}.} Unlike Java, however, Scala often -allows programmers to write very concise and elegant code. -Some therefore say: Scala is the much better Java. A number of -companies, The Guardian, Twitter, Coursera, FourSquare, -LinkedIn to name a few, either use Scala exclusively in -production code, or at least to some substantial degree. It -also seems to be useful in job-interviews (in Data Science) -according to this annectotical report - -\begin{quote} -\url{https://techcrunch.com/2016/06/14/scala-is-the-new-golden-child/} -\end{quote} - -\noindent -If you want to try out Scala yourself, the official Scala compiler can be -downloaded from - -\begin{quote} -\url{http://www.scala-lang.org} -\end{quote} - -\noindent -A ready-made bundle with the Eclipse IDE is at - -\begin{quote} -\url{http://scala-ide.org/download/sdk.html} -\end{quote} - -Why do I use Scala in the AFL module? Actually, you can do -\emph{any} part of the coursework in \emph{any} programming -language you like. I use Scala for showing you code during the -lectures because its functional programming-style allows me to -implement the functions we will discuss with very small -code-snippets. If I had to do this in Java, I would first have -to go through heaps of boilerplate code and the code-snippets -would not look pretty. Since the Scala compiler is free, you -can download the code-snippets and run every example I give. -But if you prefer, you can also easily translate them into any -other functional language, for example Haskell, Swift, -Standard ML, F$^\#$, Ocaml and so on. - -Developing programs in Scala can be done with the Eclipse IDE -and also with the IntelliJ IDE, but for the small programs I will -develop the good old Emacs-editor is adequate for me and I -will run the programs on the command line. One advantage of -Scala over Java is that it includes an interpreter (a REPL, or -\underline{R}ead-\underline{E}val-\underline{P}rint-\underline{L}oop) -with which you can run and test small code-snippets without -the need of the compiler. This helps a lot with interactively -developing programs. Once you installed Scala, you can start -the interpreter by typing on the command line: - -\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] -$ scala -Welcome to Scala version 2.11.8 (Java HotSpot(TM) 64-Bit Server VM). -Type in expressions for evaluation. Or try :help. - -scala> -\end{lstlisting} - -\noindent Of course the precise response may vary due to the -version and platform where you installed Scala. At the Scala -prompt you can type things like \code{2 + 3} \keys{Ret} and -the output will be - -\begin{lstlisting}[numbers=none] -scala> 2 + 3 -res0: Int = 5 -\end{lstlisting} - -\noindent indicating that the result of the addition is of -type \code{Int} and the actual result is 5. Another classic -example you can try out is - -\begin{lstlisting}[numbers=none] -scala> print("hello world") -hello world -\end{lstlisting} - -\noindent Note that in this case there is no result. The -reason is that \code{print} does not actually produce a result -(there is no \code{resXX} and no type), rather it is a -function that causes the \emph{side-effect} of printing out a -string. Once you are more familiar with the functional -programming-style, you will know what the difference is -between a function that returns a result, like addition, and a -function that causes a side-effect, like \code{print}. We -shall come back to this point later, but if you are curious -now, the latter kind of functions always has \code{Unit} as -return type. - -If you want to write a stand-alone app in Scala, you can -implement an object that is an instance of \code{App}, say - -\begin{lstlisting}[numbers=none] -object Hello extends App { - println("hello world") -} -\end{lstlisting} - -\noindent save it in a file, say {\tt hello-world.scala}, and -then run the compiler and runtime environment: - -\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] -$ scalac hello-world.scala -$ scala Hello -hello world -\end{lstlisting} - -As mentioned above, Scala targets the JVM and consequently -Scala programs can also be executed by the bog-standard Java -Runtime. This only requires the inclusion of {\tt -scala-library.jar}, which on my computer can be done as -follows: - -\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] -$ scalac hello-world.scala -$ java -cp /usr/local/src/scala/lib/scala-library.jar:. Hello -hello world -\end{lstlisting} - -\noindent You might need to adapt the path to where you have -installed Scala. - -\subsection*{Inductive Datatypes} - -The elegance and conciseness of Scala programs are often a -result of inductive datatypes that can be easily defined in -Scala. For example in ``every-day mathematics'' we define -regular expressions simply by giving the grammar - -\begin{center} -\begin{tabular}{r@{\hspace{2mm}}r@{\hspace{2mm}}l@{\hspace{13mm}}l} - $r$ & $::=$ & $\ZERO$ & null\\ - & $\mid$ & $\ONE$ & empty string\\ - & $\mid$ & $c$ & single character\\ - & $\mid$ & $r_1 \cdot r_2$ & sequence\\ - & $\mid$ & $r_1 + r_2$ & alternative / choice\\ - & $\mid$ & $r^\star$ & star (zero or more)\\ - \end{tabular} -\end{center} - -\noindent This grammar specifies what regular expressions are -(essentially a kind of tree-structure with three kinds of -inner nodes---sequence, alternative and star---and three kinds -of leave nodes---null, empty and character). If you are -familiar with Java, it might be an instructive exercise to -define this kind of inductive datatypes in Java\footnote{Happy -programming! \Smiley} and then compare it with how it can be -implemented in Scala. - -Implementing the regular expressions from above in Scala is -actually very simple: It first requires an \emph{abstract -class}, say, \code{Rexp}. This will act as the type for -regular expressions. Second, it requires a case for each -clause in the grammar. The cases for $\ZERO$ and $\ONE$ do not -have any arguments, while in all the other cases we do have -arguments. For example the character regular expression needs -to take as an argument the character it is supposed to -recognise. In Scala, the cases without arguments are called -\emph{case objects}, whereas the ones with arguments are -\emph{case classes}. The corresponding Scala code is as -follows: - -\begin{lstlisting}[numbers=none] -abstract class Rexp -case object ZERO extends Rexp -case object ONE extends Rexp -case class CHAR (c: Char) extends Rexp -case class SEQ (r1: Rexp, r2: Rexp) extends Rexp -case class ALT (r1: Rexp, r2: Rexp) extends Rexp -case class STAR (r: Rexp) extends Rexp -\end{lstlisting} - -\noindent In order to be an instance of \code{Rexp}, each case -object and case class needs to extend \code{Rexp}. Given the -grammar above, I hope you can see the underlying pattern. If -you want to play further with such definitions of inductive -datatypes, feel free to define for example binary trees. - -Once you make a definition like the one above in Scala, you -can represent the regular expression for $a + b$, for example, -as \code{ALT(CHAR('a'), CHAR('b'))}. Expressions such as -\code{'a'} stand for ASCII characters, though in the output -syntax, as you can see below, the quotes are omitted. In a -later section we will see how we can support the more -mathematical infix notation for regular expression operators -in Scala. If you want to assign this regular expression to a -variable, you can use the keyword \code{val} and type - -\begin{lstlisting}[numbers=none] -scala> val r = ALT(CHAR('a'), CHAR('b')) -r: ALT = ALT(CHAR(a),CHAR(b)) -\end{lstlisting} - -\noindent As you can see, in order to make such assignments, -no \code{new} or constructor is required in the class (as in -Java). However, if there is the need for some non-standard -initialisation, you can of course define such a constructor in -Scala too. But we omit such ``tricks'' here. - -Note that Scala in its response says the variable \code{r} is -of type \code{ALT}, not \code{Rexp}. This might be a bit -unexpected, but can be explained as follows: Scala always -tries to find the most general type that is needed for a -variable or expression, but does not ``over-generalise''. In -our definition the type \code{Rexp} is more general than -\code{ALT}, since it is the abstract class for all regular -expressions. But in this particular case there is no need to -give \code{r} the more general type of \code{Rexp}. This is -different if you want to form a list of regular expressions, -for example - -\begin{lstlisting}[numbers=none] -scala> val ls = List(ALT(CHAR('a'), CHAR('b')), ZERO) -ls: List[Rexp] = List(ALT(CHAR(a),CHAR(b)), ZERO) -\end{lstlisting} - -\noindent In this case, Scala needs to assign a common type to -the regular expressions so that it is compatible with the -fact that lists can only contain elements of a single type. In -this case the first common type is \code{Rexp}.\footnote{If you -type in this example, you will notice that the type contains -some further information, but let us ignore this for the -moment.} - -For compound types like \code{List[...]}, the general rule is -that when a type takes another type as argument, then this -argument type is written in angle-brackets. This can also -contain nested types as in \code{List[Set[Rexp]]}, which is a -list of sets each of which contains regular expressions. - -\subsection*{Functions and Pattern-Matching} - -I mentioned above that Scala is a very elegant programming -language for the code we will write in this module. This -elegance mainly stems from the fact that in addition to -inductive datatypes, also functions can be implemented very -easily in Scala. To show you this, let us first consider a -problem from number theory, called the \emph{Collatz-series}, -which corresponds to a famous unsolved problem in -mathematics.\footnote{See for example -\url{http://mathworld.wolfram.com/CollatzProblem.html}.} -Mathematicians define this series as: - -\[ -collatz_{n + 1} \dn -\begin{cases} -\frac{1}{2} * collatz_n & \text{if $collatz_n$ is even}\\ -3 * collatz_n + 1 & \text{if $collatz_n$ is odd} -\end{cases} -\] - -\noindent The famous unsolved question is whether this -series started with any $n > 0$ as $collatz_0$ will always -return to $1$. This is obvious when started with $1$, and also -with $2$, but already needs a bit of head-scratching for the -case of $3$. - -If we want to avoid the head-scratching, we could implement -this as the following function in Scala: - -\lstinputlisting[numbers=none]{../progs/collatz.scala} - -\noindent The keyword for function definitions is \code{def} -followed by the name of the function. After that you have a -list of arguments (enclosed in parentheses and separated by -commas). Each argument in this list needs its type to be -annotated. In this case we only have one argument, which is of -type \code{BigInt}. This type stands in Scala for arbitrary -precision integers (in case you want to try out the function -on really big numbers). After the arguments comes the type of -what the function returns---a Boolean in this case for -indicating that the function has reached 1. Finally, after the -\code{=} comes the \emph{body} of the function implementing -what the function is supposed to do. What the \code{collatz} -function does should be pretty self-explanatory: the function -first tests whether \code{n} is equal to 1 in which case it -returns \code{true} and so on. - -Notice the quirk in Scala's syntax for \code{if}s: The condition -needs to be enclosed in parentheses and the then-case comes -right after the condition---there is no \code{then} keyword in -Scala. - -The real power of Scala comes, however, from the ability to -define functions by \emph{pattern matching}. In the -\code{collatz} function above we need to test each case using a -sequence of \code{if}s. This can be very cumbersome and brittle -if there are many cases. If we wanted to define a function -over regular expressions in Java, for example, which does not -have pattern-matching, the resulting code would just be -awkward. - -Mathematicians already use the power of pattern-matching when -they define the function that takes a regular expression and -produces another regular expression that can recognise the -reversed strings. They define this function as follows: - -\begin{center} -\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l} -$rev(\ZERO)$ & $\dn$ & $\ZERO$\\ -$rev(\ONE)$ & $\dn$ & $\ONE$\\ -$rev(c)$ & $\dn$ & $c$\\ -$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ -$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ -$rev(r^*)$ & $\dn$ & $rev(r)^*$\\ -\end{tabular} -\end{center} - -\noindent It is defined by recursion analysing each pattern of -what the regular expression might look like. The corresponding -Scala code looks very similar to this definition, thanks to -pattern-matching. - -\lstinputlisting[language=Scala]{../progs/rev.scala} - -\noindent The keyword for starting a pattern-match is -\code{match} followed by a list of \code{case}s. Before the -match keyword can be another pattern, but often, as in the -case above, it is just a variable you want to pattern-match -(the \code{r} after \code{=} in Line 1). - -Each case in this definition follows the structure of how we -defined regular expressions as inductive datatype. For example -the case in Line 3 you can read as: if the regular expression -\code{r} is of the form \code{EMPTY} then do whatever follows -the \code{=>} (in this case just return \code{EMPTY}). Line 5 -reads as: if the regular expression \code{r} is of the form -\code{ALT(r1, r2)}, where the left-branch of the alternative is -matched by the variable \code{r1} and the right-branch by -\code{r2} then do ``something''. The ``something'' can now use the -variables \code{r1} and \code{r2} from the match. - -If you want to play with this function, call it for example -with the regular expression $ab + ac$. This regular expression -can recognise the strings $ab$ and $ac$. The function -\code{rev} produces $ba + ca$, which can recognise the reversed -strings $ba$ and $ca$. - -In Scala each pattern-match can also be guarded as in - -\begin{lstlisting}[ numbers=none] -case Pattern if Condition => Do_Something -\end{lstlisting} - -\noindent This allows us, for example, to re-write the -\code{collatz}-function from above as follows: - -\lstinputlisting[language=Scala]{../progs/collatz2.scala} - - -\noindent Although in this particular case the pattern-match -does not improve the code in any way. In cases like -\code{rev}, however, it is really crucial. The underscore in -Line 4 indicates that we do not care what the pattern looks -like. Thus this case acts like a default case whenever the -cases above did not match. Cases are always tried out from top -to bottom. - -\subsection*{Loops, or better the Absence thereof} - -Coming from Java or C, you might be surprised that Scala does -not really have loops. It has instead, what is in functional -programming called, \emph{maps}. To illustrate how they work, -let us assume you have a list of numbers from 1 to 8 and want to -build the list of squares. The list of numbers from 1 to 8 -can be constructed in Scala as follows: - -\begin{lstlisting}[numbers=none] -scala> (1 to 8).toList -res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8) -\end{lstlisting} - -\noindent Generating from this list, the list of squares in a -programming language such as Java, you would assume the list -is given as a kind of array. You would then iterate, or loop, -an index over this array and replace each entry in the array -by the square. Right? In Scala, and in other functional -programming languages, you use maps to achieve the same. - -A map essentially takes a function that describes how each -element is transformed (for example squared) and a list over -which this function should work. There are two forms to -express such maps in Scala. The first way is called a -\emph{for-comprehension}. Squaring the numbers from 1 to 8 -would look in this form as follows: - -\begin{lstlisting}[numbers=none] -scala> for (n <- (1 to 8).toList) yield n * n -res2: List[Int] = List(1, 4, 9, 16, 25, 36, 49, 64) -\end{lstlisting} - -\noindent The important keywords are \code{for} and -\code{yield}. This for-comprehension roughly states that from -the list of numbers we draw \code{n}s and compute the result -of \code{n * n}. As you can see, we specified the list where -each \code{n} comes from, namely \code{(1 to 8).toList}, and -how each element needs to be transformed. This can also be -expressed in a second way in Scala by using directly -\code{map}s as follows: - -\begin{lstlisting}[numbers=none] -scala> (1 to 8).toList.map(n => n * n) -res3 = List(1, 4, 9, 16, 25, 36, 49, 64) -\end{lstlisting} - -\noindent In this way, the expression \code{n => n * n} stands -for the function that calculates the square (this is how the -\code{n}s are transformed). This expression for functions -might remind you of your lessons about the lambda-calculus -where this would have been written as $\lambda n.\,n * n$. It -might not be obvious, but for-comprehensions are just -syntactic sugar: when compiling, Scala translates -for-comprehensions into equivalent maps. This even works -when for-comprehensions get more complicated (see below). - -The very charming feature of Scala is that such maps or -for-comprehensions can be written for any kind of data -collection, such as lists, sets, vectors, options and so on. -For example if we instead compute the reminders modulo 3 of -this list, we can write - -\begin{lstlisting}[numbers=none] -scala> (1 to 8).toList.map(n => n % 3) -res4 = List(1, 2, 0, 1, 2, 0, 1, 2) -\end{lstlisting} - -\noindent If we, however, transform the numbers 1 to 8 not -into a list, but into a set, and then compute the reminders -modulo 3 we obtain - -\begin{lstlisting}[numbers=none] -scala> (1 to 8).toSet[Int].map(n => n % 3) -res5 = Set(2, 1, 0) -\end{lstlisting} - -\noindent This is the correct result for sets, as there are -only three equivalence classes of integers modulo 3. Note that -in this example we need to ``help'' Scala to transform the -numbers into a set of integers by explicitly annotating the -type \code{Int}. Since maps and for-comprehensions are -just syntactic variants of each other, the latter can also be -written as - -\begin{lstlisting}[numbers=none] -scala> for (n <- (1 to 8).toSet[Int]) yield n % 3 -res5 = Set(2, 1, 0) -\end{lstlisting} - -For-comprehensions can also be nested and the selection of -elements can be guarded. For example if we want to pair up -the numbers 1 to 4 with the letters a to c, we can write - -\begin{lstlisting}[numbers=none] -scala> for (n <- (1 to 4).toList; - m <- ('a' to 'c').toList) yield (n, m) -res6 = List((1,a), (1,b), (1,c), (2,a), (2,b), (2,c), - (3,a), (3,b), (3,c), (4,a), (4,b), (4,c)) -\end{lstlisting} - -\noindent -Or if we want to find all pairs of numbers between 1 and 3 -where the sum is an even number, we can write - -\begin{lstlisting}[numbers=none] -scala> for (n <- (1 to 3).toList; - m <- (1 to 3).toList; - if (n + m) % 2 == 0) yield (n, m) -res7 = List((1,1), (1,3), (2,2), (3,1), (3,3)) -\end{lstlisting} - -\noindent The \code{if}-condition in the for-comprehension -filters out all pairs where the sum is not even. - -While hopefully this all looks reasonable, there is one -complication: In the examples above we always wanted to -transform one list into another list (e.g.~list of squares), -or one set into another set (set of numbers into set of -reminders modulo 3). What happens if we just want to print out -a list of integers? Then actually the for-comprehension -needs to be modified. The reason is that \code{print}, you -guessed it, does not produce any result, but only produces -what is in the functional-programming-lingo called a -side-effect. Printing out the list of numbers from 1 to 5 -would look as follows - -\begin{lstlisting}[numbers=none] -scala> for (n <- (1 to 5).toList) print(n) -12345 -\end{lstlisting} - -\noindent -where you need to omit the keyword \code{yield}. You can -also do more elaborate calculations such as - -\begin{lstlisting}[numbers=none] -scala> for (n <- (1 to 5).toList) { - val square_n = n * n - println(s"$n * $n = $square_n") -} -1 * 1 = 1 -2 * 2 = 4 -3 * 3 = 9 -4 * 4 = 16 -5 * 5 = 25 -\end{lstlisting} - -\noindent In this code I use a variable assignment (\code{val -square_n = ...} ) and also what is called in Scala a -\emph{string interpolation}, written \code{s"..."}. The latter -is for printing out an equation. It allows me to refer to the -integer values \code{n} and \code{square\_n} inside a string. -This is very convenient for printing out ``things''. - -The corresponding map construction for functions with -side-effects is in Scala called \code{foreach}. So you -could also write - - -\begin{lstlisting}[numbers=none] -scala> (1 to 5).toList.foreach(n => print(n)) -12345 -\end{lstlisting} - - -\noindent or even just - -\begin{lstlisting}[numbers=none] -scala> (1 to 5).toList.foreach(print) -12345 -\end{lstlisting} - -\noindent Again I hope this reminds you a bit of your -lambda-calculus lessons, where an explanation is given why -both forms produce the same result. - - -If you want to find out more about maps and functions with -side-effects, you can ponder about the response Scala gives if -you replace \code{foreach} by \code{map} in the expression -above. Scala will still allow \code{map} with side-effect -functions, but then reacts with a slightly interesting result. - -\subsection*{Types} - -In most functional programming languages, types play an -important role. Scala is such a language. You have already -seen built-in types, like \code{Int}, \code{Boolean}, -\code{String} and \code{BigInt}, but also user-defined ones, -like \code{Rexp}. Unfortunately, types can be a thorny -subject, especially in Scala. For example, why do we need to -give the type to \code{toSet[Int]}, but not to \code{toList}? -The reason is the power of Scala, which sometimes means it -cannot infer all necessary typing information. At the -beginning while getting familiar with Scala, I recommend a -``play-it-by-ear-approach'' to types. Fully understanding -type-systems, especially complicated ones like in Scala, can -take a module on their own.\footnote{Still, such a study can -be a rewarding training: If you are in the business of -designing new programming languages, you will not be able to -turn a blind eye to types. They essentially help programmers -to avoid common programming errors and help with maintaining -code.} - -In Scala, types are needed whenever you define an inductive -datatype and also whenever you define functions (their -arguments and their results need a type). Base types are types -that do not take any (type)arguments, for example \code{Int} -and \code{String}. Compound types take one or more arguments, -which as seen earlier need to be given in angle-brackets, for -example \code{List[Int]} or \code{Set[List[String]]} or -\code{Map[Int, Int]}. - -There are a few special type-constructors that fall outside -this pattern. One is for tuples, where the type is written -with parentheses. For example - -\begin{lstlisting}[ numbers=none] -(Int, Int, String) -\end{lstlisting} - -\noindent is for a triple (a tuple with three components---two -integers and a string). Tuples are helpful if you want to -define functions with multiple results, say the function -returning the quotient and reminder of two numbers. For this -you might define: - - -\begin{lstlisting}[ numbers=none] -def quo_rem(m: Int, n: Int) : (Int, Int) = (m / n, m % n) -\end{lstlisting} - - -\noindent Since this function returns a pair of integers, its -return type needs to be of type \code{(Int, Int)}. -Incidentally, this is also the input type of this function. -Notice this function takes \emph{two} arguments, namely -\code{m} and \code{n}, both of which are integers. They are -``packaged'' in a pair. Consequently the complete type of -\code{quo_rem} is - -\begin{lstlisting}[ numbers=none] -(Int, Int) => (Int, Int) -\end{lstlisting} - -Another special type-constructor is for functions, written as -the arrow \code{=>}. For example, the type \code{Int => -String} is for a function that takes an integer as input -argument and produces a string as result. A function of this -type is for instance - -\begin{lstlisting}[numbers=none] -def mk_string(n: Int) : String = n match { - case 0 => "zero" - case 1 => "one" - case 2 => "two" - case _ => "many" -} -\end{lstlisting} - -\noindent It takes an integer as input argument and returns a -string. Unlike other functional programming languages, there -is in Scala no easy way to find out the types of existing -functions, except by looking into the documentation - -\begin{quote} -\url{http://www.scala-lang.org/api/current/} -\end{quote} - -The function arrow can also be iterated, as in -\code{Int => String => Boolean}. This is the type for a function -taking an integer as first argument and a string as second, -and the result of the function is a boolean. Though silly, a -function of this type would be - - -\begin{lstlisting}[numbers=none] -def chk_string(n: Int)(s: String) : Boolean = - mk_string(n) == s -\end{lstlisting} - - -\noindent which checks whether the integer \code{n} -corresponds to the name \code{s} given by the function -\code{mk\_string}. Notice the unusual way of specifying the -arguments of this function: the arguments are given one after -the other, instead of being in a pair (what would be the type -of this function then?). This way of specifying the arguments -can be useful, for example in situations like this - -\begin{lstlisting}[numbers=none] -scala> List("one", "two", "three", "many").map(chk_string(2)) -res4 = List(false, true, false, false) - -scala> List("one", "two", "three", "many").map(chk_string(3)) -res5 = List(false, false, false, true) -\end{lstlisting} - -\noindent In each case we can give to \code{map} a specialised -version of \code{chk_string}---once specialised to 2 and once -to 3. This kind of ``specialising'' a function is called -\emph{partial application}---we have not yet given to this -function all arguments it needs, but only some of them. - -Coming back to the type \code{Int => String => Boolean}. The -rule about such function types is that the right-most type -specifies what the function returns (a boolean in this case). -The types before that specify how many arguments the function -expects and what their type is (in this case two arguments, -one of type \code{Int} and another of type \code{String}). -Given this rule, what kind of function has type -\mbox{\code{(Int => String) => Boolean}}? Well, it returns a -boolean. More interestingly, though, it only takes a single -argument (because of the parentheses). The single argument -happens to be another function (taking an integer as input and -returning a string). Remember that \code{mk_string} is just -such a function. So how can we use it? For this define -the somewhat silly function \code{apply_3}: - -\begin{lstlisting}[numbers=none] -def apply_3(f: Int => String): Bool = f(3) == "many" - -scala> apply_3(mk_string) -res6 = true -\end{lstlisting} - -You might ask: Apart from silly functions like above, what is -the point of having functions as input arguments to other -functions? In Java there is indeed no need of this kind of -feature: at least in the past it did not allow such -constructions. I think, the point of Java 8 is to lift this -restriction. But in all functional programming languages, -including Scala, it is really essential to allow functions as -input argument. Above you already seen \code{map} and -\code{foreach} which need this. Consider the functions -\code{print} and \code{println}, which both print out strings, -but the latter adds a line break. You can call \code{foreach} -with either of them and thus changing how, for example, five -numbers are printed. - - -\begin{lstlisting}[numbers=none] -scala> (1 to 5).toList.foreach(print) -12345 -scala> (1 to 5).toList.foreach(println) -1 -2 -3 -4 -5 -\end{lstlisting} - - -\noindent This is actually one of the main design principles -in functional programming. You have generic functions like -\code{map} and \code{foreach} that can traverse data containers, -like lists or sets. They then take a function to specify what -should be done with each element during the traversal. This -requires that the generic traversal functions can cope with -any kind of function (not just functions that, for example, -take as input an integer and produce a string like above). -This means we cannot fix the type of the generic traversal -functions, but have to keep them -\emph{polymorphic}.\footnote{Another interestic topic about -types, but we omit it here for the sake of brevity.} - -There is one more type constructor that is rather special. It -is called \code{Unit}. Recall that \code{Boolean} has two -values, namely \code{true} and \code{false}. This can be used, -for example, to test something and decide whether the test -succeeds or not. In contrast the type \code{Unit} has only a -single value, written \code{()}. This seems like a completely -useless type and return value for a function, but is actually -quite useful. It indicates when the function does not return -any result. The purpose of these functions is to cause -something being written on the screen or written into a file, -for example. This is what is called they cause some effect on -the side, namely a new content displayed on the screen or some -new data in a file. Scala uses the \code{Unit} type to indicate -that a function does not have a result, but potentially causes -some side-effect. Typical examples are the printing functions, -like \code{print}. - - -\subsection*{Cool Stuff} - -The first wow-moment I had with Scala was when I came across -the following code-snippet for reading a web-page. - - -\begin{lstlisting}[ numbers=none] -import io.Source -val url = """http://www.inf.kcl.ac.uk/staff/urbanc/""" -Source.fromURL(url)("ISO-8859-1").take(10000).mkString -\end{lstlisting} - - -\noindent These three lines return a string containing the -HTML-code of my webpage. It actually already does something -more sophisticated, namely only returns the first 10000 -characters of a webpage in case it is too large. Why is that -code-snippet of any interest? Well, try implementing -reading-from-a-webpage in Java. I also like the possibility of -triple-quoting strings, which I have only seen in Scala so -far. The idea behind this is that in such a string all -characters are interpreted literally---there are no escaped -characters, like \verb|\n| for newlines. - -My second wow-moment I had with a feature of Scala that other -functional programming languages do not have. This feature is -about implicit type conversions. If you have regular -expressions and want to use them for language processing you -often want to recognise keywords in a language, for example -\code{for},{} \code{if},{} \code{yield} and so on. But the -basic regular expression \code{CHAR} can only recognise a -single character. In order to recognise a whole string, like -\code{for}, you have to put many of those together using -\code{SEQ}: - - -\begin{lstlisting}[numbers=none] -SEQ(CHAR('f'), SEQ(CHAR('o'), CHAR('r'))) -\end{lstlisting} - -\noindent This gets quickly unreadable when the strings and -regular expressions get more complicated. In other functional -programming languages, you can explicitly write a conversion -function that takes a string, say \dq{\pcode{for}}, and -generates the regular expression above. But then your code is -littered with such conversion functions. - -In Scala you can do better by ``hiding'' the conversion -functions. The keyword for doing this is \code{implicit} and -it needs a built-in library called - -\begin{lstlisting}[numbers=none] -scala.language.implicitConversions -\end{lstlisting} - -\noindent -Consider the code - - -\begin{lstlisting}[language=Scala] -import scala.language.implicitConversions - -def charlist2rexp(s: List[Char]) : Rexp = s match { - case Nil => EMPTY - case c::Nil => CHAR(c) - case c::s => SEQ(CHAR(c), charlist2rexp(s)) -} - -implicit def string2rexp(s: String) : Rexp = - charlist2rexp(s.toList) -\end{lstlisting} - - -\noindent where the first seven lines implement a function -that given a list of characters generates the corresponding -regular expression. In Lines 9 and 10, this function is used -for transforming a string into a regular expression. Since the -\code{string2rexp}-function is declared as \code{implicit}, -the effect will be that whenever Scala expects a regular -expression, but I only give it a string, it will automatically -insert a call to the \code{string2rexp}-function. I can now -write for example - -\begin{lstlisting}[numbers=none] -scala> ALT("ab", "ac") -res9 = ALT(SEQ(CHAR(a),CHAR(b)),SEQ(CHAR(a),CHAR(c))) -\end{lstlisting} - -\noindent Recall that \code{ALT} expects two regular -expressions as arguments, but I only supply two strings. The -implicit conversion function will transform the string into a -regular expression. - -Using implicit definitions, Scala allows me to introduce -some further syntactic sugar for regular expressions: - - -\begin{lstlisting}[ numbers=none] -implicit def RexpOps(r: Rexp) = new { - def | (s: Rexp) = ALT(r, s) - def ~ (s: Rexp) = SEQ(r, s) - def % = STAR(r) -} - -implicit def stringOps(s: String) = new { - def | (r: Rexp) = ALT(s, r) - def | (r: String) = ALT(s, r) - def ~ (r: Rexp) = SEQ(s, r) - def ~ (r: String) = SEQ(s, r) - def % = STAR(s) -} -\end{lstlisting} - - -\noindent This might seem a bit overly complicated, but its effect is -that I can now write regular expressions such as $ab + ac$ -simply as - - -\begin{lstlisting}[numbers=none] -scala> "ab" | "ac" -res10 = ALT(SEQ(CHAR(a),CHAR(b)),SEQ(CHAR(a),CHAR(c))) -\end{lstlisting} - - -\noindent I leave you to figure out what the other -syntactic sugar in the code above stands for. - -One more useful feature of Scala is the ability to define -functions with varying argument lists. This is a feature that -is already present in old languages, like C, but seems to have -been forgotten in the meantime---Java does not have it. In the -context of regular expressions this feature comes in handy: -Say you are fed up with writing many alternatives as - - -\begin{lstlisting}[numbers=none] -ALT(..., ALT(..., ALT(..., ...))) -\end{lstlisting} - - -\noindent To make it difficult, you do not know how deep such -alternatives are nested. So you need something flexible that -can take as many alternatives as needed. In Scala one can -achieve this by adding a \code{*} to the type of an argument. -Consider the code - - -\begin{lstlisting}[language=Scala] -def Alts(rs: List[Rexp]) : Rexp = rs match { - case Nil => NULL - case r::Nil => r - case r::rs => ALT(r, Alts(rs)) -} - -def ALTS(rs: Rexp*) = Alts(rs.toList) -\end{lstlisting} - - -\noindent The function in Lines 1 to 5 takes a list of regular -expressions and converts it into an appropriate alternative -regular expression. In Line 7 there is a wrapper for this -function which uses the feature of varying argument lists. The -effect of this code is that I can write the regular -expression for keywords as - - -\begin{lstlisting}[numbers=none] -ALTS("for", "def", "yield", "implicit", "if", "match", "case") -\end{lstlisting} - - -\noindent Again I leave it to you to find out how much this -simplifies the regular expression in comparison with if I had -to write this by hand using only the ``plain'' regular -expressions from the inductive datatype. - -\subsection*{More Info} - -There is much more to Scala than I can possibly describe in -this document. Fortunately there are a number of free books -about Scala and of course lots of help online. For example - -\begin{itemize} -\item \url{http://www.scala-lang.org/docu/files/ScalaByExample.pdf} -\item \url{http://www.scala-lang.org/docu/files/ScalaTutorial.pdf} -\item \url{https://www.youtube.com/user/ShadowofCatron} -\item \url{http://docs.scala-lang.org/tutorials} -\item \url{https://www.scala-exercises.org} -\end{itemize} - -\noindent There is also a course at Coursera on Functional -Programming Principles in Scala by Martin Odersky, the main -developer of the Scala language. And a document that explains -Scala for Java programmers - -\begin{itemize} -\item \small\url{http://docs.scala-lang.org/tutorials/scala-for-java-programmers.html} -\end{itemize} - -While I am quite enthusiastic about Scala, I am also happy to -admit that it has more than its fair share of faults. The -problem seen earlier of having to give an explicit type to -\code{toSet}, but not \code{toList} is one of them. There are -also many ``deep'' ideas about types in Scala, which even to -me as seasoned functional programmer are puzzling. Whilst -implicits are great, they can also be a source of great -headaches, for example consider the code: - -\begin{lstlisting}[numbers=none] -scala> List (1, 2, 3) contains "your mom" -res1: Boolean = false -\end{lstlisting} - -\noindent Rather than returning \code{false}, this code should -throw a typing-error. There are also many limitations Scala -inherited from the JVM that can be really annoying. For -example a fixed stack size. One can work around this -particular limitation, but why does one have to? -More such `puzzles' can be found at - -\begin{center} - \url{http://scalapuzzlers.com} and - \url{http://latkin.org/blog/2017/05/02/when-the-scala-compiler-doesnt-help/} -\end{center} - -Even if Scala has been a success in several high-profile -companies, there is also a company (Yammer) that first used -Scala in their production code, but then moved away from it. -Allegedly they did not like the steep learning curve of Scala -and also that new versions of Scala often introduced -incompatibilities in old code. In the past two months -there have also been two forks of the Scala compiler. -It needs to be seen what the future brings for Scala. - -So all in all, Scala might not be a great teaching language, -but I hope this is mitigated by the fact that I never require -you to write any Scala code. You only need to be able to read -it. In the coursework you can use any programming language you -like. If you want to use Scala for this, then be my guest; if -you do not want, stick with the language you are most familiar -with. - - - -\end{document} - -%%% Local Variables: -%%% mode: latex -%%% TeX-master: t -%%% End: diff -r 739039774cee -r 94b84d880c2b handouts/scala-ho.tex-old --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/handouts/scala-ho.tex-old Tue Mar 22 00:36:18 2022 +0000 @@ -0,0 +1,1016 @@ +\documentclass{article} +\usepackage{../style} +\usepackage{../langs} +\usepackage{marvosym} + +%cheat sheet +%http://worldline.github.io/scala-cheatsheet/ + +\begin{document} + +\section*{A Crash-Course on Scala} + +Scala is a programming language that combines functional and +object-oriented programming-styles. It has received quite a +bit of attention in the last five years or so. One reason for +this attention is that, like the Java programming language, +Scala compiles to the Java Virtual Machine (JVM) and therefore +Scala programs can run under MacOSX, Linux and +Windows.\footnote{There are also experimental backends for +Android and JavaScript; and also work is under way to have a +native compiler, see \url{https://github.com/scala-native/scala-native}.} Unlike Java, however, Scala often +allows programmers to write very concise and elegant code. +Some therefore say: Scala is the much better Java. A number of +companies, The Guardian, Twitter, Coursera, FourSquare, +LinkedIn to name a few, either use Scala exclusively in +production code, or at least to some substantial degree. It +also seems to be useful in job-interviews (in Data Science) +according to this annectotical report + +\begin{quote} +\url{https://techcrunch.com/2016/06/14/scala-is-the-new-golden-child/} +\end{quote} + +\noindent +If you want to try out Scala yourself, the official Scala compiler can be +downloaded from + +\begin{quote} +\url{http://www.scala-lang.org} +\end{quote} + +\noindent +A ready-made bundle with the Eclipse IDE is at + +\begin{quote} +\url{http://scala-ide.org/download/sdk.html} +\end{quote} + +Why do I use Scala in the AFL module? Actually, you can do +\emph{any} part of the coursework in \emph{any} programming +language you like. I use Scala for showing you code during the +lectures because its functional programming-style allows me to +implement the functions we will discuss with very small +code-snippets. If I had to do this in Java, I would first have +to go through heaps of boilerplate code and the code-snippets +would not look pretty. Since the Scala compiler is free, you +can download the code-snippets and run every example I give. +But if you prefer, you can also easily translate them into any +other functional language, for example Haskell, Swift, +Standard ML, F$^\#$, Ocaml and so on. + +Developing programs in Scala can be done with the Eclipse IDE +and also with the IntelliJ IDE, but for the small programs I will +develop the good old Emacs-editor is adequate for me and I +will run the programs on the command line. One advantage of +Scala over Java is that it includes an interpreter (a REPL, or +\underline{R}ead-\underline{E}val-\underline{P}rint-\underline{L}oop) +with which you can run and test small code-snippets without +the need of the compiler. This helps a lot with interactively +developing programs. Once you installed Scala, you can start +the interpreter by typing on the command line: + +\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] +$ scala +Welcome to Scala version 2.11.8 (Java HotSpot(TM) 64-Bit Server VM). +Type in expressions for evaluation. Or try :help. + +scala> +\end{lstlisting} + +\noindent Of course the precise response may vary due to the +version and platform where you installed Scala. At the Scala +prompt you can type things like \code{2 + 3} \keys{Ret} and +the output will be + +\begin{lstlisting}[numbers=none] +scala> 2 + 3 +res0: Int = 5 +\end{lstlisting} + +\noindent indicating that the result of the addition is of +type \code{Int} and the actual result is 5. Another classic +example you can try out is + +\begin{lstlisting}[numbers=none] +scala> print("hello world") +hello world +\end{lstlisting} + +\noindent Note that in this case there is no result. The +reason is that \code{print} does not actually produce a result +(there is no \code{resXX} and no type), rather it is a +function that causes the \emph{side-effect} of printing out a +string. Once you are more familiar with the functional +programming-style, you will know what the difference is +between a function that returns a result, like addition, and a +function that causes a side-effect, like \code{print}. We +shall come back to this point later, but if you are curious +now, the latter kind of functions always has \code{Unit} as +return type. + +If you want to write a stand-alone app in Scala, you can +implement an object that is an instance of \code{App}, say + +\begin{lstlisting}[numbers=none] +object Hello extends App { + println("hello world") +} +\end{lstlisting} + +\noindent save it in a file, say {\tt hello-world.scala}, and +then run the compiler and runtime environment: + +\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] +$ scalac hello-world.scala +$ scala Hello +hello world +\end{lstlisting} + +As mentioned above, Scala targets the JVM and consequently +Scala programs can also be executed by the bog-standard Java +Runtime. This only requires the inclusion of {\tt +scala-library.jar}, which on my computer can be done as +follows: + +\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] +$ scalac hello-world.scala +$ java -cp /usr/local/src/scala/lib/scala-library.jar:. Hello +hello world +\end{lstlisting} + +\noindent You might need to adapt the path to where you have +installed Scala. + +\subsection*{Inductive Datatypes} + +The elegance and conciseness of Scala programs are often a +result of inductive datatypes that can be easily defined in +Scala. For example in ``every-day mathematics'' we define +regular expressions simply by giving the grammar + +\begin{center} +\begin{tabular}{r@{\hspace{2mm}}r@{\hspace{2mm}}l@{\hspace{13mm}}l} + $r$ & $::=$ & $\ZERO$ & null\\ + & $\mid$ & $\ONE$ & empty string\\ + & $\mid$ & $c$ & single character\\ + & $\mid$ & $r_1 \cdot r_2$ & sequence\\ + & $\mid$ & $r_1 + r_2$ & alternative / choice\\ + & $\mid$ & $r^\star$ & star (zero or more)\\ + \end{tabular} +\end{center} + +\noindent This grammar specifies what regular expressions are +(essentially a kind of tree-structure with three kinds of +inner nodes---sequence, alternative and star---and three kinds +of leave nodes---null, empty and character). If you are +familiar with Java, it might be an instructive exercise to +define this kind of inductive datatypes in Java\footnote{Happy +programming! \Smiley} and then compare it with how it can be +implemented in Scala. + +Implementing the regular expressions from above in Scala is +actually very simple: It first requires an \emph{abstract +class}, say, \code{Rexp}. This will act as the type for +regular expressions. Second, it requires a case for each +clause in the grammar. The cases for $\ZERO$ and $\ONE$ do not +have any arguments, while in all the other cases we do have +arguments. For example the character regular expression needs +to take as an argument the character it is supposed to +recognise. In Scala, the cases without arguments are called +\emph{case objects}, whereas the ones with arguments are +\emph{case classes}. The corresponding Scala code is as +follows: + +\begin{lstlisting}[numbers=none] +abstract class Rexp +case object ZERO extends Rexp +case object ONE extends Rexp +case class CHAR (c: Char) extends Rexp +case class SEQ (r1: Rexp, r2: Rexp) extends Rexp +case class ALT (r1: Rexp, r2: Rexp) extends Rexp +case class STAR (r: Rexp) extends Rexp +\end{lstlisting} + +\noindent In order to be an instance of \code{Rexp}, each case +object and case class needs to extend \code{Rexp}. Given the +grammar above, I hope you can see the underlying pattern. If +you want to play further with such definitions of inductive +datatypes, feel free to define for example binary trees. + +Once you make a definition like the one above in Scala, you +can represent the regular expression for $a + b$, for example, +as \code{ALT(CHAR('a'), CHAR('b'))}. Expressions such as +\code{'a'} stand for ASCII characters, though in the output +syntax, as you can see below, the quotes are omitted. In a +later section we will see how we can support the more +mathematical infix notation for regular expression operators +in Scala. If you want to assign this regular expression to a +variable, you can use the keyword \code{val} and type + +\begin{lstlisting}[numbers=none] +scala> val r = ALT(CHAR('a'), CHAR('b')) +r: ALT = ALT(CHAR(a),CHAR(b)) +\end{lstlisting} + +\noindent As you can see, in order to make such assignments, +no \code{new} or constructor is required in the class (as in +Java). However, if there is the need for some non-standard +initialisation, you can of course define such a constructor in +Scala too. But we omit such ``tricks'' here. + +Note that Scala in its response says the variable \code{r} is +of type \code{ALT}, not \code{Rexp}. This might be a bit +unexpected, but can be explained as follows: Scala always +tries to find the most general type that is needed for a +variable or expression, but does not ``over-generalise''. In +our definition the type \code{Rexp} is more general than +\code{ALT}, since it is the abstract class for all regular +expressions. But in this particular case there is no need to +give \code{r} the more general type of \code{Rexp}. This is +different if you want to form a list of regular expressions, +for example + +\begin{lstlisting}[numbers=none] +scala> val ls = List(ALT(CHAR('a'), CHAR('b')), ZERO) +ls: List[Rexp] = List(ALT(CHAR(a),CHAR(b)), ZERO) +\end{lstlisting} + +\noindent In this case, Scala needs to assign a common type to +the regular expressions so that it is compatible with the +fact that lists can only contain elements of a single type. In +this case the first common type is \code{Rexp}.\footnote{If you +type in this example, you will notice that the type contains +some further information, but let us ignore this for the +moment.} + +For compound types like \code{List[...]}, the general rule is +that when a type takes another type as argument, then this +argument type is written in angle-brackets. This can also +contain nested types as in \code{List[Set[Rexp]]}, which is a +list of sets each of which contains regular expressions. + +\subsection*{Functions and Pattern-Matching} + +I mentioned above that Scala is a very elegant programming +language for the code we will write in this module. This +elegance mainly stems from the fact that in addition to +inductive datatypes, also functions can be implemented very +easily in Scala. To show you this, let us first consider a +problem from number theory, called the \emph{Collatz-series}, +which corresponds to a famous unsolved problem in +mathematics.\footnote{See for example +\url{http://mathworld.wolfram.com/CollatzProblem.html}.} +Mathematicians define this series as: + +\[ +collatz_{n + 1} \dn +\begin{cases} +\frac{1}{2} * collatz_n & \text{if $collatz_n$ is even}\\ +3 * collatz_n + 1 & \text{if $collatz_n$ is odd} +\end{cases} +\] + +\noindent The famous unsolved question is whether this +series started with any $n > 0$ as $collatz_0$ will always +return to $1$. This is obvious when started with $1$, and also +with $2$, but already needs a bit of head-scratching for the +case of $3$. + +If we want to avoid the head-scratching, we could implement +this as the following function in Scala: + +\lstinputlisting[numbers=none]{../progs/collatz.scala} + +\noindent The keyword for function definitions is \code{def} +followed by the name of the function. After that you have a +list of arguments (enclosed in parentheses and separated by +commas). Each argument in this list needs its type to be +annotated. In this case we only have one argument, which is of +type \code{BigInt}. This type stands in Scala for arbitrary +precision integers (in case you want to try out the function +on really big numbers). After the arguments comes the type of +what the function returns---a Boolean in this case for +indicating that the function has reached 1. Finally, after the +\code{=} comes the \emph{body} of the function implementing +what the function is supposed to do. What the \code{collatz} +function does should be pretty self-explanatory: the function +first tests whether \code{n} is equal to 1 in which case it +returns \code{true} and so on. + +Notice the quirk in Scala's syntax for \code{if}s: The condition +needs to be enclosed in parentheses and the then-case comes +right after the condition---there is no \code{then} keyword in +Scala. + +The real power of Scala comes, however, from the ability to +define functions by \emph{pattern matching}. In the +\code{collatz} function above we need to test each case using a +sequence of \code{if}s. This can be very cumbersome and brittle +if there are many cases. If we wanted to define a function +over regular expressions in Java, for example, which does not +have pattern-matching, the resulting code would just be +awkward. + +Mathematicians already use the power of pattern-matching when +they define the function that takes a regular expression and +produces another regular expression that can recognise the +reversed strings. They define this function as follows: + +\begin{center} +\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l} +$rev(\ZERO)$ & $\dn$ & $\ZERO$\\ +$rev(\ONE)$ & $\dn$ & $\ONE$\\ +$rev(c)$ & $\dn$ & $c$\\ +$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ +$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ +$rev(r^*)$ & $\dn$ & $rev(r)^*$\\ +\end{tabular} +\end{center} + +\noindent It is defined by recursion analysing each pattern of +what the regular expression might look like. The corresponding +Scala code looks very similar to this definition, thanks to +pattern-matching. + +\lstinputlisting[language=Scala]{../progs/rev.scala} + +\noindent The keyword for starting a pattern-match is +\code{match} followed by a list of \code{case}s. Before the +match keyword can be another pattern, but often, as in the +case above, it is just a variable you want to pattern-match +(the \code{r} after \code{=} in Line 1). + +Each case in this definition follows the structure of how we +defined regular expressions as inductive datatype. For example +the case in Line 3 you can read as: if the regular expression +\code{r} is of the form \code{EMPTY} then do whatever follows +the \code{=>} (in this case just return \code{EMPTY}). Line 5 +reads as: if the regular expression \code{r} is of the form +\code{ALT(r1, r2)}, where the left-branch of the alternative is +matched by the variable \code{r1} and the right-branch by +\code{r2} then do ``something''. The ``something'' can now use the +variables \code{r1} and \code{r2} from the match. + +If you want to play with this function, call it for example +with the regular expression $ab + ac$. This regular expression +can recognise the strings $ab$ and $ac$. The function +\code{rev} produces $ba + ca$, which can recognise the reversed +strings $ba$ and $ca$. + +In Scala each pattern-match can also be guarded as in + +\begin{lstlisting}[ numbers=none] +case Pattern if Condition => Do_Something +\end{lstlisting} + +\noindent This allows us, for example, to re-write the +\code{collatz}-function from above as follows: + +\lstinputlisting[language=Scala]{../progs/collatz2.scala} + + +\noindent Although in this particular case the pattern-match +does not improve the code in any way. In cases like +\code{rev}, however, it is really crucial. The underscore in +Line 4 indicates that we do not care what the pattern looks +like. Thus this case acts like a default case whenever the +cases above did not match. Cases are always tried out from top +to bottom. + +\subsection*{Loops, or better the Absence thereof} + +Coming from Java or C, you might be surprised that Scala does +not really have loops. It has instead, what is in functional +programming called, \emph{maps}. To illustrate how they work, +let us assume you have a list of numbers from 1 to 8 and want to +build the list of squares. The list of numbers from 1 to 8 +can be constructed in Scala as follows: + +\begin{lstlisting}[numbers=none] +scala> (1 to 8).toList +res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8) +\end{lstlisting} + +\noindent Generating from this list, the list of squares in a +programming language such as Java, you would assume the list +is given as a kind of array. You would then iterate, or loop, +an index over this array and replace each entry in the array +by the square. Right? In Scala, and in other functional +programming languages, you use maps to achieve the same. + +A map essentially takes a function that describes how each +element is transformed (for example squared) and a list over +which this function should work. There are two forms to +express such maps in Scala. The first way is called a +\emph{for-comprehension}. Squaring the numbers from 1 to 8 +would look in this form as follows: + +\begin{lstlisting}[numbers=none] +scala> for (n <- (1 to 8).toList) yield n * n +res2: List[Int] = List(1, 4, 9, 16, 25, 36, 49, 64) +\end{lstlisting} + +\noindent The important keywords are \code{for} and +\code{yield}. This for-comprehension roughly states that from +the list of numbers we draw \code{n}s and compute the result +of \code{n * n}. As you can see, we specified the list where +each \code{n} comes from, namely \code{(1 to 8).toList}, and +how each element needs to be transformed. This can also be +expressed in a second way in Scala by using directly +\code{map}s as follows: + +\begin{lstlisting}[numbers=none] +scala> (1 to 8).toList.map(n => n * n) +res3 = List(1, 4, 9, 16, 25, 36, 49, 64) +\end{lstlisting} + +\noindent In this way, the expression \code{n => n * n} stands +for the function that calculates the square (this is how the +\code{n}s are transformed). This expression for functions +might remind you of your lessons about the lambda-calculus +where this would have been written as $\lambda n.\,n * n$. It +might not be obvious, but for-comprehensions are just +syntactic sugar: when compiling, Scala translates +for-comprehensions into equivalent maps. This even works +when for-comprehensions get more complicated (see below). + +The very charming feature of Scala is that such maps or +for-comprehensions can be written for any kind of data +collection, such as lists, sets, vectors, options and so on. +For example if we instead compute the reminders modulo 3 of +this list, we can write + +\begin{lstlisting}[numbers=none] +scala> (1 to 8).toList.map(n => n % 3) +res4 = List(1, 2, 0, 1, 2, 0, 1, 2) +\end{lstlisting} + +\noindent If we, however, transform the numbers 1 to 8 not +into a list, but into a set, and then compute the reminders +modulo 3 we obtain + +\begin{lstlisting}[numbers=none] +scala> (1 to 8).toSet[Int].map(n => n % 3) +res5 = Set(2, 1, 0) +\end{lstlisting} + +\noindent This is the correct result for sets, as there are +only three equivalence classes of integers modulo 3. Note that +in this example we need to ``help'' Scala to transform the +numbers into a set of integers by explicitly annotating the +type \code{Int}. Since maps and for-comprehensions are +just syntactic variants of each other, the latter can also be +written as + +\begin{lstlisting}[numbers=none] +scala> for (n <- (1 to 8).toSet[Int]) yield n % 3 +res5 = Set(2, 1, 0) +\end{lstlisting} + +For-comprehensions can also be nested and the selection of +elements can be guarded. For example if we want to pair up +the numbers 1 to 4 with the letters a to c, we can write + +\begin{lstlisting}[numbers=none] +scala> for (n <- (1 to 4).toList; + m <- ('a' to 'c').toList) yield (n, m) +res6 = List((1,a), (1,b), (1,c), (2,a), (2,b), (2,c), + (3,a), (3,b), (3,c), (4,a), (4,b), (4,c)) +\end{lstlisting} + +\noindent +Or if we want to find all pairs of numbers between 1 and 3 +where the sum is an even number, we can write + +\begin{lstlisting}[numbers=none] +scala> for (n <- (1 to 3).toList; + m <- (1 to 3).toList; + if (n + m) % 2 == 0) yield (n, m) +res7 = List((1,1), (1,3), (2,2), (3,1), (3,3)) +\end{lstlisting} + +\noindent The \code{if}-condition in the for-comprehension +filters out all pairs where the sum is not even. + +While hopefully this all looks reasonable, there is one +complication: In the examples above we always wanted to +transform one list into another list (e.g.~list of squares), +or one set into another set (set of numbers into set of +reminders modulo 3). What happens if we just want to print out +a list of integers? Then actually the for-comprehension +needs to be modified. The reason is that \code{print}, you +guessed it, does not produce any result, but only produces +what is in the functional-programming-lingo called a +side-effect. Printing out the list of numbers from 1 to 5 +would look as follows + +\begin{lstlisting}[numbers=none] +scala> for (n <- (1 to 5).toList) print(n) +12345 +\end{lstlisting} + +\noindent +where you need to omit the keyword \code{yield}. You can +also do more elaborate calculations such as + +\begin{lstlisting}[numbers=none] +scala> for (n <- (1 to 5).toList) { + val square_n = n * n + println(s"$n * $n = $square_n") +} +1 * 1 = 1 +2 * 2 = 4 +3 * 3 = 9 +4 * 4 = 16 +5 * 5 = 25 +\end{lstlisting} + +\noindent In this code I use a variable assignment (\code{val +square_n = ...} ) and also what is called in Scala a +\emph{string interpolation}, written \code{s"..."}. The latter +is for printing out an equation. It allows me to refer to the +integer values \code{n} and \code{square\_n} inside a string. +This is very convenient for printing out ``things''. + +The corresponding map construction for functions with +side-effects is in Scala called \code{foreach}. So you +could also write + + +\begin{lstlisting}[numbers=none] +scala> (1 to 5).toList.foreach(n => print(n)) +12345 +\end{lstlisting} + + +\noindent or even just + +\begin{lstlisting}[numbers=none] +scala> (1 to 5).toList.foreach(print) +12345 +\end{lstlisting} + +\noindent Again I hope this reminds you a bit of your +lambda-calculus lessons, where an explanation is given why +both forms produce the same result. + + +If you want to find out more about maps and functions with +side-effects, you can ponder about the response Scala gives if +you replace \code{foreach} by \code{map} in the expression +above. Scala will still allow \code{map} with side-effect +functions, but then reacts with a slightly interesting result. + +\subsection*{Types} + +In most functional programming languages, types play an +important role. Scala is such a language. You have already +seen built-in types, like \code{Int}, \code{Boolean}, +\code{String} and \code{BigInt}, but also user-defined ones, +like \code{Rexp}. Unfortunately, types can be a thorny +subject, especially in Scala. For example, why do we need to +give the type to \code{toSet[Int]}, but not to \code{toList}? +The reason is the power of Scala, which sometimes means it +cannot infer all necessary typing information. At the +beginning while getting familiar with Scala, I recommend a +``play-it-by-ear-approach'' to types. Fully understanding +type-systems, especially complicated ones like in Scala, can +take a module on their own.\footnote{Still, such a study can +be a rewarding training: If you are in the business of +designing new programming languages, you will not be able to +turn a blind eye to types. They essentially help programmers +to avoid common programming errors and help with maintaining +code.} + +In Scala, types are needed whenever you define an inductive +datatype and also whenever you define functions (their +arguments and their results need a type). Base types are types +that do not take any (type)arguments, for example \code{Int} +and \code{String}. Compound types take one or more arguments, +which as seen earlier need to be given in angle-brackets, for +example \code{List[Int]} or \code{Set[List[String]]} or +\code{Map[Int, Int]}. + +There are a few special type-constructors that fall outside +this pattern. One is for tuples, where the type is written +with parentheses. For example + +\begin{lstlisting}[ numbers=none] +(Int, Int, String) +\end{lstlisting} + +\noindent is for a triple (a tuple with three components---two +integers and a string). Tuples are helpful if you want to +define functions with multiple results, say the function +returning the quotient and reminder of two numbers. For this +you might define: + + +\begin{lstlisting}[ numbers=none] +def quo_rem(m: Int, n: Int) : (Int, Int) = (m / n, m % n) +\end{lstlisting} + + +\noindent Since this function returns a pair of integers, its +return type needs to be of type \code{(Int, Int)}. +Incidentally, this is also the input type of this function. +Notice this function takes \emph{two} arguments, namely +\code{m} and \code{n}, both of which are integers. They are +``packaged'' in a pair. Consequently the complete type of +\code{quo_rem} is + +\begin{lstlisting}[ numbers=none] +(Int, Int) => (Int, Int) +\end{lstlisting} + +Another special type-constructor is for functions, written as +the arrow \code{=>}. For example, the type \code{Int => +String} is for a function that takes an integer as input +argument and produces a string as result. A function of this +type is for instance + +\begin{lstlisting}[numbers=none] +def mk_string(n: Int) : String = n match { + case 0 => "zero" + case 1 => "one" + case 2 => "two" + case _ => "many" +} +\end{lstlisting} + +\noindent It takes an integer as input argument and returns a +string. Unlike other functional programming languages, there +is in Scala no easy way to find out the types of existing +functions, except by looking into the documentation + +\begin{quote} +\url{http://www.scala-lang.org/api/current/} +\end{quote} + +The function arrow can also be iterated, as in +\code{Int => String => Boolean}. This is the type for a function +taking an integer as first argument and a string as second, +and the result of the function is a boolean. Though silly, a +function of this type would be + + +\begin{lstlisting}[numbers=none] +def chk_string(n: Int)(s: String) : Boolean = + mk_string(n) == s +\end{lstlisting} + + +\noindent which checks whether the integer \code{n} +corresponds to the name \code{s} given by the function +\code{mk\_string}. Notice the unusual way of specifying the +arguments of this function: the arguments are given one after +the other, instead of being in a pair (what would be the type +of this function then?). This way of specifying the arguments +can be useful, for example in situations like this + +\begin{lstlisting}[numbers=none] +scala> List("one", "two", "three", "many").map(chk_string(2)) +res4 = List(false, true, false, false) + +scala> List("one", "two", "three", "many").map(chk_string(3)) +res5 = List(false, false, false, true) +\end{lstlisting} + +\noindent In each case we can give to \code{map} a specialised +version of \code{chk_string}---once specialised to 2 and once +to 3. This kind of ``specialising'' a function is called +\emph{partial application}---we have not yet given to this +function all arguments it needs, but only some of them. + +Coming back to the type \code{Int => String => Boolean}. The +rule about such function types is that the right-most type +specifies what the function returns (a boolean in this case). +The types before that specify how many arguments the function +expects and what their type is (in this case two arguments, +one of type \code{Int} and another of type \code{String}). +Given this rule, what kind of function has type +\mbox{\code{(Int => String) => Boolean}}? Well, it returns a +boolean. More interestingly, though, it only takes a single +argument (because of the parentheses). The single argument +happens to be another function (taking an integer as input and +returning a string). Remember that \code{mk_string} is just +such a function. So how can we use it? For this define +the somewhat silly function \code{apply_3}: + +\begin{lstlisting}[numbers=none] +def apply_3(f: Int => String): Bool = f(3) == "many" + +scala> apply_3(mk_string) +res6 = true +\end{lstlisting} + +You might ask: Apart from silly functions like above, what is +the point of having functions as input arguments to other +functions? In Java there is indeed no need of this kind of +feature: at least in the past it did not allow such +constructions. I think, the point of Java 8 is to lift this +restriction. But in all functional programming languages, +including Scala, it is really essential to allow functions as +input argument. Above you already seen \code{map} and +\code{foreach} which need this. Consider the functions +\code{print} and \code{println}, which both print out strings, +but the latter adds a line break. You can call \code{foreach} +with either of them and thus changing how, for example, five +numbers are printed. + + +\begin{lstlisting}[numbers=none] +scala> (1 to 5).toList.foreach(print) +12345 +scala> (1 to 5).toList.foreach(println) +1 +2 +3 +4 +5 +\end{lstlisting} + + +\noindent This is actually one of the main design principles +in functional programming. You have generic functions like +\code{map} and \code{foreach} that can traverse data containers, +like lists or sets. They then take a function to specify what +should be done with each element during the traversal. This +requires that the generic traversal functions can cope with +any kind of function (not just functions that, for example, +take as input an integer and produce a string like above). +This means we cannot fix the type of the generic traversal +functions, but have to keep them +\emph{polymorphic}.\footnote{Another interestic topic about +types, but we omit it here for the sake of brevity.} + +There is one more type constructor that is rather special. It +is called \code{Unit}. Recall that \code{Boolean} has two +values, namely \code{true} and \code{false}. This can be used, +for example, to test something and decide whether the test +succeeds or not. In contrast the type \code{Unit} has only a +single value, written \code{()}. This seems like a completely +useless type and return value for a function, but is actually +quite useful. It indicates when the function does not return +any result. The purpose of these functions is to cause +something being written on the screen or written into a file, +for example. This is what is called they cause some effect on +the side, namely a new content displayed on the screen or some +new data in a file. Scala uses the \code{Unit} type to indicate +that a function does not have a result, but potentially causes +some side-effect. Typical examples are the printing functions, +like \code{print}. + + +\subsection*{Cool Stuff} + +The first wow-moment I had with Scala was when I came across +the following code-snippet for reading a web-page. + + +\begin{lstlisting}[ numbers=none] +import io.Source +val url = """http://www.inf.kcl.ac.uk/staff/urbanc/""" +Source.fromURL(url)("ISO-8859-1").take(10000).mkString +\end{lstlisting} + + +\noindent These three lines return a string containing the +HTML-code of my webpage. It actually already does something +more sophisticated, namely only returns the first 10000 +characters of a webpage in case it is too large. Why is that +code-snippet of any interest? Well, try implementing +reading-from-a-webpage in Java. I also like the possibility of +triple-quoting strings, which I have only seen in Scala so +far. The idea behind this is that in such a string all +characters are interpreted literally---there are no escaped +characters, like \verb|\n| for newlines. + +My second wow-moment I had with a feature of Scala that other +functional programming languages do not have. This feature is +about implicit type conversions. If you have regular +expressions and want to use them for language processing you +often want to recognise keywords in a language, for example +\code{for},{} \code{if},{} \code{yield} and so on. But the +basic regular expression \code{CHAR} can only recognise a +single character. In order to recognise a whole string, like +\code{for}, you have to put many of those together using +\code{SEQ}: + + +\begin{lstlisting}[numbers=none] +SEQ(CHAR('f'), SEQ(CHAR('o'), CHAR('r'))) +\end{lstlisting} + +\noindent This gets quickly unreadable when the strings and +regular expressions get more complicated. In other functional +programming languages, you can explicitly write a conversion +function that takes a string, say \dq{\pcode{for}}, and +generates the regular expression above. But then your code is +littered with such conversion functions. + +In Scala you can do better by ``hiding'' the conversion +functions. The keyword for doing this is \code{implicit} and +it needs a built-in library called + +\begin{lstlisting}[numbers=none] +scala.language.implicitConversions +\end{lstlisting} + +\noindent +Consider the code + + +\begin{lstlisting}[language=Scala] +import scala.language.implicitConversions + +def charlist2rexp(s: List[Char]) : Rexp = s match { + case Nil => EMPTY + case c::Nil => CHAR(c) + case c::s => SEQ(CHAR(c), charlist2rexp(s)) +} + +implicit def string2rexp(s: String) : Rexp = + charlist2rexp(s.toList) +\end{lstlisting} + + +\noindent where the first seven lines implement a function +that given a list of characters generates the corresponding +regular expression. In Lines 9 and 10, this function is used +for transforming a string into a regular expression. Since the +\code{string2rexp}-function is declared as \code{implicit}, +the effect will be that whenever Scala expects a regular +expression, but I only give it a string, it will automatically +insert a call to the \code{string2rexp}-function. I can now +write for example + +\begin{lstlisting}[numbers=none] +scala> ALT("ab", "ac") +res9 = ALT(SEQ(CHAR(a),CHAR(b)),SEQ(CHAR(a),CHAR(c))) +\end{lstlisting} + +\noindent Recall that \code{ALT} expects two regular +expressions as arguments, but I only supply two strings. The +implicit conversion function will transform the string into a +regular expression. + +Using implicit definitions, Scala allows me to introduce +some further syntactic sugar for regular expressions: + + +\begin{lstlisting}[ numbers=none] +implicit def RexpOps(r: Rexp) = new { + def | (s: Rexp) = ALT(r, s) + def ~ (s: Rexp) = SEQ(r, s) + def % = STAR(r) +} + +implicit def stringOps(s: String) = new { + def | (r: Rexp) = ALT(s, r) + def | (r: String) = ALT(s, r) + def ~ (r: Rexp) = SEQ(s, r) + def ~ (r: String) = SEQ(s, r) + def % = STAR(s) +} +\end{lstlisting} + + +\noindent This might seem a bit overly complicated, but its effect is +that I can now write regular expressions such as $ab + ac$ +simply as + + +\begin{lstlisting}[numbers=none] +scala> "ab" | "ac" +res10 = ALT(SEQ(CHAR(a),CHAR(b)),SEQ(CHAR(a),CHAR(c))) +\end{lstlisting} + + +\noindent I leave you to figure out what the other +syntactic sugar in the code above stands for. + +One more useful feature of Scala is the ability to define +functions with varying argument lists. This is a feature that +is already present in old languages, like C, but seems to have +been forgotten in the meantime---Java does not have it. In the +context of regular expressions this feature comes in handy: +Say you are fed up with writing many alternatives as + + +\begin{lstlisting}[numbers=none] +ALT(..., ALT(..., ALT(..., ...))) +\end{lstlisting} + + +\noindent To make it difficult, you do not know how deep such +alternatives are nested. So you need something flexible that +can take as many alternatives as needed. In Scala one can +achieve this by adding a \code{*} to the type of an argument. +Consider the code + + +\begin{lstlisting}[language=Scala] +def Alts(rs: List[Rexp]) : Rexp = rs match { + case Nil => NULL + case r::Nil => r + case r::rs => ALT(r, Alts(rs)) +} + +def ALTS(rs: Rexp*) = Alts(rs.toList) +\end{lstlisting} + + +\noindent The function in Lines 1 to 5 takes a list of regular +expressions and converts it into an appropriate alternative +regular expression. In Line 7 there is a wrapper for this +function which uses the feature of varying argument lists. The +effect of this code is that I can write the regular +expression for keywords as + + +\begin{lstlisting}[numbers=none] +ALTS("for", "def", "yield", "implicit", "if", "match", "case") +\end{lstlisting} + + +\noindent Again I leave it to you to find out how much this +simplifies the regular expression in comparison with if I had +to write this by hand using only the ``plain'' regular +expressions from the inductive datatype. + +\subsection*{More Info} + +There is much more to Scala than I can possibly describe in +this document. Fortunately there are a number of free books +about Scala and of course lots of help online. For example + +\begin{itemize} +\item \url{http://www.scala-lang.org/docu/files/ScalaByExample.pdf} +\item \url{http://www.scala-lang.org/docu/files/ScalaTutorial.pdf} +\item \url{https://www.youtube.com/user/ShadowofCatron} +\item \url{http://docs.scala-lang.org/tutorials} +\item \url{https://www.scala-exercises.org} +\end{itemize} + +\noindent There is also a course at Coursera on Functional +Programming Principles in Scala by Martin Odersky, the main +developer of the Scala language. And a document that explains +Scala for Java programmers + +\begin{itemize} +\item \small\url{http://docs.scala-lang.org/tutorials/scala-for-java-programmers.html} +\end{itemize} + +While I am quite enthusiastic about Scala, I am also happy to +admit that it has more than its fair share of faults. The +problem seen earlier of having to give an explicit type to +\code{toSet}, but not \code{toList} is one of them. There are +also many ``deep'' ideas about types in Scala, which even to +me as seasoned functional programmer are puzzling. Whilst +implicits are great, they can also be a source of great +headaches, for example consider the code: + +\begin{lstlisting}[numbers=none] +scala> List (1, 2, 3) contains "your mom" +res1: Boolean = false +\end{lstlisting} + +\noindent Rather than returning \code{false}, this code should +throw a typing-error. There are also many limitations Scala +inherited from the JVM that can be really annoying. For +example a fixed stack size. One can work around this +particular limitation, but why does one have to? +More such `puzzles' can be found at + +\begin{center} + \url{http://scalapuzzlers.com} and + \url{http://latkin.org/blog/2017/05/02/when-the-scala-compiler-doesnt-help/} +\end{center} + +Even if Scala has been a success in several high-profile +companies, there is also a company (Yammer) that first used +Scala in their production code, but then moved away from it. +Allegedly they did not like the steep learning curve of Scala +and also that new versions of Scala often introduced +incompatibilities in old code. In the past two months +there have also been two forks of the Scala compiler. +It needs to be seen what the future brings for Scala. + +So all in all, Scala might not be a great teaching language, +but I hope this is mitigated by the fact that I never require +you to write any Scala code. You only need to be able to read +it. In the coursework you can use any programming language you +like. If you want to use Scala for this, then be my guest; if +you do not want, stick with the language you are most familiar +with. + + + +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: diff -r 739039774cee -r 94b84d880c2b hws/hw01.pdf Binary file hws/hw01.pdf has changed diff -r 739039774cee -r 94b84d880c2b hws/hw02.pdf Binary file hws/hw02.pdf has changed diff -r 739039774cee -r 94b84d880c2b hws/hw03.pdf Binary file hws/hw03.pdf has changed diff -r 739039774cee -r 94b84d880c2b hws/hw04.pdf Binary file hws/hw04.pdf has changed diff -r 739039774cee -r 94b84d880c2b hws/hw05.pdf Binary file hws/hw05.pdf has changed diff -r 739039774cee -r 94b84d880c2b hws/hw06.pdf Binary file hws/hw06.pdf has changed diff -r 739039774cee -r 94b84d880c2b hws/hw07.pdf Binary file hws/hw07.pdf has changed diff -r 739039774cee -r 94b84d880c2b hws/hw08.pdf Binary file hws/hw08.pdf has changed diff -r 739039774cee -r 94b84d880c2b hws/hw09.pdf Binary file hws/hw09.pdf has changed diff -r 739039774cee -r 94b84d880c2b hws/proof.pdf Binary file hws/proof.pdf has changed diff -r 739039774cee -r 94b84d880c2b progs/matcher/re1.sc --- a/progs/matcher/re1.sc Mon Jan 24 00:14:02 2022 +0000 +++ b/progs/matcher/re1.sc Tue Mar 22 00:36:18 2022 +0000 @@ -54,6 +54,9 @@ nullable(ders(s.toList, r)) + + + // some examples from the homework val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) @@ -180,3 +183,43 @@ // runs with amm2 and amm3 + +def pp(r: Rexp): String = r match { + case SEQ(CHAR(a1), SEQ(r1, r2)) => s"${a1}${pp(r1)}${pp(r2)}" + case SEQ(ONE, SEQ(r1, r2)) => s"1${pp(r1)}${pp(r2)}" + case SEQ(ZERO, SEQ(r1, r2)) => s"0${pp(r1)}${pp(r2)}" + case SEQ(CHAR(a1), CHAR(a2)) => s"${a1}${a2}" + case SEQ(ONE, CHAR(a2)) => s"1${a2}" + case SEQ(ZERO, CHAR(a2)) => s"0${a2}" + case ZERO => "0" + case ONE => "1" + case CHAR(a) => a.toString + case ALT(r1, r2) => s"(${pp(r1)} + ${pp(r2)})" + case SEQ(r1, r2) => s"(${pp(r1)} o ${pp(r2)})" + case STAR(r1) => s"(${pp(r1)})*" +} + + +val REG = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))) + +print(pp(ders("".toList, REG))) +print(pp(ders("a".toList, REG))) +print(pp(ders("aa".toList, REG))) +print(pp(ders("aaa".toList, REG))) + +size(ders("".toList, REG)) // 6 +size(ders("a".toList, REG)) // 12 +size(ders("aa".toList, REG)) // 27 +size(ders("aaa".toList, REG)) // 55 +size(ders("aaaa".toList, REG)) // 98 +size(ders("aaaaa".toList, REG)) // 169 +size(ders("aaaaaa".toList, REG)) // 283 +size(ders(("a" * 7).toList, REG)) // 468 +size(ders(("a" * 8).toList, REG)) // 767 +size(ders(("a" * 9).toList, REG)) // 1251 +size(ders(("a" * 10).toList, REG))// 2034 +size(ders(("a" * 11).toList, REG))// 3301 + +for (i <- (0 to 40)) { + println(s"$i:" + size(ders(("a" * i).toList, REG))) +} \ No newline at end of file diff -r 739039774cee -r 94b84d880c2b progs/matcher/re3.sc --- a/progs/matcher/re3.sc Mon Jan 24 00:14:02 2022 +0000 +++ b/progs/matcher/re3.sc Tue Mar 22 00:36:18 2022 +0000 @@ -187,3 +187,43 @@ // runs with amm2 and amm3 + +def pp(r: Rexp): String = r match { + case SEQ(CHAR(a1), SEQ(r1, r2)) => s"${a1}${pp(r1)}${pp(r2)}" + case SEQ(ONE, SEQ(r1, r2)) => s"1${pp(r1)}${pp(r2)}" + case SEQ(ZERO, SEQ(r1, r2)) => s"0${pp(r1)}${pp(r2)}" + case SEQ(CHAR(a1), CHAR(a2)) => s"${a1}${a2}" + case SEQ(ONE, CHAR(a2)) => s"1${a2}" + case SEQ(ZERO, CHAR(a2)) => s"0${a2}" + case ZERO => "0" + case ONE => "1" + case CHAR(a) => a.toString + case ALT(r1, r2) => s"(${pp(r1)} + ${pp(r2)})" + case SEQ(r1, r2) => s"(${pp(r1)} o ${pp(r2)})" + case STAR(r1) => s"(${pp(r1)})*" +} + + +val REG = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))) + +print(pp(ders("".toList, REG))) +print(pp(ders("a".toList, REG))) +print(pp(ders("aa".toList, REG))) +print(pp(ders("aaa".toList, REG))) + +size(ders("".toList, REG)) // 6 +size(ders("a".toList, REG)) // 12 +size(ders("aa".toList, REG)) // 27 +size(ders("aaa".toList, REG)) // 55 +size(ders("aaaa".toList, REG)) // 8 +size(ders("aaaaa".toList, REG)) // 169 +size(ders("aaaaaa".toList, REG)) // 283 +size(ders(("a" * 7).toList, REG)) // 468 +size(ders(("a" * 8).toList, REG)) // 767 +size(ders(("a" * 9).toList, REG)) // 1251 +size(ders(("a" * 10).toList, REG))// 2034 +size(ders(("a" * 11).toList, REG))// 3301 + +for (i <- (0 to 40)) { + println(s"$i:" + size(ders(("a" * i).toList, REG))) +} \ No newline at end of file diff -r 739039774cee -r 94b84d880c2b progs/matcher/re4.sc --- a/progs/matcher/re4.sc Mon Jan 24 00:14:02 2022 +0000 +++ b/progs/matcher/re4.sc Tue Mar 22 00:36:18 2022 +0000 @@ -106,7 +106,7 @@ } -@arg(doc = "Test (a?{n}) (a{n})") +//@arg(doc = "Test (a?{n}) (a{n})") @main def test1() = { for (i <- 0 to 11000 by 1000) { @@ -114,7 +114,7 @@ } } -@arg(doc = "Test (a*)* b") +//@arg(doc = "Test (a*)* b") @main def test2() = { for (i <- 0 to 7000000 by 500000) { @@ -122,7 +122,7 @@ } } -@arg(doc = "All tests.") +//@arg(doc = "All tests.") @main def all() = { test1(); test2() } diff -r 739039774cee -r 94b84d880c2b slides/slides01.pdf Binary file slides/slides01.pdf has changed diff -r 739039774cee -r 94b84d880c2b slides/slides01.tex --- a/slides/slides01.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/slides/slides01.tex Tue Mar 22 00:36:18 2022 +0000 @@ -1,7 +1,7 @@ % !TEX program = xelatex \documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer} \usepackage{../slides} -\usepackage{../graphics} +\usepackage{../graphicss} \usepackage{../langs} \usepackage{../data} diff -r 739039774cee -r 94b84d880c2b slides/slides02.pdf Binary file slides/slides02.pdf has changed diff -r 739039774cee -r 94b84d880c2b slides/slides02.tex --- a/slides/slides02.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/slides/slides02.tex Tue Mar 22 00:36:18 2022 +0000 @@ -1,7 +1,7 @@ % !TEX program = xelatex \documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer} \usepackage{../slides} -\usepackage{../graphics} +\usepackage{../graphicss} \usepackage{../langs} \usepackage{../data} diff -r 739039774cee -r 94b84d880c2b slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r 739039774cee -r 94b84d880c2b slides/slides03.tex --- a/slides/slides03.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/slides/slides03.tex Tue Mar 22 00:36:18 2022 +0000 @@ -1,7 +1,7 @@ % !TEX program = xelatex \documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer} \usepackage{../slides} -\usepackage{../graphics} +\usepackage{../graphicss} \usepackage{../langs} \usepackage{../data} diff -r 739039774cee -r 94b84d880c2b slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r 739039774cee -r 94b84d880c2b slides/slides04.tex --- a/slides/slides04.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/slides/slides04.tex Tue Mar 22 00:36:18 2022 +0000 @@ -1,7 +1,7 @@ % !TEX program = xelatex \documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer} \usepackage{../slides} -\usepackage{../graphics} +\usepackage{../graphicss} \usepackage{../langs} \usepackage{../data} diff -r 739039774cee -r 94b84d880c2b slides/slides05.pdf Binary file slides/slides05.pdf has changed diff -r 739039774cee -r 94b84d880c2b slides/slides05.tex --- a/slides/slides05.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/slides/slides05.tex Tue Mar 22 00:36:18 2022 +0000 @@ -2,7 +2,7 @@ % !TEX program = xelatex \documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer} \usepackage{../slides} -\usepackage{../graphics} +\usepackage{../graphicss} \usepackage{../langs} \usepackage{../data} \usepackage{../grammar} diff -r 739039774cee -r 94b84d880c2b slides/slides06.pdf Binary file slides/slides06.pdf has changed diff -r 739039774cee -r 94b84d880c2b slides/slides06.tex --- a/slides/slides06.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/slides/slides06.tex Tue Mar 22 00:36:18 2022 +0000 @@ -1,7 +1,7 @@ % !TEX program = xelatex \documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer} \usepackage{../slides} -\usepackage{../graphics} +\usepackage{../graphicss} \usepackage{../langs} \usepackage{../data} \usepackage{../grammar} diff -r 739039774cee -r 94b84d880c2b slides/slides07.pdf Binary file slides/slides07.pdf has changed diff -r 739039774cee -r 94b84d880c2b slides/slides07.tex --- a/slides/slides07.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/slides/slides07.tex Tue Mar 22 00:36:18 2022 +0000 @@ -3,7 +3,7 @@ \usepackage{../slides} \usepackage{../langs} \usepackage{../data} -\usepackage{../graphics} +\usepackage{../graphicss} \usepackage{../grammar} % beamer stuff diff -r 739039774cee -r 94b84d880c2b slides/slides08.pdf Binary file slides/slides08.pdf has changed diff -r 739039774cee -r 94b84d880c2b slides/slides08.tex --- a/slides/slides08.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/slides/slides08.tex Tue Mar 22 00:36:18 2022 +0000 @@ -4,7 +4,7 @@ \usepackage{../slides} \usepackage{../langs} \usepackage{../data} -\usepackage{../graphics} +\usepackage{../graphicss} \usepackage{../grammar} \usepackage[most]{tcolorbox} diff -r 739039774cee -r 94b84d880c2b slides/slides09.pdf Binary file slides/slides09.pdf has changed diff -r 739039774cee -r 94b84d880c2b slides/slides09.tex --- a/slides/slides09.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/slides/slides09.tex Tue Mar 22 00:36:18 2022 +0000 @@ -3,7 +3,7 @@ \usepackage{../slides} \usepackage{../langs} \usepackage{../data} -\usepackage{../graphics} +\usepackage{../graphicss} \usepackage{../grammar} \usepackage{soul} \usepackage{mathpartir} diff -r 739039774cee -r 94b84d880c2b slides/slides10.pdf Binary file slides/slides10.pdf has changed diff -r 739039774cee -r 94b84d880c2b slides/slides10.tex --- a/slides/slides10.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/slides/slides10.tex Tue Mar 22 00:36:18 2022 +0000 @@ -3,7 +3,7 @@ \usepackage{../slides} \usepackage{../langs} \usepackage{../data} -\usepackage{../graphics} +\usepackage{../graphicss} \usepackage{soul} \tikzset{onslide/.code args={<#1>#2}{% diff -r 739039774cee -r 94b84d880c2b slides/slides11.pdf Binary file slides/slides11.pdf has changed diff -r 739039774cee -r 94b84d880c2b slides/slides11.tex --- a/slides/slides11.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/slides/slides11.tex Tue Mar 22 00:36:18 2022 +0000 @@ -2,7 +2,7 @@ \usepackage{../slides} \usepackage{../langs} \usepackage{../data} -\usepackage{../graphics} +\usepackage{../graphicss} \usepackage{soul} \usepackage{proof} @@ -10,28 +10,28 @@ \renewcommand{\slidecaption}{CFL, King's College London} \newcommand{\bl}[1]{\textcolor{blue}{#1}} -\newcommand\grid[1]{% - \begin{tikzpicture}[baseline=(char.base)] - \path[use as bounding box] - (0,0) rectangle (1em,1em); - \draw[red!50, fill=red!20] - (0,0) rectangle (1em,1em); - \node[inner sep=1pt,anchor=base west] - (char) at (0em,\gridraiseamount) {#1}; - \end{tikzpicture}} -\newcommand\gridraiseamount{0.12em} +%\newcommand\grid[1]{% +% \begin{tikzpicture}[baseline=(char.base)] +% \path[use as bounding box] +% (0,0) rectangle (1em,1em); +% \draw[red!50, fill=red!20] +% (0,0) rectangle (1em,1em); +% \node[inner sep=1pt,anchor=base west] +% (char) at (0em,\gridraiseamount) {#1}; +% \end{tikzpicture}} +%\newcommand\gridraiseamount{0.12em} -\makeatletter -\newcommand\Grid[1]{% - \@tfor\z:=#1\do{\grid{\z}}} -\makeatother +%\makeatletter +%\newcommand\Grid[1]{% +% \@tfor\z:=#1\do{\grid{\z}}} +%\makeatother -\newcommand\Vspace[1][.3em]{% - \mbox{\kern.06em\vrule height.3ex}% - \vbox{\hrule width#1}% - \hbox{\vrule height.3ex}} +%\newcommand\Vspace[1][.3em]{% +% \mbox{\kern.06em\vrule height.3ex}% +% \vbox{\hrule width#1}% +% \hbox{\vrule height.3ex}} -\def\VS{\Vspace[0.6em]} +%\def\VS{\Vspace[0.6em]} \begin{document} diff -r 739039774cee -r 94b84d880c2b slides/slides12.pdf Binary file slides/slides12.pdf has changed diff -r 739039774cee -r 94b84d880c2b slides/slides12.tex --- a/slides/slides12.tex Mon Jan 24 00:14:02 2022 +0000 +++ b/slides/slides12.tex Tue Mar 22 00:36:18 2022 +0000 @@ -1,6 +1,6 @@ \documentclass[dvipsnames,14pt,t]{beamer} \usepackage{../slides} -\usepackage{../graphics} +\usepackage{../graphicss} \usepackage{../langs} \usepackage{../data} \usepackage{../grammar}