From bbadab7e722fd89987f6df1bce6eb3ba9fa93ad0 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Tue, 20 Jan 2004 13:33:26 +0000 Subject: *** empty log message *** --- doc/reference/ExamplesPart.tex | 211 +++++++++++++++++------------------------ 1 file changed, 89 insertions(+), 122 deletions(-) (limited to 'doc/reference/ExamplesPart.tex') diff --git a/doc/reference/ExamplesPart.tex b/doc/reference/ExamplesPart.tex index 6c27ed38e1..5afdf486e6 100644 --- a/doc/reference/ExamplesPart.tex +++ b/doc/reference/ExamplesPart.tex @@ -7,31 +7,6 @@ \newcommand{\rewriteby}[1]{\mbox{\tab\tab\rm(#1)}} -\chapter{\label{chap:intro}Introduction} - -Scala is a programming language that fuses elements from -object-oriented and functional programming. We introduce here Scala in -an informal way, through a sequence of examples. - -Chapters~\ref{chap:example-one} and \ref{chap:example-auction} -highlight some of the features that make Scala interesting. The -following chapters introduce the language constructs of Scala in a -more thorough way, starting with simple expressions and functions, and -working up through objects and classes, lists and streams, mutable -state, pattern matching to more complete examples that show -interesting programming techniques. The present informal exposition is -meant to be complemented by the Java Language Reference Manual which -specifies Scala in a more detailed and precise way. - -\paragraph{Acknowledgment} -We owe a great debt to Abelson's and Sussman's wonderful book -``Structure and Interpretation of Computer -Programs''\cite{abelson-sussman:structure}. Many of their examples and -exercises are also present here. Of course, the working language has -in each case been changed from Scheme to Scala. Furthermore, the -examples make use of Scala's object-oriented constructs where -appropriate. - \chapter{\label{chap:example-one}A First Example} As a first example, here is an implementation of Quicksort in Scala. @@ -419,14 +394,14 @@ def scale: int 35: scala.Int \end{lstlisting} \begin{lstlisting} -> def pi = 3.14159 +> def pi = 3.141592653589793 def pi: scala.Double > def radius = 10 def radius: scala.Int > 2 * pi * radius -62.8318: scala.Double +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 @@ -459,10 +434,10 @@ or a list. Here is an evaluation of an arithmetic expression. \begin{lstlisting} $\,\,\,$ (2 * pi) * radius -$\rightarrow$ (2 * 3.14159) * radius -$\rightarrow$ 6.28318 * radius -$\rightarrow$ 6.28318 * 10 -$\rightarrow$ 62.8318 +$\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}. @@ -472,19 +447,22 @@ called {\em reduction}. Using \code{def}, one can also define functions with parameters. Example: \begin{lstlisting} > def square(x: double) = x * x -def square(x: double): scala.Double +def (x: double): scala.Double > square(2) 4.0: scala.Double -> square(5 + 4) -81.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(x: scala.Double, y: scala.Double): scala.Double +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 @@ -834,92 +812,90 @@ As a motivating example, consider the following three related tasks: \item Write a function to sum all integers between two given numbers \code{a} and \code{b}: \begin{lstlisting} -def sumInts(a: int, b: int): double = +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 cubes of all integers between two given numbers +Write a function to sum the squares of all integers between two given numbers \code{a} and \code{b}: \begin{lstlisting} -def cube(x: int): double = x * x * x -def sumCubes(a: int, b: int): double = - if (a > b) 0 else cube(a) + sumSqrts(a + 1, b) +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 reciprocals of all integers between two given numbers -\code{a} and \code{b}: +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 sumReciprocals(a: int, b: int): double = - if (a > b) 0 else 1.0 / a + sumReciprocals(a + 1, b) +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(x) + 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 => double, a: int, b: int): double = +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 => double} is the type of functions that +The type \code{int => int} is the type of functions that take arguments of type \code{int} and return results of type -\code{double}. So \code{sum} is a function which takes another function as +\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): double = sum(id, a, b); -def sumCubes(a: int, b: int): double = sum(cube, a, b); -def sumReciprocals(a: int, b: int): double = sum(reciprocal, a, b); +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): double = x; -def cube(x: int): double = x * x * x; -def reciprocal(x: int): double = 1.0/x; +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{cube} and -\code{reciprocal} as separate functions, so that they could be +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 reciprocal function: +example consider the anonymous square function: \begin{lstlisting} - x: int => 1.0/x + 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: double, y: double) => x * y + (x: int, y: int) => x * y \end{lstlisting} -Using anonymous functions, we can reformulate the three summation +Using anonymous functions, we can reformulate the first two summation functions without named auxiliary functions: \begin{lstlisting} -def sumInts(a: int, b: int): double = sum(x: int => x, a, b); -def sumCubes(a: int, b: int): double = sum(x: int => x * x * x, a, b); -def sumReciprocals(a: int, b: int): double = sum(x: int => 1.0/x, a, b); +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}, \code{sumCubes} and -\code{sumReciprocals}, one knows from the type of -\code{sum} that the first parameter must be a function of type -\code{int => double}. Hence, the parameter type \code{int} is -redundant and may be omitted: +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): double = sum(x => x, a, b); -def sumCubes(a: int, b: int): double = sum(x => x * x * x, a, b); -def sumReciprocals(a: int, b: int): double = sum(x => 1.0/x, a, b); +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 @@ -942,7 +918,7 @@ We also say, anonymous functions are ``syntactic sugar''. \section{Currying} -The latest formulation of the three summing function is already quite +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 @@ -951,8 +927,8 @@ there a way to get rid of them? Let's try to rewrite \code{sum} so that it does not take the bounds \code{a} and \code{b} as parameters: \begin{lstlisting} -def sum(f: int => double) = { - def sumF(a: int, b: int): double = +def sum(f: int => int) = { + def sumF(a: int, b: int): int = if (a > b) 0 else f(a) + sumF(a + 1, b); sumF } @@ -966,26 +942,26 @@ integers between them, and sums up the results. Using this new formulation of \code{sum}, we can now define: \begin{lstlisting} def sumInts = sum(x => x); -def sumCubes = sum(x => x * x * x); -def sumReciprocals = sum(x => 1.0/x); +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 sumCubes = sum(x => x * x * x); -val sumReciprocals = sum(x => 1.0/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} -> sumCubes(1, 10) + sumReciprocals(10, 20) -3025.7687714031754: scala.Double +> 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 * x)(1, 10) , +sum(x => x * x)(1, 10) , \end{lstlisting} -the function \code{sum} is applied to the cubing function -\code{(x => x * x * x)}. The resulting function is then +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. @@ -993,15 +969,15 @@ That is, if $\mbox{args}_1$ and $\mbox{args}_2$ are argument lists, then \bda{lcl} f(\mbox{args}_1)(\mbox{args}_2) & \ \ \mbox{is equivalent to}\ \ & (f(\mbox{args}_1))(\mbox{args}_2) \eda -In our example, \code{sum(x => x * x * x)(1, 10)} is equivalent to the +In our example, \code{sum(x => x * x)(1, 10)} is equivalent to the following expression: -\code{(sum(x => x * x * x))(1, 10)}. +\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 => double)(a: int, b: int): double = +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 @@ -1035,7 +1011,7 @@ Sch\"onfinkel and Gottlob Frege. The type of a function-returning function is expressed analogously to its parameter list. Taking the last formulation of \code{sum} as an example, -the type of \code{sum} is \code{(int => double) => (int, int) => double}. +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$) @@ -1109,9 +1085,9 @@ This suggests that \code{sqrt(x)} can be computed by fixed point iteration: \begin{lstlisting} def sqrt(x: double) = fixedPoint(y => x / y)(1.0) \end{lstlisting} -Unfortunately, this does not converge. Let's instrument the fixed point -function with a print statement which keeps track of the current -\code{guess} value: +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 = { @@ -1155,7 +1131,7 @@ very useful. Consider again fixed point iterations. We started with the observation that $\sqrt(x)$ is a fixed point of the function \code{y => x / y}. Then we made the iteration converge by averaging successive values. -This technique of {\em average dampening} is so general that it +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 @@ -6104,38 +6080,31 @@ how they can be implemented in Scala. \example The {\em monitor} provides the basic means for mutual exclusion -of processes in Scala. It is defined as follows. -\begin{lstlisting} -trait Monitor { - def synchronized [a] (def e: a): a; - def await(def cond: boolean) = while (false == cond) { wait() } -} -\end{lstlisting} -The \code{synchronized} method in class \code{Monitor} executes its -argument computation \code{e} in mutual exclusive mode -- at any one -time, only one thread can execute a \code{synchronized} argument of a -given monitor. - -Threads can suspend inside a monitor by waiting on a signal. The -standard \code{java.lang.Object} class offers for this purpose methods -\code{send} and \code{notify}. 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. -Here are the signatures of these methods in class -\code{java.lang.Object}. +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] (def e: a): a; def wait(): unit; def wait(msec: long): unit; def notify(): unit; def notifyAll(): unit; \end{lstlisting} +\begin{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. +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 @@ -6149,8 +6118,6 @@ correct form of waiting for a condition $C$ uses a while loop: \begin{lstlisting} while (!$C$) wait(); \end{lstlisting} -The monitor class contains a method \code{await} which does the same -thing; using it, the above loop can be expressed as \lstinline@await($C$)@. As an example of how monitors are used, here is is an implementation of a bounded buffer class. @@ -6160,13 +6127,13 @@ class BoundedBuffer[a](N: Int) extends Monitor() { val elems = new Array[a](N); def put(x: a) = synchronized { - await (n < N); + while (n >= N) wait(); elems(in) = x ; in = (in + 1) % N ; n = n + 1; if (n == 1) notifyAll(); } def get: a = synchronized { - await (n != 0); + while (n == 0) wait(); val x = elems(out) ; out = (out + 1) % N ; n = n - 1; if (n == N - 1) notifyAll(); x @@ -6459,17 +6426,17 @@ class SyncChannel[a] with Monitor { private var writing = false; def write(x: a) = synchronized { - await(!writing); + while (writing) wait(); data = x; writing = true; if (reading) notifyAll(); - else await(reading) + else while (!reading) wait(); } def read: a = synchronized { - await(!reading); + while (reading) wait(); reading = true; - await(writing); + while (!writing) wait(); val x = data; writing = false; reading = false; @@ -6615,7 +6582,7 @@ class OnePlaceBuffer { \end{lstlisting} Here's how the mailbox class can be implemented: \begin{lstlisting} -class MailBox with Monitor { +class MailBox { private abstract class Receiver extends Signal { def isDefined(msg: Any): boolean; var msg = null; -- cgit v1.2.3