diff options
Diffstat (limited to 'doc/reference/ExamplesPart.tex')
| -rw-r--r-- | doc/reference/ExamplesPart.tex | 6862 |
1 files changed, 0 insertions, 6862 deletions
diff --git a/doc/reference/ExamplesPart.tex b/doc/reference/ExamplesPart.tex deleted file mode 100644 index c90ecffa24..0000000000 --- a/doc/reference/ExamplesPart.tex +++ /dev/null @@ -1,6862 +0,0 @@ -\def\exercise{ - \def\theresult{Exercise~\thesection.\arabic{result}} - \refstepcounter{result} - \trivlist\item[\hskip - \labelsep{\bf \theresult}]} -\def\endexercise{\endtrivlist} - -\newcommand{\rewriteby}[1]{\mbox{\tab\tab\rm(#1)}} - -\chapter{\label{chap:example-one}A First Example} - -As a first example, here is an implementation of Quicksort in Scala. - -\begin{lstlisting} -def sort(xs: Array[int]): unit = { - def swap(i: int, j: int): unit = { - val t = xs(i); xs(i) = xs(j); xs(j) = t; - } - def sort1(l: int, r: int): unit = { - val pivot = xs((l + r) / 2); - var i = l, j = r; - while (i <= j) { - while (xs(i) < pivot) { i = i + 1 } - while (xs(j) > pivot) { j = j - 1 } - if (i <= j) { - swap(i, j); - i = i + 1; - j = j - 1; - } - } - if (l < j) sort1(l, j); - if (j < r) sort1(i, r); - } - sort1(0, xs.length - 1); -} -\end{lstlisting} - -The implementation looks quite similar to what one would write in Java -or C. We use the same operators and similar control structures. -There are also some minor syntactical differences. In particular: -\begin{itemize} -\item -Definitions start with a reserved word. Function definitions start -with \code{def}, variable definitions start with \code{var} and -definitions of values (i.e. read only variables) start with \code{val}. -\item -The declared type of a symbol is given after the symbol and a colon. -The declared type can often be omitted, because the compiler can infer -it from the context. -\item -We use \code{unit} instead of \code{void} to define the result type of -a procedure. -\item -Array types are written \code{Array[T]} rather than \code{T[]}, -and array selections are written \code{a(i)} rather than \code{a[i]}. -\item -Functions can be nested inside other functions. Nested functions can -access parameters and local variables of enclosing functions. For -instance, the name of the array \code{a} is visible in functions -\code{swap} and \code{sort1}, and therefore need not be passed as a -parameter to them. -\end{itemize} -So far, Scala looks like a fairly conventional language with some -syntactic peculiarities. In fact it is possible to write programs in a -conventional imperative or object-oriented style. This is important -because it is one of the things that makes it easy to combine Scala -components with components written in mainstream languages such as -Java, C\# or Visual Basic. - -However, it is also possible to write programs in a style which looks -completely different. Here is Quicksort again, this time written in -functional style. - -\begin{lstlisting} -def sort(xs: List[int]): List[int] = - if (xs.length <= 1) xs - else { - val pivot = xs(xs.length / 2); - sort(xs.filter(x => x < pivot)) - ::: xs.filter(x => x == pivot) - ::: sort(xs.filter(x => x > pivot)) - } -\end{lstlisting} - -The functional program works with lists instead of arrays.\footnote{In -a future complete implementation of Scala, we could also have used arrays -instead of lists, but at the moment arrays do not yet support -\code{filter} and \code{:::}.} -It captures the essence of the quicksort algorithm in a concise way: -\begin{itemize} -\item If the list is empty or consists of a single element, - it is already sorted, so return it immediately. -\item If the list is not empty, pick an an element in the middle of - it 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 pivot. -\item Sort the first two sub-lists by a recursive invocation of -the sort function.\footnote{This is not quite what the imperative algorithm does; -the latter partitions the array into two sub-arrays containing elements -less than or greater or equal to pivot.} -\item The result is obtained by appending the three sub-lists together. -\end{itemize} -Both the imperative and the functional implementation have the same -asymptotic complexity -- $O(N;log(N))$ in the average case and -$O(N^2)$ in the worst case. But where the imperative implementation -operates in place by modifying the argument array, the functional -implementation returns a new sorted list and leaves the argument -list unchanged. The functional implementation thus requires more -transient memory than the imperative one. - -The functional implementation makes it look like Scala is a language -that's specialized for functional operations on lists. In fact, it -is not; all of the operations used in the example are simple library -methods of a class \code{List[t]} which is part of the standard -Scala library, and which itself is implemented in Scala. - -In particular, there is the method \code{filter} which takes as -argument a {\em predicate function} that maps list elements to -boolean values. The result of \code{filter} is a list consisting of -all the elements of the original list for which the given predicate -function is true. The \code{filter} method of an object of type -\code{List[t]} thus has the signature - -\begin{lstlisting} -def filter(p: t => boolean): List[t] -\end{lstlisting} - -Here, \code{t => boolean} is the type of functions that take an element -of type \code{t} and return a \code{boolean}. Functions like -\code{filter} that take another function as argument or return one as -result are called {\em higher-order} functions. - -In the quicksort program, \code{filter} is applied three times to an -anonymous function argument. The first argument, -\code{x => x <= pivot} represents the function that maps its parameter -\code{x} to the boolean value \code{x <= pivot}. That is, it yields -true if \code{x} is smaller or equal than \code{pivot}, false -otherwise. The function is anonymous, i.e.\ it is not defined with a -name. The type of the \code{x} parameter is omitted because a Scala -compiler can infer it automatically from the context where the -function is used. To summarize, \code{xs.filter(x => x <= pivot)} -returns a list consisting of all elements of the list \code{xs} that are -smaller than \code{pivot}. - -\comment{ -It is also possible to apply higher-order functions such as -\code{filter} to named function arguments. Here is functional -quicksort again, where the two anonymous functions are replaced by -named auxiliary functions that compare the argument to the -\code{pivot} value. - -\begin{lstlisting} -def sort (xs: List[int]): List[int] = { - val pivot = xs(xs.length / 2); - def leqPivot(x: int) = x <= pivot; - def gtPivot(x: int) = x > pivot; - def eqPivot(x: int) = x == pivot; - sort(xs filter leqPivot) - ::: sort(xs filter eqPivot) - ::: sort(xs filter gtPivot) -} -\end{lstlisting} -} - -An object of type \code{List[t]} also has a method ``\code{:::}'' -which takes an another list and which returns the result of appending this -list to itself. This method has the signature - -\begin{lstlisting} -def :::(that: List[t]): List[t] -\end{lstlisting} - -Scala does not distinguish between identifiers and operator names. An -identifier can be either a sequence of letters and digits which begins -with a letter, or it can be a sequence of special characters, such as -``\code{+}'', ``\code{*}'', or ``\code{:}''. The last definition thus -introduced a new method identifier ``\code{:::}''. This identifier is -used in the Quicksort example as a binary infix operator that connects -the two sub-lists resulting from the partition. In fact, any method -can be used as an operator in Scala. The binary operation $E;op;E'$ -is always interpreted as the method call $E.op(E')$. This holds also -for binary infix operators which start with a letter. The recursive call -to \code{sort} in the last quicksort example is thus equivalent to -\begin{lstlisting} -sort(a.filter(x => x < pivot)) - .:::(sort(a.filter(x => x == pivot))) - .:::(sort(a.filter(x => x > pivot))) -\end{lstlisting} - -Looking again in detail at the first, imperative implementation of -Quicksort, we find that many of the language constructs used in the -second solution are also present, albeit in a disguised form. - -For instance, ``standard'' binary operators such as \code{+}, -\code{-}, or \code{<} are not treated in any special way. Like -\code{append}, they are methods of their left operand. Consequently, -the expression \code{i + 1} is regarded as the invocation -\code{i.+(1)} of the \code{+} method of the integer value \code{x}. -Of course, a compiler is free (if it is moderately smart, even expected) -to recognize the special case of calling the \code{+} method over -integer arguments and to generate efficient inline code for it. - -For efficiency and better error diagnostics the \code{while} loop is a -primitive construct in Scala. But in principle, it could have just as -well been a predefined function. Here is a possible implementation of it: -\begin{lstlisting} -def While (p: => boolean) (s: => unit): unit = - if (p) { s ; While(p)(s) } -\end{lstlisting} -The \code{While} function takes as first parameter a test function, -which takes no parameters and yields a boolean value. As second -parameter it takes a command function which also takes no parameters -and yields a trivial result. \code{While} invokes the command function -as long as the test function yields true. - - -\chapter{Programming with Actors and Messages} -\label{chap:example-auction} - -Here's an example that shows an application area for which Scala is -particularly well suited. Consider the task of implementing an -electronic auction service. We use an Erlang-style actor process -model to implement the participants of the auction. Actors are -objects to which messages are sent. Every process has a ``mailbox'' of -its incoming messages which is represented as a queue. It can work -sequentially through the messages in its mailbox, or search for -messages matching some pattern. - -\begin{lstlisting}[style=floating,label=fig:simple-auction-msgs,caption=Implementation of an Auction Service] -trait AuctionMessage; -case class Offer(bid: int, client: Actor) extends AuctionMessage; -case class Inquire(client: Actor) extends AuctionMessage; - -trait AuctionReply; -case class Status(asked: int, expire: Date) extends AuctionReply; -case object BestOffer extends AuctionReply; -case class BeatenOffer(maxBid: int) extends AuctionReply; -case class AuctionConcluded(seller: Actor, client: Actor) - extends AuctionReply; -case object AuctionFailed extends AuctionReply; -case object AuctionOver extends AuctionReply; -\end{lstlisting} - -For every traded item there is an auctioneer process that publishes -information about the traded item, that accepts offers from clients -and that communicates with the seller and winning bidder to close the -transaction. We present an overview of a simple implementation -here. - -As a first step, we define the messages that are exchanged during an -auction. There are two abstract base classes (called {\em traits}): -\code{AuctionMessage} for messages from clients to the auction -service, and \code{AuctionReply} for replies from the service to the -clients. For both base classes there exists a number of cases, which -are defined in Figure~\ref{fig:simple-auction-msgs}. - -\begin{lstlisting}[style=floating,label=fig:simple-auction,caption=Implementation of an Auction Service] -class Auction(seller: Actor, minBid: int, closing: Date) extends Actor { - val timeToShutdown = 36000000; // msec - val bidIncrement = 10; - override def run() = { - var maxBid = minBid - bidIncrement; - var maxBidder: Actor = _; - var running = true; - while (running) { - receiveWithin ((closing.getTime() - new Date().getTime())) { - case Offer(bid, client) => - if (bid >= maxBid + bidIncrement) { - if (maxBid >= minBid) maxBidder send BeatenOffer(bid); - maxBid = bid; maxBidder = client; client send BestOffer; - } else { - client send BeatenOffer(maxBid); - } - case Inquire(client) => - client send Status(maxBid, closing); - case TIMEOUT => - if (maxBid >= minBid) { - val reply = AuctionConcluded(seller, maxBidder); - maxBidder send reply; seller send reply; - } else { - seller send AuctionFailed; - } - receiveWithin(timeToShutdown) { - case Offer(_, client) => client send AuctionOver - case TIMEOUT => running = false; - } - } - } - } -} -\end{lstlisting} - -For each base class, there are a number of {\em case classes} which -define the format of particular messages in the class. These messages -might well be ultimately mapped to small XML documents. We expect -automatic tools to exist that convert between XML documents and -internal data structures like the ones defined above. - -Figure~\ref{fig:simple-auction} presents a Scala implementation of a -class \code{Auction} for auction processes that coordinate the bidding -on one item. Objects of this class are created by indicating -\begin{itemize} -\item a seller process which needs to be notified when the auction is over, -\item a minimal bid, -\item the date when the auction is to be closed. -\end{itemize} -The process behavior is defined by its \code{run} method. That method -repeatedly selects (using \code{receiveWithin}) a message and reacts to it, -until the auction is closed, which is signaled by a \code{TIMEOUT} -message. Before finally stopping, it stays active for another period -determined by the \code{timeToShutdown} constant and replies to -further offers that the auction is closed. - -Here are some further explanations of the constructs used in this -program: -\begin{itemize} -\item -The \code{receiveWithin} method of class \code{Actor} takes as -parameters a time span given in milliseconds and a function that -processes messages in the mailbox. The function is given by a sequence -of cases that each specify a pattern and an action to perform for -messages matching the pattern. The \code{receiveWithin} method selects -the first message in the mailbox which matches one of these patterns -and applies the corresponding action to it. -\item -The last case of \code{receiveWithin} is guarded by a -\code{TIMEOUT} pattern. If no other messages are received in the meantime, this -pattern is triggered after the time span which is passed as argument -to the enclosing \code{receiveWithin} method. \code{TIMEOUT} is a -particular instance of class \code{Message}, which is triggered by the -\code{Actor} implementation itself. -\item -Reply messages are sent using syntax of the form -\code{destination send SomeMessage}. \code{send} is used here as a -binary operator with a process and a message as arguments. This is -equivalent in Scala to the method call -\code{destination.send(SomeMessage)}, i.e. the invocation of -the \code{send} of the destination process with the given message as -parameter. -\end{itemize} -The preceding discussion gave a flavor of distributed programming in -Scala. It might seem that Scala has a rich set of language constructs -that support actor processes, message sending and receiving, -programming with timeouts, etc. In fact, the opposite is true. All the -constructs discussed above are offered as methods in the library class -\code{Actor}. That class is itself implemented in Scala, based on the underlying -thread model of the host language (e.g. Java, or .NET). -The implementation of all features of class \code{Actor} used here is -given in Section~\ref{sec:actors}. - -The advantages of the library-based 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. The calculator returns the evaluation results and their -types. Example: - -\begin{lstlisting} -> 87 + 145 -232: scala.Int - -> 5 + 2 * 3 -11: scala.Int - -> "hello" + " world!" -hello world: scala.String -\end{lstlisting} -It is also possible to name a sub-expression and use the name instead -of the expression afterwards: -\begin{lstlisting} -> def scale = 5 -def scale: int - -> 7 * scale -35: scala.Int -\end{lstlisting} -\begin{lstlisting} -> def pi = 3.141592653589793 -def pi: scala.Double - -> def radius = 10 -def radius: scala.Int - -> 2 * pi * radius -62.83185307179586: scala.Double -\end{lstlisting} -Definitions start with the reserved word \code{def}; they introduce a -name which stands for the expression following the \code{=} sign. The -interpreter will answer with the introduced name and its type. - -Executing a definition such as \code{def x = e} will not evaluate the -expression \code{e}. Instead \code{e} is evaluated whenever \code{x} -is used. Alternatively, Scala offers a value definition -\code{val x = e}, which does evaluate the right-hand-side \code{e} as part of the -evaluation of the definition. If \code{x} is then used subsequently, -it is immediately replaced by the pre-computed value of -\code{e}, so that the expression need not be evaluated again. - -How are expressions evaluated? An expression consisting of operators -and operands is evaluated by repeatedly applying the following -simplification steps. -\begin{itemize} -\item pick the left-most operation -\item evaluate its operands -\item apply the operator to the operand values. -\end{itemize} -A name defined by \code{def}\ is evaluated by replacing the name by the -(unevaluated) definition's right hand side. A name defined by \code{val} is -evaluated by replacing the name by the value of the definitions's -right-hand side. The evaluation process stops once we have reached a -value. A value is some data item such as a string, a number, an array, -or a list. - -\example -Here is an evaluation of an arithmetic expression. -\begin{lstlisting} -$\,\,\,$ (2 * pi) * radius -$\rightarrow$ (2 * 3.141592653589793) * radius -$\rightarrow$ 6.283185307179586 * radius -$\rightarrow$ 6.283185307179586 * 10 -$\rightarrow$ 62.83185307179586 -\end{lstlisting} -The process of stepwise simplification of expressions to values is -called {\em reduction}. - -\section{Parameters} - -Using \code{def}, one can also define functions with parameters. Example: -\begin{lstlisting} -> def square(x: double) = x * x -def (x: double): scala.Double - -> square(2) -4.0: scala.Double - -> square(5 + 3) -64.0: scala.Double - -> square(square(4)) -256.0: scala.Double - -> def sumOfSquares(x: double, y: double) = square(x) + square(y) -def sumOfSquares(scala.Double,scala.Double): scala.Double - -> sumOfSquares(3, 2 + 2) -25.0: scala.Double -\end{lstlisting} - -Function parameters follow the function name and are always enclosed -in parentheses. Every parameter comes with a type, which is indicated -following the parameter name and a colon. At the present time, we -only need basic numeric types such as the type \code{scala.Double} of -double precision numbers. Scala defines {\em type aliases} for some -standard types, so we can write numeric types as in Java. For instance -\code{double} is a type alias of \code{scala.Double} and \code{int} is -a type alias for \code{scala.Int}. - -Functions with parameters are evaluated analogously to operators in -expressions. First, the arguments of the function are evaluated (in -left-to-right order). Then, the function application is replaced by -the function's right hand side, and at the same time all formal -parameters of the function are replaced by their corresponding actual -arguments. - -\example\ - -\begin{lstlisting} -$\,\,\,$ sumOfSquares(3, 2+2) -$\rightarrow$ sumOfSquares(3, 4) -$\rightarrow$ square(3) + square(4) -$\rightarrow$ 3 * 3 + square(4) -$\rightarrow$ 9 + square(4) -$\rightarrow$ 9 + 4 * 4 -$\rightarrow$ 9 + 16 -$\rightarrow$ 25 -\end{lstlisting} - -The example shows that the interpreter reduces function arguments to -values before rewriting the function application. One could instead -have chosen to apply the function to unreduced arguments. This would -have yielded the following reduction sequence: -\begin{lstlisting} -$\,\,\,$ sumOfSquares(3, 2+2) -$\rightarrow$ square(3) + square(2+2) -$\rightarrow$ 3 * 3 + square(2+2) -$\rightarrow$ 9 + square(2+2) -$\rightarrow$ 9 + (2+2) * (2+2) -$\rightarrow$ 9 + 4 * (2+2) -$\rightarrow$ 9 + 4 * 4 -$\rightarrow$ 9 + 16 -$\rightarrow$ 25 -\end{lstlisting} - -The second evaluation order is known as \emph{call-by-name}, -whereas the first one is known as \emph{call-by-value}. For -expressions that use only pure functions and that therefore can be -reduced with the substitution model, both schemes yield the same final -values. - -Call-by-value has the advantage that it avoids repeated evaluation of -arguments. Call-by-name has the advantage that it avoids evaluation of -arguments when the parameter is not used at all by the function. -Call-by-value is usually more efficient than call-by-name, but a -call-by-value evaluation might loop where a call-by-name evaluation -would terminate. Consider: -\begin{lstlisting} -> def loop: int = loop -def loop: scala.Int - -> def first(x: int, y: int) = x -def first(x: scala.Int, y: scala.Int): scala.Int -\end{lstlisting} -Then \code{first(1, loop)} reduces with call-by-name to \code{1}, -whereas the same term reduces with call-by-value repeatedly to itself, -hence evaluation does not terminate. -\begin{lstlisting} -$\,\,\,$ first(1, loop) -$\rightarrow$ first(1, loop) -$\rightarrow$ first(1, loop) -$\rightarrow$ ... -\end{lstlisting} -Scala uses call-by-value by default, but it switches to call-by-name evaluation -if the parameter type is preceded by \code{=>}. - -\example\ - -\begin{lstlisting} -> def constOne(x: int, y: => int) = 1 -constOne(x: scala.Int, y: => scala.Int): scala.Int - -> constOne(1, loop) -1: scala.Int - -> constOne(loop, 2) // gives an infinite loop. -^C -\end{lstlisting} - -\section{Conditional Expressions} - -Scala's \code{if-else} lets one choose between two alternatives. Its -syntax is like Java's \code{if-else}. But where Java's \code{if-else} -can be used only as an alternative of statements, Scala allows the -same syntax to choose between two expressions. That's why Scala's -\code{if-else} serves also as a substitute for Java's conditional -expression \code{ ... ? ... : ...}. - -\example\ - -\begin{lstlisting} -> def abs(x: double) = if (x >= 0) x else -x -abs(x: double): double -\end{lstlisting} -Scala's boolean expressions are similar to Java's; they are formed -from the constants -\code{true} and -\code{false}, comparison operators, boolean negation \code{!} and the -boolean operators $\,$\code{&&}$\,$ and $\,$\code{||}. - -\section{\label{sec:sqrt}Example: Square Roots by Newton's Method} - -We now illustrate the language elements introduced so far in the -construction of a more interesting program. The task is to write a -function -\begin{lstlisting} -def sqrt(x: double): double = ... -\end{lstlisting} -which computes the square root of \code{x}. - -A common way to compute square roots is by Newton's method of -successive approximations. One starts with an initial guess \code{y} -(say: \code{y = 1}). One then repeatedly improves the current guess -\code{y} by taking the average of \code{y} and \code{x/y}. As an -example, the next three columns indicate the guess \code{y}, the -quotient \code{x/y}, and their average for the first approximations of -$\sqrt 2$. -\begin{lstlisting} -1 2/1 = 2 1.5 -1.5 2/1.5 = 1.3333 1.4167 -1.4167 2/1.4167 = 1.4118 1.4142 -1.4142 ... ... - -$y$ $x/y$ $(y + x/y)/2$ -\end{lstlisting} -One can implement this algorithm in Scala by a set of small functions, -which each represent one of the elements of the algorithm. - -We first define a function for iterating from a guess to the result: -\begin{lstlisting} -def sqrtIter(guess: double, x: double): double = - if (isGoodEnough(guess, x)) guess - else sqrtIter(improve(guess, x), x); -\end{lstlisting} -Note that \code{sqrtIter} calls itself recursively. Loops in -imperative programs can always be modeled by recursion in functional -programs. - -Note also that the definition of \code{sqrtIter} contains a return -type, which follows the parameter section. Such return types are -mandatory for recursive functions. For a non-recursive function, the -return type is optional; if it is missing the type checker will -compute it from the type of the function's right-hand side. However, -even for non-recursive functions it is often a good idea to include a -return type for better documentation. - -As a second step, we define the two functions called by -\code{sqrtIter}: a function to \code{improve} the guess and a -termination test \code{isGoodEnough}. Here is their definition. -\begin{lstlisting} -def improve(guess: double, x: double) = - (guess + x / guess) / 2; - -def isGoodEnough(guess: double, x: double) = - abs(square(guess) - x) < 0.001; -\end{lstlisting} - -Finally, the \code{sqrt} function itself is defined by an application -of \code{sqrtIter}. -\begin{lstlisting} -def sqrt(x: double) = sqrtIter(1.0, x); -\end{lstlisting} - -\begin{exercise} The \code{isGoodEnough} test is not very precise for small -numbers and might lead to non-termination for very large ones (why?). -Design a different version of \code{isGoodEnough} which does not have -these problems. -\end{exercise} - -\begin{exercise} Trace the execution of the \code{sqrt(4)} expression. -\end{exercise} - -\section{Nested Functions} - -The functional programming style encourages the construction of many -small helper functions. In the last example, the implementation -of \code{sqrt} made use of the helper functions \code{sqrtIter}, -\code{improve} and \code{isGoodEnough}. The names of these functions -are relevant only for the implementation of \code{sqrt}. We normally -do not want users of \code{sqrt} to access these functions directly. - -We can enforce this (and avoid name-space pollution) by including -the helper functions within the calling function itself: -\begin{lstlisting} -def sqrt(x: double) = { - def sqrtIter(guess: double, x: double): double = - if (isGoodEnough(guess, x)) guess - else sqrtIter(improve(guess, x), x); - def improve(guess: double, x: double) = - (guess + x / guess) / 2; - def isGoodEnough(guess: double, x: double) = - abs(square(guess) - x) < 0.001; - sqrtIter(1.0, x) -} -\end{lstlisting} -In this program, the braces \code{\{ ... \}} enclose a {\em block}. -Blocks in Scala are themselves expressions. Every block ends in a -result expression which defines its value. The result expression may -be preceded by auxiliary definitions, which are visible only in the -block itself. - -Every definition in a block must be followed by a semicolon, which -separates this definition from subsequent definitions or the result -expression. However, a semicolon is inserted implicitly if the -definition ends in a right brace and is followed by a new line. -Therefore, the following are all legal: -\begin{lstlisting} -def f(x) = x + 1; /* `;' mandatory */ -f(1) + f(2) - -def g(x) = {x + 1} -g(1) + g(2) - -def h(x) = {x + 1}; /* `;' mandatory */ h(1) + h(2) -\end{lstlisting} -Scala uses the usual block-structured scoping rules. A name defined in -some outer block is visible also in some inner block, provided it is -not redefined there. This rule permits us to simplify our -\code{sqrt} example. We need not pass \code{x} around as an additional parameter of -the nested functions, since it is always visible in them as a -parameter of the outer function \code{sqrt}. Here is the simplified code: -\begin{lstlisting} -def sqrt(x: double) = { - def sqrtIter(guess: double): double = - if (isGoodEnough(guess)) guess - else sqrtIter(improve(guess)); - def improve(guess: double) = - (guess + x / guess) / 2; - def isGoodEnough(guess: double) = - abs(square(guess) - x) < 0.001; - sqrtIter(1.0) -} -\end{lstlisting} - -\section{Tail Recursion} - -Consider the following function to compute the greatest common divisor -of two given numbers. - -\begin{lstlisting} -def gcd(a: int, b: int): int = if (b == 0) a else gcd(b, a % b) -\end{lstlisting} - -Using our substitution model of function evaluation, -\code{gcd(14, 21)} evaluates as follows: - -\begin{lstlisting} -$\,\,$ gcd(14, 21) -$\rightarrow\!$ if (21 == 0) 14 else gcd(21, 14 % 21) -$\rightarrow\!$ if (false) 14 else gcd(21, 14 % 21) -$\rightarrow\!$ gcd(21, 14 % 21) -$\rightarrow\!$ gcd(21, 14) -$\rightarrow\!$ if (14 == 0) 21 else gcd(14, 21 % 14) -$\rightarrow$ $\rightarrow$ gcd(14, 21 % 14) -$\rightarrow\!$ gcd(14, 7) -$\rightarrow\!$ if (7 == 0) 14 else gcd(7, 14 % 7) -$\rightarrow$ $\rightarrow$ gcd(7, 14 % 7) -$\rightarrow\!$ gcd(7, 0) -$\rightarrow\!$ if (0 == 0) 7 else gcd(0, 7 % 0) -$\rightarrow$ $\rightarrow$ 7 -\end{lstlisting} - -Contrast this with the evaluation of another recursive function, -\code{factorial}: - -\begin{lstlisting} -def factorial(n: int): int = if (n == 0) 1 else n * factorial(n - 1) -\end{lstlisting} - -The application \code{factorial(5)} rewrites as follows: -\begin{lstlisting} -$\,\,\,$ factorial(5) -$\rightarrow$ if (5 == 0) 1 else 5 * factorial(5 - 1) -$\rightarrow$ 5 * factorial(5 - 1) -$\rightarrow$ 5 * factorial(4) -$\rightarrow\ldots\rightarrow$ 5 * (4 * factorial(3)) -$\rightarrow\ldots\rightarrow$ 5 * (4 * (3 * factorial(2))) -$\rightarrow\ldots\rightarrow$ 5 * (4 * (3 * (2 * factorial(1)))) -$\rightarrow\ldots\rightarrow$ 5 * (4 * (3 * (2 * (1 * factorial(0)))) -$\rightarrow\ldots\rightarrow$ 5 * (4 * (3 * (2 * (1 * 1)))) -$\rightarrow\ldots\rightarrow$ 120 -\end{lstlisting} -There is an important difference between the two rewrite sequences: -The terms in the rewrite sequence of \code{gcd} have again and again -the same form. As evaluation proceeds, their size is bounded by a -constant. By contrast, in the evaluation of factorial we get longer -and longer chains of operands which are then multiplied in the last -part of the evaluation sequence. - -Even though actual implementations of Scala do not work by rewriting -terms, they nevertheless should have the same space behavior as in the -rewrite sequences. In the implementation of \code{gcd}, one notes that -the recursive call to \code{gcd} is the last action performed in the -evaluation of its body. One also says that \code{gcd} is -``tail-recursive''. The final call in a tail-recursive function can be -implemented by a jump back to the beginning of that function. The -arguments of that call can overwrite the parameters of the current -instantiation of \code{gcd}, so that no new stack space is needed. -Hence, tail recursive functions are iterative processes, which can be -executed in constant space. - -By contrast, the recursive call in \code{factorial} is followed by a -multiplication. Hence, a new stack frame is allocated for the -recursive instance of factorial, and is deallocated 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 -primitives 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. - -\begin{exercise} Design a tail-recursive version of -\code{factorial}. -\end{exercise} - -\chapter{\label{chap:first-class-funs}First-Class Functions} - -A function in Scala is a ``first-class value''. Like any other value, -it may be passed as a parameter or returned as a result. Functions -which take other functions as parameters or return them as results are -called {\em higher-order} functions. This chapter introduces -higher-order functions and shows how they provide a flexible mechanism -for program composition. - -As a motivating example, consider the following three related tasks: -\begin{enumerate} -\item -Write a function to sum all integers between two given numbers \code{a} and \code{b}: -\begin{lstlisting} -def sumInts(a: int, b: int): int = - if (a > b) 0 else a + sumInts(a + 1, b); -\end{lstlisting} -\item -Write a function to sum the squares of all integers between two given numbers -\code{a} and \code{b}: -\begin{lstlisting} -def square(x: int): int = x * x; -def sumSquares(a: int, b: int): int = - if (a > b) 0 else square(a) + sumSquares(a + 1, b); -\end{lstlisting} -\item -Write a function to sum the powers $2^n$ of all integers $n$ between -two given numbers \code{a} and \code{b}: -\begin{lstlisting} -def powerOfTwo(x: int): int = if (x == 0) 1 else x * powerOfTwo(x - 1); -def sumPowersOfTwo(a: int, b: int): int = - if (a > b) 0 else powerOfTwo(a) + sumPowersOfTwo(a + 1, b); -\end{lstlisting} -\end{enumerate} -These functions are all instances of -\(\sum^b_a f(n)\) for different values of $f$. -We can factor out the common pattern by defining a function \code{sum}: -\begin{lstlisting} -def sum(f: int => int, a: int, b: int): double = - if (a > b) 0 else f(a) + sum(f, a + 1, b); -\end{lstlisting} -The type \code{int => int} is the type of functions that -take arguments of type \code{int} and return results of type -\code{int}. So \code{sum} is a function which takes another function as -a parameter. In other words, \code{sum} is a {\em higher-order} -function. - -Using \code{sum}, we can formulate the three summing functions as -follows. -\begin{lstlisting} -def sumInts(a: int, b: int): int = sum(id, a, b); -def sumSquares(a: int, b: int): int = sum(square, a, b); -def sumPowersOfTwo(a: int, b: int): int = sum(powerOfTwo, a, b); -\end{lstlisting} -where -\begin{lstlisting} -def id(x: int): int = x; -def square(x: int): int = x * x; -def powerOfTwo(x: int): int = if (x == 0) 1 else x * powerOfTwo(x - 1); -\end{lstlisting} - -\section{Anonymous Functions} - -Parameterization by functions tends to create many small functions. In -the previous example, we defined \code{id}, \code{square} and -\code{power} as separate functions, so that they could be -passed as arguments to \code{sum}. - -Instead of using named function definitions for these small argument -functions, we can formulate them in a shorter way as {\em anonymous -functions}. An anonymous function is an expression that evaluates to a -function; the function is defined without giving it a name. As an -example consider the anonymous square function: -\begin{lstlisting} - x: int => x * x -\end{lstlisting} -The part before the arrow `\code{=>}' is the parameter of the function, -whereas the part following the `\code{=>}' is its body. If there are -several parameters, we need to enclose them in parentheses. For -instance, here is an anonymous function which multiples its two arguments. -\begin{lstlisting} - (x: int, y: int) => x * y -\end{lstlisting} -Using anonymous functions, we can reformulate the first two summation -functions without named auxiliary functions: -\begin{lstlisting} -def sumInts(a: int, b: int): int = sum(x: int => x, a, b); -def sumSquares(a: int, b: int): int = sum(x: int => x * x, a, b); -\end{lstlisting} -Often, the Scala compiler can deduce the parameter type(s) from the -context of the anonymous function in which case they can be omitted. -For instance, in the case of \code{sumInts} or \code{sumSquares}, one -knows from the type of \code{sum} that the first parameter must be a -function of type \code{int => int}. Hence, the parameter type -\code{int} is redundant and may be omitted: -\begin{lstlisting} -def sumInts(a: int, b: int): int = sum(x => x, a, b); -def sumSquares(a: int, b: int): int = sum(x => x * x, a, b); -\end{lstlisting} - -Generally, the Scala term -\code{(x}$_1$\code{: T}$_1$\code{, ..., x}$_n$\code{: T}$_n$\code{) => E} -defines a function which maps its parameters -\code{x}$_1$\code{, ..., x}$_n$ to the result of the expression \code{E} -(where \code{E} may refer to \code{x}$_1$\code{, ..., x}$_n$). Anonymous -functions are not essential language elements of Scala, as they can -always be expressed in terms of named functions. Indeed, the -anonymous function -\begin{lstlisting} -(x$_1$: T$_1$, ..., x$_n$: T$_n$) => E -\end{lstlisting} -is equivalent to the block -\begin{lstlisting} -{ def f (x$_1$: T$_1$, ..., x$_n$: T$_n$) = E ; f } -\end{lstlisting} -where \code{f} is fresh name which is used nowhere else in the program. -We also say, anonymous functions are ``syntactic sugar''. - -\section{Currying} - -The latest formulation of the summing functions is already quite -compact. But we can do even better. Note that -\code{a} and \code{b} appear as parameters and arguments of every function -but they do not seem to take part in interesting combinations. Is -there a way to get rid of them? - -Let's try to rewrite \code{sum} so that it does not take the bounds -\code{a} and \code{b} as parameters: -\begin{lstlisting} -def sum(f: int => int) = { - def sumF(a: int, b: int): int = - if (a > b) 0 else f(a) + sumF(a + 1, b); - sumF -} -\end{lstlisting} -In this formulation, \code{sum} is a function which returns another -function, namely the specialized summing function \code{sumF}. This -latter function does all the work; it takes the bounds \code{a} and -\code{b} as parameters, applies \code{sum}'s function parameter \code{f} to all -integers between them, and sums up the results. - -Using this new formulation of \code{sum}, we can now define: -\begin{lstlisting} -def sumInts = sum(x => x); -def sumSquares = sum(x => x * x); -def sumPowersOfTwo = sum(powerOfTwo); -\end{lstlisting} -Or, equivalently, with value definitions: -\begin{lstlisting} -val sumInts = sum(x => x); -val sumSquares = sum(x => x * x); -val sumPowersOfTwo = sum(powerOfTwo); -\end{lstlisting} -These functions can be applied like other functions. For instance, -\begin{lstlisting} -> sumSquares(1, 10) + sumPowersOfTwo(10, 20) -267632001: scala.Int -\end{lstlisting} -How are function-returning functions applied? As an example, in the expression -\begin{lstlisting} -sum(x => x * x)(1, 10) , -\end{lstlisting} -the function \code{sum} is applied to the squaring function -\code{(x => x * x)}. The resulting function is then -applied to the second argument list, \code{(1, 10)}. - -This notation is possible because function application associates to the left. -That is, if $\mbox{args}_1$ and $\mbox{args}_2$ are argument lists, then -\bda{lcl} -f(\mbox{args}_1)(\mbox{args}_2) & \ \ \mbox{is equivalent to}\ \ & (f(\mbox{args}_1))(\mbox{args}_2) -\eda -In our example, \code{sum(x => x * x)(1, 10)} is equivalent to the -following expression: -\code{(sum(x => x * x))(1, 10)}. - -The style of function-returning functions is so useful that Scala has -special syntax for it. For instance, the next definition of \code{sum} -is equivalent to the previous one, but is shorter: -\begin{lstlisting} -def sum(f: int => int)(a: int, b: int): int = - if (a > b) 0 else f(a) + sum(f)(a + 1, b); -\end{lstlisting} -Generally, a curried function definition -\begin{lstlisting} -def f (args$_1$) ... (args$_n$) = E -\end{lstlisting} -where $n > 1$ expands to -\begin{lstlisting} -def f (args$_1$) ... (args$_{n-1}$) = { def g (args$_n$) = E ; g } -\end{lstlisting} -where \code{g} is a fresh identifier. Or, shorter, using an anonymous function: -\begin{lstlisting} -def f (args$_1$) ... (args$_{n-1}$) = ( args$_n$ ) => E . -\end{lstlisting} -Performing this step $n$ times yields that -\begin{lstlisting} -def f (args$_1$) ... (args$_n$) = E -\end{lstlisting} -is equivalent to -\begin{lstlisting} -def f = (args$_1$) => ... => (args$_n$) => E . -\end{lstlisting} -Or, equivalently, using a value definition: -\begin{lstlisting} -val f = (args$_1$) => ... => (args$_n$) => E . -\end{lstlisting} -This style of function definition and application is called {\em -currying} after its promoter, Haskell B.\ Curry, a logician of the -20th century, even though the idea goes back further to Moses -Sch\"onfinkel and Gottlob Frege. - -The type of a function-returning function is expressed analogously to -its parameter list. Taking the last formulation of \code{sum} as an example, -the type of \code{sum} is \code{(int => int) => (int, int) => int}. -This is possible because function types associate to the right. I.e. -\begin{lstlisting} -T$_1$ => T$_2$ => T$_3$ $\mbox{is equivalent to}$ T$_1$ => (T$_2$ => T$_3$) -\end{lstlisting} - - -\begin{exercise} -1. The \code{sum} function uses a linear recursion. Can you write a -tail-recursive one by filling in the ??'s? - -\begin{lstlisting} -def sum(f: int => double)(a: int, b: int): double = { - def iter(a, result) = { - if (??) ?? - else iter(??, ??) - } - iter(??, ??) -} -\end{lstlisting} -\end{exercise} - -\begin{exercise} -Write a function \code{product} that computes the product of the -values of functions at points over a given range. -\end{exercise} - -\begin{exercise} -Write \code{factorial} in terms of \code{product}. -\end{exercise} - -\begin{exercise} -Can you write an even more general function which generalizes both -\code{sum} and \code{product}? -\end{exercise} - -\section{Example: Finding Fixed Points of Functions} - -A number \code{x} is called a {\em fixed point} of a function \code{f} if -\begin{lstlisting} -f(x) = x . -\end{lstlisting} -For some functions \code{f} we can locate the fixed point by beginning -with an initial guess and then applying \code{f} repeatedly, until the -value does not change anymore (or the change is within a small -tolerance). This is possible if the sequence -\begin{lstlisting} -x, f(x), f(f(x)), f(f(f(x))), ... -\end{lstlisting} -converges to fixed point of $f$. This idea is captured in -the following ``fixed-point finding function'': -\begin{lstlisting} -val tolerance = 0.0001; -def isCloseEnough(x: double, y: double) = abs((x - y) / x) < tolerance; -def fixedPoint(f: double => double)(firstGuess: double) = { - def iterate(guess: double): double = { - val next = f(guess); - if (isCloseEnough(guess, next)) next - else iterate(next) - } - iterate(firstGuess) -} -\end{lstlisting} -We now apply this idea in a reformulation of the square root function. -Let's start with a specification of \code{sqrt}: -\begin{lstlisting} -sqrt(x) = $\mbox{the {\sl y} such that}$ y * y = x - = $\mbox{the {\sl y} such that}$ y = x / y -\end{lstlisting} -Hence, \code{sqrt(x)} is a fixed point of the function \code{y => x / y}. -This suggests that \code{sqrt(x)} can be computed by fixed point iteration: -\begin{lstlisting} -def sqrt(x: double) = fixedPoint(y => x / y)(1.0) -\end{lstlisting} -But if we try this, we find that the computation does not -converge. Let's instrument the fixed point function with a print -statement which keeps track of the current \code{guess} value: -\begin{lstlisting} -def fixedPoint(f: double => double)(firstGuess: double) = { - def iterate(guess: double): double = { - val next = f(guess); - System.out.println(next); - if (isCloseEnough(guess, next)) next - else iterate(next) - } - iterate(firstGuess) -} -\end{lstlisting} -Then, \code{sqrt(2)} yields: -\begin{lstlisting} - 2.0 - 1.0 - 2.0 - 1.0 - 2.0 - ... -\end{lstlisting} -One way to control such oscillations is to prevent the guess from changing too much. -This can be achieved by {\em averaging} successive values of the original sequence: -\begin{lstlisting} -> def sqrt(x: double) = fixedPoint(y => (y + x/y) / 2)(1.0) -def sqrt(x: scala.Double): scala.Double -> sqrt(2.0) - 1.5 - 1.4166666666666665 - 1.4142156862745097 - 1.4142135623746899 - 1.4142135623746899 -\end{lstlisting} -In fact, expanding the \code{fixedPoint} function yields exactly our -previous definition of fixed point from Section~\ref{sec:sqrt}. - -The previous examples showed that the expressive power of a language -is considerably enhanced if functions can be passed as arguments. The -next example shows that functions which return functions can also be -very useful. - -Consider again fixed point iterations. We started with the observation -that $\sqrt(x)$ is a fixed point of the function \code{y => x / y}. -Then we made the iteration converge by averaging successive values. -This technique of {\em average damping} is so general that it -can be wrapped in another function. -\begin{lstlisting} -def averageDamp(f: double => double)(x: double) = (x + f(x)) / 2; -\end{lstlisting} -Using \code{averageDamp}, we can reformulate the square root function -as follows. -\begin{lstlisting} -def sqrt(x: double) = fixedPoint(averageDamp(y => x/y))(1.0); -\end{lstlisting} -This expresses the elements of the algorithm as clearly as possible. - -\begin{exercise} Write a function for cube roots using \code{fixedPoint} and -\code{averageDamp}. -\end{exercise} - -\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 present chapter has shown that these abstractions can be combined -by higher-order functions to create further abstractions. As -programmers, we should look out for opportunities to abstract and to -reuse. The highest possible level of abstraction is not always the -best, but it is important to know abstraction techniques, so that one -can use abstractions where appropriate. - -\section{Language Elements Seen So Far} - -Chapters~\ref{chap:simple-funs} and \ref{chap:first-class-funs} have -covered Scala's language elements to express expressions and types -comprising of primitive data and functions. The context-free syntax -of these language elements is given below in extended Backus-Naur -form, where `\code{|}' denotes alternatives, \code{[...]} denotes -option (0 or 1 occurrence), and \lstinline@{...}@ denotes repetition -(0 or more occurrences). - -\subsection*{Characters} - -Scala programs are sequences of (Unicode) characters. We distinguish the -following character sets: -\begin{itemize} -\item -whitespace, such as `\code{ }', tabulator, or newline characters, -\item -letters `\code{a}' to `\code{z}', `\code{A}' to `\code{Z}', -\item -digits \code{`0'} to `\code{9}', -\item -the delimiter characters - -\begin{lstlisting} -. , ; ( ) { } [ ] \ $\mbox{\tt "}$ ' -\end{lstlisting} - -\item -operator characters, such as `\code{#}' `\code{+}', -`\code{:}'. Essentially, these are printable characters which are -in none of the character sets above. -\end{itemize} - -\subsection*{Lexemes:} - -\begin{lstlisting} -ident = letter {letter | digit} - | operator { operator } - | ident '_' ident -literal = $\mbox{``as in Java''}$ -\end{lstlisting} - -Literals are as in Java. They define numbers, characters, strings, or -boolean values. Examples of literals as \code{0}, \code{1.0d10}, \code{'x'}, -\code{"he said \"hi!\""}, or \code{true}. - -Identifiers can be of two forms. They either start with a letter, -which is followed by a (possibly empty) sequence of letters or -symbols, or they start with an operator character, which is followed -by a (possibly empty) sequence of operator characters. Both forms of -identifiers may contain underscore characters `\code{_}'. Furthermore, -an underscore character may be followed by either sort of -identifier. Hence, the following are all legal identifiers: -\begin{lstlisting} -x Room10a + -- foldl_: +_vector -\end{lstlisting} -It follows from this rule that subsequent operator-identifiers need to -be separated by whitespace. For instance, the input -\code{x+-y} is parsed as the three token sequence \code{x}, \code{+-}, -\code{y}. If we want to express the sum of \code{x} with the -negated value of \code{y}, we need to add at least one space, -e.g. \code{x+ -y}. - -The \verb@$@ character is reserved for compiler-generated -identifiers; it should not be used in source programs. %$ - -The following are reserved words, they may not be used as identifiers: -\begin{lstlisting}[keywordstyle=] -abstract case catch class def -do else extends false final -finally for if import new -null object override package private -protected return sealed super this -trait try true type val -var while with yield -_ : = => <- <: >: # @ -\end{lstlisting} - -\subsection*{Types:} - -\begin{lstlisting} -Type = SimpleType | FunctionType -FunctionType = SimpleType '=>' Type | '(' [Types] ')' '=>' Type -SimpleType = byte | short | char | int | long | double | float | - boolean | unit | String -Types = Type {`,' Type} -\end{lstlisting} - -Types can be: -\begin{itemize} -\item number types \code{byte}, \code{short}, \code{char}, \code{int}, \code{long}, \code{float} and \code{double} (these are as in Java), -\item the type \code{boolean} with values \code{true} and \code{false}, -\item the type \code{unit} with the only value \code{()}, -\item the type \code{String}, -\item function types such as \code{(int, int) => int} or \code{String => Int => String}. -\end{itemize} - -\subsection*{Expressions:} - -\begin{lstlisting} -Expr = InfixExpr | FunctionExpr | if '(' Expr ')' Expr else Expr -InfixExpr = PrefixExpr | InfixExpr Operator InfixExpr -Operator = ident -PrefixExpr = ['+' | '-' | '!' | '~' ] SimpleExpr -SimpleExpr = ident | literal | SimpleExpr '.' ident | Block -FunctionExpr = Bindings '=>' Expr -Bindings = ident [':' SimpleType] | '(' [Binding {',' Binding}] ')' -Binding = ident [':' Type] -Block = '{' {Def ';'} Expr '}' -\end{lstlisting} - -Expressions can be: -\begin{itemize} -\item -identifiers such as \code{x}, \code{isGoodEnough}, \code{*}, or \code{+-}, -\item -literals, such as \code{0}, \code{1.0}, or \code{"abc"}, -\item -field and method selections, such as \code{System.out.println}, -\item -function applications, such as \code{sqrt(x)}, -\item -operator applications, such as \code{-x} or \code{y + x}, -\item -conditionals, such as \code{if (x < 0) -x else x}, -\item -blocks, such as \lstinline@{ val x = abs(y) ; x * 2 }@, -\item -anonymous functions, such as \code{x => x + 1} or \code{(x: int, y: int) => x + y}. -\end{itemize} - -\subsection*{Definitions:} - -\begin{lstlisting} -Def = FunDef | ValDef -FunDef = 'def' ident {'(' [Parameters] ')'} [':' Type] '=' Expr -ValDef = 'val' ident [':' Type] '=' Expr -Parameters = Parameter {',' Parameter} -Parameter = ['def'] ident ':' Type -\end{lstlisting} -Definitions can be: -\begin{itemize} -\item -function definitions such as \code{def square(x: int): int = x * x}, -\item -value definitions such as \code{val y = square(2)}. -\end{itemize} - -\chapter{Classes and Objects} -\label{chap:classes} - -Scala does not have a built-in type of rational numbers, but it is -easy to define one, using a class. Here's a possible implementation. - -\begin{lstlisting} -class Rational(n: int, d: int) { - private def gcd(x: int, y: int): int = { - if (x == 0) y - else if (x < 0) gcd(-x, y) - else if (y < 0) -gcd(x, -y) - else gcd(y % x, x); - } - private val g = gcd(n, d); - - val numer: int = n/g; - val denom: int = d/g; - def +(that: Rational) = - new Rational(numer * that.denom + that.numer * denom, - denom * that.denom); - def -(that: Rational) = - new Rational(numer * that.denom - that.numer * denom, - denom * that.denom); - def *(that: Rational) = - new Rational(numer * that.numer, denom * that.denom); - def /(that: Rational) = - new Rational(numer * that.denom, denom * that.numer); -} -\end{lstlisting} -This defines \code{Rational} as a class which takes two constructor -arguments \code{n} and \code{d}, containing the number's numerator and -denominator parts. The class provides fields which return these parts -as well as methods for arithmetic over rational numbers. Each -arithmetic method takes as parameter the right operand of the -operation. The left operand of the operation is always the rational -number of which the method is a member. - -\paragraph{Private members} -The implementation of rational numbers defines a private method -\code{gcd} which computes the greatest common denominator of two -integers, as well as a private field \code{g} which contains the -\code{gcd} of the constructor arguments. These members are inaccessible -outside class \code{Rational}. They are used in the implementation of -the class to eliminate common factors in the constructor arguments in -order to ensure that numerator and denominator are always in -normalized form. - -\paragraph{Creating and Accessing Objects} -As an example of how rational numbers can be used, here's a program -that prints the sum of all numbers $1/i$ where $i$ ranges from 1 to 10. -\begin{lstlisting} -var i = 1; -var x = new Rational(0, 1); -while (i <= 10) { - x = x + new Rational(1,i); - i = i + 1; -} -System.out.println("" + x.numer + "/" + x.denom); -\end{lstlisting} -The \code{+} takes as left operand a string and as right operand a -value of arbitrary type. It returns the result of converting its right -operand to a string and appending it to its left operand. - -\paragraph{Inheritance and Overriding} -Every class in Scala has a superclass which it extends. -\comment{Excepted is -only the root class \code{Object}, which does not have a superclass, -and which is indirectly extended by every other class. } -If a class -does not mention a superclass in its definition, the root type -\code{scala.AnyRef} is implicitly assumed (for Java implementations, -this type is an alias for \code{java.lang.Object}. For instance, class -\code{Rational} could equivalently be defined as -\begin{lstlisting} -class Rational(n: int, d: int) extends AnyRef { - ... // as before -} -\end{lstlisting} -A class inherits all members from its superclass. It may also redefine -(or: {\em override}) some inherited members. For instance, class -\code{java.lang.Object} defines -a method -\code{toString} which returns a representation of the object as a string: -\begin{lstlisting} -class Object { - ... - def toString(): String = ... -} -\end{lstlisting} -The implementation of \code{toString} in \code{Object} -forms a string consisting of the object's class name and a number. It -makes sense to redefine this method for objects that are rational -numbers: -\begin{lstlisting} -class Rational(n: int, d: int) extends AnyRef { - ... // as before - override def toString() = "" + numer + "/" + denom; -} -\end{lstlisting} -Note that, unlike in Java, redefining definitions need to be preceded -by an \code{override} modifier. - -If class $A$ extends class $B$, then objects of type $A$ may be used -wherever objects of type $B$ are expected. We say in this case that -type $A$ {\em conforms} to type $B$. For instance, \code{Rational} -conforms to \code{AnyRef}, so it is legal to assign a \code{Rational} -value to a variable of type \code{AnyRef}: -\begin{lstlisting} -var x: AnyRef = new Rational(1,2); -\end{lstlisting} - -\paragraph{Parameterless Methods} -%Also unlike in Java, methods in Scala do not necessarily take a -%parameter list. An example is \code{toString}; the method is invoked -%by simply mentioning its name. For instance: -%\begin{lstlisting} -%val r = new Rational(1,2); -%System.out.println(r.toString()); // prints``1/2'' -%\end{lstlisting} -Unlike in Java, methods in Scala do not necessarily take a -parameter list. An example is the \code{square} method below. This -method is invoked by simply mentioning its name. -\begin{lstlisting} -class Rational(n: int, d: int) extends AnyRef { - ... // as before - def square = new Rational(numer*numer, denom*denom); -} -val r = new Rational(3,4); -System.out.println(r.square); // prints``9/16''* -\end{lstlisting} -That is, parameterless methods are accessed just as value fields such -as \code{numer} are. The difference between values and parameterless -methods lies in their definition. The right-hand side of a value is -evaluated when the object is created, and the value does not change -afterwards. A right-hand side of a parameterless method, on the other -hand, is evaluated each time the method is called. The uniform access -of fields and parameterless methods gives increased flexibility for -the implementer of a class. Often, a field in one version of a class -becomes a computed value in the next version. Uniform access ensures -that clients do not have to be rewritten because of that change. - -\paragraph{Abstract Classes} - -Consider the task of writing a class for sets of integer numbers with -two operations, \code{incl} and \code{contains}. \code{(s incl x)} -should return a new set which contains the element \code{x} together -with all the elements of set \code{s}. \code{(s contains x)} should -return true if the set \code{s} contains the element \code{x}, and -should return \code{false} otherwise. The interface of such sets is -given by: -\begin{lstlisting} -abstract class IntSet { - def incl(x: int): IntSet; - def contains(x: int): boolean; -} -\end{lstlisting} -\code{IntSet} is labeled as an \emph{abstract class}. This has two -consequences. First, abstract classes may have {\em deferred} members -which are declared but which do not have an implementation. In our -case, both \code{incl} and \code{contains} are such members. Second, -because an abstract class might have unimplemented members, no objects -of that class may be created using \code{new}. By contrast, an -abstract class may be used as a base class of some other class, which -implements the deferred members. - -\paragraph{Traits} - -Instead of \code{abstract class} one also often uses the keyword -\code{trait} in Scala. A trait is an abstract class with no state, no -constructor arguments, and no side effects during object -initialization. Since \code{IntSet}'s fall in this category, one can -alternatively define them as traits: -\begin{lstlisting} -trait IntSet { - def incl(x: int): IntSet; - def contains(x: int): boolean; -} -\end{lstlisting} -A trait corresponds to an interface in Java, except -that a trait can also define implemented methods. - -\paragraph{Implementing Abstract Classes} - -Let's say, we plan to implement sets as binary trees. There are two -possible forms of trees. A tree for the empty set, and a tree -consisting of an integer and two subtrees. Here are their -implementations. - -\begin{lstlisting} -class EmptySet extends IntSet { - def contains(x: int): boolean = false; - def incl(x: int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet); -} -\end{lstlisting} - -\begin{lstlisting} -class NonEmptySet(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 NonEmptySet(elem, left incl x, right) - else if (x > elem) new NonEmptySet(elem, left, right incl x) - else this; -} -\end{lstlisting} -Both \code{EmptySet} and \code{NonEmptySet} extend class -\code{IntSet}. This implies that types \code{EmptySet} and -\code{NonEmptySet} conform to type \code{IntSet} -- a value of type \code{EmptySet} or \code{NonEmptySet} may be used wherever a value of type \code{IntSet} is required. - -\begin{exercise} Write methods \code{union} and \code{intersection} to form -the union and intersection between two sets. -\end{exercise} - -\begin{exercise} Add a method -\begin{lstlisting} -def excl(x: int) -\end{lstlisting} -to return the given set without the element \code{x}. To accomplish this, -it is useful to also implement a test method -\begin{lstlisting} -def isEmpty: boolean -\end{lstlisting} -for sets. -\end{exercise} - -\paragraph{Dynamic Binding} - -Object-oriented languages (Scala included) use \emph{dynamic dispatch} -for method invocations. That is, the code invoked for a method call -depends on the run-time type of the object which contains the method. -For example, consider the expression \code{s contains 7} where -\code{s} is a value of declared type \code{s: IntSet}. Which code for -\code{contains} is executed depends on the type of value of \code{s} at run-time. -If it is an \code{EmptySet} value, it is the implementation of \code{contains} in class \code{EmptySet} that is executed, and analogously for \code{NonEmptySet} values. -This behavior is a direct consequence of our substitution model of evaluation. -For instance, -\begin{lstlisting} - (new EmptySet).contains(7) - --> $\rewriteby{by replacing {\sl contains} by its body in class {\sl EmptySet}}$ - - false -\end{lstlisting} -Or, -\begin{lstlisting} - new NonEmptySet(7, new EmptySet, new EmptySet).contains(1) - --> $\rewriteby{by replacing {\sl contains} by its body in class {\sl NonEmptySet}}$ - - if (1 < 7) new EmptySet contains 1 - else if (1 > 7) new EmptySet contains 1 - else true - --> $\rewriteby{by rewriting the conditional}$ - - new EmptySet contains 1 - --> $\rewriteby{by replacing {\sl contains} by its body in class {\sl EmptySet}}$ - - false . -\end{lstlisting} - -Dynamic method dispatch is analogous to higher-order function -calls. In both cases, the identity of code to be executed is known -only at run-time. This similarity is not just superficial. Indeed, -Scala represents every function value as an object (see -Section~\ref{sec:functions}). - - -\paragraph{Objects} - -In the previous implementation of integer sets, empty sets were -expressed with \code{new EmptySet}; so a new object was created every time -an empty set value was required. We could have avoided unnecessary -object creations by defining a value \code{empty} once and then using -this value instead of every occurrence of \code{new EmptySet}. E.g. -\begin{lstlisting} -val EmptySetVal = new EmptySet; -\end{lstlisting} -One problem with this approach is that a value definition such as the -one above is not a legal top-level definition in Scala; it has to be -part of another class or object. Also, the definition of class -\code{EmptySet} now seems a bit of an overkill -- why define a class of objects, -if we are only interested in a single object of this class? A more -direct approach is to use an {\em object definition}. Here is -a more streamlined alternative definition of the empty set: -\begin{lstlisting} -object EmptySet extends IntSet { - def contains(x: int): boolean = false; - def incl(x: int): IntSet = new NonEmptySet(x, EmptySet, EmptySet); -} -\end{lstlisting} -The syntax of an object definition follows the syntax of a class -definition; it has an optional extends clause as well as an optional -body. As is the case for classes, the extends clause defines inherited -members of the object whereas the body defines overriding or new -members. However, an object definition defines a single object only; -it is not possible to create other objects with the same structure -using \code{new}. Therefore, object definitions also lack constructor -parameters, which might be present in class definitions. - -Object definitions can appear anywhere in a Scala program; including -at top-level. Since there is no fixed execution order of top-level -entities in Scala, one might ask exactly when the object defined by an -object definition is created and initialized. The answer is that the -object is created the first time one of its members is accessed. This -strategy is called {\em lazy evaluation}. - -\paragraph{Standard Classes} - -\todo{include picture} - -Scala is a pure object-oriented language. This means that every value -in Scala can be regarded as an object. In fact, even primitive types -such as \code{int} or \code{boolean} are not treated specially. They -are defined as type aliases of Scala classes in module \code{Predef}: -\begin{lstlisting} -type boolean = scala.Boolean; -type int = scala.Int; -type long = scala.Long; -... -\end{lstlisting} -For efficiency, the compiler usually represents values of type -\code{scala.Int} by 32 bit integers, values of type -\code{scala.Boolean} by Java's booleans, etc. But it converts these -specialized representations to objects when required, for instance -when a primitive \code{int} value is passed to a function with a -parameter of type \code{AnyRef}. Hence, the special representation of -primitive values is just an optimization, it does not change the -meaning of a program. - -Here is a specification of class \code{Boolean}. -\begin{lstlisting} -package scala; -trait Boolean { - def && (x: => Boolean): Boolean; - def || (x: => Boolean): Boolean; - def ! : Boolean; - - def == (x: Boolean) : Boolean; - def != (x: Boolean) : Boolean; - def < (x: Boolean) : Boolean; - def > (x: Boolean) : Boolean; - def <= (x: Boolean) : Boolean; - def >= (x: Boolean) : Boolean; -} -\end{lstlisting} -Booleans can be defined using only classes and objects, without -reference to a built-in type of booleans or numbers. A possible -implementation of class \code{Boolean} is given below. This is not -the actual implementation in the standard Scala library. For -efficiency reasons the standard implementation uses built-in -booleans. -\begin{lstlisting} -package scala; -trait Boolean { - def ifThenElse(thenpart: => Boolean, elsepart: => Boolean); - - def && (x: => Boolean): Boolean = ifThenElse(x, false); - def || (x: => Boolean): Boolean = ifThenElse(true, x); - def ! : Boolean = ifThenElse(false, true); - - def == (x: Boolean) : Boolean = ifThenElse(x, x.!); - def != (x: Boolean) : Boolean = ifThenElse(x.!, x); - def < (x: Boolean) : Boolean = ifThenElse(false, x); - def > (x: Boolean) : Boolean = ifThenElse(x.!, false); - def <= (x: Boolean) : Boolean = ifThenElse(x, true); - def >= (x: Boolean) : Boolean = ifThenElse(true, x.!); -} -case object True extends Boolean { - def ifThenElse(t: => Boolean, e: => Boolean) = t; -} -case object False extends Boolean { - def ifThenElse(t: => Boolean, e: => Boolean) = e; -} -\end{lstlisting} -Here is a partial specification of class \code{Int}. - -\begin{lstlisting} -package scala; -trait Int extends AnyVal { - def coerce: Long; - def coerce: Float; - def coerce: Double; - - def + (that: Double): Double; - def + (that: Float): Float; - def + (that: Long): Long; - def + (that: Int): Int; // analogous for -, *, /, % - - def << (cnt: Int): Int; // analogous for >>, >>> - - def & (that: Long): Long; - def & (that: Int): Int; // analogous for |, ^ - - def == (that: Double): Boolean; - def == (that: Float): Boolean; - def == (that: Long): Boolean; // analogous for !=, <, >, <=, >= -} -\end{lstlisting} - -Class \code{Int} can in principle also be implemented using just -objects and classes, without reference to a built in type of -integers. To see how, we consider a slightly simpler problem, namely -how to implement a type \code{Nat} of natural (i.e. non-negative) -numbers. Here is the definition of a trait \code{Nat}: -\begin{lstlisting} -trait Nat { - def isZero: Boolean; - def predecessor: Nat; - def successor: Nat; - def + (that: Nat): Nat; - def - (that: Nat): Nat; -} -\end{lstlisting} -To implement the operations of class \code{Nat}, we define a sub-object -\code{Zero} and a subclass \code{Succ} (for successor). Each number -\code{N} is represented as \code{N} applications of the \code{Succ} -constructor to \code{Zero}: -\[ -\underbrace{\mbox{\sl new Succ( ... new Succ}}_{\mbox{$N$ times}}\mbox{\sl (Zero) ... )} -\] -The implementation of the \code{Zero} object is straightforward: -\begin{lstlisting} -object Zero extends Nat { - def isZero: Boolean = true; - def predecessor: Nat = throw new Error("negative number"); - def successor: Nat = new Succ(Zero); - def + (that: Nat): Nat = that; - def - (that: Nat): Nat = if (that.isZero) Zero - else throw new Error("negative number") -} -\end{lstlisting} - -The implementation of the predecessor and subtraction functions on -\code{Zero} throws an \code{Error} exception, which aborts the program -with the given error message. - -Here is the implementation of the successor class: -\begin{lstlisting} -class Succ(x: Nat) extends Nat { - def isZero: Boolean = false; - def predecessor: Nat = x; - def successor: Nat = new Succ(this); - def + (that: Nat): Nat = x + that.successor; - def - (that: Nat): Nat = x - that.predecessor; -} -\end{lstlisting} -Note the implementation of method \code{successor}. To create the -successor of a number, we need to pass the object itself as an -argument to the \code{Succ} constructor. The object itself is -referenced by the reserved name \code{this}. - -The implementations of \code{+} and \code{-} each contain a recursive -call with the constructor argument as receiver. The recursion will -terminate once the receiver is the \code{Zero} object (which is -guaranteed to happen eventually because of the way numbers are formed). - -\begin{exercise} Write an implementation \code{Integer} of integer numbers -The implementation should support all operations of class \code{Nat} -while adding two methods -\begin{lstlisting} -def isPositive: Boolean; -def negate: Integer; -\end{lstlisting} -The first method should return \code{true} if the number is positive. The second method should negate the number. -Do not use any of Scala's standard numeric classes in your -implementation. (Hint: There are two possible ways to implement -\code{Integer}. One can either make use the existing implementation of -\code{Nat}, representing an integer as a natural number and a sign. -Or one can generalize the given implementation of \code{Nat} to -\code{Integer}, using the three subclasses \code{Zero} for 0, -\code{Succ} for positive numbers and \code{Pred} for negative numbers.) -\end{exercise} - - - -\subsection*{Language Elements Introduced In This Chapter} - -\textbf{Types:} -\begin{lstlisting} -Type = ... | ident -\end{lstlisting} - -Types can now be arbitrary identifiers which represent classes. - -\textbf{Expressions:} -\begin{lstlisting} -Expr = ... | Expr '.' ident | 'new' Expr | 'this' -\end{lstlisting} - -An expression can now be an object creation, or -a selection \code{E.m} of a member \code{m} -from an object-valued expression \code{E}, or it can be the reserved name \code{this}. - -\textbf{Definitions and Declarations:} -\begin{lstlisting} -Def = FunDef | ValDef | ClassDef | TraitDef | ObjectDef -ClassDef = ['abstract'] 'class' ident ['(' [Parameters] ')'] - ['extends' Expr] [`{' {TemplateDef} `}'] -TraitDef = 'trait' ident ['extends' Expr] ['{' {TemplateDef} '}'] -ObjectDef = 'object' ident ['extends' Expr] ['{' {ObjectDef} '}'] -TemplateDef = [Modifier] (Def | Dcl) -ObjectDef = [Modifier] Def -Modifier = 'private' | 'override' -Dcl = FunDcl | ValDcl -FunDcl = 'def' ident {'(' [Parameters] ')'} ':' Type -ValDcl = 'val' ident ':' Type -\end{lstlisting} - -A definition can now be a class, trait or object definition such as -\begin{lstlisting} -class C(params) extends B { defs } -trait T extends B { defs } -object O extends B { defs } -\end{lstlisting} -The definitions \code{defs} in a class, trait or object may be -preceded by modifiers \code{private} or \code{override}. - -Abstract classes and traits may also contain declarations. These -introduce {\em deferred} functions or values with their types, but do -not give an implementation. Deferred members have to be implemented in -subclasses before objects of an abstract class or trait can be created. - -\chapter{Case Classes and Pattern Matching} - -Say, we want to write an interpreter for arithmetic expressions. To -keep things simple initially, we restrict ourselves to just numbers -and \code{+} operations. Such expressions can be represented as a class hierarchy, with an abstract base class \code{Expr} as the root, and two subclasses \code{Number} and -\code{Sum}. Then, an expression \code{1 + (3 + 7)} would be represented as -\begin{lstlisting} -new Sum(new Number(1), new Sum(new Number(3), new Number(7))) -\end{lstlisting} -Now, an evaluator of an expression like this needs to know of what -form it is (either \code{Sum} or \code{Number}) and also needs to -access the components of the expression. The following -implementation provides all necessary methods. -\begin{lstlisting} -trait Expr { - def isNumber: boolean; - def isSum: boolean; - def numValue: int; - def leftOp: Expr; - def rightOp: Expr; -} -class Number(n: int) extends Expr { - def isNumber: boolean = true; - def isSum: boolean = false; - def numValue: int = n; - def leftOp: Expr = throw new Error("Number.leftOp"); - def rightOp: Expr = throw new Error("Number.rightOp"); -} -class Sum(e1: Expr, e2: Expr) extends Expr { - def isNumber: boolean = false; - def isSum: boolean = true; - def numValue: int = throw new Error("Sum.numValue"); - def leftOp: Expr = e1; - def rightOp: Expr = e2; -} -\end{lstlisting} -With these classification and access methods, writing an evaluator function is simple: -\begin{lstlisting} -def eval(e: Expr): int = { - if (e.isNumber) e.numValue - else if (e.isSum) eval(e.leftOp) + eval(e.rightOp) - else throw new Error("unrecognized expression kind") -} -\end{lstlisting} -However, defining all these methods in classes \code{Sum} and -\code{Number} is rather tedious. Furthermore, the problem becomes worse -when we want to add new forms of expressions. For instance, consider -adding a new expression form -\code{Prod} for products. Not only do we have to implement a new class \code{Prod}, with all previous classification and access methods; we also have to introduce a -new abstract method \code{isProduct} in class \code{Expr} and -implement that method in subclasses \code{Number}, \code{Sum}, and -\code{Prod}. Having to modify existing code when a system grows is always problematic, since it introduces versioning and maintenance problems. - -The promise of object-oriented programming is that such modifications -should be unnecessary, because they can be avoided by re-using -existing, unmodified code through inheritance. Indeed, a more -object-oriented decomposition of our problem solves the problem. The -idea is to make the ``high-level'' operation \code{eval} a method of -each expression class, instead of implementing it as a function -outside the expression class hierarchy, as we have done -before. Because \code{eval} is now a member of all expression nodes, -all classification and access methods become superfluous, and the implementation is simplified considerably: -\begin{lstlisting} -trait Expr { - def eval: int; -} -class Number(n: int) extends Expr { - def eval: int = n; -} -class Sum(e1: Expr, e2: Expr) extends Expr { - def eval: int = e1.eval + e2.eval; -} -\end{lstlisting} -Furthermore, adding a new \code{Prod} class does not entail any changes to existing code: -\begin{lstlisting} -class Prod(e1: Expr, e2: Expr) extends Expr { - def eval: int = e1.eval * e2.eval; -} -\end{lstlisting} - -The conclusion we can draw from this example is that object-oriented -decomposition is the technique of choice for constructing systems that -should be extensible with new types of data. But there is also another -possible way we might want to extend the expression example. We might -want to add new {\em operations} on expressions. For instance, we might -want to add an operation that pretty-prints an expression tree to standard output. - -If we have defined all classification and access methods, such an -operation can easily be written as an external function. Here is an -implementation: -\begin{lstlisting} -def print(e: Expr): unit = - if (e.isNumber) System.out.print(e.numValue) - else if (e.isSum) { - System.out.print("("); - print(e.leftOp); - System.out.print("+"); - print(e.rightOp); - System.out.print(")"); - } else throw new Error("unrecognized expression kind"); -\end{lstlisting} -However, if we had opted for an object-oriented decomposition of -expressions, we would need to add a new \code{print} method -to each class: -\begin{lstlisting} -trait Expr { - def eval: int; - def print: unit; -} -class Number(n: int) extends Expr { - def eval: int = n; - def print: unit = System.out.print(n); -} -class Sum(e1: Expr, e2: Expr) extends Expr { - def eval: int = e1.eval + e2.eval; - def print: unit = { - System.out.print("("); - print(e1); - System.out.print("+"); - print(e2); - System.out.print(")"); -} -\end{lstlisting} -Hence, classical object-oriented decomposition requires modification -of all existing classes when a system is extended with new operations. - -As yet another way we might want to extend the interpreter, consider -expression simplification. For instance, we might want to write a -function which rewrites expressions of the form -\code{a * b + a * c} to \code{a * (b + c)}. This operation requires inspection of -more than a single node of the expression tree at the same -time. Hence, it cannot be implemented by a method in each expression -kind, unless that method can also inspect other nodes. So we are -forced to have classification and access methods in this case. This -seems to bring us back to square one, with all the problems of -verbosity and extensibility. - -Taking a closer look, one observers that the only purpose of the -classification and access functions is to {\em reverse} the data -construction process. They let us determine, first, which sub-class -of an abstract base class was used and, second, what were the -constructor arguments. Since this situation is quite common, Scala has -a way to automate it with case classes. - -\section{Case Classes and Case Objects} - -{\em Case classes} and {\em case objects} are defined like a normal -classes or objects, except that the definition is prefixed with the modifier -\code{case}. For instance, the definitions -\begin{lstlisting} -trait Expr; -case class Number(n: int) extends Expr; -case class Sum(e1: Expr, e2: Expr) extends Expr; -\end{lstlisting} -introduce \code{Number} and \code{Sum} as case classes. -The \code{case} modifier in front of a class or object -definition has the following effects. -\begin{enumerate} -\item Case classes implicitly come with a constructor function, with the same name as the class. In our example, the two functions -\begin{lstlisting} -def Number(n: int) = new Number(n); -def Sum(e1: Expr, e2: Expr) = new Sum(e1, e2); -\end{lstlisting} -would be added. Hence, one can now construct expression trees a bit more concisely, as in -\begin{lstlisting} -Sum(Sum(Number(1), Number(2)), Number(3)) -\end{lstlisting} -\item Case classes and case objects -implicitly come with implementations of methods -\code{toString}, \code{equals} and \code{hashCode}, which override the -methods with the same name in class \code{AnyRef}. The implementation -of these methods takes in each case the structure of a member of a -case class into account. The \code{toString} method represents an -expression tree the way it was constructed. So, -\begin{lstlisting} -Sum(Sum(Number(1), Number(2)), Number(3)) -\end{lstlisting} -would be converted to exactly that string, whereas the default -implementation in class \code{AnyRef} would return a string consisting -of the outermost constructor name \code{Sum} and a number. The -\code{equals} methods treats two case members of a case class as equal -if they have been constructed with the same constructor and with -arguments which are themselves pairwise equal. This also affects the -implementation of \code{==} and \code{!=}, which are implemented in -terms of \code{equals} in Scala. So, -\begin{lstlisting} -Sum(Number(1), Number(2)) == Sum(Number(1), Number(2)) -\end{lstlisting} -will yield \code{true}. If \code{Sum} or \code{Number} were not case -classes, the same expression would be \code{false}, since the standard -implementation of \code{equals} in class \code{AnyRef} always treats -objects created by different constructor calls as being different. -The \code{hashCode} method follows the same principle as other two -methods. It computes a hash code from the case class constructor name -and the hash codes of the constructor arguments, instead of from the object's -address, which is what the as the default implementation of \code{hashCode} does. -\item -Case classes implicitly come with nullary accessor methods which -retrieve the constructor arguments. -In our example, \code{Number} would obtain an accessor method -\begin{lstlisting} -def n: int; -\end{lstlisting} -which returns the constructor parameter \code{n}, whereas \code{Sum} would obtain two accessor methods -\begin{lstlisting} -def e1: Expr, e2: Expr; -\end{lstlisting} -Hence, if for a value \code{s} of type \code{Sum}, say, one can now -write \code{s.e1}, to access the left operand. However, for a value -\code{e} of type \code{Expr}, the term \code{e.e1} would be illegal -since \code{e1} is defined in \code{Sum}; it is not a member of the -base class \code{Expr}. -So, how do we determine the constructor and access constructor -arguments for values whose static type is the base class \code{Expr}? -This is solved by the fourth and final particularity of case classes. -\item -Case classes allow the constructions of {\em patterns} which refer to -the case class constructor. -\end{enumerate} - -\section{Pattern Matching} - -Pattern matching is a generalization of C or Java's \code{switch} -statement to class hierarchies. Instead of a \code{switch} statement, -there is a standard method \code{match}, which is defined in Scala's -root class \code{Any}, and therefore is available for all objects. -The \code{match} method takes as argument a number of cases. -For instance, here is an implementation of \code{eval} using -pattern matching. -\begin{lstlisting} -def eval(e: Expr): int = e match { - case Number(x) => x - case Sum(l, r) => eval(l) + eval(r) -} -\end{lstlisting} -In this example, there are two cases. Each case associates a pattern -with an expression. Patterns are matched against the selector -values \code{e}. The first pattern in our example, -\code{Number(n)}, matches all values of the form \code{Number(v)}, -where \code{v} is an arbitrary value. In that case, the {\em pattern -variable} \code{n} is bound to the value \code{v}. Similarly, the -pattern \code{Sum(l, r)} matches all selector values of form -\code{Sum(v}$_1$\code{, v}$_2$\code{)} and binds the pattern variables -\code{l} and \code{r} -to \code{v}$_1$ and \code{v}$_2$, respectively. - -In general, patterns are built from -\begin{itemize} -\item Case class constructors, e.g. \code{Number}, \code{Sum}, whose arguments - are again patterns, -\item pattern variables, e.g. \code{n}, \code{e1}, \code{e2}, -\item the ``wildcard'' pattern \code{_}, -\item literals, e.g. \code{1}, \code{true}, "abc", -\item constant identifiers, e.g. \code{MAXINT}, \code{EmptySet}. -\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. Each variable name may occur only once in a -pattern. For instance, \code{Sum(x, x)} would be illegal as a pattern, -since the pattern variable \code{x} occurs twice in it. - -\paragraph{Meaning of Pattern Matching} -A pattern matching expression -\begin{lstlisting} -e match { case p$_1$ => e$_1$ ... case p$_n$ => e$_n$ } -\end{lstlisting} -matches the patterns $p_1 \commadots p_n$ in the order they -are written against the selector value \code{e}. -\begin{itemize} -\item -A constructor pattern $C(p_1 \commadots p_n)$ matches all values that -are of type \code{C} (or a subtype thereof) and that have been constructed with -\code{C}-arguments matching patterns $p_1 \commadots p_n$. -\item -A variable pattern \code{x} matches any value and binds the variable -name to that value. -\item -The wildcard pattern `\code{_}' matches any value but does not bind a name to that value. -\item A constant pattern \code{C} matches a value which is -equal (in terms of \code{==}) to \code{C}. -\end{itemize} -The pattern matching expression rewrites to the right-hand-side of the -first case whose pattern matches the selector value. References to -pattern variables are replaced by corresponding constructor arguments. -If none of the patterns matches, the pattern matching expression is -aborted with a \code{MatchError} exception. - -\example Our substitution model of program evaluation extends quite naturally to pattern matching, For instance, here is how \code{eval} applied to a simple expression is re-written: -\begin{lstlisting} - eval(Sum(Number(1), Number(2))) - --> $\mbox{\tab\tab\rm(by rewriting the application)}$ - - Sum(Number(1), Number(2)) match { - case Number(n) => n - case Sum(e1, e2) => eval(e1) + eval(e2) - } - --> $\mbox{\tab\tab\rm(by rewriting the pattern match)}$ - - eval(Number(1)) + eval(Number(2)) - --> $\mbox{\tab\tab\rm(by rewriting the first application)}$ - - Number(1) match { - case Number(n) => n - case Sum(e1, e2) => eval(e1) + eval(e2) - } + eval(Number(2)) - --> $\mbox{\tab\tab\rm(by rewriting the pattern match)}$ - - 1 + eval(Number(2)) - -->$^*$ 1 + 2 -> 3 -\end{lstlisting} - -\paragraph{Pattern Matching and Methods} -In the previous example, we have used pattern -matching in a function which was defined outside the class hierarchy -over which it matches. Of course, it is also possible to define a -pattern matching function in that class hierarchy itself. For -instance, we could have defined -\code{eval} is a method of the base class \code{Expr}, and still have used pattern matching in its implementation: -\begin{lstlisting} -trait Expr { - def eval: int = this match { - case Number(n) => n - case Sum(e1, e2) => e1.eval + e2.eval - } -} -\end{lstlisting} - -\begin{exercise} Consider the following definitions representing trees -of integers. These definitions can be seen as an alternative -representation of \code{IntSet}: -\begin{lstlisting} -trait IntTree; -case object EmptyTree extends IntTree; -case class Node(elem: int, left: IntTree, right: IntTree) extends IntTree; -\end{lstlisting} -Complete the following implementations of function \code{contains} and \code{insert} for -\code{IntTree}'s. -\begin{lstlisting} -def contains(t: IntTree, v: int): boolean = t match { ... - ... -} -def insert(t: IntTree, v: int): IntTree = t match { ... - ... -} -\end{lstlisting} -\end{exercise} - -\paragraph{Pattern Matching Anonymous Functions} - -So far, case-expressions always appeared in conjunction with a -\verb@match@ operation. But it is also possible to use -case-expressions by themselves. A block of case-expressions such as -\begin{lstlisting} -{ case $P_1$ => $E_1$ ... case $P_n$ => $E_n$ } -\end{lstlisting} -is seen by itself as a function which matches its arguments -against the patterns $P_1 \commadots P_n$, and produces the result of -one of $E_1 \commadots E_n$. (If no pattern matches, the function -would throw a \code{MatchError} exception instead). -In other words, the expression above is seen as a shorthand for the anonymous function -\begin{lstlisting} -(x => x match { case $P_1$ => $E_1$ ... case $P_n$ => $E_n$ }) -\end{lstlisting} -where \code{x} is a fresh variable which is not used -otherwise in the expression. - -\chapter{Generic Types and Methods} - -Classes in Scala can have type parameters. We demonstrate the use of -type parameters with functional stacks as an example. Say, we want to -write a data type of stacks of integers, with methods \code{push}, -\code{top}, \code{pop}, and \code{isEmpty}. This is achieved by the -following class hierarchy: -\begin{lstlisting} -trait IntStack { - def push(x: int): IntStack = new IntNonEmptyStack(x, this); - def isEmpty: boolean; - def top: int; - def pop: IntStack; -} -class IntEmptyStack extends IntStack { - def isEmpty = true; - def top = throw new Error("EmptyStack.top"); - def pop = throw new Error("EmptyStack.pop"); -} -class IntNonEmptyStack(elem: int, rest: IntStack) { - def isEmpty = false; - def top = elem; - def pop = rest; -} -\end{lstlisting} -Of course, it would also make sense to define an abstraction for a -stack of Strings. To do that, one could take the existing abstraction -for \code{IntStack}, rename it to \code{StringStack} and at the same -time rename all occurrences of type \code{int} to \code{String}. - -A better way, which does not entail code duplication, is to -parameterize the stack definitions with the 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 -{\em generic} version of \code{Stack}, we equip it with a type -parameter. -\begin{lstlisting} -trait Stack[a] { - def push(x: a): Stack[a] = new NonEmptyStack[a](x, this); - def isEmpty: boolean - def top: a; - def pop: Stack[a]; -} -class EmptyStack[a] extends Stack[a] { - def isEmpty = true; - def top = throw new Error("EmptyStack.top"); - def pop = throw new Error("EmptyStack.pop"); -} -class NonEmptyStack[a](elem: a, rest: Stack[a]) extends Stack[a] { - def isEmpty = false; - def top = elem; - def pop = rest; -} -\end{lstlisting} -In the definitions above, `\code{a}' is a {\em type parameter} of -class \code{Stack} and its subclasses. Type parameters are arbitrary -names; they are enclosed in brackets instead of parentheses, so that -they can be easily distinguished from value parameters. Here is an -example how the generic classes are used: -\begin{lstlisting} -val x = new EmptyStack[int]; -val y = x.push(1).push(2); -System.out.println(y.pop.top); -\end{lstlisting} -The first line creates a new empty stack of \code{int}'s. Note the -actual type argument \code{[int]} which replaces the formal type -parameter \code{a}. - -It is also possible to parameterize methods with types. As an example, -here is a generic method which determines whether one stack is a -prefix of another. -\begin{lstlisting} -def isPrefix[a](p: Stack[a], s: Stack[a]): boolean = { - p.isEmpty || - p.top == s.top && isPrefix[a](p.pop, s.pop); -} -\end{lstlisting} -parameters are called {\em polymorphic}. Generic methods are also -called {\em polymorphic}. The term comes from the Greek, where it -means ``having many forms''. To apply a polymorphic method such as -\code{isPrefix}, we pass type parameters as well as value parameters -to it. For instance, -\begin{lstlisting} -val s1 = new EmptyStack[String].push("abc"); -val s2 = new EmptyStack[String].push("abx").push(s.pop) -System.out.println(isPrefix[String](s1, s2)); -\end{lstlisting} - -\paragraph{Local Type Inference} -Passing type parameters such as \code{[int]} or \code{[String]} all -the time can become tedious in applications where generic 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 expression \code{isPrefix[String](s1, s2)} as an -example, we know that its value parameters are both of type -\code{Stack[String]}, so we can deduce that the type parameter must -be \code{String}. 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, one -could have written \code{isPrefix(s1, s2)} and the missing type argument -\code{[String]} would have been inserted by the type inferencer. - -\section{Type Parameter Bounds} - -Now that we know how to make classes generic it is natural to -generalize some of the earlier classes we have written. For instance -class \code{IntSet} could be generalized to sets with arbitrary -element types. Let's try. The trait for generic sets is easily -written. -\begin{lstlisting} -trait Set[a] { - def incl(x: a): Set[a]; - def contains(x: a): boolean; -} -\end{lstlisting} -However, if we still want to implement sets as binary search trees, we -encounter a problem. The \code{contains} and \code{incl} methods both -compare elements using methods \code{<} and \code{>}. For -\code{IntSet} this was OK, since type \code{int} has these two -methods. But for an arbitrary type parameter \code{a}, we cannot -guarantee this. Therefore, the previous implementation of, say, -\code{contains} would generate a compiler error. -\begin{lstlisting} - def contains(x: int): boolean = - if (x < elem) left contains x - ^ < $\mbox{\sl not a member of type}$ a. -\end{lstlisting} -One way to solve the problem is to restrict the legal types that can -be substituted for type \code{a} to only those types that contain methods -\code{<} and \code{>} of the correct types. There is a trait -\code{Ord[a]} in the standard class library Scala which represents -values which are comparable (via \code{<} and \code{>}) to values of -type \code{a}. We can enforce the comparability of a type by demanding -that the type is a subtype of \code{Ord}. This is done by giving an -upper bound to the type parameter of \code{Set}: -\begin{lstlisting} -trait Set[a <: Ord[a]] { - def incl(x: a): Set[a]; - def contains(x: a): boolean; -} -\end{lstlisting} -The parameter declaration \code{a <: Ord[a]} introduces \code{a} as a -type parameter which must be a subtype of \code{Ord[a]}, i.e.\ its values -must be comparable to values of the same type. - -With this restriction, we can now implement the rest of the generic -set abstraction as we did in the case of \code{IntSet}s before. - -\begin{lstlisting} -class EmptySet[a <: Ord[a]] extends Set[a] { - def contains(x: a): boolean = false; - def incl(x: a): Set[a] = new NonEmptySet(x, new EmptySet[a], new EmptySet[a]); -} -\end{lstlisting} - -\begin{lstlisting} -class NonEmptySet[a <: Ord[a]] - (elem:a, left: Set[a], right: Set[a]) extends Set[a] { - def contains(x: a): boolean = - if (x < elem) left contains x - else if (x > elem) right contains x - else true; - def incl(x: a): Set[a] = - if (x < elem) new NonEmptySet(elem, left incl x, right) - else if (x > elem) new NonEmptySet(elem, left, right incl x) - else this; -} -\end{lstlisting} -Note that we have left out the type argument in the object creations -\code{new NonEmptySet(...)}. In the same way as for polymorphic methods, -missing type arguments in constructor calls are inferred from value -arguments and/or the expected result type. - -Here is an example that uses the generic set abstraction. -\begin{lstlisting} -val s = new EmptySet[double].incl(1.0).incl(2.0); -s.contains(1.5) -\end{lstlisting} -This is OK, as type \code{double} implements trait \code{Ord[double]}. -However, the following example is in error. -\begin{lstlisting} -val s = new EmptySet[java.io.File] - ^ java.io.File $\mbox{\sl does not conform to type}$ - $\mbox{\sl parameter bound}$ Ord[java.io.File]. -\end{lstlisting} -To conclude the discussion of type parameter -bounds, here is the definition of trait \code{Ord} in scala. -\begin{lstlisting} -package scala; -trait Ord[t <: Ord[t]]: t { - def < (that: t): Boolean; - def <=(that: t): Boolean = this < that || this == that; - def > (that: t): Boolean = that < this; - def >=(that: t): Boolean = that <= this; -} -\end{lstlisting} - -\section{Variance Annotations}\label{sec:first-arrays} - -The combination of type parameters and subtyping poses some -interesting questions. For instance, should \code{Stack[String]} be a -subtype of \code{Stack[AnyRef]}? Intuitively, this seems OK, since a -stack of \code{String}s is a special case of a stack of -\code{AnyRef}s. More generally, if \code{T} is a subtype of type \code{S} -then \code{Stack[T]} should be a subtype of \code{Stack[S]}. -This property is called {\em co-variant} subtyping. - -In Scala, generic types have by default non-variant subtyping. That -is, with \code{Stack} defined as above, stacks with different element -types would never be in a subtype relation. However, we can enforce -co-variant subtyping of stacks by changing the first line of the -definition of class \code{Stack} as follows. -\begin{lstlisting} -class Stack[+a] { -\end{lstlisting} -Prefixing a formal type parameter with a \code{+} indicates that -subtyping is covariant in that parameter. -Besides \code{+}, there is also a prefix \code{-} which indicates -contra-variant subtyping. If \code{Stack} was defined \code{class -Stack[-a] ...}, then \code{T} a subtype of type \code{S} would imply -that \code{Stack[S]} is a subtype of \code{Stack[T]} (which in the -case of stacks would be rather surprising!). - -In a purely functional world, all types could be co-variant. However, -the situation changes once we introduce mutable data. Consider the -case of arrays in Java or .NET. Such arrays are represented in Scala -by a generic class \code{Array}. Here is a partial definition of this -class. -\begin{lstlisting} -class Array[a] { - def apply(index: int): a; - def update(index: int, elem: a): unit; -} -\end{lstlisting} -The class above defines the way Scala arrays are seen from Scala user -programs. The Scala compiler will map this abstraction to the -underlying arrays of the host system in most cases where this -possible. - -In Java, arrays are indeed covariant; that is, for reference types -\code{T} and \code{S}, if \code{T} is a subtype of \code{S}, then also -\code{Array[T]} is a subtype of \code{Array[S]}. This might seem -natural but leads to safety problems that require special runtime -checks. Here is an example: -\begin{lstlisting} -val x = new Array[String](1); -val y: Array[Any] = x; -y(0) = new Rational(1, 2); // this is syntactic sugar for - // y.update(0, new Rational(1, 2)); -\end{lstlisting} -In the first line, a new array of strings is created. In the second -line, this array is bound to a variable \code{y}, of type -\code{Array[Any]}. Assuming arrays are covariant, this is OK, since -\code{Array[String]} is a subtype of \code{Array[Any]}. Finally, in -the last line a rational number is stored in the array. This is also -OK, since type \code{Rational} is a subtype of the element type -\code{Any} of the array \code{y}. We thus end up storing a rational -number in an array of strings, which clearly violates type soundness. - -Java solves this problem by introducing a run-time check in the third -line which tests whether the stored element is compatible with the -element type with which the array was created. We have seen in the -example that this element type is not necessarily the static element -type of the array being updated. If the test fails, an -\code{ArrayStoreException} is raised. - -Scala solves this problem instead statically, by disallowing the -second line at compile-time, because arrays in Scala have non-variant -subtyping. This raises the question how a Scala compiler verifies that -variance annotations are correct. If we had simply declared arrays -co-variant, how would the potential problem have been detected? - -Scala uses a conservative approximation to verify soundness of -variance annotations. A covariant type parameter of a class may only -appear in co-variant positions inside the class. Among the co-variant -positions are the types of values in the class, the result types of -methods in the class, and type arguments to other covariant types. Not -co-variant are types of formal method parameters. Hence, the following -class definition would have been rejected -\begin{lstlisting} -class Array[+a] { - def apply(index: int): a; - def update(index: int, elem: a): unit; - ^ $\mbox{\sl covariant type parameter}$ a - $\mbox{\sl appears in contravariant position.}$ -} -\end{lstlisting} -So far, so good. Intuitively, the compiler was correct in rejecting -the \code{update} method in a co-variant class because \code{update} -potentially changes state, and therefore undermines the soundness of -co-variant subtyping. - -However, there are also methods which do not mutate state, but where a -type parameter still appears contra-variantly. An example is -\code{push} in type \code{Stack}. Again the Scala compiler will reject -the definition of this method for co-variant stacks. -\begin{lstlisting} -class Stack[+a] { - def push(x: a): Stack[a] = - ^ $\mbox{\sl covariant type parameter}$ a - $\mbox{\sl appears in contravariant position.}$ -\end{lstlisting} -This is a pity, because, unlike arrays, stacks are purely functional data -structures and therefore should enable co-variant subtyping. However, -there is a a way to solve the problem by using a polymorphic method -with a lower type parameter bound. - -\section{Lower Bounds} - -We have seen upper bounds for type parameters. In a type parameter -declaration such as \code{t <: U}, the type parameter \code{t} is -restricted to range only over subtypes of type \code{U}. Symmetrical -to this are lower bounds in Scala. In a type parameter declaration -\code{t >: L}, the type parameter \code{t} is restricted to range only -over {\em supertypes} of type \code{L}. (One can also combine lower and -upper bounds, as in \code{t >: L <: U}.) - -Using lower bounds, we can generalize the \code{push} method in -\code{Stack} as follows. -\begin{lstlisting} -class Stack[+a] { - def push[b >: a](x: b): Stack[b] = new NonEmptyStack(x, this); -\end{lstlisting} -Technically, this solves our variance problem since now the type -parameter \code{a} appears no longer as a parameter type of method -\code{push}. Instead, it appears as lower bound for another type -parameter of a method, which is classified as a co-variant position. -Hence, the Scala compiler accepts the new definition of \code{push}. - -In fact, we have not only solved the technical variance problem but -also have generalized the definition of \code{push}. Before, we were -required to push only elements with types that conform to the declared -element type of the stack. Now, we can push also elements of a -supertype of this type, but the type of the returned stack will change -accordingly. For instance, we can now push an \code{AnyRef} onto a -stack of \code{String}s, but the resulting stack will be a stack of -\code{AnyRef}s instead of a stack of \code{String}s! - -In summary, one should not hesitate to add variance annotations to -your data structures, as this yields rich natural subtyping -relationships. The compiler will detect potential soundness -problems. Even if the compiler's approximation is too conservative, as -in the case of method \code{push} of class \code{Stack}, this will -often suggest a useful generalization of the contested method. - -\section{Least Types} - -Scala does not allow one to parameterize objects with types. That's -why we originally defined a generic class \code{EmptyStack[a]}, even -though a single value denoting empty stacks of arbitrary type would -do. For co-variant stacks, however, one can use the following idiom: -\begin{lstlisting} -object EmptyStack extends Stack[All] { ... } -\end{lstlisting} -The identifier \code{All} refers to the bottom type \code{scala.All}, -which is a subtype of all other types. Hence, for co-variant stacks, -\code{Stack[All]} is a subtype of \code{Stack[T]}, for any other type -\code{T}. This makes it possible to use a single empty stack object -in user code. For instance: -\begin{lstlisting} -val s = EmptyStack.push("abc").push(new AnyRef()); -\end{lstlisting} -Let's analyze the type assignment for this expression in detail. The -\code{EmptyStack} object is of type \code{Stack[All]}, which has a -method -\begin{lstlisting} -push[b >: All](elem: b): Stack[b] . -\end{lstlisting} -Local type inference will determine that the type parameter \code{b} -should be instantiated to \code{String} in the application -\code{EmptyStack.push("abc")}. The result type of that application is hence -\code{Stack[String]}, which in turn has a method -\begin{lstlisting} -push[b >: String](elem: b): Stack[b] . -\end{lstlisting} -The final part of the value definition above is the application of -this method to \code{new AnyRef()}. Local type inference will -determine that the type parameter \code{b} should this time be -instantiated to \code{AnyRef}, with result type \code{Stack[AnyRef]}. -Hence, the type assigned to value \code{s} is \code{Stack[AnyRef]}. - -Besides \code{scala.All}, which is a subtype of every other type, -there is also the type \code{scala.AllRef}, which is a subtype of -\code{scala.AnyRef}, and every type derived from it. The \code{null} -literal in Scala is of that type. This makes \code{null} compatible -with every reference type, but not with a value type such as -\code{int}. - -We conclude this section with the complete improved definition of -stacks. Stacks have now co-variant subtyping, the \code{push} method -has been generalized, and the empty stack is represented by a single -object. -\begin{lstlisting} -trait Stack[+a] { - def push[b >: a](x: b): Stack[b] = new NonEmptyStack(x, this); - def isEmpty: boolean; - def top: a; - def pop: Stack[a]; -} -object EmptyStack extends Stack[All] { - def isEmpty = true; - def top = throw new Error("EmptyStack.top"); - def pop = throw new Error("EmptyStack.pop"); -} -class NonEmptyStack[+a](elem: a, rest: Stack[a]) extends Stack[a] { - def isEmpty = false; - def top = elem; - def pop = rest; -} -\end{lstlisting} -Many classes in the Scala library are generic. We now present two -commonly used families of generic classes, tuples and functions. The -discussion of another common class, lists, is deferred to the next -chapter. - -\section{Tuples} - -Sometimes, a function needs to return more than one result. For -instance, take the function \code{divmod} which returns the integer quotient -and rest of two given integer arguments. Of course, one can define a -class to hold the two results of \code{divmod}, as in: -\begin{lstlisting} -case class TwoInts(first: int, second: int); -def divmod(x: int, y: int): TwoInts = new TwoInts(x / y, x % y); -\end{lstlisting} -However, having to define a new class for every possible pair of -result types is very tedious. In Scala one can use instead a -the generic classes \lstinline@Tuple$n$@, for each $n$ between -2 and 9. As an example, here is the definition of Tuple2. -\begin{lstlisting} -package scala; -case class Tuple2[a, b](_1: a, _2: b); -\end{lstlisting} -With \code{Tuple2}, the \code{divmod} method can be written as follows. -\begin{lstlisting} -def divmod(x: int, y: int) = new Tuple2[int, int](x / y, x % y); -\end{lstlisting} -As usual, type parameters to constructors can be omitted if they are -deducible from value arguments. Also, Scala defines an alias -\code{Pair} for \code{Tuple2} (as well as \code{Triple} for \code{Tuple3}). -With these conventions, \code{divmod} can equivalently be written as -follows. -\begin{lstlisting} -def divmod(x: int, y: int) = Pair(x / y, x % y); -\end{lstlisting} -How are elements of tuples accessed? Since tuples are case classes, -there are two possibilities. One can either access a tuple's fields -using the names of the constructor parameters \lstinline@_$i$@, as in the following example: -\begin{lstlisting} -val xy = divmod(x, y); -System.out.println("quotient: " + x._1 + ", rest: " + x._2); -\end{lstlisting} -Or one uses pattern matching on tuples, as in the following example: -\begin{lstlisting} -divmod(x, y) match { - case Pair(n, d) => - System.out.println("quotient: " + n + ", rest: " + d); -} -\end{lstlisting} -Note that type parameters are never used in patterns; it would have -been illegal to write case \code{Pair[int, int](n, d)}. - -\section{Functions}\label{sec:functions} - -Scala is a functional language in that functions are first-class -values. Scala is also an object-oriented language in that every value -is an object. It follows that functions are objects in Scala. For -instance, a function from type \code{String} to type \code{int} is -represented as an instance of the trait \code{Function1[String, int]}. -The \code{Function1} trait is defined as follows. -\begin{lstlisting} -package scala; -trait Function1[-a, +b] { - def apply(x: a): b; -} -\end{lstlisting} -Besides \code{Function1}, there are also definitions of -\code{Function0} and \code{Function2} up to \code{Function9} in the -standard Scala library. That is, there is one definition for each -possible number of function parameters between 0 and 9. Scala's -function type syntax ~\lstinline@$T_1 \commadots T_n$ => $S$@~ is -simply an abbreviation for the parameterized type -~\lstinline@Function$n$[$T_1 \commadots T_n, S$]@~. - -Scala uses the same syntax $f(x)$ for function application, no matter -whether $f$ is a method or a function object. This is made possible by -the following convention: A function application $f(x)$ where $f$ is -an object (as opposed to a method) is taken to be a shorthand for -\lstinline@$f$.apply($x$)@. Hence, the \code{apply} method of a -function type is inserted automatically where this is necessary. - -That's also why we defined array subscripting in -Section~\ref{sec:first-arrays} by an \code{apply} method. For any -array \code{a}, the subscript operation \code{a(i)} is taken to be a -shorthand for \code{a.apply(i)}. - -Functions are an example where a contra-variant type parameter -declaration is useful. For example, consider the following code: -\begin{lstlisting} -val f: (AnyRef => int) = x => x.hashCode(); -val g: (String => int) = f; -g("abc") -\end{lstlisting} -It's sound to bind the value \code{g} of type \code{String => int} to -\code{f}, which is of type \code{AnyRef => int}. Indeed, all one can -do with function of type \code{String => int} is pass it a string in -order to obtain an integer. Clearly, the same works for function -\code{f}: If we pass it a string (or any other object), we obtain an -integer. This demonstrates that function subtyping is contra-variant -in its argument type whereas it is covariant in its result type. -In short, $S \Rightarrow T$ is a subtype of $S' \Rightarrow T'$, provided -$S'$ is a subtype of $S$ and $T$ is a subtype of $T'$. - -\example Consider the Scala code -\begin{lstlisting} -val plus1: (int => int) = (x: int) => x + 1; -plus1(2) -\end{lstlisting} -This is expanded into the following object code. -\begin{lstlisting} -val plus1: Function1[int, int] = new Function1[int, int] { - def apply(x: int): int = x + 1; -} -plus1.apply(2) -\end{lstlisting} -Here, the object creation \lstinline@new Function1[int, int]{ ... }@ -represents an instance of an {\em anonymous class}. It combines the -creation of a new \code{Function1} object with an implementation of -the \code{apply} method (which is abstract in \code{Function1}). -Equivalently, but more verbosely, one could have used a local class: -\begin{lstlisting} -val plus1: Function1[int, int] = { - class Local extends Function1[int, int] { - def apply(x: int): int = x + 1; - } - new Local: Function1[int, int] -} -plus1.apply(2) -\end{lstlisting} - -\chapter{Lists} - -Lists are an important data structure in many Scala programs. -A list containing the elements \code{x}$_1$, \ldots, \code{x}$_n$ is written -\code{List(x}$_1$\code{, ..., x}$_n$\code{)}. Examples are: -\begin{lstlisting} -val fruit = List("apples", "oranges", "pears"); -val nums = List(1, 2, 3, 4); -val diag3 = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1)); -val empty = List(); -\end{lstlisting} -Lists are similar to arrays in languages such as C or Java, but there -are also three important differences. First, lists are immutable. That -is, elements of a list cannot 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. - -\section{Using Lists} - -\paragraph{The List type} -Like arrays, lists are {\em homogeneous}. That is, the elements of a -list all have the same type. The type of a list with elements of type -\code{T} is written \code{List[T]} (compare to \code{T[]} in Java). -\begin{lstlisting} -val fruit: List[String] = List("apples", "oranges", "pears"); -val nums : List[int] = List(1, 2, 3, 4); -val diag3: List[List[int]] = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1)); -val empty: List[int] = List(); -\end{lstlisting} - -\paragraph{List constructors} -All lists are built from two more fundamental constructors, \code{Nil} -and \code{::} (pronounced ``cons''). \code{Nil} represents an empty -list. The infix operator \code{::} expresses list extension. That is, -\code{x :: xs} represents a list whose first element is \code{x}, -which is followed by (the elements of) list \code{xs}. Hence, the -list values above could also have been defined as follows (in fact -their previous definition is simply syntactic sugar for the definitions below). -\begin{lstlisting} -val fruit = "apples" :: ("oranges" :: ("pears" :: Nil)); -val nums = 1 :: (2 :: (3 :: (4 :: Nil))); -val diag3 = (1 :: (0 :: (0 :: Nil))) :: - (0 :: (1 :: (0 :: Nil))) :: - (0 :: (0 :: (1 :: Nil))) :: Nil; -val empty = Nil; -\end{lstlisting} -The `\code{::}' operation associates to the right: \code{A :: B :: C} is -interpreted as \code{A :: (B :: C)}. Therefore, we can drop the -parentheses in the definitions above. For instance, we can write -shorter -\begin{lstlisting} -val nums = 1 :: 2 :: 3 :: 4 :: Nil; -\end{lstlisting} - -\paragraph{Basic operations on lists} -All operations on lists can be expressed in terms of the following three: - -\begin{tabular}{ll} -\code{head} & returns the first element of a list,\\ -\code{tail} & returns the list consisting of all elements except the\\ -& first element,\\ -\code{isEmpty} & returns \code{true} iff the list is empty -\end{tabular} - -These operations are defined as methods of list objects. So we invoke -them by selecting from the list that's operated on. Examples: -\begin{lstlisting} -empty.isEmpty = true -fruit.isEmpty = false -fruit.head = "apples" -fruit.tail.head = "oranges" -diag3.head = List(1, 0, 0) -\end{lstlisting} -The \code{head} and \code{tail} methods are defined only for non-empty -lists. When selected from an empty list, they throw an exception. - -As an example of how lists can be processed, consider sorting the -elements of a list of numbers into ascending order. One simple way to -do so is {\em insertion sort}, which works as follows: To sort a -non-empty list with first element \code{x} and rest \code{xs}, sort -the remainder \code{xs} and insert the element \code{x} at the right -position in the result. Sorting an empty list will yield the -empty list. Expressed as Scala code: -\begin{lstlisting} -def isort(xs: List[int]): List[int] = - if (xs.isEmpty) Nil - else insert(xs.head, isort(xs.tail)); -\end{lstlisting} - -\begin{exercise} Provide an implementation of the missing function -\code{insert}. -\end{exercise} - -\paragraph{List patterns} In fact, \code{::} is defined as a case -class in Scala's standard library. Hence, it is possible to decompose -lists by pattern matching, using patterns composed from the \code{Nil} -and \code{::} constructors. For instance, \code{isort} can be written -alternatively as follows. -\begin{lstlisting} -def isort(xs: List[int]): List[int] = xs match { - case List() => List() - case x :: xs1 => insert(x, isort(xs1)) -} -\end{lstlisting} -where -\begin{lstlisting} -def insert(x: int, xs: List[int]): List[int] = xs match { - case List() => List(x) - case y :: ys => if (x <= y) x :: xs else y :: insert(x, ys) -} -\end{lstlisting} - -\section{Definition of class List I: First Order Methods} -\label{sec:list-first-order} - -Lists are not built in in Scala; they are defined by an abstract class -\code{List}, which comes with two subclasses for \code{::} and \code{Nil}. -In the following we present a tour through class \code{List}. -\begin{lstlisting} -package scala; -abstract class List[+a] { -\end{lstlisting} -\code{List} is an abstract class, so one cannot define elements by -calling the empty \code{List} constructor (e.g. by -\code{new List}). The class has a type parameter \code{a}. It is -co-variant in this parameter, which means that -\code{List[S] <: List[T]} for all types \code{S} and \code{T} such that -\code{S <: T}. The class is situated in the package -\code{scala}. This is a package containing the most important standard -classes of Scala. - \code{List} defines a number of methods, which are -explained in the following. - -\paragraph{Decomposing lists} -First, there are the three basic methods \code{isEmpty}, -\code{head}, \code{tail}. Their implementation in terms of pattern -matching is straightforward: -\begin{lstlisting} -def isEmpty: boolean = match { - case Nil => true - case x :: xs => false -} -def head: a = match { - case Nil => throw new Error("Nil.head") - case x :: xs => x -} -def tail: List[a] = match { - case Nil => throw new Error("Nil.tail") - case x :: xs => x -} -\end{lstlisting} - -The next function computes the length of a list. -\begin{lstlisting} -def length = match { - case Nil => 0 - case x :: xs => 1 + xs.length -} -\end{lstlisting} -\begin{exercise} Design a tail-recursive version of \code{length}. -\end{exercise} - -The next two functions are the complements of \code{head} and -\code{tail}. -\begin{lstlisting} -def last: a; -def init: List[a]; -\end{lstlisting} -\code{xs.last} returns the last element of list \code{xs}, whereas -\code{xs.init} returns all elements of \code{xs} except the last. -Both functions have to traverse the entire list, and are thus less -efficient than their \code{head} and \code{tail} analogues. -Here is the implementation of \code{last}. -\begin{lstlisting} -def last: a = match { - case Nil => throw new Error("Nil.last") - case x :: Nil => x - case x :: xs => xs.last -} -\end{lstlisting} -The implementation of \code{init} is analogous. - -The next three functions return a prefix of the list, or a suffix, or -both. -\begin{lstlisting} -def take(n: int): List[a] = - if (n == 0 || isEmpty) Nil else head :: tail.take(n-1); - -def drop(n: int): List[a] = - if (n == 0 || isEmpty) this else tail.drop(n-1); - -def split(n: int): Pair[List[a], List[a]] = Pair(take(n), drop(n)); -\end{lstlisting} -\code{(xs take n)} returns the first \code{n} elements of list -\code{xs}, or the whole list, if its length is smaller than \code{n}. -\code{(xs drop n)} returns all elements of \code{xs} except the -\code{n} first ones. Finally, \code{(xs split n)} returns a pair -consisting of the lists resulting from \code{xs take n} and -\code{xs drop n}. - -The next function returns an element at a given index in a list. -It is thus analogous to array subscripting. Indices start at 0. -\begin{lstlisting} -def apply(n: int): a = drop(n).head; -\end{lstlisting} -The \code{apply} method has a special meaning in Scala. An object with -an \code{apply} method can be applied to arguments as if it was a -function. For instance, to pick the 3'rd element of a list \code{xs}, -one can write either \code{xs.apply(3)} or \code{xs(3)} -- the latter -expression expands into the first. - -With \code{take} and \code{drop}, we can extract sublists consisting -of consecutive elements of the original list. To extract the sublist -$xs_m \commadots xs_{n-1}$ of a list \code{xs}, use: - -\begin{lstlisting} -xs.drop(m).take(n - m) -\end{lstlisting} - -\paragraph{Zipping lists} The next function combines two lists into a list of pairs. -Given two lists -\begin{lstlisting} -xs = List(x$_1$, ..., x$_n$) $\mbox{\rm, and}$ -ys = List(y$_1$, ..., y$_n$) , -\end{lstlisting} -\code{xs zip ys} constructs the list -\code{List(Pair(x}$_1$\code{, y}$_1$\code{), ..., Pair(x}$_n$\code{, y}$_n$\code{))}. -If the two lists have different lengths, the longer one of the two is -truncated. Here is the definition of \code{zip} -- note that it is a -polymorphic method. -\begin{lstlisting} -def zip[b](that: List[b]): List[Pair[a,b]] = - if (this.isEmpty || that.isEmpty) Nil - else Pair(this.head, that.head) :: (this.tail zip that.tail); -\end{lstlisting} - -\paragraph{Consing lists.} -Like any infix operator, \code{::} -is also implemented as a method of an object. In this case, the object -is the list that is extended. This is possible, because operators -ending with a `\code{:}' character are treated specially in Scala. -All such operators are treated as methods of their right operand. E.g., -\begin{lstlisting} - x :: y = y.::(x) $\mbox{\rm whereas}$ x + y = x.+(y) -\end{lstlisting} -Note, however, that operands of a binary operation are in each case -evaluated from left to right. So, if \code{D} and \code{E} are -expressions with possible side-effects, \code{D :: E} is translated to -\lstinline@{val x = D; E.::(x)}@ in order to maintain the left-to-right -order of operand evaluation. - -Another difference between operators ending in a `\code{:}' and other -operators concerns their associativity. Operators ending in -`\code{:}' are right-associative, whereas other operators are -left-associative. E.g., -\begin{lstlisting} - x :: y :: z = x :: (y :: z) $\mbox{\rm whereas}$ x + y + z = (x + y) + z -\end{lstlisting} -The definition of \code{::} as a method in -class \code{List} is as follows: -\begin{lstlisting} -def ::[b >: a](x: b): List[b] = new scala.::(x, this); -\end{lstlisting} -Note that \code{::} is defined for all elements \code{x} of type -\code{B} and lists of type \code{List[A]} such that the type \code{B} -of \code{x} is a supertype of the list's element type \code{A}. The result -is in this case a list of \code{B}'s. This -is expressed by the type parameter \code{b} with lower bound \code{a} -in the signature of \code{::}. - -\paragraph{Concatenating lists} -An operation similar to \code{::} is list concatenation, written -`\code{:::}'. The result of \code{(xs ::: ys)} is a list consisting of -all elements of \code{xs}, followed by all elements of \code{ys}. -Because it ends in a colon, \code{:::} is right-associative and is -considered as a method of its right-hand operand. Therefore, -\begin{lstlisting} -xs ::: ys ::: zs = xs ::: (ys ::: zs) - = zs.:::(ys).:::(xs) -\end{lstlisting} -Here is the implementation of the \code{:::} method: -\begin{lstlisting} - def :::[b >: a](prefix: List[b]): List[b] = prefix match { - case Nil => this - case p :: ps => this.:::(ps).::(p) - } -\end{lstlisting} - -\paragraph{Reversing lists} Another useful operation -is list reversal. There is a method \code{reverse} in \code{List} to -that effect. Let's try to give its implementation: -\begin{lstlisting} -def reverse[a](xs: List[a]): List[a] = xs match { - case Nil => Nil - case x :: xs => reverse(xs) ::: List(x) -} -\end{lstlisting} -This implementation has the advantage of being simple, but it is not -very efficient. Indeed, one concatenation is executed for every -element in the list. List concatenation takes time proportional to the -length of its first operand. Therefore, the complexity of -\code{reverse(xs)} is -\[ -n + (n - 1) + ... + 1 = n(n+1)/2 -\] -where $n$ is the length of \code{xs}. Can \code{reverse} be -implemented more efficiently? We will see later that there exists -another implementation which has only linear complexity. - -\section{Example: Merge sort} - -The insertion sort presented earlier in this chapter is simple to -formulate, but also not very efficient. It's average complexity is -proportional to the square of the length of the input list. We now -design a program to sort the elements of a list which is more -efficient than insertion sort. A good algorithm for this is {\em merge -sort}, which works as follows. - -First, if the list has zero or one elements, it is already sorted, so -one returns the list unchanged. Longer lists are split into two -sub-lists, each containing about half the elements of the original -list. Each sub-list is sorted by a recursive call to the sort -function, and the resulting two sorted lists are then combined in a -merge operation. - -For a general implementation of merge sort, we still have to specify -the type of list elements to be sorted, as well as the function to be -used for the comparison of elements. We obtain a function of maximal -generality by passing these two items as parameters. This leads to the -following implementation. -\begin{lstlisting} -def msort[a](less: (a, a) => boolean)(xs: List[a]): List[a] = { - 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); - val n = xs.length/2; - if (n == 0) xs - else merge(msort(less)(xs take n), msort(less)(xs drop n)) -} -\end{lstlisting} -The complexity of \code{msort} is $O(N;log(N))$, where $N$ is the -length of the input list. To see why, note that splitting a list in -two and merging two sorted lists each take time proportional to the -length of the argument list(s). Each recursive call of \code{msort} -halves the number of elements in its input, so there are $O(log(N))$ -consecutive recursive calls until the base case of lists of length 1 -is reached. However, for longer lists each call spawns off two -further calls. Adding everything up we obtain that at each of the -$O(log(N))$ call levels, every element of the original lists takes -part in one split operation and in one merge operation. Hence, every -call level has a total cost proportional to $O(N)$. Since there are -$O(log(N))$ call levels, we obtain an overall cost of -$O(N;log(N))$. That cost does not depend on the initial distribution -of elements in the list, so the worst case cost is the same as the -average case cost. This makes merge sort an attractive algorithm for -sorting lists. - -Here is an example how \code{msort} is used. -\begin{lstlisting} -msort(x: int, y: int => x < y)(List(5, 7, 1, 3)) -\end{lstlisting} -The definition of \code{msort} is curried, to make it easy to specialize it with particular -comparison functions. For instance, -\begin{lstlisting} - -val intSort = msort(x: int, y: int => x < y) -val reverseSort = msort(x: int, y: int => x > y) -\end{lstlisting} - -\section{Definition of class List II: Higher-Order Methods} - -The examples encountered so far show that functions over lists often -have similar structures. We can identify several patterns of -computation over lists, like: -\begin{itemize} - \item transforming every element of a list in some way. - \item extracting from a list all elements satisfying a criterion. - \item combine the elements of a list using some operator. -\end{itemize} -Functional programming languages enable programmers to write general -functions which implement patterns like this by means of higher order -functions. We now discuss a set of commonly used higher-order -functions, which are implemented as methods in class \code{List}. - -\paragraph{Mapping over lists} -A common operation is to transform each element of a list and then -return the lists of results. For instance, to scale each element of a -list by a given factor. -\begin{lstlisting} -def scaleList(xs: List[double], factor: double): List[double] = xs match { - case Nil => xs - case x :: xs1 => x * factor :: scaleList(xs1, factor) -} -\end{lstlisting} -This pattern can be generalized to the \code{map} method of class \code{List}: -\begin{lstlisting} -abstract class List[a] { ... - def map[b](f: a => b): List[b] = this match { - case Nil => this - case x :: xs => f(x) :: xs.map(f) - } -\end{lstlisting} -Using \code{map}, \code{scaleList} can be more concisely written as follows. -\begin{lstlisting} -def scaleList(xs: List[double], factor: double) = - xs map (x => x * factor); -\end{lstlisting} - -As another example, consider the problem of returning a given column -of a matrix which is represented as a list of rows, where each row is -again a list. This is done by the following function \code{column}. - -\begin{lstlisting} -def column[a](xs: List[List[a[]], index: int): List[a] = - xs map (row => row at index); -\end{lstlisting} - -Closely related to \code{map} is the \code{foreach} method, which -applies a given function to all elements of a list, but does not -construct a list of results. The function is thus applied only for its -side effect. \code{foreach} is defined as follows. -\begin{lstlisting} - def foreach(f: a => unit): unit = this match { - case Nil => () - case x :: xs => f(x) ; xs.foreach(f) - } -\end{lstlisting} -This function can be used for printing all elements of a list, for instance: -\begin{lstlisting} - xs foreach (x => System.out.println(x)) -\end{lstlisting} - -\begin{exercise} Consider a function which squares all elements of a list and -returns a list with the results. Complete the following two equivalent -definitions of \code{squareList}. - -\begin{lstlisting} -def squareList(xs: List[int]): List[int] = xs match { - case List() => ?? - case y :: ys => ?? -} -def squareList(xs: List[int]): List[int] = - xs map ?? -\end{lstlisting} -\end{exercise} - -\paragraph{Filtering Lists} -Another common operation selects from a list all elements fulfilling a -given criterion. For instance, to return a list of all positive -elements in some given lists of integers: -\begin{lstlisting} -def posElems(xs: List[int]): List[int] = xs match { - case Nil => xs - case x :: xs1 => if (x > 0) x :: posElems(xs1) else posElems(xs1) -} -\end{lstlisting} -This pattern is generalized to the \code{filter} method of class \code{List}: -\begin{lstlisting} - def filter(p: a => boolean): List[a] = this match { - case Nil => this - case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p) - } -\end{lstlisting} -Using \code{filter}, \code{posElems} can be more concisely written as -follows. -\begin{lstlisting} -def posElems(xs: List[int]): List[int] = - xs filter (x => x > 0); -\end{lstlisting} - -An operation related to filtering is testing whether all elements of a -list satisfy a certain condition. Dually, one might also be interested -in the question whether there exists an element in a list that -satisfies a certain condition. These operations are embodied in the -higher-order functions \code{forall} and \code{exists} of class -\code{List}. -\begin{lstlisting} -def forall(p: a => Boolean): Boolean = - isEmpty || (p(head) && (tail forall p)); -def exists(p: a => Boolean): Boolean = - !isEmpty && (p(head) || (tail exists p)); -\end{lstlisting} -To illustrate the use of \code{forall}, consider the question whether -a number if prime. Remember that a number $n$ is prime of it can be -divided without remainder only by one and itself. The most direct -translation of this definition would test that $n$ divided by all -numbers from 2 up to and excluding itself gives a non-zero -remainder. This list of numbers can be generated using a function -\code{List.range} which is defined in object \code{List} as follows. -\begin{lstlisting} -package scala; -object List { ... - def range(from: int, end: int): List[int] = - if (from >= end) Nil else from :: range(from + 1, end); -\end{lstlisting} -For example, \code{List.range(2, n)} -generates the list of all integers from 2 up to and excluding $n$. -The function \code{isPrime} can now simply be defined as follows. -\begin{lstlisting} -def isPrime(n: int) = - List.range(2, n) forall (x => n % x != 0); -\end{lstlisting} -We see that the mathematical definition of prime-ness has been -translated directly into Scala code. - -Exercise: Define \code{forall} and \code{exists} in terms of \code{filter}. - - -\paragraph{Folding and Reducing Lists} -Another common operation is to combine the elements of a list with -some operator. For instance: -\begin{lstlisting} -sum(List(x$_1$, ..., x$_n$)) = 0 + x$_1$ + ... + x$_n$ -product(List(x$_1$, ..., x$_n$)) = 1 * x$_1$ * ... * x$_n$ -\end{lstlisting} -Of course, we can implement both functions with a -recursive scheme: -\begin{lstlisting} -def sum(xs: List[int]): int = xs match { - case Nil => 0 - case y :: ys => y + sum(ys) -} -def product(xs: List[int]): int = xs match { - case Nil => 1 - case y :: ys => y * product(ys) -} -\end{lstlisting} -But we can also use the generalization of this program scheme embodied -in the \code{reduceLeft} method of class \code{List}. This method -inserts a given binary operator between adjacent elements of a given list. -E.g.\ -\begin{lstlisting} -List(x$_1$, ..., x$_n$).reduceLeft(op) = (...(x$_1$ op x$_2$) op ... ) op x$_n$ -\end{lstlisting} -Using \code{reduceLeft}, we can make the common pattern -in \code{sum} and \code{product} apparent: -\begin{lstlisting} -def sum(xs: List[int]) = (0 :: xs) reduceLeft {(x, y) => x + y}; -def product(xs: List[int]) = (1 :: xs) reduceLeft {(x, y) => x * y}; -\end{lstlisting} -Here is the implementation of \code{reduceLeft}. -\begin{lstlisting} - def reduceLeft(op: (a, a) => a): a = this match { - case Nil => throw new Error("Nil.reduceLeft") - case x :: xs => (xs foldLeft x)(op) - } - def foldLeft[b](z: b)(op: (b, a) => b): b = this match { - case Nil => z - case x :: xs => (xs foldLeft op(z, x))(op) - } -} -\end{lstlisting} -We see that the \code{reduceLeft} method is defined in terms of -another generally useful method, \code{foldLeft}. The latter takes as -additional parameter an {\em accumulator} \code{z}, which is returned -when \code{foldLeft} is applied on an empty list. That is, -\begin{lstlisting} -(List(x$_1$, ..., x$_n$) foldLeft z)(op) = (...(z op x$_1$) op ... ) op x$_n$ -\end{lstlisting} -The \code{sum} and \code{product} methods can be defined alternatively -using \code{foldLeft}: -\begin{lstlisting} -def sum(xs: List[int]) = (xs foldLeft 0) {(x, y) => x + y}; -def product(xs: List[int]) = (xs foldLeft 1) {(x, y) => x * y}; -\end{lstlisting} - -\paragraph{FoldRight and ReduceRight} -Applications of \code{foldLeft} and \code{reduceLeft} expand to -left-leaning trees. \todo{insert pictures}. They have duals -\code{foldRight} and \code{reduceRight}, which produce right-leaning -trees. -\begin{lstlisting} -List(x$_1$, ..., x$_n$).reduceRight(op) = x$_1$ op ( ... (x$_{n-1}$ op x$_n$)...) -(List(x$_1$, ..., x$_n$) foldRight acc)(op) = x$_1$ op ( ... (x$_n$ op acc)...) -\end{lstlisting} -These are defined as follows. -\begin{lstlisting} - def reduceRight(op: (a, a) => a): a = match - case Nil => throw new Error("Nil.reduceRight") - case x :: Nil => x - case x :: xs => op(x, xs.reduceRight(op)) - } - def foldRight[b](z: b)(op: (a, b) => b): b = match { - case Nil => z - case x :: xs => op(x, (xs foldRight z)(op)) - } -\end{lstlisting} - -Class \code{List} defines also two symbolic abbreviations for -\code{foldLeft} and \code{foldRight}: -\begin{lstlisting} - def /:[b](z: b)(f: (b, a) => b): b = foldLeft(z)(f); - def :\[b](z: b)(f: (a, b) => b): b = foldRight(z)(f); -\end{lstlisting} -The method names picture the left/right leaning trees of the fold -operations by forward or backward slashes. The \code{:} points in each -case to the list argument whereas the end of the slash points to the -accumulator (or: zero) argument \code{z}. -That is, -\begin{lstlisting} -(z /: List(x$_1$, ..., x$_n$))(op) = (...(z op x$_1$) op ... ) op x$_n$ -(List(x$_1$, ..., x$_n$) :\ z)(op) = x$_1$ op ( ... (x$_n$ op acc)...) -\end{lstlisting} -For associative and commutative operators, \code{/:} and -\code{:\\} are equivalent (even though there may be a difference -in efficiency). -%But sometimes, only one of the two operators is -%appropriate or has the right type: - -\begin{exercise} Consider the problem of writing a function \code{flatten}, -which takes a list of element lists as arguments. The result of -\code{flatten} should be the concatenation of all element lists into a -single list. Here is the an implementation of this method in terms of -\code{:\\}. -\begin{lstlisting} -def flatten[a](xs: List[List[a]]): List[a] = - (xs :\ (Nil: List[a])) {(x, xs) => x ::: xs}; -\end{lstlisting} -Consider replacing the first part of the body of \lstinline@flatten@ -by \lstinline@(Nil /: xs)@. What would be the difference in asymptotoc -complexity between the two versions of \lstinline@flatten@? - -In fact \code{flatten} is predefined together with a set of other -userful function in an object called \code{List} in the standatd Scala -library. It can be accessed from user program by calling -\code{List.flatten}. Note that \code{flatten} is not a method of class -\code{List} -- it would not make sense there, since it applies only -to lists of lists, not to all lists in general. -\end{exercise} - -\paragraph{List Reversal Again} We have seen in -Section~\ref{sec:list-first-order} an implementation of method -\code{reverse} whose run-time was quadratic in the length of the list -to be reversed. We now develop a new implementation of \code{reverse}, -which has linear cost. The idea is to use a \code{foldLeft} -operation based on the following program scheme. -\begin{lstlisting} -class List[+a] { ... - def reverse: List[a] = (z? /: this)(op?); -\end{lstlisting} -It only remains to fill in the \code{z?} and \code{op?} parts. Let's -try to deduce them from examples. -\begin{lstlisting} - Nil -= Nil.reverse // by specification -= (z /: Nil)(op) // by the template for reverse -= (Nil foldLeft z)(op) // by the definition of /: -= z // by definition of foldLeft -\end{lstlisting} -Hence, \code{z?} must be \code{Nil}. To deduce the second operand, -let's study reversal of a list of length one. -\begin{lstlisting} - List(x) -= List(x).reverse // by specification -= (Nil /: List(x))(op) // by the template for reverse, with z = Nil -= (List(x) foldLeft Nil)(op) // by the definition of /: -= op(Nil, x) // by definition of foldLeft -\end{lstlisting} -Hence, \code{op(Nil, x)} equals \code{List(x)}, which is the same -as \code{x :: Nil}. This suggests to take as \code{op} the -\code{::} operator with its operands exchanged. Hence, we arrive at -the following implementation for \code{reverse}, which has linear complexity. -\begin{lstlisting} -def reverse: List[a] = - ((Nil: List[a]) /: this) {(xs, x) => x :: xs}; -\end{lstlisting} -(Remark: The type annotation of \code{Nil} is necessary -to make the type inferencer work.) - -\begin{exercise} Fill in the missing expressions to complete the following -definitions of some basic list-manipulation operations as fold -operations. -\begin{lstlisting} -def mapFun[a, b](xs: List[a], f: a => b): List[b] = - (xs :\ List[b]()){ ?? }; - -def lengthFun[a](xs: List[a]): int = - (0 /: xs){ ?? }; -\end{lstlisting} -\end{exercise} - -\paragraph{Nested Mappings} - -We can employ higher-order list processing functions to express many -computations that are normally expressed as nested loops in imperative -languages. - -As an example, consider the following problem: Given a positive -integer $n$, find all pairs of positive integers $i$ and $j$, where -$1 \leq j < i < n$ such that $i + j$ is prime. For instance, if $n = 7$, -the pairs are -\bda{c|lllllll} -i & 2 & 3 & 4 & 4 & 5 & 6 & 6\\ -j & 1 & 2 & 1 & 3 & 2 & 1 & 5\\ \hline -i + j & 3 & 5 & 5 & 7 & 7 & 7 & 11 -\eda - -A natural way to solve this problem consists of two steps. In a first step, -one generates the sequence of all pairs $(i, j)$ of integers such that -$1 \leq j < i < n$. In a second step one then filters from this sequence -all pairs $(i, j)$ such that $i + j$ is prime. - -Looking at the first step in more detail, a natural way to generate -the sequence of pairs consists of three sub-steps. First, generate -all integers between $1$ and $n$ for $i$. -\item -Second, for each integer $i$ between $1$ and $n$, generate the list of -pairs $(i, 1)$ up to $(i, i-1)$. This can be achieved by a -combination of \code{range} and \code{map}: -\begin{lstlisting} - List.range(1, i) map (x => Pair(i, x)) -\end{lstlisting} -Finally, combine all sublists using \code{foldRight} with \code{:::}. -Putting everything together gives the following expression: -\begin{lstlisting} -List.range(1, n) - .map(i => List.range(1, i).map(x => Pair(i, x))) - .foldRight(List[Pair[int, int]]()) {(xs, ys) => xs ::: ys} - .filter(pair => isPrime(pair._1 + pair._2)) -\end{lstlisting} - -\paragraph{Flattening Maps} -The combination of mapping and then concatenating sublists -resulting from the map -is so common that we there is a special method -for it in class \code{List}: -\begin{lstlisting} -abstract class List[+a] { ... - def flatMap[b](f: a => List[b]): List[b] = match { - case Nil => Nil - case x :: xs => f(x) ::: (xs flatMap f) - } -} -\end{lstlisting} -With \code{flatMap}, the pairs-whose-sum-is-prime expression -could have been written more concisely as follows. -\begin{lstlisting} -List.range(1, n) - .flatMap(i => List.range(1, i).map(x => Pair(i, x))) - .filter(pair => isPrime(pair._1 + pair._2)) -\end{lstlisting} - - - -\section{Summary} - -This chapter has ingtroduced lists as a fundamental data structure in -programming. Since lists are immutable, they are a common data type in -functional programming languages. They play there a role comparable to -arrays in imperative languages. However, the access patterns between -arrays and lists are quite different. Where array accessing is always -done by indexing, this is much less common for lists. We have seen -that \code{scala.List} defines a method called \code{apply} for indexing; -however this operation is much more costly than in the case of arrays -(linear as opposed to constant time). Instead of indexing, lists are -usually traversed recursively, where recursion steps are usually based -on a pattern match over the traversed list. There is also a rich set of -higher-order combinators which allow one to instantiate a set of -predefined patterns of computations over lists. - -\comment{ -\bsh{Reasoning About Lists} - -Recall the concatenation operation for lists: - -\begin{lstlisting} -class List[+a] { - ... - def ::: (that: List[a]): List[a] = - if (isEmpty) that - else head :: (tail ::: that) -} -\end{lstlisting} - -We would like to verify that concatenation is associative, with the -empty list \code{List()} as left and right identity: -\bda{lcl} - (xs ::: ys) ::: zs &=& xs ::: (ys ::: zs) \\ - xs ::: List() &=& xs \gap =\ List() ::: xs -\eda -\emph{Q}: How can we prove statements like the one above? - -\emph{A}: By \emph{structural induction} over lists. -\es -\bsh{Reminder: Natural Induction} - -Recall the proof principle of \emph{natural induction}: - -To show a property \mathtext{P(n)} for all numbers \mathtext{n \geq b}: -\be -\item Show that \mathtext{P(b)} holds (\emph{base case}). -\item For arbitrary \mathtext{n \geq b} show: -\begin{quote} - if \mathtext{P(n)} holds, then \mathtext{P(n+1)} holds as well -\end{quote} -(\emph{induction step}). -\ee -%\es\bs -\emph{Example}: Given -\begin{lstlisting} -def factorial(n: int): int = - if (n == 0) 1 - else n * factorial(n-1) -\end{lstlisting} -show that, for all \code{n >= 4}, -\begin{lstlisting} - factorial(n) >= 2$^n$ -\end{lstlisting} -\es\bs -\Case{\code{4}} -is established by simple calculation of \code{factorial(4) = 24} and \code{2$^4$ = 16}. - -\Case{\code{n+1}} -We have for \code{n >= 4}: -\begin{lstlisting} - \= factorial(n + 1) - = \> $\expl{by the second clause of factorial(*)}$ - \> (n + 1) * factorial(n) - >= \> $\expl{by calculation}$ - \> 2 * factorial(n) - >= \> $\expl{by the induction hypothesis}$ - \> 2 * 2$^n$. -\end{lstlisting} -Note that in our proof we can freely apply reduction steps such as in (*) -anywhere in a term. - - -This works because purely functional programs do not have side -effects; so a term is equivalent to the term it reduces to. - -The principle is called {\em\emph{referential transparency}}. -\es -\bsh{Structural Induction} - -The principle of structural induction is analogous to natural induction: - -In the case of lists, it is as follows: - -To prove a property \mathtext{P(xs)} for all lists \mathtext{xs}, -\be -\item Show that \code{P(List())} holds (\emph{base case}). -\item For arbitrary lists \mathtext{xs} and elements \mathtext{x} - show: -\begin{quote} - if \mathtext{P(xs)} holds, then \mathtext{P(x :: xs)} holds as well -\end{quote} -(\emph{induction step}). -\ee - -\es -\bsh{Example} - -We show \code{(xs ::: ys) ::: zs = xs ::: (ys ::: zs)} by structural induction -on \code{xs}. - -\Case{\code{List()}} -For the left-hand side, we have: -\begin{lstlisting} - \= (List() ::: ys) ::: zs - = \> $\expl{by first clause of \prog{:::}}$ - \> ys ::: zs -\end{lstlisting} -For the right-hand side, we have: -\begin{lstlisting} - \= List() ::: (ys ::: zs) - = \> $\expl{by first clause of \prog{:::}}$ - \> ys ::: zs -\end{lstlisting} -So the case is established. - -\es -\bs -\Case{\code{x :: xs}} - -For the left-hand side, we have: -\begin{lstlisting} - \= ((x :: xs) ::: ys) ::: zs - = \> $\expl{by second clause of \prog{:::}}$ - \> (x :: (xs ::: ys)) ::: zs - = \> $\expl{by second clause of \prog{:::}}$ - \> x :: ((xs ::: ys) ::: zs) - = \> $\expl{by the induction hypothesis}$ - \> x :: (xs ::: (ys ::: zs)) -\end{lstlisting} - -For the right-hand side, we have: -\begin{lstlisting} - \= (x :: xs) ::: (ys ::: zs) - = \> $\expl{by second clause of \prog{:::}}$ - \> x :: (xs ::: (ys ::: zs)) -\end{lstlisting} -So the case (and with it the property) is established. - -\begin{exercise} -Show by induction on \code{xs} that \code{xs ::: List() = xs}. -\es -\bsh{Example (2)} -\end{exercise} - -As a more difficult example, consider function -\begin{lstlisting} -abstract class List[a] { ... - def reverse: List[a] = match { - case List() => List() - case x :: xs => xs.reverse ::: List(x) - } -} -\end{lstlisting} -We would like to prove the proposition that -\begin{lstlisting} - xs.reverse.reverse = xs . -\end{lstlisting} -We proceed by induction over \code{xs}. The base case is easy to establish: -\begin{lstlisting} - \= List().reverse.reverse - = \> $\expl{by first clause of \prog{reverse}}$ - \> List().reverse - = \> $\expl{by first clause of \prog{reverse}}$ - \> List() -\end{lstlisting} -\es\bs -For the induction step, we try: -\begin{lstlisting} - \= (x :: xs).reverse.reverse - = \> $\expl{by second clause of \prog{reverse}}$ - \> (xs.reverse ::: List(x)).reverse -\end{lstlisting} -There's nothing more we can do to this expression, so we turn to the right side: -\begin{lstlisting} - \= x :: xs - = \> $\expl{by induction hypothesis}$ - \> x :: xs.reverse.reverse -\end{lstlisting} -The two sides have simplified to different expressions. - -So we still have to show that -\begin{lstlisting} - (xs.reverse ::: List(x)).reverse = x :: xs.reverse.reverse -\end{lstlisting} -Trying to prove this directly by induction does not work. - -Instead we have to {\em generalize} the equation to: -\begin{lstlisting} - (ys ::: List(x)).reverse = x :: ys.reverse -\end{lstlisting} -\es\bs -This equation can be proved by a second induction argument over \code{ys}. -(See blackboard). - -\begin{exercise} -Is it the case that \code{(xs drop m) at n = xs at (m + n)} for all -natural numbers \code{m}, \code{n} and all lists \code{xs}? -\end{exercise} - -\es -\bsh{Structural Induction on Trees} - -Structural induction is not restricted to lists; it works for arbitrary -trees. - -The general induction principle is as follows. - -To show that property \code{P(t)} holds for all trees of a certain type, -\begin{itemize} -\item Show \code{P(l)} for all leaf trees \code{$l$}. -\item For every interior node \code{t} with subtrees \code{s$_1$, ..., s$_n$}, - show that \code{P(s$_1$) $\wedge$ ... $\wedge$ P(s$_n$) => P(t)}. -\end{itemize} - -\example Recall our definition of \code{IntSet} with -operations \code{contains} and \code{incl}: - -\begin{lstlisting} -abstract class IntSet { - abstract def incl(x: int): IntSet - abstract def contains(x: int): boolean -} -\end{lstlisting} -\es\bs -\begin{lstlisting} -case class Empty extends IntSet { - def contains(x: int): boolean = false - def incl(x: int): IntSet = NonEmpty(x, Empty, Empty) -} -case class NonEmpty(elem: int, left: Set, right: Set) 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) NonEmpty(elem, left incl x, right) - else if (x > elem) NonEmpty(elem, left, right incl x) - else this -} -\end{lstlisting} -(With \code{case} added, so that we can use factory methods instead of \code{new}). - -What does it mean to prove the correctness of this implementation? -\es -\bsh{Laws of IntSet} - -One way to state and prove the correctness of an implementation is -to prove laws that hold for it. - -In the case of \code{IntSet}, three such laws would be: - -For all sets \code{s}, elements \code{x}, \code{y}: - -\begin{lstlisting} -Empty contains x \= = false -(s incl x) contains x \> = true -(s incl x) contains y \> = s contains y if x $\neq$ y -\end{lstlisting} - -(In fact, one can show that these laws characterize the desired data -type completely). - -How can we establish that these laws hold? - -\emph{Proposition 1}: \code{Empty contains x = false}. - -\emph{Proof}: By the definition of \code{contains} in \code{Empty}. -\es\bs -\emph{Proposition 2}: \code{(xs incl x) contains x = true} - -\emph{Proof:} - -\Case{\code{Empty}} -\begin{lstlisting} - \= (Empty incl x) contains x - = \> $\expl{by definition of \prog{incl} in \prog{Empty}}$ - \> NonEmpty(x, Empty, Empty) contains x - = \> $\expl{by definition of \prog{contains} in \prog{NonEmpty}}$ - \> true -\end{lstlisting} - -\Case{\code{NonEmpty(x, l, r)}} -\begin{lstlisting} - \= (NonEmpty(x, l, r) incl x) contains x - = \> $\expl{by definition of \prog{incl} in \prog{NonEmpty}}$ - \> NonEmpty(x, l, r) contains x - = \> $\expl{by definition of \prog{contains} in \prog{Empty}}$ - \> true -\end{lstlisting} -\es\bs -\Case{\code{NonEmpty(y, l, r)} where \code{y < x}} -\begin{lstlisting} - \= (NonEmpty(y, l, r) incl x) contains x - = \> $\expl{by definition of \prog{incl} in \prog{NonEmpty}}$ - \> NonEmpty(y, l, r incl x) contains x - = \> $\expl{by definition of \prog{contains} in \prog{NonEmpty}}$ - \> (r incl x) contains x - = \> $\expl{by the induction hypothesis}$ - \> true -\end{lstlisting} - -\Case{\code{NonEmpty(y, l, r)} where \code{y > x}} is analogous. - -\bigskip - -\emph{Proposition 3}: If \code{x $\neq$ y} then -\code{xs incl y contains x = xs contains x}. - -\emph{Proof:} See blackboard. -\es -\bsh{Exercise} - -Say we add a \code{union} function to \code{IntSet}: - -\begin{lstlisting} -class IntSet { ... - def union(other: IntSet): IntSet -} -class Expty extends IntSet { ... - def union(other: IntSet) = other -} -class NonEmpty(x: int, l: IntSet, r: IntSet) extends IntSet { ... - def union(other: IntSet): IntSet = l union r union other incl x -} -\end{lstlisting} - -The correctness of \code{union} can be subsumed with the following -law: - -\emph{Proposition 4}: -\code{(xs union ys) contains x = xs contains x || ys contains x}. -Is that true ? What hypothesis is missing ? Show a counterexample. - -Show Proposition 4 using structural induction on \code{xs}. -\es -\comment{ - -\emph{Proof:} By induction on \code{xs}. - -\Case{\code{Empty}} - -\Case{\code{NonEmpty(x, l, r)}} - -\Case{\code{NonEmpty(y, l, r)} where \code{y < x}} - -\begin{lstlisting} - \= (Empty union ys) contains x - = \> $\expl{by definition of \prog{union} in \prog{Empty}}$ - \> ys contains x - = \> $\expl{Boolean algebra}$ - \> false || ys contains x - = \> $\expl{by definition of \prog{contains} in \prog{Empty} (reverse)}$ - \> (Empty contains x) || (ys contains x) -\end{lstlisting} - -\begin{lstlisting} - \= (NonEmpty(x, l, r) union ys) contains x - = \> $\expl{by definition of \prog{union} in \prog{NonEmpty}}$ - \> (l union r union ys incl x) contains x - = \> $\expl{by Proposition 2}$ - \> true - = \> $\expl{Boolean algebra}$ - \> true || (ys contains x) - = \> $\expl{by definition of \prog{contains} in \prog{NonEmpty} (reverse)}$ - \> (NonEmpty(x, l, r) contains x) || (ys contains x) -\end{lstlisting} - -\begin{lstlisting} - \= (NonEmpty(y, l, r) union ys) contains x - = \> $\expl{by definition of \prog{union} in \prog{NonEmpty}}$ - \> (l union r union ys incl y) contains x - = \> $\expl{by Proposition 3}$ - \> (l union r union ys) contains x - = \> $\expl{by the induction hypothesis}$ - \> ((l union r) contains x) || (ys contains x) - = \> $\expl{by Proposition 3}$ - \> ((l union r incl y) contains x) || (ys contains x) -\end{lstlisting} - -\Case{\code{NonEmpty(y, l, r)} where \code{y < x}} - ... is analogous. - -\es -}} -\chapter{\label{sec:for-notation}For-Comprehensions} - -The last chapter demonstrated that higher-order functions such as -\verb@map@, \verb@flatMap@, \verb@filter@ provide powerful -constructions for dealing with lists. But sometimes the level of -abstraction required by these functions makes a program hard to -understand. - -To help understandability, Scala has a special notation which -simplifies common patterns of applications of higher-order functions. -This notation builds a bridge between set-comprehensions in -mathematics and for-loops in imperative languages such as C or -Java. It also closely resembles the query notation of relational -databases. - -As a first example, say we are given a list \code{persons} of persons -with \code{name} and \code{age} fields. To print the names of all -persons in the sequence which are aged over 20, one can write: -\begin{lstlisting} -for (val p <- persons; p.age > 20) yield p.name -\end{lstlisting} -This is equivalent to the following expression , which uses -higher-order functions \code{filter} and \code{map}: -\begin{lstlisting} -persons filter (p => p.age > 20) map (p => p.name) -\end{lstlisting} -The for-comprehension looks a bit like a for-loop in imperative languages, -except that it constructs a list of the results of all iterations. - -Generally, a for-comprehension is of the form -\begin{lstlisting} -for ( $s$ ) yield $e$ -\end{lstlisting} -Here, $s$ is a sequence of {\em generators} and {\em filters}. A {\em -generator} is of the form \code{val x <- e}, where \code{e} is a -list-valued expression. It binds \code{x} to successive values in the -list. A {\em filter} is an expression \code{f} of type -\code{boolean}. It omits from consideration all bindings for which -\code{f} is \code{false}. The sequence $s$ starts in each case 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, let's redo an example of the previous chapter: Given a positive -integer $n$, find all pairs of positive integers $i$ and $j$, where $1 -\leq j < i < n$ such that $i + j$ is prime. With a for-comprehension -this problem is solved as follows: -\begin{lstlisting} -for (val i <- List.range(1, n); - val j <- List.range(1, i); - isPrime(i+j)) yield Pair(i, j) -\end{lstlisting} -This is arguably much clearer than the solution using \code{map}, -\code{flatMap} and \code{filter} that we have developed previously. - -As a second example, consider computing the scalar product of two -vectors \code{xs} and \code{ys}. Using a for-comprehension, this can -be written as follows. -\begin{lstlisting} - sum (for(val (x, y) <- xs zip ys) yield x * y) -\end{lstlisting} - -\section{The N-Queens Problem} - -For-comprehensions are especially useful for solving combinatorial -puzzles. An example of such a puzzle is the 8-queens problem: Given a -standard chess-board, place 8 queens such that no queen is in check from any -other (a queen can check another piece if they are on the same -column, row, or diagonal). We will now develop a solution to this -problem, generalizing it to chess-boards of arbitrary size. Hence, the -problem is to place $n$ queens on a chess-board of size $n \times n$. - -To solve this problem, note that we need to place a queen in each row. -So we could place queens in successive rows, each time checking that a -newly placed queen is not in check from any other queens that have -already been placed. In the course of this search, it might arrive -that a queen to be placed in row $k$ would be in check in all fields -of that row from queens in row $1$ to $k-1$. In that case, we need to -abort that part of the search in order to continue with a different -configuration of queens in columns $1$ to $k-1$. - -This suggests a recursive algorithm. Assume that we have already -generated all solutions of placing $k-1$ queens on a board of size $n -\times n$. We can represent each such solution by a list of length -$k-1$ of column numbers (which can range from $1$ to $n$). We treat -these partial solution lists as stacks, where the column number of the -queen in row $k-1$ comes first in the list, followed by the column -number of the queen in row $k-2$, etc. The bottom of the stack is the -column number of the queen placed in the first row of the board. All -solutions together are then represented as a list of lists, with one -element for each solution. - -Now, to place the $k$'the queen, we generate all possible extensions -of each previous solution by one more queen. This yields another list -of solution lists, this time of length $k$. We continue the process -until we have reached solutions of the size of the chess-board $n$. -This algorithmic idea is embodied in function \code{placeQueens} below: -\begin{lstlisting} -def queens(n: int): List[List[int]] = { - def placeQueens(k: int): List[List[int]] = - if (k == 0) List(List()) - else for (val queens <- placeQueens(k - 1); - val column <- List.range(1, n + 1); - isSafe(column, queens, 1)) yield col :: queens; - placeQueens(n); -} -\end{lstlisting} - -\begin{exercise} Write the function -\begin{lstlisting} - def isSafe(col: int, queens: List[int], delta: int): boolean -\end{lstlisting} -which tests whether a queen in the given column \verb@col@ is safe with -respect to the \verb@queens@ already placed. Here, \verb@delta@ is the difference between the row of the queen to be -placed and the row of the first queen in the list. -\end{exercise} - -\section{Querying with For-Comprehensions} - -The for-notation is essentially equivalent to common operations of -database query languages. For instance, say we are given a -database \code{books}, represented as a list of books, where -\code{Book} is defined as follows. -\begin{lstlisting} -case class Book(title: String, authors: List[String]); -\end{lstlisting} -Here is a small example database: -\begin{lstlisting} -val books: List[Book] = List( - Book("Structure and Interpretation of Computer Programs", - List("Abelson, Harold", "Sussman, Gerald J.")), - Book("Principles of Compiler Design", - List("Aho, Alfred", "Ullman, Jeffrey")), - Book("Programming in Modula-2", - List("Wirth, Niklaus")), - Book("Introduction to Functional Programming"), - List("Bird, Richard")), - Book("The Java Language Specification", - List("Gosling, James", "Joy, Bill", "Steele, Guy", "Bracha, Gilad"))); -\end{lstlisting} -Then, to find the titles of all books whose author's last name is ``Ullman'': -\begin{lstlisting} -for (val b <- books; val a <- b.authors; a startsWith "Ullman") -yield b.title -\end{lstlisting} -(Here, \code{startsWith} is a method in \code{java.lang.String}). Or, -to find the titles of all books that have the string ``Program'' in -their title: -\begin{lstlisting} -for (val b <- books; (b.title indexOf "Program") >= 0) -yield b.title -\end{lstlisting} -Or, to find the names of all authors that have written at least two -books in the database. -\begin{lstlisting} -for (val b1 <- books; val b2 <- books; b1 != b2; - val a1 <- b1.authors; val a2 <- b2.authors; a1 == a2) -yield a1 -\end{lstlisting} -The last solution is not yet perfect, because authors will appear -several times in the list of results. We still need to remove -duplicate authors from result lists. This can be achieved with the -following function. -\begin{lstlisting} -def removeDuplicates[a](xs: List[a]): List[a] = - if (xs.isEmpty) xs - else xs.head :: removeDuplicates(xs.tail filter (x => x != xs.head)); -\end{lstlisting} -Note that the last expression in method \code{removeDuplicates} -can be equivalently expressed using a for-comprehension. -\begin{lstlisting} -xs.head :: removeDuplicates(for (val x <- xs.tail; x != xs.head) yield x) -\end{lstlisting} - -\section{Translation of For-Comprehensions} - -Every for-comprehension can be expressed in terms of the three -higher-order functions \code{map}, \code{flatMap} and \code{filter}. -Here is the translation scheme, which is also used by the Scala compiler. -\begin{itemize} -\item -A simple for-comprehension -\begin{lstlisting} -for (val x <- e) yield e' -\end{lstlisting} -is translated to -\begin{lstlisting} -e.map(x => e') -\end{lstlisting} -\item -A for-comprehension -\begin{lstlisting} -for (val x <- e; f; s) yield e' -\end{lstlisting} -where \code{f} is a filter and \code{s} is a (possibly empty) -sequence of generators or filters -is translated to -\begin{lstlisting} -for (val x <- e.filter(x => f); s) yield e' -\end{lstlisting} -and then translation continues with the latter expression. -\item -A for-comprehension -\begin{lstlisting} -for (val x <- e; y <- e'; s) yield e'' -\end{lstlisting} -where \code{s} is a (possibly empty) -sequence of generators or filters -is translated to -\begin{lstlisting} -e.flatMap(x => for (y <- e'; s) yield e'') -\end{lstlisting} -and then translation continues with the latter expression. -\end{itemize} -For instance, taking our "pairs of integers whose sum is prime" example: -\begin{lstlisting} -for ( val i <- range(1, n); - val j <- range(1, i); - isPrime(i+j) -) yield (i, j) -\end{lstlisting} -Here is what we get when we translate this expression: -\begin{lstlisting} -range(1, n) - .flatMap(i => - range(1, i) - .filter(j => isPrime(i+j)) - .map(j => (i, j))) -\end{lstlisting} - -Conversely, it would also be possible to express functions \code{map}, -\code{flatMap}{ and \code{filter} using for-comprehensions. Here are the -three functions again, this time implemented using for-comprehensions. -\begin{lstlisting} -object Demo { - def map[a, b](xs: List[a], f: a => b): List[b] = - for (val x <- xs) yield f(x); - - def flatMap[a, b](xs: List[a], f: a => List[b]): List[b] = - for (val x <- xs; val y <- f(x)) yield y; - - def filter[a](xs: List[a], p: a => boolean): List[a] = - for (val x <- xs; p(x)) yield x; -} -\end{lstlisting} -Not surprisingly, the translation of the for-comprehension in the body of -\code{Demo.map} will produce a call to \code{map} in class \code{List}. -Similarly, \code{Demo.flatMap} and \code{Demo.filter} translate to -\code{flatMap} and \code{filter} in class \code{List}. - -\begin{exercise} -Define the following function in terms of \code{for}. -\begin{lstlisting} -def flatten(xss: List[List[a]]): List[a] = - (xss :\ List()) ((xs, ys) => xs ::: ys) -\end{lstlisting} -\end{exercise} - -\begin{exercise} -Translate -\begin{lstlisting} -for ( val b <- books; val a <- b.authors; a startsWith "Bird" ) yield b.title -for ( val b <- books; (b.title indexOf "Program") >= 0 ) yield b.title -\end{lstlisting} -to higher-order functions. -\end{exercise} - -\section{For-Loops}\label{sec:for-loops} - -For-comprehensions resemble for-loops in imperative languages, except -that they produce a list of results. Sometimes, a list of results is -not needed but we would still like the flexibility of generators and -filters in iterations over lists. This is made possible by a variant -of the for-comprehension syntax, which expresses for-loops: -\begin{lstlisting} -for ( $s$ ) $e$ -\end{lstlisting} -This construct is the same as the standard for-comprehension syntax -except that the keyword \code{yield} is missing. The for-loop is -executed by executing the expression $e$ for each element generated -from the sequence of generators and filters $s$. - -As an example, the following expression prints out all elements of a -matrix represented as a list of lists: - \begin{lstlisting} -for (xs <- xss) { - for (x <- xs) System.out.print(x + "\t") - System.out.println() -} -\end{lstlisting} -The translation of for-loops to higher-order methods of class -\code{List} is similar to the translation of for-comprehensions, but -is simpler. Where for-comprehensions translate to \code{map} and -\code{flatMap}, for-loops translate in each case to \code{foreach}. - -\section{Generalizing For} - -We have seen that the translation of for-comprehensions only relies on -the presence of methods \code{map}, \code{flatMap}, and -\code{filter}. Therefore it is possible to apply the same notation to -generators that produce objects other than lists; these objects only -have to support the three key functions \code{map}, \code{flatMap}, -and \code{filter}. - -The standard Scala library has several other abstractions that support -these three methods and with them support for-comprehensions. We will -encounter some of them in the following chapters. As a programmer you -can also use this principle to enable for-comprehensions for types you -define -- these types just need to support methods \code{map}, -\code{flatMap}, and \code{filter}. - -There are many examples where this is useful: Examples are database -interfaces, XML trees, or 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. - -One caveat: It is not assured automatically that the result -translating a for-comprehension is well-typed. To ensure this, the -types of \code{map}, \code{flatMap} and \code{filter} have to be -essentially similar to the types of these methods in class \code{List}. - -To make this precise, assume you have a parameterized class - \code{C[a]} for which you want to enable for-comprehensions. Then - \code{C} should define \code{map}, \code{flatMap} and \code{filter} - with the following types: -\begin{lstlisting} -def map[b](f: a => b): C[b] -def flatMap[b](f: a => C[b]): C[b] -def filter(p: a => boolean): C[a] -\end{lstlisting} -It would be attractive to enforce these types statically in the Scala -compiler, for instance by requiring that any type supporting -for-comprehensions implements a standard trait with these methods -\footnote{In the programming language Haskell, which has similar -constructs, this abstraction is called a ``monad with zero''}. The -problem is that such a standard trait would have to abstract over the -identity of the class \code{C}, for instance by taking \code{C} as a -type parameter. Note that this parameter would be a type constructor, -which gets applied to {\em several different} types in the signatures of -methods \code{map} and \code{flatMap}. Unfortunately, the Scala type -system is too weak to express this construct, since it can handle only -type parameters which are fully applied types. - -\chapter{Mutable State} - -Most programs we have presented so for did not have side-effects -\footnote{We ignore here the fact that some of our program printed to -standard output, which technically is a side effect.}. Therefore, the -notion of {\em time} did not matter. For a program that terminates, -any sequence of actions would have led to the same result! This is -also reflected by the substitution model of computation, where a -rewrite step can be applied anywhere in a term, and all rewritings -that terminate lead to the same solution. In fact, this {\em -confluence} property is a deep result in $\lambda$-calculus, the -theory underlying functional programming. - -In this chapter, we introduce functions with side effects and study -their behavior. We will see that as a consequence we have to -fundamentally modify up the substitution model of computation which we -employed so far. - -\section{Stateful Objects} - -We normally view the world as a set of objects, some of which have -state that {\em changes} over time. Normally, state is associated -with a set of variables that can be changed in the course of a -computation. There is also a more abstract notion of state, which -does not refer to particular constructs of a programming language: An -object {\em has state} (or: {\em is stateful}) if its behavior is -influenced by its history. - -For instance, a bank account object has state, because the question -``can I withdraw 100 CHF?'' -might have different answers during the lifetime of the account. - -In Scala, all mutable state is ultimately built from variables. A -variable definition is written like a value definition, but starts -with \verb@var@ instead of \verb@val@. For instance, the following two -definitions introduce and initialize two variables \code{x} and -\code{count}. -\begin{lstlisting} -var x: String = "abc"; -var count = 111; -\end{lstlisting} -Like a value definition, a variable definition associates a name with -a value. But in the case of a variable definition, this association -may be changed later by an assignment. Such assignments are written -as in C or Java. Examples: -\begin{lstlisting} -x = "hello"; -count = count + 1; -\end{lstlisting} -In Scala, every defined variable has to be initialized at the point of -its definition. For instance, the statement ~\code{var x: int;}~ is -{\em not} regarded as a variable definition, because the initializer -is missing\footnote{If a statement like this appears in a class, it is -instead regarded as a variable declaration, which introduces -abstract access methods for the variable, but does not associate these -methods with a piece of state.}. If one does not know, or does not -care about, the appropriate initializer, one can use a wildcard -instead. I.e. -\begin{lstlisting} -val x: T = _; -\end{lstlisting} -will initialize \code{x} to some default value (\code{null} for -reference types, \code{false} for booleans, and the appropriate -version of \code{0} for numeric value types). - -Real-world objects with state are represented in Scala by objects that -have variables as members. For instance, here is a class that -represents bank accounts. -\begin{lstlisting} -class BankAccount { - private var balance = 0; - def deposit(amount: int): unit = - if (amount > 0) balance = balance + amount; - - def withdraw(amount: int): int = - if (0 < amount && amount <= balance) { - balance = balance - amount; - balance - } else throw new Error("insufficient funds"); -} -\end{lstlisting} -The class defines a variable \code{balance} which contains the current -balance of an account. Methods \code{deposit} and \code{withdraw} -change the value of this variable through assignments. Note that -\code{balance} is \code{private} in class \code{BankAccount} -- hence -it can not be accessed directly outside the class. - -To create bank-accounts, we use the usual object creation notation: -\begin{lstlisting} -val myAccount = new BankAccount -\end{lstlisting} - -\example Here is a \code{scalaint} session that deals with bank -accounts. - -\begin{lstlisting} -> :l bankaccount.scala -loading file 'bankaccount.scala' -> val account = new BankAccount -val account : BankAccount = BankAccount$\Dollar$class@1797795 -> account deposit 50 -(): scala.Unit -> account withdraw 20 -30: scala.Int -> account withdraw 20 -10: scala.Int -> account withdraw 15 -java.lang.RuntimeException: insufficient funds - at BankAccount$\Dollar$class.withdraw(bankaccount.scala:13) - at <top-level>(console:1) -> -\end{lstlisting} -The example shows that applying the same operation (\code{withdraw -20}) twice to an account yields different results. So, clearly, -accounts are stateful objects. - -\paragraph{Sameness and Change} -Assignments pose new problems in deciding when two expressions are -``the same''. -If assignments are excluded, and one writes -\begin{lstlisting} -val x = E; val y = E; -\end{lstlisting} -where \code{E} is some arbitrary expression, -then \code{x} and \code{y} can reasonably be assumed to be the same. -I.e. one could have equivalently written -\begin{lstlisting} -val x = E; val y = x; -\end{lstlisting} -(This property is usually called {\em referential transparency}). But -once we admit assignments, the two definition sequences are different. -Consider: -\begin{lstlisting} -val x = new BankAccount; val y = new BankAccount; -\end{lstlisting} -To answer the question whether \code{x} and \code{y} are the same, we -need to be more precise what ``sameness'' means. This meaning is -captured in the notion of {\em operational equivalence}, which, -somewhat informally, is stated as follows. - -Suppose we have two definitions of \code{x} and \code{y}. -To test whether \code{x} and \code{y} define the same value, proceed -as follows. -\begin{itemize} -\item -Execute the definitions followed by an -arbitrary sequence \code{S} of operations that involve \code{x} and -\code{y}. Observe the results (if any). -\item -Then, execute the definitions with another sequence \code{S'} which -results from \code{S} by renaming all occurrences of \code{y} in -\code{S} to \code{x}. -\item -If the results of running \code{S'} are different, then surely -\code{x} and \code{y} are different. -\item -On the other hand, if all possible pairs of sequences \code{(S, S')} -yield the same results, then \code{x} and \code{y} are the same. -\end{itemize} -In other words, operational equivalence regards two definitions -\code{x} and \code{y} as defining the same value, if no possible -experiment can distinguish between \code{x} and \code{y}. An -experiment in this context are two version of an arbitrary program which use either -\code{x} or \code{y}. - -Given this definition, let's test whether -\begin{lstlisting} -val x = new BankAccount; val y = new BankAccount; -\end{lstlisting} -defines values \code{x} and \code{y} which are the same. -Here are the definitions again, followed by a test sequence: - -\begin{lstlisting} -> val x = new BankAccount -> val y = new BankAccount -> x deposit 30 -30 -> y withdraw 20 -java.lang.RuntimeException: insufficient funds -\end{lstlisting} - -Now, rename all occurrences of \code{y} in that sequence to -\code{x}. We get: -\begin{lstlisting} -> val x = new BankAccount -> val y = new BankAccount -> x deposit 30 -30 -> x withdraw 20 -10 -\end{lstlisting} -Since the final results are different, we have established that -\code{x} and \code{y} are not the same. -On the other hand, if we define -\begin{lstlisting} -val x = new BankAccount; val y = x -\end{lstlisting} -then no sequence of operations can distinguish between \code{x} and -\code{y}, so \code{x} and \code{y} are the same in this case. - -\paragraph{Assignment and the Substitution Model} -These examples show that our previous substitution model of -computation cannot be used anymore. After all, under this -model we could always replace a value name by its -defining expression. -For instance in -\begin{lstlisting} -val x = new BankAccount; val y = x -\end{lstlisting} -the \code{x} in the definition of \code{y} could -be replaced by \code{new BankAccount}. -But we have seen that this change leads to a different program. -So the substitution model must be invalid, once we add assignments. - -\section{Imperative Control Structures} - -Scala has the \code{while} and \code{do-while} loop constructs known -from the C and Java languages. There is also a single branch \code{if} -which leaves out the else-part as well as a \code{return} statement which -aborts a function prematurely. This makes it possible to program in a -conventional imperative style. For instance, the following function, -which computes the \code{n}'th power of a given parameter \code{x}, is -implemented using \code{while} and single-branch \code{if}. -\begin{lstlisting} -def power (x: double, n: int): double = { - var r = 1.0; - var i = n; - while (i > 0) { - if ((i & 1) == 1) { r = r * x } - if (i > 1) r = r * r; - i = i >> 1; - } - r -} -\end{lstlisting} -These imperative control constructs are in the language for -convenience. They could have been left out, as the same constructs can -be implemented using just functions. As an example, let's develop a -functional implementation of the while loop. \code{whileLoop} should -be a function that takes two parameters: a condition, of type -\code{boolean}, and a command, of type \code{unit}. Both condition and -command need to be passed by-name, so that they are evaluated -repeatedly for each loop iteration. This leads to the following -definition of \code{whileLoop}. -\begin{lstlisting} -def whileLoop(condition: => boolean)(command: => unit): unit = - if (condition) { - command; whileLoop(condition)(command) - } else {} -\end{lstlisting} -Note that \code{whileLoop} is tail recursive, so it operates in -constant stack space. - -\begin{exercise} Write a function \code{repeatLoop}, which should be -applied as follows: -\begin{lstlisting} -repeatLoop { command } ( condition ) -\end{lstlisting} -Is there also a way to obtain a loop syntax like the following? -\begin{lstlisting} -repeatLoop { command } until ( condition ) -\end{lstlisting} -\end{exercise} - -Some other control constructs known from C and Java are missing in -Scala: There are no \code{break} and \code{continue} jumps for loops. -There are also no for-loops in the Java sense -- these have been -replaced by the more general for-loop construct discussed in -Section~\ref{sec:for-loops}. - -\section{Extended Example: Discrete Event Simulation} - -We now discuss an example that demonstrates how assignments and -higher-order functions can be combined in interesting ways. -We will build a simulator for digital circuits. - -The example is taken from Abelson and Sussman's book -\cite{abelson-sussman:structure}. We augment their basic (Scheme-) -code by an object-oriented structure which allows code-reuse through -inheritance. The example also shows how discrete event simulation programs -in general are structured and built. - -We start with a little language to describe digital circuits. -A digital circuit is built from {\em wires} and {\em function boxes}. -Wires carry signals which are transformed by function boxes. -We will represent signals by the booleans \code{true} and -\code{false}. - -Basic function boxes (or: {\em gates}) are: -\begin{itemize} -\item An \emph{inverter}, which negates its signal -\item An \emph{and-gate}, which sets its output to the conjunction of its input. -\item An \emph{or-gate}, which sets its output to the disjunction of its -input. -\end{itemize} -Other function boxes can be built by combining basic ones. - -Gates have {\em delays}, so an output of a gate will change only some -time after its inputs change. - -\paragraph{A Language for Digital Circuits} - -We describe the elements of a digital circuit by the following set of -Scala classes and functions. - -First, there is a class \code{Wire} for wires. -We can construct wires as follows. -\begin{lstlisting} -val a = new Wire; -val b = new Wire; -val c = new Wire; -\end{lstlisting} -Second, there are functions -\begin{lstlisting} -def inverter(input: Wire, output: Wire): unit -def andGate(a1: Wire, a2: Wire, output: Wire): unit -def orGate(o1: Wire, o2: Wire, output: Wire): unit -\end{lstlisting} -which ``make'' the basic gates we need (as side-effects). -More complicated function boxes can now be built from these. -For instance, to construct a half-adder, we can define: - -\begin{lstlisting} - def halfAdder(a: Wire, b: Wire, s: Wire, c: Wire): unit = { - val d = new Wire; - val e = new Wire; - orGate(a, b, d); - andGate(a, b, c); - inverter(c, e); - andGate(d, e, s); - } -\end{lstlisting} -This abstraction can itself be used, for instance in defining a full -adder: -\begin{lstlisting} - def fullAdder(a: Wire, b: Wire, cin: Wire, sum: Wire, cout: Wire) = { - val s = new Wire; - val c1 = new Wire; - val c2 = new Wire; - halfAdder(a, cin, s, c1); - halfAdder(b, s, sum, c2); - orGate(c1, c2, cout); - } -\end{lstlisting} -Class \code{Wire} and functions \code{inverter}, \code{andGate}, and -\code{orGate} represent thus a little language in which users can -define digital circuits. We now give implementations of this class -and these functions, which allow one to simulate circuits. -These implementations are based on a simple and general API for -discrete event simulation. - -\paragraph{The Simulation API} - -Discrete event simulation performs user-defined \emph{actions} at -specified \emph{times}. -An {\em action} is represented as a function which takes no parameters and -returns a \code{unit} result: -\begin{lstlisting} -type Action = () => unit; -\end{lstlisting} -The \emph{time} is simulated; it is not the actual ``wall-clock'' time. - -A concrete simulation will be done inside an object which inherits -from the abstract \code{Simulation} class. This class has the following -signature: - -\begin{lstlisting} -abstract class Simulation { - def currentTime: int; - def afterDelay(delay: int, action: => Action): unit; - def run: unit; -} -\end{lstlisting} -Here, -\code{currentTime} returns the current simulated time as an integer -number, -\code{afterDelay} schedules an action to be performed at a specified -delay after \code{currentTime}, and -\code{run} runs the simulation until there are no further actions to be -performed. - -\paragraph{The Wire Class} -A wire needs to support three basic actions. -\begin{itemize} -\item[] -\code{getSignal: boolean}~~ returns the current signal on the wire. -\item[] -\code{setSignal(sig: boolean): unit}~~ sets the wire's signal to \code{sig}. -\item[] -\code{addAction(p: Action): unit}~~ attaches the specified procedure -\code{p} to the {\em actions} of the wire. All attached action -procedures will be executed every time the signal of a wire changes. -\end{itemize} -Here is an implementation of the \code{Wire} class: -\begin{lstlisting} -class Wire { - private var sigVal = false; - private var actions: List[Action] = List(); - def getSignal = sigVal; - def setSignal(s: boolean) = - if (s != sigVal) { - sigVal = s; - actions.foreach(action => action()); - } - def addAction(a: Action) = { - actions = a :: actions; a() - } -} -\end{lstlisting} -Two private variables make up the state of a wire. The variable -\code{sigVal} represents the current signal, and the variable -\code{actions} represents the action procedures currently attached to -the wire. - -\paragraph{The Inverter Class} -We implement an inverter by installing an action on its input wire, -namely the action which puts the negated input signal onto the output -signal. The action needs to take effect at \code{InverterDelay} -simulated time units after the input changes. This suggests the -following implementation: -\begin{lstlisting} -def inverter(input: Wire, output: Wire) = { - def invertAction() = { - val inputSig = input.getSignal; - afterDelay(InverterDelay, () => output.setSignal(!inputSig)) - } - input addAction invertAction -} -\end{lstlisting} - -\paragraph{The And-Gate Class} -And-gates are implemented analogously to inverters. The action of an -\code{andGate} is to output the conjunction of its input signals. -This should happen at \code{AndGateDelay} simulated time units after -any one of its two inputs changes. Hence, the following implementation: -\begin{lstlisting} -def andGate(a1: Wire, a2: Wire, output: Wire) = { - def andAction() = { - val a1Sig = a1.getSignal; - val a2Sig = a2.getSignal; - afterDelay(AndGateDelay, () => output.setSignal(a1Sig & a2Sig)); - } - a1 addAction andAction; - a2 addAction andAction; -} -\end{lstlisting} - -\begin{exercise} Write the implementation of \code{orGate}. -\end{exercise} - -\begin{exercise} Another way is to define an or-gate by a combination of -inverters and and gates. Define a function \code{orGate} in terms of -\code{andGate} and \code{inverter}. What is the delay time of this function? -\end{exercise} - -\paragraph{The Simulation Class} - -Now, we just need to implement class \code{Simulation}, and we are -done. The idea is that we maintain inside a \code{Simulation} object -an \emph{agenda} of actions to perform. The agenda is represented as -a list of pairs of actions and the times they need to be run. The -agenda list is sorted, so that earlier actions come before later ones. -\begin{lstlisting} -class Simulation { - private type Agenda = List[Pair[int, Action]]; - private var agenda: Agenda = List(); -\end{lstlisting} -There is also a private variable \code{curtime} to keep track of the -current simulated time. -\begin{lstlisting} - private var curtime = 0; -\end{lstlisting} -An application of the method \code{afterDelay(delay, action)} -inserts the pair \code{(curtime + delay, action)} into the -\code{agenda} list at the appropriate place. -\begin{lstlisting} - def afterDelay(int delay)(action: => Action): unit = { - val actiontime = curtime + delay; - def insertAction(ag: Agenda): Agenda = ag match { - case List() => - Pair(actiontime, action) :: ag - case (first @ Pair(time, act)) :: ag1 => - if (actiontime < time) Pair(actiontime, action) :: ag - else first :: insert(ag1) - } - agenda = insert(agenda) - } -\end{lstlisting} -An application of the \code{run} method removes successive elements -from the \code{agenda} and performs their actions. -It continues until the agenda is empty: -\begin{lstlisting} -def run = { - afterDelay(0, () => System.out.println("*** simulation started ***")); - agenda match { - case List() => - case Pair(_, action) :: agenda1 => - agenda = agenda1; action(); run - } -} -\end{lstlisting} - - -\paragraph{Running the Simulator} -To run the simulator, we still need a way to inspect changes of -signals on wires. To this purpose, we write a function \code{probe}. -\begin{lstlisting} -def probe(name: String, wire: Wire): unit = { - wire addAction (() => - System.out.println( - name + " " + currentTime + " new_value = " + wire.getSignal); - ) -} -\end{lstlisting} -Now, to see the simulator in action, let's define four wires, and place -probes on two of them: -\begin{lstlisting} -> val input1 = new Wire -> val input2 = new Wire -> val sum = new Wire -> val carry = new Wire - -> probe("sum", sum) -sum 0 new_value = false -> probe("carry", carry) -carry 0 new_value = false -\end{lstlisting} -Now let's define a half-adder connecting the wires: -\begin{lstlisting} -> halfAdder(input1, input2, sum, carry); -\end{lstlisting} -Finally, set one after another the signals on the two input wires to -\code{true} and run the simulation. -\begin{lstlisting} -> input1 setSignal true; run -*** simulation started *** -sum 8 new_value = true -> input2 setSignal true; run -carry 11 new_value = true -sum 15 new_value = false -\end{lstlisting} - -\section{Summary} - -We have seen in this chapter the constructs that let us model state in -Scala -- these are variables, assignments, and imperative control -structures. State and Assignment complicate our mental model of -computation. In particular, referential transparency is lost. On the -other hand, assignment gives us new ways to formulate programs -elegantly. As always, it depends on the situation whether purely -functional programming or programming with assignments works best. - -\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 modeled by changing the state of variables in a -computation. Time changes in the real world thus are modeled 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 modeled by -a function \code{f(t)} with a time parameter \code{t}. The same can be -done in computation. Instead of overwriting a variable with successive -values, we represent all these values as successive elements in a -list. So, a mutable variable \code{var x: T} gets replaced by an -immutable value \code{val x: List[T]}. In a sense, we trade space for -time -- the different values of the variable now all exit concurrently -as different elements of the list. One advantage of the list-based -view is that we can ``time-travel'', i.e. view several successive -values of the variable at the same time. Another advantage is that we -can make use of the powerful library of list processing functions, -which often simplifies computation. For instance, consider the -imperative way to compute the sum of all prime numbers in an interval: -\begin{lstlisting} -def sumPrimes(start: int, end: int): int = { - var i = start; - var acc = 0; - while (i < end) { - if (isPrime(i)) acc = acc + i; - i = i + 1; - } - acc -} -\end{lstlisting} -Note that the variable \code{i} ``steps through'' all values of the interval -\code{[start .. end-1]}. - -A more functional way is to represent the list of values of variable \code{i} directly as \code{range(start, end)}. Then the function can be rewritten as follows. -\begin{lstlisting} -def sumPrimes(start: int, end: int) = - sum(range(start, end) filter isPrime); -\end{lstlisting} - -No contest which program is shorter and clearer! However, the -functional program is also considerably less efficient since it -constructs a list of all numbers in the interval, and then another one -for the prime numbers. Even worse from an efficiency point of view is -the following example: - -To find the second prime number between \code{1000} and \code{10000}: -\begin{lstlisting} - range(1000, 10000) filter isPrime at 1 -\end{lstlisting} -Here, the list of all numbers between \code{1000} and \code{10000} is -constructed. But most of that list is never inspected! - -However, we can obtain efficient execution for examples like these by -a trick: -\begin{quote} -%\red - Avoid computing the tail of a sequence unless that tail is actually - necessary for the computation. -\end{quote} -We define a new class for such sequences, which is called \code{Stream}. - -Streams are created using the constant \code{empty} and the constructor \code{cons}, -which are both defined in module \code{scala.Stream}. For instance, the following -expression constructs a stream with elements \code{1} and \code{2}: -\begin{lstlisting} -Stream.cons(1, Stream.cons(2, Stream.empty)) -\end{lstlisting} -As another example, here is the analogue of \code{List.range}, -but returning a stream instead of a list: -\begin{lstlisting} -def range(start: Int, end: Int): Stream[Int] = - if (start >= end) Stream.empty - else Stream.cons(start, range(start + 1, end)); -\end{lstlisting} -(This function is also defined as given above in module -\code{Stream}). Even though \code{Stream.range} and \code{List.range} -look similar, their execution behavior is completely different: - -\code{Stream.range} immediately returns with a \code{Stream} object -whose first element is \code{start}. All other elements are computed -only when they are \emph{demanded} by calling the \code{tail} method -(which might be never at all). - -Streams are accessed just as lists. as for lists, the basic access -methods are \code{isEmpty}, \code{head} and \code{tail}. For instance, -we can print all elements of a stream as follows. -\begin{lstlisting} -def print(xs: Stream[a]): unit = - if (!xs.isEmpty) { System.out.println(xs.head); print(xs.tail) }; -\end{lstlisting} -Streams also support almost all other methods defined on lists (see -below for where their methods sets differ). For instance, we can find -the second prime number between \code{1000} and \code{10000} by applying methods -\code{filter} and \code{apply} on an interval stream: -\begin{lstlisting} - Stream.range(1000, 10000) filter isPrime at 1 -\end{lstlisting} -The difference to the previous list-based implementation is that now -we do not needlessly construct and test for primality any numbers -beyond 3. - -\paragraph{Consing and appending streams} Two methods in class \code{List} -which are not supported by class \code{Stream} are \code{::} and -\code{:::}. The reason is that these methods are dispatched on their -right-hand side argument, which means that this argument needs to be -evaluated before the method is called. For instance, in the case of -\code{x :: xs} on lists, the tail \code{xs} needs to be evaluated -before \code{::} can be called and the new list can be constructed. -This does not work for streams, where we require that the tail of a -stream should not be evaluated until it is demanded by a \code{tail} operation. -The argument why list-append \code{:::} cannot be adapted to streams is analogous. - -Instead of \code{x :: xs}, one uses \code{Stream.cons(x, xs)} for -constructing a stream with first element \code{x} and (unevaluated) -rest \code{xs}. Instead of \code{xs ::: ys}, one uses the operation -\code{xs append ys}. - -\chapter{Iterators} - -Iterators are the imperative version of streams. Like streams, -iterators describe potentially infinite lists. However, there is no -data-structure which contains the elements of an iterator. Instead, -iterators allow one to step through the sequence, using two abstract methods \code{next} and \code{hasNext}. -\begin{lstlisting} -trait Iterator[+a] { - def hasNext: boolean; - def next: a; -\end{lstlisting} -Method \code{next} returns successive elements. Method \code{hasNext} -indicates whether there are still more elements to be returned by -\code{next}. Iterators also support some other methods, which are -explained later. - -As an example, here is an application which prints the squares of all -numbers from 1 to 100. -\begin{lstlisting} -var it: Iterator[int] = Iterator.range(1, 100); -while (it.hasNext) { - val x = it.next; - System.out.println(x * x) -} -\end{lstlisting} - -\section{Iterator Methods} - -Iterators support a rich set of methods besides \code{next} and -\code{hasNext}, which is described in the following. Many of these -methods mimic a corresponding functionality in lists. - -\paragraph{Append} -Method \code{append} constructs an iterator which resumes with the -given iterator \code{it} after the current iterator has finished. -\begin{lstlisting} - def append[b >: a](that: Iterator[b]): Iterator[b] = new Iterator[b] { - def hasNext = Iterator.this.hasNext || that.hasNext; - def next = if (Iterator.this.hasNext) Iterator.this.next else that.next; - } -\end{lstlisting} -The terms \code{Iterator.this.next} and \code{Iterator.this.hasNext} -in the definition of \code{append} call the corresponding methods as -they are defined in the enclosing \code{Iterator} class. If the -\code{Iterator} prefix to \code{this} would have been missing, -\code{hasNext} and \code{next} would have called recursively the -methods being defined in the result of \code{append}, which is not -what we want. - -\paragraph{Map, FlatMap, Foreach} Method \code{map} -constructs an iterator which returns all elements of the original -iterator transformed by a given function \code{f}. -\begin{lstlisting} - def map[b](f: a => b): Iterator[b] = new Iterator[b] { - def hasNext = Iterator.this.hasNext; - def next = f(Iterator.this.next); - } -\end{lstlisting} -Method \code{flatMap} is like method \code{map}, except that the -transformation function \code{f} now returns an iterator. -The result of \code{flatMap} is the iterator resulting from appending -together all iterators returned from successive calls of \code{f}. -\begin{lstlisting} - def flatMap[b](f: a => Iterator[b]): Iterator[b] = new Iterator[b] { - private var cur: Iterator[b] = Iterator.empty; - def hasNext: Boolean = - if (cur.hasNext) true - else if (Iterator.this.hasNext) { cur = f(Iterator.this.next); hasNext } - else false; - def next: b = - if (cur.hasNext) cur.next - else if (Iterator.this.hasNext) { cur = f(Iterator.this.next); next } - else throw new Error("next on empty iterator"); - } -\end{lstlisting} -Closely related to \code{map} is the \code{foreach} method, which -applies a given function to all elements of an iterator, but does not -construct a list of results -\begin{lstlisting} - def foreach(f: a => Unit): Unit = - while (hasNext) { f(next) } -\end{lstlisting} - -\paragraph{Filter} Method \code{filter} constructs an iterator which -returns all elements of the original iterator that satisfy a criterion -\code{p}. -\begin{lstlisting} - def filter(p: a => Boolean) = new BufferedIterator[a] { - private val source = - Iterator.this.buffered; - private def skip: Unit = - while (source.hasNext && !p(source.head)) { source.next; () } - def hasNext: Boolean = - { skip; source.hasNext } - def next: a = - { skip; source.next } - def head: a = - { skip; source.head; } - } -\end{lstlisting} -In fact, \code{filter} returns instances of a subclass of iterators -which are ``buffered''. A \code{BufferedIterator} object is an -iterator which has in addition a method \code{head}. This method -returns the element which would otherwise have been returned by -\code{head}, but does not advance beyond that element. Hence, the -element returned by \code{head} is returned again by the next call to -\code{head} or \code{next}. Here is the definition of the -\code{BufferedIterator} trait. -\begin{lstlisting} -trait BufferedIterator[+a] extends Iterator[a] { - def head: a; -} -\end{lstlisting} -Since \code{map}, \code{flatMap}, \code{filter}, and \code{foreach} -exist for iterators, it follows that for-comprehensions and for-loops -can also be used on iterators. For instance, the application which prints the squares of numbers between 1 and 100 could have equivalently been expressed as follows. -\begin{lstlisting} -for (val i <- Iterator.range(1, 100)) - System.out.println(i * i); -\end{lstlisting} - -\paragraph{Zip} Method \code{zip} takes another iterator and -returns an iterator consisting of pairs of corresponding elements -returned by the two iterators. -\begin{lstlisting} - def zip[b](that: Iterator[b]) = new Iterator[Pair[a, b]] { - def hasNext = Iterator.this.hasNext && that.hasNext; - def next = Pair(Iterator.this.next, that.next); - } -} -\end{lstlisting} - -\section{Constructing Iterators} - -Concrete iterators need to provide implementations for the two -abstract methods \code{next} and \code{hasNext} in class -\code{Iterator}. The simplest iterator is \code{Iterator.empty} which -always returns an empty sequence: -\begin{lstlisting} -object Iterator { - object empty extends Iterator[All] { - def hasNext = false; - def next: a = throw new Error("next on empty iterator"); - } -\end{lstlisting} -A more interesting iterator enumerates all elements of an array. This -iterator is constructed by the \code{fromArray} method, which is also defined in the object \code{Iterator} -\begin{lstlisting} - def fromArray[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 throw new Error("next on empty iterator"); - } -\end{lstlisting} -Another iterator enumerates an integer interval. The -\code{Iterator.range} function returns an iterator which traverses a -given interval of integer values. It is defined as follows. -\begin{lstlisting} -object Iterator { - def range(start: int, end: int) = new Iterator[int] { - private var current = start; - def hasNext = current < end; - def next = { - val r = current; - if (current < end) current = current + 1 - else throw new Error("end of iterator"); - r - } - } -} -\end{lstlisting} -All iterators seen so far terminate eventually. It is also possible to -define iterators that go on forever. For instance, the following -iterator returns successive integers from some start -value\footnote{Due to the finite representation of type \prog{int}, -numbers will wrap around at $2^31$.}. -\begin{lstlisting} -def from(start: int) = new Iterator[int] { - private var last = start - 1; - def hasNext = true; - def next = { last = last + 1; last } -} -\end{lstlisting} - -\section{Using Iterators} - -Here are two more examples how iterators are used. First, to print all -elements of an array \code{xs: Array[int]}, one can write: -\begin{lstlisting} - Iterator.fromArray(xs) foreach (x => - System.out.println(x)) -\end{lstlisting} -Or, using a for-comprehension: -\begin{lstlisting} - for (val x <- Iterator.fromArray(xs)) - System.out.println(x) -\end{lstlisting} -As a second example, consider the problem of finding the indices of -all the elements in an array of \code{double}s greater than some -\code{limit}. The indices should be returned as an iterator. -This is achieved by the following expression. -\begin{lstlisting} -import Iterator._; -fromArray(xs) -.zip(from(0)) -.filter(case Pair(x, i) => x > limit) -.map(case Pair(x, i) => i) -\end{lstlisting} -Or, using a for-comprehension: -\begin{lstlisting} -import Iterator._; -for (val Pair(x, i) <- fromArray(xs) zip from(0); x > limit) -yield i -\end{lstlisting} - - - - - - - -\chapter{Combinator Parsing}\label{sec: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 {\em parser combinators}, that closely model the -constructions of an EBNF grammar \cite{wirth:ebnf}. - -As running example, we consider parsers for possibly nested -lists of identifiers and numbers, which -are 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] -list &::=& `(' [listElems] `)' \\ -listElems &::=& expr [`,' listElems] \\ -expr &::=& ident | number | list - -\eda - -\section{Simple Combinator Parsing} - -In this section we will only be concerned with the task of recognizing -input strings, not with processing them. So we can describe parsers -by the sets of input strings they accept. There are two -fundamental operators over parsers: -\code{&&&} expresses the sequential composition of a parser with -another, while \code{|||} expresses an alternative. These operations -will both be defined as methods of a \code{Parser} class. We will -also define constructors for the following primitive parsers: - -\begin{tabular}{ll} -\code{empty} & The parser that accepts the empty string -\\ -\code{fail} & The parser that accepts no string -\\ -\code{chr(c: char)} - & The parser that accepts the single-character string ``$c$''. -\\ -\code{chr(p: char => boolean)} - & The parser that accepts single-character strings - ``$c$'' \\ - & for which $p(c)$ is true. -\end{tabular} - -There are also the two higher-order parser combinators \code{opt}, -expressing optionality and \code{rep}, expressing repetition. -For any parser $p$, \code{opt(}$p$\code{)} yields a parser that -accepts the strings accepted by $p$ or else the empty string, while -\code{rep(}$p$\code{)} accepts arbitrary sequences of the strings accepted by -$p$. In EBNF, \code{opt(}$p$\code{)} corresponds to $[p]$ and -\code{rep(}$p$\code{)} corresponds to $\{p\}$. - -The central idea of parser combinators is that parsers can be produced -by a straightforward rewrite of the grammar, replacing \code{::=} with -\code{=}, sequencing with -\code{&&&}, choice -\code{|} with \code{|||}, repetition \code{\{...\}} with -\code{rep(...)} and optional occurrence \code{[...]} with \code{opt(...)}. -Applying this process to the grammar of lists -yields the following class. -\begin{lstlisting} -abstract class ListParsers extends Parsers { - def chr(p: char => boolean): Parser; - def chr(c: char): Parser = chr(d: char => d == c); - - def letter : Parser = chr(Character.isLetter); - def digit : Parser = chr(Character.isDigit); - - def ident : Parser = letter &&& rep(letter ||| digit); - def number : Parser = digit &&& rep(digit); - def list : Parser = chr('(') &&& opt(listElems) &&& chr(')'); - def listElems : Parser = expr &&& (chr(',') &&& listElems ||| empty); - def expr : Parser = ident ||| number ||| list; -} -\end{lstlisting} -This class isolates the grammar from other aspects of parsing. It -abstracts over the type of input -and over the method used to parse a single character -(represented by the abstract method \code{chr(p: char => -boolean))}. The missing bits of information need to be supplied by code -applying the parser class. - -It remains to explain how to implement a library with the combinators -described above. We will pack combinators and their underlying -implementation in a base class \code{Parsers}, which is inherited by -\code{ListParsers}. The first question to decide is which underlying -representation type to use for a parser. We treat parsers here -essentially as functions that take a datum of the input type -\code{intype} and that yield a parse result of type -\code{Option[intype]}. The \code{Option} type is predefined as -follows. -\begin{lstlisting} -trait Option[+a]; -case object None extends Option[All]; -case class Some[a](x: a) extends Option[a]; -\end{lstlisting} -A parser applied to some input either succeeds or fails. If it fails, -it returns the constant \code{None}. If it succeeds, it returns a -value of the form \code{Some(in1)} where \code{in1} represents the -input that remains to be parsed. -\begin{lstlisting} -abstract class Parsers { - type intype; - abstract class Parser { - type Result = Option[intype]; - def apply(in: intype): Result; -\end{lstlisting} -A parser also implements the combinators -for sequence and alternative: -\begin{lstlisting} - /*** p &&& q applies first p, and if that succeeds, then q - */ - def &&& (q: => Parser) = new Parser { - def apply(in: intype): Result = Parser.this.apply(in) match { - case None => None - case Some(in1) => q(in1) - } - } - - /*** p ||| q applies first p, and, if that fails, then q. - */ - def ||| (q: => Parser) = new Parser { - def apply(in: intype): Result = Parser.this.apply(in) match { - case None => q(in) - case s => s - } - } -\end{lstlisting} -The implementations of the primitive parsers \code{empty} and \code{fail} -are trivial: -\begin{lstlisting} - val empty = new Parser { def apply(in: intype): Result = Some(in) } - val fail = new Parser { def apply(in: intype): Result = None } -\end{lstlisting} -The higher-order parser combinators \code{opt} and \code{rep} can be -defined in terms of the combinators for sequence and alternative: -\begin{lstlisting} - def opt(p: Parser): Parser = p ||| empty; // p? = (p | <empty>) - def rep(p: Parser): Parser = opt(rep1(p)); // p* = [p+] - def rep1(p: Parser): Parser = p &&& rep(p); // p+ = p p* -} // end Parser -\end{lstlisting} -To run combinator parsers, we still need to decide on a way to handle -parser input. Several possibilities exist: The input could be -represented as a list, as an array, or as a random access file. Note -that the presented combinator parsers use backtracking to change from -one alternative to another. Therefore, it must be possible to reset -input to a point that was previously parsed. If one restricted the -focus to LL(1) grammars, a non-backtracking implementation of the -parser combinators in class \code{Parsers} would also be possible. In -that case sequential input methods based on (say) iterators or -sequential files would also be possible. - -In our example, we represent the input by a pair of a string, which -contains the input phrase as a whole, and an index, which represents -the portion of the input which has not yet been parsed. Since the -input string does not change, just the index needs to be passed around -as a result of individual parse steps. This leads to the following -class of parsers that read strings: -\begin{lstlisting} -class ParseString(s: String) extends Parsers { - type intype = int; - def chr(p: char => boolean) = new Parser { - def apply(in: int): Parser#Result = - if (in < s.length() && p(s charAt in)) Some(in + 1); - else None; - } - val input = 0; -} -\end{lstlisting} -This class implements a method \code{chr(p: char => boolean)} and a -value \code{input}. The \code{chr} method builds a parser that either -reads a single character satisfying the given predicate \code{p} or -fails. All other parsers over strings are ultimately implemented in -terms of that method. The \code{input} value represents the input as a -whole. In out case, it is simply value \code{0}, the start index of -the string to be read. - -Note \code{apply}'s result type, \code{Parser#Result}. This syntax -selects the type element \code{Result} of the type \code{Parser}. It -thus corresponds roughly to selecting a static inner class from some -outer class in Java. Note that we could {\em not} have written -\code{Parser.Result}, as the latter would express selection of the -\code{Result} element from a {\em value} named \code{Parser}. - -We have now extended the root class \code{Parsers} in two different -directions: Class \code{ListParsers} defines a grammar of phrases to -be parsed, whereas class \code{ParseString} defines a method by which -such phrases are input. To write a concrete parsing application, we -need to define both grammar and input method. We do this by combining -two extensions of \code{Parsers} using a {\em mixin composition}. -Here is the start of a sample application: -\begin{lstlisting} -object Test { - def main(args: Array[String]): unit = { - val ps = new ListParsers with ParseString(args(0)); -\end{lstlisting} -The last line above creates a new family of parsers by composing class -\code{ListParsers} with class \code{ParseString}. The two classes -share the common superclass \code{Parsers}. The abstract method -\code{chr} in \code{ListParsers} is implemented by class \code{ParseString}. - -To run the parser, we apply the start symbol of the grammar -\code{expr} the argument code{input} and observe the result: -\begin{lstlisting} - ps.expr(input) match { - case Some(n) => - System.out.println("parsed: " + args(0).substring(0, n)); - case None => - System.out.println("nothing parsed"); - } - } -}// end Test -\end{lstlisting} -Note the syntax ~\code{ps.expr(input)}, which treats the \code{expr} -parser as if it was a function. In Scala, objects with \code{apply} -methods can be applied directly to arguments as if they were functions. - -Here is an example run of the program above: -\begin{lstlisting} -> java examples.Test "(x,1,(y,z))" -parsed: (x,1,(y,z)) -> java examples.Test "(x,,1,(y,z))" -nothing parsed -\end{lstlisting} - -\section{\label{sec:parsers-results}Parsers that Produce Results} - -The combinator library of the previous section does not support the -generation of output from parsing. But usually one does not just want -to check whether a given string belongs to the defined language, one -also wants to convert the input string into some internal -representation such as an abstract syntax tree. - -In this section, we modify our parser library to build parsers that -produce results. We will make use of the for-comprehensions introduced -in Chapter~\ref{sec:for-notation}. The basic combinator of sequential -composition, formerly ~\code{p &&& q}, now becomes -\begin{lstlisting} -for (val x <- p; val y <- q) yield e . -\end{lstlisting} -Here, the names \code{x} and \code{y} are bound to the results of -executing the parsers \code{p} and \code{q}. \code{e} is an expression -that uses these results to build the tree returned by the composed -parser. - -Before describing the implementation of the new parser combinators, we -explain how the new building blocks are used. Say we want to modify -our list parser so that it returns an abstract syntax tree of the -parsed expression. Syntax trees are given by the following class hierarchy: -\begin{lstlisting} -abstract class Tree{} -case class Id (s: String) extends Tree {} -case class Num(n: int) extends Tree {} -case class Lst(elems: List[Tree]) extends Tree {} -\end{lstlisting} -That is, a syntax tree is an identifier, an integer number, or a -\code{Lst} node with a list of trees as descendants. - -As a first step towards parsers that produce results we define three -little parsers that return a single read character as result. -\begin{lstlisting} -abstract class CharParsers extends Parsers { - def any: Parser[char]; - def chr(ch: char): Parser[char] = - for (val c <- any; c == ch) yield c; - def chr(p: char => boolean): Parser[char] = - for (val c <- any; p(c)) yield c; -} -\end{lstlisting} -The \code{any} parser succeeds with the first character of remaining -input as long as input is nonempty. It is abstract in class -\code{ListParsers} since we want to abstract in this class from the -concrete input method used. The two \code{chr} parsers return as before -the first input character if it equals a given character or matches a -given predicate. They are now implemented in terms of \code{any}. - -The next level is represented by parsers reading identifiers, numbers -and lists. Here is a parser for identifiers. -\begin{lstlisting} -abstract class ListParsers extends CharParsers { - def ident: Parser[Tree] = - for ( - val c: char <- chr(Character.isLetter); - val cs: List[char] <- rep(chr(Character.isLetterOrDigit)) - ) yield Id((c :: cs).mkString("", "", "")); -\end{lstlisting} -Remark: Because \code{chr(...)} returns a single character, its -repetition \code{rep(chr(...))} returns a list of characters. The -\code{yield} part of the for-comprehension converts all intermediate -results into an \code{Id} node with a string as element. To convert -the read characters into a string, it conses them into a single list, -and invokes the \code{mkString} method on the result. - -Here is a parser for numbers: -\begin{lstlisting} - def number: Parser[Tree] = - for ( - val d: char <- chr(Character.isDigit); - val ds: List[char] <- rep(chr(Character.isDigit)) - ) yield Num(((d - '0') /: ds) ((x, digit) => x * 10 + digit - '0')); -\end{lstlisting} -Intermediate results are in this case the leading digit of -the read number, followed by a list of remaining digits. The -\code{yield} part of the for-comprehension reduces these to a number -by a fold-left operation. - -Here is a parser for lists: -\begin{lstlisting} - def list: Parser[Tree] = - for ( - val _ <- chr('('); - val es <- listElems ||| succeed(List()); - val _ <- chr(')') - ) yield Lst(es); - - def listElems: Parser[List[Tree]] = - for ( - val x <- expr; - val xs <- chr(',') &&& listElems ||| succeed(List()) - ) yield x :: xs; -\end{lstlisting} -The \code{list} parser returns a \code{Lst} node with a list of trees -as elements. That list is either the result of \code{listElems}, or, -if that fails, the empty list (expressed here as: the result of a -parser which always succeeds with the empty list as result). - -The highest level of our grammar is represented by function -\code{expr}: -\begin{lstlisting} - def expr: Parser[Tree] = - ident ||| number ||| list -}// end ListParsers. -\end{lstlisting} -We now present the parser combinators that support the new -scheme. Parsers that succeed now return a parse result besides the -un-consumed input. -\begin{lstlisting} -abstract class Parsers { - type intype; - trait Parser[a] { - type Result = Option[Pair[a, intype]]; - def apply(in: intype): Result; -\end{lstlisting} -Parsers are parameterized with the type of their result. The class -\code{Parser[a]} now defines new methods \code{map}, \code{flatMap} -and \code{filter}. The \code{for} expressions are mapped by the -compiler to calls of these functions using the scheme described in -Chapter~\ref{sec:for-notation}. For parsers, these methods are -implemented as follows. -\begin{lstlisting} - def filter(pred: a => boolean) = new Parser[a] { - def apply(in: intype): Result = Parser.this.apply(in) match { - case None => None - case Some(Pair(x, in1)) => if (pred(x)) Some(Pair(x, in1)) else None - } - } - def map[b](f: a => b) = new Parser[b] { - def apply(in: intype): Result = Parser.this.apply(in) match { - case None => None - case Some(Pair(x, in1)) => Some(Pair(f(x), in1)) - } - } - def flatMap[b](f: a => Parser[b]) = new Parser[b] { - def apply(in: intype): Result = Parser.this.apply(in) match { - case None => None - case Some(Pair(x, in1)) => f(x).apply(in1) - } - } -\end{lstlisting} -The \code{filter} method takes as parameter a predicate $p$ which it -applies to the results of the current parser. If the predicate is -false, the parser fails by returning \code{None}; otherwise it returns -the result of the current parser. The \code{map} method takes as -parameter a function $f$ which it applies to the results of the -current parser. The \code{flatMap} takes as parameter a function -\code{f} which returns a parser. It applies \code{f} to the result of -the current parser and then continues with the resulting parser. The -\code{|||} method is essentially defined as before. The -\code{&&&} method can now be defined in terms of \code{for}. -\begin{lstlisting} - def ||| (p: => Parser[a]) = new Parser[a] { - def apply(in: intype): Result = Parser.this.apply(in) match { - case None => p(in) - case s => s - } - } - - def &&& [b](p: => Parser[b]): Parser[b] = - for (val _ <- this; val x <- p) yield x; - }// end Parser -\end{lstlisting} - -The primitive parser \code{succeed} replaces \code{empty}. It consumes -no input and returns its parameter as result. -\begin{lstlisting} - def succeed[a](x: a) = new Parser[a] { - def apply(in: intype) = Some(Pair(x, in)) - } -\end{lstlisting} - -The parser combinators \code{rep} and \code{opt} now also return -results. \code{rep} returns a list which contains as elements the -results of each iteration of its sub-parser. \code{opt} returns a list -which is either empty or returns as single element the result of the -optional parser. -\begin{lstlisting} - def rep[a](p: Parser[a]): Parser[List[a]] = - rep1(p) ||| succeed(List()); - - 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[List[a]] = - (for (val x <- p) yield List(x)) ||| succeed(List()); -} // end Parsers -\end{lstlisting} -The root class \code{Parsers} abstracts over which kind of -input is parsed. As before, we determine the input method by a separate class. -Here is \code{ParseString}, this time adapted to parsers that return results. -It defines now the method \code{any}, which returns the first input character. -\begin{lstlisting} -class ParseString(s: String) extends Parsers { - type intype = int; - val input = 0; - def any = new Parser[char] { - def apply(in: int): Parser[char]#Result = - if (in < s.length()) Some(Pair(s charAt in, in + 1)) else None; - } -} -\end{lstlisting} -The rest of the application is as before. Here is a test program which -constructs a list parser over strings and prints out the result of -applying it to the command line argument. -\begin{lstlisting} -object Test { - def main(args: Array[String]): unit = { - val ps = new ListParsers with ParseString(args(0)); - ps.expr(ps.input) match { - case Some(Pair(list, _)) => System.out.println("parsed: " + list); - case None => "nothing parsed" - } - } -} -\end{lstlisting} - -\begin{exercise}\label{exercise:end-marker} The parsers we have defined so -far can succeed even if there is some input beyond the parsed text. To -prevent this, one needs a parser which recognizes the end of input. -Redesign the parser library so that such a parser can be introduced. -Which classes need to be modified? -\end{exercise} - -\chapter{\label{sec:hm}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 -\cite{milner:polymorphism}. The source language for the type inferencer is -lambda calculus with a let construct called Mini-ML. Abstract syntax -trees for the Mini-ML are represented by the following data type of -\code{Terms}. -\begin{lstlisting} -trait Term {} -case class Var(x: String) extends Term { - override def toString() = x; -} -case class Lam(x: String, e: Term) extends Term { - override def toString() = "(\\" + x + "." + e + ")"; -} -case class App(f: Term, e: Term) extends Term { - override def toString() = "(" + f + " " + e + ")"; -} -case class Let(x: String, e: Term, f: Term) extends Term { - override def toString() = "let " + x + " = " + e + " in " + f; -} -\end{lstlisting} -There are four tree constructors: \code{Var} for variables, \code{Lam} -for function abstractions, \code{App} for function applications, and -\code{Let} for let expressions. Each case class overrides the -\code{toString()} method of class \code{Any}, so that terms can be -printed in legible form. - -We next define the types that are -computed by the inference system. -\begin{lstlisting} -sealed trait Type {} -case class Tyvar(a: String) extends Type { - override def toString() = a; -} -case class Arrow(t1: Type, t2: Type) extends Type { - override def toString() = "(" + t1 + "->" + t2 + ")"; -} -case class Tycon(k: String, ts: List[Type]) extends Type { - override def toString() = - k + (if (ts.isEmpty) "" else ts.mkString("[", ",", "]")); -} -\end{lstlisting} -There are three type constructors: \code{Tyvar} for type variables, -\code{Arrow} for function types and \code{Tycon} for type constructors -such as \code{boolean} or \code{List}. Type constructors have as -component a list of their type parameters. This list is empty for type -constants such as \code{boolean}. Again, the type constructors -implement the \code{toString} method in order to display types legibly. - -Note that \code{Type} is a \code{sealed} class. This means that no -subclasses or data constructors that extend \code{Type} can be formed -outside the sequence of definitions in which \code{Type} is defined. -This makes \code{Type} a {\em closed} algebraic data type with exactly -three alternatives. By contrast, type \code{Term} is an {\em open} -algebraic type for which further alternatives can be defined. - -The main parts of the type inferencer are contained in object -\code{typeInfer}. We start with a utility function which creates -fresh type variables: -\begin{lstlisting} -object typeInfer { - private var n: Int = 0; - def newTyvar(): Type = { n = n + 1 ; Tyvar("a" + n) } -\end{lstlisting} -We next define a class for substitutions. A substitution is an -idempotent function from type variables to types. It maps a finite -number of type variables to some types, and leaves all other type -variables unchanged. The meaning of a substitution is extended -point-wise to a mapping from types to types. -\begin{lstlisting} - trait Subst extends Any with Function1[Type,Type] { - - def lookup(x: Tyvar): Type; - - def apply(t: Type): Type = t match { - case tv @ Tyvar(a) => val u = lookup(tv); 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 Subst.this.lookup(y); - } - } - val emptySubst = new Subst { def lookup(t: Tyvar): Type = t } -\end{lstlisting} -We represent substitutions as functions, of type \code{Type => -Type}. This is achieved by making class \code{Subst} inherit from the -unary function type \code{Function1[Type, Type]}\footnote{ -The class inherits the function type as a mixin rather than as a direct -superclass. This is because in the current Scala implementation, the -\code{Function1} type is a Java interface, which cannot be used as a direct -superclass of some other class.}. -To be an instance -of this type, a substitution \code{s} has to implement an \code{apply} -method that takes a \code{Type} as argument and yields another -\code{Type} as result. A function application \code{s(t)} is then -interpreted as \code{s.apply(t)}. - -The \code{lookup} method is abstract in class \code{Subst}. There are -two concrete forms of substitutions which differ in how they -implement this method. One form is defined by the \code{emptySubst} value, -the other is defined by the \code{extend} method in class -\code{Subst}. - -The next data type describes type schemes, which consist of a type and -a list of names of type variables which appear universally quantified -in the type scheme. -For instance, the type scheme $\forall a\forall b.a \!\arrow\! b$ would be represented in the type checker as: -\begin{lstlisting} -TypeScheme(List(TyVar("a"), TyVar("b")), Arrow(Tyvar("a"), Tyvar("b"))) . -\end{lstlisting} -The class definition of type schemes does not carry an extends -clause; this means that type schemes extend directly class -\code{AnyRef}. Even though there is only one possible way to -construct a type scheme, a case class representation was chosen -since it offers convenient ways to decompose an instance of this type into its -parts. -\begin{lstlisting} -case class TypeScheme(tyvars: List[String], tpe: Type) { - def newInstance: Type = { - (emptySubst /: tyvars) ((s, tv) => s.extend(tv, newTyvar())) (tpe); - } -} -\end{lstlisting} -Type scheme objects come with a method \code{newInstance}, which -returns the type contained in the scheme after all universally type -variables have been renamed to fresh variables. The implementation of -this method folds (with \code{/:}) the type scheme's type variables -with an operation which extends a given substitution \code{s} by -renaming a given type variable \code{tv} to a fresh type -variable. The resulting substitution renames all type variables of the -scheme to fresh ones. This substitution is then applied to the type -part of the type scheme. - -The last type we need in the type inferencer is -\code{Env}, a type for environments, which associate variable names -with type schemes. They are represented by a type alias \code{Env} in -module \code{typeInfer}: -\begin{lstlisting} -type Env = List[Pair[String, TypeScheme]]; -\end{lstlisting} -There are two operations on environments. The \code{lookup} function -returns the type scheme associated with a given name, or \code{null} -if the name is not recorded in the environment. -\begin{lstlisting} - def lookup(env: Env, x: String): TypeScheme = env match { - case List() => null - case Pair(y, t) :: env1 => if (x == y) t else lookup(env1, x) - } -\end{lstlisting} -The \code{gen} function turns a given type into a type scheme, -quantifying over all type variables that are free in the type, but -not in the environment. -\begin{lstlisting} - def gen(env: Env, t: Type): TypeScheme = - TypeScheme(tyvars(t) diff tyvars(env), t); -\end{lstlisting} -The set of free type variables of a type is simply the set of all type -variables which occur in the type. It is represented here as a list of -type variables, which is constructed as follows. -\begin{lstlisting} - def tyvars(t: Type): List[Tyvar] = t match { - case tv @ Tyvar(a) => - List(tv) - case Arrow(t1, t2) => - tyvars(t1) union tyvars(t2) - case Tycon(k, ts) => - (List[Tyvar]() /: ts) ((tvs, t) => tvs union tyvars(t)); - } -\end{lstlisting} -Note that the syntax \code{tv @ ...} in the first pattern introduces a variable -which is bound to the pattern that follows. Note also that the explicit type parameter \code{[Tyvar]} in the expression of the third -clause is needed to make local type inference work. - -The set of free type variables of a type scheme is the set of free -type variables of its type component, excluding any quantified type variables: -\begin{lstlisting} - def tyvars(ts: TypeScheme): List[Tyvar] = - tyvars(ts.tpe) diff ts.tyvars; -\end{lstlisting} -Finally, the set of free type variables of an environment is the union -of the free type variables of all type schemes recorded in it. -\begin{lstlisting} - def tyvars(env: Env): List[Tyvar] = - (List[Tyvar]() /: env) ((tvs, nt) => tvs union tyvars(nt._2)); -\end{lstlisting} -A central operation of Hindley/Milner type checking is unification, -which computes a substitution to make two given types equal (such a -substitution is called a {\em unifier}). Function \code{mgu} computes -the most general unifier of two given types $t$ and $u$ under a -pre-existing substitution $s$. That is, it returns the most general -substitution $s'$ which extends $s$, and which makes $s'(t)$ and -$s'(u)$ equal types. -\begin{lstlisting} - def mgu(t: Type, u: Type, s: Subst): Subst = Pair(s(t), s(u)) match { - case Pair(Tyvar(a), Tyvar(b)) if (a == b) => - s - case Pair(Tyvar(a), _) if !(tyvars(u) contains a) => - s.extend(Tyvar(a), u) - case Pair(_, Tyvar(a)) => - mgu(u, t, s) - case Pair(Arrow(t1, t2), Arrow(u1, u2)) => - mgu(t1, u1, mgu(t2, u2, s)) - case Pair(Tycon(k1, ts), Tycon(k2, us)) if (k1 == k2) => - (s /: (ts zip us)) ((s, tu) => mgu(tu._1, tu._2, s)) - case _ => - throw new TypeError("cannot unify " + s(t) + " with " + s(u)) - } -\end{lstlisting} -The \code{mgu} function throws a \code{TypeError} exception if no -unifier 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. Such exceptions are modeled here as instances of case classes -that inherit from the predefined \code{Exception} class. -\begin{lstlisting} - case class TypeError(s: String) extends Exception(s) {} -\end{lstlisting} -The main task of the type checker is implemented by function -\code{tp}. This function takes as parameters an environment $env$, a -term $e$, a proto-type $t$, and 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{milner:polymorphism}. A -\code{TypeError} exception is thrown if no such substitution exists. -\begin{lstlisting} - def tp(env: Env, e: Term, t: Type, s: Subst): Subst = { - current = e; - e match { - case Var(x) => - val u = lookup(env, x); - if (u == null) throw new TypeError("undefined: " + x); - 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 = Pair(x, TypeScheme(List(), 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(Pair(x, gen(env, s1(a))) :: env, e2, t, s1) - } - } - var current: Term = null; -\end{lstlisting} -To aid error diagnostics, the \code{tp} function stores the currently -analyzed sub-term in variable \code{current}. Thus, if type checking -is aborted with a \code{TypeError} exception, this variable will -contain the subterm that caused the problem. - -The last function of the type inference module, \code{typeOf}, is a -simplified facade for \code{tp}. It computes the type of a given term -$e$ in a given environment $env$. It does so by creating a fresh type -variable $a$, computing a typing substitution that makes $env \ts e: a$ -into a derivable type judgment, and returning -the result of applying the substitution to $a$. -\begin{lstlisting} - def typeOf(env: Env, e: Term): Type = { - val a = newTyvar(); - tp(env, e, a, emptySubst)(a) - } -}// end typeInfer -\end{lstlisting} -To apply the type inferencer, it is convenient to have a predefined -environment that contains bindings for commonly used constants. The -module \code{predefined} defines an environment \code{env} that -contains bindings for the types of booleans, numbers and lists -together with some primitive operations over them. It also -defines a fixed point operator \code{fix}, which can be used to -represent recursion. -\begin{lstlisting} -object predefined { - val booleanType = Tycon("Boolean", List()); - val intType = Tycon("Int", List()); - def listType(t: Type) = Tycon("List", List(t)); - - private def gen(t: Type): typeInfer.TypeScheme = typeInfer.gen(List(), t); - private val a = typeInfer.newTyvar(); - val env = List( - Pair("true", gen(booleanType)), - Pair("false", gen(booleanType)), - Pair("if", gen(Arrow(booleanType, Arrow(a, Arrow(a, a))))), - Pair("zero", gen(intType)), - Pair("succ", gen(Arrow(intType, intType))), - Pair("nil", gen(listType(a))), - Pair("cons", gen(Arrow(a, Arrow(listType(a), listType(a))))), - Pair("isEmpty", gen(Arrow(listType(a), booleanType))), - Pair("head", gen(Arrow(listType(a), a))), - Pair("tail", gen(Arrow(listType(a), listType(a)))), - Pair("fix", gen(Arrow(Arrow(a, a), a))) - ) -} -\end{lstlisting} -Here's an example how the type inferencer can be used. -Let's define a function \code{showType} which returns the type of -a given term computed in the predefined environment -\code{Predefined.env}: -\begin{lstlisting} -object testInfer { - def showType(e: Term): String = - try { - typeInfer.typeOf(predefined.env, e).toString(); - } catch { - case typeInfer.TypeError(msg) => - "\n cannot type: " + typeInfer.current + - "\n reason: " + msg; - } -\end{lstlisting} -Then the application -\begin{lstlisting} -> testInfer.showType(Lam("x", App(App(Var("cons"), Var("x")), Var("nil")))); -\end{lstlisting} -would give the response -\begin{lstlisting} -> (a6->List[a6]) -\end{lstlisting} -To make the type inferencer more useful, we complete it with a -parser. -Function \code{main} of module \code{testInfer} -parses and typechecks a Mini-ML expression which is given as the first -command line argument. -\begin{lstlisting} - def main(args: Array[String]): unit = { - val ps = new MiniMLParsers with ParseString(args(0)); - ps.all(ps.input) match { - case Some(Pair(term, _)) => - System.out.println("" + term + ": " + showType(term)); - case None => - System.out.println("syntax error"); - } - } -}// typeInf -\end{lstlisting} -To do the parsing, method \code{main} uses the combinator parser -scheme of Chapter~\ref{sec:combinator-parsing}. It creates a parser -family \code{ps} as a mixin composition of parsers -that understand MiniML (but do not know where input comes from) and -parsers that read input from a given string. The \code{MiniMLParsers} -object implements parsers for the following grammar. -\begin{lstlisting} -term ::= "\" ident "." term - | term1 {term1} - | "let" ident "=" term "in" term -term1 ::= ident - | "(" term ")" -all ::= term ";" -\end{lstlisting} -Input as a whole is described by the production \code{all}; it -consists of a term followed by a semicolon. We allow ``whitespace'' -consisting of one or more space, tabulator or newline characters -between any two lexemes (this is not reflected in the grammar -above). Identifiers are defined as in -Chapter~\ref{sec:combinator-parsing} except that an identifier cannot -be one of the two reserved words "let" and "in". -\begin{lstlisting} -abstract class MiniMLParsers[intype] extends CharParsers[intype] { - - /** whitespace */ - def whitespace = rep{chr(' ') ||| chr('\t') ||| chr('\n')}; - - /** A given character, possible preceded by whitespace */ - def wschr(ch: char) = whitespace &&& chr(ch); - - /** identifiers or keywords */ - def id: Parser[String] = - for ( - val c: char <- whitespace &&& chr(Character.isLetter); - val cs: List[char] <- rep(chr(Character.isLetterOrDigit)) - ) yield (c :: cs).mkString("", "", ""); - - /** Non-keyword identifiers */ - def ident: Parser[String] = - for (val s <- id; s != "let" && s != "in") yield s; - - /** term = '\' ident '.' term | term1 {term1} | let ident "=" term in term */ - def term: Parser[Term] = - ( for ( - val _ <- wschr('\\'); - val x <- ident; - val _ <- wschr('.'); - val t <- term) - yield Lam(x, t): Term ) - ||| - ( for ( - val letid <- id; letid == "let"; - val x <- ident; - val _ <- wschr('='); - val t <- term; - val inid <- id; inid == "in"; - val c <- term) - yield Let(x, t, c) ) - ||| - ( for ( - val t <- term1; - val ts <- rep(term1)) - yield (t /: ts)((f, arg) => App(f, arg)) ); - - /** term1 = ident | '(' term ')' */ - def term1: Parser[Term] = - ( for (val s <- ident) - yield Var(s): Term ) - ||| - ( for ( - val _ <- wschr('('); - val t <- term; - val _ <- wschr(')')) - yield t ); - - /** all = term ';' */ - def all: Parser[Term] = - for ( - val t <- term; - val _ <- wschr(';')) - yield t; -} -\end{lstlisting} -Here are some sample MiniML programs and the output the type inferencer gives for each of them: -\begin{lstlisting} -> java testInfer -| "\x.\f.f(f x);" -(\x.(\f.(f (f x)))): (a8->((a8->a8)->a8)) - -> java testInfer -| "let id = \x.x -| in if (id true) (id nil) (id (cons zero nil));" -let id = (\x.x) in (((if (id true)) (id nil)) (id ((cons zero) nil))): List[Int] - -> java testInfer -| "let id = \x.x -| in if (id true) (id nil);" -let id = (\x.x) in ((if (id true)) (id nil)): (List[a13]->List[a13]) - -> java testInfer -| "let length = fix (\len.\xs. -| if (isEmpty xs) -| zero -| (succ (len (tail xs)))) -| in (length nil);" -let length = (fix (\len.(\xs.(((if (isEmpty xs)) zero) -(succ (len (tail xs))))))) in (length nil): Int - -> java testInfer -| "let id = \x.x -| in if (id true) (id nil) zero;" -let id = (\x.x) in (((if (id true)) (id nil)) zero): - cannot type: zero - reason: cannot unify Int with List[a14] -\end{lstlisting} - -\begin{exercise}\label{exercise:hm-parse} Using the parser library constructed in -Exercise~\ref{exercise:end-marker}, modify the MiniML parser library -so that no marker ``;'' is necessary for indicating the end of input. -\end{exercise} - -\begin{exercise}\label{execcise:hm-extend} Extend the Mini-ML parser and type -inferencer with a \code{letrec} construct which allows the definition of -recursive functions. Syntax: -\begin{lstlisting} -letrec ident "=" term in term . -\end{lstlisting} -The typing of \code{letrec} is as for \code{let}, -except that the defined identifier is visible in the defining expression. Using \code{letrec}, the \code{length} function for lists can now be defined as follows. -\begin{lstlisting} -letrec length = \xs. - if (isEmpty xs) - zero - (succ (length (tail xs))) -in ... -\end{lstlisting} -\end{exercise} - -\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. Every instance of class \code{AnyRef} can be -used as a monitor by calling one or more of the methods below. -\begin{lstlisting} - def synchronized[a] (e: => a): a; - def wait(): unit; - def wait(msec: long): unit; - def notify(): unit; - def notifyAll(): unit; -\end{lstlisting} -The \code{synchronized} method executes its argument computation -\code{e} in mutual exclusive mode -- at any one time, only one thread -can execute a \code{synchronized} argument of a given monitor. - -Threads can suspend inside a monitor by waiting on a signal. Threads -that call the \code{wait} method wait until a \code{notify} method of -the same object is called subsequently by some other thread. Calls to -\code{notify} with no threads waiting for the signal are ignored. - -There is also a timed form of \code{wait}, which blocks only as long -as no signal was received or the specified amount of time (given in -milliseconds) has elapsed. Furthermore, there is a \code{notifyAll} -method which unblocks all threads which wait for the signal. These -methods, as well as class \code{Monitor} are primitive in Scala; they -are implemented in terms of the underlying runtime system. - -Typically, a thread waits for some condition to be established. If the -condition does not hold at the time of the wait call, the thread -blocks until some other thread has established the condition. It is -the responsibility of this other thread to wake up waiting processes -by issuing a \code{notify} or \code{notifyAll}. Note however, that -there is no guarantee that a waiting process gets to run immediately -after the call to notify is issued. It could be that other processes -get to run first which invalidate the condition again. Therefore, the -correct form of waiting for a condition $C$ uses a while loop: -\begin{lstlisting} -while (!$C$) wait(); -\end{lstlisting} - -As an example of how monitors are used, here is is an implementation -of a bounded buffer class. -\begin{lstlisting} -class BoundedBuffer[a](N: Int) { - var in = 0, out = 0, n = 0; - val elems = new Array[a](N); - - def put(x: a) = synchronized { - while (n >= N) wait(); - elems(in) = x ; in = (in + 1) % N ; n = n + 1; - if (n == 1) notifyAll(); - } - - def get: a = synchronized { - while (n == 0) wait(); - val x = elems(out) ; out = (out + 1) % N ; n = n - 1; - if (n == N - 1) notifyAll(); - x - } -} -\end{lstlisting} -And here is a program using a bounded buffer to communicate between a -producer and a consumer process. -\begin{lstlisting} -import scala.concurrent.ops._; -... -val buf = new BoundedBuffer[String](10); -spawn { while (true) { val s = produceString ; buf.put(s) } } -spawn { while (true) { val s = buf.get ; consumeString(s) } } -} -\end{lstlisting} -The \code{spawn} method spawns a new thread which executes the -expression given in the parameter. It is defined in object \code{concurrent.ops} -as follows. -\begin{lstlisting} -def spawn(p: => unit) = { - val t = new Thread() { override def run() = p; } - t.start() -} -\end{lstlisting} - -\comment{ -\section{Logic Variable} - -A logic variable (or lvar for short) offers operations \code{:=} -and \code{value} to define the variable and to retrieve its value. -Variables can be \code{define}d only once. A call to \code{value} -blocks until the variable has been defined. - -Logic variables can be implemented as follows. - -\begin{lstlisting} -class LVar[a] { - private val defined = new Signal - private var isDefined: boolean = false - private var v: a - def value = synchronized { - if (!isDefined) defined.wait - v - } - def :=(x: a) = synchronized { - v = x ; isDefined = true ; defined.send - } -} -\end{lstlisting} -} - -\section{SyncVars} - -A synchronized variable (or syncvar for short) offers \code{get} and -\code{put} operations to read and set the variable. \code{get} operations -block until the variable has been defined. An \code{unset} operation -resets the variable to undefined state. - -Here's the standard implementation of synchronized variables. -\begin{lstlisting} -package scala.concurrent; -class SyncVar[a] { - private var isDefined: Boolean = false; - private var value: a = _; - def get = synchronized { - if (!isDefined) wait(); - value - } - def set(x: a) = synchronized { - value = x ; isDefined = true ; notifyAll(); - } - def isSet: Boolean = synchronized { - isDefined; - } - def unset = synchronized { - isDefined = false; - } -} -\end{lstlisting} - -\section{Futures} -\label{sec:futures} - -A {\em future} is a value which is computed in parallel to some other -client thread, to be used by the client thread at some future time. -Futures are used in order to make good use of parallel processing -resources. A typical usage is: - -\begin{lstlisting} -import scala.concurrent.ops._; -... -val x = future(someLengthyComputation); -anotherLengthyComputation; -val y = f(x()) + g(x()); -\end{lstlisting} - -The \code{future} method is defined in object -\code{scala.concurrent.ops} as follows. -\begin{lstlisting} -def future[a](p: => a): unit => a = { - val result = new SyncVar[a]; - fork { result.set(p) } - (() => result.get) -} -\end{lstlisting} - -The \code{future} method gets as parameter a computation \code{p} to -be performed. The type of the computation is arbitrary; it is -represented by \code{future}'s type parameter \code{a}. The -\code{future} method defines a guard \code{result}, which takes a -parameter representing the result of the computation. It then forks -off a new thread that computes the result and invokes the -\code{result} guard when it is finished. In parallel to this thread, -the function returns an anonymous function of type \code{a}. -When called, this functions waits on the result guard to be -invoked, and, once this happens returns the result argument. -At the same time, the function reinvokes the \code{result} guard with -the same argument, so that future invocations of the function can -return the result immediately. - -\section{Parallel Computations} - -The next example presents a function \code{par} which takes a pair of -computations as parameters and which returns the results of the computations -in another pair. The two computations are performed in parallel. - -The function is defined in object -\code{scala.concurrent.ops} as follows. -\begin{lstlisting} - def par[a, b](xp: => a, yp: => b): Pair[a, b] = { - val y = new SyncVar[b]; - spawn { y set yp } - Pair(xp, y.get) - } -\end{lstlisting} -Defined in the same place is a function \code{replicate} which performs a -number of replicates of a computation in parallel. Each -replication instance is passed an integer number which identifies it. -\begin{lstlisting} - def replicate(start: Int, end: Int)(p: Int => Unit): Unit = { - if (start == end) - () - else if (start + 1 == end) - p(start) - else { - val mid = (start + end) / 2; - spawn { replicate(start, mid)(p) } - replicate(mid, end)(p) - } - } -\end{lstlisting} - -The next function uses \code{replicate} to perform parallel -computations on all elements of an array. - -\begin{lstlisting} -def parMap[a,b](f: a => b, xs: Array[a]): Array[b] = { - val results = new Array[b](xs.length); - replicate(0, xs.length) { i => results(i) = f(xs(i)) } - results -} -\end{lstlisting} - -\section{Semaphores} - -A common mechanism for process synchronization is a {\em lock} (or: -{\em semaphore}). A lock offers two atomic actions: \prog{acquire} and -\prog{release}. Here's the implementation of a lock in Scala: - -\begin{lstlisting} -package scala.concurrent; - -class Lock { - var available = true; - def acquire = synchronized { - if (!available) wait(); - available = false - } - def release = synchronized { - available = true; - notify() - } -} -\end{lstlisting} - -\section{Readers/Writers} - -A more complex form of synchronization distinguishes between {\em -readers} which access a common resource without modifying it and {\em -writers} which can both access and modify it. To synchronize readers -and writers we need to implement operations \prog{startRead}, \prog{startWrite}, -\prog{endRead}, \prog{endWrite}, such that: -\begin{itemize} -\item there can be multiple concurrent readers, -\item there can only be one writer at one time, -\item pending write requests have priority over pending read requests, -but don't preempt ongoing read operations. -\end{itemize} -The following implementation of a readers/writers lock is based on the -{\em mailbox} concept (see Section~\ref{sec:mailbox}). - -\begin{lstlisting} -import scala.concurrent._; - -class ReadersWriters { - val m = new MailBox; - private case class Writers(n: int), Readers(n: int) { m send this; }; - 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 => } - } - def endRead = m receive { - case Readers(n) => Readers(n-1) - } - def endWrite = m receive { - case Writers(n) => Writers(n-1) ; if (n == 0) Readers(0) - } -} -\end{lstlisting} - -\section{Asynchronous Channels} - -A fundamental way of interprocess communication is the asynchronous -channel. Its implementation makes use the following simple class for linked -lists: -\begin{lstlisting} -class LinkedList[a] { - var elem: a = _; - var next: LinkedList[a] = null; -} -\end{lstlisting} -To facilitate insertion and deletion of elements into linked lists, -every reference into a linked list points to the node which precedes -the node which conceptually forms the top of the list. -Empty linked lists start with a dummy node, whose successor is \code{null}. - -The channel class uses a linked list to store data that has been sent -but not read yet. At the opposite end, threads that -wish to read from an empty channel, register their presence by -incrementing the \code{nreaders} field and waiting to be notified. -\begin{lstlisting} -package scala.concurrent; - -class Channel[a] { - class LinkedList[a] { - var elem: a = _; - var next: LinkedList[a] = null; - } - private var written = new LinkedList[a]; - private var lastWritten = written; - private var nreaders = 0; - - def write(x: a) = synchronized { - lastWritten.elem = x; - lastWritten.next = new LinkedList[a]; - lastWritten = lastWritten.next; - if (nreaders > 0) notify(); - } - - def read: a = synchronized { - if (written.next == null) { - nreaders = nreaders + 1; wait(); nreaders = nreaders - 1; - } - val x = written.elem; - written = written.next; - x - } -} -\end{lstlisting} - -\section{Synchronous Channels} - -Here's an implementation of synchronous channels, where the sender of -a message blocks until that message has been received. Synchronous -channels only need a single variable to store messages in transit, but -three signals are used to coordinate reader and writer processes. -\begin{lstlisting} -package scala.concurrent; - -class SyncChannel[a] { - private var data: a = _; - private var reading = false; - private var writing = false; - - def write(x: a) = synchronized { - while (writing) wait(); - data = x; - writing = true; - if (reading) notifyAll(); - else while (!reading) wait(); - } - - def read: a = synchronized { - while (reading) wait(); - reading = true; - while (!writing) wait(); - val x = data; - writing = false; - reading = false; - notifyAll(); - x - } -} -\end{lstlisting} - -\section{Workers} - -Here's an implementation of a {\em compute server} in Scala. The -server implements a \code{future} method which evaluates a given -expression in parallel with its caller. Unlike the implementation in -Section~\ref{sec:futures} the server computes futures only with a -predefined number of threads. A possible implementation of the server -could run each thread on a separate processor, and could hence avoid -the overhead inherent in context-switching several threads on a single -processor. - -\begin{lstlisting} -import scala.concurrent._, scala.concurrent.ops._; - -class ComputeServer(n: Int) { - - private trait Job { - type t; - def task: t; - def ret(x: t): Unit; - } - - private val openJobs = new Channel[Job](); - - private def processor(i: Int): Unit = { - while (true) { - val job = openJobs.read; - job.ret(job.task) - } - } - - def future[a](p: => a): () => a = { - val reply = new SyncVar[a](); - openJobs.write{ - new Job { - type t = a; - def task = p; - def ret(x: a) = reply.set(x); - } - } - () => reply.get - } - - spawn(replicate(0, n) { processor }) -} -\end{lstlisting} -Expressions to be computed (i.e. arguments -to calls of \code{future}) are written to the \code{openJobs} -channel. A {\em job} is an object with -\begin{itemize} -\item -An abstract type \code{t} which describes the result of the compute -job. -\item -A parameterless \code{task} method of type \code{t} which denotes -the expression to be computed. -\item -A \code{return} method which consumes the result once it is -computed. -\end{itemize} -The compute server creates $n$ \code{processor} processes as part of -its initialization. Every such process repeatedly consumes an open -job, evaluates the job's \code{task} method and passes the result on -to the job's -\code{return} method. The polymorphic \code{future} method creates -a new job where the \code{return} method is implemented by a guard -named \code{reply} and inserts this job into the set of open jobs by -calling the \code{isOpen} guard. It then waits until the corresponding -\code{reply} guard is called. - -The example demonstrates the use of abstract types. The abstract type -\code{t} keeps track of the result type of a job, which can vary -between different jobs. Without abstract types it would be impossible -to implement the same class to the user in a statically type-safe -way, without relying on dynamic type tests and type casts. - - -Here is some code which uses the compute server to evaluate -the expression \code{41 + 1}. -\begin{lstlisting} -object Test with Executable { - val server = new ComputeServer(1); - val f = server.future(41 + 1); - Console.println(f()) -} -\end{lstlisting} - -\section{Mailboxes} -\label{sec:mailbox} - -Mailboxes are high-level, flexible constructs for process -synchronization and communication. They allow sending and receiving of -messages. A {\em message} in this context is an arbitrary object. -There is a special message \code{TIMEOUT} which is used to signal a -time-out. -\begin{lstlisting} -case object TIMEOUT; -\end{lstlisting} -Mailboxes implement the following signature. -\begin{lstlisting} -class MailBox { - def send(msg: Any): unit; - def receive[a](f: PartialFunction[Any, a]): a; - def receiveWithin[a](msec: long)(f: PartialFunction[Any, a]): a; -} -\end{lstlisting} -The state of a mailbox consists of a multi-set of messages. -Messages are added to the mailbox the \code{send} method. Messages -are removed using the \code{receive} method, which is passed a message -processor \code{f} as argument, which is a partial function from -messages to some arbitrary result type. Typically, this function is -implemented as a pattern matching expression. The \code{receive} -method blocks until there is a message in the mailbox for which its -message processor is defined. The matching message is then removed -from the mailbox 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 mailboxes are used, consider a -one-place buffer: -\begin{lstlisting} -class OnePlaceBuffer { - private val m = new MailBox; // An internal mailbox - private case class Empty, Full(x: int); // Types of messages we deal with - m send Empty; // Initialization - def write(x: int): unit = - m receive { case Empty => m send Full(x) } - def read: int = - m receive { case Full(x) => m send Empty ; x } -} -\end{lstlisting} -Here's how the mailbox class can be implemented: -\begin{lstlisting} -class MailBox { - private abstract class Receiver extends Signal { - def isDefined(msg: Any): boolean; - var msg = null; - } -\end{lstlisting} -We define an internal class for receivers with a test method -\code{isDefined}, which indicates whether the receiver is -defined for a given message. The receiver inherits from class -\code{Signal} a \code{notify} method which is used to wake up a -receiver thread. When the receiver thread is woken up, the message it -needs to be applied to is stored in the \code{msg} variable of -\code{Receiver}. -\begin{lstlisting} - private val sent = new LinkedList[Any]; - private var lastSent = sent; - private val receivers = new LinkedList[Receiver]; - private var lastReceiver = receivers; -\end{lstlisting} -The mailbox class maintains two linked lists, -one for sent but unconsumed messages, the other for waiting receivers. -\begin{lstlisting} - def send(msg: Any): unit = synchronized { - var r = receivers, r1 = r.next; - while (r1 != null && !r1.elem.isDefined(msg)) { - r = r1; r1 = r1.next; - } - if (r1 != null) { - r.next = r1.next; r1.elem.msg = msg; r1.elem.notify; - } else { - lastSent = insert(lastSent, msg); - } - } -\end{lstlisting} -The \code{send} method first checks whether a waiting receiver is -applicable to the sent message. If yes, the receiver is notified. -Otherwise, the message is appended to the linked list of sent messages. -\begin{lstlisting} - def receive[a](f: PartialFunction[Any, a]): a = { - val msg: Any = synchronized { - var s = sent, s1 = s.next; - while (s1 != null && !f.isDefinedAt(s1.elem)) { - s = s1; s1 = s1.next - } - if (s1 != null) { - s.next = s1.next; s1.elem - } else { - val r = insert(lastReceiver, new Receiver { - def isDefined(msg: Any) = f.isDefinedAt(msg); - }); - lastReceiver = r; - r.elem.wait(); - r.elem.msg - } - } - f(msg) - } -\end{lstlisting} -The \code{receive} method first checks whether the message processor function -\code{f} can be applied to a message that has already been sent but that -was not yet consumed. If yes, the thread continues immediately by -applying \code{f} to the message. Otherwise, a new receiver is created -and linked into the \code{receivers} list, and the thread waits for a -notification on this receiver. Once the thread is woken up again, it -continues by applying \code{f} to the message that was stored in the -receiver. The insert method on linked lists is defined as follows. -\begin{lstlisting} - def insert(l: LinkedList[a], x: a): LinkedList[a] = { - l.next = new LinkedList[a]; - l.next.elem = x; - l.next.next = l.next; - l - } -\end{lstlisting} -The mailbox class also offers a method \code{receiveWithin} -which blocks for only a specified maximal amount of time. If no -message is received within the specified time interval (given in -milliseconds), the message processor argument $f$ will be unblocked -with the special \code{TIMEOUT} message. The implementation of -\code{receiveWithin} is quite similar to \code{receive}: -\begin{lstlisting} - def receiveWithin[a](msec: long)(f: PartialFunction[Any, a]): a = { - val msg: Any = synchronized { - var s = sent, s1 = s.next; - while (s1 != null && !f.isDefinedAt(s1.elem)) { - s = s1; s1 = s1.next ; - } - if (s1 != null) { - s.next = s1.next; s1.elem - } else { - val r = insert(lastReceiver, new Receiver { - def isDefined(msg: Any) = f.isDefinedAt(msg); - }); - lastReceiver = r; - r.elem.wait(msec); - if (r.elem.msg == null) r.elem.msg = TIMEOUT; - r.elem.msg - } - } - f(msg) - } -} // end MailBox -\end{lstlisting} -The only differences are the timed call to \code{wait}, and the -statement following it. - -\section{Actors} -\label{sec:actors} - -Chapter~\ref{chap:example-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 mailbox. Actors are -hence defined as a mixin composition extension of Java's standard -\code{Thread} class with the \code{MailBox} class. -\begin{lstlisting} -abstract class Actor extends Thread with MailBox; -\end{lstlisting} - -\comment{ -As an extended example of an application that uses actors, we come -back to the auction server example of Section~\ref{sec:ex-auction}. -The following code implements: - -\begin{figure}[thb] -\begin{lstlisting} -class AuctionMessage; -case class - Offer(bid: int, client: Process), // make a bid - Inquire(client: Process) extends AuctionMessage // inquire status - -class AuctionReply; -case class - Status(asked; int, expiration: Date), // asked sum, expiration date - BestOffer, // yours is the best offer - BeatenOffer(maxBid: int), // offer beaten by maxBid - AuctionConcluded(seller: Process, client: Process),// auction concluded - AuctionFailed // failed with no bids - AuctionOver extends AuctionReply // bidding is closed -\end{lstlisting} -\end{figure} - -\begin{lstlisting} -class Auction(seller: Process, minBid: int, closing: Date) - extends Process { - - val timeToShutdown = 36000000 // msec - val delta = 10 // bid increment -\end{lstlisting} -\begin{lstlisting} - override def run = { - var askedBid = minBid - var maxBidder: Process = null - while (true) { - receiveWithin ((closing - Date.currentDate).msec) { - case Offer(bid, client) => { - if (bid >= askedBid) { - if (maxBidder != null && maxBidder != client) { - maxBidder send BeatenOffer(bid) - } - maxBidder = client - askedBid = bid + delta - client send BestOffer - } else client send BeatenOffer(maxBid) - } -\end{lstlisting} -\begin{lstlisting} - case Inquire(client) => { - client send Status(askedBid, closing) - } -\end{lstlisting} -\begin{lstlisting} - case TIMEOUT => { - if (maxBidder != null) { - val reply = AuctionConcluded(seller, maxBidder) - maxBidder send reply - seller send reply - } else seller send AuctionFailed - receiveWithin (timeToShutdown) { - case Offer(_, client) => client send AuctionOver ; discardAndContinue - case _ => discardAndContinue - case TIMEOUT => stop - } - } -\end{lstlisting} -\begin{lstlisting} - case _ => discardAndContinue - } - } - } -\end{lstlisting} -\begin{lstlisting} - def houseKeeping: int = { - val Limit = 100 - var nWaiting: int = 0 - receiveWithin(0) { - case _ => - nWaiting = nWaiting + 1 - if (nWaiting > Limit) { - receiveWithin(0) { - case Offer(_, _) => continue - case TIMEOUT => - case _ => discardAndContinue - } - } else continue - case TIMEOUT => - } - } -} -\end{lstlisting} -\begin{lstlisting} -class Bidder (auction: Process, minBid: int, maxBid: int) - extends Process { - val MaxTries = 3 - val Unknown = -1 - - var nextBid = Unknown -\end{lstlisting} -\begin{lstlisting} - def getAuctionStatus = { - var nTries = 0 - while (nextBid == Unknown && nTries < MaxTries) { - auction send Inquiry(this) - nTries = nTries + 1 - receiveWithin(waitTime) { - case Status(bid, _) => bid match { - case None => nextBid = minBid - case Some(curBid) => nextBid = curBid + Delta - } - case TIMEOUT => - case _ => continue - } - } - status - } -\end{lstlisting} -\begin{lstlisting} - def bid: unit = { - if (nextBid < maxBid) { - auction send Offer(nextBid, this) - receive { - case BestOffer => - receive { - case BeatenOffer(bestBid) => - nextBid = bestBid + Delta - bid - case AuctionConcluded(seller, client) => - transferPayment(seller, nextBid) - case _ => continue - } - - case BeatenOffer(bestBid) => - nextBid = nextBid + Delta - bid - - case AuctionOver => - - case _ => continue - } - } - } -\end{lstlisting} -\begin{lstlisting} - override def run = { - getAuctionStatus - if (nextBid != Unknown) bid - } - - def transferPayment(seller: Process, amount: int) -} -\end{lstlisting} -} |