afl-material: comparison handouts/scala-ho.tex

equal deleted inserted replaced

-:370c0647a9bf
+:527fdb90fffe
 \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, for example, I
-would first have to run through heaps of boilerplate code and
+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, Standard ML, F$^\#$, Ocaml and so on.
 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 have as return type
+now, the latter kind of functions always has as return type
 \code{Unit}.
 If you want to write a stand-alone app in Scala, you can
 implement an object that is an instance of \code{App}, say
 $ 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. For
+result of inductive datatypes that can be easily defined in
-example in ``every-day mathematics'' we define regular
+Scala. For example in ``every-day mathematics'' we define
-expressions simply by giving the grammar
+regular expressions simply by giving the grammar
 \begin{center}
 \begin{tabular}{r@{\hspace{2mm}}r@{\hspace{2mm}}l@{\hspace{13mm}}l}
 $r$ & $::=$ &   $\varnothing$         & null\\
 & $\mid$ & $\epsilon$           & empty string\\
 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, for example, the regular expression for $a + b$
+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
 Notice a 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
 \code{collatz}-function from above as follows:
 \lstinputlisting[language=Scala]{../progs/collatz2.scala}
-\noindent Although in this case the pattern-match does not
+\noindent Although in this particular case the pattern-match
-improve the code in any way. In cases like \code{rev} it
+does not improve the code in any way. In cases like \code{rev}
-is really crucial. The underscore in the last case indicates
+it is really crucial. The underscore in Line 4 indicates that
-that we do not care what the pattern looks like. Thus Line 4
+we do not care what the patter8n 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 the Absence of}
 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,
-lets assume you have a list of numbers from 1 to 10 and want to
+lets 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 10
+build the list of squares. The list of numbers from 1 to 8
 can be constructed in Scala as follows:
 \begin{lstlisting}[language=Scala,numbers=none]
-scala> (1 to 10).toList
+scala> (1 to 8).toList
-res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
+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,
 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
-for-comprehension. Squaring the numbers from 1 to 10 would
+\emph{for-comprehension}. Squaring the numbers from 1 to 8
-look in this form as follows:
+would look in this form as follows:
 \begin{lstlisting}[language=Scala,numbers=none]
-scala> for (n <- (1 to 10).toList) yield n * n
+scala> for (n <- (1 to 8).toList) yield n * n
-res2: List[Int] = List(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)
+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 10).toList}, and
+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}[language=Scala,numbers=none]
-scala> (1 to 10).toList.map(n => n * n)
+scala> (1 to 8).toList.map(n => n * n)
-res3 = List(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)
+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
 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}[language=Scala,numbers=none]
-scala> (1 to 10).toList.map(n => n % 3)
+scala> (1 to 8).toList.map(n => n % 3)
-res4 = List(1, 2, 0, 1, 2, 0, 1, 2, 0, 1)
+res4 = List(1, 2, 0, 1, 2, 0, 1, 2)
 \end{lstlisting}
-\noindent If we, however, transform the numbers 1 to 10 not
+\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}[language=Scala,numbers=none]
-scala> (1 to 10).toSet[Int].map(n => n % 3)
+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
 type \code{Int}. Since maps and for-comprehensions are
 just syntactic variants of each other, the latter can also be
 written as
 \begin{lstlisting}[language=Scala,numbers=none]
-scala> for (n <- (1 to 10).toSet[Int]) yield n % 3
+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
 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
+\noindent The \code{if}-condition in the for-comprehension
-The \code{if}-condition filters out all pairs where the
+filters out all pairs where the sum is not even.
-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
 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}[language=Scala,numbers=none]
-scala> for (n <- (1 to 5).toList) println(n)
+scala> for (n <- (1 to 5).toList) print(n)
-1
+12345
-2
-3
-4
-5
 \end{lstlisting}
 \noindent
 where you need to omit the keyword \code{yield}. You can
 also do more elaborate calculations such as
 side-effects is in Scala called \code{foreach}. So you
 could also write
 \begin{lstlisting}[language=Scala,numbers=none]
-scala> (1 to 5).toList.foreach(n => println(n))
+scala> (1 to 5).toList.foreach(n => print(n))
-1
+12345
-2
-3
-4
-5
 \end{lstlisting}
 \noindent or even just
+\begin{lstlisting}[language=Scala,numbers=none]
-\begin{lstlisting}[language=Scala,numbers=none]
+scala> (1 to 5).toList.foreach(print)
-scala> (1 to 5).toList.foreach(println)
+12345
-1
+\end{lstlisting}
-2
-3
-4
-5
-\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.
 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}?
+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
 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 \code{(Int, Int, String)} for a
