*** empty log message ***

1 files changed, 5510 insertions, 0 deletions

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