From 8222cb50fb57c1d406fbf8f4a79d5c97796a908c Mon Sep 17 00:00:00 2001 From: Matthias Zenger Date: Mon, 18 Aug 2003 22:36:11 +0000 Subject: *** empty log message *** --- doc/reference/ScalaByExample.tex | 5510 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 5510 insertions(+) create mode 100644 doc/reference/ScalaByExample.tex (limited to 'doc') diff --git a/doc/reference/ScalaByExample.tex b/doc/reference/ScalaByExample.tex new file mode 100644 index 0000000000..fdc2c60598 --- /dev/null +++ b/doc/reference/ScalaByExample.tex @@ -0,0 +1,5510 @@ +\documentclass[a4paper,12pt,twoside,titlepage]{book} + +\usepackage{scaladoc} +\usepackage{fleqn} +\usepackage{modefs} +\usepackage{math} +\usepackage{scaladefs} + +\ifpdf + \pdfinfo { + /Author (Martin Odersky) + /Title (Scala by Example) + /Keywords (Scala) + /Subject () + /Creator (TeX) + /Producer (PDFLaTeX) + } +\fi + +\newcommand{\exercise}{\paragraph{Exercise:}} +\newcommand{\rewriteby}[1]{\mbox{\tab\tab\rm(#1)}} + +\renewcommand{\doctitle}{Scala By Example\\[33mm]\ } +\renewcommand{\docauthor}{Martin Odersky} + +\begin{document} + +\frontmatter +\makedoctitle +\clearemptydoublepage +\tableofcontents +\mainmatter +\sloppy + +\chapter{\label{chap:intro}Introduction} + +\input{rationale-chapter.tex} + +The rest of this document is structured as +follows. Chapters~\ref{chap:example-one} and +\ref{chap:example-auction} highlight some of the features that make +Scala interesting. The following chapters introduce the language +constructs of Scala in a more thorough +way. Chapter~\ref{chap:simple-funs} introduces basic expressions and +simple functions. Chapter~\ref{chap:first-class-funs} introduces +higher-order functions. (to be continued). + +This document ows a great dept to Sussman and Abelson's wonderful book +``Structure and Interpretation of Computer +Programs''\cite{abelson-sussman:structure}. Many of their examples and +exercises are also present here. Of course, the working language has +in each case been changed from Scheme to Scala. Furthermore, the +examples make use of Scala's object-oriented constructs where +appropriate. + + +\chapter{\label{chap:example-one}A First Example} + +As a first example, here is an implementation of Quicksort in Scala. + +\begin{lstlisting} +def sort(xs: Array[int]): unit = { + def swap(i: int, j: int): unit = { + val t = xs(i); xs(i) = xs(j); xs(j) = t; + } + def sort1(l: int, r: int): unit = { + val pivot = xs((l + r) / 2); + var i = l, j = r; + while (i <= j) { + while (xs(i) < pivot) { i = i + 1 } + while (xs(j) > pivot) { j = j - 1 } + if (i <= j) { + swap(i, j); + i = i + 1; + j = j - 1; + } + } + if (l < j) sort1(l, j); + if (j < r) sort1(i, r); + } + sort1(0, xs.length - 1); +} +\end{lstlisting} + +The implementation looks quite similar to what one would write in Java +or C. We use the same operators and similar control structures. +There are also some minor syntactical differences. In particular: +\begin{itemize} +\item +Definitions start with a reserved word. Function definitions start +with \code{def}, variable definitions start with \code{var} and +definitions of values (i.e. read only variables) start with \code{val}. +\item +The declared type of a symbol is given after the symbol and a colon. +The declared type can often be omitted, because the compiler can infer +it from the context. +\item +We use \code{unit} instead of \code{void} to define the result type of +a procedure. +\item +Array types are written \code{Array[T]} rather than \code{T[]}, +and array selections are written \code{a(i)} rather than \code{a[i]}. +\item +Functions can be nested inside other functions. Nested functions can +access parameters and local variables of enclosing functions. For +instance, the name of the array \code{a} is visible in functions +\code{swap} and \code{sort1}, and therefore need not be passed as a +parameter to them. +\end{itemize} +So far, Scala looks like a fairly conventional language with some +syntactic pecularities. In fact it is possible to write programs in a +conventional imperative or object-oriented style. This is important +because it is one of the things that makes it easy to combine Scala +components with components written in mainstream languages such as +Java, C\# or Visual Basic. + +However, it is also possible to write programs in a style which looks +completely different. Here is Quicksort again, this time written in +functional style. + +\begin{lstlisting} +def sort(xs: List[int]): List[int] = { + val pivot = a(a.length / 2); + sort(a.filter(x => x < pivot)) + ::: a.filter(x => x == pivot) + ::: sort(a.filter(x => x > pivot)) +} +\end{lstlisting} + +The functional program works with lists instead of arrays.\footnote{In +a future complete implemenetation of Scala, we could also have used arrays +instead of lists, but at the moment arrays do not yet support +\code{filter} and \code{:::}.} +It captures the essence of the quicksort algorithm in a concise way: +\begin{itemize} +\item Pick an element in the middle of the list as a pivot. +\item Partition the lists into two sub-lists containing elements that +are less than, respectively greater than the pivot element, and a +third list which contains elements equal to privot. +\item Sort the first two sub-lists by a recursive invocation of +the sort function.\footnote{This is not quite what the imperative algorithm does; +the latter partitions the array into two sub-arrays containing elements +less than or greater or equal to pivot.} +\item The result is obtained by appending the three sub-lists together. +\end{itemize} +Both the imperative and the functional implementation have the same +asymptotic complexity -- $O(N;log(N))$ in the average case and +$O(N^2)$ in the worst case. But where the imperative implementation +operates in place by modifying the argument array, the functional +implementation returns a new sorted list and leaves the argument +list unchanged. The functional implementation thus requires more +transient memory than the imperative one. + +The functional implementation makes it look like Scala is a language +that's specialized for functional operations on lists. In fact, it +is not; all of the operations used in the example are simple library +methods of a class \code{List[t]} which is part of the standard +Scala library, and which itself is implemented in Scala. + +In particular, there is the method \code{filter} which takes as +argument a {\em predicate function} that maps list elements to +boolean values. The result of \code{filter} is a list consisting of +all the elements of the original list for which the given predicate +function is true. The \code{filter} method of an object of type +\code{List[t]} thus has the signature + +\begin{lstlisting} +def filter(p: t => boolean): List[t] +\end{lstlisting} + +Here, \code{t => boolean} is the type of functions that take an element +of type \code{t} and return a \code{boolean}. Functions like +\code{filter} that take another function as argument or return one as +result are called {\em higher-order} functions. + +In the quicksort program, \code{filter} is applied three times to an +anonymous function argument. The first argument, +\code{x => x <= pivot} represents the function that maps its parameter +\code{x} to the boolean value \code{x <= pivot}. That is, it yields +true if \code{x} is smaller or equal than \code{pivot}, false +otherwise. The function is anonymous, i.e.\ it is not defined with a +name. The type of the \code{x} parameter is omitted because a Scala +compiler can infer it automatically from the context where the +function is used. To summarize, \code{xs.filter(x => x <= pivot)} +returns a list consisting of all elements of the list \code{xs} that are +smaller than \code{pivot}. + +\comment{ +It is also possible to apply higher-order functions such as +\code{filter} to named function arguments. Here is functional +quicksort again, where the two anonymous functions are replaced by +named auxiliary functions that compare the argument to the +\code{pivot} value. + +\begin{lstlisting} +def sort (xs: List[int]): List[int] = { + val pivot = xs(xs.length / 2); + def leqPivot(x: int) = x <= pivot; + def gtPivot(x: int) = x > pivot; + def eqPivot(x: int) = x == pivot; + sort(xs filter leqPivot) + ::: sort(xs filter eqPivot) + ::: sort(xs filter gtPivot) +} +\end{lstlisting} +} + +An object of type \code{List[t]} also has a method ``\code{:::}'' +which takes an another list and which returns the result of appending this +list to itself. This method has the signature + +\begin{lstlisting} +def :::(that: List[t]): List[t] +\end{lstlisting} + +Scala does not distinguish between identifiers and operator names. An +identifier can be either a sequence of letters and digits which begins +with a letter, or it can be a sequence of special characters, such as +``\code{+}'', ``\code{*}'', or ``\code{:}''. The last definition thus +introduced a new method identifier ``\code{:::}''. This identifier is +used in the Quicksort example as a binary infix operator that connects +the two sub-lists resulting from the partition. In fact, any method +can be used as an operator in Scala. The binary operation $E;op;E'$ +is always interpreted as the method call $E.op(E')$. This holds also +for binary infix operators which start with a letter. The recursive call +to \code{sort} in the last quicksort example is thus equivalent to +\begin{lstlisting} +sort(a.filter(x => x < pivot)) + .:::(sort(a.filter(x => x == pivot))) + .:::(sort(a.filter(x => x > pivot))) +\end{lstlisting} + +Looking again in detail at the first, imperative implementation of +Quicksort, we find that many of the language constructs used in the +second solution are also present, albeit in a disguised form. + +For instance, ``standard'' binary operators such as \code{+}, +\code{-}, or \code{<} are not treated in any special way. Like +\code{append}, they are methods of their left operand. Consequently, +the expression \code{i + 1} is regarded as the invocation +\code{i.+(1)} of the \code{+} method of the integer value \code{x}. +Of course, a compiler is free (if it is moderately smart, even expected) +to recognize the special case of calling the \code{+} method over +integer arguments and to generate efficient inline code for it. + +Control constructs such as \code{while} are also not primitive but are +predefined functions in the standard Scala library. Here is the +definition of \code{while} in Scala. +\begin{lstlisting} +def while (def p: boolean) (def s: unit): unit = + if (p) { s ; while(p)(s) } +\end{lstlisting} +The \code{while} function takes as first parameter a test function, +which takes no parameters and yields a boolean value. As second +parameter it takes a command function which also takes no parameters +and yields a trivial result. \code{while} invokes the command function +as long as the test function yields true. Again, compilers are free to +pick specialized implementations of \code{while} that have the same +behavior as the invocation of the function given above. + +\chapter{Programming with Actors and Messages} +\label{chap:example-auction} + +Here's an example that shows an application area for which Scala is +particularly well suited. Consider the task of implementing an +electronic auction service. We use an Erlang-style actor process +model to implement the participants of the auction. Actors are +objects to which messages are sent. Every process has a ``mailbox'' of +its incoming messages which is represented as a queue. It can work +sequentially through the messages in its mailbox, or search for +messages matching some pattern. + +For every traded item there is an auctioneer process that publishes +information about the traded item, that accepts offers from clients +and that communicates with the seller and winning bidder to close the +transaction. We present an overview of a simple implementation +here. + +As a first step, we define the messages that are exchanged during an +auction. There are two abstract base classes (called {\em traits}): +\code{AuctionMessage} for messages from clients to the auction +service, and \code{AuctionReply} for replies from the service to the +clients. These are defined as follows. +\begin{lstlisting} +trait AuctionMessage; +case class + Offer(bid: int, client: Actor), // make a bid + Inquire(client: Actor) extends AuctionMessage; // inquire status + +trait AuctionReply; +case class + Status(asked: int, expiration: Date), // asked sum, expiration date + BestOffer, // yours is the best offer + BeatenOffer(maxBid: int), // offer beaten by maxBid + AuctionConcluded(seller: Actor, client: Actor), // auction concluded + AuctionFailed, // failed with no bids + AuctionOver extends AuctionReply; // bidding is closed +\end{lstlisting} + +\begin{lstlisting}[style=floating,label=fig:simple-auction,caption=Implementation of an Auction Service] +class Auction(seller: Actor, minBid: int, closing: Date) extends Actor { + val timeToShutdown = 36000000; // msec + val bidIncrement = 10; + def execute { + var maxBid = minBid - bidIncrement; + var maxBidder: Actor = _; + var running = true; + while (running) { + receiveWithin ((closing.getTime() - new Date().getTime())) { + case Offer(bid, client) => + if (bid >= maxBid + bidIncrement) { + if (maxBid >= minBid) maxBidder send BeatenOffer(bid); + maxBid = bid; maxBidder = client; client send BestOffer; + } else { + client send BeatenOffer(maxBid); + } + case Inquire(client) => + client send Status(maxBid, closing); + case TIMEOUT => + if (maxBid >= minBid) { + val reply = AuctionConcluded(seller, maxBidder); + maxBidder send reply; seller send reply; + } else { + seller send AuctionFailed; + } + receiveWithin(timeToShutdown) { + case Offer(_, client) => client send AuctionOver + case TIMEOUT => running = false; + } + } + } + } +} +\end{lstlisting} + +For each base class, there are a number of {\em case classes} which +define the format of particular messages in the class. These messages +might well be ultimately mapped to small XML documents. We expect +automatic tools to exist that convert between XML documents and +internal data structures like the ones defined above. + +Figure~\ref{fig:simple-auction} presents a Scala implementation of a +class \code{Auction} for auction processes that coordinate the bidding +on one item. Objects of this class are created by indicating +\begin{itemize} +\item a seller process which needs to be notified when the auction is over, +\item a minimal bid, +\item the date when the auction is to be closed. +\end{itemize} +The process behavior is defined by its \code{run} method. That method +repeatedly selects (using \code{receiveWithin}) a message and reacts to it, +until the auction is closed, which is signalled by a \code{TIMEOUT} +message. Before finally stopping, it stays active for another period +determined by the \code{timeToShutdown} constant and replies to +further offers that the auction is closed. + +Here are some further explanations of the constructs used in this +program: +\begin{itemize} +\item +The \code{receiveWithin} method of class \code{Actor} takes as +parameters a time span given in milliseconds and a function that +processes messages in the mailbox. The function is given by a sequence +of cases that each specify a pattern and an action to perform for +messages matching the pattern. The \code{receiveWithin} method selects +the first message in the mailbox which matches one of these patterns +and applies the corresponding action to it. +\item +The last case of \code{receiveWithin} is guarded by a +\code{TIMEOUT} pattern. If no other messages are received in the meantime, this +pattern is triggered after the time span which is passed as argument +to the enclosing \code{receiveWithin} method. \code{TIMEOUT} is a +particular instance of class \code{Message}, which is triggered by the +\code{Actor} implementation itself. +\item +Reply messages are sent using syntax of the form +\code{destination send SomeMessage}. \code{send} is used here as a +binary operator with a process and a message as arguments. This is +equivalent in Scala to the method call +\code{destination.send(SomeMessage)}, i.e. the invocation of +the \code{send} of the destination process with the given message as +parameter. +\end{itemize} +The preceding discussion gave a flavor of distributed programming in +Scala. It might seem that Scala has a rich set of language constructs +that support actor processes, message sending and receiving, +programming with timeouts, etc. In fact, the opposite is true. All the +constructs discussed above are offered as methods in the library class +\code{Actor}. That class is itself implemented in Scala, based on the underlying +thread model of the host language (e.g. Java, or .NET). +The implementation of all features of class \code{Actor} used here is +given in Section~\ref{sec:actors}. + +The advantages of this approach are relative simplicity of the core +language and flexibility for library designers. Because the core +language need not specify details of high-level process communication, +it can be kept simpler and more general. Because the particular model +of messages in a mailbox is a library module, it can be freely +modified if a different model is needed in some applications. The +approach requires however that the core language is expressive enough +to provide the necessary language abstractions in a convenient +way. Scala has been designed with this in mind; one of its major +design goals was that it should be flexible enough to act as a +convenient host language for domain specific languages implemented by +library modules. For instance, the actor communication constructs +presented above can be regarded as one such domain specific language, +which conceptually extends the Scala core. + +\chapter{\label{chap:simple-funs}Expressions and Simple Functions} + +The previous examples gave an impression of what can be done with +Scala. We now introduce its constructs one by one in a more +systematic fashion. We start with the smallest level, expressions and +functions. + +\section{Expressions And Simple Functions} + +A Scala system comes with an interpreter which can be seen as a +fancy calculator. A user interacts with the calculator by typing in +expressions and obtaining the results of their evaluation. Example: + +\begin{lstlisting} +? 87 + 145 +232 + +? 1000 - 333 +667 + +? 5 + 2 * 3 +11 +\end{lstlisting} +It is also possible to name a sub-expression and use the name instead +of the expression afterwards: +\begin{lstlisting} +? def size = 2 +def size: int + +? 5 * size +10 +\end{lstlisting} +\begin{lstlisting} +? def pi = 3.14159 +def pi: double + +? def radius = 10 +def radius: int + +? 2 * pi * radius +62.8318 +\end{lstlisting} +Definitions start with the reserved word \code{def}; they introduce a +name which stands for the expression following the \code{=} sign. The +interpreter will answer with the introduced name and its type. + +Executing a definition such as \code{def x = e} will not evaluate the +expression \code{e}. Instead \code{e} is evaluated whenever \code{x} +is used. Alternatively, Scala offers a value definition +\code{val x = e}, which does evaluate the right-hand-side \code{e} as part of the +evaluation of the definition. If \code{x} is then used subsequently, +it is immediately replaced by the pre-computed value of +\code{e}, so that the expression need not be evaluated again. + +How are expressions evaluated? An expression consisting of operators +and operands is evaluated by repeatedly applying the following +simplification steps. +\begin{itemize} +\item pick the left-most operation +\item evaluate its operands +\item apply the operator to the operand values. +\end{itemize} +A name defined by \code{def}\ is evaluated by replacing the name by the +definition's right hand side. A name defined by \code{val} is +evaluated by replacing the name by the value of the definitions's +right-hand side. The evaluation process stops once we have reached a +value. A value is some data item such as a string, a number, an array, +or a list. + +\example +Here is an evaluation of an arithmetic expression. +\begin{lstlisting} +$\,\,\,$ (2 * pi) * radius +$\rightarrow$ (2 * 3.14159) * radius +$\rightarrow$ 6.28318 * radius +$\rightarrow$ 6.28318 * 10 +$\rightarrow$ 62.8318 +\end{lstlisting} +The process of stepwise simplification of expressions to values is +called {\em reduction}. + +\section{Parameters} + +Using \code{def}, one can also define functions with parameters. Example: +\begin{lstlisting} +? def square(x: double) = x * x +def square(x: double): double + +? square(2) +4.0 + +? square(5 + 4) +81.0 + +? square(square(4)) +256.0 + +? def sumOfSquares(x: double, y: double) = square(x) + square(y) +def sumOfSquares(x: double, y: double): double +\end{lstlisting} + +Function parameters follow the function name and are always enclosed +in parentheses. Every parameter comes with a type, which is indicated +following the parameter name and a colon. At the present time, we only +need basic numeric types such as the type \code{double} of double +precision numbers. These are written as in Java. + +Functions with parameters are evaluated analogously to operators in +expressions. First, the arguments of the function are evaluated (in +left-to-right order). Then, the function application is replaced by +the function's right hand side, and at the same time all formal +parameters of the function are replaced by their corresponding actual +arguments. + +\example\ + +\begin{lstlisting} +$\,\,\,$ sumOfSquares(3, 2+2) +$\rightarrow$ sumOfSquares(3, 4) +$\rightarrow$ square(3) + square(4) +$\rightarrow$ 3 * 3 + square(4) +$\rightarrow$ 9 + square(4) +$\rightarrow$ 9 + 4 * 4 +$\rightarrow$ 9 + 16 +$\rightarrow$ 25 +\end{lstlisting} + +The example shows that the interpreter reduces function arguments to +values before rewriting the function application. One could instead +have chosen to apply the function to unreduced arguments. This would +have yielded the following reduction sequence: +\begin{lstlisting} +$\,\,\,$ sumOfSquares(3, 2+2) +$\rightarrow$ square(3) + square(2+2) +$\rightarrow$ 3 * 3 + square(2+2) +$\rightarrow$ 9 + square(2+2) +$\rightarrow$ 9 + (2+2) * (2+2) +$\rightarrow$ 9 + 4 * (2+2) +$\rightarrow$ 9 + 4 * 4 +$\rightarrow$ 9 + 16 +$\rightarrow$ 25 +\end{lstlisting} + +The second evaluation order is known as \emph{call-by-name}, +whereas the first one is known as \emph{call-by-value}. For +expressions that use only pure functions and that therefore can be +reduced with the substitution model, both schemes yield the same final +values. + +Call-by-value has the advantage that it avoids repeated evaluation of +arguments. Call-by-name has the advantage that it avoids evaluation of +arguments when the parameter is not used at all by the function. +Call-by-value is usually more efficient than call-by-name, but a +call-by-value evaluation might loop where a call-by-name evaluation +would terminate. Consider: +\begin{lstlisting} +? def loop: int = loop +def loop: int + +? def first(x: int, y: int) = x +def first(x: int, y: int): int +\end{lstlisting} +Then \code{first(1, loop)} reduces with call-by-name to \code{1}, +whereas the same term reduces with call-by-value repeatedly to itself, +hence evaluation does not terminate. +\begin{lstlisting} +$\,\,\,$ first(1, loop) +$\rightarrow$ first(1, loop) +$\rightarrow$ first(1, loop) +$\rightarrow$ ... +\end{lstlisting} +Scala uses call-by-value by default, but it switches to call-by-name evaluation +if the parameter is preceded by \code{def}. + +\example\ + +\begin{lstlisting} +? def constOne(x: int, def y: int) = 1 +constOne(x: int, def y: int): int + +? constOne(1, loop) +1 + +? constOne(loop, 2) // gives an infinite loop. +^C +\end{lstlisting} + +\section{Conditional Expressions} + +Scala's \code{if-else} lets one choose between two alternatives. Its +syntax is like Java's \code{if-else}. But where Java's \code{if-else} +can be used only as an alternative of statements, Scala allows the +same syntax to choose between two expressions. Scala's \code{if-else} +hence also replaces Java's conditional expression \code{ ... ? ... : ...}. + +\example\ + +\begin{lstlisting} +? def abs(x: double) = if (x >= 0) x else -x +abs(x: double): double +\end{lstlisting} +Scala's boolean expressions are similar to Java's; they are formed +from the constants +\code{true} and +\code{false}, comparison operators, boolean negation \code{!} and the +boolean operators \code{&&} and \code{||}. + +\section{\label{sec:sqrt}Example: Square Roots by Newton's Method} + +We now illustrate the language elements introduced so far in the +construction of a more interesting program. The task is to write a +function +\begin{lstlisting} +def sqrt(x: double): double = ... +\end{lstlisting} +which computes the square root of \code{x}. + +A common way to compute square roots is by Newton's method of +successive approximations. One starts with an initial guess \code{y} +(say: \code{y = 1}). One then repeatedly improves the current guess +\code{y} by taking the average of \code{y} and \code{x/y}. +As an example, the next three columns indicate the guess \code{y}, the +quotient \code{x/y}, and their average for the first approximations of +$\sqrt 2$. +\begin{lstlisting} +1 2/1 = 2 1.5 +1.5 2/1.5 = 1.3333 1.4167 +1.4167 2/1.4167 = 1.4118 1.4142 +1.4142 ... ... + +$y$ $x/y$ $(y + x/y)/2$ +\end{lstlisting} +One can implement this algorithm in Scala by a set of small functions, +which each represent one of the elements of the algorithm. + +We first define a function for iterating from a guess to the result: +\begin{lstlisting} +def sqrtIter(guess: double, x: double): double = + if (isGoodEnough(guess, x)) guess + else sqrtIter(improve(guess, x), x); +\end{lstlisting} +Note that \code{sqrtIter} calls itself recursively. Loops in +imperative programs can always be modelled by recursion in functional +programs. + +Note also that the definition of \code{sqrtIter} contains a return +type, which follows the parameter section. Such return types are +mandatory for recursive functions. For a non-recursive function, the +return type is optional; if it is missing the type checker will +compute it from the type of the function's right-hand side. However, +even for non-recursive functions it is often a good idea to include a +return type for better documentation. + +As a second step, we define the two functions called by +\code{sqrtIter}: a function to \code{improve} the guess and a +termination test \code{isGoodEnough}. Here's their definition. +\begin{lstlisting} +def improve(guess: double, x: double) = + (guess + x / guess) / 2; + +def isGoodEnough(guess: double, x: double) = + abs(square(guess) - x) < 0.001; +\end{lstlisting} + +Finally, the \code{sqrt} function itself is defined by an aplication +of \code{sqrtIter}. +\begin{lstlisting} +def sqrt(x: double) = sqrtIter(1.0, x); +\end{lstlisting} + +\exercise The \code{isGoodEnough} test is not very precise for small numbers +and might lead to non-termination for very large ones (why?). +Design a different version \code{isGoodEnough} which does not have these problems. + +\exercise Trace the execution of the \code{sqrt(4)} expression. + +\section{Nested Functions} + +The functional programming style encourages the construction of many +small helper functions. In the last example, the implementation +of \code{sqrt} made use of the helper functions +\code{sqrtIter}, \code{improve} and +\code{isGoodEnough}. The names of these functions +are relevant only for the implementation of +\code{sqrt}. We normally do not want users of \code{sqrt} to acess these functions +directly. + +We can enforce this (and avoid name-space pollution) by including +the helper functions within the calling function itself: +\begin{lstlisting} +def sqrt(x: double) = { + def sqrtIter(guess: double, x: double): double = + if (isGoodEnough(guess, x)) guess + else sqrtIter(improve(guess, x), x); + def improve(guess: double, x: double) = + (guess + x / guess) / 2; + def isGoodEnough(guess: double, x: double) = + abs(square(guess) - x) < 0.001; + sqrtIter(1.0, x) +} +\end{lstlisting} +In this program, the braces \code{\{ ... \}} enclose a {\em block}. +Blocks in Scala are themselves expressions. Every block ends in a +result expression which defines its value. The result expression may +be preceded by auxiliary definitions, which are visible only in the +block itself. + +Every definition in a block must be followed by a semicolon, which +separates this definition from subsequent definitions or the result +expression. However, a semicolon is inserted implicitly if the +definition ends in a right brace and is followed by a new line. +Therefore, the following are all legal: +\begin{lstlisting} +def f(x) = x + 1; /* `;' mandatory */ +f(1) + f(2) + +def g(x) = {x + 1} +g(1) + g(2) + +def h(x) = {x + 1}; /* `;' mandatory */ h(1) + h(2) +\end{lstlisting} +Scala uses the usual block-structured scoping rules. A name defined in +some outer block is visible also in some inner block, provided it is +not redefined there. This rule permits us to simplify our +\code{sqrt} example. We need not pass \code{x} around as an additional parameter of +the nested functions, since it is always visible in them as a +parameter of the outer function \code{sqrt}. Here is the simplified code: +\begin{lstlisting} +def sqrt(x: double) = { + def sqrtIter(guess: double): double = + if (isGoodEnough(guess)) guess + else sqrtIter(improve(guess)); + def improve(guess: double) = + (guess + x / guess) / 2; + def isGoodEnough(guess: double) = + abs(square(guess) - x) < 0.001; + sqrtIter(1.0) +} +\end{lstlisting} + +\section{Tail Recursion} + +Consider the following function to compute the greatest common divisor +of two given numbers. + +\begin{lstlisting} +def gcd(a: int, b: int): int = if (b == 0) a else gcd(b, a % b) +\end{lstlisting} + +Using our substitution model of function evaluation, +\code{gcd(14, 21)} evaluates as follows: + +$\,\,\,$ sumOfSquares(3, 2+2) +$\rightarrow$ square(3) + square(2+2) + +\begin{lstlisting} +$\,\,$ gcd(14, 21) +$\rightarrow\!$ if (21 == 0) 14 else gcd(21, 14 % 21) +$\rightarrow\!$ if (false) 14 else gcd(21, 14 % 21) +$\rightarrow\!$ gcd(21, 14 % 21) +$\rightarrow\!$ gcd(21, 14) +$\rightarrow\!$ if (14 == 0) 21 else gcd(14, 21 % 14) +$\rightarrow$ $\rightarrow$ gcd(14, 21 % 14) +$\rightarrow\!$ gcd(14, 7) +$\rightarrow\!$ if (7 == 0) 14 else gcd(7, 14 % 7) +$\rightarrow$ $\rightarrow$ gcd(7, 14 % 7) +$\rightarrow\!$ gcd(7, 0) +$\rightarrow\!$ if (0 == 0) 7 else gcd(0, 7 % 0) +$\rightarrow$ $\rightarrow$ 7 +\end{lstlisting} + +Contrast this with the evaluation of another recursive function, +\code{factorial}: + +\begin{lstlisting} +def factorial(n: int): int = if (n == 0) 1 else n * factorial(n - 1) +\end{lstlisting} + +The application \code{factorial(5)} rewrites as follows: +\begin{lstlisting} +$\,\,\,$ factorial(5) +$\rightarrow$ if (5 == 0) 1 else 5 * factorial(5 - 1) +$\rightarrow$ 5 * factorial(5 - 1) +$\rightarrow$ 5 * factorial(4) +$\rightarrow\ldots\rightarrow$ 5 * (4 * factorial(3)) +$\rightarrow\ldots\rightarrow$ 5 * (4 * (3 * factorial(2))) +$\rightarrow\ldots\rightarrow$ 5 * (4 * (3 * (2 * factorial(1)))) +$\rightarrow\ldots\rightarrow$ 5 * (4 * (3 * (2 * (1 * factorial(0)))) +$\rightarrow\ldots\rightarrow$ 5 * (4 * (3 * (2 * (1 * 1)))) +$\rightarrow\ldots\rightarrow$ 120 +\end{lstlisting} +There is an important difference between the two rewrite sequences: +The terms in the rewrite sequence of \code{gcd} have again and again +the same form. As evaluation proceeds, their size is bounded by a +constant. By contrast, in the evaluation of factorial we get longer +and longer chains of operands which are then multiplied in the last +part of the evaluation sequence. + +Even though actual implementations of Scala do not work by rewriting +terms, they nevertheless should have the same space behavior as in the +rewrite sequences. In the implementation of \code{gcd}, one notes that +the recursive call to \code{gcd} is the last action performed in the +evaluation of its body. One also says that \code{gcd} is +``tail-recursive''. The final call in a tail-recursive function can be +implemented by a jump back to the beginning of that function. The +arguments of that call can overwrite the parameters of the current +instantiation of \code{gcd}, so that no new stack space is needed. +Hence, tail recursive functions are iterative processes, which can be +executed in constant space. + +By contrast, the recursive call in \code{factorial} is followed by a +multiplication. Hence, a new stack frame is allocated for the +recursive instance of factorial, and is decallocated after that +instance has finished. The given formulation of the factorial function +is not tail-recursive; it needs space proportional to its input +parameter for its execution. + +More generally, if the last action of a function is a call to another +(possibly the same) function, only a single stack frame is needed for +both functions. Such calls are called ``tail calls''. In principle, +tail calls can always re-use the stack frame of the calling function. +However, some run-time environments (such as the Java VM) lack the +primititives to make stack frame re-use for tail calls efficient. A +production quality Scala implementation is therefore only required to re-use +the stack frame of a directly tail-recursive function whose last +action is a call to itself. Other tail calls might be optimized also, +but one should not rely on this across +implementations\footnote{The current Scala implementation is not yet +production quality; it never optimizes tail calls, not even directly +recursive ones}. + +\exercise Design a tail-recursive version of +\code{factorial}. + +\chapter{\label{chap:first-class-funs}First-Class Functions} + +A function in Scala is a ``first-class value''. Like any other value, +it may be passed as a parameter or returned as a result. Functions +which take other functions as parameters or return them as results are +called {\em higher-order} functions. This chapter introduces +higher-order functions and shows how they provide a flexible mechanism +for program composition. + +As a motivating example, consider the following three related tasks: +\begin{enumerate} +\item +Write a function to sum all integers between two given numbers \code{a} and \code{b}: +\begin{lstlisting} +def sumInts(a: int, b: int): double = + if (a > b) 0 else a + sumInts(a + 1, b) +\end{lstlisting} +\item +Write a function to sum the cubes of all integers between two given numbers +\code{a} and \code{b}: +\begin{lstlisting} +def cube(x: int): double = x * x * x +def sumCubes(a: int, b: int): double = + if (a > b) 0 else cube(a) + sumSqrts(a + 1, b) +\end{lstlisting} +\item +Write a function to sum the reciprocals of all integers between two given numbers +\code{a} and \code{b}: +\begin{lstlisting} +def sumReciprocals(a: int, b: int): double = + if (a > b) 0 else 1.0 / a + sumReciprocals(a + 1, b) +\end{lstlisting} +\end{enumerate} +These functions are all instances of +\(\sum^b_a f(n)\) for different values of $f$. +We can factor out the common pattern by defining a function \code{sum}: +\begin{lstlisting} +def sum(f: int => double, a: int, b: int): double = + if (a > b) 0 else f(a) + sum(f, a + 1, b) +\end{lstlisting} +The type \code{int => double} is the type of functions that +take arguments of type \code{int} and return results of type +\code{double}. So \code{sum} is a function which takes another function as +a parameter. In other words, \code{sum} is a {\em higher-order} +function. + +Using \code{sum}, we can formulate the three summing functions as +follows. +\begin{lstlisting} +def sumInts(a: int, b: int): double = sum(id, a, b); +def sumCubes(a: int, b: int): double = sum(cube, a, b); +def sumReciprocals(a: int, b: int): double = sum(reciprocal, a, b); +\end{lstlisting} +where +\begin{lstlisting} +def id(x: int): double = x; +def cube(x: int): double = x * x * x; +def reciprocal(x: int): double = 1.0/x; +\end{lstlisting} + +\section{Anonymous Functions} + +Parameterization by functions tends to create many small functions. In +the previous example, we defined \code{id}, \code{cube} and +\code{reciprocal} as separate functions, so that they could be +passed as arguments to \code{sum}. + +Instead of using named function definitions for these small argument +functions, we can formulate them in a shorter way as {\em anonymous +functions}. An anonymous function is an expression that evaluates to a +function; the function is defined without giving it a name. As an +example consider the anonymous reciprocal function: +\begin{lstlisting} + x: int => 1.0/x +\end{lstlisting} +The part before the arrow `\code{=>}' is the parameter of the function, +whereas the part following the `\code{=>}' is its body. If there are +several parameters, we need to enclose them in parentheses. For +instance, here is an anonymous function which multiples its two arguments. +\begin{lstlisting} + (x: double, y: double) => x * y +\end{lstlisting} +Using anonymous functions, we can reformulate the three summation +functions without named auxiliary functions: +\begin{lstlisting} +def sumInts(a: int, b: int): double = sum(x: int => x, a, b); +def sumCubes(a: int, b: int): double = sum(x: int => x * x * x, a, b); +def sumReciprocals(a: int, b: int): double = sum(x: int => 1.0/x, a, b); +\end{lstlisting} +Often, the Scala compiler can deduce the parameter type(s) from the +context of the anonymous function. In this case, they can be omitted. +For instance, in the case of \code{sumInts}, \code{sumCubes} and +\code{sumReciprocals}, one knows from the type of +\code{sum} that the first parameter must be a function of type +\code{int => double}. Hence, the parameter type \code{int} is +redundant and may be omitted: +\begin{lstlisting} +def sumInts(a: int, b: int): double = sum(x => x, a, b); +def sumCubes(a: int, b: int): double = sum(x => x * x * x, a, b); +def sumReciprocals(a: int, b: int): double = sum(x => 1.0/x, a, b); +\end{lstlisting} + +Generally, the Scala term +\code{(x}$_1$\code{: T}$_1$\code{, ..., x}$_n$\code{: T}$_n$\code{) => E} +defines a function which maps its parameters +\code{x}$_1$\code{, ..., x}$_n$ to the result of the expression \code{E} +(where \code{E} may refer to \code{x}$_1$\code{, ..., x}$_n$). Anonymous +functions are not essential language elements of Scala, as they can +always be expressed in terms of named functions. Indeed, the +anonymous function +\begin{lstlisting} +(x$_1$: T$_1$, ..., x$_n$: T$_n$) => E +\end{lstlisting} +is equivalent to the block +\begin{lstlisting} +{ def f (x$_1$: T$_1$, ..., x$_n$: T$_n$) = E ; f } +\end{lstlisting} +where \code{f} is fresh name which is used nowhere else in the program. +We also say, anonymous functions are ``syntactic sugar''. + +\section{Currying} + +The latest formulation of the three summing function is already quite +compact. But we can do even better. Note that +\code{a} and \code{b} appear as parameters and arguments of every function +but they do not seem to take part in interesting combinations. Is +there a way to get rid of them? + +Let's try to rewrite \code{sum} so that it does not take the bounds +\code{a} and \code{b} as parameters: +\begin{lstlisting} +def sum(f: int => double) = { + def sumF(a: int, b: int): double = + if (a > b) 0 else f(a) + sumF(a + 1, b); + sumF +} +\end{lstlisting} +In this formulation, \code{sum} is a function which returns another +function, namely the specialized summing function \code{sumF}. This +latter function does all the work; it takes the bounds \code{a} and +\code{b} as parameters, applies \code{sum}'s function parameter \code{f} to all +integers between them, and sums up the results. + +Using this new formulation of \code{sum}, we can now define: +\begin{lstlisting} +def sumInts = sum(x => x); +def sumCubes = sum(x => x * x * x); +def sumReciprocals = sum(x => 1.0/x); +\end{lstlisting} +Or, equivalently, with value definitions: +\begin{lstlisting} +val sumInts = sum(x => x); +val sumCubes = sum(x => x * x * x); +val sumReciprocals = sum(x => 1.0/x); +\end{lstlisting} +These functions can be applied like other functions. For instance, +\begin{lstlisting} +? sumCubes(1, 10) + sumReciprocals (10, 20) +3025.7687714031754 +\end{lstlisting} +How are function-returning functions applied? As an example, in the expression +\begin{lstlisting} +sum (x => x * x * x) (1, 10) , +\end{lstlisting} +the function \code{sum} is applied to the cubing function +\code{(x => x * x * x)}. The resulting function is then +applied to the second argument list, \code{(1, 10)}. + +This notation is possible because function application associates to the left. +That is, if $\mbox{args}_1$ and $\mbox{args}_2$ are argument lists, then +\bda{lcl} +f(\mbox{args}_1)(\mbox{args}_2) & \ \ \mbox{is equivalent to}\ \ & (f(\mbox{args}_1))(\mbox{args}_2) +\eda +In our example, \code{sum(x => x * x * x)(1, 10)} is equivalent to the +following expression: +\code{(sum(x => x * x * x))(1, 10)}. + +The style of function-returning functions is so useful that Scala has +special syntax for it. For instance, the next definition of \code{sum} +is equivalent to the previous one, but is shorter: +\begin{lstlisting} +def sum(f: int => double)(a: int, b: int): double = + if (a > b) 0 else f(a) + sum(f)(a + 1, b) +\end{lstlisting} +Generally, a curried function definition +\begin{lstlisting} +def f (args$_1$) ... (args$_n$) = E +\end{lstlisting} +where $n > 1$ expands to +\begin{lstlisting} +def f (args$_1$) ... (args$_{n-1}$) = { def g (args$_n$) = E ; g } +\end{lstlisting} +where \code{g} is a fresh identifier. Or, shorter, using an anonymous function: +\begin{lstlisting} +def f (args$_1$) ... (args$_{n-1}$) = ( args$_n$ ) => E . +\end{lstlisting} +Performing this step $n$ times yields that +\begin{lstlisting} +def f (args$_1$) ... (args$_n$) = E +\end{lstlisting} +is equivalent to +\begin{lstlisting} +def f = (args$_1$) => ... => (args$_n$) => E . +\end{lstlisting} +Or, equivalently, using a value definition: +\begin{lstlisting} +val f = (args$_1$) => ... => (args$_n$) => E . +\end{lstlisting} +This style of function definition and application is called {\em +currying} after its promoter, Haskell B.\ Curry, a logician of the +20th century, even though the idea goes back further to Moses +Sch\"onfinkel and Gottlob Frege. + +The type of a function-returning function is expressed analogously to +its parameter list. Taking the last formulation of \code{sum} as an example, +the type of \code{sum} is \code{(int => double) => (int, int) => double}. +This is possible because function types associate to the right. I.e. +\begin{lstlisting} +T$_1$ => T$_2$ => T$_3$ $\mbox{is equivalent to}$ T$_1$ => (T$_2$ => T$_3$) +\end{lstlisting} + +\subsection*{Exercises:} + +1. The \code{sum} function uses a linear recursion. Can you write a +tail-recursive one by filling in the ??'s? + +\begin{lstlisting} +def sum(f: int => double)(a: int, b: int): double = { + def iter (a, result) = { + if (??) ?? + else iter (??, ??) + } + iter (??, ??) +} +\end{lstlisting} + +2. Write a function \code{product} that computes the product of the +values of functions at points over a given range. + +3. Write \code{factorial} in terms of \code{product}. + +4. Can you write an even more general function which generalizes both +\code{sum} and \code{product}? + +\section{Example: Finding Fixed Points of Functions} + +A number \code{x} is called a {\em fixed point} of a function \code{f} if +\begin{lstlisting} +f(x) = x . +\end{lstlisting} +For some functions \code{f} we can locate the fixed point by beginning +with an initial guess and then applying \code{f} repeatedly, until the +value does not change anymore (or the change is within a small +tolerance). This is possible if the sequence +\begin{lstlisting} +x, f(x), f(f(x)), f(f(f(x))), ... +\end{lstlisting} +converges to fixed point of $f$. This idea is captured in +the following ``fixed-point finding function'': +\begin{lstlisting} +val tolerance = 0.0001; +def isCloseEnough(x: double, y: double) = abs((x - y) / x) < tolerance; +def fixedPoint(f: double => double)(firstGuess: double) = { + def iterate(guess: double): double = { + val next = f(guess); + if (isCloseEnough(guess, next)) next + else iterate(next) + } + iterate(firstGuess) +} +\end{lstlisting} +We now apply this idea in a reformulation of the square root function. +Let's start with a specification of \code{sqrt}: +\begin{lstlisting} +sqrt(x) = $\mbox{the {\sl y} such that}$ y * y = x + = $\mbox{the {\sl y} such that}$ y = x / y +\end{lstlisting} +Hence, \code{sqrt(x)} is a fixed point of the function \code{y => x / y}. +This suggests that \code{sqrt(x)} can be computed by fixed point iteration: +\begin{lstlisting} +def sqrt(x: double) = fixedPoint(y => x / y)(1.0) +\end{lstlisting} +Unfortunately, this does not converge. Let's instrument the fixed point +function with a print statement which keeps track of the current +\code{guess} value: +\begin{lstlisting} +def fixedPoint(f: double => double)(firstGuess: double) = { + def iterate(guess: double): double = { + val next = f(guess); + System.out.println(next); + if (isCloseEnough(guess, next)) next + else iterate(next) + } + iterate(firstGuess) +} +\end{lstlisting} +Then, \code{sqrt(2)} yields: +\begin{lstlisting} + 2.0 + 1.0 + 2.0 + 1.0 + 2.0 + ... +\end{lstlisting} +One way to control such oscillations is to prevent the guess from changing too much. +This can be achieved by {\em averaging} successive values of the original sequence: +\begin{lstlisting} +> def sqrt(x: double) = fixedPoint(y => (y + x/y) / 2)(1.0) +> sqrt(2.0) + 1.5 + 1.4166666666666665 + 1.4142156862745097 + 1.4142135623746899 + 1.4142135623746899 +\end{lstlisting} +In fact, expanding the \code{fixedPoint} function yields exactly our +previous definition of fixed point from Section~\ref{sec:sqrt}. + +The previous examples showed that the expressive power of a language +is considerably enhanced if functions can be passed as arguments. The +next example shows that functions which return functions can also be +very useful. + +Consider again fixed point iterations. We started with the observation +that $\sqrt(x)$ is a fixed point of the function \code{y => x / y}. +Then we made the iteration converge by averaging successive values. +This technique of {\em average dampening} is so general that it +can be wrapped in another function. +\begin{lstlisting} +def averageDamp(f: double => double)(x: double) = (x + f(x)) / 2 +\end{lstlisting} +Using \code{averageDamp}, we can reformulate the square root function +as follows. +\begin{lstlisting} +def sqrt(x: double) = fixedPoint(averageDamp(y => x/y))(1.0) +\end{lstlisting} +This expresses the elements of the algorithm as clearly as possible. + +\exercise Write a function for cube roots using \code{fixedPoint} and +\code{averageDamp}. + +\section{Summary} + +We have seen in the previous chapter that functions are essential +abstractions, because they permit us to introduce general methods of +computing as explicit, named elements in our programming language. +The current chapter has shown that these abstractions can be combined by +higher-order functions to create further abstractions. As +programmers, we should look out for opportunities to abstract and to +reuse. The highest possible level of abstraction is not always the +best, but it is important to know abstraction techniques, so that one +can use abstractions where appropriate. + +\section{Language Elements Seen So Far} + +Chapters~\ref{chap:simple-funs} and \ref{chap:first-class-funs} have +covered Scala's language elements to express expressions and types +comprising of primitive data and functions. The context-free syntax +of these language elements is given below in extended Backus-Naur +form, where `\code{|}' denotes alternatives, \code{[...]} denotes +option (0 or 1 occurrences), and \code{{...}} denotes repetition (0 or +more occurrences). + +\subsection*{Characters} + +Scala programs are sequences of (Unicode) characters. We distinguish the +following character sets: +\begin{itemize} +\item +whitespace, such as `\code{ }', tabulator, or newline characters, +\item +letters `\code{a}' to `\code{z}', `\code{A}' to `\code{Z}', +\item +digits \code{`0'} to `\code{9}', +\item +the delimiter characters + +\begin{lstlisting} +. , ; ( ) { } [ ] \ $\mbox{\tt "}$ ' +\end{lstlisting} + +\item +operator characters, such as `\code{#}' `\code{+}', +`\code{:}'. Essentially, these are printable characters which are +in none of the character sets above. +\end{itemize} + +\subsection*{Lexemes:} + +\begin{lstlisting} +ident = letter {letter | digit} + | operator { operator } + | ident '_' ident +literal = $\mbox{``as in Java''}$ +\end{lstlisting} + +Literals are as in Java. They define numbers, characters, strings, or +boolean values. Examples of literals as \code{0}, \code{1.0d10}, \code{'x'}, +\code{"he said \"hi!\""}, or \code{true}. + +Identifiers can be of two forms. They either start with a letter, +which is followed by a (possibly empty) sequence of letters or +symbols, or they start with an operator character, which is followed +by a (possibly empty) sequence of operator characters. Both forms of +identifiers may contain underscore characters `\code{_}'. Furthermore, +an underscore character may be followed by either sort of +identifier. Hence, the following are all legal identifiers: +\begin{lstlisting} +x Room10a + -- foldl_: +_vector +\end{lstlisting} +It follows from this rule that subsequent operator-identifiers need to +be separated by whitespace. For instance, the input +\code{x+-y} is parsed as the three token sequence \code{x}, \code{+-}, +\code{y}. If we want to express the sum of \code{x} with the +negated value of \code{y}, we need to add at least one space, +e.g. \code{x+ -y}. + +The \verb@$@ character is reserved for compiler-generated +identifiers; it should not be used in source programs. %$ + +The following are reserved words, they may not be used as identifiers: +\begin{lstlisting}[keywordstyle=] +abstract case catch class def +do else extends false final +finally for if import new +null object override package private +protected return sealed super this +trait try true type val +var while with yield +_ : = => <- <: >: # @ +\end{lstlisting} + +\subsection*{Types:} + +\begin{lstlisting} +Type = SimpleType | FunctionType +FunctionType = SimpleType '=>' Type | '(' [Types] ')' '=>' Type +SimpleType = byte | short | char | int | long | double | float | + boolean | unit | String +Types = Type {`,' Type} +\end{lstlisting} + +Types can be: +\begin{itemize} +\item number types \code{byte}, \code{short}, \code{char}, \code{int}, \code{long}, \code{float} and \code{double} (these are as in Java), +\item the type \code{boolean} with values \code{true} and \code{false}, +\item the type \code{unit} with the only value \code{()}, +\item the type \code{String}, +\item function types such as \code{(int, int) => int} or \code{String => Int => String}. +\end{itemize} + +\subsection*{Expressions:} + +\begin{lstlisting} +Expr = InfixExpr | FunctionExpr | if '(' Expr ')' Expr else Expr +InfixExpr = PrefixExpr | InfixExpr Operator InfixExpr +Operator = ident +PrefixExpr = ['+' | '-' | '!' | '~' ] SimpleExpr +SimpleExpr = ident | literal | SimpleExpr '.' ident | Block +FunctionExpr = Bindings '=>' Expr +Bindings = ident [':' SimpleType] | '(' [Binding {',' Binding}] ')' +Binding = ident [':' Type] +Block = '{' {Def ';'} Expr '}' +\end{lstlisting} + +Expressions can be: +\begin{itemize} +\item +identifiers such as \code{x}, \code{isGoodEnough}, \code{*}, or \code{+-}, +\item +literals, such as \code{0}, \code{1.0}, or \code{"abc"}, +\item +field and method selections, such as \code{System.out.println}, +\item +function applications, such as \code{sqrt(x)}, +\item +operator applications, such as \code{-x} or \code{y + x}, +\item +conditionals, such as \code{if (x < 0) -x else x}, +\item +blocks, such as \code{{ val x = abs(y) ; x * 2 }}, +\item +anonymous functions, such as \code{x => x + 1} or \code{(x: int, y: int) => x + y}. +\end{itemize} + +\subsection*{Definitions:} + +\begin{lstlisting} +Def = FunDef | ValDef +FunDef = 'def' ident {'(' [Parameters] ')'} [':' Type] '=' Expr +ValDef = 'val' ident [':' Type] '=' Expr +Parameters = Parameter {',' Parameter} +Parameter = ['def'] ident ':' Type +\end{lstlisting} +Definitions can be: +\begin{itemize} +\item +function definitions such as \code{def square(x: int) = x * x}, +\item +value definitions such as \code{val y = square(2)}. +\end{itemize} + +\chapter{Classes and Objects} +\label{chap:classes} + +Scala does not have a built-in type of rational numbers, but it is +easy to define one, using a class. Here's a possible implementation. + +\begin{lstlisting} +class Rational(n: int, d: int) { + private def gcd(x: int, y: int): int = { + if (x == 0) y + else if (x < 0) gcd(-x, y) + else if (y < 0) -gcd(x, -y) + else gcd(y % x, x); + } + private val g = gcd(n, d); + + val numer: int = n/g; + val denom: int = d/g; + def +(that: Rational) = + new Rational(numer * that.denom + that.numer * denom, + denom * that.denom); + def -(that: Rational) = + new Rational(numer * that.denom - that.numer * denom, + denom * that.denom); + def *(that: Rational) = + new Rational(numer * that.numer, denom * that.denom); + def /(that: Rational) = + new Rational(numer * that.denom, denom * that.numer); +} +\end{lstlisting} +This defines \code{Rational} as a class which takes two constructor +arguments \code{n} and \code{d}, containing the number's numerator and +denominator parts. The class provides fields which return these parts +as well as methods for arithmetic over rational numbers. Each +arithmetic method takes as parameter the right operand of the +operation. The left operand of the operation is always the rational +number of which the method is a member. + +\paragraph{Private members} +The implementation of rational numbers defines a private method +\code{gcd} which computes the greatest common denominator of two +integers, as well as a private field \code{g} which contains the +\code{gcd} of the constructor arguments. These members are inaccessible +outside class \code{Rational}. They are used in the implementation of +the class to eliminate common factors in the constructor arguments in +order to ensure that nominator and denominator are always in +normalized form. + +\paragraph{Creating and Accessing Objects} +As an example of how rational numbers can be used, here's a program +that prints the sum of all numbers $1/i$ where $i$ ranges from 1 to 10. +\begin{lstlisting} +var i = 1; +var x = Rational(0, 1); +while (i <= 10) { + x = x + Rational(1,i); + i = i + 1; +} +System.out.println(x.numer + "/" + x.denom); +\end{lstlisting} +The \code{+} operation converts both its operands to strings and returns the +concatenation of the result strings. It thus corresponds to \code{+} in Java. + +\paragraph{Inheritance and Overriding} +Every class in Scala has a superclass which it extends. +Excepted is only the root class \code{Object}, which does not have a +superclass, and which is indirectly extended by every other class. +If a class does not mention a superclass in its definition, the root +class \code{Object} is implicitly assumed. For instance, class +\code{Rational} could equivalently be defined as +\begin{lstlisting} +class Rational(n: int, d: int) extends Object { + ... // as before +} +\end{lstlisting} +A class inherits all members from its superclass. It may also redefine +(or: {\em override}) some inherited members. For instance, class +\code{Object} defines +a method +\code{toString} which returns a representation of the object as a string: +\begin{lstlisting} +class Object { + ... + def toString(): String = ... +} +\end{lstlisting} +The implementation of \code{toString} in \code{Object} +forms a string consisting of the object's class name and a number. It +makes sense to redefine this method for objects that are rational +numbers: +\begin{lstlisting} +class Rational(n: int, d: int) extends Object { + ... // as before + override def toString() = numer + "/" + denom; +} +\end{lstlisting} +Note that, unlike in Java, redefining definitions need to be preceded +by an \code{override} modifier. + +If class $A$ extends class $B$, then objects of type $A$ may be used +wherever objects of type $B$ are expected. We say in this case that +type $A$ {\em conforms} to type $B$. For instance, \code{Rational} +conforms to \code{Object}, so it is legal to assign a \code{Rational} +value to a variable of type \code{Object}: +\begin{lstlisting} +var x: Object = new Rational(1,2); +\end{lstlisting} + +\paragraph{Parameterless Methods} +%Also unlike in Java, methods in Scala do not necessarily take a +%parameter list. An example is \code{toString}; the method is invoked +%by simply mentioning its name. For instance: +%\begin{lstlisting} +%val r = new Rational(1,2); +%System.out.println(r.toString()); // prints``1/2'' +%\end{lstlisting} +Also unlike in Java, methods in Scala do not necessarily take a +parameter list. An example is the \code{square} method below. This +method is invoked by simply mentioning its name. +\begin{lstlisting} +class Rational(n: int, d: int) extends Object { + ... // as before + def square = Rational(numer*numer, denom*denom); +} +val r = new Rational(3,4); +System.out.println(r.square); // prints``9/16'' +\end{lstlisting} +That is, parameterless methods are accessed just as value fields such +as \code{numer} are. The difference between values and parameterless +methods lies in their definition. The right-hand side of a value is +evaluated when the object is created, and the value does not change +afterwards. A right-hand side of a parameterless method, on the other +hand, is evaluated each time the method is called. The uniform access +of fields and parameterless methods gives increased flexibility for +the implementer of a class. Often, a field in one version of a class +becomes a computed value in the next version. Uniform access ensures +that clients do not have to be rewritten because of that change. + +\paragraph{Abstract Classes} + +Consider the task of writing a class for sets of integer numbers with +two operations, \code{incl} and \code{contains}. \code{(s incl x)} +should return a new set which contains the element \code{x} togther +with all the elements of set \code{s}. \code{(s contains x)} should +return true if the set \code{s} contains the element \code{x}, and +should return \code{false} otherwise. The interface of such sets is +given by: +\begin{lstlisting} +abstract class IntSet { + def incl(x: int): IntSet; + def contains(x: int): boolean; +} +\end{lstlisting} +\code{IntSet} is labeled as an \emph{abstract class}. This has two +consequences. First, abstract classes may have {\em deferred} members +which are declared but which do not have an implementation. In our +case, both \code{incl} and \code{contains} are such members. Second, +because an abstract class might have unimplemented members, no objects +of that class may be created using \code{new}. By contrast, an +abstract class may be used as a base class of some other class, which +implements the deferred members. + +\paragraph{Traits} + +Instead of ``\code{abstract class} one also often uses the keyword +\code{trait} in Scala. A trait is an abstract class with no state, no +constructor arguments, and no side effects during object +initialization. Since \code{IntSet}'s fall in this category, one can +alternatively define them as traits: +\begin{lstlisting} +trait IntSet { + def incl(x: int): IntSet; + def contains(x: int): boolean; +} +\end{lstlisting} +A trait corresponds to an interface in Java, except +that a trait can also define implemented methods. + +\paragraph{Implementing Abstract Classes} + +Let's say, we plan to implement sets as binary trees. There are two +possible forms of trees. A tree for the empty set, and a tree +consisting of an integer and two subtrees. Here are their +implementations. + +\begin{lstlisting} +class Empty extends IntSet { + def contains(x: int): boolean = false; + def incl(x: int): IntSet = new NonEmpty(x, new Empty, new Empty); +} +\end{lstlisting} + +\begin{lstlisting} +class NonEmpty(elem:int, left:IntSet, right:IntSet) extends IntSet { + def contains(x: int): boolean = + if (x < elem) left contains x + else if (x > elem) right contains x + else true; + def incl(x: int): IntSet = + if (x < elem) new NonEmpty(elem, left incl x, right) + else if (x > elem) new NonEmpty(elem, left, right incl x) + else this; +} +\end{lstlisting} +Both \code{Empty} and \code{NonEmpty} extend class +\code{IntSet}. This implies that types \code{Empty} and +\code{NonEmpty} conform to type \code{IntSet} -- a value of type \code{Empty} or \code{NonEmpty} may be used wherever a value of type \code{IntSet} is required. + +\exercise Write methods \code{union} and \code{intersection} to form +the union and intersection between two sets. + +\exercise Add a method +\begin{lstlisting} +def excl(x: int) +\end{lstlisting} +to return the given set without the element \code{x}. To accomplish this, +it is useful to also implement a test method +\begin{lstlisting} +def isEmpty: boolean +\end{lstlisting} +for sets. + +\paragraph{Dynamic Binding} + +Object-oriented languages (Scala included) use \emph{dynamic dispatch} +for method invocations. That is, the code invoked for a method call +depends on the run-time type of the object which contains the method. +For example, consider the expression \code{s contains 7} where +\code{s} is a value of declared type \code{s: IntSet}. Which code for +\code{contains} is executed depends on the type of value of \code{s} at run-time. +If it is an \code{Empty} value, it is the implementation of \code{contains} in class \code{Empty} that is executed, and analogously for \code{NonEmpty} values. +This behavior is a direct consequence of our substitution model of evaluation. +For instance, +\begin{lstlisting} + (new Empty).contains(7) + +-> $\rewriteby{by replacing {\sl contains} by its body in class {\sl Empty}}$ + + false +\end{lstlisting} +Or, +\begin{lstlisting} + new NonEmpty(7, new Empty, new Empty).contains(1) + +-> $\rewriteby{by replacing {\sl contains} by its body in class {\sl NonEmpty}}$ + + if (1 < 7) new Empty contains 1 + else if (1 > 7) new Empty contains 1 + else true + +-> $\rewriteby{by rewriting the conditional}$ + + new Empty contains 1 + +-> $\rewriteby{by replacing {\sl contains} by its body in class {\sl Empty}}$ + + false . +\end{lstlisting} + +Dynamic method dispatch is analogous to higher-order function +calls. In both cases, the identity of code to be executed is known +only at run-time. This similarity is not just superficial. Indeed, +Scala represents every function value as an object (see +Section~\ref{sec:funs-are-objects}). + + +\paragraph{Objects} + +In the previous implementation of integer sets, empty sets were +expressed with \code{new Empty}; so a new object was created every time +an empty set value was required. We could have avoided unnecessary +object creations by defining a value \code{empty} once and then using +this value instead of every occurrence of \code{new Empty}. E.g. +\begin{lstlisting} +val empty = new Empty; +\end{lstlisting} +One problem with this approach is that a value definition such as the +one above is not a legal top-level definition in Scala; it has to be +part of another class or object. Also, the definition of class +\code{Empty} now seems a bit of an overkill -- why define a class of objects, +if we are only interested in a single object of this class? A more +direct approach is to use an {\em object definition}. Here is +a more streamlined alternative definition of the empty set: +\begin{lstlisting} +object empty extends IntSet { + def contains(x: int): boolean = false; + + def incl(x: int): IntSet = new NonEmpty(x, empty, empty); +} +\end{lstlisting} +The syntax of an object definition follows the syntax of a class +definition; it has an optional extends clause as well as an optional +body. As is the case for classes, the extends clause defines inherited +members of the object whereas the body defines overriding or new +members. However, an object definition defines a single object only; +it is not possible to create other objects with the same structure +using \code{new}. Therefore, object definitions also lack constructor +parameters, which might be present in class definitions. + +Object definitions can appear anywhere in a Scala program; including +at top-level. Since there is no fixed execution order of top-level +entities in Scala, one might ask exactly when the object defined by an +object definition is created and initialized. The answer is that the +object is created the first time one of its members is accessed. This +strategy is called {\em lazy evaluation}. + +\paragraph{Standard Classes} + +Scala is a pure object-oriented language. This means that every value +in Scala can be regarded as an object. In fact, even primitive types +such as \code{int} or \code{boolean} are not treated specially. They +are defined as type aliases of Scala classes in module \code{Predef}: +\begin{lstlisting} +type boolean = scala.Boolean; +type int = scala.Int; +type long = scala.Long; +... +\end{lstlisting} +For efficiency, the compiler usually represents values of type +\code{scala.Int} by 32 bit integers, values of type +\code{scala.Boolean} by Java's booleans, etc. But it converts these +specialized representations to objects when required, for instance +when a primitive \code{int} value is passed to a function that with a +parameter of type \code{Object}. Hence, the special representation of +primitive values is just an optimization, it does not change the +meaning of a program. + +Here is a specification of class \code{Boolean}. +\begin{lstlisting} +package scala; +trait Boolean { + def && (def x: Boolean): Boolean; + def || (def x: Boolean): Boolean; + def ! : Boolean; + + def == (x: Boolean) : Boolean + def != (x: Boolean) : Boolean + def < (x: Boolean) : Boolean + def > (x: Boolean) : Boolean + def <= (x: Boolean) : Boolean + def >= (x: Boolean) : Boolean +} +\end{lstlisting} +Booleans can be defined using only classes and objects, without +reference to a built-in type of booleans or numbers. A possible +implementation of class \code{Boolean} is given below. This is not +the actual implementation in the standard Scala library. For +efficiency reasons the standard implementation is built from built-in +booleans. +\begin{lstlisting} +package scala; +trait Boolean { + def ifThenElse(def thenpart: Boolean, def elsepart: Boolean) + + def && (def x: Boolean): Boolean = ifThenElse(x, false); + def || (def x: Boolean): Boolean = ifThenElse(true, x); + def ! : Boolean = ifThenElse(false, true); + + def == (x: Boolean) : Boolean = ifThenElse(x, x.!); + def != (x: Boolean) : Boolean = ifThenElse(x.!, x); + def < (x: Boolean) : Boolean = ifThenElse(false, x); + def > (x: Boolean) : Boolean = ifThenElse(x.!, false); + def <= (x: Boolean) : Boolean = ifThenElse(x, true); + def >= (x: Boolean) : Boolean = ifThenElse(true, x.!); +} +case object True extends Boolean { + def ifThenElse(def t: Boolean, def e: Boolean) = t +} +case object False extends Boolean { + def ifThenElse(def t: Boolean, def e: Boolean) = e +} +\end{lstlisting} +Here is a partial specification of class \code{Int}. + +\begin{lstlisting} +package scala; +trait Int extends Long { + def + (that: Double): Double; + def + (that: Float): Float; + def + (that: Long): Long; + def + (that: Int): Int; // analogous for -, *, /, % + + def << (cnt: Int): Int; // analogous for >>, >>> + + def & (that: Long): Long; + def & (that: Int): Int; // analogous for |, ^ + + def == (that: Double): Boolean; + def == (that: Float): Boolean; + def == (that: Long): Boolean; // analogous for !=, <, >, <=, >= +} +\end{lstlisting} + +Class \code{Int} can in principle also be implemented using just +objects and classes, without reference to a built in type of +integers. To see how, we consider a slightly simpler problem, namely +how to implement a type \code{Nat} of natural (i.e. non-negative) +numbers. Here is the definition of a trait \code{Nat}: +\begin{lstlisting} +trait Nat { + def isZero: Boolean; + def predecessor: Nat; + def successor: Nat; + def + (that: Nat): Nat; + def - (that: Nat): Nat; +} +\end{lstlisting} +To implement the operations of class \code{Nat}, we define a subobject +\code{Zero} and a subclass \code{Succ} (for successor). Each number +\code{N} is represented as \code{N} applications of the \code{Succ} +constructor to \code{Zero}: +\[ +\underbrace{\mbox{\sl new Succ( ... new Succ}}_{\mbox{$N$ times}}\mbox{\sl (Zero) ... )} +\] +The implementation of the \code{Zero} object is straightforward: +\begin{lstlisting} +object Zero extends Nat { + def isZero: Boolean = true; + def predecessor: Nat = error("negative number"); + def successor: Nat = new Succ(Zero); + def + (that: Nat): Nat = that; + def - (that: Nat): Nat = if (that.isZero) Zero else error("negative number") +} +\end{lstlisting} + +The implementation of the predecessor and subtraction functions on +\code{Zero} contains a call to the predefined \code{error} +function. This function aborts the program with the given error +message. + +Here is the implementation of the successor class: +\begin{lstlisting} +class Succ(x: Nat) extends Nat { + def isZero: Boolean = false; + def predecessor: Nat = x; + def successor: Nat = new Succ(this); + def + (that: Nat): Nat = x.+(that.successor); + def - (that: Nat): Nat = x.-(that.predecessor) +} +\end{lstlisting} +Note the implementation of method \code{successor}. To create the +successor of a number, we need to pass the object itself as an +argument to the \code{Succ} constructor. The object itself is +referenced by the reserved name \code{this}. + +The implementations of \code{+} and \code{-} each contain a recursive +call with the constructor argument as receiver. The recursion will +terminate once the receiver is the \code{Zero} object (which is +guaranteed to happen eventually from the way numbers are formed). + +\exercise Write an implementation \code{Integer} of integer numbers +The implementation should support all operations of class \code{Nat} +while adding two methods +\begin{lstlisting} +def isPositive: Boolean +def negate: Integer +\end{lstlisting} +The first method should return \code{true} if the number is positive. The second method should negate the number. +Do not use any of Scala's standard numeric classes in your +implementation. (Hint: There are two possible ways to implement +\code{Integer}. One can either make use the existing implementation of +\code{Nat}, representing an integer as a natural number and a sign. +Or one can generalize the given implementation of \code{Nat} to +\code{Integer}, using the three subclasses \code{Zero} for 0, +\code{Succ} for positive numbers and \code{Pred} for negative numbers.) + + + +\paragraph{Language Elements Introduced In This Chapter} + +\textbf{Types:} +\begin{lstlisting} +Type = ... | ident +\end{lstlisting} + +Types can now be arbitrary identifiers which represent classes. + +\textbf{Expressions:} +\begin{lstlisting} +Expr = ... | Expr '.' ident | 'new' Expr | 'this' +\end{lstlisting} + +An expression can now be an object creation, or +a selection \code{E.m} of a member \code{m} +from an object-valued expression \code{E}, or it can be the reserved name \code{this}. + +\textbf{Definitions and Declarations:} +\begin{lstlisting} +Def = FunDef | ValDef | ClassDef | TraitDef | ObjectDef +ClassDef = ['abstract'] 'class' ident ['(' [Parameters] ')'] + ['extends' Expr] [`{' {TemplateDef} `}'] +TraitDef = 'trait' ident ['extends' Expr] ['{' {TemplateDef} '}'] +ObjectDef = 'object' ident ['extends' Expr] ['{' {ObjectDef} '}'] +TemplateDef = [Modifier] (Def | Dcl) +ObjectDef = [Modifier] Def +Modifier = 'private' | 'override' +Dcl = FunDcl | ValDcl +FunDcl = 'def' ident {'(' [Parameters] ')'} ':' Type +ValDcl = 'val' ident ':' Type +\end{lstlisting} + +A definition can now be a class, trait or object definition such as +\begin{lstlisting} +class C(params) extends B { defs } +trait T extends B { defs } +object O extends B { defs } +\end{lstlisting} +The definitions \code{defs} in a class, trait or object may be +preceded by modifiers \code{private} or \code{override}. + +Abstract classes and traits may also contain declarations. These +introduce {\em deferred} functions or values with their types, but do +not give an implementation. Deferred members have to be implemented in +subclasses before objects of an abstract class or trait can be created. + +\chapter{Case Classes and Pattern Matching} + +Say, we want to write an interpreter for arithmetic expressions. To +keep things simple initially, we restrict ourselves to just numbers +and \code{+} operations. Such expressions can be represented as a class hierarchy, with an abstract base class \code{Expr} as the root, and two subclasses \code{Number} and +\code{Sum}. Then, an expression \code{1 + (3 + 7)} would be represented as +\begin{lstlisting} +new Sum(new Number(1), new Sum(new Number(3), new Number(7))) +\end{lstlisting} +Now, an evaluator of an expression like this needs to know of what +form it is (either \code{Sum} or \code{Number}) and also needs to +access the components of the expression. The following +implementation provides all necessary methods. +\begin{lstlisting} +abstract class Expr { + def isNumber: boolean; + def isSum: boolean; + def numValue: int; + def leftOp: Expr; + def rightOp: Expr; +} +class Number(n: int) extends Expr { + def isNumber: boolean = true; + def isSum: boolean = false; + def numValue: int = n; + def leftOp: Expr = error("Number.leftOp"); + def rightOp: Expr = error("Number.rightOp"); +} +class Sum(e1: Expr, e2: Expr) extends Expr { + def isNumber: boolean = false; + def isSum: boolean = true; + def numValue: int = error("Sum.numValue"); + def leftOp: Expr = e1; + def rightOp: Expr = e2; +} +\end{lstlisting} +With these classification and access methods, writing an evaluator function is simple: +\begin{lstlisting} +def eval(e: Expr): int = { + if (e.isNumber) e.numValue + else if (e.isSum) eval(e.leftOp) + eval(e.rightOp) + else error("unrecognized expression kind") +} +\end{lstlisting} +However, defining all these methods in classes \code{Sum} and +\code{Number} is rather tedious. Furthermore, the problem becomes worse +when we want to add new forms of expressions. For instance, consider +adding a new expression form +\code{Prod} for products. Not only do we have to implement a new class \code{Prod}, with all previous classification and access methods; we also have to introduce a +new abstract method \code{isProduct} in class \code{Expr} and +implement that method in subclasses \code{Number}, \code{Sum}, and +\code{Prod}. Having to modify existing code when a system grows is always problematic, since it introduces versioning and maintenance problems. + +The promise of object-oriented programming is that such modifications +should be unnecessary, because they can be avoided by re-using +existing, unmodified code through inheritance. Indeed, a more +object-oriented decomposition of our problem solves the problem. The +idea is to make the ``high-level'' operation \code{eval} a method of +each expression class, instead of implementing it as a function +outside the expression class hierarchy, as we have done +before. Because \code{eval} is now a member of all expression nodes, +all classification and access methods become superfluous, and the implementation is simplified considerably: +\begin{lstlisting} +abstract class Expr { + def eval: int; +} +class Number(n: int) extends Expr { + def eval: int = n; +} +class Sum(e1: Expr, e2: Expr) extends Expr { + def eval: int = e1.eval + e2.eval; +} +\end{lstlisting} +Furthermore, adding a new \code{Prod} class does not entail any changes to existing code: +\begin{lstlisting} +class Prod(e1: Expr, e2: Expr) extends Expr { + def eval: int = e1.eval * e2.eval; +} +\end{lstlisting} + +The conclusion we can draw from this example is that object-oriented +decomposition is the technique of choice for constructing systems that +should be extensible with new types of data. But there is also another +possible way we might want to extend the expression example. We might +want to add new {\em operations} on expressions. For instance, we might +want to add an operation that pretty-prints an expression tree to standard output. + +If we have defined all classification and access methods, such an +operation can easily be written as an external function. Here is an +implementation: +\begin{lstlisting} +def print(e: Expr): unit = + if (e.isNumber) System.out.print(e.numValue) + else if (e.isSum) { + System.out.print("("); + print(e.leftOp); + System.out.print("+"); + print(e.rightOp); + System.out.print(")"); + } else error("unrecognized expression kind"); +\end{lstlisting} +However, if we had opted for an object-oriented decomposition of +expressions, we would need to add a new \code{print} method +to each class: +\begin{lstlisting} +abstract class Expr { + def eval: int; + def print: unit; +} +class Number(n: int) extends Expr { + def eval: int = n; + def print: unit = System.out.print(n); +} +class Sum(e1: Expr, e2: Expr) extends Expr { + def eval: int = e1.eval + e2.eval; + def print: unit = { + System.out.print("("); + print(e1); + System.out.print("+"); + print(e2); + System.out.print(")"); +} +\end{lstlisting} +Hence, classical object-oriented decomposition requires modification +of all existing classes when a system is extended with new operations. + +As yet another way we might want to extend the interpreter, consider +expression simplification. For instance, we might want to write a +function which rewrites expressions of the form +\code{a * b + a * c} to \code{a * (b + c)}. This operation requires inspection of +more than a single node of the expression tree at the same +time. Hence, it cannot be implemented by a method in each expression +kind, unless that method can also inspect other nodes. So we are +forced to have classification and access methods in this case. This +seems to bring us back to square one, with all the problems of +verbosity and extensibility. + +Taking a closer look, one observers that the only purpose of the +classification and access functions is to {\em reverse} the data +construction process. They let us determine, first, which sub-class +of an abstract base class was used and, second, what were the +constructor arguments. Since this situation is quite common, Scala has +a way to automate it with case classes. + +\paragraph{Case Classes} +A {\em case class} is defined like a normal class, except that the definition +is prefixed with the modifier \code{case}. For instance, the definitions +\begin{lstlisting} +abstract class Expr; +case class Number(n: int) extends Expr; +case class Sum(e1: Expr, e2: Expr) extends Expr; +\end{lstlisting} +introduce \code{Number} and \code{Sum} as case classes. +The \code{case} modifier in front of a class definition has the following effects. +\begin{enumerate} +\item Case classes implicitly come with a constructor function, with the same name as the class. In our example, the two functions +\begin{lstlisting} +def Number(n: int) = new Number(n); +def Sum(e1: Expr, e2: Expr) = new Sum(e1, e2); +\end{lstlisting} +would be added. Hence, one can now construct expression trees a bit more concisely, as in +\begin{lstlisting} +Sum(Sum(Number(1), Number(2)), Number(3)) +\end{lstlisting} +\item Case classes implicity come with implementations of methods +\code{toString}, \code{equals} and \code{hashCode}, which override the +methods with the same name in class \code{Object}. The implementation +of these methods takes in each case the structure of a member of a +case class into account. The \code{toString} method represents an +expression tree the way it was constructed. So, +\begin{lstlisting} +Sum(Sum(Number(1), Number(2)), Number(3)) +\end{lstlisting} +would be converted to exactly that string, whereas he default +implementation in class \code{Object} would return a string consisting +of the outermost constructor name \code{Sum} and a number. The +\code{equals} methods treats two case members of a case class as equal +if they have been constructed with the same constructor and with +arguments which are themselves pairwise equal. This also affects the +implementation of \code{==} and \code{!=}, which are implemented in +terms of \code{equals} in Scala. So, +\begin{lstlisting} +Sum(Number(1), Number(2)) == Sum(Number(1), Number(2)) +\end{lstlisting} +will yield \code{true}. If \code{Sum} or \code{Number} were not case +classes, the same expression would be \code{false}, since the standard +implementation of \code{equals} in class \code{Object} always treats +objects created by different constructor calls as being different. +The \code{hashCode} method follows the same principle as other two +methods. It computes a hash code from the case class constructor name +and the hash codes of the constructor arguments, instead of from the object's +address, which is what the as the default implementation of \code{hashCode} does. +\item +Case classes implicity come with nullary accessor methods which +retrieve the constructor arguments. +In our example, \code{Number} would obtain an accessor method +\begin{lstlisting} +def n: int +\end{lstlisting} +which returns the constructor parameter \code{n}, whereas \code{Sum} would obtain two accessor methods +\begin{lstlisting} +def e1: Expr, e2: Expr; +\end{lstlisting} +Hence, if for a value \code{s} of type \code{Sum}, say, one can now +write \code{s.e1}, to access the left operand. However, for a value +\code{e} of type \code{Expr}, the term \code{e.e1} would be illegal +since \code{e1} is defined in \code{Sum}; it is not a member of the +base class \code{Expr}. +So, how do we determine the constructor and access constructor +arguments for values whose static type is the base class \code{Expr}? +This is solved by the fourth and final particularity of case classes. +\item +Case classes allow the constructions of {\em patterns} which refer to +the case class constructor. +\end{enumerate} + +\paragraph{Pattern Matching} + +Pattern matching is a generalization of C or Java's \code{switch} +statement to class hierarchies. Instead of a \code{switch} statement, +there is a standard method \code{match}, which is defined in Scala's +root class \code{Any}, and therefore is available for all objects. +The \code{match} method takes as argument a number of cases. +For instance, here is an implementation of \code{eval} using +pattern matching. +\begin{lstlisting} +def eval(e: Expr): int = e match { + case Number(x) => x + case Sum(l, r) => eval(l) + eval(r) +} +\end{lstlisting} +In this example, there are two cases. Each case associates a pattern +with an expression. Patterns are matched against the selector +values \code{e}. The first pattern in our example, +\code{Number(n)}, matches all values of the form \code{Number(v)}, +where \code{v} is an arbitrary value. In that case, the {\em pattern +variable} \code{n} is bound to the value \code{v}. Similarly, the +pattern \code{Sum(l, r)} matches all selector values of form +\code{Sum(v}$_1$\code{, v}$_2$\code{)} and binds the pattern variables +\code{l} and \code{r} +to \code{v}$_1$ and \code{v}$_2$, respectively. + +In general, patterns are built from +\begin{itemize} +\item Case class constructors, e.g. \code{Number}, \code{Sum}, whose arguments + are again patterns, +\item pattern variables, e.g. \code{n}, \code{e1}, \code{e2}, +\item the ``wildcard'' pattern \code{_}, +\item constants, e.g. \code{1}, \code{true}, "abc", \code{MAXINT}. +\end{itemize} +Pattern variables always start with a lower-case letter, so that they +can be distinguished from constant identifiers, which start with an +upper case letter. The only exceptions to that rule are the reserved +words \code{null}, \code{true}, \code{false}, which are treated as constants. +Each variable name may occur only once in a pattern. For instance, +\code{Sum(x, x)} would be illegal as a pattern, since \code{x} occurs +twice in it. + +\paragraph{Meaning of Pattern Matching} +A pattern matching expression +\begin{lstlisting} +e.match { case p$_1$ => e$_1$ ... case p$_n$ => e$_n$ } +\end{lstlisting} +matches the patterns $p_1 \commadots p_n$ in the order they +are written against the selector value \code{e}. +\begin{itemize} +\item +A constructor pattern $C(p_1 \commadots p_n)$ matches all values that +are of type \code{C} (or a subtype thereof) and that have been constructed with +\code{C}-arguments matching patterns $p_1 \commadots p_n$. +\item +A variable pattern \code{x} matches any value and binds the variable +name to that value. +\item +The wildcard pattern `\code{_}' matches any value but does not bind a name to that value. +\item A constant pattern \code{C} matches a value which is +equal (in terms of \code{==}) to \code{C}. +\end{itemize} +The pattern matching expression rewrites to the right-hand-side of the +first case whose pattern matches the selector value. References to +pattern variables are replaced by corresponding constructor arguments. +If none of the patterns matches, the pattern matching expression is +aborted with a \code{MatchError} exception. + +\example Our substitution model of program evaluation extends quite naturally to pattern matching, For instance, here is how \code{eval} applied to a simple expression is re-written: +\begin{lstlisting} + eval(Sum(Number(1), Number(2))) + +-> $\mbox{\tab\tab\rm(by rewriting the application)}$ + + Sum(Number(1), Number(2)) match { + case Number(n) => n + case Sum(e1, e2) => eval(e1) + eval(e2) + } + +-> $\mbox{\tab\tab\rm(by rewriting the pattern match)}$ + + eval(Number(1)) + eval(Number(2)) + +-> $\mbox{\tab\tab\rm(by rewriting the first application)}$ + + Number(1) match { + case Number(n) => n + case Sum(e1, e2) => eval(e1) + eval(e2) + } + eval(Number(2)) + +-> $\mbox{\tab\tab\rm(by rewriting the pattern match)}$ + + 1 + eval(Number(2)) + +->$^*$ 1 + 2 -> 3 +\end{lstlisting} + +\paragraph{Pattern Matching and Methods} +In the previous example, we have used pattern +matching in a function which was defined outside the class hierarchy +over which it matches. Of course, it is also possible to define a +pattern matching function in that class hierarchy itself. For +instance, we could have defined +\code{eval} is a method of the base class \code{Expr}, and still have used pattern matching in its implementation: +\begin{lstlisting} +abstract class Expr { + def eval: int = this match { + case Number(n) => n + case Sum(e1, e2) => e1.eval + e2.eval + } +} +\end{lstlisting} + +\exercise +Consider the following three classes representing trees of integers. +These classes can be seen as an alternative representation of \code{IntSet}: +\begin{lstlisting} +trait IntTree; +case class Empty extends IntTree; +case class Node(elem: int, left: IntTree, right: IntTree) extends IntTree; +\end{lstlisting} +Complete the following implementations of function \code{contains} and \code{insert} for +\code{IntTree}'s. +\begin{lstlisting} +def contains(t: IntTree, v: int): boolean = t match { ... + ... +} +def insert(t: IntTree, v: int): IntTree = t match { ... + ... +} +\end{lstlisting} + +\subsection*{Tuples} + +Sometimes, a function needs to return more than one result. For +instance, take the function \code{divmod} which returns the quotient +and rest of two given integer arguments. Of course, one can +define a class to hold the two results of \code{divmod}, as in: +\begin{lstlisting} +case class TwoInts(first: int, second: int); + +def divmod(x: int, y: int): TwoInts = new TwoInts(x / y, x % y) +\end{lstlisting} +However, having to define a new class for every possible pair of +result types is very tedious. It should also be unneccessary because +all such classes have exactly the same structure. In Scala, the +repetition can be avoided by defining a {\em generic class}: +\begin{lstlisting} +case class Pair[+a, +b](first: a, second: b); + +def divmod(x: int, y: int): Pair[int, int] = new Pair[Int, Int](x / y, x % y) +\end{lstlisting} +In this example, \code{[a, b]} are {\em type parameters} of class +\code{Pair}. In a \code{Pair} type, these parameters are replaced by +concrete types. For instance, \code{Pair[int, String]} represents the +type of pairs with \code{int} and \code{String} elements. + +Type arguments can be omitted in constructors, if the correct type can +be inferred from the other constructor arguments or the constructor's +expected result type. In our example, we could have omitted the type +arguments in the body of \code{divmod}, because they can be deduced +from the two value parameters of type \code{int}: +\begin{lstlisting} +def divmod(x: int, y: int): Pair[int, int] = new Pair(x / y, x % y) +\end{lstlisting} +Type parameters are never used in patterns. For instance, here is an +expression in which \code{divmod}'s result is decomposed: +\begin{lstlisting} +divmod(x, y) match { + case Pair(n, d) => System.out.println("quotient: " + n + ", rest: " + d); +} +\end{lstlisting} +The type parameters in class \code{Pair} are each prefixed by a +\code{+} sign. This indicates that \code{Pair}s are {\em +covariant}. That is, if types \code{T}$_1$ and \code{T}$_2$ are +subtypes of types \code{S}$_1$ and \code{S}$_2$, then +\code{Pair[T}$_1$\code{, T}$_2$\code{]} is a subtype of +\code{Pair[S}$_1$\code{, S}$_2$\code{]}. For instance, +\code{Pair[String, int]} is a +subtype of \code{Pair[Object, long]}. If the \code{+}-annotation was +missing, the type constructor would be treated as being +non-variant. That is, pairs with different element types would never +be in a subtype relation. +Besides, \code{+}, there is also a prefix +\code{-} for contra-variant type constructors. +The precise rules that +for variance annotations are given in Chapter~\ref{sec:variance}. + +The idea of pairs is generalized in Scala to tuples of greater arity. +There is a predefined case class \code{Tuple}$_n$ for every \code{n} +from \code{2} to \code{9} in Scala's standard library. The +definitions all follow the template +\begin{lstlisting} +case class Tuple$_n$[+a$_1$, ..., +a$_n$](_1: a$_1$, ..., _n: a$_n$); +\end{lstlisting} +Class \code{Pair} (as well as class \code{Triple}) are also +predefined, but not as classes of their own. Instead +\code{Pair} is an alias of \code{Tuple2} and \code{Triple} is an +alias of \code{Tuple3}. + +\chapter{Lists} + +Lists are an important data structure in many Scala programs. +A list containing the elements \code{x}$_1$, \ldots, \code{x}$_n$ is written +\code{List(x}$_1$\code{, ..., x}$_n$\code{)}. Examples are: +\begin{lstlisting} +val fruit = List("apples", "oranges", "pears"); +val nums = List(1, 2, 3, 4); +val diag3 = List(List(1, 0, 0), List(0, 1, 0)); +val empty = List(); +\end{lstlisting} +Lists are similar to arrays in languages such as C or Java, but there +are also three important differences. First, lists are immutable. That +is, elements of a list can not be changed by assignment. Second, +lists have a recursive structure, whereas arrays are flat. Third, +lists support a much richer set of operations than arrays usually do. + +\paragraph{The List type} +Like arrays, lists are {\em homogeneous}. That is, the elements of a +list all have the same type. The type of a list with elements of type +\code{T} is written \code{List[T]}. (Compare to \code{[]T} for the +type of arrays of type \code{T} in C or Java.). Therefore, the +definitions of list values above can be annotated with types as +follows. +\begin{lstlisting} +val fruit: List[String] = List("apples", "oranges", "pears"); +val nums : List[int] = List(1, 2, 3, 4); +val diag3: List[List[int]] = List(List(1, 0, 0), List(0, 1, 0)); +val empty: List[int] = List(); +\end{lstlisting} + +\paragraph{List constructors} +All lists are built from two more fundamental constructors, \code{Nil} +and \code{::} (pronounced ``cons''). \code{Nil} represents an empty +list. The infix operator \code{::} expresses list extension. That is, +\code{x :: xs} represents a list whose first element is \code{x}, +which is followed by (the elements of) list \code{xs}. Hence, the +list values above could also have been defined as follows (in fact +their previous definition is simply syntactic sugar for the definitions below). +\begin{lstlisting} +val fruit = "apples" :: ("oranges" :: ("pears" :: Nil)); +val nums = 1 :: (2 :: (3 :: (4 :: Nil))); +val diag3 = (1 :: (0 :: (0 :: Nil))) :: + (0 :: (1 :: (0 :: Nil))) :: + (0 :: (0 :: (1 :: Nil))) :: Nil; +val empty = Nil; +\end{lstlisting} +The `\code{::}' operation associates to the right: \code{A :: B :: C} is +interpreted as \code{A :: (B :: C)}. Therefore, we can drop the +parentheses in the definitions above. For instance, we can write +shorter +\begin{lstlisting} +val nums = 1 :: 2 :: 3 :: 4 :: Nil; +\end{lstlisting} + +\paragraph{Basic operations on lists} +All operations on lists can be expressed in terms of the following three: + +\begin{tabular}{ll} +\code{head} & returns the first element of a list,\\ +\code{tail} & returns the list consisting of all elements except the\\ +first element, +\code{isEmpty} & returns \code{true} iff the list is empty +\end{tabular} + +These operations are defined as methods of list objects. So we invoke +them by selecting from the list that's operated on. Examples: +\begin{lstlisting} +empty.isEmpty = true +fruit.isEmpty = false +fruit.head = "apples" +fruit.tail.head = "oranges" +diag3.head = List(1, 0, 0) +\end{lstlisting} +Both \code{head} and \code{tail} are only defined for non-empty lists. +When selected from an empty list, they cause an error instead. + +As an example of how lists can be processed, consider sorting the +elements of a list of numbers into ascending order. One simple way to +do so is {\em insertion sort}, which works as follows: To sort a +non-empty list with first element \code{x} and rest \code{xs}, sort +the remainder \code{xs} and insert the element \code{x} at the right +position in the result. Sorting an empty list will of course yield the +empty list. Expressed as Scala code: +\begin{lstlisting} +def isort(xs: List[int]): List[int] = + if (xs.isEmpty) Nil + else insert(xs.head, isort(xs.tail)) +\end{lstlisting} + +\exercise Provide an implementation of the missing function +\code{insert}. + +\paragraph{List patterns} In fact, \code{::} is +defined defined as a case class in Scala's standard library. Hence, it +is possible to decompose lists by pattern matching, using patterns +composed from the \code{Nil} and \code{::} constructors. For instance, +\code{isort} can be written alternatively as follows. +\begin{lstlisting} +def isort(xs: List[int]): List[int] = xs match { + case List() => List() + case x :: xs1 => insert(x, isort(xs1)) +} +\end{lstlisting} +where +\begin{lstlisting} +def insert(x: int, xs: List[int]): List[int] = xs match { + case List() => List(x) + case y :: ys => if (x <= y) x :: xs else y :: insert(x, ys) +} +\end{lstlisting} + +\paragraph{Polymorphic functions} Consider the problem of writing a + function \code{concat}, which takes a list of element lists as + arguments. The result of \code{concat} should be the concatenation of all + element lists into a single list. + +When trying to define such a function, we observe that we need to give +a type for the list elements: +\begin{lstlisting} +def concat(xss: List[List[ ?? ]]): List[ ?? ] = ... +\end{lstlisting} +Clearly, one could replace \code{??} by \code{int}, say, to obtain a +function \code{concat} that works on lists of lists of integers. But then the +same function could not be applied to other kinds of lists. This is a +pity, since clearly the same algorithm of list concatenation can work +for lists of any element type. Parameterization lets us generalize +from a specific instance of a problem to a more general one. So far, +we have used parameterization only for values, but it is available +also for types. To arrive at a general version of \code{concat}, we +equip it with a type parameter. +\begin{lstlisting} +def concat[a](xs: List[List[a]]): List[a] = xs match { + case List() => xs + case List() :: yss => concat[a](yss) + case (x :: xs) :: yss => x :: concat[a](xs :: yss) +} +\end{lstlisting} +Type parameters are arbitrary names; they are enclosed in brackets +instead of parentheses, so that they can be easily distinguished from +value parameters. Functions like \code{concat} that take type +parameters are called {\em polymorphic}. The term comes from the +Greek, where it means ``having many forms''. + +To apply \code{concat}, we pass type parameters as well as value +parameters to it. For instance, +\begin{lstlisting} +val diag3 = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1)); +concat[int](diag3) +\end{lstlisting} +yields \code{List(1, 0, 0, 0, 1, 0, 0, 0, 1)}. + +\paragraph{Local Type Inference} +Passing type parameters such as \code{[int]} all the time can become +tedious in applications where polymorphic functions are used a +lot. Quite often, the information in a type parameter is redundant, +because the correct parameter type can also be determined by +inspecting the function's value parameters or expected result type. +Taking \code{concat[int](diag3)} function as an example, we know that +its value parameter is of type \code{List[List[int]]}, so we can +deduce that the type parameter must be \code{int}. Scala has a +fairly powerful type inferencer which allows one to omit type +parameters to polymorphic functions and constructors in situations +like these. In the example above, the \code{int} type parameter would +have been inferred if it was not given explicitly. In fact, the same +principle applies in the definition of the value \code{diag3}. +Here, type parameters have been inferred for the four calls of +\code{List}. + +\paragraph{Definition of class List} + +Lists are not built in in Scala; they are defined by an abstract class +\code{List}, which comes with two subclasses for \code{::} and \code{Nil}. +In the following we present a tour through class \code{List}. +\begin{lstlisting} +package scala; +abstract class List[+a] { +\end{lstlisting} +\code{List} is an abstract class, so one cannot define elements by +calling the empty \code{List} constructor (e.g. by +\code{new List}). The class has a type parameter \code{a}. It is +co-variant in this parameter, which means that +\code{List[S] <: List[T]} for all types \code{S} and \code{T} such that +\code{S <: T}. The class is situated in the package +\code{scala}. This is a package containing the most important standard +classes of Scala. \code{List} defines a number of methods, which are +explained in the following. + +First, there are the three basic functions \code{isEmpty}, +\code{head}, \code{tail}. Their implementation in terms of pattern +matching is straightforward: +\begin{lstlisting} +def isEmpty: boolean = match { + case Nil => true + case x :: xs => false +} +def head: a = match { + case Nil => error("Nil.head") + case x :: xs => x +} +def tail: List[a] = match { + case Nil => error("Nil.tail") + case x :: xs => x +} +\end{lstlisting} + +The next function computes the length of a list. +\begin{lstlisting} +def length = match { + case Nil => 0 + case x :: xs => 1 + xs.length +} +\end{lstlisting} + +\exercise Design a tail-recursive version of \code{length}. + +The next two functions are the complements of \code{head} and +\code{tail}. +\begin{lstlisting} +def last: a; +def init: List[a]; +\end{lstlisting} +\code{xs.last} returns the last element of list \code{xs}, whereas +\code{xs.init} returns all elements of \code{xs} except the last. +Both functions have to traverse the entire list, and are thus less +efficient than their \code{head} and \code{tail} analogues. +Here is the implementation of \code{last}. +\begin{lstlisting} +def last: a = match { + case Nil => error("Nil.last") + case x :: Nil => x + case x :: xs => xs.last +} +\end{lstlisting} +The implementation of \code{init} is analogous. + +The next three functions return a prefix of the list, or a suffix, or +both. +\begin{lstlisting} +def take(n: int): List[a] = + if (n == 0 || isEmpty) Nil else head :: tail.take(n-1); + +def drop(n: int): List[a] = + if (n == 0 || isEmpty) this else tail.drop(n-1); + +def split(n: int): Pair[List[a], List[a]] = + if (n == 0 || isEmpty) Pair(Nil, this) + else tail.split(n - 1) match { case Pair(xs, ys) => (head :: xs, ys) } +\end{lstlisting} +\code{(xs take n)} returns the first \code{n} elements of list +\code{xs}, or the whole list, if its length is smaller than \code{n}. +\code{(xs drop n)} returns all elements of \code{xs} except the +\code{n} first ones. Finally, \code{(xs split n)} returns a pair +consisting of the lists resulting from \code{xs take n} and +\code{xs drop n}, but the call is more efficient than performing the +two calls separately. + +The next function returns an element at a given index in a list. +It is thus analogous to array subscripting. Indices start at 0. +\begin{lstlisting} +def at(n: int): a = drop(n).head; +\end{lstlisting} + +With \code{take} and \code{drop}, we can extract sublists consisting +of consecutive elements of the original list. To extract the sublist +$xs_m \commadots xs_{n-1}$ of a list \code{xs}, use: + +\begin{lstlisting} +xs.drop(m).take(n - m) +\end{lstlisting} + +The next function combines two lists into a list of pairs. +Given two lists +\begin{lstlisting} +xs = List(x$_1$, ..., x$_n$) $\mbox{\rm, and}$ +ys = List(y$_1$, ..., y$_n$) , +\end{lstlisting} +\code{xs zip ys} constructs the list +\code{Pair(x}$_1$\code{, y}$_1$\code{), ..., Pair(x}$_n$\code{, y}$_n$\code{)}. +If the two lists have different lengths, the longer one of the two is +truncated. Here is the definition of \code{zip} -- note that it is a +polymorphic method. +\begin{lstlisting} +def zip[b](that: List[b]): List[Pair[a,b]] = + if (this.isEmpty || that.isEmpty) Nil + else Pair(this.head, that.head) :: (this.tail zip that.tail); +\end{lstlisting} + +Like any infix operator, \code{::} +is also implemented as a method of an object. In this case, the object +is the list that is extended. This is possible, because operators +ending with a `\code{:}' character are treated specially in Scala. +All such operators are treated as methods of their right operand. E.g., +\begin{lstlisting} + x :: y = y.::(x) $\mbox{\rm whereas}$ x + y = x.+(y) +\end{lstlisting} +Note, however, that operands of a binary operation are in each case +evaluated from left to right. So, if \code{D} and \code{E} are +expressions with possible side-effects, \code{D :: E} is translated to +\code{{val x = D; E.::(x)}} in order to maintain the left-to-right +order of operand evaluation. + +Another difference between operators ending in a `\code{:}' and other +operators concerns their associativity. Operators ending in +`\code{:}' are right-associative, whereas other operators are +left-associative. E.g., +\begin{lstlisting} + x :: y :: z = x :: (y :: z) $\mbox{\rm whereas}$ x + y + z = (x + y) + z +\end{lstlisting} +The definition of \code{::} as a method in +class \code{List} is as follows: +\begin{lstlisting} +def ::[b >: a](x: b): List[b] = new scala.::(x, this); +\end{lstlisting} +Note that \code{::} is defined for all elements \code{x} of type +\code{B} and lists of type \code{List[A]} such that the type \code{B} +of \code{x} is a supertype of the list's element type \code{A}. The result +is in this case a list of \code{B}'s. This +is expressed by the type parameter \code{b} with lower bound \code{a} +in the signature of \code{::}. + +An operation similar to \code{::} is list concatenation, written +`\code{:::}'. The result of \code{(xs ::: ys)} is a list consisting of +all elements of \code{xs}, followed by all elements of \code{ys}. +Because it ends in a colon, \code{:::} is right-associative and is +considered as a method of its right-hand operand. Therefore, +\begin{lstlisting} +xs ::: ys ::: zs = xs ::: (ys ::: zs) + = zs.:::(ys).:::(xs) +\end{lstlisting} +Here is the implementation of the \code{:::} method: +\begin{lstlisting} + def :::[b >: a](prefix: List[b]): List[b] = prefix match { + case Nil => this + case p :: ps => this.:::(ps).::(p) + } +\end{lstlisting} + +\paragraph{Example: Reverse} As another example of how to program with +lists consider a list reversal. There is a method \code{reverse} in +\code{List} to that effect, but let's implement it as a function +outside the class. Here is a possible implementation of +\code{reverse}: +\begin{lstlisting} +def reverse[a](xs: List[a]): List[a] = xs match { + case List() => List() + case x :: xs => reverse(xs) ::: List(x) +} +\end{lstlisting} +The implementation is quite simple. However, it is not very efficient. +Indeed, one concatenation is executed for every element in the +list. List concatenation takes time proportional to the length +of its first operand. Therefore, the complexity of \code{reverse(xs)} is +\[ +n + (n - 1) + ... + 1 = n(n+1)/2 +\] +where $n$ is the length of \code{xs}. Can \code{reverse} be +implemented more efficiently? We will see later that there is exists +another implementation which has only linear complexity. + +\paragraph{Example: Merge sort} +The insertion sort presented earlier in this chapter is simple to +formulate, but also not very efficient. It's average complexity is +proportional to the square of the length of the input list. We now +design a program to sort the elements of a list which is more +efficient than insertion sort. A good algorithm for this is {\em merge +sort}, which works as follows. + +First, if the list has zero or one elements, it is already sorted, so +one returns the list unchanged. Longer lists are split into two +sub-lists, each containing about half the elements of the original +list. Each sub-list is sorted by a recursive call to the sort +function, and the resulting two sorted lists are then combined in a +merge operation. + +For a general implementation of merge sort, we still have to specify +the type of list elements to be sorted, as well as the function to be +used for the comparison of elements. We obtain a function of maximal +generality by passing these two items as parameters. This leads to the +following implementation. +\begin{lstlisting} +def msort[a](less: (a, a) => boolean)(xs: List[a]): List[a] = { + val n = xs.length/2; + if (n == 0) xs + else { + def merge(xs1: List[a], xs2: List[a]): List[a] = + if (xs1.isEmpty) xs2 + else if (xs2.isEmpty) xs1 + else if (less(xs1.head, xs2.head)) xs1.head :: merge(xs1.tail, xs2) + else xs2.head :: merge(xs1, xs2.tail); + + merge(msort(less)(xs take n), msort(less)(xs drop n)) + } +} +\end{lstlisting} +The complexity of \code{msort} is $O(N;log(N))$, where $N$ is the +length of the input list. To see why, note that splitting a list in +two and merging two sorted lists each take time proportional to the +length of the argument list(s). Each recursive call of \code{msort} +halves the number of elements in its input, so there are $O(log(N))$ +consecutive recursive calls until the base case of lists of length 1 +is reached. However, for longer lists each call spawns off two +further calls. Adding everything up we obtain that at each of the +$O(log(N))$ call levels, every element of the original lists takes +part in one split operation and in one merge operation. Hence, every +call level has a total cost proportional to $O(N)$. Since there are +$O(log(N))$ call levels, we obtain an overall cost of +$O(N;log(N))$. That cost does not depend on the initial distribution +of elements in the list, so the worst case cost is the same as the +average case cost. This makes merge sort an attractive algorithm for +sorting lists. + +Here is an example how \code{msort} is used. +\begin{lstlisting} +def iless(x: int, y: int) = x < y +msort(iless)(List(5, 7, 1, 3)) +\end{lstlisting} +The definition of \code{msort} is curried, to make it easy to specialize it with particular +comparison functions. For instance, +\begin{lstlisting} + +val intSort = msort(iless) +val reverseSort = msort(x: int, y: int => x > y) +\end{lstlisting} + +\section*{Higher-Order Methods} + +\chapter{Computing with Streams} + +The previous chapters have introduced variables, assignment and +stateful objects. We have seen how real-world objects that change +with time can be modelled by changing the state of variables in a +computation. Time changes in the real world thus are modelled by time +changes in program execution. Of course, such time changes are usually +stretched out or compressed, but their relative order is the same. +This seems quite natural, but there is a also price to pay: Our simple +and powerful substitution model for functional computation is no +longer applicable once we introduce variables and assignment. + +Is there another way? Can we model state change in the real world +using only immutable functions? Taking mathematics as a guide, the +answer is clearly yes: A time-changing quantity is simply modelled by +a function \code{f(t)} with a time parameter \code{t}. The same can be +done in computation. Instead of overwriting a variable with successive +values, we represent all these values as successive elements in a +list. So, a mutabel variable \code{var x: T} gets replaced by an +immutable value \code{val x: List[T]}. In a sense, we trade space for +time -- the different values of the variable now all exit concurrently +as different elements of the list. One advantage of the list-based +view is that we can ``time-travel'', i.e. view several successive +values of the variable at the same time. Another advantage is that we +can make use of the powerful library of list processing functions, +which often simplifies computation. For instance, consider the way +imperative way to compute the sum of all prime numbers in an interval: +\begin{lstlisting} +def sumPrimes(start: int, end: int): int = { + var i = start; + var acc = 0; + while (i < end) { + if (isPrime(i)) acc = acc + i; + i = i + 1; + } + acc +} +\end{lstlisting} +Note that the variable \code{i} ``steps through'' all values of the interval +\code{[start .. end-1]}. +%\es\bs +A more functional way is to represent the list of values of variable \code{i} directly as \code{range(start, end)}. Then the function can be rewritten as follows. +\begin{lstlisting} +def sumPrimes(start: int, end: int) = + sum(range(start, end) filter isPrime); +\end{lstlisting} + +No contest which program is shorter and clearer! However, the +functional program is also considerably less efficient since it +constructs a list of all numbers in the interval, and then another one +for the prime numbers. Even worse from an efficiency point of view is +the following example: + +To find the second prime number between \code{1000} and \code{10000}: +\begin{lstlisting} + range(1000, 10000) filter isPrime at 1 +\end{lstlisting} +Here, the list of all numbers between \code{1000} and \code{10000} is +constructed. But most of that list is never inspected! + +However, we can obtain efficient execution for examples like these by +a trick: +\begin{quote} +%\red + Avoid computing the tail of a sequence unless that tail is actually + necessary for the computation. +\end{quote} +We define a new class for such sequences, which is called \code{Stream}. + +Streams are created using the constant \code{empty} and the constructor \code{cons}, +which are both defined in module \code{scala.Stream}. For instance, the following +expression constructs a stream with elements \code{1} and \code{2}: +\begin{lstlisting} +Stream.cons(1, Stream.cons(2, Stream.empty)) +\end{lstlisting} +As another example, here is the analogue of \code{List.range}, +but returning a stream instead of a list: +\begin{lstlisting} +def range(start: Int, end: Int): Stream[Int] = + if (start >= end) Stream.empty + else Stream.cons(start, range(start + 1, end)); +\end{lstlisting} +(This function is also defined as given above in module +\code{Stream}). Even though \code{Stream.range} and \code{List.range} +look similar, their execution behavior is completely different: + +\code{Stream.range} immediately returns with a \code{Stream} object +whose first element is \code{start}. All other elements are computed +only when they are \emph{demanded} by calling the \code{tail} method +(which might be never at all). + +Streams are accessed just as lists. as for lists, the basic access +methods are \code{isEmpty}, \code{head} and \code{tail}. For instance, +we can print all elements of a stream as follows. +\begin{lstlisting} +def print(xs: Stream[a]): unit = + if (!xs.isEmpty) { System.out.println(xs.head); print(xs.tail) } +\end{lstlisting} +Streams also support almost all other methods defined on lists (see +below for where their methods sets differ). For instance, we can find +the second prime number between \code{1000} and \code{10000} by applying methods +\code{filter} and \code{at} on an interval stream: +\begin{lstlisting} + Stream.range(1000, 10000) filter isPrime at 1 +\end{lstlisting} +The difference to the previous list-based implementation is that now +we do not needlessly construct and test for primality any numbers +beyond 3. + +\paragraph{Consing and appending streams} Two methods in class \code{List} +which are not supported by class \code{Stream} are \code{::} and +\code{:::}. The reason is that these methods are dispatched on their +right-hand side argument, which means that this argument needs to be +evaluated before the method is called. For instance, in the case of +\code{x :: xs} on lists, the tail \code{xs} needs to be evaluated +before \code{::} can be called and the new list can be constructed. +This does not work for streams, where we require that the tail of a +stream should not be evaluated until it is demanded by a \code{tail} operation. +The argument why list-append \code{:::} cannot be adapted to streams is analogous. + +Intstead of \code{x :: xs}, one uses \code{Stream.cons(x, xs)} for +constructing a stream with first element \code{x} and (unevaluated) +rest \code{xs}. Instead of \code{xs ::: ys}, one uses the operation +\code{xs append ys}. + +%\redtext +{Is there another way?} + + + +\bibliography{examples} +\end{document} + + + +\paragrph{Higher Order Functions +\bsh{Patterns of Computation over Lists} + +\bi +\item The examples show that functions over lists often have similar + structures +\item We can identify several patterns of computation like + \bi + \item Transform every element of a list in some way. + \item Extract from a list all elements satisfying a criterion. + \item Combine the elements of a list using some operator. + \ei +\item Functional programming languages enable programmers to write + general functions which implement patterns like this +\item These functions are \redtext{\em higher-order functions} which get + a transformation or an operator as one argument +\ei +\es + +Pairs, and tuples or greater arity are useful enough to + + + + + +\chapter{Generic Types and Methods} + +Classes in Scala can have type parameters. We demonstrate the use of +type parameters with iterators as an example. An iterator is an object +which traverses a sequence of values, using two abstract methods. +\begin{lstlisting} +abstract class Iterator[a] { + def hasNext: boolean; + def next: a; +\end{lstlisting} +Method \code{next} returns successive elements. Method \code{hasNext} +indicates whether there are still more elements to be returned by +\code{next}. The type of the elements returned by an iterator is +arbitrary. We express this by giving the class \code{Iterator} the +type parameter \code{a}. Type parameters are written in square +brackets, in contrast to normal value parameters, which are written in +parentheses. Iterators also support other methods, which are +explained later. + +Here's an iterator which traverses an interval of integer values. +\begin{lstlisting} +class RangeIterator(start: int, end: int) extends Iterator[int] { + private var current = 0; + def hasNext = current < end; + def next = { + val r = current; + if (current < end) current = current + 1 + else error("end of iterator"); + r + } +} +\end{lstlisting} +The superclass of \code{RangeIterator} is \code{Iterator[int]}, +i.e. an iterator returning integer numbers. + +Note that, unlike the classes we have seen so far, +\code{RangeIterator} has internal state + + +Here is a function that takes an iterator of arbitrary element type +\code{a} and a procedure that maps \code{a}-values to the trivial type \code{unit}. +It applies the given function to every value returned by the iterator. +\begin{lstlisting} + def forall[a](i: Iterator[a])(f: a => boolean): boolean = + !hasNext || { val x = next; f(x) && forall(i, f) } +\end{lstlisting} +\code{forEach} can work with any type of iterator, +since the iterator's element type is passed as a type parameter \code{a}. +Functions that take type parameters are called {\em polymorphic}. The term +comes from Greek, where it means ``having many forms''. + +Finally, here is an application which uses \code{RangeIterator} and +\code{foreach} to test whether a given number is prime, i.e. whether it can be +divided only by 1 and itself. +\begin{lstlisting} +def isPrime(x: int) = + forall[int](new RangeIterator(2, n)) { x => x % n != 0 } +\end{lstlisting} +As always, the actual parameters of \code{forEach} correspond to its +formal parameters. First comes the type parameter \code{int}, which +determines the element type of the iterator which is passed next. + +\paragraph{Local Type Inference} +Passing type parameters such as \code{[int]} all the time can become +tedious in applications where polymorphic functions are used a +lot. Quite often, the information in a type parameter is redundant, +because the correct parameter type can also be determined by +inspecting the function's value parameters or expected result type. +Taking the \code{isPrime} function as an example, we know that its +first value parameter is of type \code{Iterator[int]}, so we can +determine the type parameter \code{int} from it. Scala contains a +fairly powerful local type inferencer which allows one to omit type +parameters to polymorphic functions and constructors in situations +like these. In the example above, the \code{int} type parameter would +have been inferred if it was not given explicitly. + +Here is another +application which prints all prime numbers between 1 and 10000. +\begin{lstlisting} +forall(new RangeIterator(1, 10001)){ x => if (isPrime(x)) System.out.println(x) } +\end{lstlisting} +This time, the type parameter for \code{forEach} was omitted (and was +inferred to be \code{int}). + +Method \code{append} constructs an iterator which resumes with the +given iterator \code{it} after the current iterator has finished. +\begin{lstlisting} + def append(that: Iterator[a]): Iterator[a] = new Iterator[a] { + def hasNext = outer.hasNext || that.hasNext; + def next = if (outer.hasNext) outer.next else that.next; + } +\end{lstlisting} +The terms \code{outer.next} and \code{outer.hasNext} in the definition +of \code{append} call the corresponding methods as they are defined in +the enclosing \code{Iterator} class. Generally, an +\code{outer} prefix in a selection indicates an identifier that is +visible immediately outside the current class or template. If the +\code{outer} prefix would have been missing, +\code{hasNext} and \code{next} would have +called recursively the methods being defined in the iterator +constructed by \code{append}, which is not what we want. + +Method \code{filter} constructs an iterator which returns all elements +of the original iterator that satisfy a criterion \code{p}. +\begin{lstlisting} + def filter(p: a => boolean) = new Iterator[a] { + private class Cell[T](elem_: T) { def elem = elem_; } + private var head: Cell[a] = null; + private var isAhead = false; + def hasNext: boolean = + if (isAhead) true + else if (outer.hasNext) { + head = Cell(outer.next); isAhead = p(head.elem); hasNext } + else false; + def next: a = + if (hasNext) { isAhead = false; head.elem } + else error("next on empty iterator"); + } +\end{lstlisting} +Method \code{map} constructs an iterator which returns all elements of +the original iterator transformed by a given function \code{f}. +\begin{lstlisting} + def map[b](f: a => b) = new Iterator[b] { + def hasNext: boolean = outer.hasNext; + def next: b = f(outer.next); + } +\end{lstlisting} +The return type of the transformation function \code{f} is +arbitrary. This is expressed by a type parameter \code{b} in the +signature of method \code{map}, which represents the return type. +We also say, \code{map} is a {\em polymorphic} function. + +Method \code{flatMap} is like method \code{map}, except that the +transformation function \code{f} now returns an iterator. +The result of \code{flatMap} is the iterator resulting from appending +together all iterators returned from successive calls of \code{f}. +\begin{lstlisting} + private var cur: Iterator[b] = new EmptyIterator[b]; + def hasNext: boolean = + if (cur.hasNext) true + else if (outer.hasNext) { cur = f(outer.next); hasNext } + else false; + def next: b = + if (cur.hasNext) cur.next + else if (outer.hasNext) { cur = f(outer.next); next } + else error("next on empty iterator"); + } +\end{lstlisting} +Finally, method \code{zip} takes another iterator and +returns an iterator consisting of pairs of corresponding elements +returned by the two iterators. +\begin{lstlisting} + def zip[b](that: Iterator[b]) = new Iterator[(a, b)] { + def hasNext = outer.hasNext && that.hasNext; + def next = (outer.next, that.next); + } +} //end iterator; +\end{lstlisting} +Concrete iterators need to provide implementations for the two +abstract methods \code{next} and \code{hasNext} in class +\code{Iterator}. The simplest iterator is \code{EmptyIterator} +which always returns an empty sequence: +\begin{lstlisting} +class EmptyIterator[a] extends Iterator[a] { + def hasNext = false; + def next: a = error("next on empty iterator"); +} +\end{lstlisting} +A more interesting iterator enumerates all elements of an array. +This iterator is formulated here as a polymorphic function. It could +have also been written as a class, like \code{EmptyIterator}. The +difference between the two formulation is that classes also define new +types, whereas functions do not. +\begin{lstlisting} +def arrayIterator[a](xs: Array[a]) = new Iterator[a] { + private var i = 0; + def hasNext: boolean = + i < xs.length; + def next: a = + if (i < xs.length) { val x = xs(i) ; i = i + 1 ; x } + else error("next on empty iterator"); +} +\end{lstlisting} +Another iterator enumerates an integer interval: +\begin{lstlisting} +def range(lo: int, hi: int) = new Iterator[int] { + private var i = lo; + def hasNext: boolean = + i <= hi; + def next: int = + if (i <= hi) { i = i + 1 ; i - 1 } + else error("next on empty iterator"); +} +\end{lstlisting} +%In fact, enumerating integer intervals is so common that it is +%supported by a method +%\begin{lstlisting} +%def to(hi: int): Iterator[int] +%\end{lstlisting} +%in class \code{int}. Hence, one could also write \code{l to h} instead of +%\code{range(l, h)}. +All iterators seen so far terminate eventually. It is also possible to +define iterators that go on forever. For instance, the following +iterator returns successive integers from some start +value\footnote{Due to the finite representation of type \prog{int}, +numbers will wrap around at $2^31$.}. +\begin{lstlisting} +def from(start: int) = new Iterator[int] { + private var last = start - 1; + def hasNext = true; + def next = { last = last + 1; last } +} +\end{lstlisting} +Here are two examples how iterators are used. First, to print all +elements of an array \code{xs: Array[int]}, one can write: +\begin{lstlisting} + arrayIterator[int](xs) foreach (x => System.out.println(x)) +\end{lstlisting} +Here, \code{[int]} is a type argument clause, which matches the type +parameter clause \code{[a]} of function \code{arrayIterator}. It +substitutes the formal argument \code{int} for the formal argument +\code{a} in the type of the method that follows. Hence, +\code{arrayIterator[a]} is a function that takes an \code{Array[int]} +and that returns an \code{Iterator[int]}. + +In this example, the formal type argument \code{int} is redundant +since it could also have been inferred from the value \code{xs}, which +is, after all, an array of \code{int}. The Scala compiler contains a +fairly powerful type inferencer which infers type arguments for +methods and constructors from the types of value arguments and the +expected return type. In our example, the \code{[int]} clause can be +inferred, so that one can abbreviate to: +\begin{lstlisting} + arrayIterator(xs) foreach (x => System.out.println(x)) +\end{lstlisting} +%As a second example, consider the problem of finding the indices of +%all the elements in an array of \code{double}s greater than some +%\code{limit}. The indices should be returned as an iterator. +%This is achieved by the following expression. +%\begin{lstlisting} +%arrayIterator(xs) +% .zip(from(0)) +% .filter(x, i => x > limit) +% .map(x, i => i) +%\end{lstlisting} +%The first line in this expression iterates through all array elements, +%the second lines pairs elements with their indices, the third line +%selects all value/index pairs where the value is greater than +%\code{limit}, and the fourth line returns the index part of all +%selected pairs. + +%Note that we have omitted the type arguments for the calls of +%\code{arrayIterator}, \code{zip} and \code{map}. These are all +%implicitly inserted by the type inferencer. + + + +\es +\paragraph{Abstract Methods} +Classes can also omit some of the definitions of their members. As an +example, consider the following class \code{Ord} which provides the +comparison operators \code{<, >, <=, >=}. +%\begin{lstlisting} +%abstract class Ord { +% abstract def <(that: this); +% def <=(that: this) = this < that || this == that; +% def >(that: this) = that < this; +% def >=(that: this) = that <= this; +%} +%\end{lstlisting} +\begin{lstlisting} +abstract class Ord { + def <(that: this): boolean; + def <=(that: this) = this < that || this == that; + def >(that: this) = that < this; + def >=(that: this) = that <= this; +} +\end{lstlisting} +Since we want to leave open which objects are compared, we are unable +to give an implementation for the \code{<} method. However, once +\code{<} is given, we can define the other three comparison operators +in terms of \code{<} and the equality test \code{==} (which is defined +in class \code{Object}). This is expressed by having in \code{Ord} an +{\em abstract} method \code{<} to which the implementations of the +other methods refer. + +\paragraph{Self References} The name \code{this} refers in this class +to the current object. The type of \code{this} is also called +\code{this} (generally, every name in Scala can have a definition as a +term and another one as a type). When used as a type, \code{this} +refers to the type of the current object. This type is always +compatible with the class being defined (\code{Ord} in this case). + +\paragraph{Mixin Composition} +We can now define a class of \code{Rational} numbers that +support comparison operators. +\begin{lstlisting} +final class OrderedRational(n: int, d: int) + extends Rational(n, d) with Ord { + override def ==(that: OrderedRational) = + numer == that.numer && denom == that.denom; + def <(that: OrderedRational): boolean = + numer * that.denom < that.numer * denom; +} +\end{lstlisting} +Class \code{OrderedRational} redefines method \code{==}, which is +defined as reference equality in class \code{Object}. It also +implements the abstract method \code{<} from class \code{Ord}. In +addition, it inherits all members of class \code{Rational} and all +non-abstract members of class \code{Ord}. The implementations of +\code{==} and \code{<} replace the definition of \code{==} in class +\code{Object} and the abstract declaration of \code{<} in class +\code{Ord}. The other inherited comparison methods then refer to this +implementation in their body. + +The clause ``\code{Rational(d, d) with Ord}'' is an instance of {\em +mixin composition}. It describes a template for an object that is +compatible with both \code{Rational} and \code{Ord} and that contains +all members of either class. \code{Rational} is called the {\em +superclass} of \code{OrderedRational} while \code{Ord} is called a +{\em mixin class}. The type of this template is the {\em compound +type} ``\code{Rational with Ord}''. + +On the surface, mixin composition looks much like multiple +inheritance. The difference between the two becomes apparent if we +look at superclasses of inherited classes. With multiple inheritance, +both \code{Rational} and \code{Ord} would contribute a superclass +\code{Object} to the template. We therefore have to answer some +tricky questions, such as whether members of \code{Object} are present +once or twice and whether the initializer of \code{Object} is called +once or twice. Mixin composition avoids these complications. In the +mixin composition \code{Rational with Ord}, class +\code{Rational} is treated as actual superclass of class \code{Ord}. +A mixin composition \code{C with M} is well-formed as long as the +first operand \code{C} conforms to the declared superclass of the +second operand \code{M}. This holds in our example, because +\code{Rational} conforms to \code{Object}. In a sense, mixin composition +amounts to overriding the superclass of a class. + +\paragraph{Final Classes} +Note that class \code{OrderedRational} was defined +\code{final}. This means that no classes extending \code{OrderedRational} +may be defined in other parts of the program. +%Within final classes the +%type \code{this} is an alias of the defined class itself. Therefore, +%we could define our \code{<} method with an argument of type +%\code{OrderedRational} as a well-formed implementation of the abstract class +%\code{less(that: this)} in class \code{Ord}. + + +\chapter{Generic Types and Methods} + +Classes in Scala can have type parameters. We demonstrate the use of +type parameters with iterators as an example. An iterator is an object +which traverses a sequence of values, using two abstract methods. +\begin{lstlisting} +abstract class Iterator[a] { + def hasNext: boolean; + def next: a; +\end{lstlisting} +Method \code{next} returns successive elements. Method \code{hasNext} +indicates whether there are still more elements to be returned by +\code{next}. The type of elements returned by an iterator is +arbitrary. We express that by giving the class \code{Iterator} the +type parameter \code{a}. Type parameters are written in square +brackets, in contrast to normal value parameters, which are written in +parentheses. Iterators also support other methods, which are +explained in the following. + +Method \code{foreach} applies a procedure (i.e. a function +returning \code{unit} to each element returned by the iterator: +\begin{lstlisting} + def foreach(f: a => unit): unit = + while (hasNext) { f(next) } +\end{lstlisting} + +Method \code{append} constructs an iterator which resumes with the +given iterator \code{it} after the current iterator has finished. +\begin{lstlisting} + def append(that: Iterator[a]): Iterator[a] = new Iterator[a] { + def hasNext = outer.hasNext || that.hasNext; + def next = if (outer.hasNext) outer.next else that.next; + } +\end{lstlisting} +The terms \code{outer.next} and \code{outer.hasNext} in the definition +of \code{append} call the corresponding methods as they are defined in +the enclosing \code{Iterator} class. Generally, an +\code{outer} prefix in a selection indicates an identifier that is +visible immediately outside the current class or template. If the +\code{outer} prefix would have been missing, +\code{hasNext} and \code{next} would have +called recursively the methods being defined in the iterator +constructed by \code{append}, which is not what we want. + +Method \code{filter} constructs an iterator which returns all elements +of the original iterator that satisfy a criterion \code{p}. +\begin{lstlisting} + def filter(p: a => boolean) = new Iterator[a] { + private class Cell[T](elem_: T) { def elem = elem_; } + private var head: Cell[a] = null; + private var isAhead = false; + def hasNext: boolean = + if (isAhead) true + else if (outer.hasNext) { + head = Cell(outer.next); isAhead = p(head.elem); hasNext } + else false; + def next: a = + if (hasNext) { isAhead = false; head.elem } + else error("next on empty iterator"); + } +\end{lstlisting} +Method \code{map} constructs an iterator which returns all elements of +the original iterator transformed by a given function \code{f}. +\begin{lstlisting} + def map[b](f: a => b) = new Iterator[b] { + def hasNext: boolean = outer.hasNext; + def next: b = f(outer.next); + } +\end{lstlisting} +The return type of the transformation function \code{f} is +arbitrary. This is expressed by a type parameter \code{b} in the +signature of method \code{map}, which represents the return type. +We also say, \code{map} is a {\em polymorphic} function. + +Method \code{flatMap} is like method \code{map}, except that the +transformation function \code{f} now returns an iterator. +The result of \code{flatMap} is the iterator resulting from appending +together all iterators returned from successive calls of \code{f}. +\begin{lstlisting} + private var cur: Iterator[b] = new EmptyIterator[b]; + def hasNext: boolean = + if (cur.hasNext) true + else if (outer.hasNext) { cur = f(outer.next); hasNext } + else false; + def next: b = + if (cur.hasNext) cur.next + else if (outer.hasNext) { cur = f(outer.next); next } + else error("next on empty iterator"); + } +\end{lstlisting} +Finally, method \code{zip} takes another iterator and +returns an iterator consisting of pairs of corresponding elements +returned by the two iterators. +\begin{lstlisting} + def zip[b](that: Iterator[b]) = new Iterator[(a, b)] { + def hasNext = outer.hasNext && that.hasNext; + def next = (outer.next, that.next); + } +} //end iterator; +\end{lstlisting} +Concrete iterators need to provide implementations for the two +abstract methods \code{next} and \code{hasNext} in class +\code{Iterator}. The simplest iterator is \code{EmptyIterator} +which always returns an empty sequence: +\begin{lstlisting} +class EmptyIterator[a] extends Iterator[a] { + def hasNext = false; + def next: a = error("next on empty iterator"); +} +\end{lstlisting} +A more interesting iterator enumerates all elements of an array. +This iterator is formulated here as a polymorphic function. It could +have also been written as a class, like \code{EmptyIterator}. The +difference between the two formulation is that classes also define new +types, whereas functions do not. +\begin{lstlisting} +def arrayIterator[a](xs: Array[a]) = new Iterator[a] { + private var i = 0; + def hasNext: boolean = + i < xs.length; + def next: a = + if (i < xs.length) { val x = xs(i) ; i = i + 1 ; x } + else error("next on empty iterator"); +} +\end{lstlisting} +Another iterator enumerates an integer interval: +\begin{lstlisting} +def range(lo: int, hi: int) = new Iterator[int] { + private var i = lo; + def hasNext: boolean = + i <= hi; + def next: int = + if (i <= hi) { i = i + 1 ; i - 1 } + else error("next on empty iterator"); +} +\end{lstlisting} +%In fact, enumerating integer intervals is so common that it is +%supported by a method +%\begin{lstlisting} +%def to(hi: int): Iterator[int] +%\end{lstlisting} +%in class \code{int}. Hence, one could also write \code{l to h} instead of +%\code{range(l, h)}. +All iterators seen so far terminate eventually. It is also possible to +define iterators that go on forever. For instance, the following +iterator returns successive integers from some start +value\footnote{Due to the finite representation of type \prog{int}, +numbers will wrap around at $2^31$.}. +\begin{lstlisting} +def from(start: int) = new Iterator[int] { + private var last = start - 1; + def hasNext = true; + def next = { last = last + 1; last } +} +\end{lstlisting} +Here are two examples how iterators are used. First, to print all +elements of an array \code{xs: Array[int]}, one can write: +\begin{lstlisting} + arrayIterator[int](xs) foreach (x => System.out.println(x)) +\end{lstlisting} +Here, \code{[int]} is a type argument clause, which matches the type +parameter clause \code{[a]} of function \code{arrayIterator}. It +substitutes the formal argument \code{int} for the formal argument +\code{a} in the type of the method that follows. Hence, +\code{arrayIterator[a]} is a function that takes an \code{Array[int]} +and that returns an \code{Iterator[int]}. + +In this example, the formal type argument \code{int} is redundant +since it could also have been inferred from the value \code{xs}, which +is, after all, an array of \code{int}. The Scala compiler contains a +fairly powerful type inferencer which infers type arguments for +methods and constructors from the types of value arguments and the +expected return type. In our example, the \code{[int]} clause can be +inferred, so that one can abbreviate to: +\begin{lstlisting} + arrayIterator(xs) foreach (x => System.out.println(x)) +\end{lstlisting} +%As a second example, consider the problem of finding the indices of +%all the elements in an array of \code{double}s greater than some +%\code{limit}. The indices should be returned as an iterator. +%This is achieved by the following expression. +%\begin{lstlisting} +%arrayIterator(xs) +% .zip(from(0)) +% .filter(x, i => x > limit) +% .map(x, i => i) +%\end{lstlisting} +%The first line in this expression iterates through all array elements, +%the second lines pairs elements with their indices, the third line +%selects all value/index pairs where the value is greater than +%\code{limit}, and the fourth line returns the index part of all +%selected pairs. + +%Note that we have omitted the type arguments for the calls of +%\code{arrayIterator}, \code{zip} and \code{map}. These are all +%implicitly inserted by the type inferencer. + +\chapter{\label{sec:for-notation}For-Comprehensions} + +The last chapter has demonstrated that the use of higher-order +functions over sequences can lead to very concise programs. But +sometimes the level of abstraction required by these functions makes a +program hard to understand. + +Here, Scala's \code{for} notation can help. For instance, say we are +given a sequence \code{persons} of persons with \code{name} and +\code{age} fields. That sequence could be an array, or a list, or an +iterator, or some other type implementing the sequence abstraction +(this will be made more precise below). To print the names of all +persons in the sequence which are aged over 20, one writes: +\begin{lstlisting} +for { val p <- persons; p.age > 20 } yield p.name +\end{lstlisting} +This is equivalent to the following expression , which uses +higher-order functions \code{filter} and \code{map}: +\begin{lstlisting} +persons filter (p => p.age > 20) map (p => p.name) +\end{lstlisting} +The for-expression looks a bit like a for-loop in imperative languages, +except that it constructs a list of the results of all iterations. + +Generally, a for-comprehension is of the form +\begin{lstlisting} +for ( s ) yield e +\end{lstlisting} +(Instead of parentheses, braces may also be used.) +Here, \code{s} is a sequence of {\em generators} and {\em filters}. +\begin{itemize} +\item A {\em generator} is of the form \code{val x <- e}, +where \code{e} is a list-valued expression. It binds \code{x} to +successive values in the list. +\item A {\em filter} is an expression \code{f} of type \code{boolean}. +It omits from consideration all bindings for which \code{f} is \code{false}. +\end{itemize} +The sequence must start with a generator. +If there are several generators in a sequence, later generators vary +more rapidly than earlier ones. + +Here are two examples that show how for-comprehensions are used. + +First, given a positive integer \code{n}, find all pairs of positive +integers +\code{i}, \code{j}, where \code{1 <= j < i <= n} such that \code{i + j} is prime. +\begin{lstlisting} +for { val i <- range(1, n); + val j <- range(1, i-1); + isPrime(i+j) +} yield (i, j) +\end{lstlisting} + +As second example, the scalar product of two vectors \code{xs} and +\code{ys} can now be written as +follows. +\begin{lstlisting} + sum (for { val (x, y) <- xs zip ys } yield x * y) +\end{lstlisting} +The for-notation is essentially equivalent to common operations of +database query languages. For instance, say we are given a book +database \code{books}, represented as a list of books, where +\code{Book} is defined as follows. +\begin{lstlisting} +abstract class Book { + val title: String; + val authors: List[String] +} +\end{lstlisting} +\begin{lstlisting} +val books: List[Book] = [ + new Book { + val title = "Structure and Interpretation of Computer Programs"; + val authors = ["Abelson, Harald", "Sussman, Gerald J."]; + }, + new Book { + val title = "Principles of Compiler Design"; + val authors = ["Aho, Alfred", "Ullman, Jeffrey"]; + }, + new Book { + val title = "Programming in Modula-2"; + val authors = ["Wirth, Niklaus"]; + } +]; +\end{lstlisting} +Then, to find the titles of all books whose author's last name is ``Ullman'': +\begin{lstlisting} +for { val b <- books; val a <- b.authors; a startsWith "Ullman" +} yield b.title +\end{lstlisting} +(Here, \code{startsWith} is a method in \code{java.lang.String}). Or, +to find the titles of all books that have the string ``Program'' in +their title: +\begin{lstlisting} +for { val b <- books; (b.title indexOf "Program") >= 0 +} yield b.title +\end{lstlisting} +Or, to find the names of all authors that have written at least two +books in the database. +\begin{lstlisting} +for { val b1 <- books; + val b2 <- books; + b1 != b2; + val a1 <- b1.authors; + val a2 <- b2.authors; + a1 == a2 } yield a1 +\end{lstlisting} +The last solution is not yet perfect, because authors will appear +several times in the list of results. We still need to remove +duplicate authors from result lists. This can be achieved with the +following function. +\begin{lstlisting} +def removeDuplicates[a](xs: List[a]): List[a] = + if (xs.isEmpty) xs + else xs.head :: removeDuplicates(xs.tail filter (x => x != xs.head)); +\end{lstlisting} +The last expression can be equivalently expressed as follows. +\begin{lstlisting} +xs.head :: removeDuplicates(for (val x <- xs.tail; x != xs.head) yield x) +\end{lstlisting} + +\subsection*{Translation of \prog{for}} + +Every for-comprehensions can be expressed in terms of the three +higher-order functions \code{map}, \code{flatMap} and \code{filter}. +Here is the translation scheme, which is also used by the Scala compiler. +\begin{itemize} +\item +A simple for-comprehension +\begin{lstlisting} +for (val x <- e) yield e' +\end{lstlisting} +is translated to +\begin{lstlisting} +e.map(x => e') +\end{lstlisting} +\item +A for-comprehension +\begin{lstlisting} +for (val x <- e; f; s) yield e' +\end{lstlisting} +where \code{f} is a filter and \code{s} is a (possibly empty) +sequence of generators or filters +is translated to +\begin{lstlisting} +for (val x <- e.filter(x => f); s) yield e' +\end{lstlisting} +and then translation continues with the latter expression. +\item +A for-comprehension +\begin{lstlisting} +for (val x <- e; y <- e'; s) yield e'' +\end{lstlisting} +where \code{s} is a (possibly empty) +sequence of generators or filters +is translated to +\begin{lstlisting} +e.flatMap(x => for (y <- e'; s) yield e'') +\end{lstlisting} +and then translation continues with the latter expression. +\end{itemize} +For instance, taking our "pairs of integers whose sum is prime" example: +\begin{lstlisting} +for { val i <- range(1, n); + val j <- range(1, i-1); + isPrime(i+j) +} yield (i, j) +\end{lstlisting} +Here is what we get when we translate this expression: +\begin{lstlisting} +range(1, n) + .flatMap(i => + range(1, i-1) + .filter(j => isPrime(i+j)) + .map(j => (i, j))) +\end{lstlisting} + +\exercise +Define the following function in terms of \code{for}. +\begin{lstlisting} +def concat(xss: List[List[a]]): List[a] = + (xss foldr []) { xs, ys => xs ::: ys } +\end{lstlisting} +\exercise +Translate +\begin{lstlisting} +for { val b <- books; val a <- b.authors; a startsWith "Bird" } yield b.title +for { val b <- books; (b.title indexOf "Program") >= 0 } yield b.title +\end{lstlisting} +to higher-order functions. + +We have seen that the for-translation only relies on the presence of +methods \code{map}, +\code{flatMap}, and \code{filter}. +This gives programmers the possibility to have for-syntax for +other types as well -- one only needs to define \code{map}, +\code{flatMap}, and \code{filter} for these types. +That's also why we were able to define \code{for} at the same time for +arrays, iterators, and lists -- all these types have the required +three methods \code{map},\code{flatMap}, and \code{filter} as members. +Of course, it is also possible for users and library designers to +define other types with these methods. There are many examples where +this is useful: Databases, XML trees, optional values. We will see in +Chapter~\ref{sec:parsers-results} how for-comprehensions can be used in the +definition of parsers for context-free grammars that construct +abstract syntax trees. + +\chapter{\label{sec:simple-examples}Pattern Matching} + +\todo{Complete} + +Consider binary trees whose leafs contain integer arguments. This can +be described by a class for trees, with subclasses for leafs and +branch nodes: +\begin{lstlisting} +abstract class Tree; +case class Branch(left: Tree, right: Tree) extends Tree; +case class Leaf(x: int) extends Tree; +\end{lstlisting} +Note that the class \code{Tree} is not followed by an extends +clause or a body. This defines \code{Tree} to be an empty +subclass of \code{Object}, as if we had written +\begin{lstlisting} +class Tree extends Object {} +\end{lstlisting} +Note also that the two subclasses of \code{Tree} have a \code{case} +modifier. That modifier has two effects. First, it lets us construct +values of a case class by simply calling the constructor, without +needing a preceding \code{new}. Example: +\begin{lstlisting} +val tree1 = Branch(Branch(Leaf(1), Leaf(2)), Branch(Leaf(3), Leaf(4))) +\end{lstlisting} +Second, it lets us use constructors for these classes in patterns, as +is illustrated in the following example. +\begin{lstlisting} +def sumLeaves(t: Tree): int = t match { + case Branch(l, r) => sumLeaves(l) + sumLeaves(r) + case Leaf(x) => x +} +\end{lstlisting} +The function \code{sumLeaves} sums up all the integer values in the +leaves of a given tree \code{t}. It is is implemented by calling the +\code{match} method of \code{t} with a {\em choice expression} as +argument (\code{match} is a predefined method in class \code{Object}). +The choice expression consists of two cases which both +relate a pattern with an expression. The pattern of the first case, +\code{Branch(l, r)} matches all instances of class \code{Branch} +and binds the {\em pattern variables} \code{l} and \code{r} to the +constructor arguments, i.e.\ the left and right subtrees of the +branch. Pattern variables always start with a lower case letter; to +avoid ambiguities, constructors in patterns should start with an upper +case letter. + +The effect of the choice expression is to select the first alternative +whose pattern matches the given select value, and to evaluate the body +of this alternative in a context where pattern variables are bound to +corresponding parts of the selector. For instance, the application +\code{sumLeaves(tree1)} would select the first alternative with the +\code{Branch(l,r)} pattern, and would evaluate the expression +\code{sumLeaves(l) + sumLeaves(r)} with bindings +\begin{lstlisting} +l = Branch(Leaf(1), Leaf(2)), r = Branch(Leaf(3), Leaf(4)). +\end{lstlisting} +As another example, consider the following class +\begin{lstlisting} +abstract final class Option[+a]; +case object None extends Option[All]; +case class Some[a](item: a) extends Option[a]; +\end{lstlisting} +... + +%\todo{Several simple and intermediate examples needed}. + +\begin{lstlisting} +def find[a,b](it: Iterator[(a, b)], x: a): Option[b] = { + var result: Option[b] = None; + while (it.hasNext && result == None) { + val (x1, y) = it.next; + if (x == x1) result = Some(y) + } + result +} +find(xs, x) match { + case Some(y) => System.out.println(y) + case None => System.out.println("no match") +} +\end{lstlisting} + +\comment{ + + +class MaxCounter { + var maxVal: Option[int] = None; + def set(x: int) = maxVal match { + case None => maxVal = Some(x) + case Some(y) => maxVal = Some(Math.max(x, y)) + } +} +\end{lstlisting} +} +\comment{ +\begin{lstlisting} +class Stream[a] = List[a] + +module Stream { + def concat(xss: Stream[Stream[a]]): Stream[a] = { + let result: Stream[a] = xss match { + case [] => [] + case [] :: xss1 => concat(xss1) + case (x :: xs) :: xss1 => x :: concat(xs :: xss1) + } + result + } +} +\end{lstlisting} +} +\comment{ +\chapter{Implementing Abstract Types: Search Trees} + +This chapter presents unbalanced binary search trees, implemented in +three different styles: algebraic, object-oriented, and imperative. +In each case, a search tree package is seen as an implementation +of a class {\em MapStruct}. +\begin{lstlisting} +abstract class MapStruct[kt, vt] { + abstract type Map extends kt => vt { + def apply(key: kt): vt; + def extend(key: kt, value: vt): Map; + def remove(key: kt): Map; + def domain: Stream[kt]; + def range: Stream[vt]; + } + def empty: Map; +} +\end{lstlisting} +The \code{MapStruct} class is parameterized with a type of keys +\code{kt} and a type of values \code{vt}. It +specifies an abstract type \code{Map} and an abstract value +\code{empty}, which represents empty maps. Every implementation +\code{Map} needs to conform to that abstract type, which +extends the function type \code{kt => vt} +with four new +methods. The method \code{domain} yields a stream that enumerates the +map's domain, i.e. the set of keys that are mapped to non-null values. +The method \code{range} yields a stream that enumerates the function's +range, i.e.\ the values obtained by applying the function to arguments +in its domain. The method +\code{extend} extends the map with a given key/value binding, whereas +\code{remove} removes a given key from the map's domain. Both +methods yield a new map value as result, which has the same +representation as the receiver object. + +\begin{figure}[t] +\begin{lstlisting} +class AlgBinTree[kt extends Ord, vt] extends MapStruct[kt, vt] { + private case + Empty extends Map, + Node(key: kt, value: vt, l: Map, r: Map) extends Map + + final class Map extends kt => vt { + def apply(key: kt): vt = this match { + case Empty => null + case Node(k, v, l, r) => + if (key < k) l.apply(key) + else if (key > k) r.apply(key) + else v + } + + def extend(key: kt, value: vt): Map = this match { + case Empty => Node(k, v, Empty, Empty) + case Node(k, v, l, r) => + if (key < k) Node(k, v, l.extend(key, value), r) + else if (key > k) Node(k, v, l, r.extend(key, value)) + else Node(k, value, l, r) + } + + def remove(key: kt): Map = this match { + case Empty => Empty + case Node(k, v, l, r) => + if (key < k) Node(k, v, l.remove(key), r) + else if (key > k) Node(k, v, l, r.remove(key)) + else if (l == Empty) r + else if (r == Empty) l + else { + val midKey = r.domain.head + Node(midKey, r.apply(midKey), l, r.remove(midKey)) + } + } + + def domain: Stream[kt] = this match { + case Empty => [] + case Node(k, v, l, r) => Stream.concat([l.domain, [k], r.domain]) + } + def range: Stream[vt] = this match { + case Empty => [] + case Node(k, v, l, r) => Stream.concat([l.range, [v], r.range]) + } + } + def empty: Map = Empty +} +\end{lstlisting} +\caption{\label{fig:algbintree}Algebraic implementation of binary +search trees} +\end{figure} +We now present three implementations of \code{Map}, which are all +based on binary search trees. The \code{apply} method of a map is +implemented in each case by the usual search function over binary +trees, which compares a given key with the key stored in the topmost +tree node, and depending on the result of the comparison, searches the +left or the right hand sub-tree. The type of keys must implement the +\code{Ord} class, which contains comparison methods +(see Chapter~\ref{chap:classes} for a definition of class \code{Ord}). + +The first implementation, \code{AlgBinTree}, is given in +Figure~\ref{fig:algbintree}. It represents a map with a +data type \code{Map} with two cases, \code{Empty} and \code{Node}. + +Every method of \code{AlgBinTree[kt, vt].Map} performs a pattern +match on the value of +\code{this} using the \code{match} method which is defined as postfix +function application in class \code{Object} (\sref{sec:class-object}). + +The functions \code{domain} and \code{range} return their results as +lazily constructed lists. The \code{Stream} class is an alias of +\code{List} which should be used to indicate the fact that its values +are constructed lazily. + +\begin{figure}[thb] +\begin{lstlisting} +class OOBinTree[kt extends Ord, vt] extends MapStruct[kt, vt] { + abstract class Map extends kt => vt { + def apply(key: kt): v + def extend(key: kt, value: vt): Map + def remove(key: kt): Map + def domain: Stream[kt] + def range: Stream[vt] + } + module empty extends Map { + def apply(key: kt) = null + def extend(key: kt, value: vt) = Node(key, value, empty, empty) + def remove(key: kt) = empty + def domain = [] + def range = [] + } + private class Node(k: kt, v: vt, l: Map, r: Map) extends Map { + def apply(key: kt): vt = + if (key < k) l.apply(key) + else if (key > k) r.apply(key) + else v + def extend(key: kt, value: vt): Map = + if (key < k) Node(k, v, l.extend(key, value), r) + else if (key > k) Node(k, v, l, r.extend(key, value)) + else Node(k, value, l, r) + def remove(key: kt): Map = + if (key < k) Node(k, v, l.remove(key), r) + else if (key > k) Node(k, v, l, r.remove(key)) + else if (l == empty) r + else if (r == empty) l + else { + val midKey = r.domain.head + Node(midKey, r(midKey), l, r.remove(midKey)) + } + def domain: Stream[kt] = Stream.concat([l.domain, [k], r.domain] ) + def range: Stream[vt] = Stream.concat([l.range, [v], r.range]) + } +} +\end{lstlisting} +\caption{\label{fig:oobintree}Object-oriented implementation of binary +search trees} +\end{figure} + +The second implementation of maps is given in +Figure~\ref{fig:oobintree}. Class \code{OOBinTree} implements the +type \code{Map} with a module \code{empty} and a class +\code{Node}, which define the behavior of empty and non-empty trees, +respectively. + +Note the different nesting structure of \code{AlgBinTree} and +\code{OOBinTree}. In the former, all methods form part of the base +class \code{Map}. The different behavior of empty and non-empty trees +is expressed using a pattern match on the tree itself. In the +latter, each subclass of \code{Map} defines its own set of +methods, which override the methods in the base class. The pattern +matches of the algebraic implementation have been replaced by the +dynamic binding that comes with method overriding. + +Which of the two schemes is preferable depends to a large degree on +which extensions of the type are anticipated. If the type is later +extended with a new alternative, it is best to keep methods in each +alternative, the way it was done in \code{OOBinTree}. On the other +hand, if the type is extended with additional methods, then it is +preferable to keep only one implementation of methods and to rely on +pattern matching, since this way existing subclasses need not be +modified. + +\begin{figure} +\begin{lstlisting} +class MutBinTree[kt extends Ord, vt] extends MapStruct[kt, vt] { + class Map(key: kt, value: vt) extends kt => vt { + val k = key + var v = value + var l = empty, r = empty + + def apply(key: kt): vt = + if (this eq empty) null + else if (key < k) l.apply(key) + else if (key > k) r.apply(key) + else v + + def extend(key: kt, value: vt): Map = + if (this eq empty) Map(key, value) + else { + if (key < k) l = l.extend(key, value) + else if (key > k) r = r.extend(key, value) + else v = value + this + } + + def remove(key: kt): Map = + if (this eq empty) this + else if (key < k) { l = l.remove(key) ; this } + else if (key > k) { r = r.remove(key) ; this } + else if (l eq empty) r + else if (r eq empty) l + else { + var mid = r + while (!(mid.l eq empty)) { mid = mid.l } + mid.r = r.remove(mid.k) + mid.l = l + mid + } + + def domain: Stream[kt] = Stream.concat([l.domain, [k], r.domain]) + def range: Stream[vt] = Stream.concat([l.range, [v], r.range]) + } + let empty = new Map(null, null) +} +\end{lstlisting} +\caption{\label{fig:impbintree}Side-effecting implementation of binary +search trees} +\end{figure} + +The two versions of binary trees presented so far are {\em +persistent}, in the sense that maps are values that cannot be changed +by side effects. By contrast, in the next implementation of binary +trees, the implementations of \code{extend} and +\code{remove} do have an effect on the state of their receiver +object. This corresponds to the way binary trees are usually +implemented in imperative languages. The new implementation can lead +to some savings in computing time and memory allocation, but care is +required not to use the original tree after it has been modified by a +side-effecting operation. + +In this implementation, \code{value}, \code{l} and \code{r} are +variables that can be affected by method calls. The +class \code{MutBinTree[kt, vt].Map} takes two instance parameters +which define the \code{key} value and the initial value of the +\code{value} variable. Empty trees are represented by a +value \code{empty}, which has \code{null} (signifying undefined) in +both its key and value fields. Note that this value needs to be +defined lazily using \code{let} since its definition involves the +creation of a +\code{Map} object, +which accesses \code{empty} recursively as part of its initialization. +All methods test first whether the current tree is empty using the +reference equality operator \code{eq} (\sref{sec:class-object}). + +As a program using the \code{MapStruct} abstraction, consider a function +which creates a map from strings to integers and then applies it to a +key string: +\begin{lstlisting} +def mapTest(def mapImpl: MapStruct[String, int]): int = { + val map: mapImpl.Map = mapImpl.empty.extend("ab", 1).extend("bx", 3) + val x = map("ab") // returns 1 +} +\end{lstlisting} +The function is parameterized with the particular implementation of +\code{MapStruct}. It can be applied to any one of the three implementations +described above. E.g.: +\begin{lstlisting} +mapTest(AlgBinTree[String, int]) +mapTest(OOBinTree[String, int]) +mapTest(MutBinTree[String, int]) +\end{lstlisting} +} +\chapter{Programming with Higher-Order Functions: Combinator Parsing} + +In this chapter we describe how to write combinator parsers in +Scala. Such parsers are constructed from predefined higher-order +functions, so called parser combinators, that closely model the +constructions of an EBNF grammar \cite{ebnf}. + +As running example, we consider parsers for arithmetic expressions +described by the following context-free grammar. +\bda{p{3cm}cp{10cm}} +letter &::=& /* all letters */ \\ +digit &::=& /* all digits */ \\[0.5em] +ident &::=& letter \{letter $|$ digit \}\\ +number &::=& digit \{digit\}\\[0.5em] + +expr &::=& expr1 \{`+' expr1 $|$ `$-$' expr1\}\\ +expr1 &::=& expr2 \{`*' expr2 $|$ `/' expr2\}\\ +expr2 &::=& ident $|$ number $|$ `(' expr `)' +\eda + +\section{Simple Combinator Parsing} + +In this section we will only be concerned with the task of recognizing +input strings, not with processing them. So we can describe parsers +by the sets of input strings they accept. There are two +fundamental operators over parsers: +\code{&&&} expresses the sequential composition of a parser with +another, while \code{|||} expresses an alternative. These operations +will both be defined as methods of a \code{Parser} class. We will +also define constructors for the following primitive parsers: + +\begin{quote}\begin{tabular}{ll} +\code{empty} & The parser that accepts the empty string +\\ +\code{fail} & The parser that accepts no string +\\ +\code{chr} & The parser that accepts any character. +\\ +\code{chr(c: char)} + & The parser that accepts the single-character string ``$c$''. +\\ +\code{chrWith(p: char => boolean)} + & The parser that accepts single-character strings + ``$c$'' \\ + & for which $p(c)$ is true. +\end{tabular}\end{quote} + +There are also the two higher-order parser combinators \code{opt}, +expressing optionality and \code{rep}, expressing repetition. +For any parser $p$, \code{opt(}$p$\code{)} yields a parser that +accepts the strings accepted by $p$ or else the empty string, while +\code{rep(}$p$\code{)} accepts arbitrary sequences of the strings accepted by +$p$. In EBNF, \code{opt(}$p$\code{)} corresponds to $[p]$ and +\code{rep(}$p$\code{)} corresponds to $\{p\}$. + +The central idea of parser combinators is that parsers can be produced +by a straightforward rewrite of the grammar, replacing \code{::=} with +\code{=}, sequencing with +\code{&&&}, choice +\code{|} with \code{|||}, repetition \code{\{...\}} with +\code{rep(...)} and optional occurrence with \code{[...]}. +Applying this process to the grammar of arithmetic +expressions yields: +\begin{lstlisting} +module ExprParser { + import Parse; + + def letter = chrWith(c => c.isLetter); + def digit = chrWith(c => c.isDigit); + + def ident = letter &&& rep(letter ||| digit); + def number = digit &&& rep(digit); + + def expr:Parser = expr1 &&& rep((chr('+') &&& expr1) ||| (chr('-') &&& expr1)); + def expr1 = expr2 &&& rep((chr('*') &&& expr2) ||| (chr('/') &&& expr2)); + def expr2 = ident ||| number ||| (chr('(') &&& expr &&& chr(')')); +} +\end{lstlisting} +It remains to explain how to implement a library with the combinators +described above. We will pack combinators and their underlying +implementation in a module \code{Parse}. The first question to decide +is which underlying representation type to use for a parser. We treat +parsers here as functions that take a list of characters as input +parameter and that yield a parse result. +\begin{lstlisting} +module Parse { + type Result = Option[List[char]]; + abstract class Parser extends Function1[List[char],Result] { +\end{lstlisting} +\comment{ +The \code{Option} type is predefined as follows. +\begin{lstlisting} +abstract final class Option[a]; +case class None[a] extends Option[a]; +case class Some[a](x: a) extends Option[a]; +\end{lstlisting} +} +A parser returns either the constant \code{None}, which +signifies that the parser did not recognize a legal input string, or +it returns a value \code{Some(in1)} where \code{in1} represents that +part of the input list that the parser did not consume. + +Parsers are instances of functions from \code{List[char]} to +\code{Parse.Result}, which also implement the combinators +for sequence and alternative. This is modeled by +defining \code{Parser} as a class that extends type +\code{Function1[List[char],Result]} and that defines an \code{apply} +method, as well as methods \code{&&&} and \code{|||}. +\begin{lstlisting} + abstract def apply(in: List[char]): Result; +\end{lstlisting} +\begin{lstlisting} + def &&& (def p: Parser) = new Parser { + def apply(in: List[char]) = outer.apply(in) match { + case Some(in1) => p(in1) + case n => n + } + } + def ||| (def p: Parser) = new Parser { + def apply(in: List[char]) = outer.apply(in) match { + case None => p(in) + case s => s + } + } + } +\end{lstlisting} +The implementations of the primitive parsers \code{empty}, \code{fail}, +\code{chrWith} and \code{chr} are as follows. +\begin{lstlisting} + def empty = new Parser { def apply(in: List[char]) = Some(in) } + + def fail = new Parser { def apply(in: List[char]) = None[List[char]] } + + def chrWith(p: char => boolean) = new Parser { + def apply(in: List[char]) = in match { + case [] => None[List[char]] + case (c :: in1) => if (p(c)) Some(in1) else None[List[char]] + } + } + + def chr(c: char): Parser = chrWith(d => d == c); +\end{lstlisting} +The higher-order parser combinators \code{opt} and \code{rep} can be +defined in terms of the combinators for sequence and alternative: +\begin{lstlisting} + def opt(p: Parser): Parser = p ||| empty; + def rep(p: Parser): Parser = opt(rep1(p)); + def rep1(p: Parser): Parser = p &&& rep(p); +} // end Parser +\end{lstlisting} +This is all that's needed. Parsers such as the one for arithmetic +expressions given above can now be composed from these building +blocks. These parsers need not refer to the underlying implementation of +parsers as functions from input lists to parse results. + +The presented combinator parsers use backtracking to change from one +alternative to another. If one restricts the focus to LL(1) grammars, +a non-backtracking implementation of parsers is also possible. This +implementation can then be based on iterators instead of lists. + +\section{\label{sec:parsers-results}Parsers that Return Results} + +The combinator library of the previous section does not support the +generation of output from parsing. But usually one does not just want +to check whether a given string belongs to the defined language, one +also wants to convert the input string into some internal +representation such as an abstract syntax tree. + +In this section, we modify our parser library to build parsers that +produce results. We will make use of the for-comprehensions introduced +in Chapter~\ref{sec:for-notation}. The basic combinator of sequential +composition, formerly \code{p &&& q}, now becomes +\begin{lstlisting} +for (val x <- p; val y <- q) yield e +\end{lstlisting}. +Here, the names \code{x} and \code{y} are bound to the results of +executing the parsers \code{p} and \code{q}. \code{e} is an expression +that uses these results to build the tree returned by the composed +parser. + +Before describing the implementation of the new parser combinators, we +explain how the new building blocks are used. Say we want to modify +our arithmetic expression parser so that it returns an abstract syntax +tree of the parsed expression. The class of syntax trees is given by: +\begin{lstlisting} +abstract class Tree; +case class Var(n: String) extends Tree; +case class Num(n: int) extends Tree; +case class Binop(op: char, l: Tree, r: Tree) extends Tree; +\end{lstlisting} +That is, a syntax tree is a named variable, an integer number, or a +binary operation with two operand trees and a character indicating the +operation. + +As a first step towards parsers that produce syntax trees, we need to +modify the ``micro-syntax'' parsers \code{letter}, \code{digit}, +\code{ident} and \code{number} so that they return representations of +the parsed input: +\begin{lstlisting} +def letter: Parser[char] = chrWith(c => c.isLetter); +def digit : Parser[char] = chrWith(c => c.isDigit); + +def ident: Parser[String] = + for (val c <- letter; val cs <- rep(letter ||| digit)) + yield ((c :: cs) foldr "") {c, s => c+ s}; + +def number: Parser[int] = + for (val d <- digit; val ds <- rep(digit)) + yield ((d - '0') :_foldl ds) {x, y => x * 10 + (y - '0')}; +\end{lstlisting} +The \code{letter} and \code{digit} parsers simply return the letter +that was parsed. The \code{ident} and \code{number} parsers return the +string, respectively integer number that was parsed. In both cases, +sub-parsers are applied in a for-comprehension and their results are +embedded in the result of the calling parser. The remainder of the +parser for arithmetic expressions follows the same scheme. +\begin{lstlisting} +def expr: Parser[Tree] = + for { + val e1 <- expr1; + val es <- rep ( + for { + val op <- chr('+') ||| chr('-'); + val e <- expr1 + } yield (x => Binop(op, x, e)) : Tree => Tree + ) + } yield applyAll(es, e1); +\end{lstlisting} +\begin{lstlisting} +def expr1: Parser[Tree] = + for { + val e1 <- expr2; + val es <- rep ( + for { + val op <- chr('*') ||| chr('/'); + val e <- expr2 + } yield (x => Binop(op, x, e)) : Tree => Tree + ) + } yield applyAll(es, e1); +\end{lstlisting} +\begin{lstlisting} +def expr2: Parser[Tree] = { + ( for { val n <- ident } yield Var(n) : Tree ) + ||| ( for { val n <- number } yield Num(n) : Tree ) + ||| ( for { val _ <- chr('('); val e <- expr; val _ <- chr(')') } yield e ); +} +\end{lstlisting} +Note the treatment of the repetitions in \code{expr} and +\code{expr1}. The parser for an expression suffix $op;e$ consisting of an +operator $op$ and an expression $e$ returns a function, which, given a +left operand expression $d$, constructs a \code{Binop} node that +represents $d;op;e$. The \code{rep} parser combinator forms a list of +all these functions. The final \code{yield} part applies all functions +to the first operand in the sequence, which is represented by +\code{e1}. Here \code{applyAll} applies the list of functions passed as its first +argument to its second argument. It is defined as follows. +\begin{lstlisting} +def applyAll[a](fs: List[a => a], e: a): a = + (e :_foldl fs) { x, f => f(x) } +\end{lstlisting} +We now present the parser combinators that support the new +scheme. Parsers that succeed now return a parse result besides the +un-consumed input. +\begin{lstlisting} +module Parse { + type Result[a] = Option[(a, List[char])] +\end{lstlisting} +Parsers are parameterized with the type of their result. The class +\code{Parser[a]} now defines new methods \code{map}, \code{flatMap} +and \code{filter}. The \code{for} expressions are mapped by the +compiler to calls of these functions using the scheme described in +Chapter~\ref{sec:for-notation}. + +Here is the complete definition of the new \code{Parser} class. +\begin{lstlisting} + abstract class Parser[a] extends Function1[List[char],Result[a]] { + + def apply(in: List[char]): Result[a]; + + def filter(p: a => boolean) = new Parser[a] { + def apply(in: List[char]): Result[a] = outer.apply(in) match { + case Some((x, in1)) => if (p(x)) Some((x, in1)) else None + case None => None + } + } + + def map[b](f: a => b) = new Parser[b] { + def apply(in: List[char]): Result[b] = outer.apply(in) match { + case Some((x, in1)) => Some((f(x), in1)) + case None => None + } + } + + def flatMap[b](f: a => Parser[b]) = new Parser[b] { + def apply(in: List[char]): Result[b] = outer.apply(in) match { + case Some((x, in1)) => f(x)(in1) + case None => None + } + } + + def ||| (def p: Parser[a]) = new Parser[a] { + def apply(in: List[char]): Result[a] = outer.apply(in) match { + case None => p(in) + case s => s + } + } + + def &&& [b](def p: Parser[b]): Parser[b] = + for (val _ <- this; val result <- p) yield result; + } +\end{lstlisting} + +The \code{filter} method takes as parameter a predicate $p$ which it +applies to the results of the current parser. If the predicate is +false, the parser fails by returning \code{None}; otherwise it returns +the result of the current parser. The \code{map} method takes as +parameter a function $f$ which it applies to the results of the +current parser. The \code{flatMap} tales as parameter a function +\code{f} which returns a parser. It applies \code{f} to the result of +the current parser and then continues with the resulting parser. The +\code{|||} method is essentially defined as before. The +\code{&&&} method can now be defined in terms of \code{for}. + +% Here is the code for fail, chrWith and chr +% +%\begin{lstlisting} +% def fail[a] = new Parser[a] { def apply(in: List[char]) = None[(a,List[char])] } +% +% def chrWith(p: char => boolean) = new Parser[char] { +% def apply(in: List[char]) = in match { +% case [] => None[(char,List[char])] +% case (c :: in1) => if (p(c)) Some((c,in1)) else None[(char,List[char])] +% } +% } +% +% def chr(c: char): Parser[char] = chrWith(d => d == c); +%\end{lstlisting} +The primitive parser \code{succeed} replaces \code{empty}. It consumes +no input and returns its parameter as result. +\begin{lstlisting} + def succeed[a](x: a) = new Parser[a] { + def apply(in: List[char]) = Some((x, in)) + } +\end{lstlisting} +The \code{fail} parser is as before. The parser combinators +\code{rep} and \code{opt} now also return results. \code{rep} returns +a list which contains as elements the results of each iteration of its +sub-parser. \code{opt} returns an +\code{Option} type which indicates whether something was recognized by +its sub-parser. +\begin{lstlisting} + def rep[a](p: Parser[a]): Parser[List[a]] = + rep1(p) ||| succeed([]); + + def rep1[a](p: Parser[a]): Parser[List[a]] = + for (val x <- p; val xs <- rep(p)) yield x :: xs; + + def opt[a](p: Parser[a]): Parser[Option [a]] = + { for (val x <- p) yield (Some(x): Option[a]) } ||| succeed((None: Option[a])); +} // end Parse +\end{lstlisting} + +\chapter{\label{sec:hm}Programming with Patterns: Hindley/Milner Type Inference} + +This chapter demonstrates Scala's data types and pattern matching by +developing a type inference system in the Hindley/Milner style. The +source language for the type inferencer is lambda calculus with a let +construct. Abstract syntax trees for the source language are +represented by the following data type of \code{Terms}. +\begin{lstlisting} +abstract class Term; +case class Var(x: String) extends Term; +case class Lam(x: String, e: Term) extends Term; +case class App(f: Term, e: Term) extends Term; +case class Let(x: String, e: Term, f: Term) extends Term; +\end{lstlisting} +There are four tree constructors: \code{Var} for variables, \code{Lam} +for function abstractions, \code{App} for function applications, and +\code{Let} for let expressions. Note that these tree constructors are +defined outside the \code{Term} class. It would also be possible +to define further constructors for this type in other parts of the +program. + +The next data type describes the form of types that are +computed by the inference system. +\begin{lstlisting} +module Types { + abstract final class Type; + case class Tyvar(a: String) extends Type; + case class Arrow(t1: Type, t2: Type) extends Type; + case class Tycon(k: String, ts: List[Type]) extends Type; + private var n: int = 0; + def newTyvar: Type = { n = n + 1 ; Tyvar("a" + n) } +} +import Types; +\end{lstlisting} +There are three type constructors: \code{Tyvar} for type variables, +\code{Arrow} for function types and \code{Tycon} for type +constructors such as \code{boolean} or \code{List}. Type constructors +have as component a list of their type parameters. This list is empty +for type constants such as \code{boolean}. The data type is packaged +in a module \code{Types}. Also contained in that module is a function +\code{newTyvar} which creates a fresh type variable each time it is +called. The module definition is followed by an import clause +\code{import Types}, which makes the non-private members of +this module available without qualification in the code that follows. + +Note that \code{Type} is a \code{final} class. This means that no +subclasses or data constructors that extend \code{Type} can be formed +except for the three constructors that follow the class. This makes +\code{Type} into a {\em closed} algebraic data type with a fixed +number of alternatives. By contrast, type \code{Term} is an {\em open} +algebraic type for which further alternatives can be defined. + +The next data type describes type schemes, which consist of a type and +a list of names of type variables which appear universally quantified +in the type scheme. For instance, the type scheme $\forall a\forall +b.a \arrow b$ would be represented in the type checker as: +\begin{lstlisting} +TypeScheme(["a", "b"], Arrow(Tyvar("a"), Tyvar("b"))) . +\end{lstlisting} +The data type definition of type schemes does not carry an extends +clause; this means that type schemes extend directly class +\code{Object}. +Even though there is only one possible way to construct a type scheme, +a \code{case class} representation was chosen since it offers a convenient +way to decompose a type scheme into its parts using pattern matching. +\begin{lstlisting} +case class TypeScheme(ls: List[String], t: Type) { + def newInstance: Type = { + val instSubst = + ((EmptySubst: Subst) :_foldl ls) { s, a => s.extend(Tyvar(a), newTyvar) } + instSubst(t) + } +} +\end{lstlisting} +Type scheme objects come with a method \code{newInstance}, which +returns the type contained in the scheme after all universally type +variables have been renamed to fresh variables. + +The next class describes substitutions. A substitution is an +idempotent function from type variables to types. It maps a finite +number of given type variables to given types, and leaves all other +type variables unchanged. The meaning of a substitution is extended +point-wise to a mapping from types to types. + +\begin{lstlisting} +abstract class Subst extends Function1[Type,Type] { + def lookup(x: Tyvar): Type; + def apply(t: Type): Type = t match { + case Tyvar(a) => val u = lookup(Tyvar(a)); if (t == u) t else apply(u); + case Arrow(t1, t2) => Arrow(apply(t1), apply(t2)) + case Tycon(k, ts) => Tycon(k, ts map apply) + } + def extend(x: Tyvar, t: Type) = new Subst { + def lookup(y: Tyvar): Type = if (x == y) t else outer.lookup(y); + } +} +case class EmptySubst extends Subst { def lookup(t: Tyvar): Type = t } +\end{lstlisting} +We represent substitutions as functions, of type +\code{Type => Type}. To be an instance of this type, a +substitution \code{s} has to implement an \code{apply} method that takes a +\code{Type} as argument and yields another \code{Type} as result. A function +application \code{s(t)} is then interpreted as \code{s.apply(t)}. + +The \code{lookup} method is abstract in class \code{Subst}. Concrete +substitutions are defined by the case class \code{EmptySubst} and the +method \code{extend} in class \code{Subst}. + +The next class gives a naive implementation of sets using lists as the +implementation type. It implements methods \code{contains} for +membership tests as well as \code{union} and \code{diff} for set union +and difference. Alternatively, one could have used a more efficient +implementation of sets in some standard library. +\begin{lstlisting} +class ListSet[a](xs: List[a]) { + val elems: List[a] = xs; + + def contains(y: a): boolean = xs match { + case [] => false + case x :: xs1 => (x == y) || (xs1 contains y) + } + + def union(ys: ListSet[a]): ListSet[a] = xs match { + case [] => ys + case x :: xs1 => + if (ys contains x) ListSet(xs1) union ys + else ListSet(x :: (ListSet(xs1) union ys).elems) + } + + def diff(ys: ListSet[a]): ListSet[a] = xs match { + case [] => ListSet([]) + case x :: xs1 => + if (ys contains x) ListSet(xs1) diff ys + else ListSet(x :: (ListSet(xs1) diff ys).elems) + } +} +\end{lstlisting} + +We now present the type checker module. The type checker +computes a type for a given term in a given environment. Environments +associate variable names with type schemes. They are represented by a +type alias \code{Env} in module \code{TypeChecker}: +\begin{lstlisting} +module TypeChecker { + + /** Type environments are lists of bindings that associate a + * name with a type scheme. + */ + type Env = List[(String, TypeScheme)]; +\end{lstlisting} +There is also an exception \code{TypeError}, which is thrown when type +checking fails. Exceptions are modeled as case classes that inherit +from the predefined \code{Exception} class. +\begin{lstlisting} + case class TypeError(msg: String) extends Exception(msg); +\end{lstlisting} +The \code{Exception} class defines a \code{throw} method which causes +the exception to be thrown. + +The \code{TypeChecker} module contains several utility +functions. Function +\code{tyvars} yields the set of free type variables of a type, +of a type scheme, of a list of types, or of an environment. Its +implementation is as four overloaded functions, one for each type of +argument. +\begin{lstlisting} + def tyvars(t: Type): ListSet[String] = t match { + case Tyvar(a) => new ListSet([a]) + case Arrow(t1, t2) => tyvars(t1) union tyvars(t2) + case Tycon(k, ts) => tyvars(ts) + } + def tyvars(ts: TypeScheme): ListSet[String] = ts match { + case TypeScheme(as, t) => tyvars(t) diff new ListSet(as) + } + def tyvars(ts: List[Type]): ListSet[String] = ts match { + case [] => new ListSet[String]([]) + case t :: ts1 => tyvars(t) union tyvars(ts1) + } + def tyvars(env: Env): ListSet[String] = env match { + case [] => new ListSet[String]([]) + case (x, t) :: env1 => tyvars(t) union tyvars(env1) + } +\end{lstlisting} +The next utility function, \code{lookup}, returns the type scheme +associated with a given variable name in the given environment, or +returns \code{null} if no binding for the variable exists in the environment. +\begin{lstlisting} + def lookup(env: Env, x: String): TypeScheme = env match { + case [] => null + case (y, t) :: env1 => if (x == y) t else lookup(env1, x) + } +\end{lstlisting} +The next utility function, \code{gen}, returns the type scheme that +results from generalizing a given type in a given environment. This +means that all type variables that occur in the type but not in the +environment are universally quantified. +\begin{lstlisting} + def gen(env: Env, t: Type): TypeScheme = + TypeScheme((tyvars(t) diff tyvars(env)).elems, t); +\end{lstlisting} +The next utility function, \code{mgu}, computes the most general +unifier of two given types $t$ and $u$ under a pre-existing +substitution $s$. That is, it returns the most general +substitution $s'$ which extends $s$, and which makes $s'(t)$ and +$s'(u)$ equal types. The function throws a \code{TypeError} exception +if no such substitution exists. This can happen because the two types +have different type constructors at corresponding places, or because +a type variable is unified with a type that contains the type variable +itself. +\begin{lstlisting} + def mgu(t: Type, u: Type)(s: Subst): Subst = (s(t), s(u)) match { + case (Tyvar( a), Tyvar(b)) if a == b => + s + case (Tyvar(a), _) => + if (tyvars(u) contains a) + TypeError("unification failure: occurs check").throw + else s.extend(Tyvar(a), u) + case (_, Tyvar(a)) => + mgu(u, t)(s) + case (Arrow(t1, t2), Arrow(u1, u2)) => + mgu(t1, u1)(mgu(t2, u2)(s)) + case (Tycon(k1, ts), Tycon(k2, us)) if k1 == k2 => + (s :_foldl ((ts zip us) map (case (t,u) => mgu(t,u)))) { s, f => f(s) } + case _ => TypeError("unification failure").throw + } +\end{lstlisting} +The main task of the type checker is implemented by function +\code{tp}. This function takes as first parameters an environment $env$, a +term $e$ and a proto-type $t$. As a second parameter it takes a +pre-existing substitution $s$. The function yields a substitution +$s'$ that extends $s$ and that +turns $s'(env) \ts e: s'(t)$ into a derivable type judgment according +to the derivation rules of the Hindley/Milner type system \cite{hindley-milner}. A +\code{TypeError} exception is thrown if no such substitution exists. +\begin{lstlisting} + def tp(env: Env, e: Term, t: Type)(s: Subst): Subst = e match { + case Var(x) => { + val u = lookup(env, x); + if (u == null) TypeError("undefined: x").throw + else mgu(u.newInstance, t)(s) + } + case Lam(x, e1) => { + val a = newTyvar, b = newTyvar; + val s1 = mgu(t, Arrow(a, b))(s); + val env1 = (x, TypeScheme([], a)) :: env; + tp(env1, e1, b)(s1) + } + case App(e1, e2) => { + val a = newTyvar; + val s1 = tp(env, e1, Arrow(a, t))(s); + tp(env, e2, a)(s1) + } + case Let(x, e1, e2) => { + val a = newTyvar; + val s1 = tp(env, e1, a)(s); + tp((x, gen(env, s1(a))) :: env, e2, t)(s1) + } + } +\end{lstlisting} +The next function, \code{typeOf} is a simplified facade for +\code{tp}. It computes the type of a given term $e$ in a given +environment $env$. It does so by creating a fresh type variable \verb$a$, +computing a typing substitution that makes \code{env $\ts$ e: a} into +a derivable type judgment, and finally by returning the result of +applying the substitution to $a$. +\begin{lstlisting} + def typeOf(env: Env, e: Term): Type = { + val a = newTyvar; + tp(env, e, a)(EmptySubst)(a) + } +} +\end{lstlisting} +This concludes the presentation of the type inference system. +To apply the system, it is convenient to have a predefined environment +that contains bindings for commonly used constants. The module +\code{Predefined} defines an environment \code{env} that contains +bindings for booleans, numbers and lists together with some primitive +operations over these types. It also defines a fixed point operator +\code{fix}, which can be used to represent recursion. +\begin{lstlisting} +module Predefined { + val booleanType = Tycon("Boolean", []); + val intType = Tycon("Int", []); + def listType(t: Type) = Tycon("List", [t]); + + private def gen(t: Type): TypeScheme = TypeChecker.gen([], t); + private val a = newTyvar; + val env = [ + ("true", gen(booleanType)), + ("false", gen(booleanType)), + ("$\mbox{\prog{if}}$", gen(Arrow(booleanType, Arrow(a, Arrow(a, a))))), + ("zero", gen(intType)), + ("succ", gen(Arrow(intType, intType))), + ("$\mbox{\prog{nil}}$", gen(listType(a))), + ("cons", gen(Arrow(a, Arrow(listType(a), listType(a))))), + ("isEmpty", gen(Arrow(listType(a), booleanType))), + ("head", gen(Arrow(listType(a), a))), + ("tail", gen(Arrow(listType(a), listType(a)))), + ("fix", gen(Arrow(Arrow(a, a), a))) + ]; +} +\end{lstlisting} +Here's an example how the type inferencer is used. +Let's define a function \code{showType} which returns the type of +a given term computed in the predefined environment +\code{Predefined.env}: +\begin{lstlisting} +> def showType(e: Term) = TypeChecker.typeOf(Predefined.env, e); +\end{lstlisting} +Then the application +\begin{lstlisting} +> showType(Lam("x", App(App(Var("cons"), Var("x")), Var("$\mbox{\prog{nil}}$")))); +\end{lstlisting} +would give the response +\begin{lstlisting} +> TypeScheme([a0], Arrow(Tyvar(a0), Tycon("List", [Tyvar(a0)]))); +\end{lstlisting} + +\exercise +Add \code{toString} methods to the data constructors of class +\code{Type} and \code{TypeScheme} which represent types in a more +natural way. + +\chapter{Abstractions for Concurrency}\label{sec:ex-concurrency} + +This section reviews common concurrent programming patterns and shows +how they can be implemented in Scala. + +\section{Signals and Monitors} + +\example +The {\em monitor} provides the basic means for mutual exclusion +of processes in Scala. It is defined as follows. +\begin{lstlisting} +class Monitor { + def synchronized [a] (def e: a): a; +} +\end{lstlisting} +The \code{synchronized} method in class \code{Monitor} executes its +argument computation \code{e} in mutual exclusive mode -- at any one +time, only one thread can execute a \code{synchronized} argument of a +given monitor. + +Threads can suspend inside a monitor by waiting on a signal. The +\code{Signal} class offers two methods \code{send} and +\code{wait}. Threads that call the \code{wait} method wait until a +\code{send} method of the same signal is called subsequently by some +other thread. Calls to \code{send} with no threads waiting for the +signal are ignored. Here is the specification of the \code{Signal} +class. +\begin{lstlisting} +class Signal { + def wait: unit; + def wait(msec: long): unit; + def notify: unit; + def notifyAll: unit; +} +\end{lstlisting} +A signal also implements a timed form of \code{wait}, which blocks +only as long as no signal was received or the specified amount of time +(given in milliseconds) has elapsed. Furthermore, there is a +\code{notifyAll} method which unblocks all threads which wait for the +signal. \code{Signal} and \code{Monitor} are primitive classes in +Scala which are implemented in terms of the underlying runtime system. + +As an example of how monitors and signals are used, here is is an +implementation of a bounded buffer class. +\begin{lstlisting} +class BoundedBuffer[a](N: int) extends Monitor { + var in = 0, out = 0, n = 0; + val elems = new Array[a](N); + val nonEmpty = new Signal; + val nonFull = new Signal; +\end{lstlisting} +\begin{lstlisting} + def put(x: a) = synchronized { + if (n == N) nonFull.wait; + elems(in) = x ; in = (in + 1) % N ; n = n + 1; + if (n == 1) nonEmpty.send; + } +\end{lstlisting} +\begin{lstlisting} + def get: a = synchronized { + if (n == 0) nonEmpty.wait + val x = elems(out) ; out = (out + 1) % N ; n = n - 1; + if (n == N - 1) nonFull.send; + x + } +} +\end{lstlisting} +And here is a program using a bounded buffer to communicate between a +producer and a consumer process. +\begin{lstlisting} +val buf = new BoundedBuffer[String](10) +fork { while (true) { val s = produceString ; buf.put(s) } } +fork { while (true) { val s = buf.get ; consumeString(s) } } +\end{lstlisting} +The \code{fork} method spawns a new thread which executes the +expression given in the parameter. It can be defined as follows. +\begin{lstlisting} +def fork(def e: unit) = { + val p = new Thread { def run = e; } + p.run +} +\end{lstlisting} + +\comment{ +\section{Logic Variable} + +A logic variable (or lvar for short) offers operations \code{:=} +and \code{value} to define the variable and to retrieve its value. +Variables can be \code{define}d only once. A call to \code{value} +blocks until the variable has been defined. + +Logic variables can be implemented as follows. + +\begin{lstlisting} +class LVar[a] extends Monitor { + private val defined = new Signal + private var isDefined: boolean = false + private var v: a + def value = synchronized { + if (!isDefined) defined.wait + v + } + def :=(x: a) = synchronized { + v = x ; isDefined = true ; defined.send + } +} +\end{lstlisting} +} + +\section{SyncVars} + +A synchronized variable (or syncvar for short) offers \code{get} and +\code{put} operations to read and set the variable. \code{get} operations +block until the variable has been defined. An \code{unset} operation +resets the variable to undefined state. + +Synchronized variables can be implemented as follows. +\begin{lstlisting} +class SyncVar[a] extends Monitor { + private val defined = new Signal; + private var isDefined: boolean = false; + private var value: a; + def get = synchronized { + if (!isDefined) defined.wait; + value + } + def set(x: a) = synchronized { + value = x ; isDefined = true ; defined.send; + } + def isSet: boolean = + isDefined; + def unset = synchronized { + isDefined = false; + } +} +\end{lstlisting} + +\section{Futures} +\label{sec:futures} + +A {\em future} is a value which is computed in parallel to some other +client thread, to be used by the client thread at some future time. +Futures are used in order to make good use of parallel processing +resources. A typical usage is: + +\begin{lstlisting} +val x = future(someLengthyComputation); +anotherLengthyComputation; +val y = f(x()) + g(x()); +\end{lstlisting} + +Futures can be implemented in Scala as follows. + +\begin{lstlisting} +def future[a](def p: a): unit => a = { + val result = new SyncVar[a]; + fork { result.set(p) } + (=> result.get) +} +\end{lstlisting} + +The \code{future} method gets as parameter a computation \code{p} to +be performed. The type of the computation is arbitrary; it is +represented by \code{future}'s type parameter \code{a}. The +\code{future} method defines a guard \code{result}, which takes a +parameter representing the result of the computation. It then forks +off a new thread that computes the result and invokes the +\code{result} guard when it is finished. In parallel to this thread, +the function returns an anonymous function of type \code{a}. +When called, this functions waits on the result guard to be +invoked, and, once this happens returns the result argument. +At the same time, the function reinvokes the \code{result} guard with +the same argument, so that future invocations of the function can +return the result immediately. + +\section{Parallel Computations} + +The next example presents a function \code{par} which takes a pair of +computations as parameters and which returns the results of the computations +in another pair. The two computations are performed in parallel. + +\begin{lstlisting} +def par[a, b](def xp: a, def yp: b): (a, b) = { + val y = new SyncVar[a]; + fork { y.set(yp) } + (xp, y) +} +\end{lstlisting} + +The next example presents a function \code{replicate} which performs a +number of replicates of a computation in parallel. Each +replication instance is passed an integer number which identifies it. + +\begin{lstlisting} +def replicate(start: int, end: int)(def p: int => unit): unit = { + if (start == end) { + } else if (start + 1 == end) { + p(start) + } else { + val mid = (start + end) / 2; + par ( replicate(start, mid)(p), replicate(mid, end)(p) ) + } +} +\end{lstlisting} + +The next example shows how to use \code{replicate} to perform parallel +computations on all elements of an array. + +\begin{lstlisting} +def parMap[a,b](f: a => b, xs: Array[a]): Array[b] = { + val results = new Array[b](xs.length); + replicate(0, xs.length) { i => results(i) = f(xs(i)) } + results +} +\end{lstlisting} + +\section{Semaphores} + +A common mechanism for process synchronization is a {\em lock} (or: +{\em semaphore}). A lock offers two atomic actions: \prog{acquire} and +\prog{release}. Here's the implementation of a lock in Scala: + +\begin{lstlisting} +class Lock extends Monitor with Signal { + var available = true; + def acquire = { + if (!available) wait; + available = false + } + def release = { + available = true; + notify + } +} +\end{lstlisting} + +\section{Readers/Writers} + +A more complex form of synchronization distinguishes between {\em +readers} which access a common resource without modifying it and {\em +writers} which can both access and modify it. To synchronize readers +and writers we need to implement operations \prog{startRead}, \prog{startWrite}, +\prog{endRead}, \prog{endWrite}, such that: +\begin{itemize} +\item there can be multiple concurrent readers, +\item there can only be one writer at one time, +\item pending write requests have priority over pending read requests, +but don't preempt ongoing read operations. +\end{itemize} +The following implementation of a readers/writers lock is based on the +{\em message space} concept (see Section~\ref{sec:messagespace}). + +\begin{lstlisting} +class ReadersWriters { + val m = new MessageSpace; + private case class Writers(n: int), Readers(n: int); + Writers(0); Readers(0); + def startRead = m receive { + case Writers(n) if n == 0 => m receive { + case Readers(n) => Writers(0) ; Readers(n+1); + } + } + def startWrite = m receive { + case Writers(n) => + Writers(n+1); + m receive { case Readers(n) if n == 0 => } + } +\end{lstlisting} +\begin{lstlisting} + def endRead = receive { + case Readers(n) => Readers(n-1) + } + def endWrite = receive { + case Writers(n) => Writers(n-1) ; if (n == 0) Readers(0) + } +} +\end{lstlisting} + +\section{Asynchronous Channels} + +A fundamental way of interprocess communication is the asynchronous +channel. Its implementation makes use the following class for linked +lists: +\begin{lstlisting} +class LinkedList[a](x: a) { + val elem: a = x; + var next: LinkedList[a] = null; +} +\end{lstlisting} +To facilitate insertion and deletion of elements into linked lists, +every reference into a linked list points to the node which precedes +the node which conceptually forms the top of the list. +Empty linked lists start with a dummy node, whose successor is \code{null}. + +The channel class uses a linked list to store data that has been sent +but not read yet. In the opposite direction, a signal \code{moreData} is +used to wake up reader threads that wait for data. +\begin{lstlisting} +class Channel[a] { + private val written = new LinkedList[a](null); + private var lastWritten = written; + private val moreData = new Signal; + + def write(x: a) = { + lastWritten.next = new LinkedList(x); + lastWritten = lastWritten.next; + moreData.notify; + } + + def read: a = { + if (written.next == null) moreData.wait; + written = written.next; + written.elem; + } +} +\end{lstlisting} + +\section{Synchronous Channels} + +Here's an implementation of synchronous channels, where the sender of +a message blocks until that message has been received. Synchronous +channels only need a single variable to store messages in transit, but +three signals are used to coordinate reader and writer processes. +\begin{lstlisting} +class SyncChannel[a] { + val data = new SyncVar[a]; + + def write(x: a): unit = synchronized { + val empty = new Signal, full = new Signal, idle = new Signal; + if (data.isSet) idle.wait; + data.put(x); + full.send; + empty.wait; + data.unset; + idle.send; + } + + def read: a = synchronized { + if (!(data.isSet)) full.wait; + x = data.get; + empty.send; + x + } +} +\end{lstlisting} + +\section{Workers} + +Here's an implementation of a {\em compute server} in Scala. The +server implements a \code{future} method which evaluates a given +expression in parallel with its caller. Unlike the implementation in +Section~\ref{sec:futures} the server computes futures only with a +predefined number of threads. A possible implementation of the server +could run each thread on a separate processor, and could hence avoid +the overhead inherent in context-switching several threads on a single +processor. + +\begin{lstlisting} +class ComputeServer(n: int) { + private abstract class Job { + abstract type t; + def task: t; + def return(x: t): unit; + } + + private val openJobs = new Channel[Job] + + private def processor: unit = { + while (true) { + val job = openJobs.read; + job.return(job.task) + } + } +\end{lstlisting} +\begin{lstlisting} + def future[a](def p: a): () => a = { + val reply = new SyncVar[a]; + openJobs.write( + new Job { + type t = a; + def task = p; + def return(x: a) = reply.set(x); + } + ) + (=> reply.get) + } + + replicate(n){processor}; +} +\end{lstlisting} + +Expressions to be computed (i.e. arguments +to calls of \code{future}) are written to the \code{openJobs} +channel. A {\em job} is an object with +\begin{itemize} +\item +An abstract type \code{t} which describes the result of the compute +job. +\item +A parameterless \code{task} method of type \code{t} which denotes +the expression to be computed. +\item +A \code{return} method which consumes the result once it is +computed. +\end{itemize} +The compute server creates $n$ \code{processor} processes as part of +its initialization. Every such process repeatedly consumes an open +job, evaluates the job's \code{task} method and passes the result on +to the job's +\code{return} method. The polymorphic \code{future} method creates +a new job where the \code{return} method is implemented by a guard +named \code{reply} and inserts this job into the set of open jobs by +calling the \code{isOpen} guard. It then waits until the corresponding +\code{reply} guard is called. + +The example demonstrates the use of abstract types. The abstract type +\code{t} keeps track of the result type of a job, which can vary +between different jobs. Without abstract types it would be impossible +to implement the same class to the user in a statically type-safe +way, without relying on dynamic type tests and type casts. + +\section{Message Spaces} +\label{sec:messagespace} + +Message spaces are high-level, flexible constructs for process +synchronization and communication. A {\em message} in this context is +an arbitrary object. There is a special message \code{TIMEOUT} which +is used to signal a time-out. +\begin{lstlisting} +case class TIMEOUT; +\end{lstlisting} +Message spaces implement the following signature. +\begin{lstlisting} +class MessageSpace { + def send(msg: Any): unit; + def receive[a](f: PartialFunction[Any, a]): a; + def receiveWithin[a](msec: long)(f: PartialFunction[Any, a]): a; +} +\end{lstlisting} +The state of a message space consists of a multi-set of messages. +Messages are added to the space using the \code{send} method. Messages +are removed using the \code{receive} method, which is passed a message +processor \code{f} as argument, which is a partial function from +messages to some arbitrary result type. Typically, this function is +implemented as a pattern matching expression. The \code{receive} +method blocks until there is a message in the space for which its +message processor is defined. The matching message is then removed +from the space and the blocked thread is restarted by applying the +message processor to the message. Both sent messages and receivers are +ordered in time. A receiver $r$ is applied to a matching message $m$ +only if there is no other (message, receiver) pair which precedes $(m, +r)$ in the partial ordering on pairs that orders each component in +time. + +As a simple example of how message spaces are used, consider a +one-place buffer: +\begin{lstlisting} +class OnePlaceBuffer { + private val m = new MessageSpace; // An internal message space + private case class Empty, Full(x: int); // Types of messages we deal with + m send Empty; // Initialization + def write(x: int): unit = + m receive { case Empty => m send Full(x) } + def read: int = + m receive { case Full(x) => m send Empty ; x } +} +\end{lstlisting} +Here's how the message space class can be implemented: +\begin{lstlisting} +class MessageSpace { + private abstract class Receiver extends Signal { + def isDefined(msg: Any): boolean; + var msg = null; + } +\end{lstlisting} +We define an internal class for receivers with a test method +\code{isDefined}, which indicates whether the receiver is +defined for a given message. The receiver inherits from class +\code{Signal} a \code{notify} method which is used to wake up a +receiver thread. When the receiver thread is woken up, the message it +needs to be applied to is stored in the \code{msg} variable of +\code{Receiver}. +\begin{lstlisting} + private val sent = new LinkedList[Any](null) ; + private var lastSent = sent; + private var receivers = new LinkedList[Receiver](null); + private var lastReceiver = receivers; +\end{lstlisting} +The message space class maintains two linked lists, +one for sent but unconsumed messages, the other for waiting receivers. +\begin{lstlisting} + def send(msg: Any): unit = synchronized { + var r = receivers, r1 = r.next; + while (r1 != null && !r1.elem.isDefined(msg)) { + r = r1; r1 = r1.next; + } + if (r1 != null) { + r.next = r1.next; r1.elem.msg = msg; r1.elem.notify; + } else { + l = new LinkedList(msg); lastSent.next = l; lastSent = l; + } + } +\end{lstlisting} +The \code{send} method first checks whether a waiting receiver is + +applicable to the sent message. If yes, the receiver is notified. +Otherwise, the message is appended to the linked list of sent messages. +\begin{lstlisting} + def receive[a](f: PartialFunction[Any, a]): a = { + val msg: Any = synchronized { + var s = sent, s1 = s.next; + while (s1 != null && !f.isDefined(s1.elem)) { + s = s1; s1 = s1.next + } + if (s1 != null) { + s.next = s1.next; s1.elem + } else { + val r = new LinkedList( + new Receiver { + def isDefined(msg: Any) = f.isDefined(msg); + }); + lastReceiver.next = r; lastReceiver = r; + r.elem.wait; + r.elem.msg + } + } + f(msg) + } +\end{lstlisting} +The \code{receive} method first checks whether the message processor function +\code{f} can be applied to a message that has already been sent but that +was not yet consumed. If yes, the thread continues immediately by +applying \code{f} to the message. Otherwise, a new receiver is created +and linked into the \code{receivers} list, and the thread waits for a +notification on this receiver. Once the thread is woken up again, it +continues by applying \code{f} to the message that was stored in the receiver. + +The message space class also offers a method \code{receiveWithin} +which blocks for only a specified maximal amount of time. If no +message is received within the specified time interval (given in +milliseconds), the message processor argument $f$ will be unblocked +with the special \code{TIMEOUT} message. The implementation of +\code{receiveWithin} is quite similar to \code{receive}: +\begin{lstlisting} + def receiveWithin[a](msec: long)(f: PartialFunction[Any, a]): a = { + val msg: Any = synchronized { + var s = sent, s1 = s.next; + while (s1 != null && !f.isDefined(s1.elem)) { + s = s1; s1 = s1.next ; + } + if (s1 != null) { + s.next = s1.next; s1.elem + } else { + val r = new LinkedList( + new Receiver { + def isDefined(msg: Any) = f.isDefined(msg); + } + ) + lastReceiver.next = r; lastReceiver = r; + r.elem.wait(msec); + if (r.elem.msg == null) r.elem.msg = TIMEOUT; + r.elem.msg + } + } + f(msg) + } +} // end MessageSpace +\end{lstlisting} +The only differences are the timed call to \code{wait}, and the +statement following it. + +\section{Actors} +\label{sec:actors} + +Chapter~\ref{sec:ex-auction} sketched as a program example the +implementation of an electronic auction service. This service was +based on high-level actor processes, that work by inspecting messages +in their mailbox using pattern matching. An actor is simply a thread +whose communication primitives are those of a message space. +Actors are therefore defined by a mixin composition of threads and message spaces. +\begin{lstlisting} +abstract class Actor extends Thread with MessageSpace; +\end{lstlisting} + +\comment{ +As an extended example of an application that uses actors, we come +back to the auction server example of Section~\ref{sec:ex-auction}. +The following code implements: + +\begin{figure}[thb] +\begin{lstlisting} +class AuctionMessage; +case class + Offer(bid: int, client: Process), // make a bid + Inquire(client: Process) extends AuctionMessage // inquire status + +class AuctionReply; +case class + Status(asked; int, expiration: Date), // asked sum, expiration date + BestOffer, // yours is the best offer + BeatenOffer(maxBid: int), // offer beaten by maxBid + AuctionConcluded(seller: Process, client: Process),// auction concluded + AuctionFailed // failed with no bids + AuctionOver extends AuctionReply // bidding is closed +\end{lstlisting} +\end{figure} + +\begin{lstlisting} +class Auction(seller: Process, minBid: int, closing: Date) + extends Process { + + val timeToShutdown = 36000000 // msec + val delta = 10 // bid increment +\end{lstlisting} +\begin{lstlisting} + def run = { + var askedBid = minBid + var maxBidder: Process = null + while (true) { + receiveWithin ((closing - Date.currentDate).msec) { + case Offer(bid, client) => { + if (bid >= askedBid) { + if (maxBidder != null && maxBidder != client) { + maxBidder send BeatenOffer(bid) + } + maxBidder = client + askedBid = bid + delta + client send BestOffer + } else client send BeatenOffer(maxBid) + } +\end{lstlisting} +\begin{lstlisting} + case Inquire(client) => { + client send Status(askedBid, closing) + } +\end{lstlisting} +\begin{lstlisting} + case TIMEOUT => { + if (maxBidder != null) { + val reply = AuctionConcluded(seller, maxBidder) + maxBidder send reply + seller send reply + } else seller send AuctionFailed + receiveWithin (timeToShutdown) { + case Offer(_, client) => client send AuctionOver ; discardAndContinue + case _ => discardAndContinue + case TIMEOUT => stop + } + } +\end{lstlisting} +\begin{lstlisting} + case _ => discardAndContinue + } + } + } +\end{lstlisting} +\begin{lstlisting} + def houseKeeping: int = { + val Limit = 100 + var nWaiting: int = 0 + receiveWithin(0) { + case _ => + nWaiting = nWaiting + 1 + if (nWaiting > Limit) { + receiveWithin(0) { + case Offer(_, _) => continue + case TIMEOUT => + case _ => discardAndContinue + } + } else continue + case TIMEOUT => + } + } +} +\end{lstlisting} +\begin{lstlisting} +class Bidder (auction: Process, minBid: int, maxBid: int) + extends Process { + val MaxTries = 3 + val Unknown = -1 + + var nextBid = Unknown +\end{lstlisting} +\begin{lstlisting} + def getAuctionStatus = { + var nTries = 0 + while (nextBid == Unknown && nTries < MaxTries) { + auction send Inquiry(this) + nTries = nTries + 1 + receiveWithin(waitTime) { + case Status(bid, _) => bid match { + case None => nextBid = minBid + case Some(curBid) => nextBid = curBid + Delta + } + case TIMEOUT => + case _ => continue + } + } + status + } +\end{lstlisting} +\begin{lstlisting} + def bid: unit = { + if (nextBid < maxBid) { + auction send Offer(nextBid, this) + receive { + case BestOffer => + receive { + case BeatenOffer(bestBid) => + nextBid = bestBid + Delta + bid + case AuctionConcluded(seller, client) => + transferPayment(seller, nextBid) + case _ => continue + } + + case BeatenOffer(bestBid) => + nextBid = nextBid + Delta + bid + + case AuctionOver => + + case _ => continue + } + } + } +\end{lstlisting} +\begin{lstlisting} + def run = { + getAuctionStatus + if (nextBid != Unknown) bid + } + + def transferPayment(seller: Process, amount: int) +} +\end{lstlisting} +} +%\todo{We also need some XML examples.} +\end{document} + + + + case ([], _) => ys + case (_, []) => xs + case (x :: xs1, y :: ys1) => + if (x < y) x :: merge(xs1, ys) else y :: merge(xs, ys1) +} + +def split (xs: List[a]): (List[a], List[a]) = xs match { + case [] => ([], []) + case [x] => (x, []) + case y :: z :: xs1 => val (ys, zs) = split(xs1) ; (y :: ys, z :: zs) +} + +def sort(xs: List[a]): List[a] = { + val (ys, zs) = split(xs) + merge(sort(ys), sort(zs)) +} + + +def sort(a:Array[String]): Array[String] = { + val pivot = a(a.length / 2) + sort(a.filter(x => x < pivot)) ++ + a.filter(x => x == pivot) ++ + sort(a.filter(x => x > pivot)) +} + +def sort(a:Array[String]): Array[String] = { + + def swap (i: int, j: int): unit = { + val t = a(i) ; a(i) = a(j) ; a(j) = t + } + + def sort1(l: int, r: int): unit = { + val pivot = a((l + r) / 2) + var i = l, j = r + while (i <= r) { + while (i < r && a(i) < pivot) { i = i + 1 } + while (j > l && a(j) > pivot) { j = j - 1 } + if (i <= j) { + swap(i, j) + i = i + 1 + j = j - 1 + } + } + if (l < j) sort1(l, j) + if (j < r) sort1(i, r) + } + + sort1(0, a.length - 1) +} + +class Array[a] { + + def copy(to: Array[a], src: int, dst: int, len: int): unit + val length: int + val apply(i: int): a + val update(i: int, x: a): unit + + def filter (p: a => boolean): Array[a] = { + val temp = new Array[a](a.length) + var i = 0, j = 0 + for (i < a.length, i = i + 1) { + val x = a(i) + if (p(x)) { temp(j) = x; j = j + 1 } + } + val res = new Array[a](j) + temp.copy(res, 0, 0, j) + } + + def ++ (that: Array[a]): Array[a] = { + val a = new Array[a](this.length + that.length) + this.copy(a, 0, 0, this.length) + that.copy(a, 0, this.length, that.length) + } + +static + + def concat [a] (as: List[Array[a]]) = { + val l = (as map (a => a.length)).sum + val dst = new Array[a](l) + var j = 0 + as forall {a => { a.copy(dst, j, a.length) ; j = j + a.length }} + dst + } + +} + +module ABT extends AlgBinTree[kt, vt] +ABT.Map -- cgit v1.2.3