+with parentheses. For example
-triple consisting of two integers and a string. Tuples are
-helpful if you want to define functions with multiple
+\begin{lstlisting}[language=Scala, numbers=none]
-results, say the function returning the quotient and reminder
+(Int, Int, String)
-of two numbers. For this you might define:
+\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}[language=Scala, numbers=none]
 def quo_rem(m: Int, n: Int) : (Int, Int) = (m / n, m % n)
 \end{lstlisting}
-\noindent
+\noindent Since this function returns a pair of integers, its
-Since this function returns a pair of integers, its
+return type needs to be of type \code{(Int, Int)}.
-return type needs to be \code{(Int, Int)}. Incidentally,
+Incidentally, this is also the input type of this function.
-this is also the input type of this function. Notice it takes
+Notice this function takes \emph{two} arguments, namely
-\emph{two} arguments, namely \code{m} and \code{n}, both
+\code{m} and \code{n}, both of which are integers. They are
-of which are integers. They are ``packaged'' in a pair.
+``packaged'' in a pair. Consequently the complete type of
-Consequently the complete type of \code{quo_rem} is
+\code{quo_rem} is
 \begin{lstlisting}[language=Scala, 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 argument
 and produces a string. A function of this type is for instance
 \begin{lstlisting}[language=Scala,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 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
 and the result of the function is a boolean. Though silly, a
 function of this type would be
 \begin{lstlisting}[language=Scala,numbers=none]
-def chk_string(n: Int, s: String) : Boolean =
+def chk_string(n: Int)(s: String) : Boolean =
 mk_string(n) == s
 \end{lstlisting}
-\noindent which checks whether the integer \code{n} corresponds
+\noindent which checks whether the integer \code{n}
-to the name \code{s} given by the function \code{mk\_string}.
+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}[language=Scala,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 one 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 is their type (in this case two arguments,
+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).
+returning a string). Remember that \code{mk_string} is just
+such a function. So how can we use it? For this define
-Now you might ask, what is the point of having function as
+the somewhat silly function \code{apply_3}
-arguments to other functions? In Java there is no need of this
-kind of feature. But in all functional programming languages,
+\begin{lstlisting}[language=Scala,numbers=none]
-including Scala, it is really essential. Above you already
+def apply_3(f: Int => String): Bool = f(3) == "many"
-seen \code{map} and \code{foreach} which need this. Consider
-the functions \code{print} and \code{println}, which both
+scala> apply_3(mk_string)
-print out strings, but the latter adds a line break. You can
+res6 = true
-call \code{foreach} with either of them and thus changing how,
+\end{lstlisting}
-for example, five numbers are printed.
+You might ask, apart from silly functions like above, what is
+the point of having function as arguments to other functions?
+In Java there is indeed no need of this kind of feature. But
+in all functional programming languages, including Scala, it
+is really essential. 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}[language=Scala,numbers=none]
 scala> (1 to 5).toList.foreach(print)
 12345
 My second wow-moment I had with a feature of Scala that other
 functional programming languages also 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
+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}:
 regular expression above. But then your code is littered with
 such conversion function.
 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 \code{implicitConversions}.
+it needs a built-in library called
+\begin{lstlisting}[language=Scala,numbers=none]
+scala.language.implicitConversions
+\end{lstlisting}
+\noindent
 Consider the code
 \begin{lstlisting}[language=Scala]
 import scala.language.implicitConversions
 insert a call to the \code{string2rexp}-function. I can now
 write for example
 \begin{lstlisting}[language=Scala,numbers=none]
 scala> ALT("ab", "ac")
-res9: ALT = ALT(SEQ(CHAR(a),CHAR(b)),SEQ(CHAR(a),CHAR(c)))
+res9 = ALT(SEQ(CHAR(a),CHAR(b)),SEQ(CHAR(a),CHAR(c)))
 \end{lstlisting}
 \noindent \code{ALT} expects two regular expressions
 as arguments, but I only supply two strings. The implicit
 conversion function will transform the string into
 Using implicit definitions, Scala allows me to introduce
 some further syntactic sugar for regular expressions:
-\begin{lstlisting}[language=Scala]
+\begin{lstlisting}[language=Scala, numbers=none]
 implicit def RexpOps(r: Rexp) = new {
 def | (s: Rexp) = ALT(r, s)
 def ~ (s: Rexp) = SEQ(r, s)
 def % = STAR(r)
 }
 even simpler as
 \begin{lstlisting}[language=Scala,numbers=none]
 scala> "ab" | "ac"
-res10: ALT = ALT(SEQ(CHAR(a),CHAR(b)),SEQ(CHAR(a),CHAR(c)))
+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.

changeset 238	527fdb90fffe
parent 237	370c0647a9bf
child 239	68d98140b90b