This post presents some features of functional programming with Scala.
In essence, functional programming is about programming by making use of mathematical functions.

All well-known features of functional programming are just a result of using mathematical functions, e.g.:

• referential transparency
• immutable state
• higher-order functions
• pattern matching

I especially like ‘pattern matching’ as it allows for a direct translation of mathematical notation as shown below.

Obviously, no all languages are equally suited to deal with mathematical functions. My first experience with functional programming was during my time at “Uni” when we used to use Mathematica to solve mathematical problems. We also used Fortran but that was a completely different story!

Currently, Scala is popular for functional programming and that is my language of choice for this post.

 

Factorial function

Let’s consider the mathematical definition of the factorial function

This class Factorial.scala contains 3 different implementations of the factorial:

1. ‘tailRecursive’: in this implementation, the last line of the recursive function is a call to itself (what is called ‘tail recursion’) and the compiler can optimise it and convert the recursive calls into a loop.
2. ‘notTailRecursive’: in this case, the last line of the function is a multiplication and therefore no optimisation can be done (as all the frames on the stack resulting from the recursive calls need to be retained to complete calculations as functions return)
3. ‘factorial’: this is a non-tail recursive implementation too. The remarkable thing about this version is that the use of pattern matching allows to define the function very similarly to the actual mathematical definition.

To prove the optimisation made by the compiler, this class FactorialTest.scala invokes ‘tailRecursive’ and ‘notTailRecursive’ to calculate the factorial of 10,000. The test calling ‘tailRecursive’ completes successfully whereas the one calling ‘notTailRecursive’ throws an StackOverflowError.

Tail recursion

Let’s look a little further into tail recursion. As we just said, when the last statement of a recursive function is a call to itself, the Scala compiler can reuse the same frame over and over by turning the recursive call into a loop.

To see this feature in action, the function Recursion.scala contains 2 functions, ‘tailRecursive‘ and ‘notTailRecursive’. The body of both functions could not be simpler, it is just a call to itself. Therefore, both functions are tail recursive and candidates to be optimised by the compiler. However, only ‘tailRecursive‘ is optimised. The reason being becomes evident when using the annotation ‘@tailrec’, that is used to get information about which methods are optimised. The compiler complains

error: could not optimize @tailrec annotated method: it is neither private nor final so can be overridden

See http://stackoverflow.com/questions/4785502/why-wont-the-scala-compiler-apply-tail-call-optimization-unless-a-method-is-fin for a detailed description.

Now, inspecting the bytecode with the command

javap -v target/scala-2.11/classes/fjab/factorial/Recursion.class

we get the following:

public final void tailRecursive();                                              
    descriptor: ()V
    flags: ACC_PUBLIC, ACC_FINAL
    Code:
      stack=0, locals=1, args_size=1
         0: goto          0
      LocalVariableTable:
        Start  Length  Slot  Name   Signature
            0       3     0  this   Lfjab/factorial/Recursion;
      LineNumberTable:
        line 10: 0
      StackMapTable: number_of_entries = 1
        frame_type = 0 /* same */

public void notTailRecursive();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0
         1: invokevirtual #15                 // Method notTailRecursive:()V
         4: return
      LocalVariableTable:
        Start  Length  Slot  Name   Signature
            0       5     0  this   Lfjab/factorial/Recursion;
      LineNumberTable:
        line 11: 0

Clearly, the bytecode of the method ‘tailRecursive’ corresponds to a loop (an infinite loop in this case!) whereas ‘notTailRecursive’ invokes itself infinitely.