Файл: Programming_in_Scala,_2nd_edition.pdf

scala> speed(distance = 100, time = 10) res29: Float = 10.0

Called with named arguments, the arguments can be reversed without changing the meaning:

scala> speed(time = 10, distance = 100) res30: Float = 10.0

It is also possible to mix positional and named arguments. In that case, the positional arguments come first.

Named arguments are most frequently used in combination with default parameter values.

Default parameter values

Scala lets you specify default values for function parameters. The argument for such a parameter can optionally be omitted from a function call, in which case the corresponding argument will be filled in with the default.

An example is shown in Listing 8.3. Function printTime has one parameter, out, and it has a default value of Console.out.

def printTime(out: java.io.PrintStream = Console.out) = out.println("time = "+ System.currentTimeMillis())

Listing 8.3 · A parameter with a default value.

If you call the function as printTime(), thus specifying no argument to be used for out, then out will be set to its default value of Console.out. You could also call the function with an explicit output stream. For example, you could send logging to the standard error output by calling the function as printTime(Console.err).

Default parameters are especially helpful when used in combination with named parameters. In Listing 8.4, function printTime2 has two optional parameters. The out parameter has a default of Console.out, and the divisor parameter has a default value of 1.

Function printTime2 can be called as printTime2() to have both parameters filled in with their default values. Using named arguments, however, either one of the parameters can be specified while leaving the other as the default. To specify the output stream, call it like this:

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

def printTime2(out: java.io.PrintStream = Console.out, divisor: Int = 1) =

out.println("time = "+ System.currentTimeMillis()/divisor)

Listing 8.4 · A function with two parameters that have defaults.

printTime2(out = Console.err)

To specify the time divisor, call it like this:

printTime2(divisor = 1000)

8.9Tail recursion

In Section 7.2, we mentioned that to transform a while loop that updates vars into a more functional style that uses only vals, you may sometimes need to use recursion. Here’s an example of a recursive function that approximates a value by repeatedly improving a guess until it is good enough:

def approximate(guess: Double): Double = if (isGoodEnough(guess)) guess

else approximate(improve(guess))

A function like this is often used in search problems, with appropriate implementations for isGoodEnough and improve. If you want the approximate function to run faster, you might be tempted to write it with a while loop to try and speed it up, like this:

def approximateLoop(initialGuess: Double): Double = { var guess = initialGuess

while (!isGoodEnough(guess)) guess = improve(guess)

guess

}

Which of the two versions of approximate is preferable? In terms of brevity and var avoidance, the first, functional one wins. But is the imperative approach perhaps more efficient? In fact, if we measure execution times it turns

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

out that they are almost exactly the same! This might seem surprising, because a recursive call looks much more expensive than a simple jump from the end of a loop to its beginning.

However, in the case of approximate above, the Scala compiler is able to apply an important optimization. Note that the recursive call is the last thing that happens in the evaluation of function approximate’s body. Functions like approximate, which call themselves as their last action, are called tail recursive. The Scala compiler detects tail recursion and replaces it with a jump back to the beginning of the function, after updating the function parameters with the new values.

The moral is that you should not shy away from using recursive algorithms to solve your problem. Often, a recursive solution is more elegant and concise than a loop-based one. If the solution is tail recursive, there won’t be any runtime overhead to be paid.

Tracing tail-recursive functions

A tail-recursive function will not build a new stack frame for each call; all calls will execute in a single frame. This may surprise a programmer inspecting a stack trace of a program that failed. For example, this function calls itself some number of times then throws an exception:

def boom(x: Int): Int =

if (x == 0) throw new Exception("boom!") else boom(x - 1) + 1

This function is not tail recursive, because it performs an increment operation after the recursive call. You’ll get what you expect when you run it:

scala> boom(3) java.lang.Exception: boom!

at .boom(<console>:5) at .boom(<console>:6) at .boom(<console>:6) at .boom(<console>:6) at .<init>(<console>:6)

...

If you now modify boom so that it does become tail recursive:

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Tail call optimization

The compiled code for approximate is essentially the same as the compiled code for approximateLoop. Both functions compile down to the same thirteen instructions of Java bytecodes. If you look through the bytecodes generated by the Scala compiler for the tail recursive method, approximate, you’ll see that although both isGoodEnough and improve are invoked in the body of the method, approximate is not. The Scala compiler optimized away the recursive call:

public double approximate(double); Code:

0:aload_0

1:astore_3

2:aload_0

3:dload_1

10:dload_1

11:dreturn

12:aload_0

13:dload_1

def bang(x: Int): Int =

if (x == 0) throw new Exception("bang!") else bang(x - 1)

You’ll get:

