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