Preface
This chapter covers
The previous chapter introduced powerful methods and functions, but some shouldn’t be used in production because they can overflow the stack and crash the application (or at least the thread in which they’re called). These “dangerous” methods and functions are mainly explicitly recursive, but not always. You’ve seen that composing functions can also overflow the stack, and this can occur even with nonrecursive functions, although this isn’t common.
In this chapter, you’ll learn how to turn stack-based functions into heap-based functions. This is necessary because the stack is a limited memory area. For recursive functions to be safe, you have to implement them in such a way that they use the heap (the main memory area) instead of the limited stack space. To understand the problem completely, you must first understand the difference between recursion and corecursion.
Understanding corecursion and recursion
Corecursion is composing computing steps by using the output of one step as the input of the next one, starting with the first step. Recursion is the same operation, but starting with the last step. In recursion, you have to delay evaluation until you encounter a base condition (corresponding to the first step of corecursion). Let’s say you have only two instructions in your programming language: incrementation (adding 1 to a value) and decrementation (subtracting 1 from a value). As an example, you’ll implement addition by composing these instructions.
Exploring corecursive and recursive addition examples
To add two numbers, x and y, you can do the following:
This can be written in Java as follows:
Here’s a simpler approach:
There’s no problem with using the parameters x and y directly, because in Java, all parameters are passed by value. Also note that you use post-decrementation to simplify coding. You could have used pre-decrementation by slightly changing the condition, thus switching from iterating from y to 1, to iterating from y - 1 to 0:
The recursive version is trickier, but still simple:
Both approaches seem to work, but if you try the recursive version with big numbers, you may have a surprise. Although this version,
produces the expected result of 10,003, switching the parameters, like this,
produces a StackOverflowException.
Implementing recursion in Java
To understand what’s happening, you must look at how Java handles method calls. When a method is called, Java suspends what it’s currently doing and pushes the environment on the stack to make a place for executing the called method. When this method returns, Java pops the stack to restore the environment and resume program execution. If you call one method after another, the stack always holds at most one of these method call environments. But methods aren’t composed only by calling them one after the other. Methods call methods. If method1 calls method2 as part of its implementation, Java again suspends the method1 execution, pushes the current environment on the stack, and starts executing method2. When method2 returns, Java pops the last pushed environment from the stack and resumes execution (of method1 in this case). When method1 completes, Java again pops the last environment from the stack and resumes what it was doing before calling this method.
Method calls may be deeply nested, and this nesting depth does have a limit, which is the size of the stack. In current situations, the limit is somewhere around a few thousand levels, and it’s possible to increase this limit by configuring the stack size. But because the same stack size is used for all threads, increasing the stack size generally wastes space. The default stack size varies from 320 KB to 1024 KB, depending on the version of Java and the system used. For a 64-bit Java 8 program with minimal stack usage, the maximum number of nested method calls is about 7,000. Generally, you won’t need more, except in specific cases. One such case is recursive method calls.
Using tail call elimination
Pushing the environment on the stack is typically necessary in order to resume computation after the called method returns, but not always. When the call to a method is the last thing the calling method does, there’s nothing to resume when the method returns, so it should be OK to resume directly with the caller of the current method instead of the current method itself. A method call occurring in the last position, meaning it’s the last thing to do before returning, is called a tail call. Avoiding pushing the environment to the stack to resume method processing after a tail call is an optimization technique known as tail call elimination (TCE). Unfortunately, Java doesn’t use TCE.
Tail call elimination is sometimes called tail call optimization (TCO). TCE is generally an optimization, and you can live without it. But when it comes to recursive function calls, TCE is no longer an optimization. It’s a necessary feature. That’s why TCE is a better term than TCO when it comes to handling recursion.
Using tail recursive methods and functions
Most functional languages have TCE. But TCE isn’t enough to make every recursive call possible. To be a candidate for TCE, the recursive call must be the last thing the method has to do. Consider the following method, which is computing the sum of the elements of a list:
This method uses the head and tail methods from chapter 3. The recursive call to the sum method isn’t the last thing the method has to do. The four last things the method does are as follows:
Even if you had TCE, you wouldn’t be able to use this method with lists of 10,000 elements. But you can rewrite this method in order to put the call to sum in the tail position:
Here, the sumTail method is tail recursive and can be optimized through TCE.
Abstracting recursion
So far, so good, but why bother with all this if Java doesn’t have TCE? Well, Java doesn’t have it, but you can do without it. All you need to do is the following:
Most examples of recursive methods use the factorial function. Other examples use the Fibonacci series. The factorial method presents no particular interest beside being recursive. The Fibonacci series is more interesting, and we’ll come back to it later. To start with, you’ll use the much simpler recursive addition method shown at the beginning of this chapter.
Recursive and corecursive functions are both functions where f(n) is a composition of f(n - 1), f(n - 2), f(n - 3), and so on, until a terminal condition is encountered (generally f(0) or f(1)). Remember that in traditional programming, composing generally means composing the results of an evaluation. This means that composing function f(a) and g(a) consists of evaluating g(a) and then using the result as input to f. But it doesn’t have to be done that way. In chapter 2, you developed a compose method to compose functions, and a higherCompose function to do the same thing. Neither evaluated the composed functions. They only produced another function that could be applied later.
Recursion and corecursion are similar, but there’s a difference. You create a list of function calls instead of a list of functions. With corecursion, each step is terminal, so it may be evaluated in order to get the result and use it as input for the next step. With recursion, you start from the other end, so you have to put non-evaluated calls in the list until you find a terminal condition, from which you can process the list in reverse order. You stack the steps until the last one is found, and then you process the stack in reverse order (last in, first out), again evaluating each step and using the result as the input for the next (in fact, the previous) one.
The problem is that Java uses the thread stack for both recursion and corecursion, and its capacity is limited. Typically, the stack overflows after 6,000 to 7,000 steps. What you have to do is create a function or a method returning a non-evaluated step. To represent a step in the calculation, you’ll use an abstract class called TailCall (because you want to represent a call to a method that appears in the tail position).
This TailCall abstract class has two subclasses. One represents an intermediate call, when the processing of one step is suspended to call the method again for evaluating the next step. This is represented by a subclass named Suspend. It’s instantiated with Supplier> , which represents the next recursive call. This way, instead of putting all TailCalls in a list, you’ll construct a linked list by linking each tail call to the next. The benefit of this approach is that such a linked list is a stack, offering constant time insertion as well as constant time access to the last inserted element, which is optimal for a LIFO structure.
The second subclass represents the last call, which is supposed to return the result, so you’ll call it Return. It won’t hold a link to the next TailCall, because there’s nothing next, but it’ll hold the result. Here’s what you get:
To handle these classes, you’ll need some methods: one to return the result, one to return the next call, and one helper method to determine whether a TailCall is a Suspend or a Return. You could avoid this last method, but you’d have to use instanceof to do the job, which is ugly. The three methods are as follows:
The resume method has no implementation in Return and will throw a runtime exception. The user of your API shouldn’t be in a situation to call this method, so if it’s eventually called, it’ll be a bug and you’ll stop the application. In the Suspend class, this method will return the next TailCall. The eval method returns the result stored in the Return class. In the first version, it’ll throw a runtime exception if called on the Suspend class. The isSuspend method returns true in Suspend, and false in Return. The following listing shows this first version.
Listing 4.1. The TailCall interface and its two implementations
To make the recursive method add work with any number of steps (within the limits of available memory!), you have a few changes to make. Starting with your original method,
you need to make the modifications shown in the following listing.
Listing 4.2. The modified recursive method
This method returns a TailCall> , which is the next step of the computation in terms of execution sequence, or the previous in terms of calling sequence. It’s important to understand that Return corresponds to the last step in terms of the method call, but to the first step in terms of evaluation. Also note that we’ve slightly changed the evaluation, replacing ++x and --y with x + 1 and y – 1. This is necessary because we’re using a closure, which works only if closed-over variables are effectively final. This is cheating, but not too much. We could have created and called two methods, dec and inc, using the original operators. This method returns a chain of TailCall instances, all being Suspend instances except the last one, which is a Return.
So far, so good, but this method isn’t a drop-in replacement for the original one. Not a big deal! The original method was used as follows:
Doesn’t it look nice? If you feel frustrated, I understand. You thought you would just use a new method in place of the old one in a transparent manner. You seem to be far from this. But you can make things much better with a little effort.
Using a drop-in replacement for stack-based recursive methods
In the beginning of the previous section, I said that the user of your recursive API would have no opportunity to mess with the TailCall instances by calling resume on a Return or eval on a Suspend. This is easy to achieve by putting the evaluation code in the eval method of the Suspend class:
Now you can get the result of the recursive call in a much simpler and safer way:
But this isn’t what you want. You want to get rid of this call to the eval method. This can be done with a helper method:
Now you can call the add method exactly as the original one. You can make your recursive API easier to use by providing static factory methods to instantiate Return and Suspend, which also allows you to make the Return and Suspendinternal subclasses private:
Now that you have a stack-safe tail recursive method, can you do the same thing with a function?
Working with recursive functions
In theory, recursive functions shouldn’t be more difficult to create than methods, if functions are implemented as methods in an anonymous class. But lambdas aren’t implemented as methods in anonymous classes. The first problem is that, in theory, lambdas can’t be recursive. But this is theory. In fact, you learned a trick to work around this problem in chapter 2. A statically defined recursive add function looks like this:
Here, ContainingClass stands for the name of the class in which the function is defined. Or you may prefer an instance function instead of a static one:
But here, you have the same problem you had with the add method. You must call eval on the result. You could use the same trick, with a helper method alongside the recursive implementation. But you should make the whole thing self-contained. In other languages, such as Scala, you can define helper functions locally, inside the main function. Can you do the same in Java?
Using locally defined functions
Defining a function inside a function isn’t directly possible in Java. But a function written as a lambda is a class. Can you define a local function in that class? In fact, you can’t. You can’t use a static function, because a local class can’t have static members, and anyway, they have no name. Can you use an instance function? No, because you need a reference to this. And one of the differences between lambdas and anonymous classes is the this reference. Instead of referring to the anonymous class instance, the this reference used in a lambda refers to the enclosing instance. The solution is to declare a local class containing an instance function, as shown in the following listing.
Listing 4.4. A standalone tail recursive function
Making functions tail recursive
Previously, I said that a simple recursive functional method computing the sum of elements in a list couldn’t be handled safely because it isn’t tail recursive:
You saw that you had to transform the method as follows:
The principle is quite simple, although it’s sometimes tricky to apply. It consists of using an accumulator holding the result of the computation. This accumulator is added to the parameters of the method. Then the function is transformed into a helper method called by the original one with the initial value of the accumulator. It’s important to make this process nearly instinctive, because you’ll have to use it each time you want to write a recursive method or function.
It may be OK to change a method into two methods. After all, methods don’t travel, so you only have to make the main method public and the helper method (the one doing the job) private. The same is true for functions, because the call to the helper function by the main function is a closure. The main reason to prefer a locally defined helper function over a private helper method is to avoid name clashes.
A current practice in languages that allow locally defined functions is to call all helper functions with a single name, such as go or process. This can’t be done with nonlocal functions (unless you have only one function in each class). In the previous example, the helper function for sum was called sumTail. Another current practice is to call the helper function with the same name as the main function with an appended underscore, such as sum_. Whatever system you choose, it’s useful to be consistent. In the rest of this book, I’ll use the underscore to denote tail recursive helper functions.
Doubly recursive functions: the Fibonacci example
No book about recursive functions can avoid the Fibonacci series function. Although it’s totally useless to most of us, it’s ubiquitous and fun. Let’s start with the requirements, in case you’ve never met this function. The Fibonacci series is a suite of numbers, and each number is the sum of the two previous ones. This is a recursive definition. You need a terminal condition, so the full requirements are as follows:
This isn’t the original Fibonacci series, in which the first two numbers are equal to 1. Each number is supposed to be a function of its position in the series, and that position starts at 1. In computing, you generally prefer to start at 0. Anyway, this doesn’t change the problem. Why is this function so interesting? Instead of answering this question right now, let’s try a naive implementation:
Now let’s write a simple program to test this method:
If you run this test program, you’ll get the first 10 (or 9, according to the original definition) Fibonacci numbers:
Based on what you know about naive recursion in Java, you may think that this method will succeed in calculating f(n) for n, up to 6,000 to 7,000 before overflowing the stack. Well, let’s check it. Replace int n = 10 with int n = 6000 and see what happens. Launch the program and take a coffee break. When you return, you’ll realize that the program is still running. It will have reached somewhere around 1,836,311,903 (your mileage may vary—you could get a negative number!), but it’ll never finish. No stack overflow, no exception—just hanging in the wild. What’s happening?
The problem is that each call to the function creates two recursive calls. So to calculate f(n), you need 2n recursive calls. Let’s say your method needs 10 nanoseconds to execute. (Just guessing, but you’ll see soon that it doesn’t change anything.) Calculating f(5000) will take 25000 × 10 nanoseconds. Do you have any idea how long this is? This program will never terminate because it would need longer than the expected duration of the solar system (if not the universe!). To make a usable Fibonacci function, you have to change it to use a single tail recursive call. There’s also another problem: the results are so big that you’ll soon get an arithmetic overflow, resulting in negative numbers.
Let's Create a tail recursive version of the Fibonacci functional method (Exercise 4.1). The accumulator solution is the way to go. But there are two recursive calls, so you’ll need two accumulators. Let’s first write the signature of the helper method. It’ll take two BigInteger instances as accumulators, and one for the original argument, and it’ll return a BigInteger:
Eventually, you have to deal with recursion. You must do the following:
Here’s the transcription in code:
The last thing to do is to create the main method that calls this helper method with the initial values of the accumulators:
This is only one possible implementation. You may organize accumulators, initial values, and conditions in a slightly different manner, as long as it works. Now you can call fib(5000), and it’ll give you the result in a couple of nanoseconds. Well, it’ll take a few dozen milliseconds, but only because printing to the console is a slow operation. We’ll come back to this shortly. The result is impressive, whether it’s the result of the computation (1,045 digits!) or the increase in speed due to the transformation of a dual recursive call into a single one. But you still can’t use the method with values higher than 7,500.
Now let's Turn this method into a stack-safe recursive one (Exercise 4.2). This should be easy. The following code shows the needed changes:
You may now compute fib(10000) and count the digits in the result!
Making the list methods stack-safe and recursive
In the previous chapter, you developed functional methods to work on lists. Some of these methods were naively recursive, so they couldn’t be used in production. It’s time to fix this.
Let's create a stack-safe recursive version of the foldLeft method (Exercise 4.3). The naively recursive version of the foldLeft method was tail recursive:
Turning it into a fully recursive method is easy:
Let's Create a fully recursive version of the recursive range method (Exercise 4.4). Here should beware of the direction of list construction (append or prepend). The range method isn’t tail recursive:
You have to first create a tail recursive version, using an accumulator. Here, you need to return a list, so the accumulator will be a list, and you’ll start with an empty list. But you must build the list in reverse order:
Then you must turn this method into a main method and a helper method by using true recursion:
Let's Create a stack-safe recursive version of the foldRight method (Exercise 4.5). The stack-based recursive version of the foldRight method is as follows:
This method isn’t tail recursive, so let’s first create a tail recursive version. You might end up with this:
Unfortunately, this doesn’t work! Can you see why? If not, test this version and compare the result with the standard version. You can compare the two versions by using the test designed in the previous chapter:
You’ll get the following result:
This shows that the list is processed in reverse order. One easy solution is to reverse the list in the main method before calling the helper method. If you apply this trick while making the method stack-safe and recursive, you’ll get this:
In chapter 5, you’ll develop the process of reversing the list by implementing foldLeft in terms of foldRight, and foldRight in terms of foldLeft. But this shows that the recursive implementation of foldRight won’t be optimal because reverse is an O(n) operation: the time needed to execute it is proportional to the number of elements in the list, because you must traverse the list. By using reverse, you double this time by traversing the list twice. The conclusion is that when considering using fold-Right, you should do one of the following:
This chapter covers
The previous chapter introduced powerful methods and functions, but some shouldn’t be used in production because they can overflow the stack and crash the application (or at least the thread in which they’re called). These “dangerous” methods and functions are mainly explicitly recursive, but not always. You’ve seen that composing functions can also overflow the stack, and this can occur even with nonrecursive functions, although this isn’t common.
In this chapter, you’ll learn how to turn stack-based functions into heap-based functions. This is necessary because the stack is a limited memory area. For recursive functions to be safe, you have to implement them in such a way that they use the heap (the main memory area) instead of the limited stack space. To understand the problem completely, you must first understand the difference between recursion and corecursion.
Understanding corecursion and recursion
Corecursion is composing computing steps by using the output of one step as the input of the next one, starting with the first step. Recursion is the same operation, but starting with the last step. In recursion, you have to delay evaluation until you encounter a base condition (corresponding to the first step of corecursion). Let’s say you have only two instructions in your programming language: incrementation (adding 1 to a value) and decrementation (subtracting 1 from a value). As an example, you’ll implement addition by composing these instructions.
Exploring corecursive and recursive addition examples
To add two numbers, x and y, you can do the following:
This can be written in Java as follows:
- static int add(int x, int y) {
- while(y > 0) {
- x = ++x;
- y = --y;
- }
- return x;
- }
- static int add(int x, int y) {
- while(y-- > 0) {
- x = ++x;
- }
- return x;
- }
- static int add(int x, int y) {
- while(--y >= 0) {
- x = ++x;
- }
- return x;
- }
- static int addRec(int x, int y) {
- return y == 0
- ? x
- : addRec(++x, --y);
- }
- addRec(10000, 3);
- addRec(3, 10000);
Implementing recursion in Java
To understand what’s happening, you must look at how Java handles method calls. When a method is called, Java suspends what it’s currently doing and pushes the environment on the stack to make a place for executing the called method. When this method returns, Java pops the stack to restore the environment and resume program execution. If you call one method after another, the stack always holds at most one of these method call environments. But methods aren’t composed only by calling them one after the other. Methods call methods. If method1 calls method2 as part of its implementation, Java again suspends the method1 execution, pushes the current environment on the stack, and starts executing method2. When method2 returns, Java pops the last pushed environment from the stack and resumes execution (of method1 in this case). When method1 completes, Java again pops the last environment from the stack and resumes what it was doing before calling this method.
Method calls may be deeply nested, and this nesting depth does have a limit, which is the size of the stack. In current situations, the limit is somewhere around a few thousand levels, and it’s possible to increase this limit by configuring the stack size. But because the same stack size is used for all threads, increasing the stack size generally wastes space. The default stack size varies from 320 KB to 1024 KB, depending on the version of Java and the system used. For a 64-bit Java 8 program with minimal stack usage, the maximum number of nested method calls is about 7,000. Generally, you won’t need more, except in specific cases. One such case is recursive method calls.
Using tail call elimination
Pushing the environment on the stack is typically necessary in order to resume computation after the called method returns, but not always. When the call to a method is the last thing the calling method does, there’s nothing to resume when the method returns, so it should be OK to resume directly with the caller of the current method instead of the current method itself. A method call occurring in the last position, meaning it’s the last thing to do before returning, is called a tail call. Avoiding pushing the environment to the stack to resume method processing after a tail call is an optimization technique known as tail call elimination (TCE). Unfortunately, Java doesn’t use TCE.
Tail call elimination is sometimes called tail call optimization (TCO). TCE is generally an optimization, and you can live without it. But when it comes to recursive function calls, TCE is no longer an optimization. It’s a necessary feature. That’s why TCE is a better term than TCO when it comes to handling recursion.
Using tail recursive methods and functions
Most functional languages have TCE. But TCE isn’t enough to make every recursive call possible. To be a candidate for TCE, the recursive call must be the last thing the method has to do. Consider the following method, which is computing the sum of the elements of a list:
- static Integer sum(List
list) { - return list.isEmpty()
- ? 0
- : head(list) + sum(tail(list));
- }
Even if you had TCE, you wouldn’t be able to use this method with lists of 10,000 elements. But you can rewrite this method in order to put the call to sum in the tail position:
- static Integer sum(List
list) { - return sumTail(list, 0);
- }
- static Integer sumTail(List
list, int acc) { - return list.isEmpty()
- ? acc
- : sumTail(tail(list), acc + head(list));
- }
Abstracting recursion
So far, so good, but why bother with all this if Java doesn’t have TCE? Well, Java doesn’t have it, but you can do without it. All you need to do is the following:
Most examples of recursive methods use the factorial function. Other examples use the Fibonacci series. The factorial method presents no particular interest beside being recursive. The Fibonacci series is more interesting, and we’ll come back to it later. To start with, you’ll use the much simpler recursive addition method shown at the beginning of this chapter.
Recursive and corecursive functions are both functions where f(n) is a composition of f(n - 1), f(n - 2), f(n - 3), and so on, until a terminal condition is encountered (generally f(0) or f(1)). Remember that in traditional programming, composing generally means composing the results of an evaluation. This means that composing function f(a) and g(a) consists of evaluating g(a) and then using the result as input to f. But it doesn’t have to be done that way. In chapter 2, you developed a compose method to compose functions, and a higherCompose function to do the same thing. Neither evaluated the composed functions. They only produced another function that could be applied later.
Recursion and corecursion are similar, but there’s a difference. You create a list of function calls instead of a list of functions. With corecursion, each step is terminal, so it may be evaluated in order to get the result and use it as input for the next step. With recursion, you start from the other end, so you have to put non-evaluated calls in the list until you find a terminal condition, from which you can process the list in reverse order. You stack the steps until the last one is found, and then you process the stack in reverse order (last in, first out), again evaluating each step and using the result as the input for the next (in fact, the previous) one.
The problem is that Java uses the thread stack for both recursion and corecursion, and its capacity is limited. Typically, the stack overflows after 6,000 to 7,000 steps. What you have to do is create a function or a method returning a non-evaluated step. To represent a step in the calculation, you’ll use an abstract class called TailCall (because you want to represent a call to a method that appears in the tail position).
This TailCall abstract class has two subclasses. One represents an intermediate call, when the processing of one step is suspended to call the method again for evaluating the next step. This is represented by a subclass named Suspend. It’s instantiated with Supplier
The second subclass represents the last call, which is supposed to return the result, so you’ll call it Return. It won’t hold a link to the next TailCall, because there’s nothing next, but it’ll hold the result. Here’s what you get:
- package fp.utils;
- import fp.compose.ch3.Supplier;
- public abstract class TailCall
{ - public static class Return
{ - private final T t;
- public Return(T t) {
- this.t = t;
- }
- }
- public static class Suspend
{ - private final Supplier
> resume; - private Suspend(Supplier
> resume) { - this.resume = resume;
- }
- }
- }
- public abstract TailCall
resume(); - public abstract T eval();
- public abstract boolean isSuspend();
Listing 4.1. The TailCall interface and its two implementations
- package fp.utils;
- import fp.compose.ch3.Supplier;
- public abstract class TailCall
{ - public static class Return
{ - private final T t;
- public Return(T t) {
- this.t = t;
- }
- @Override
- public TailCall
resume() { - throw new IllegalStateException("Return has no resume");
- }
- @Override
- public T eval() {
- return t;
- }
- @Override
- public boolean isSuspend() {
- return false;
- }
- }
- public static class Suspend
{ - private final Supplier
> resume; - public Suspend(Supplier
> resume) { - this.resume = resume;
- }
- @Override
- public TailCall
resume() { - return resume.get();
- }
- @Override
- public T eval() {
- throw new IllegalStateException("Suspend has no value");
- }
- @Override
- public boolean isSuspend() {
- return true;
- }
- }
- public abstract TailCall
resume(); - public abstract T eval();
- public abstract boolean isSuspend();
- }
- static int add(int x, int y) {
- return y == 0
- ? x
- : add(++x, --y) ;
- }
Listing 4.2. The modified recursive method
- public static TailCall
add( int x, int y) // (1) - {
- return y==0
- ? new TailCall.Return<>(x) // (2)
- : new TailCall.Suspend<>(()->add(x + 1, y - 1)); // (3)
- }
So far, so good, but this method isn’t a drop-in replacement for the original one. Not a big deal! The original method was used as follows:
- package fp.ch4;
- import fp.utils.TailCall;
- public class TestP8_1 {
- public static TailCall
add( int x, int y) // (1) - {
- return y==0
- ? new TailCall.Return<>(x) // (2)
- : new TailCall.Suspend<>(()->add(x + 1, y - 1)); // (3)
- }
- public static void main(String args[])
- {
- TailCall
tailCall = add(3, 100000000); - while(tailCall.isSuspend()) {
- tailCall = tailCall.resume();
- }
- System.out.println(tailCall.eval());
- }
- }
Using a drop-in replacement for stack-based recursive methods
In the beginning of the previous section, I said that the user of your recursive API would have no opportunity to mess with the TailCall instances by calling resume on a Return or eval on a Suspend. This is easy to achieve by putting the evaluation code in the eval method of the Suspend class:
- @Override
- public T eval() {
- TailCall
tailRec = this; - while(tailRec.isSuspend()) {
- tailRec = tailRec.resume();
- }
- return tailRec.eval();
- }
- TailCall
tailCall = add( 3, 100000000); - System.out.println(tailCall.eval());
- package fp.ch4;
- import static fp.utils.TailCall.*;
- import fp.utils.TailCall;
- public class TestP8_2 {
- private static TailCall
addRec( int x, int y) { - return y == 0
- ? ret(x)
- : sus(() -> addRec(x + 1, y - 1));
- }
- public static int add(int x, int y) {
- return addRec(x, y).eval();
- }
- public static void main(String[] args) {
- assert(add(1, 1000) == 1001);
- }
- }
- public static
Return ret(T t) { - return new Return<>(t);
- }
- public static
Suspend sus(Supplier > s) { - return new Suspend<>(s);
- }
Working with recursive functions
In theory, recursive functions shouldn’t be more difficult to create than methods, if functions are implemented as methods in an anonymous class. But lambdas aren’t implemented as methods in anonymous classes. The first problem is that, in theory, lambdas can’t be recursive. But this is theory. In fact, you learned a trick to work around this problem in chapter 2. A statically defined recursive add function looks like this:
- static Function
>> add = - a -> b -> b == 0
- ? ret(a)
- : sus(() -> ContainingClass.add.apply(a + 1).apply(b - 1));
- Function
>> add = - a -> b -> b == 0
- ? ret(a)
- : sus(() -> this.add.apply(a + 1).apply(b - 1));
Using locally defined functions
Defining a function inside a function isn’t directly possible in Java. But a function written as a lambda is a class. Can you define a local function in that class? In fact, you can’t. You can’t use a static function, because a local class can’t have static members, and anyway, they have no name. Can you use an instance function? No, because you need a reference to this. And one of the differences between lambdas and anonymous classes is the this reference. Instead of referring to the anonymous class instance, the this reference used in a lambda refers to the enclosing instance. The solution is to declare a local class containing an instance function, as shown in the following listing.
Listing 4.4. A standalone tail recursive function
- package fp.ch4;
- import fp.utils.Function;
- import fp.utils.TailCall;
- import static fp.utils.TailCall.*;
- public class List4_4 {
- static Function
> add = x -> y -> { - class AddHelper{
- Function
>> addHelper = - a -> b -> b == 0
- ? ret(a)
- : sus(() -> this.addHelper.apply(a + 1).apply(b - 1));
- }
- return new AddHelper().addHelper.apply(x).apply(y).eval();
- };
- public static void main(String[] args) {
- assert(add.apply(3).apply(1000) == 1003);
- }
- }
Previously, I said that a simple recursive functional method computing the sum of elements in a list couldn’t be handled safely because it isn’t tail recursive:
- static Integer sum(List
list) { - return list.isEmpty()
- ? 0
- : head(list) + sum(tail(list));
- }
- static Integer sum(List
list) { - return sumTail(list, 0);
- }
- static Integer sumTail(List
list, int acc) { - return list.isEmpty()
- ? acc
- : sumTail(tail(list), acc + head(list));
- }
It may be OK to change a method into two methods. After all, methods don’t travel, so you only have to make the main method public and the helper method (the one doing the job) private. The same is true for functions, because the call to the helper function by the main function is a closure. The main reason to prefer a locally defined helper function over a private helper method is to avoid name clashes.
A current practice in languages that allow locally defined functions is to call all helper functions with a single name, such as go or process. This can’t be done with nonlocal functions (unless you have only one function in each class). In the previous example, the helper function for sum was called sumTail. Another current practice is to call the helper function with the same name as the main function with an appended underscore, such as sum_. Whatever system you choose, it’s useful to be consistent. In the rest of this book, I’ll use the underscore to denote tail recursive helper functions.
Doubly recursive functions: the Fibonacci example
No book about recursive functions can avoid the Fibonacci series function. Although it’s totally useless to most of us, it’s ubiquitous and fun. Let’s start with the requirements, in case you’ve never met this function. The Fibonacci series is a suite of numbers, and each number is the sum of the two previous ones. This is a recursive definition. You need a terminal condition, so the full requirements are as follows:
This isn’t the original Fibonacci series, in which the first two numbers are equal to 1. Each number is supposed to be a function of its position in the series, and that position starts at 1. In computing, you generally prefer to start at 0. Anyway, this doesn’t change the problem. Why is this function so interesting? Instead of answering this question right now, let’s try a naive implementation:
- public static int fibonacci(int number) {
- if (number == 0 || number == 1) {
- return number;
- }
- return fibonacci(number - 1) + fibonacci(number - 2);
- }
- public static void main(String args[]) {
- int n = 10;
- for(int i = 0; i <= n; i++){
- System.out.print(fibonacci(i) +" ");
- }
- }
Based on what you know about naive recursion in Java, you may think that this method will succeed in calculating f(n) for n, up to 6,000 to 7,000 before overflowing the stack. Well, let’s check it. Replace int n = 10 with int n = 6000 and see what happens. Launch the program and take a coffee break. When you return, you’ll realize that the program is still running. It will have reached somewhere around 1,836,311,903 (your mileage may vary—you could get a negative number!), but it’ll never finish. No stack overflow, no exception—just hanging in the wild. What’s happening?
The problem is that each call to the function creates two recursive calls. So to calculate f(n), you need 2n recursive calls. Let’s say your method needs 10 nanoseconds to execute. (Just guessing, but you’ll see soon that it doesn’t change anything.) Calculating f(5000) will take 25000 × 10 nanoseconds. Do you have any idea how long this is? This program will never terminate because it would need longer than the expected duration of the solar system (if not the universe!). To make a usable Fibonacci function, you have to change it to use a single tail recursive call. There’s also another problem: the results are so big that you’ll soon get an arithmetic overflow, resulting in negative numbers.
Let's Create a tail recursive version of the Fibonacci functional method (Exercise 4.1). The accumulator solution is the way to go. But there are two recursive calls, so you’ll need two accumulators. Let’s first write the signature of the helper method. It’ll take two BigInteger instances as accumulators, and one for the original argument, and it’ll return a BigInteger:
- private static BigInteger fib_(BigInteger acc1, BigInteger acc2, BigInteger x) {
- if (x.equals(BigInteger.ZERO)) {
- return BigInteger.ZERO;
- } else if (x.equals(BigInteger.ONE)) {
- return acc1.add(acc2);
- } else {
- ...
- }
- }
Here’s the transcription in code:
- private static BigInteger fib_(BigInteger acc1, BigInteger acc2, BigInteger x) {
- if (x.equals(BigInteger.ZERO)) {
- return BigInteger.ZERO;
- } else if (x.equals(BigInteger.ONE)) {
- return acc1.add(acc2);
- } else {
- return fib_(acc2, acc1.add(acc2), x.subtract(BigInteger.ONE));
- }
- }
- package fp.ch4;
- import java.math.BigInteger;
- import static fp.utils.CollectionUtilities.*;
- public class Sol4_1 {
- private static BigInteger fib_(BigInteger acc1, BigInteger acc2, BigInteger x) {
- if (x.equals(BigInteger.ZERO)) {
- return BigInteger.ZERO;
- } else if (x.equals(BigInteger.ONE)) {
- return acc1.add(acc2);
- } else {
- return fib_(acc2, acc1.add(acc2), x.subtract(BigInteger.ONE));
- }
- }
- public static BigInteger fib(int x) {
- return fib_(BigInteger.ONE, BigInteger.ZERO, BigInteger.valueOf(x));
- }
- public static void main(String argss[]) {
- for(int i:range(0,100))
- {
- System.out.printf("f(%d)=%d\n", i, fib(i));
- }
- }
- }
Now let's Turn this method into a stack-safe recursive one (Exercise 4.2). This should be easy. The following code shows the needed changes:
- package fp.ch4;
- import java.math.BigInteger;
- import fp.utils.TailCall;
- import static fp.utils.TailCall.*;
- import static fp.utils.CollectionUtilities.*;
- public class Sol4_2 {
- static TailCall
fib_(BigInteger acc1, BigInteger acc2, BigInteger x) { - if (x.equals(BigInteger.ZERO)) {
- return ret(BigInteger.ZERO);
- } else if (x.equals(BigInteger.ONE)) {
- return ret(acc1.add(acc2));
- } else {
- return sus(() -> fib_(acc2, acc1.add(acc2), x.subtract(BigInteger.ONE)));
- }
- }
- static BigInteger fib(int x) {
- return fib_(BigInteger.ONE, BigInteger.ZERO, BigInteger.valueOf(x)).eval();
- }
- public static void main(String args[])
- {
- for(int i:range(0, 10000))
- {
- System.out.printf("f(%d)=%d\n", i, fib(i));
- }
- }
- }
Making the list methods stack-safe and recursive
In the previous chapter, you developed functional methods to work on lists. Some of these methods were naively recursive, so they couldn’t be used in production. It’s time to fix this.
Let's create a stack-safe recursive version of the foldLeft method (Exercise 4.3). The naively recursive version of the foldLeft method was tail recursive:
- public static
U foldLeft(List ts, U identity, - Function> f) {
- return ts.isEmpty()
- ? identity
- : foldLeft(tail(ts), f.apply(identity).apply(head(ts)), f);
- }
- private static
TailCall foldLeft_(List ts, U identity, Function> f) { - return ts.isEmpty()
- ? ret(identity)
- : sus(() -> foldLeft_(tail(ts), f.apply(identity).apply(head(ts)), f));
- }
- public static
U foldLeft(List ts, U identity, Function> f) { - return foldLeft_(ts, identity, f).eval();
- }
- public static List
range(Integer start, Integer end) { - return end <= start
- ? list()
- : prepend(start, range(start + 1, end));
- }
- public static List<Integer> range(List<Integer> acc,
- Integer start, Integer end) {
- return end <= start
- ? acc
- : range(append(acc, start), start + 1, end);
- }
- private static TailCall<List<Integer>> range_(List<Integer> acc, Integer start, Integer end) {
- return end <= start
- ? ret(acc)
- : sus(() -> range_(append(acc, start), start + 1, end));
- }
- public static List<Integer> range(Integer start, Integer end) {
- return range_(list(), start, end).eval();
- }
- public static <T, U> U foldRight(List<T> ts, U identity,
- Function<T, Function<U, U>> f) {
- return ts.isEmpty()
- ? identity
- : f.apply(head(ts)).apply(foldRight(tail(ts), identity, f));
- }
- public static <T, U> U foldRight(U acc, List<T> ts, U identity,
- Function<T, Function<U, U>> f) {
- return ts.isEmpty()
- ? acc
- : foldRight(f.apply(head(ts)).apply(acc), tail(ts), identity, f);
- }
- public static String addIS(Integer i, String s) {
- return "(" + i + " + " + s + ")";
- }
- List<Integer> list = list(1, 2, 3, 4, 5);
- System.out.println(foldRight(list, "0", x -> y -> addIS(x, y)));
- System.out.println(foldRightTail("0", list, "0", x -> y -> addIS(x, y)));
This shows that the list is processed in reverse order. One easy solution is to reverse the list in the main method before calling the helper method. If you apply this trick while making the method stack-safe and recursive, you’ll get this:
- private static <T, U> TailCall<U> foldRight_(U acc, List<T> ts, Function<T, Function<U, U>> f) {
- return ts.isEmpty()
- ? ret(acc)
- : sus(() -> foldRight_(f.apply(head(ts)).apply(acc), tail(ts), f));
- }
- public static <T, U> U foldRight(List<T> ts, U identity, Function<T, Function<U, U>> f) {
- return foldRight_(identity, reverse(ts), f).eval();
- }
沒有留言:
張貼留言