9 \usepackage[scaled=.95]{helvet}

     9 \usepackage[scaled=.9]{helvet}

    22 attention is that, like the Java programming language, it

    22 attention is that, like the Java programming language, Scala

    27 and elegant code; some therefore say Scala is the much better

    27 and elegant code. Some therefore say Scala is the much better

    28 Java. If you want to try it out, the Scala compiler can be

    28 Java. If you want to try it out yourself, the Scala compiler

    29 downloaded from

    29 can be downloaded from

    39 programming-style allows me to implement some of the functions

    39 programming-style allows me to implement the functions we will

    40 we will discuss with very small and elegant code. Since the

    40 discuss with very small code-snippets. Since the compiler is

    41 compiler is free, you can download it and run every example I

    41 free, you can download them and run every example I give. But

    42 give. But if you prefer, you can also translate the examples

    42 if you prefer, you can also easily translate the code-snippets

    47 also with IntelliJ, but for the small programs we will look at

    47 also with IntelliJ, but for the small programs I will develop

    48 the Emacs-editor id good for me and I will run programs on the

    48 the good old Emacs-editor is adequate for me and I will run

    49 command line. One advantage of Scala over Java is that it

    49 the programs on the command line. One advantage of Scala over Java

    50 includes an interpreter (a REPL, or Read-Eval-Print-Loop) with

    50 is that it includes an interpreter (a REPL, or

    51 which you can run and test small code-snippets without the

    51 Read-Eval-Print-Loop) with which you can run and test small

    52 need of the compiler. This helps a lot for interactively

    52 code-snippets without the need of the compiler. This helps a

    53 developing programs. Once you installed Scala correctly, you

    53 lot with interactively developing programs. Once you installed

    54 can start the interpreter by typing

    54 Scala correctly, you can start the interpreter by typing

    66 \noindent The precise output may vary due to the platform

    66 \noindent The precise response may vary due to the platform

    77 example you can type in is

    77 classic example you can try out is

    84 \noindent which prints out a string. Note that in this case

    84 \noindent Note that in this case there is no result: the

    85 there is no result: the reason is that {\tt print} does not

    85 reason is that {\tt print} does not actually produce a result

    86 actually produce a result (there is no {\tt res\_}), rather it

    86 (there is no {\tt resXX}), rather it is a function that causes

    87 is a function that causes the \emph{side-effect} of printing

    87 the \emph{side-effect} of printing out a string. Once you are

    88 out a string. Once you are more familiar with the functional

    88 more familiar with the functional programming-style, you will

    89 programming-style, you will know what the difference is

    89 know what the difference is between a function that returns a

    90 between a function that returns a result, like addition, and a

    90 result, like addition, and a function that causes a

    91 function that causes a side-effect, like {\tt print}. We shall

    91 side-effect, like {\tt print}. We shall come back to this

    92 come back to this later, but if you are curious, the latter

    92 point in due course, but if you are curious now, the latter

    97 The elegance and conciseness of Scala programs stems often

   130 The elegance and conciseness of Scala programs are often a

    98 from the fact that inductive datatypes can be easily defined.

   131 result of inductive datatypes that can be easily defined. For

    99 For example in ``every-day Mathematics'' we would define

   132 example in ``every-day mathematics'' we would define regular

   100 regular expressions simply by the grammar

   133 expressions simply by giving the grammar

   115 inner nodes and three kinds of leave nodes). If you are

   148 inner nodes---sequence, alternative and star---and three kinds

   149 of leave nodes---null, empty and character). If you are

   122 {\tt Rexp}. This will act as type for regular expressions.

   156 {\tt Rexp}. This will act as the type for regular expressions.

   125 in the other cases we do have arguments. For example the

   159 in all the other cases we do have arguments. For example the

   144 \noindent Given the grammar above, I hope you can see the

   178 \noindent In order to be an instance of {\tt Rexp}, each case

   145 underlying pattern. In order to be an instance of {\tt Rexp},

   179 object and case class needs to extend {\tt Rexp}. Given the

   146 each case object or case class needs to extend {\tt Rexp}. If

   180 grammar above, I hope you can see the underlying pattern. If

   147 you want to play with such definitions, feel free to define

   181 you want to play further with such definitions, feel free to

   148 for example binary trees.

   182 define for example binary trees.

   149 

   183 

   150 Once you make a definition like the one above, you can 

   184 Once you make a definition like the one above, you can

   151 represent, say, the regular expression for $a + b$ as

   185 represent, for example, the regular expression for $a + b$ in

   152 {\tt ALT(CHAR('a'), CHAR('b'))}. If you want to assign 

   186 Scala as {\tt ALT(CHAR('a'), CHAR('b'))}. Expressions such as

   153 this regular expression to a variable, you can just type

   187 {\tt 'a'} stand for ASCII characters. If you want to assign

   188 this regular expression to a variable, you can use the keyword

   189 {\tt val} and type

   160 \noindent In order to make such assignments there is no

   196 \noindent As you can see, in order to make such assignments,

   161 constructor need in the class (like in Java). However, if

   197 no constructor is required in the class (as in Java). However,

   162 there is the need, you can of course define such a constructor

   198 if there is the need for some non-standard initialisation, you

   163 in Scala. 

   199 can of course define such a constructor in Scala. But we omit

   164 

   200 this here. 

   165 Note that Scala says the variable {\tt r} is of type {\tt

   201 

   166 ALT}, not {\tt Rexp}. Scala always tries to find the most

   202 Note that Scala in its response says the variable {\tt r} is

   167 general type that is needed for a variable, but does not

   203 of type {\tt ALT}, not {\tt Rexp}. This might be a bit

   168 ``over-generalise''. In this case there is no need to give

   204 unexpected, but can be explained as follows: Scala always

   169 {\tt r} the more general type of {\tt Rexp}. This is different

   205 tries to find the most general type that is needed for a

   170 if you want to form a list of regular expressions, for example

   206 variable or expression, but does not ``over-generalise''. In

   207 this case there is no need to give {\tt r} the more general

   208 type of {\tt Rexp}. This is different if you want to form a

   209 list of regular expressions, for example

   177 \noindent In this case Scala needs to assign a type to the

   216 \noindent In this case Scala needs to assign a common type to

   178 regular expressions, so that it is compatible with the fact

   217 the regular expressions, so that it is compatible with the

   179 that list can only contain elements of a single type, in this

   218 fact that lists can only contain elements of a single type, in

   180 case this is {\tt Rexp}.\footnote{If you type in this example,

   219 this case the type is {\tt Rexp}.\footnote{If you type in this

   181 you will notice that the type contains some further

   220 example, you will notice that the type contains some further

   182 information, but lets ignore this for the moment.} Note that if a type takes another

   221 information, but lets ignore this for the moment.} 

   183 type as argument, this is written for example as

   222 

   184 {\tt List[Rexp]}.

   223 For types like {\tt List[...]} the general rule is that when a

   224 type takes another type as argument, then this is written in

   225 angle-brackets. This can also contain nested types as in {\tt

   226 List[Set[Rexp]]}, which is a list of sets each of which

   227 contains regular expressions.

   188 

   231 I mentioned above that Scala is a very elegant programming

   189 

   232 language for the code we will write in this module. This

   233 elegance mainly stems from the fact that functions can be

   234 implemented very easily in Scala. Lets first consider a

   235 problem from number theory, called the \emph{Collatz-series},

   236 which corresponds to a famous unsolved problem in

   237 mathematics.\footnote{See for example

   238 \url{http://mathworld.wolfram.com/CollatzProblem.html}.}

   239 Mathematician define this series as:

   240 

   241 \[

   242 collatz_{n + 1} \dn 

   243 \begin{cases}

   244 \frac{1}{2} * collatz_n & \text{if $collatz_n$ is even}\\

   245 3 * collatz_n + 1 & \text{if $collatz_n$ is odd}

   246 \end{cases}

   247 \]

   248 

   249 \noindent The famous unsolved question is whether this

   250 series started with any $n > 0$ as $collaz_0$ will always

   251 return to $1$. This is obvious when started with $1$, and also

   252 with $2$, but already needs a bit of head-scratching for the

   253 case of $3$.

   254 

   255 If we want to avoid the head-scratching, we could implement

   256 this as the following function in Scala:

   257 

   258 \begin{quote}

   259 \lstinputlisting[language=Scala]{../progs/collatz.scala}

   260 \end{quote}

   261 

   262 \noindent The keyword for function definitions is {\tt def}

   263 followed by the name of the function. After that you have a

   264 list of arguments (enclosed in parentheses and separated by

   265 commas). Each argument in this list needs its type annotated.

   266 In this case we only have one argument, which is of type {\tt

   267 BigInt}. This type stands for arbitrary precision integers.

   268 After the arguments comes the type of what the function

   269 returns---a Boolean in this case for indicating that the

   270 function has reached {\tt 1}. Finally, after the {\tt =} comes

   271 the \emph{body} of the function implementing what the function

   272 is supposed to do. What the {\tt collatz} function does should

   273 be pretty self-explanatory: the function first tests whether

   274 {\tt n} is equal to $1$ in which case it returns {\tt true}

   275 and so on.

   276 

   277 Notice a quirk in Scala's syntax for {\tt if}s: The condition

   278 needs to be enclosed in parentheses and the then-case comes

   279 right after the condition---there is no {\tt then} keyword in

   280 Scala.

   281 

   282 The real power of Scala comes, however, from the ability to

   283 define functions by \emph{pattern matching}. In the {\tt

   284 collatz} function above we need to test each case using a

   285 sequence of {\tt if}s. This can be very cumbersome and brittle

   286 if there are many cases. If we wanted to define a function

   287 over regular expressions in say Java, which does not have

   288 pattern-matching, the resulting code would just be awkward.

   289 

   290 Mathematicians already use the power of pattern-matching, for

   291 example, when they define the function that takes a regular

   292 expression and produces another regular expression that can

   293 recognise the reversed strings. The resulting recursive

   294 function is often defined as follows:

   295 

   296 \begin{center}

   297 \begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}

   298 $rev(\varnothing)$   & $\dn$ & $\varnothing$\\

   299 $rev(\epsilon)$      & $\dn$ & $\epsilon$\\

   300 $rev(c)$             & $\dn$ & $c$\\

   301 $rev(r_1 + r_2)$     & $\dn$ & $rev(r_1) + rev(r_2)$\\

   302 $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\

   303 $rev(r^*)$                   & $\dn$ & $rev(r)^*$\\

   304 \end{tabular}

   305 \end{center}

   306 

   307 \noindent The corresponding Scala code looks very similar

   308 to this definition, thanks to pattern-matching.

   309 

   310 

   311 \begin{quote}

   312 \lstinputlisting[language=Scala]{../progs/rev.scala}

   313 \end{quote}

   314 

   315 \noindent The keyword for starting a pattern-match is {\tt

   316 match} followed by a list of {\tt case}s. Before the match

   317 can be another pattern, but often as in the case above, 

   318 it is just a variable you want to pattern-match.

   319 

   320 In the {\tt rev}-function above, each case follows the

   321 structure of how we defined regular expressions as inductive

   322 datatype. For example the case in Line 3 you can read as: if

   323 the regular expression {\tt r} is of the form {\tt EMPTY} then

   324 do whatever follows the {\tt =>} (in this case just return

   325 {\tt EMPTY}). Line 5 reads as: if the regular expression

   326 {\tt r} is of the form {\tt ALT(r1, r2)}, where the

   327 left-branch of the alternative is matched by the variable {\tt

   328 r1} and the right-branch by {\tt r2} then do ``something''.

   329 The ``something'' can now use the variables {\tt r1} and {\tt

   330 r2} from the match. 

   331 

   332 If you want to play with this function, call, it for 

   333 example, with the regular expression $ab + ac$. This regular

   334 expression can recognise the strings $ab$ and $ac$. The 

   335 function {\tt rev} produces the result $ba + ca$, which

   336 can recognise the reversed strings $ba$ and $ca$.

   337 

   338 In Scala each pattern-match can also be guarded as in

   339 

   340 \begin{quote}

   341 \begin{lstlisting}[language=Scala, numbers=none]

   342 case Pattern if Condition => Do_Something

   343 \end{lstlisting}

   344 \end{quote}

   345 

   346 \noindent This allows us, for example, to re-write the {\tt

   347 collatz}-function from above as follows:

   348  

   349 \begin{quote}

   350 \lstinputlisting[language=Scala]{../progs/collatz2.scala}

   351 \end{quote}

   352 

   353 \noindent Although in this case the pattern-match does not

   354 improve the code in any way. The underscore in the last case

   355 indicates that we do not care what the pattern looks like. 

   356 Thus Line 4 acts like a default case whenever the cases above 

   357 did not match. Cases are always tried out from top to bottom.

   358  

   359 \subsection*{Loops}

   360 

   361 Coming from Java or C, you might be surprised that Scala does

   362 not really have loops. It has instead, what is in functional

   363 programming called \emph{maps}. To illustrate how they work,

   364 lets assume you have a list of numbers from 1 to 10 and want to

   365 build the list of squares. The list of numbers from 1 to 10 

   366 can be constructed in Scala as follows:

   367 

   368 \begin{alltt}

   369 scala> (1 to 10).toList

   370 res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

   371 \end{alltt}

   372 

   373 \noindent Generating from this list the list of squares in a

   374 non-functional language (e.g.~Java), you would assume the list

   375 is given as a kind of array. You would then iterate, or loop,

   376 an index over this array and replace each entry in the array

   377 by the square. Right? In Scala, and in other functional

   378 programming languages, you use maps to achieve the same. 

   379 

   380 Maps essentially take a function that describes how each

   381 element is transformed (for example squaring) and a list over

   382 which this function should work. There are two forms to

   383 express maps in Scala. The first way is in a {\tt

   384 for}-construction. Squaring the numbers from 1 to 10 would

   385 look in this form as follows:

   386 

   387 \begin{alltt}

   388 scala> for (n <- (1 to 10).toList) yield n * n

   389 res2: List[Int] = List(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)

   390 \end{alltt}

   391 

   392 \noindent The keywords are {\tt for} and {\tt yield}. This

   393 {\tt for}-construction roughly says that from the list of

   394 numbers we draw {\tt n}s and compute the result of {\tt n *

   395 n}. In consequence we specified the list where each {\tt n}

   396 comes from, namely {\tt (1 to 10).toList}, and how each

   397 element needs to be transformed. This can also be expressed

   398 in a second way by using directly {\tt map} as follows:

   399 

   400 \begin{alltt}

   401 scala> (1 to 10).toList.map(n => n * n)

   402 res3 = List(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)

   403 \end{alltt}

   404 

   405 \noindent In this way the expression {\tt n => n * n} stands

   406 for the function that calculates the square (this is how the

   407 {\tt n}s are transformed). This expression for functions might

   408 remind you on your lessons about the lambda-calculus where

   409 this would have been written as $\lambda n.\,n * n$.

   410 

   411 It might not be obvious, but {\tt for}-constructions are just

   412 syntactic sugar: when compiling, Scala translates them into

   413 equivalent maps.

   414 

   415 

   416 The very charming feature of Scala is that such maps or {\tt

   417 for}-constructions can be written for any kind of data

   418 collection, such as lists, sets, vectors and so on. For

   419 example if we instead compute the reminders modulo $3$ of this

   420 list, we can write

   421 

   422 \begin{alltt}

   423 scala> (1 to 10).toList.map(n => n \% 3)

   424 res4 = List(1, 2, 0, 1, 2, 0, 1, 2, 0, 1)

   425 \end{alltt}

   426 

   427 \noindent If we, however, transform the numbers 1 to 10 not

   428 into a list, but into a set, and then compute the reminders

   429 modulo $3$ we obtain

   430 

   431 \begin{alltt}

   432 scala> (1 to 10).toSet[Int].map(n => n \% 3)

   433 res5 = Set(2, 1, 0)

   434 \end{alltt}

   435 

   436 \noindent This is the correct result for sets, as there are

   437 only 3 equivalence classes of integers modulo 3. Note that we

   438 need to ``help'' Scala in this example to transform the

   439 numbers into a set of integers by explicitly annotating the

   440 type {\tt Int}. Since maps and {\tt for}-construction are just

   441 syntactic variants of each other, the latter can also be

   442 written as

   443 

   444 \begin{alltt}

   445 scala> for (n <- (1 to 10).toSet[Int]) yield n \% 3

   446 res5 = Set(2, 1, 0)

   447 \end{alltt}

   448 

   449 While hopefully this all looks reasonable, there is one

   450 complication: In the examples above we always wanted to

   451 transform one list into another list (e.g.~list of squares),

   452 or one set into another set (set of numbers into set of

   453 reminders modulo 3). What happens if we just want to print out

   454 a list of integers? Then actually the {\tt for}-construction

   455 needs to be modified. The reason is that {\tt print}, you

   456 guessed it, does not produce any result, but only produces, in

   457 the functional-programming-lingo, a side-effect. Printing out

   458 the list of numbers from 1 to 5 would look as follows

   459 

   460 \begin{alltt}

   461 scala> for (n <- (1 to 5).toList) println(n)

   462 1

   463 2

   464 3

   465 4

   466 5

   467 \end{alltt}

   468 

   469 \noindent

   470 where you need to omit the keyword {\tt yield}. You can

   471 also do more elaborate calculations such as

   472 

   473 \begin{alltt}

   474 scala> for (n <- (1 to 5).toList) \{

   475   val square_n = n * n

   476   println(s"$n * $n = $square_n") 

   477 \}

   478 1 * 1 = 1

   479 2 * 2 = 4

   480 3 * 3 = 9

   481 4 * 4 = 16

   482 5 * 5 = 25

   483 \end{alltt}

   484 

   485 \noindent

   486 In this code I use a \emph{string interpolation},

   487 written {\tt s"..."} in order to print out an equation.

   488 This string interpolation allows me to refer to the integer 

   489 values {\tt n} and {\tt square\_n} inside a string. This

   490 is very convenient for printing out ``things''. 

   491 

   492 The corresponding map construction for functions with 

   493 side-effexts is in Scala called {\tt foreach}. So you 

   494 could also write

   495 

   496 \begin{alltt}

   497 scala> (1 to 5).toList.foreach(n => println(n))

   498 1

   499 2

   500 3

   501 4

   502 5

   503 \end{alltt}

   504 

   505 \noindent or even just

   506 

   507 \begin{alltt}

   508 scala> (1 to 5).toList.foreach(println)

   509 1

   510 2

   511 3

   512 4

   513 5

   514 \end{alltt}

   515 

   516 \noindent If you want to find out more maps and functions

   517 with side-efffects, you can ponder about the response Scala

   518 gives if you replace {\tt foreach} by {\tt map} in the

   519 expression above. Scala will still allow {\tt map}, but

   520 then reacts with an interesting result.