scala> bang(5) java.lang.Exception: bang!

at .bang(<console>:5)

at .<init>(<console>:6) ...

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

This time, you see only a single stack frame for bang. You might think that bang crashed before it called itself, but this is not the case. If you think you might be confused by tail-call optimizations when looking at a stack trace, you can turn them off by giving the following argument to the scala shell or to the scalac compiler:

-g:notailcalls

With that option specified, you will get a longer stack trace:

scala> bang(5) java.lang.Exception: bang!

at .bang(<console>:5) at .bang(<console>:5) at .bang(<console>:5) at .bang(<console>:5) at .bang(<console>:5) at .bang(<console>:5)

at .<init>(<console>:6) ...

Limits of tail recursion

The use of tail recursion in Scala is fairly limited, because the JVM instruction set makes implementing more advanced forms of tail recursion very difficult. Scala only optimizes directly recursive calls back to the same function making the call. If the recursion is indirect, as in the following example of two mutually recursive functions, no optimization is possible:

You also won’t get a tail-call optimization if the final call goes to a function value. Consider for instance the following recursive code:

val funValue = nestedFun _ def nestedFun(x: Int) {

if (x != 0) { println(x); funValue(x - 1) }

}

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

The funValue variable refers to a function value that essentially wraps a call to nestedFun. When you apply the function value to an argument, it turns around and applies nestedFun to that same argument, and returns the result. You might hope, therefore, the Scala compiler would perform a tail-call optimization, but in this case it would not. Thus, tail-call optimization is limited to situations in which a method or nested function calls itself directly as its last operation, without going through a function value or some other intermediary. (If you don’t fully understand tail recursion yet, see Section 8.9).

8.10 Conclusion

This chapter has given you a grand tour of functions in Scala. In addition to methods, Scala provides local functions, function literals, and function values. In addition to normal function calls, Scala provides partially applied functions and functions with repeated parameters. When possible, function calls are implemented as optimized tail calls, and thus many nice-looking recursive functions run just as quickly as hand-optimized versions that use while loops. The next chapter will build on these foundations and show how Scala’s rich support for functions helps you abstract over control.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Chapter 9

Control Abstraction

In Chapter 7, we pointed out that Scala doesn’t have many built-in control abstractions, because it gives you the ability to create your own. In the previous chapter, you learned about function values. In this chapter, we’ll show you how to apply function values to create new control abstractions. Along the way, you’ll also learn about currying and by-name parameters.

9.1Reducing code duplication

All functions are separated into common parts, which are the same in every invocation of the function, and non-common parts, which may vary from one function invocation to the next. The common parts are in the body of the function, while the non-common parts must be supplied via arguments. When you use a function value as an argument, the non-common part of the algorithm is itself some other algorithm! At each invocation of such a function, you can pass in a different function value as an argument, and the invoked function will, at times of its choosing, invoke the passed function value. These higher-order functions—functions that take functions as parameters—give you extra opportunities to condense and simplify code.

One benefit of higher-order functions is they enable you to create control abstractions that allow you to reduce code duplication. For example, suppose you are writing a file browser, and you want to provide an API that allows users to search for files matching some criterion. First, you add a facility to search for files whose names end in a particular string. This would enable your users to find, for example, all files with a “.scala” extension. You could provide such an API by defining a public filesEnding method inside

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

a singleton object like this:

object FileMatcher {

private def filesHere = (new java.io.File(".")).listFiles

def filesEnding(query: String) =

for (file <- filesHere; if file.getName.endsWith(query)) yield file

}

The filesEnding method obtains the list of all files in the current directory using the private helper method filesHere, then filters them based on whether each file name ends with the user-specified query. Given filesHere is private, the filesEnding method is the only accessible method defined in FileMatcher, the API you provide to your users.

So far so good, and there is no repeated code yet. Later on, though, you decide to let people search based on any part of the file name. This is good for when your users cannot remember if they named a file phb-important.doc, stupid-phb-report.doc, may2003salesdoc.phb, or something entirely different, but they think that “phb” appears in the name somewhere. You go back to work and add this function to your FileMatcher API:

def filesContaining(query: String) =

for (file <- filesHere; if file.getName.contains(query)) yield file

This function works just like filesEnding. It searches filesHere, checks the name, and returns the file if the name matches. The only difference is that this function uses contains instead of endsWith.

The months go by, and the program becomes more successful. Eventually, you give in to the requests of a few power users who want to search based on regular expressions. These sloppy guys have immense directories with thousands of files, and they would like to do things like find all “pdf” files that have “oopsla” in the title somewhere. To support them, you write this function:

def filesRegex(query: String) =

for (file <- filesHere; if file.getName.matches(query)) yield file

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index