Trampoline Calls
Even though the TCO support in Scala is quite powerful, it’s limited. The compiler only detects direct recursions—that is, a function calling itself. If two functions call each other, known as a trampoline call, Scala doesn’t detect such recursion and performs no optimization.
Though the Scala compiler provides no support for trampoline calls, we can use the TailRec class to avoid stack overflow issues.
Let’s first take a look at an example with trampoline calls that will run into the stack overflow error for large input values.
| ProgrammingRecursions/words.scala | |
| | import scala.io.Source._ |
| | |
| | def explore(count: Int, words: List[String]) : Int = |
| | if(words.size == 0) |
| | count |
| | else |
| | countPalindrome(count, words) |
| | |
| | def countPalindrome(count: Int, words: List[String]) : Int = { |
| | val firstWord = words.head |
| | |
| | if(firstWord.reverse == firstWord) |
| | explore(count + 1, words.tail) |
| | else |
| | explore(count, words.tail) |
| | } |
| | |
| | def callExplore(text: String) = println(explore(0, text.split(" ").toList)) |
| | |
| | callExplore("dad mom and racecar") |
| | |
| | try { |
| | val text = |
| | fromURL("https://en.wikipedia.org/wiki/Gettysburg_Address").mkString |
| | callExplore(text) |
| | } catch { |
| | case ex : Throwable => println(ex) |
| | } |
The explore function takes a partial result count and a list of words as its parameters. If the list is empty, the function immediately returns the given count; otherwise, it calls the countPalindrome method. That method in turn checks if the first word in the list is a palindrome or not. If it is, it calls the explore method with an increased value of count. Otherwise, it calls the explore method with the value of count unaltered. In either case, it passes forward, to the explore function, the list with the first word removed.
The callExplore function takes a string of text, splits it into words separated by spaces, converts that array to a list, and forwards it to the explore function. It finally reports the result.
We call callExplore twice, first with a small string and then with a large piece of text we obtain from the web. Let’s take a look at the response from the execution of the code:
| | 3 |
| | java.lang.StackOverflowError |
For the short string, the code correctly identified the number of palindromes. However, for the longer text it ran into trouble.
Marking any of the functions in this example with @scala.annotation.tailrec won’t help—you’ll get an error that none of these functions are recursive. The Scala compiler doesn’t recognize recursion that spans across methods.
In cases like this where the recursion involves functions calling each other, we can use the TailRec class and the functions available in the scala.util.control.TailCalls package.
An instance of TailRec simply holds a function value (see Chapter 6, Function Values and Closures). The function result of TailRec is a simple iterator or a loop. It gets the inner function held in the TailRec and checks if it’s actually an instance of a subclass Call or Done. If an instance of Call is received, it signals continuation of the calls and the iteration continues to execute the inner function for further processing. If an instance of Done is received, it signals the termination of the iteration and the result held in the inner function is returned.
If you’d like to continue the recursion, use the tailcall function. To terminate the recursion, use the done function, which will in turn create an instance of Done. Let’s apply these ideas to the previous code example by refactoring it to use TailRec.
| ProgrammingRecursions/wordsTrampoline.scala | |
| | import scala.io.Source._ |
| | import scala.util.control.TailCalls._ |
| | |
| | def explore(count: Int, words: List[String]) : TailRec[Int] = |
| | if(words.size == 0) |
| | done(count) |
| | else |
| | tailcall(countPalindrome(count, words)) |
| | |
| | def countPalindrome(count: Int, words: List[String]) : TailRec[Int] = { |
| | val firstWord = words.head |
| | |
| | if(firstWord.reverse == firstWord) |
| | tailcall(explore(count + 1, words.tail)) |
| | else |
| | tailcall(explore(count, words.tail)) |
| | } |
| | |
| | def callExplore(text: String) = |
| | println(explore(0, text.split(" ").toList).result) |
| | |
| | callExplore("dad mom and racecar") |
| | |
| | try { |
| | val text = |
| | fromURL("https://en.wikipedia.org/wiki/Gettysburg_Address").mkString |
| | callExplore(text) |
| | } catch { |
| | case ex : Throwable => println(ex) |
| | } |
The explore method returns a TailRec instead of an Int. If the list is empty, it returns the result of a call to done with the desired result. To continue the recursion, it calls tailcall. Likewise, the countPalindrome continues the recursion by calling tailcall with the appropriate values.
The key idea to remember here is that both done or tailcall simply wrap their parameters into a function for later evaluation or lazy evaluation, and return immediately from the function. The actual decision to continue execution or to terminate is made within the result function, which is called on the result of the explore function. This critical step is carried out in the callExplore function.
Run this modified version and you can see that the code doesn’t suffer the stack overflow problem:
| | 3 |
| | 352 |
Although Scala does automatic optimization for calls that are tail recursive, it doesn’t provide direct compiler support for trampoline calls. But as you saw, we can easily avoid running into the stack overflow issue by using the facility provided in the Scala library.