diff -r 93bd75031ced -r 4df4404455d0 handouts/scala-ho.tex --- a/handouts/scala-ho.tex Thu Aug 21 15:10:53 2014 +0100 +++ b/handouts/scala-ho.tex Sun Aug 24 10:49:21 2014 +0100 @@ -9,43 +9,51 @@ \usepackage[scaled=.95]{helvet} \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% - +\definecolor{codegray}{gray}{0.9} +\newcommand{\code}[1]{\colorbox{codegray}{\texttt{#1}}} \begin{document} \section*{A Crash-Course on Scala} Scala is programming language that combines functional and -object-oriented programming-styles. This language received in -the last five years quite a bit of attention. One reason is -that, like the Java programming language, it compiles to the -Java Virtual Machine (JVM) and therefore can run under MacOSX, -Linux and Windows.\footnote{There are also experimental -backends for Android and JavaScript.} The main compiler can be +object-oriented programming-styles, and has received in the +last five years quite a bit of attention. One reason for this +attention is that, like the Java programming language, it +compiles to the Java Virtual Machine (JVM) and therefore can +run under MacOSX, Linux and Windows.\footnote{There are also +experimental backends for Android and JavaScript.} Unlike +Java, however, Scala often allows programmers to write concise +and elegant code; some therefore say Scala is the much better +Java. If you want to try it out, the Scala compiler can be downloaded from \begin{quote} \url{http://www.scala-lang.org} \end{quote} -\noindent Why do I use Scala in this course? Actually, you can -do any part of the programming coursework in \emph{any} -programming language you like. I use Scale because its -functional programming-style allows for some very small and -elegant code. Since the compiler is free, you can download it -and run every example I give. But if you prefer, you can also -translate the examples into any other functional language, for -example Haskell, ML, F\# and so on. +Why do I use Scala in the AFL course? Actually, you can do +\emph{any} part of the programming 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 some of the functions +we will discuss with very small and elegant code. Since the +compiler is free, you can download it and run every example I +give. But if you prefer, you can also translate the examples +into any other functional language, for example Haskell, ML, +F\# and so on. -Writing programs in Scala can be done with Eclipse IDE and -also with IntelliJ, but I am using just the Emacs-editor and -run programs on the command line. One advantage of Scala is -that it has an interpreter (a REPL --- read-eval-print-loop) -with which you can run and test small code-snippets without -the need of the compiler. This helps a lot for interactively +Writing programs in Scala can be done with the Eclipse IDE and +also with IntelliJ, but for the small programs we will look at +the Emacs-editor id good for me and I will run programs on the +command line. One advantage of Scala over Java is that it +includes an interpreter (a REPL, or Read-Eval-Print-Loop) with +which you can run and test small code-snippets without the +need of the compiler. This helps a lot for interactively developing programs. Once you installed Scala correctly, you can start the interpreter by typing + \begin{alltt} $ scala\small Welcome to Scala version 2.11.2 (Java HotSpot(TM) 64-Bit Server VM). @@ -55,18 +63,18 @@ scala> \end{alltt} -\noindent At the scala prompt you can type things like {\tt 2 + 3} -\keys{Ret}. The output will be +\noindent The precise output may vary due to the platform +where you installed Scala. At the scala prompt you can type +things like {\tt 2 + 3} \keys{Ret} and the output will be \begin{alltt} scala> 2 + 3 res0: Int = 5 \end{alltt} -\noindent -indicating that the result is of type {\tt Int} and the result -of the addition is {\tt 5}. Another example you can type in -immediately is +\noindent indicating that the result of the addition is of +type {\tt Int} and the actual result is {\tt 5}. Another +example you can type in is \begin{alltt} scala> print ("hello world") @@ -75,20 +83,21 @@ \noindent which prints out a string. Note that in this case there is no result: the reason is that {\tt print} does not -produce any result indicated by {\tt res\_}, rather it is a -function that causes a \emph{side-effect} of printing out a -string. Once you are more familiar with the functional -programming-style, you will immediately see what the -difference is between a function that returns a result and a -function that causes a side-effect (the latter always has as -return type {\tt Unit}). +actually produce a result (there is no {\tt res\_}), 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 {\tt print}. We shall +come back to this later, but if you are curious, the latter +kind of functions always have as return type {\tt Unit}. \subsection*{Inductive Datatypes} The elegance and conciseness of Scala programs stems often from the fact that inductive datatypes can be easily defined. -For example in ``Mathematics'' we would define regular -expressions by the grammar +For example in ``every-day Mathematics'' we would define +regular expressions simply by the grammar \begin{center} \begin{tabular}{r@{\hspace{2mm}}r@{\hspace{2mm}}l@{\hspace{13mm}}l} @@ -103,284 +112,86 @@ \noindent This grammar specifies what regular expressions are (essentially a kind of tree-structure with three kinds of -inner nodes and three leave nodes). If you are familiar with -Java, it might be an instructive exercise to define this -kind of inductive datatypes in Java. - -Implementing the regular expressions from above in Scala -requires an \emph{abstract class}, say, {\tt Rexp}. The -different kinds of regular expressions will be instances of -this abstract class. The cases for $\varnothing$ and -$\epsilon$ do not require any arguments, while in the other -cases we do have arguments. For example the character regular -expressions need to take as argument the character they are -supposed to recognise. - -. is a relative recen programming language -This course is about the processing of strings. Lets start -with what we mean by \emph{strings}. Strings (they are also -sometimes referred to as \emph{words}) are lists of characters -drawn from an \emph{alphabet}. If nothing else is specified, -we usually assume the alphabet consists of just the lower-case -letters $a$, $b$, \ldots, $z$. Sometimes, however, we -explicitly restrict strings to contain, for example, only the -letters $a$ and $b$. In this case we say the alphabet is the -set $\{a, b\}$. +inner nodes and three kinds of leave nodes). If you are +familiar with Java, it might be an instructive exercise to +define this kind of inductive datatypes in +Java.\footnote{Happy programming! ;o)} -There are many ways how we can write down strings. In programming languages, they are usually -written as {\it "hello"} where the double quotes indicate that we dealing with a string. -Essentially, strings are lists of characters which can be written for example as follows - -\[ -[\text{\it h, e, l, l, o}] -\] - -\noindent -The important point is that we can always decompose strings. For example, we will often consider the -first character of a string, say $h$, and the ``rest'' of a string say {\it "ello"} when making definitions -about strings. There are some subtleties with the empty string, sometimes written as {\it ""} but also as -the empty list of characters $[\,]$. Two strings, for example $s_1$ and $s_2$, can be \emph{concatenated}, -which we write as $s_1 @ s_2$. Suppose we are given two strings {\it "foo"} and {\it "bar"}, then their concatenation -gives {\it "foobar"}. - -We often need to talk about sets of strings. For example the set of all strings over the alphabet $\{a, \ldots\, z\}$ -is - -\[ -\{\text{\it "", "a", "b", "c",\ldots,"z", "aa", "ab", "ac", \ldots, "aaa", \ldots}\} -\] - -\noindent -Any set of strings, not just the set-of-all-strings, is often called a \emph{language}. The idea behind -this choice of terminology is that if we enumerate, say, all words/strings from a dictionary, like +Implementing the regular expressions from above in Scala is +very simple: It first requires an \emph{abstract class}, say, +{\tt Rexp}. This will act as type for regular expressions. +Second, it requires some instances. The cases for +$\varnothing$ and $\epsilon$ do not have any arguments, while +in 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}, while the +ones with arguments are \emph{case classes}. The corresponding +code is as follows: -\[ -\{\text{\it "the", "of", "milk", "name", "antidisestablishmentarianism", \ldots}\} -\] - -\noindent -then we have essentially described the English language, or more precisely all -strings that can be used in a sentence of the English language. French would be a -different set of strings, and so on. In the context of this course, a language might -not necessarily make sense from a natural language point of view. For example -the set of all strings shown above is a language, as is the empty set (of strings). The -empty set of strings is often written as $\varnothing$ or $\{\,\}$. Note that there is a -difference between the empty set, or empty language, and the set that -contains only the empty string $\{\text{""}\}$: the former has no elements, whereas -the latter has one element. - -As seen, there are languages which contain infinitely many strings, like the set of all strings. -The ``natural'' languages like English, French and so on contain many but only finitely many -strings (namely the ones listed in a good dictionary). It might be therefore be surprising that the -language consisting of all email addresses is infinite provided we assume it is defined by the -regular expression\footnote{See \url{http://goo.gl/5LoVX7}} - -\[ -([\text{\it{}a-z0-9\_.-}]^+)@([\text{\it a-z0-9.-}]^+).([\text{\it a-z.}]^{\{2,6\}}) -\] +\begin{quote} +\begin{lstlisting}[language=Scala] +abstract class Rexp +case object NULL extends Rexp +case object EMPTY 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} +\end{quote} -\noindent -One reason is that before the $@$-sign there can be any string you want assuming it -is made up from letters, digits, underscores, dots and hyphens---clearly there are infinitely many -of those. Similarly the string after the $@$-sign can be any string. However, this does not mean -that every string is an email address. For example - -\[ -"\text{\it foo}@\text{\it bar}.\text{\it c}" -\] - -\noindent -is not, because the top-level-domains must be of length of at least two. (Note that there is -the convention that uppercase letters are treated in email-addresses as if they were -lower-case.) -\bigskip - -Before we expand on the topic of regular expressions, let us review some operations on -sets. We will use capital letters $A$, $B$, $\ldots$ to stand for sets of strings. -The union of two sets is written as usual as $A \cup B$. We also need to define the -operation of \emph{concatenating} two sets of strings. This can be defined as - -\[ -A @ B \dn \{s_1@ s_2 | s_1 \in A \wedge s_2 \in B \} -\] - -\noindent -which essentially means take the first string from the set $A$ and concatenate it with every -string in the set $B$, then take the second string from $A$ do the same and so on. You might -like to think about what this definition means in case $A$ or $B$ is the empty set. - -We also need to define -the power of a set of strings, written as $A^n$ with $n$ being a natural number. This is defined inductively as follows +\noindent Given the grammar above, I hope you can see the +underlying pattern. In order to be an instance of {\tt Rexp}, +each case object or case class needs to extend {\tt Rexp}. If +you want to play with such definitions, feel free to define +for example binary trees. -\begin{center} -\begin{tabular}{rcl} -$A^0$ & $\dn$ & $\{[\,]\}$ \\ -$A^{n+1}$ & $\dn$ & $A @ A^n$\\ -\end{tabular} -\end{center} - -\noindent -Finally we need the \emph{star} of a set of strings, written $A^*$. This is defined as the union -of every power of $A^n$ with $n\ge 0$. The mathematical notation for this operation is - -\[ -A^* \dn \bigcup_{0\le n} A^n -\] - -\noindent -This definition implies that the star of a set $A$ contains always the empty string (that is $A^0$), one -copy of every string in $A$ (that is $A^1$), two copies in $A$ (that is $A^2$) and so on. In case $A=\{"a"\}$ we therefore -have - -\[ -A^* = \{"", "a", "aa", "aaa", \ldots\} -\] - -\noindent -Be aware that these operations sometimes have quite non-intuitive properties, for example +Once you make a definition like the one above, you can +represent, say, the regular expression for $a + b$ as +{\tt ALT(CHAR('a'), CHAR('b'))}. If you want to assign +this regular expression to a variable, you can just type -\begin{center} -\begin{tabular}{@{}ccc@{}} -\begin{tabular}{@{}r@{\hspace{1mm}}c@{\hspace{1mm}}l} -$A \cup \varnothing$ & $=$ & $A$\\ -$A \cup A$ & $=$ & $A$\\ -$A \cup B$ & $=$ & $B \cup A$\\ -\end{tabular} & -\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} -$A @ B$ & $\not =$ & $B @ A$\\ -$A @ \varnothing$ & $=$ & $\varnothing @ A = \varnothing$\\ -$A @ \{""\}$ & $=$ & $\{""\} @ A = A$\\ -\end{tabular} & -\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l@{}} -$\varnothing^*$ & $=$ & $\{""\}$\\ -$\{""\}^*$ & $=$ & $\{""\}$\\ -$A^\star$ & $=$ & $\{""\} \cup A\cdot A^*$\\ -\end{tabular} -\end{tabular} -\end{center} -\bigskip +\begin{alltt} +scala> val r = ALT(CHAR('a'), CHAR('b')) +r: ALT = ALT(CHAR(a),CHAR(b)) +\end{alltt} -\noindent -\emph{Regular expressions} are meant to conveniently describe languages...at least languages -we are interested in in Computer Science. For example there is no convenient regular expression -for describing the English language short of enumerating all English words. -But they seem useful for describing all permitted email addresses, as seen above. +\noindent In order to make such assignments there is no +constructor need in the class (like in Java). However, if +there is the need, you can of course define such a constructor +in Scala. -Regular expressions are given by the following grammar: - -\begin{center} -\begin{tabular}{r@{\hspace{1mm}}r@{\hspace{1mm}}l@{\hspace{13mm}}l} - $r$ & $::=$ & $\varnothing$ & null\\ - & $\mid$ & $\epsilon$ & empty string / "" / []\\ - & $\mid$ & $c$ & single character\\ - & $\mid$ & $r_1 \cdot r_2$ & sequence\\ - & $\mid$ & $r_1 + r_2$ & alternative / choice\\ - & $\mid$ & $r^*$ & star (zero or more)\\ - \end{tabular} -\end{center} - -\noindent -Because we overload our notation, there are some subtleties you should be aware of. First, the letter -$c$ stands for any character from the -alphabet at hand. Second, we will use parentheses to disambiguate -regular expressions. For example we will write $(r_1 + r_2)^*$, which is different from, say $r_1 + (r_2)^*$. -The former means roughly zero or more times $r_1$ or $r_2$, while the latter means $r_1$ or zero or more times -$r_2$. We should also write $(r_1 + r_2) + r_3$, which is different from the regular expression $r_1 + (r_2 + r_3)$, -but in case of $+$ and $\cdot$ we actually do not care about the order and just write $r_1 + r_2 + r_3$, or $r_1 \cdot r_2 \cdot r_3$, -respectively. The reasons for this will become clear shortly. In the literature you will often find that the choice -$r_1 + r_2$ is written as $r_1\mid{}r_2$ or $r_1\mid\mid{}r_2$. Also following the convention in the literature, we will in case of $\cdot$ even -often omit it all together. For example the regular expression for email addresses shown above is meant to be of the form +Note that Scala says the variable {\tt r} is of type {\tt +ALT}, not {\tt Rexp}. Scala always tries to find the most +general type that is needed for a variable, but does not +``over-generalise''. In this case there is no need to give +{\tt r} the more general type of {\tt Rexp}. This is different +if you want to form a list of regular expressions, for example -\[ -([\ldots])^+ \cdot @ \cdot ([\ldots])^+ \cdot . \cdot \ldots -\] - -\noindent -meaning first comes a name (specified by the regular expression $([\ldots])^+$), then an $@$-sign, then -a domain name (specified by the regular expression $([\ldots])^+$), then a dot and then a top-level domain. Similarly if -we want to specify the regular expression for the string {\it "hello"} we should write - -\[ -{\it h} \cdot {\it e} \cdot {\it l} \cdot {\it l} \cdot {\it o} -\] +\begin{alltt} +scala> val ls = List(ALT(CHAR('a'), CHAR('b')), NULL) +ls: List[Rexp] = List(ALT(CHAR(a),CHAR(b)), NULL) +\end{alltt} -\noindent -but often just write {\it hello}. - -Another source of confusion might arise from the fact that we use the term \emph{regular expression} for the regular expressions used in ``theory'' -and also the ones used in ``practice''. In this course we refer by default to the regular expressions defined by the grammar above. -In ``practice'' we often use $r^+$ to stand for one or more times, $\backslash{}d$ to stand for a digit, $r^?$ to stand for an optional regular -expression, or ranges such as $[\text{\it a - z}]$ to stand for any lower case letter from $a$ to $z$. They are however mere convenience -as they can be seen as shorthand for +\noindent In this case Scala needs to assign a type to the +regular expressions, so that it is compatible with the fact +that list can only contain elements of a single type, in this +case this is {\tt Rexp}.\footnote{If you type in this example, +you will notice that the type contains some further +information, but lets ignore this for the moment.} Note that if a type takes another +type as argument, this is written for example as +{\tt List[Rexp]}. -\begin{center} -\begin{tabular}{rcl} -$r^+$ & $\mapsto$ & $r\cdot r^*$\\ -$r^?$ & $\mapsto$ & $\epsilon + r$\\ -$\backslash d$ & $\mapsto$ & $0 + 1 + 2 + \ldots + 9$\\ -$[\text{\it a - z}]$ & $\mapsto$ & $a + b + \ldots + z$\\ -\end{tabular} -\end{center} +\subsection*{Functions and Pattern-Matching} -We will see later that the \emph{not}-regular-expression can also be seen as convenience. This regular -expression is supposed to stand for every string \emph{not} matched by a regular expression. We will write -such not-regular-expressions as $\sim{}r$. While being ``convenience'' it is often not so clear what the shorthand for -these kind of not-regular-expressions is. Try to write down the regular expression which can match any -string except the two strings {\it "hello"} and {\it "world"}. It is possible in principle, but often it is easier to just include -$\sim{}r$ in the definition of regular expressions. Whenever we do so, we will state it explicitly. -So far we have only considered informally what the \emph{meaning} of a regular expression is. -To do so more formally we will associate with every regular expression a set of strings -that is supposed to be matched by this -regular expression. This can be defined recursively as follows - -\begin{center} -\begin{tabular}{rcl} -$L(\varnothing)$ & $\dn$ & $\{\,\}$\\ -$L(\epsilon)$ & $\dn$ & $\{""\}$\\ -$L(c)$ & $\dn$ & $\{"c"\}$\\ -$L(r_1+ r_2)$ & $\dn$ & $L(r_1) \cup L(r_2)$\\ -$L(r_1 \cdot r_2)$ & $\dn$ & $\{s_1@ s_2 | s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$\\ -$L(r^*)$ & $\dn$ & $\bigcup_{n \ge 0} L(r)^n$\\ -\end{tabular} -\end{center} -\noindent -As a result we can now precisely state what the meaning, for example, of the regular expression -${\it h} \cdot {\it e} \cdot {\it l} \cdot {\it l} \cdot {\it o}$ is, namely -$L({\it h} \cdot {\it e} \cdot {\it l} \cdot {\it l} \cdot {\it o}) = \{\text{\it"hello"}\}$...as expected. Similarly if we have the -choice-regular-expression $a + b$, its meaning is $L(a + b) = \{\text{\it"a"}, \text{\it"b"}\}$, namely the only two strings which can possibly -be matched by this choice. You can now also see why we do not make a difference -between the different regular expressions $(r_1 + r_2) + r_3$ and $r_1 + (r_2 + r_3)$....they -are not the same regular expression, but have the same meaning. - -The point of the definition of $L$ is that we can use it to precisely specify when a string $s$ is matched by a -regular expression $r$, namely only when $s \in L(r)$. In fact we will write a program {\it match} that takes any string $s$ and -any regular expression $r$ as argument and returns \emph{yes}, if $s \in L(r)$ and \emph{no}, -if $s \not\in L(r)$. We leave this for the next lecture. +\subsection*{Types} -\begin{figure}[p] -{\lstset{language=Scala}\texttt{\lstinputlisting{../progs/crawler1.scala}}} -\caption{Scala code for a web-crawler that can detect broken links in a web-page. It uses -the regular expression {\tt http\_pattern} in Line~15 for recognising URL-addresses. It finds -all links using the library function {\tt findAllIn} in Line~21.} -\end{figure} +\subsection*{Cool Stuff} -\begin{figure}[p] -{\lstset{language=Scala}\texttt{\lstinputlisting{../progs/crawler2.scala}}} -\caption{A version of the web-crawler which only follows links in ``my'' domain---since these are the -ones I am interested in to fix. It uses the regular expression {\tt my\_urls} in Line~16. -The main change is in Line~26 where there is a test whether URL is in ``my'' domain or not.} - -\end{figure} - -\begin{figure}[p] -{\lstset{language=Scala}\texttt{\lstinputlisting{../progs/crawler3.scala}}} -\caption{A small email harvester---whenever we download a web-page, we also check whether -it contains any email addresses. For this we use the regular expression {\tt email\_pattern} in -Line~17. The main change is in Lines 33 and 34 where all email addresses that can be found in a page are printed.} -\end{figure} \end{document}