*** empty log message ***

1 files changed, 1176 insertions, 236 deletions

diff --git a/doc/reference/examples.verb.tex b/doc/reference/examples.verb.tex
index 2459ba7ff1..37800bee0e 100644
--- a/doc/reference/examples.verb.tex
+++ b/doc/reference/examples.verb.tex
@@ -1,6 +1,6 @@
 %% $Id$
 
-\documentclass[11pt]{report}
+\documentclass[11pt]{book}
 
 \usepackage{fleqn,a4wide,vquote,modefs,math,prooftree,scaladefs}
 \newcommand{\exercise}{\paragraph{Exercise:}}
@@ -8,24 +8,47 @@
 \title{Scala By Examples}
 
 \author{
-Martin Odersky
+Martin Odersky \\ EPFL
 }
 
 \sloppy
 \begin{document}
 \maketitle
+\bibliographystyle{alpha}
 
-\chapter{\label{sec:example-one}A First Example}
+\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{verbatim}
-def sort(xs: Array[Int]): Unit = {
+def sort(xs: Array[int]): unit = {
 
-  def swap(i: Int, j: 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 = {
+  def sort1(l: int, r: int): unit = {
     val pivot = xs((l + r) / 2);
     var i = l, j = r;
     while (i <= j) {
@@ -57,10 +80,11 @@ 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 \verb@Unit@ instead of \verb@void@ to define the result type of
+We use \verb@unit@ instead of \verb@void@ to define the result type of
 a procedure.
 \item
-Array types are written \verb@Array[$T$]@ rather than \verb@$T$[]@.
+Array types are written \verb@Array[T]@ rather than \verb@T[]@, 
+and array selections are written \verb@a(i)@ rather than \verb@a[i]@.
 \item
 Functions can be nested inside other functions. Nested functions can
 access parameters and local variables of enclosing functions. For
@@ -69,7 +93,7 @@ instance, the name of the array \verb@a@ is visible in functions
 parameter to them.
 \end{itemize}
 So far, Scala looks like a fairly conventional language with some
-syntactic particularitis. In fact it is possible to write programs in a
+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
@@ -80,7 +104,7 @@ completely different. Here is Quicksort again, this time written in
 functional style.
 
 \begin{verbatim}
-def sort(xs: List[Int]): List[Int] = {
+def sort(xs: List[int]): List[int] = {
   val pivot = a(a.length / 2);
   sort(a.filter(x => x < pivot))
     :::  a.filter(x => x == pivot)
@@ -88,9 +112,10 @@ def sort(xs: List[Int]): List[Int] = {
 }
 \end{verbatim}
 
-The functional program works with lists instead of arrays\footnote{
-This is necessary for now, because arrays do not yet support
-\verb@filter@ and \verb@:::@.}.
+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
+\verb@filter@ and \verb@:::@.}
 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.
@@ -98,7 +123,7 @@ It captures the essence of the quicksort algorithm in a concise way:
 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 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.
@@ -119,22 +144,22 @@ Scala library, and which itself is implemented in Scala.
 
 In particular, there is the method \verb@filter@ which takes as
 argument a {\em predicate function} that maps list elements to
-Boolean values. The result of \verb@filter@ is a list consisting of
+boolean values. The result of \verb@filter@ is a list consisting of
 all the elements of the original list for which the given predicate
 function is true.  The \verb@filter@ method of an object of type
 \verb@List[t]@ thus has the signature
 \begin{verbatim}
-  def filter(p: t => Boolean): List[t]  .
+  def filter(p: t => boolean): List[t]  .
 \end{verbatim}
-Here, \verb@t => Boolean@ is the type of functions that take an element
-of type \verb@t@ and return a \verb@Boolean@.  Functions like
+Here, \verb@t => boolean@ is the type of functions that take an element
+of type \verb@t@ and return a \verb@boolean@.  Functions like
 \verb@filter@ that take another function as argument or return one as
 result are called {\em higher-order} functions.
 
 In the quicksort program, \verb@filter@ is applied three times to an
 anonymous function argument.  The first argument,
 \verb@x => x <= pivot@ represents the function that maps its parameter
-\verb@x@ to the Boolean value \verb@x <= pivot@. That is, it yields
+\verb@x@ to the boolean value \verb@x <= pivot@. That is, it yields
 true if \verb@x@ is smaller or equal than \verb@pivot@, false
 otherwise. The function is anonymous, i.e.\ it is not defined with a
 name. The type of the \verb@x@ parameter is omitted because a Scala
@@ -143,6 +168,7 @@ function is used. To summarize, \verb@xs.filter(x => x <= pivot)@
 returns a list consisting of all elements of the list \verb@xs@ that are
 smaller than \verb@pivot@.
 
+\comment{
 It is also possible to apply higher-order functions such as
 \verb@filter@ to named function arguments. Here is functional
 quicksort again, where the two anonymous functions are replaced by
@@ -150,16 +176,17 @@ named auxiliary functions that compare the argument to the
 \verb@pivot@ value.
 
 \begin{verbatim}
-def sort (xs: List[Int]): List[Int] = {
+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;
+  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{verbatim}
+}
 
 An object of type \verb@List[t]@ also has a method ``\verb@:::@''
 which takes an another list and which returns the result of appending this
@@ -177,11 +204,11 @@ 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 \verb@sort@ in the last quicksort example is hence equivalent to:
+to \verb@sort@ in the last quicksort example is thus equivalent to
 \begin{verbatim}
-  sort(a.filter(leqPivot))
-    .append(sort(a.filter(eqPivot)))
-    .append(sort(a.filter(gtPivot))) .
+  sort(a.filter(x => x < pivot))
+    .:::(sort(a.filter(x => x == pivot)))
+    .:::(sort(a.filter(x => x > pivot))) .
 \end{verbatim}
 
 Looking again in detail at the first, imperative implementation of
@@ -201,21 +228,21 @@ Control constructs such as \verb@while@ are also not primitive but are
 predefined functions in the standard Scala library. Here is the
 definition of \verb@while@ in Scala.
 \begin{verbatim}
-def while (def p: Boolean) (def s: Unit): Unit = if (p) { s ; while(p)(s) }
+def while (def p: boolean) (def s: unit): unit = if (p) { s ; while(p)(s) }
 \end{verbatim}
 The \verb@while@ function takes as first parameter a test function,
-which takes no parameters and yields a Boolean value. As second
+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. \verb@while@ invokes the command function
 as long as the test function yields true. Again, compilers are free to
 pick specialized implementations of \verb@while@ that have the same
 behavior as the invocation of the function given above.
 
-\chapter{\label{sec:ex-auction}Programming with Actors and Messages}
+\chapter{\label{chap:example-auction}Programming with Actors and Messages}
 
 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 will use an Erlang-style actor process
+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
@@ -236,22 +263,22 @@ clients.  These are defined as follows.
 \begin{verbatim}
 trait AuctionMessage;
 case class 
-  Offer(bid: Int, client: Actor),                     // make a bid
-  Inquire(client: Actor) extends AuctionMessage;      // inquire status
+  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
+  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{verbatim}
 
-\begin{figure}[h]
+\begin{figure}[htb]
 \begin{verbatim}
-class Auction(seller: Actor, minBid: Int, closing: Date) extends Actor() {
+class Auction(seller: Actor, minBid: int, closing: Date) extends Actor() {
   val timeToShutdown = 36000000; // msec
   val bidIncrement = 10;
   def execute {
@@ -263,9 +290,7 @@ class Auction(seller: Actor, minBid: Int, closing: Date) extends Actor() {
 	case Offer(bid, client) =>
 	  if (bid >= maxBid + bidIncrement) { 
             if (maxBid >= minBid) maxBidder send BeatenOffer(bid);
-            maxBid = bid;
-            maxBidder = client;
-            client send BestOffer();
+            maxBid = bid; maxBidder = client; client send BestOffer();
           } else {
             client send BeatenOffer(maxBid);
           }
@@ -276,26 +301,21 @@ class Auction(seller: Actor, minBid: Int, closing: Date) extends Actor() {
 	case TIMEOUT() =>
 	  if (maxBid >= minBid) {
 	    val reply = AuctionConcluded(seller, maxBidder);
-	    maxBidder send reply;
-	    seller send reply;
+	    maxBidder send reply; seller send reply;
 	  } else {
 	    seller send AuctionFailed();
           }
           receiveWithin(timeToShutdown) {
             case Offer(_, client) => client send AuctionOver()
             case TIMEOUT() => running = false;
-          }
-      }
-    }
-  }
-}
+          }}}}}
 \end{verbatim}
 \caption{\label{fig:simple-auction}Implementation of an Auction Service}
 \end{figure}
 
 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 implemented as small XML documents. We expect
+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.
 
@@ -315,8 +335,10 @@ repeatedly selects (using \verb@receiveWithin@) a message and reacts to it,
 until the auction is closed, which is signalled by a \verb@TIMEOUT@
 message. Before finally stopping, it stays active for another period
 determined by the \verb@timeToShutdown@ constant and replies to
-further offers that the auction is closed.  Here are some further
-explanations of the constructs used in this program:
+further offers that the auction is closed.  
+
+Here are some further explanations of the constructs used in this
+program:
 \begin{itemize}
 \item
 The \verb@receiveWithin@ method of class \verb@Actor@ takes as
@@ -367,28 +389,949 @@ 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{Simple Functions}
+\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. 
+functions.
+
+\section{Expressions And Simple Functions}
 
 A Scala system comes with an interpreter which can be seen as a
-glorified calculator. A user interacts with the calculator by tying in
+fancy calculator. A user interacts with the calculator by typing in
 expressions and obtaining the results of their evaluation. Example:
 
+\begin{verbatim}
+? 87 + 145
+232
+
+? 1000 - 333
+667
+
+? 5 + 2 * 3
+11
+\end{verbatim}
+It is also possible to name a sub-expression and use the name instead
+of the expression afterwards:
+\begin{verbatim}
+? def size = 2
+def size: int
+
+? 5 * size
+10
+\end{verbatim}
+\begin{verbatim}
+? def pi = 3.14159
+def pi: double
+
+? def radius = 10
+def radius: int
+
+
+? 2 * pi * radius
+62.8318
+\end{verbatim}
+Definitions start with the reserved word \verb@def@; they introduce a
+name which stands for the expression following the \verb@=@ sign.  The
+interpreter will answer with the introduced name and its type.
+
+Executing a definition such as \verb@def x = e@ will not evaluate the
+expression \verb@e@.  Instead \verb@e@ is evaluated whenever \verb@x@
+is used. Alternatively, Scala offers a value definition 
+\verb@val x = e@, which does evaluate the right-hand-side \verb@e@ as part of the
+evaluation of the definition. If \verb@x@ is then used subsequently,
+it is immediately replaced by the pre-computed value of
+\verb@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 \verb@def@\ is evaluated by replacing the name by the
+definition's right hand side. A name defined by \verb@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{verbatim}
+    \=(2 * pi) * radius
+->  \>(2 * 3.14159) * radius
+->  \>6.28318 * radius
+->  \>6.28318 * 10
+->  \>62.8318
+\end{verbatim}
+The process of stepwise simplification of expressions to values is
+called {\em reduction}.
+
+\section{Parameters}
+
+Using \verb@def@, one can also define functions with parameters. Example:
+\begin{verbatim}
+? 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{verbatim}
+
+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 \verb@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{verbatim}
+    \=sumOfSquares(3, 2+2)
+->  \>sumOfSquares(3, 4)
+->  \>square(3) + square(4)
+->  \>3 * 3 + square(4)
+->  \>9 + square(4)
+->  \>9 + 4 * 4
+->  \>9 + 16
+->  \>25
+\end{verbatim}
+
+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{verbatim}
+    \= sumOfSquares(3, 2+2)
+->  \>square(3) + square(2+2)
+->  \>3 * 3 + square(2+2)
+->  \>9 + square(2+2)
+->  \>9 + (2+2) * (2+2)
+->  \>9 + 4 * (2+2)
+->  \>9 + 4 * 4
+->  \>9 + 16
+->  \>25
+\end{verbatim}
+
+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{verbatim}
+? def loop: int = loop
+def loop: int
+
+? def first(x: int, y: int) = x
+def first(x: int, y: int): int
+\end{verbatim}
+Then \verb@first(1, loop)@ reduces with call-by-name to \verb@1@,
+whereas the same term reduces with call-by-value repeatedly to itself,
+hence evaluation does not terminate.
+\begin{verbatim}
+    \=first(1, loop)
+->  \>first(1, loop)
+->  \>first(1, loop)
+->  \>...
+\end{verbatim}
+Scala uses call-by-value by default, but it switches to call-by-name evaluation
+if the parameter is preceded by \verb@def@.
+
+\example\ 
+ 
+\begin{verbatim}
+? 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{verbatim}
+
+\section{Conditional Expressions}
+
+Scala's \verb@if-else@ lets one choose between two alternatives.  Its
+syntax is like Java's \verb@if-else@. But where Java's \verb@if-else@
+can be used only as an alternative of statements, Scala allows the
+same syntax to choose between two expressions. Scala's \verb@if-else@
+hence also replaces Java's conditional expression \verb@ ... ? ... :
+...@.
+
+\example\ 
+
+\begin{verbatim}
+? def abs(x: double) = if (x >= 0) x else -x
+abs(x: double): double
+\end{verbatim}
+Scala's boolean expressions are similar to Java's; they are formed
+from the constants
+\verb@true@ and
+\verb@false@, comparison operators, boolean negation \verb@!@ and the
+boolean operators \verb@&&@ and \verb@||@.
+
+\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{verbatim}
+def sqrt(x: double): double = ... 
+\end{verbatim}
+which computes the square root of \verb@x@.
+
+A common way to compute square roots is by Newton's method of
+successive approximations. One starts with an initial guess \verb@y@
+(say: \verb@y = 1@). One then repeatedly improves the current guess
+\verb@y@ by taking the average of \verb@y@ and \verb@x/y@.
+As an example, the next three columns indicate the guess \verb@y@, the
+quotient \verb@x/y@, and their average for the first approximations of
+$\sqrt 2$. 
+\begin{verbatim}
+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{verbatim}
+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{verbatim}
+def sqrtIter(guess: double, x: double): double = 
+  if (isGoodEnough(guess, x)) guess
+  else sqrtIter(improve(guess, x), x);
+\end{verbatim}
+Note that \verb@sqrtIter@ calls itself recursively.  Loops in
+imperative programs can always be modelled by recursion in functional
+programs. 
+
+Note also that the definition of \verb@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
+\verb@sqrtIter@: a function to \verb@improve@ the guess and a
+termination test \verb@isGoodEnough@. Here's their definition.
+\begin{verbatim}
+def improve(guess: double, x: double) = 
+  (guess + x / guess) / 2;
+
+def isGoodEnough(guess: double, x: double) = 
+  abs(square(guess) - x) < 0.001;
+\end{verbatim}
+
+Finally, the \verb@sqrt@ function itself is defined by an aplication
+of \verb@sqrtIter@.
+\begin{verbatim}
+def sqrt(x: double) = sqrtIter(1.0, x);
+\end{verbatim}
+
+\exercise The \verb@isGoodEnough@ test is not very precise for small numbers
+and might lead to non-termination for very large ones (why?).
+Design a different version \verb@isGoodEnough@ which does not have these problems.
+
+\exercise Trace the execution of the \verb@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 \verb@sqrt@ made use of the helper functions
+\verb@sqrtIter@, \verb@improve@ and
+\verb@isGoodEnough@. The names of these functions 
+are relevant only for the implementation of
+\verb@sqrt@. We normally do not want users of \verb@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{verbatim}
+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{verbatim}
+In this program, the braces \verb@{ ... }@ 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{verbatim}
+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{verbatim}
+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
+\verb@sqrt@ example. We need not pass \verb@x@ around as an additional parameter of
+the nested functions, since it is always visible in them as a
+parameter of the outer function \verb@sqrt@. Here is the simplified code:
+\begin{verbatim}
+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{verbatim}
+
+\section{Tail Recursion}
+
+Consider the following function to compute the greatest common divisor
+of two given numbers.
+
+\begin{verbatim}
+def gcd(a: int, b: int): int = if (b == 0) a else gcd(b, a % b)
+\end{verbatim}
+
+Using our substitution model of function evaluation, 
+\verb@gcd(14, 21)@ evaluates as follows:
+
+\begin{verbatim}
+        \=gcd(14, 21)  
+->      \>if (21 == 0) 14 else gcd(21, 14 % 21)
+->      \>if (false) 14 else gcd(21, 14 % 21)
+->      \>gcd(21, 14 % 21)
+->      \>gcd(21, 14)
+->      \>if (14 == 0) 21 else gcd(14, 21 % 14)
+-> ->   \>gcd(14, 21 % 14)
+->      \>gcd(14, 7)
+->      \>if (7 == 0) 14 else gcd(7, 14 % 7)
+-> ->   \>gcd(7, 14 % 7)
+->      \>gcd(7, 0)
+->      \>if (0 == 0) 7 else gcd(0, 7 % 0)
+-> ->   \>7
+\end{verbatim}
+
+Contrast this with the evaluation of another recursive function, 
+\verb@factorial@:
+
+\begin{verbatim}
+def factorial(n: int): int = if (n == 0) 1 else n * factorial(n - 1)
+\end{verbatim}
+
+The application \verb@factorial(5)@ rewrites as follows:
+\begin{verbatim}
+        \=factorial(5)
+->      \>if (5 == 0) 1 else 5 * factorial(5 - 1)
+->      \>5 * factorial(5 - 1)
+->      \>5 * factorial(4)
+-> ... -> \>5 * (4 * factorial(3))
+-> ... -> \>5 * (4 * (3 * factorial(2)))
+-> ... -> \>5 * (4 * (3 * (2 * factorial(1))))
+-> ... -> \>5 * (4 * (3 * (2 * (1 * factorial(0))))
+-> ... -> \>5 * (4 * (3 * (2 * (1 * 1))))
+-> ... -> \>120
+
+\end{verbatim}
+There is an important difference between the two rewrite sequences:
+The terms in the rewrite sequence of \verb@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 \verb@gcd@, one notes that
+the recursive call to \verb@gcd@ is the last action performed in the
+evaluation of its body. One also says that \verb@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 \verb@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 \verb@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
+\verb@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 \verb@a@ and \verb@b@:
+\begin{verbatim}
+def sumInts(a: int, b: int): double =
+  if (a > b) 0 else a + sumInts(a + 1, b)
+\end{verbatim}
+\item 
+Write a function to sum the cubes of all integers between two given numbers 
+\verb@a@ and \verb@b@:
+\begin{verbatim}
+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{verbatim}
+\item
+Write a function to sum the reciprocals of all integers between two given numbers 
+\verb@a@ and \verb@b@:
+\begin{verbatim}
+def sumReciprocals(a: int, b: int): double =
+  if (a > b) 0 else 1.0 / a + sumReciprocals(a + 1, b)
+\end{verbatim}
+\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 \verb@sum@:
+\begin{verbatim}
+def sum(f: int => double, a: int, b: int): double =
+  if (a > b) 0 else f(a) + sum(f, a + 1, b)
+\end{verbatim}
+The type \verb@int => double@ is the type of functions that
+take arguments of type \verb@int@ and return results of type
+\verb@double@. So \verb@sum@ is a function which takes another function as 
+a parameter. In other words, \verb@sum@ is a {\em higher-order}
+function.
+
+Using \verb@sum@, we can formulate the three summing functions as
+follows.
+\begin{verbatim}
+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{verbatim}
+where
+\begin{verbatim}
+def id(x: int): double = x;
+def cube(x: int): double = x * x * x;
+def reciprocal(x: int): double = 1.0/x;
+\end{verbatim}
+
+\section{Anonymous Functions}
+
+Parameterization by functions tends to create many small functions. In
+the previous example, we defined \verb@id@, \verb@cube@ and
+\verb@reciprocal@ as separate functions, so that they could be 
+passed as arguments to \verb@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{verbatim}
+  x: int => 1.0/x
+\end{verbatim}
+The part before the arrow `\verb@=>@' is the parameter of the function,
+whereas the part following the `\verb@=>@' 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{verbatim}
+  (x: double, y: double) => x * y
+\end{verbatim}
+Using anonymous functions, we can reformulate the three summation
+functions without named auxiliary functions:
+\begin{verbatim}
+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{verbatim}
+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 \verb@sumInts@, \verb@sumCubes@ and
+verb@sumReciprocals@, one knows from the type of
+\verb@sum@ that the first parameter must be a function of type
+\verb@int => double@.  Hence, the parameter type \verb@int@ is
+redundant and may be omitted:
+\begin{verbatim}
+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{verbatim}
+
+Generally, the Scala term
+\verb@(x$_1$: T$_1$, ..., x$_n$: T$_n$) => E@ 
+defines a function which maps its parameters
+\verb@x$_1$, ..., x$_n$@ to the result of the expression \verb@E@
+(where \verb@E@ may refer to \verb@x$_1$, ..., 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
+\verb@(x$_1$: T$_1$, ..., x$_n$: T$_n$) => E@ 
+is equivalent to the block
+\begin{verbatim}
+{ def f (x$_1$: T$_1$, ..., x$_n$: T$_n$) = E ; f }
+\end{verbatim}
+where \verb@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
+\verb@a@ and \verb@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 \verb@sum@ so that it does not take the bounds
+\verb@a@ and \verb@b@ as parameters:
+\begin{verbatim}
+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{verbatim}
+In this formulation, \verb@sum@ is a function which returns another
+function, namely the specialized summing function \verb@sumF@. This
+latter function does all the work; it takes the bounds \verb@a@ and
+\verb@b@ as parameters, applies \verb@sum@'s function parameter \verb@f@ to all
+integers between them, and sums up the results. 
+
+Using this new formulation of \verb@sum@, we can now define:
+\begin{verbatim}
+def sumInts = sum(x => x);
+def sumCubes = sum(x => x * x * x);
+def sumReciprocals = sum(x => 1.0/x);
+\end{verbatim}
+Or, equivalently, with value definitions:
+\begin{verbatim}
+val sumInts = sum(x => x);
+val sumCubes = sum(x => x * x * x);
+val sumReciprocals = sum(x => 1.0/x);
+\end{verbatim}
+These functions can be applied like other functions. For instance,
+\begin{verbatim}
+? sumCubes(1, 10) + sumReciprocals (10, 20)
+3025.7687714031754
+\end{verbatim}
+How are function-returning functions applied? As an example, in the expression
+\begin{verbatim}
+sum (x => x * x * x) (1, 10) ,
+\end{verbatim}
+the function \verb@sum@ is applied to the cubing function 
+\verb@(x => x * x * x)@. The resulting function is then 
+applied to the second argument list, \verb@(1, 10)@.
+
+This notation is possible because function application associates to the left.
+That is, if $args_1$ and $args_2$ are argument lists, then 
+\bda{lcl}
+f(args_1)(args_2) & \ \ \mbox{is equivalent to}\ \ & (f(args_1))(args_2)
+\eda
+In our example, \verb@sum(x => x * x * x)(1, 10)@ is equivalent to 
+\verb@(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 \verb@sum@
+is equivalent to the previous one, but is shorter:
+\begin{verbatim}
+def sum(f: int => double)(a: int, b: int): double =
+  if (a > b) 0 else f(a) + sum(f)(a + 1, b)
+\end{verbatim}
+Generally, a curried function definition 
+\begin{verbatim}
+def f (args$_1$) ... (args$_n$) = E
+\end{verbatim}
+where $n > 1$ expands to
+\begin{verbatim}
+def f (args$_1$) ... (args$_{n-1}$) = { def g (args$_n$) = E ; g }
+\end{verbatim}
+where \verb@g@ is a fresh identifier. Or, shorter, using an anonymous function:
+\begin{verbatim}
+def f (args$_1$) ... (args$_{n-1}$) = ( args$_n$ ) => E .
+\end{verbatim}
+Performing this step $n$ times yields that
+\begin{verbatim}
+def f (args$_1$) ... (args$_n$) = E
+\end{verbatim}
+is equivalent to
+\begin{verbatim}
+def f = (args$_1$) => ... => (args$_n$) => E .
+\end{verbatim}
+Or, equivalently, using a value definition:
+\begin{verbatim}
+val f = (args$_1$) => ... => (args$_n$) => E .
+\end{verbatim}
+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 \verb@sum@ as an example,
+the type of \verb@sum@ is \verb@(int => double) => (int, int) => double@.
+This is possible because function types associate to the right. I.e.
+\begin{verbatim}
+T$_1$ => T$_2$ => T$_3$       \=$\mbox{is equivalent to}$     \=T$_1$ => (T$_2$ => T$_3$) .
+\end{verbatim}
+
+\subsection*{Exercises:}
+
+1. The \verb@sum@ function uses a linear recursion. Can you write a
+tail-recursive one by filling in the ??'s?
+
+\begin{verbatim}
+def sum(f: int => double)(a: int, b: int): double = {
+  def iter (a, result) = {
+    if (??) ??
+    else iter (??, ??)
+  }
+  iter (??, ??)
+}
+\end{verbatim}
+
+2. Write a function \verb@product@ that computes the product of the
+values of functions at points over a given range.
+
+3. Write \verb@factorial@ in terms of \verb@product@.
+
+4. Can you write an even more general function which generalizes both
+\verb@sum@ and \verb@product@?
+
+\section{Example: Finding Fixed Points of Functions}
+
+A number \verb@x@ is called a {\em fixed point} of a function \verb@f@ if
+\begin{verbatim}
+f(x) = x .
+\end{verbatim}
+For some functions \verb@f@ we can locate the fixed point by beginning
+with an initial guess and then applying \verb@f@ repeatedly, until the
+value does not change anymore (or the change is within a small
+tolerance). This is possible if the sequence
+\begin{verbatim}
+x, f(x), f(f(x)), f(f(f(x))), ...
+\end{verbatim}
+converges to fixed point of $f$. This idea is captured in
+the following ``fixed-point finding function'':
+\begin{verbatim}
+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{verbatim}
+We now apply this idea in a reformulation of the square root function.
+Let's start with a specification of \verb@sqrt@:
+\begin{verbatim}
+sqrt(x)  \==  $\mbox{the {\sl y} such that}$  y * y = x
+         \>=  $\mbox{the {\sl y} such that}$  y = x / y
+\end{verbatim}
+Hence, \verb@sqrt(x)@ is a fixed point of the function \verb@y => x / y@.
+This suggests that \verb@sqrt(x)@ can be computed by fixed point iteration:
+\begin{verbatim}
+def sqrt(x: double) = fixedPoint(y => x / y)(1.0)
+\end{verbatim}
+Unfortunately, this does not converge. Let's instrument the fixed point
+function with a print statement which keeps track of the current
+\verb@guess@ value:
+\begin{verbatim}
+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{verbatim}
+Then, \verb@sqrt(2)@ yields:
+\begin{verbatim}
+  2.0
+  1.0
+  2.0
+  1.0
+  2.0
+  ...
+\end{verbatim}
+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{verbatim}
+> 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{verbatim}
+In fact, expanding the \verb@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 \verb@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{verbatim}
+def averageDamp(f: double => double)(x: double) = (x + f(x)) / 2
+\end{verbatim}
+Using \verb@averageDamp@, we can reformulate the square root function
+as follows.
+\begin{verbatim}
+def sqrt(x: double) = fixedPoint(averageDamp(y => x/y))(1.0)
+\end{verbatim}
+This expresses the elements of the algorithm as clearly as possible.
+
+\exercise Write a function for cube roots using \verb@fixedPoint@ and 
+\verb@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 `\verb@|@' denotes alternatives, \verb@[...]@ denotes
+option (0 or 1 occurrences), and \verb@{...}@ 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 `\verb@ @', tabulator, or newline characters,
+\item
+letters `\verb@a@' to `\verb@z@', `\verb@A@' to `\verb@Z@',
+\item
+digits \verb@`0'@ to `\verb@9@',
+\item
+the delimiter characters
+\begin{verbatim}
+.    ,    ;    (    )    {    }    [    ]    \    "    '
+\end{verbatim}
+\item
+operator characters, such as `\verb@#@' `\verb@+@',
+`\verb@:@'. Essentially, these are printable characters which are
+in none of the character sets above.
+\end{itemize}
+
+\subsection*{Lexemes:}
+
+\begin{verbatim}
+ident      ::=   letter {letter | digit} | operator { operator } | ident `_' ident
+literal    ::=   $\mbox{``as in Java''}$
+\end{verbatim}
+
+Literals are as in Java. They define numbers, characters, strings, or
+boolean values.  Examples of literals as \verb@0@, \verb@1.0d10@, \verb@'x'@,
+\verb@"he said \"hi!\""@, or \verb@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 `\verb@_@'. Furthermore,
+an underscore character may be followed by either sort of
+identifier. Hence, the following are all legal identifiers:
+\begin{verbatim}
+x     Room10a     +     --     foldl_:     +_vector
+\end{verbatim}
+It follows from this rule that subsequent operator-identifiers need to
+be separated by whitespace. For instance, the input
+\verb@x+-y@ is parsed as the three token sequence \verb@x@, \verb@+-@,
+\verb@y@. If we want to express the sum of \verb@x@ with the
+negated value of \verb@y@, we need to add at least one space,
+e.g. \verb@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{verbatim}
+abstract    case    class    def    do    else   
+extends    false    final    for    if    import    
+module    new    null    override    package    
+private    protected    super    this    trait
+true    type    val    var    with    yield
+\end{verbatim}
+
+\subsection*{Types:}
+
+\begin{verbatim}
+Type           \= = SimpleType | FunctionType
+FunctionType \> = SimpleType `=>' Type | `(' [Types] `)' `=>' Type
+SimpleType   \> = byte | short | char | int | long | double | float | boolean | unit | String
+Types        \> = Type {`,' Type}
+\end{verbatim}
+
+Types can be:
+\begin{itemize}
+\item number types \verb@byte@, \verb@short@, \verb@char@, \verb@int@, \verb@long@, \verb@float@ and \verb@double@ (these are as in Java),
+\item the type \verb@boolean@ with values \verb@true@ and \verb@false@,
+\item the type \verb@unit@ with the only value \verb@{}@,
+\item the type \verb@String@,
+\item function types such as \verb@(int, int) => int@ or \verb@String => Int => String@. 
+\end{itemize}
+
+\subsection*{Expressions:}
+
+\begin{verbatim}
+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{verbatim}
+
+Expressions can be:
+\begin{itemize}
+\item
+identifiers such as \verb@x@, \verb@isGoodEnough@, \verb@*@, or \verb@+-@,
+\item
+literals, such as \verb@0@, \verb@1.0@, or \verb@"abc"@,
+\item
+field and method selections, such as \verb@System.out.println@,
+\item
+function applications, such as \verb@sqrt(x)@, 
+\item
+operator applications, such as \verb@-x@ or \verb@y + x@,
+\item
+conditionals, such as \verb@if (x < 0) -x else x@,
+\item
+blocks, such as \verb@{ val x = abs(y) ; x * 2 }@,
+\item
+anonymous functions, such as \verb@x => x + 1@ or \verb@(x: int, y: int) => x + y@.
+\end{itemize}
+
+\subsection*{Definitions:}
+
+\begin{verbatim}
+Def                \= = \=FunDef  |  ValDef
+FunDef       \> = \>def ident {`(' [Parameters] `)'} [`:' Type] `=' Expr
+ValDef       \> = \>val ident [`:' Type] `=' Expr
+Parameters   \> = \>Parameter {`,' Parameter}
+Parameter    \> = \>[def] ident `:' Type
+\end{verbatim}
+Definitions can be:
+\begin{itemize}
+\item
+function definitions such as \verb@def square(x: int) = x * x@, 
+\item
+value definitions such as \verb@val y = square(2)@.
+\end{itemize}
+\bibliography{master}
+\end{document}
 
 \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.
+easy to define one, using a class. Here's a possible implementation.
 
 \begin{verbatim}
-class Rational(n: Int, d: Int) with {
-  private def gcd(x: Int, y: Int): Int = {
+class Rational(n: int, d: int) with {
+  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)
@@ -396,8 +1339,8 @@ class Rational(n: Int, d: Int) with {
   }
   private val g = gcd(n, d);
 
-  val numer: Int = n/g;
-  val denom: Int = d/g;
+  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) =
@@ -447,7 +1390,7 @@ If a class does not mention a superclass in its definition, the root
 class \verb@Object@ is implicitly assumed. For instance, class
 \verb@Rational@ could equivalently be defined as
 \begin{verbatim}
-class Rational(n: Int, d: Int) extends Object with {
+class Rational(n: int, d: int) extends Object with {
   ... // as before
 }
 \end{verbatim}
@@ -467,7 +1410,7 @@ 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 in order to get a more useful behavior:
 \begin{verbatim}
-class Rational(n: Int, d: Int) extends Object with {
+class Rational(n: int, d: int) extends Object with {
   ... // as before
   override def toString() = numer + "/" + denom;
 }
@@ -476,7 +1419,7 @@ Note that, unlike in Java, redefining definitions need to be preceded
 by an \verb@override@ modifier.
 
 If class $A$ extends class $B$, then objects of type $A$ may be used
-whereever objects of type $B$ are expected. We say in this case that
+wherever objects of type $B$ are expected. We say in this case that
 type $A$ {\em conforms} to type $B$.  For instance, \verb@Rational@
 conforms to \verb@Object@, so it is legal to assign a \verb@Rational@
 value to a variable of type \verb@Object@:
@@ -496,7 +1439,7 @@ Also unlike in Java, methods in Scala do not necessarily take a
 parameter list. An example is \verb@square@; the method is invoked by
 simply mentioning its name. For instance:
 \begin{verbatim}
-class Rational(n: Int, d: Int) extends Object with {
+class Rational(n: int, d: int) extends Object with {
   ... // as before
   def square = Rational(numer*numer, denom*denom);
 }
@@ -528,7 +1471,7 @@ comparison operators \verb@<, >, <=, >=@.
 %\end{verbatim}
 \begin{verbatim}
 abstract class Ord with {
-  def <(that: this): Boolean;
+  def <(that: this): boolean;
   def <=(that: this)  =  this < that || this == that;
   def >(that: this)  =  that < this;
   def >=(that: this)  =  that <= this;
@@ -553,11 +1496,11 @@ compatible with the class being defined (\verb@Ord@ in this case).
 We can now define a class of \verb@Rational@ numbers that
 support comparison operators.
 \begin{verbatim}
-final class OrderedRational(n: Int, d: Int)
+final class OrderedRational(n: int, d: int)
  extends Rational(n, d) with Ord with {
   override def ==(that: OrderedRational) =
     numer == that.numer && denom == that.denom;
-  def <(that: OrderedRational): Boolean =
+  def <(that: OrderedRational): boolean =
     numer * that.denom < that.numer * denom;
 }
 \end{verbatim}
@@ -568,7 +1511,7 @@ addition, it inherits all members of class \verb@Rational@ and all
 non-abstract members of class \verb@Ord@. The implementations of
 \verb@==@ and \verb@<@ replace the definition of \verb@==@ in class
 \verb@Object@ and the abstract declaration of \verb@<@ in class
-\verb@Ord@. The other inherited comparsion methods then refer to this
+\verb@Ord@. The other inherited comparison methods then refer to this
 implementation in their body.
 
 The clause ``\verb@Rational(d, d) with Ord@'' is an instance of {\em
@@ -613,10 +1556,10 @@ type parameters with iterators as an example. An iterator is an object
 which traverses a sequence of values, using two abstract methods.
 \begin{verbatim}
 abstract class Iterator[a] with {
-  def hasNext: Boolean;
+  def hasNext: boolean;
   def next: a;
 \end{verbatim}
-Method \verb@next@ returns succesive elements.  Method \verb@hasNext@
+Method \verb@next@ returns successive elements.  Method \verb@hasNext@
 indicates whether there are still more elements to be returned by
 \verb@next@. The type of elements returned by an iterator is
 arbitrary. We express that by giving the class \verb@Iterator@ the
@@ -626,9 +1569,9 @@ parentheses.  Iterators also support other methods, which are
 explained in the following.
 
 Method \verb@foreach@ applies a procedure (i.e. a function
-returning \verb@Unit@ to each element returned by the iterator:
+returning \verb@unit@ to each element returned by the iterator:
 \begin{verbatim}
-  def foreach(f: (a)Unit): Unit =
+  def foreach(f: a => unit): unit =
     while (hasNext) { f(next) }
 \end{verbatim}
 
@@ -643,7 +1586,7 @@ given iterator \verb@it@ after the current iterator has finished.
 The terms \verb@outer.next@ and \verb@outer.hasNext@ in the definition
 of \verb@append@ call the corresponding methods as they are defined in
 the enclosing \verb@Iterator@ class. Generally, an
-\verb@outer@ prefix in a selection indicates an identifer that is
+\verb@outer@ prefix in a selection indicates an identifier that is
 visible immediately outside the current class or template. If the
 \verb@outer@ prefix would have been missing,
 \verb@hasNext@ and \verb@next@ would have
@@ -653,25 +1596,25 @@ constructed by \verb@append@, which is not what we want.
 Method \verb@filter@ constructs an iterator which returns all elements
 of the original iterator that satisfy a criterion \verb@p@.
 \begin{verbatim}
-  def filter(p: (a)Boolean) = new Iterator[a] with {
+  def filter(p: a => boolean) = new Iterator[a] with {
     private class Cell[T](elem_: T) with { def elem = elem_; }
     private var head: Cell[a] = null;
-    private var isAhead = False;
-    def hasNext: Boolean =
-      if (isAhead) True
+    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;
+      else false;
     def next: a =
-      if (hasNext) { isAhead = False; head.elem }
+      if (hasNext) { isAhead = false; head.elem }
       else error("next on empty iterator");
   }
 \end{verbatim}
 Method \verb@map@ constructs an iterator which returns all elements of
 the original iterator transformed by a given function \verb@f@.
 \begin{verbatim}
-  def map[b](f: (a)b) = new Iterator[b] with {
-    def hasNext: Boolean = outer.hasNext;
+  def map[b](f: a => b) = new Iterator[b] with {
+    def hasNext: boolean = outer.hasNext;
     def next: b = f(outer.next);
   }
 \end{verbatim}
@@ -686,10 +1629,10 @@ The result of \verb@flatMap@ is the iterator resulting from appending
 together all iterators returned from successive calls of \verb@f@.
 \begin{verbatim}
     private var cur: Iterator[b] = new EmptyIterator[b];
-    def hasNext: Boolean =
-      if (cur.hasNext) True
+    def hasNext: boolean =
+      if (cur.hasNext) true
       else if (outer.hasNext) { cur = f(outer.next); hasNext }
-      else False;
+      else false;
     def next: b =
       if (cur.hasNext) cur.next
       else if (outer.hasNext) { cur = f(outer.next); next }
@@ -712,7 +1655,7 @@ abstract methods \verb@next@ and \verb@hasNext@ in class
 which always returns an empty sequence:
 \begin{verbatim}
 class EmptyIterator[a] extends Iterator[a] with {
-  def hasNext = False;
+  def hasNext = false;
   def next: a = error("next on empty iterator");
 }
 \end{verbatim}
@@ -724,7 +1667,7 @@ types, whereas functions do not.
 \begin{verbatim}
 def arrayIterator[a](xs: Array[a]) = new Iterator[a] with {
   private var i = 0;
-  def hasNext: Boolean =
+  def hasNext: boolean =
     i < xs.length;
   def next: a =
     if (i < xs.length) { val x = xs(i) ; i = i + 1 ; x }
@@ -733,11 +1676,11 @@ def arrayIterator[a](xs: Array[a]) = new Iterator[a] with {
 \end{verbatim}
 Another iterator enumerates an integer interval:
 \begin{verbatim}
-def range(lo: Int, hi: Int) = new Iterator[Int] with {
+def range(lo: int, hi: int) = new Iterator[int] with {
   private var i = lo;
-  def hasNext: Boolean =
+  def hasNext: boolean =
     i <= hi;
-  def next: Int =
+  def next: int =
     if (i <= hi) { i = i + 1 ; i - 1 }
     else error("next on empty iterator");
 }
@@ -745,46 +1688,46 @@ def range(lo: Int, hi: Int) = new Iterator[Int] with {
 %In fact, enumerating integer intervals is so common that it is
 %supported by a method
 %\begin{verbatim}
-%def to(hi: Int): Iterator[Int]
+%def to(hi: int): Iterator[int]
 %\end{verbatim}
-%in class \verb@Int@. Hence, one could also write \verb@l to h@ instead of
+%in class \verb@int@. Hence, one could also write \verb@l to h@ instead of
 %\verb@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},
+value\footnote{Due to the finite representation of type \prog{int},
 numbers will wrap around at $2^31$.}.
 \begin{verbatim}
-def from(start: Int) = new Iterator[Int] with {
+def from(start: int) = new Iterator[int] with {
   private var last = start - 1;
-  def hasNext = True;
+  def hasNext = true;
   def next = { last = last + 1; last }
 }
 \end{verbatim}
 Here are two examples how iterators are used. First, to print all
-elements of an array \verb@xs: Array[Int]@, one can write:
+elements of an array \verb@xs: Array[int]@, one can write:
 \begin{verbatim}
-  arrayIterator[Int](xs) foreach (x => System.out.println(x))
+  arrayIterator[int](xs) foreach (x => System.out.println(x))
 \end{verbatim}
-Here, \verb@[Int]@ is a type argument clause, which matches the type
+Here, \verb@[int]@ is a type argument clause, which matches the type
 parameter clause \verb@[a]@ of function \verb@arrayIterator@. It
-substitutes the formal argument \verb@Int@ for the formal argument
+substitutes the formal argument \verb@int@ for the formal argument
 \verb@a@ in the type of the method that follows. Hence,
-\verb@arrayIterator[a]@ is a function that takes an \verb@Array[Int]@
-and that returns an \verb@Iterator[Int]@.
+\verb@arrayIterator[a]@ is a function that takes an \verb@Array[int]@
+and that returns an \verb@Iterator[int]@.
 
-In this example, the formal type argument \verb@Int@ is redundant
+In this example, the formal type argument \verb@int@ is redundant
 since it could also have been inferred from the value \verb@xs@, which
-is, after all, an array of \verb@Int@. The Scala compiler contains a
+is, after all, an array of \verb@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 \verb@[Int]@ clause can be
+expected return type. In our example, the \verb@[int]@ clause can be
 inferred, so that one can abbreviate to:
 \begin{verbatim}
   arrayIterator(xs) foreach (x => System.out.println(x))
 \end{verbatim}
 %As a second example, consider the problem of finding the indices of
-%all the elements in an array of \verb@Double@s greater than some
+%all the elements in an array of \verb@double@s greater than some
 %\verb@limit@. The indices should be returned as an iterator.
 %This is achieved by the following expression.
 %\begin{verbatim}
@@ -837,8 +1780,8 @@ Here, \verb@s@ is a sequence of {\em generators} and {\em filters}.
 \item A {\em generator} is of the form \verb@val x <- e@,
 where \verb@e@ is a list-valued expression. It binds \verb@x@ to
 successive values in the list.
-\item A {\em filter} is an expression \verb@f@ of type \verb@Boolean@.
-It omits from consideration all bindings for which \verb@f@ is \verb@False@.
+\item A {\em filter} is an expression \verb@f@ of type \verb@boolean@.
+It omits from consideration all bindings for which \verb@f@ is \verb@false@.
 \end{itemize}
 The sequence must start with a generator.
 If there are several generators in a sequence, later generators vary
@@ -1003,10 +1946,10 @@ other types as well -- one only needs to define \verb@map@,
 That's also why we were able to define \verb@for@ at the same time for
 arrays, iterators, and lists -- all these types have the required
 three methods \verb@map@,\verb@flatMap@, and \verb@filter@ as members.
-Of course, it is also possible for users and librariy designers to
+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-comprehesnions can be used in the
+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.
 
@@ -1020,7 +1963,7 @@ branch nodes:
 \begin{verbatim}
 abstract class Tree;
 case class Branch(left: Tree, right: Tree) extends Tree;
-case class Leaf(x: Int) extends Tree;
+case class Leaf(x: int) extends Tree;
 \end{verbatim}
 Note that the class \verb@Tree@ is not followed by an extends
 clause or a body. This defines \verb@Tree@ to be an empty
@@ -1038,7 +1981,7 @@ val tree1 = Branch(Branch(Leaf(1), Leaf(2)), Branch(Leaf(3), Leaf(4)))
 Second, it lets us use constructors for these classes in patterns, as
 is illustrated in the following example.
 \begin{verbatim}
-def sumLeaves(t: Tree): Int = t match {
+def sumLeaves(t: Tree): int = t match {
   case Branch(l, r) => sumLeaves(l) + sumLeaves(r)
   case Leaf(x) => x
 }
@@ -1095,8 +2038,8 @@ find(xs, x) match {
 
 
 class MaxCounter with {
-  var maxVal: Option[Int] = None;
-  def set(x: Int) = maxVal match {
+  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))
   }
@@ -1128,7 +2071,7 @@ In each case, a search tree package is seen as an implementation
 of a class {\em MapStruct}.
 \begin{verbatim}
 abstract class MapStruct[kt, vt] with {
-  abstract type Map extends (kt)vt with {
+  abstract type Map extends kt => vt with {
     def apply(key: kt): vt;
     def extend(key: kt, value: vt): Map;
     def remove(key: kt): Map;
@@ -1143,7 +2086,7 @@ The \verb@MapStruct@ class is parameterized with a type of keys
 specifies an abstract type \verb@Map@ and an abstract value
 \verb@empty@, which represents empty maps.  Every implementation
 \verb@Map@ needs to conform to that abstract type, which
-extends the function type \verb@(kt)vt@
+extends the function type \verb@kt => vt@
 with four new
 methods. The method \verb@domain@ yields a stream that enumerates the
 map's domain, i.e. the set of keys that are mapped to non-null values.
@@ -1162,7 +2105,7 @@ class AlgBinTree[kt extends Ord, vt] extends MapStruct[kt, vt] with {
     Empty extends Map,
     Node(key: kt, value: vt, l: Map, r: Map) extends Map
 
-  final class Map extends (kt)vt with {
+  final class Map extends kt => vt with {
     def apply(key: kt): vt = this match {
       case Empty => null
       case Node(k, v, l, r) =>
@@ -1233,7 +2176,7 @@ are constructed lazily.
 \begin{figure}[thb]
 \begin{verbatim}
 class OOBinTree[kt extends Ord, vt] extends MapStruct[kt, vt] with {
-  abstract class Map extends (kt)vt with {
+  abstract class Map extends kt => vt with {
     def apply(key: kt): v
     def extend(key: kt, value: vt): Map
     def remove(key: kt): Map
@@ -1301,7 +2244,7 @@ modified.
 \begin{figure}
 \begin{verbatim}
 class MutBinTree[kt extends Ord, vt] extends MapStruct[kt, vt] with {
-  class Map(key: kt, value: vt) extends (kt)vt with {
+  class Map(key: kt, value: vt) extends kt => vt with {
     val k = key
     var v = value
     var l = empty, r = empty
@@ -1374,7 +2317,7 @@ As a program using the \verb@MapStruct@ abstraction, consider a function
 which creates a map from strings to integers and then applies it to a
 key string:
 \begin{verbatim}
-def mapTest(def mapImpl: MapStruct[String, Int]): Int = {
+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
 }
@@ -1383,9 +2326,9 @@ The function is parameterized with the particular implementation of
 \verb@MapStruct@. It can be applied to any one of the three implementations
 described above. E.g.:
 \begin{verbatim}
-mapTest(AlgBinTree[String, Int])
-mapTest(OOBinTree[String, Int])
-mapTest(MutBinTree[String, Int])
+mapTest(AlgBinTree[String, int])
+mapTest(OOBinTree[String, int])
+mapTest(MutBinTree[String, int])
 \end{verbatim}
 }
 \chapter{Programming with Higher-Order Functions: Combinator Parsing}
@@ -1426,10 +2369,10 @@ also define constructors for the following primitive parsers:
 \\
 \verb@chr@      & The parser that accepts any character.
 \\
-\verb@chr(c: Char)@
+\verb@chr(c: char)@
 		& The parser that accepts the single-character string ``$c$''.
 \\
-\verb@chrWith(p: (Char)Boolean)@
+\verb@chrWith(p: char => boolean)@
 		& The parser that accepts single-character strings
                   ``$c$'' \\
 	        & for which $p(c)$ is true.
@@ -1475,9 +2418,9 @@ parameter and that yield a parse result.
 \begin{verbatim}
 module Parse with {
 
-  type Result = Option[List[Char]];
+  type Result = Option[List[char]];
 
-  abstract class Parser extends Function1[List[Char],Result] with {
+  abstract class Parser extends Function1[List[char],Result] with {
 \end{verbatim}
 \comment{
 The \verb@Option@ type is predefined as follows.
@@ -1492,25 +2435,25 @@ signifies that the parser did not recognize a legal input string, or
 it returns a value \verb@Some(in1)@ where \verb@in1@ represents that
 part of the input list that the parser did not consume.
 
-Parsers are instances of functions from \verb@List[Char]@ to
+Parsers are instances of functions from \verb@List[char]@ to
 \verb@Parse.Result@, which also implement the combinators
-for sequence and alternative. This is modelled by
+for sequence and alternative. This is modeled by
 defining \verb@Parser@ as a class that extends type
-\verb@Function1[List[Char],Result]@ and that defines an \verb@apply@
+\verb@Function1[List[char],Result]@ and that defines an \verb@apply@
 method, as well as methods \verb@&&&@ and \verb@|||@.
 \begin{verbatim}
-    abstract def apply(in: List[Char]): Result;
+    abstract def apply(in: List[char]): Result;
 \end{verbatim}
 \begin{verbatim}
     def &&& (def p: Parser) = new Parser with {
-      def apply(in: List[Char]) = outer.apply(in) match {
+      def apply(in: List[char]) = outer.apply(in) match {
         case Some(in1) => p(in1)
         case n => n
       }
     }
 
     def ||| (def p: Parser) = new Parser with {
-      def apply(in: List[Char]) = outer.apply(in) match {
+      def apply(in: List[char]) = outer.apply(in) match {
         case None => p(in)
         case s => s
       }
@@ -1521,18 +2464,18 @@ The implementations of the primitive parsers \verb@empty@, \verb@fail@,
 \verb@chrWith@ and \verb@chr@ are as follows.
 \begin{verbatim}
 
-  def empty = new Parser with { def apply(in: List[Char]) = Some(in) }
+  def empty = new Parser with { def apply(in: List[char]) = Some(in) }
 
-  def fail = new Parser with { def apply(in: List[Char]) = None[List[Char]] }
+  def fail = new Parser with { def apply(in: List[char]) = None[List[char]] }
 
-  def chrWith(p: (Char)Boolean) = new Parser with {
-    def apply(in: List[Char]) = in match {
-      case [] => None[List[Char]]
-      case (c :: in1) => if (p(c)) Some(in1) else None[List[Char]]
+  def chrWith(p: char => boolean) = new Parser with {
+    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);
+  def chr(c: char): Parser = chrWith(d => d == c);
 \end{verbatim}
 The higher-order parser combinators \verb@opt@ and \verb@rep@ can be
 defined in terms of the combinators for sequence and alternative:
@@ -1579,8 +2522,8 @@ tree of the parsed expression. The class of syntax trees is given by:
 \begin{verbatim}
 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;
+case class Num(n: int) extends Tree;
+case class Binop(op: char, l: Tree, r: Tree) extends Tree;
 \end{verbatim}
 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
@@ -1591,14 +2534,14 @@ modify the ``micro-syntax'' parsers \verb@letter@, \verb@digit@,
 \verb@ident@ and \verb@number@ so that they return representations of
 the parsed input:
 \begin{verbatim}
-def letter: Parser[Char] = chrWith(c => c.isLetter);
-def digit : Parser[Char] = chrWith(c => c.isDigit);
+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] =
+def number: Parser[int] =
   for (val d <- digit; val ds <- rep(digit))
   yield ((d - '0') :_foldl ds) {x, y => x * 10 + (y - '0')};
 \end{verbatim}
@@ -1616,7 +2559,7 @@ def expr: Parser[Tree] =
       for {
         val op <- chr('+') ||| chr('-');
 	val e <- expr1
-      } yield (x => Binop(op, x, e)) : (Tree)Tree
+      } yield (x => Binop(op, x, e)) : Tree => Tree
     )
   } yield applyAll(es, e1);
 \end{verbatim}
@@ -1628,7 +2571,7 @@ def expr1: Parser[Tree] =
       for {
         val op <- chr('*') ||| chr('/');
         val e <- expr2
-      } yield (x => Binop(op, x, e)) : (Tree)Tree
+      } yield (x => Binop(op, x, e)) : Tree => Tree
     )
   } yield applyAll(es, e1);
 \end{verbatim}
@@ -1649,7 +2592,7 @@ to the first operand in the sequence, which is represented by
 \verb@e1@. Here \verb@applyAll@ applies the list of functions passed as its first
 argument to its second argument. It is defined as follows.
 \begin{verbatim}
-def applyAll[a](fs: List[(a)a], e: a): a =
+def applyAll[a](fs: List[a => a], e: a): a =
   (e :_foldl fs) { x, f => f(x) }
 \end{verbatim}
 We now present the parser combinators that support the new
@@ -1658,7 +2601,7 @@ un-consumed input.
 \begin{verbatim}
 module Parse with {
 
-  type Result[a] = Option[(a, List[Char])]
+  type Result[a] = Option[(a, List[char])]
 \end{verbatim}
 Parsers are parameterized with the type of their result. The class
 \verb@Parser[a]@ now defines new methods \verb@map@, \verb@flatMap@
@@ -1668,33 +2611,33 @@ Chapter~\ref{sec:for-notation}.
 
 Here is the complete definition of the new \verb@Parser@ class.
 \begin{verbatim}
-  abstract class Parser[a] extends Function1[List[Char],Result[a]] with {
+  abstract class Parser[a] extends Function1[List[char],Result[a]] with {
 
-    def apply(in: List[Char]): Result[a];
+    def apply(in: List[char]): Result[a];
 
-    def filter(p: (a)Boolean) = new Parser[a] with {
-      def apply(in: List[Char]): Result[a] = outer.apply(in) match {
+    def filter(p: a => boolean) = new Parser[a] with {
+      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] with {
-      def apply(in: List[Char]): Result[b] = outer.apply(in) match {
+    def map[b](f: a => b) = new Parser[b] with {
+      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] with {
-      def apply(in: List[Char]): Result[b] = outer.apply(in) match {
+    def flatMap[b](f: a => Parser[b]) = new Parser[b] with {
+      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] with {
-      def apply(in: List[Char]): Result[a] = outer.apply(in) match {
+      def apply(in: List[char]): Result[a] = outer.apply(in) match {
 	case None => p(in)
 	case s => s
       }
@@ -1719,22 +2662,22 @@ the current parser and then continues with the resulting parser.  The
 % Here is the code for fail, chrWith and chr
 %
 %\begin{verbatim}
-%  def fail[a] = new Parser[a] with { def apply(in: List[Char]) = None[(a,List[Char])] }
+%  def fail[a] = new Parser[a] with { def apply(in: List[char]) = None[(a,List[char])] }
 %
-%  def chrWith(p: (Char)Boolean) = new Parser[Char] with {
-%    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 chrWith(p: char => boolean) = new Parser[char] with {
+%    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);
+%  def chr(c: char): Parser[char] = chrWith(d => d == c);
 %\end{verbatim}
 The primitive parser \verb@succeed@ replaces \verb@empty@. It consumes
 no input and returns its parameter as result.
 \begin{verbatim}
   def succeed[a](x: a) = new Parser[a] with {
-    def apply(in: List[Char]) = Some((x, in))
+    def apply(in: List[char]) = Some((x, in))
   }
 \end{verbatim}
 The \verb@fail@ parser is as before.  The parser combinators
@@ -1784,16 +2727,16 @@ module Types with {
   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;
+  private var n: int = 0;
   def newTyvar: Type = { n = n + 1 ; Tyvar("a" + n) }
 }
 import Types;
 \end{verbatim}
 There are three type constructors: \verb@Tyvar@ for type variables,
 \verb@Arrow@ for function types and \verb@Tycon@ for type
-constructors such as \verb@Boolean@ or \verb@List@. Type constructors
+constructors such as \verb@boolean@ or \verb@List@. Type constructors
 have as component a list of their type parameters. This list is empty
-for type constants such as \verb@Boolean@. The data type is packaged
+for type constants such as \verb@boolean@. The data type is packaged
 in a module \verb@Types@. Also contained in that module is a function
 \verb@newTyvar@ which creates a fresh type variable each time it is
 called. The module definition is followed by an import clause
@@ -1854,7 +2797,7 @@ abstract class Subst extends Function1[Type,Type] with {
 case class EmptySubst extends Subst with { def lookup(t: Tyvar): Type = t }
 \end{verbatim}
 We represent substitutions as functions, of type
-\verb@(Type)Type@. To be an instance of this type, a
+\verb@Type => Type@. To be an instance of this type, a
 substitution \verb@s@ has to implement an \verb@apply@ method that takes a
 \verb@Type@ as argument and yields another \verb@Type@ as result. A function
 application \verb@s(t)@ is then interpreted as \verb@s.apply(t)@.
@@ -1872,8 +2815,8 @@ implementation of sets in some standard library.
 class ListSet[a](xs: List[a]) with {
   val elems: List[a] = xs;
 
-  def contains(y: a): Boolean = xs match {
-    case [] => False
+  def contains(y: a): boolean = xs match {
+    case [] => false
     case x :: xs1 => (x == y) || (xs1 contains y)
   }
 
@@ -1906,7 +2849,7 @@ module TypeChecker with {
   type Env = List[(String, TypeScheme)];
 \end{verbatim}
 There is also an exception \verb@TypeError@, which is thrown when type
-checking fails. Exceptions are modelled as case classes that inherit
+checking fails. Exceptions are modeled as case classes that inherit
 from the predefined \verb@Exception@ class.
 \begin{verbatim}
   case class TypeError(msg: String) extends Exception(msg);
@@ -1986,7 +2929,7 @@ The main task of the type checker is implemented by function
 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 judgement according
+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
 \verb@TypeError@ exception is thrown if no such substitution exists.
 \begin{verbatim}
@@ -2018,7 +2961,7 @@ The next function, \verb@typeOf@ is a simplified facade for
 \verb@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 \verb@env $\ts$ e: a@ into
-a derivable type judgement, and finally by returning the result of
+a derivable type judgment, and finally by returning the result of
 applying the substitution to $a$.
 \begin{verbatim}
   def typeOf(env: Env, e: Term): Type = {
@@ -2073,7 +3016,7 @@ would give the response
 > TypeScheme([a0], Arrow(Tyvar(a0), Tycon("List", [Tyvar(a0)])));
 \end{verbatim}
 
-\paragraph{Exercise:}
+\exercise
 Add \verb@toString@ methods to the data constructors of class
 \verb@Type@ and \verb@TypeScheme@ which represent types in a more
 natural way.
@@ -2085,7 +3028,8 @@ how they can be implemented in Scala.
 
 \section{Signals and Monitors}
 
-\example Th {\em monitor} provides the basic means for mutual exclusion
+\example
+The {\em monitor} provides the basic means for mutual exclusion
 of processes in Scala. It is defined as follows.
 \begin{verbatim}
 class Monitor with {
@@ -2106,15 +3050,15 @@ signal are ignored. Here is the specification of the \verb@Signal@
 class.
 \begin{verbatim}
 class Signal with {
-  def wait: Unit;
-  def wait(msec: Long): Unit;
-  def notify: Unit;
-  def notifyAll: Unit;
+  def wait: unit;
+  def wait(msec: long): unit;
+  def notify: unit;
+  def notifyAll: unit;
 }
 \end{verbatim}
 A signal also implements a timed form of \verb@wait@, which blocks
-only as long as no signal was recieved or the specified amount of time
-(given in milliseconds) has elaosed. Furthermore, there is a
+only as long as no signal was received or the specified amount of time
+(given in milliseconds) has elapsed. Furthermore, there is a
 \verb@notifyAll@ method which unblocks all threads which wait for the
 signal. \verb@Signal@ and \verb@Monitor@ are primitive classes in
 Scala which are implemented in terms of the underlying runtime system.
@@ -2148,13 +3092,13 @@ And here is a program using a bounded buffer to communicate between a
 producer and a consumer process.
 \begin{verbatim}
 val buf = new BoundedBuffer[String](10)
-fork { while (True) { val s = produceString ; buf.put(s) } }
-fork { while (True) { val s = buf.get ; consumeString(s) } }
+fork { while (true) { val s = produceString ; buf.put(s) } }
+fork { while (true) { val s = buf.get ; consumeString(s) } }
 \end{verbatim}
 The \verb@fork@ method spawns a new thread which executes the
 expression given in the parameter. It can be defined as follows.
 \begin{verbatim}
-def fork(def e: Unit) = {
+def fork(def e: unit) = {
   val p = new Thread with { def run = e; }
   p.run
 }
@@ -2173,14 +3117,14 @@ Logic variables can be implemented as follows.
 \begin{verbatim}
 class LVar[a] extends Monitor with {
   private val defined = new Signal
-  private var isDefined: Boolean = False
+  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
+    v = x ; isDefined = true ; defined.send
   }
 }
 \end{verbatim}
@@ -2197,19 +3141,19 @@ Synchronized variables can be implemented as follows.
 \begin{verbatim}
 class SyncVar[a] extends Monitor with {
   private val defined = new Signal;
-  private var isDefined: Boolean = False;
+  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;
+    value = x ; isDefined = true ; defined.send;
   }
-  def isSet: Boolean =
+  def isSet: boolean =
     isDefined;
   def unset = synchronized {
-    isDefined = False;
+    isDefined = false;
   }
 }
 \end{verbatim}
@@ -2231,7 +3175,7 @@ val y = f(x()) + g(x());
 Futures can be implemented in Scala as follows.
 
 \begin{verbatim}
-def future[a](def p: a): (Unit)a = {
+def future[a](def p: a): unit => a = {
   val result = new SyncVar[a];
   fork { result.set(p) }
   (=> result.get)
@@ -2271,7 +3215,7 @@ number of replicates of a computation in parallel. Each
 replication instance is passed an integer number which identifies it.
 
 \begin{verbatim}
-def replicate(start: Int, end: Int)(def p: (Int)Unit): Unit = {
+def replicate(start: int, end: int)(def p: int => unit): unit = {
   if (start == end) {
   } else if (start + 1 == end) {
     p(start)
@@ -2286,7 +3230,7 @@ The next example shows how to use \verb@replicate@ to perform parallel
 computations on all elements of an array.
 
 \begin{verbatim}
-def parMap[a,b](f: (a)b, xs: Array[a]): Array[b] = {
+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
@@ -2301,13 +3245,13 @@ A common mechanism for process synchronization is a {\em lock} (or:
 
 \begin{verbatim}
 class Lock extends Monitor with Signal with {
-  var available = True;
+  var available = true;
   def acquire = {
     if (!available) wait;
-    available = False
+    available = false
   }
   def release = {
-    available = True;
+    available = true;
     notify
   }
 }
@@ -2332,7 +3276,7 @@ The following implementation of a readers/writers lock is based on the
 \begin{verbatim}
 class ReadersWriters with {
   val m = new MessageSpace;
-  private case class Writers(n: Int), Readers(n: Int);
+  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 {
@@ -2357,7 +3301,7 @@ class ReadersWriters with {
 
 \section{Asynchronous Channels}
 
-A fundamental way of interprocess comunication is the asynchronous
+A fundamental way of interprocess communication is the asynchronous
 channel. Its implementation makes use the following class for linked
 lists:
 \begin{verbatim}
@@ -2366,7 +3310,7 @@ class LinkedList[a](x: a) with {
   var next: LinkedList[a] = null;
 }
 \end{verbatim}
-To facilite insertion and deletion of elements into linked lists,
+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 \verb@null@.
@@ -2404,7 +3348,7 @@ three signals are used to coordinate reader and writer processes.
 class SyncChannel[a] with {
   val data = new SyncVar[a];
 
-  def write(x: a): Unit = synchronized {
+  def write(x: a): unit = synchronized {
     val empty = new Signal, full = new Signal, idle = new Signal;
     if (data.isSet) idle.wait;
     data.put(x);
@@ -2435,24 +3379,24 @@ the overhead inherent in context-switching several threads on a single
 processor.
 
 \begin{verbatim}
-class ComputeServer(n: Int) {
+class ComputeServer(n: int) {
   private abstract class Job with {
     abstract type t;
     def task: t;
-    def return(x: t): Unit;
+    def return(x: t): unit;
   }
 
   private val openJobs = new Channel[Job]
 
-  private def processor: Unit = {
-    while (True) {
+  private def processor: unit = {
+    while (true) {
       val job = openJobs.read;
       job.return(job.task)
     }
   }
 \end{verbatim}
 \begin{verbatim}
-  def future[a](def p: a): ()a = {
+  def future[a](def p: a): () => a = {
     val reply = new SyncVar[a];
     openJobs.write(
       new Job with {
@@ -2511,9 +3455,9 @@ case class TIMEOUT;
 Message spaces implement the following signature.
 \begin{verbatim}
 class MessageSpace with {
-  def send(msg: Any): Unit;
+  def send(msg: Any): unit;
   def receive[a](f: PartialFunction[Any, a]): a;
-  def receiveWithin[a](msec: Long)(f: PartialFunction[Any, a]): a;
+  def receiveWithin[a](msec: long)(f: PartialFunction[Any, a]): a;
 }
 \end{verbatim}
 The state of a message space consists of a multi-set of messages.
@@ -2536,14 +3480,14 @@ one-place buffer:
 \begin{verbatim}
 class OnePlaceBuffer with {
   private val m = new MessageSpace;        \=// An internal message space
-  private case class Empty, Full(x: Int);    \>// Types of messages we deal with
+  private case class Empty, Full(x: int);    \>// Types of messages we deal with
 
   m send Empty;                           \>// Initialization
 
-  def write(x: Int): Unit =
+  def write(x: int): unit =
     m receive { case Empty => m send Full(x) }
 
-  def read: Int =
+  def read: int =
     m receive { case Full(x) => m send Empty ; x }
 }
 \end{verbatim}
@@ -2552,7 +3496,7 @@ Here's how the message space class can be implemented:
 class MessageSpace with {
 
   private abstract class Receiver extends Signal with {
-    def isDefined(msg: Any): Boolean;
+    def isDefined(msg: Any): boolean;
     var msg = null;
   }
 \end{verbatim}
@@ -2572,7 +3516,7 @@ needs to be applied to is stored in the \verb@msg@ variable of
 The message space class maintains two linked lists,
 one for sent but unconsumed messages, the other for waiting receivers.
 \begin{verbatim}
-  def send(msg: Any): Unit = synchronized {
+  def send(msg: Any): unit = synchronized {
     var r = receivers, r1 = r.next;
     while (r1 != null && !r1.elem.isDefined(msg)) {
       r = r1; r1 = r1.next;
@@ -2615,8 +3559,8 @@ The \verb@receive@ method first checks whether the message processor function
 was not yet consumed. If yes, the thread continues immediately by
 applying \verb@f@ to the message. Otherwise, a new receiver is created
 and linked into the \verb@receivers@ list, and the thread waits for a
-notification on this receiver. Once the thrad is woken up again, it
-continues by applying \verb@f@ to the message that was stored in te receiver.
+notification on this receiver. Once the thread is woken up again, it
+continues by applying \verb@f@ to the message that was stored in the receiver.
 
 The message space class also offers a method \verb@receiveWithin@
 which blocks for only a specified maximal amount of time.  If no
@@ -2625,7 +3569,7 @@ milliseconds), the message processor argument $f$ will be unblocked
 with the special \verb@TIMEOUT@ message.  The implementation of
 \verb@receiveWithin@ is quite similar to \verb@receive@:
 \begin{verbatim}
-  def receiveWithin[a](msec: Long)(f: PartialFunction[Any, a]): a = {
+  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)) {
@@ -2670,18 +3614,18 @@ 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}[h]
+\begin{figure}[thb]
 \begin{verbatim}
 class AuctionMessage;
 case class
-  \=Offer(bid: Int, client: Process),                             \=// make a bid
+  \=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
+  \=Status(asked; int, expiration: Date),   \>// asked sum, expiration date
      \>BestOffer,                                       \>// yours is the best offer
-     \>BeatenOffer(maxBid: Int),                        \>// offer beaten by maxBid
+     \>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
@@ -2689,7 +3633,7 @@ case class
 \end{figure}
 
 \begin{verbatim}
-class Auction(seller: Process, minBid: Int, closing: Date)
+class Auction(seller: Process, minBid: int, closing: Date)
  extends Process with {
 
   val timeToShutdown = 36000000 // msec
@@ -2699,7 +3643,7 @@ class Auction(seller: Process, minBid: Int, closing: Date)
   def run = {
     var askedBid = minBid
     var maxBidder: Process = null
-    while (True) {
+    while (true) {
       receiveWithin ((closing - Date.currentDate).msec) {
 	case Offer(bid, client) => {
 	  if (bid >= askedBid) {
@@ -2709,9 +3653,7 @@ class Auction(seller: Process, minBid: Int, closing: Date)
             maxBidder = client
             askedBid = bid + delta
             client send BestOffer
-          } else {
-            client send BeatenOffer(maxBid)
-          }
+          } else client send BeatenOffer(maxBid)
         }
 \end{verbatim}
 \begin{verbatim}
@@ -2725,9 +3667,7 @@ class Auction(seller: Process, minBid: Int, closing: Date)
 	    val reply = AuctionConcluded(seller, maxBidder)
 	    maxBidder send reply
 	    seller send reply
-	  } else {
-	    seller send AuctionFailed
-          }
+	  } else seller send AuctionFailed
           receiveWithin (timeToShutdown) {
             case Offer(_, client) => client send AuctionOver ; discardAndContinue
             case _ => discardAndContinue
@@ -2742,9 +3682,9 @@ class Auction(seller: Process, minBid: Int, closing: Date)
   }
 \end{verbatim}
 \begin{verbatim}
-  def houseKeeping: Int = {
+  def houseKeeping: int = {
     val Limit = 100
-    var nWaiting: Int = 0
+    var nWaiting: int = 0
     receiveWithin(0) {
       case _ =>
         nWaiting = nWaiting + 1
@@ -2761,7 +3701,7 @@ class Auction(seller: Process, minBid: Int, closing: Date)
 }
 \end{verbatim}
 \begin{verbatim}
-class Bidder (auction: Process, minBid: Int, maxBid: Int)
+class Bidder (auction: Process, minBid: int, maxBid: int)
  extends Process with {
   val MaxTries = 3
   val Unknown = -1
@@ -2787,7 +3727,7 @@ class Bidder (auction: Process, minBid: Int, maxBid: Int)
   }
 \end{verbatim}
 \begin{verbatim}
-  def bid: Unit = {
+  def bid: unit = {
     if (nextBid < maxBid) {
       auction send Offer(nextBid, this)
       receive {
@@ -2818,7 +3758,7 @@ class Bidder (auction: Process, minBid: Int, maxBid: Int)
     if (nextBid != Unknown) bid
   }
 
-  def transferPayment(seller: Process, amount: Int)
+  def transferPayment(seller: Process, amount: int)
 }
 \end{verbatim}
 }
@@ -2854,7 +3794,7 @@ def sort(a:Array[String]): Array[String] = {
 
 def sort(a:Array[String]): Array[String] = {
 
-  def swap (i: Int, j: Int): unit = {
+  def swap (i: int, j: int): unit = {
     val t = a(i) ; a(i) = a(j) ; a(j) = t
   }
 
@@ -2884,7 +3824,7 @@ class Array[a] with {
   val apply(i: int): a
   val update(i: int, x: a): unit
 
-  def filter (p: a => Boolean): Array[a] = {
+  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) {