Learning Scala : Recursion and TCO 2

Authored by Win Myo Htet

In the previous post, we talk about the TCO. Now, we will do some TCO'ed recursion exercise. I have picked an example  from "Programming Interviews Exposed" on P.97. Here is the problem definition : "Implement a function that prints all possible combinations of the characters  in a string. These combinations range in length from one to the length of the string. Two combinations that differ only in ordering of their characters are the same combination. In other words, "ab" and "ca" are different combinations from their input string "abc". But "ba" is the same as "ab""

We want to write a tail call recursive code with accumulator, which will give us the final result, at the end of iteration. We have to remember that we don't want any computation on the way back in these recursive calls. We will accumulate the result along the way so that we don't have to do backtrack computing. Before we go on analyzing the code, let me disclose something first. In the past, when I started coding, I tried to implement this problem by myself without reading at the authors' analysis. I failed. :) I was quite frustrated with my attempts and didn't try it again until I have started learning recursion in Scala. I try again this time. Yay! I made it. ;) With these experience, I have understood the problem and answer well. I am able to do educated grouping to form some patterns.

Yet, I still need paper and pencil! Nothing can beat paper and pencil in this age of computing when it comes to do pattern analyzing scratches for the problem. Holding pencil in the right hand like a sword, while paper in the left hand like a shield, I march on! When I am implementing the simple recursion for this problem, I look at the two logically grouped tables in the book (I won't be drawing these tables here. Buy the book!) It helps me with my thinking and visualizing of the data grouping and the flow of the data in the code too. Now, I am trying to go through the data flow where I don't have to backtrack for computing, the following data flow emerge.

input: w x y z 
=======
result: w wx wxy wxyz wxz wy wyz wz x xy xyz xz y yz z 

mydata flow
-----------
w
x
  wx 
y
  wy  xy
          wxy
z
  wz  xz  
          wxz
               yz
                   wyz  xyz  
                             wxyz  

Authored by Win Myo Htet


First, we will have 'w', which we will carry it in our accumulator to the next iteration. Then, we have 'x'. We will keep the 'w'. We want to add 'x' and also our first combination of character 'wx' too. I would like to go over this again. We start with 'w'. Carry it over. Get a new character 'x', keep the 'w', add the new 'x' and add 'w' and 'x' combination. Carry all these over in the accumulator to the next iteration. We still want to keep whatever we have before and add a new 'y' and the new characters combinations of 'y' and the previous list. Now, you know what happens to Z. If you don't, well, read this whole paragraph recursively until you get it. ;)

So basically, we have the accumulator and add a new character to the accumulator and also add a new list which has the combination of the new character with the string in the accumulator. Cool!

import scala.annotation.tailrec
 final def tailReccursionEx(str : String) : List[String] = {

  @tailrec
  def doTailRecursionEx(str : String, pos : Int, accu : List[String]) : List[String] = {
   if (pos == str.length) return accu
   else {
    val newAccu = accu ++ accu.foldLeft(List[String](str(`pos`).toString)) {
     (l, ch) => l :+ ch + str(`pos`)
    }
    doTailRecursionEx(str, pos + 1, newAccu)
   }
  }

  doTailRecursionEx(str, 0, List[String]())
 }

To make life simpler, I have started foldLeft process with the List with the new character. You can get the complete source code here .

When you look at the complete source code from the provided git repo link. You will see the comparison of imperative, recursion and TCO'ed recursion. They all look comparable. Here is another FP recursion implementation from the book (the one after the above example). When I implement the regular recursion, I am able to write it out. However, I have to make considerable effort to get it TCO'ed. The TCO'ed code is more verbose than regular recursion and at the same time also suffer from the performance impact.

Why do we want TCO again? To prevent side effect. To prevent stack over flow. To prevent our precious application from crashing. Is TCO worth the time and energy? Do you have better tip and trick ? Please let me know. I get to this haskell thread when I start looking into recursion via Ackermann.  I was thinking of implementing it TCO'ed. Having read the thread and seeing the TCO destroy the beauty of recursion and the extent needed to go to achieve the TCO, I don't want to try anymore. Yup, these are the ugly sides of FP and recursion. It is the different side of the same coin. We need to have discussion going how to tackle these issue to get FP traction for wider use. Here is one of the methods called trampoline to address some TCO issue in Scala. It is still not easy to use. It is advanced stuff. Well, it's an option.

StackOverflow discussion on this.

Authored by Win Myo Htet

Learning Scala : Recursion and TCO 1

Authored by Win Myo Htet

fib=1:1[a+b|(a,b)<-zip fib(tail fib)]

My buddy texted me the above Haskell Fibonacci code, which uses  recursion, of course. Very neat, huh? We have also seen recursion making QuickSort self documenting  and gracefully simple. I have also used recursion in my Boyer-Moore search without making a conscious effort. Yes, recursion is at home in functional programming.

Recursion can make thing simple. Yet, simple is not easy! It takes recursively using recursion to master recursion. Ok, that's not a very good joke. But you get the point that you need to keep using recursion whenever possible to learn to think in recursion if you want to be the master in the land of functional programming. In Scala, you can get away with, without using recursion, then, you are not really in functional programming land. Assume that you have decided to start using recursion buying into my much lauded hype, well, let me raise the bar a bit then. With great power comes ... I mean, "With Recursion comes this nasty bug stack overflow."

Great... Well, all hope is not lost, sort of... The stack overflow happens because the function keeps calling itself thus putting itself on the stack memory again and again until it runs out of stack memory. The remedy to this is TCO (Tail Call Optimization). In TCO, we are using a particular pattern of recursion so that the compiler can optimize the code to avoid the stack overflow. Let's try lookat some code.

scala> List(1,2,3,4,5,6).foldLeft(10)(_ + _)
res0: Int = 31

Are we still talking about recursion? Yes, we are. I have mentioned in one of the blog before that foldLeft is preferred over foldRight. The reason being is that foldLeft is TCO'ed while foldRight is not. Here is a bit detail analysis of their process.

Here is the foldLeft sequence:
((((((10 + 1) + 2) + 3) + 4) + 5) + 6)
((((((11) + 2) + 3) + 4) + 5) + 6)
(((((13) + 3) + 4) + 5) + 6)
((((16) + 4) + 5) + 6)
(((20) + 5) + 6)
((25) + 6)
(31)

Here is the foldRight sequence:
(1 + (2 + (3 + (4 + (5 + (6 + 10))))))
(1 + (2 + (3 + (4 + (5 + (16))))))
(1 + (2 + (3 + (4 + (21)))))
(1 + (2 + (3 + (25))))
(1 + (2 + (28)))
(1 + (30))
(31)

In foldLeft, you can see that the result can be computed before the next iteration, while foldRight have to traverse all the way to the end, then compute and backtrack for more computing. Alright, how do we do that for our own Fibonacci code? Following the above foldLeft example, here is our Fibonacci code

object Fibonacci{

  def main(args:Array[String]):Unit={
    println(fibonacci(6))  
  }

  import scala.annotation.tailrec
  private def fibonacci(n:Int):Int={
  
    @tailrec
    def fibonacciTCO(n:Int,accu:Int):Int={
      if(n==1) return n+accu
      fibonacciTCO(n-1,n+accu)
    }
    
    fibonacciTCO(n,10)
  }  
}

Authored by Win Myo Htet

We have to include proper import above fibonacci and @tailrec annotation above fibonacciTCO. The fibonacci function has to be declared private or final so that the method cannot be overridden to undo the TCO. You also need to have accumulator (e.g. In our case accu) so that we can carry on our result and return  the final result at the last iteration without needing to backtrack all the way back. If you look carefully at the code, you will notice that, our (near ?) result(accu) is always in the same function scope and the stack reference to the previous call is not needed any more. Now, to make sure that our method is TCO'ed, we will look into the byte code of our compilation using javap with -c and -private option on the class file of Fibonacci$.class itself.

aunndroid@ubuntu:/host/Users/aunndroid/workspace/source_code$ javap -c -private Fibonacci\$
Compiled from "fibonacci.scala"
public final class Fibonacci$ extends java.lang.Object implements scala.ScalaObject{
public static final Fibonacci$ MODULE$;

public static {};
  Code:
   0: new #9; //class Fibonacci$
   3: invokespecial #12; //Method "":()V
   6: return

public void main(java.lang.String[]);
  Code:
   0: getstatic #19; //Field scala/Predef$.MODULE$:Lscala/Predef$;
   3: aload_0
   4: bipush 6
   6: invokespecial #24; //Method fibonacci:(I)I
   9: invokestatic #30; //Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
   12: invokevirtual #34; //Method scala/Predef$.println:(Ljava/lang/Object;)V
   15: return

private int fibonacci(int);
  Code:
   0: aload_0
   1: iload_1
   2: bipush 10
   4: invokespecial #42; //Method fibonacciTCO$1:(II)I
   7: ireturn

private final int fibonacciTCO$1(int, int);
  Code:
   0: iload_1
   1: iconst_1
   2: if_icmpne 9
   5: iload_1
   6: iload_2
   7: iadd
   8: ireturn
   9: iload_1
   10: iconst_1
   11: isub
   12: iload_1
   13: iload_2
   14: iadd
   15: istore_2
   16: istore_1
   17: goto 0

private Fibonacci$();
  Code:
   0: aload_0
   1: invokespecial #48; //Method java/lang/Object."":()V
   4: aload_0
   5: putstatic #50; //Field MODULE$:LFibonacci$;
   8: return

}

aunndroid@ubuntu:/host/Users/aunndroid/workspace/source_code$ 

Don't worry too much if you don't know anything here. Well, if you know everything and if you are the master of the Scala Universe, you might even not bother to read this, right ? ;) So, we find our TCO'ed fibonacciTCO$1, at line 30. At line 47, instead of re-referencing itself, we find this 17: goto 0. When you see that goto expression, you can be rest assured that your tail call recursion has been TCO'ed. The tail call recursion get optimized by scala compiler using goto. Compare to other functional languages, Scala has some restraints. Since Scala run on JVM and JVM does not support TCO(yet), Scala requires that tail call recursion must be self recursive tail call (e.g. fibonacciTCO must call fibonacciTCO).

Yup, that's quite a bit of info. I don't conceive these knowledge auto-magically. I am not the creator of Scala. I have read the blogs and books. So, I also recommend you to keep on reading about recursion and encourage you to blog about it too. Reading the same info from different narration will help you grasp the concept better. Here are the two I have read: Graham's blog and Nick's blog. They are also explaining the same info in their own way. As usual, we will be getting into some code in the next blog in this series.

Authored by Win Myo Htet