From Java to Scala: Tail Recursion


James O. Coplien, “To iterate is human, to recurse, divine.”

It’s been almost 20 years since I attended a functional programming course at university. It taught us how to divide a problem into sub problems, and sub- sub-problems until a base case was reached which solved not only the sub problem, but the problem as a whole. Then, in our first Java course, we learned recursion might produce the simplest solution, but each recursive call consumed more memory from the stack. Eventually, the memory would run out and the program would crash with a StackOverflowException. This is unfortunate as recursion is a key concept within functional programming. Luckily, Scala does a much better job with recursion than Java.

Why do we want to use recursion?

  • immutability Unlike a iterative approach recursion lets you write solutions to problems without changing the state of any variables. Instead, the calculation is performed as part of the next recursive call and immediately saved to a parameter.
  • readability A recursive solution will read like a list of the cases you need to handle, which, uncluttered by loop constructs, is easier to read and understand.

How do we solve a problem using recursion?

  1. Identify parameter and return type by looking at what we start with and what we want to produce.
  2. Identify the cases which we need to cover: error cases, base cases and recursion cases.
  3. Implement simplest case, usually the error case, first.
  4. Then, implement base cases.
  5. Finally, implement the recursion cases.

Let’s look at a simple user story to demonstrate the technique:
As a secret agent I want to reverse the text of my documents so that I can keep them secret.

  1. Our starting data is a String and the result is another String.
  2. Our only error case is a null starting value.
  3. Our base case is when we have no more characters to reverse.
  4. Our only recursion case is everything else.
def reverse(s: String): String = { // (1)
if (s == null) return null // (2)
if (s.tail.isEmpty) return s // (3)
reverse(s.tail) + s.head // (4)
}

Each time reverse calls itself a new frame is added to the stack as the result of reverse(s.tail) is needed before it can be added to s.head. If possible, we want to avoid this to make to protect us from a StackOverflowException. Head and tail is functional programming lingo for the first element and the remaining elements.

Enter Tail Recursion

A function can be called tail recursive when the last thing that happened was a call to itself, and no other recursive calls were made earlier. A clever compiler can then avoid adding a new frame to the stack, thus saving memory. Unlike Java, Scala has this capability.

Our simple reverse function can easily be converted into using tail recursion by adding a variable to track the result. We will also take advantage of the @tailrec annotation which tells the compiler to expect tail recursion and throw an error if that is not the case.

@scala.annotation.tailrec
def reverse_tail(s: String, r: String): String = {
if (s == null) return null
if (s.tail.isEmpty) return s.head + r
reverse_tail(s.tail, s.head + r)
}

Adding a second parameter is not really ideal, so lets take it a step further by defining a helper function inside reverse_tail to hide the second parameter.

def reverse_tail2(s: String): String = {
@scala.annotation.tailrec
def impl(ss: String, r: String): String = {
if (ss == null) return null
if (ss.tail.isEmpty) return ss.head + r
impl(ss.tail, ss.head + r)
}
impl(s, “”);
}

To a Java developer this will look weird, but in a functional language this is perfectly normal. Promise.

Next time: A closer look at some of the more common higher order functions used in functional programming.

Next Story — Gandalf: White Wizard, Code Reviewer
Currently Reading - Gandalf: White Wizard, Code Reviewer

Gandalf: White Wizard, Code Reviewer


Too many cooks spoil the broth.

Rare is the system with only one developer to support it. Managers will happily add bums to seats in a project to meet deadlines, fill a skill gap, or any other reason they can think of. The more the merrier you might say, and I won’t dispute that, but growing a team is not without consequences.

The problem is we are all unique individuals with different backgrounds, preferences and skill sets. Meaning, two developers might give two different solutions for the same problem. For just one problem this won’t matter, but as developers come and go over the years your code base will turn into a patchwork quilt of different coding styles, repeated code, and various re-inventions of the wheel.

Sounds familiar? Keep reading.

Code review, or peer review

A code review is simply the process where any written code is examined by the author’s colleagues before the code is allowed to be pushed into the repository. It’s a chance for the whole team to learn from mistakes, not point the finger of blame.

Pros and cons

Done right the only downside to code reviews is an upfront investment of time. Meaning, you spend time fixing problems before they actually turn into problems. The technical debt will grow at a reduced rate as a result. Yes, code reviewing will take time. Especially so for the more senior members of staff, but code reviewing is a skill and they will become faster and better given time.

There is a social benefit to it as well. When you know one, or more, of your colleagues will look at your code you also make sure you do your very best.

The pros are numerous:

  • consistency every problem has many solutions, and code reviewing is your best chance of making sure the there is only one wheel in your application.
  • readability by enforcing style guidelines and by refactoring overly complicated code your code base will be easier to understand and maintain in the long run.
  • training code reviewing is a great way to bring new developers up to speed on your code base, your coding standards, and industry best practices your organisation uses.

What about bugs?

This might come as a surprise, but the purpose of a code review is not to find bugs. Sure, bugs will be found, but most of them will be trivial. You do code reviews for the long term benefits, like maintainability, and it’s the job of your testing suite to prove the code works.

What do you need before you start?

  • tools Gerrit, Github, Crucible and Barkeep are all examples of code review suites.
  • style guidelines examples of how to write clean, readable code. Style guidelines are more about formatting than technical issues.
  • coding guidelines examples of how to write code adhering to your paradigm and language of choice. Joshua Bloch’s Effective Java is pretty much the industry standard for Java developers across the world.
  • dependencies list list of third party libraries which are allowed in the code base.
  • module specifics specifics for modules, for a web layer this could be related to security.

Process overview

  1. coder writes code with tests.
  2. coder submit for review.
  3. coder continues to work in another branch.
  4. reviewer reviews and submits feedback.
  5. coder updates his code, or asks reviewer to explain his/her comments if needed.
  6. goto 2 or submit if code is approved.

You will also need a list of approvers, those who can actually sign off a piece of code so it can be submitted. This could simply be your senior developers, or those with particular domain or technology expertise. It’s a good idea to test a person before you give them permission to approve code, to make sure they really know the ins and outs of your guides.

Code of conduct

You are not Gandalf.

Basically, don’t be a dick. Be constructive in your criticism and use examples to get your point across. Pay attention how you phrase your comments. It’s better to be humble and respectful than try and force your opinion on others. You are not Gandalf, and the other developers are not Balrogs, and must be allowed to pass. Eventually.

Speed is also important. Try and do the review as quickly as possible, and if you feel you do not have time reassign it to someone else.

Make sure to use examples to get your point across. It’s your chance to teach your colleagues to adhere to company guidelines and industry best practices.

Next Story — From Java to Scala: A Higher Order
Currently Reading - From Java to Scala: A Higher Order

From Java to Scala: A Higher Order


I have previously mentioned how functional programming lets you favour intent over step by step instructions, and now it’s time for a practical demonstration. Here are a few examples using some of the more common higher order functions used in functional programming and Scala when working with collections.

filter

def filter(p: (A) ⇒ Boolean): List[A]

It seems only natural to start with filter, after all, before we iterate over a collection we need to make sure it contains the right data. filter takes a single function as an argument, a predicate function. A predicate is a function which can be used to answer true/false questions on values of a certain type. A new collection is created containing each element which the predicate is true for.

Consider the following use case:
As a employee I want to know if it is the 25th day of the month so that I can know when I get paid.

// A payday predicate could be defined as:
def isPayday = (dayOfMonth: Int) => dayOfMonth == 25
//Now, given a List of all days of the month I would simply do:

val list = 22 to 28 toList
res0: List[Int] = List(22, 23, 24, 25, 26, 27, 28)
scala> list.filter(isPayday)
res1: List[Int] = List(25)
// Compare that to doing the same using Google’s Guava library:

public class IsPaydayPredicate implements Predicate<Integer> {
@Override
public boolean apply(Integer day) {
return 25 == day;
}
}

map

def map[B](f: (A) ⇒ B): List[B]

map applies a unary function on each element of a collection, and each result from that function is inserted into a new collection. That means if you call map on a collection with 5 elements the resulting collection will also contain 5 elements.

Consider the following use case:
As a loudmouth I want to use caps so that I can be heard.

val words = List(“can”, “you”, “hear”, “me?”)
scala> words.map((s: String) => s.toUpperCase)
res2: List[String] = List(CAN, YOU, HEAR, ME?)

flatten

def flatten[B]: List[B]

flatten collapses one level in a collection containing other collections, i.e. a List of Lists is turned into a List.

scala> val lists = List(List(1, 2, 3), List(4, 5, 6))
lists: List[List[Int]] = List(List(1, 2, 3), List(4, 5, 6))
scala> lists.flatten
res7: List[Int] = List(1, 2, 3, 4, 5, 6)

Could be used to transform input before it can be used by the consuming function when you have use case which covers the larger picture. Consider the following use case:

As a manager I want to see how much work we have planned across all projects so that I know if I have enough staff.

// Adds the points from all stories
def allPoints(stories: List[Story]): Int =
stories.foldLeft(0)(_ + _)

Notice how Scala lets you omit declaring the name of the parameters for the adding function, and how I could use a ‘_’ as a placeholder instead. We can do this as the type can be inferred and we don’t actually care about which parameter is which.

// Returns a List containing a List of Stories for each Project
def allStories(projects: List[Project]): List[List[Story]] =
projects.map((project) => project.stories)
// Flattens the List of Story Lists into a List of Stories
// before calling allPoints
val points = allPoints(allStories(projects).flatten)

flatMap

def flatMap[B](f: (A) ⇒ GenTraversableOnce[B]): List[B]

flatMap applies a function, which returns a collection, to each element of a collection and flattens the result into a new collection. Consider the following:

// Adds the points from all stories
def allPoints(stories: List[Story]): Int =
stories.foldLeft(0)(_ + _)
def allStories(projects: List[Project]): List[Story] =
projects.flatMap((project) => project.stories)
val points = allPoints(allStories(projects))

foldLeft

def foldLeft[B](z: B)(f: (B, A) => B): B

foldLeft is different from map as it takes a starting value and a binary function as parameters. For the first element in the collection the starting value is passed in as the first argument and the element itself as the second. For any remaining elements the result of the previous operation is used as the first argument. This means foldLeft produces a single result and not a new collection.

scala> val list = List(1, 2, 3)
list: List[Int] = List(1, 2, 3)
scala> list.foldLeft(0)((a, b) => a + b)
res3: Int = 6

This produces three calls the our adding function.
1. 0 + 1 // 0 is the starting value, and 1 is the 1st element.
2. 1 + 2 // 1 is the result of the previous operation, and 2 is the 2nd element.
3. 3 + 3 // 3 is the result of the previous operation, and 3 is the 3rd element.

Consider the use case with the secret agent from my tail recursion post:
As a secret agent I want to reverse the text of my documents so that I can keep them secret.

def reverseFoldLeft(s: String): String = 
s.foldLeft("")((a, b) => b + a)

// It can be shorted even further by using ```/:``` which is a // shortcut for foldLeft.

def reverseFoldLeft(s: String): String =
(""/:s)((a, b) => b + a)

foldRight

def foldRight[B](z: B)(op: ((A, B), B) ⇒ B): B

foldRight goes from right to left and swaps the order of the parameters to the binary function.

scala> val list = List(1, 2, 3)
list: List[Int] = List(1, 2, 3)
scala> list.foldRight(0)((a, b) => a + b)
res3: Int = 6

This produces three calls the our adding function.
1. 3 + 0 // 3 is the last element and 0 is the starting value.
2. 2 + 3 // 2 is the 2nd element and 3 is the result from the previous operation.
3. 1 + 5 // 1 is the 1st element and 5 is the result from the previous operation.

// Just like foldLeft there is a short hand version of 
// foldRight, :\.
def reverseFoldRight(s: String): String = 
(s:\"")((a, b) => b + a)

What’s next?

This post only scratches the very surface of higher order functions and collections, and I am sure there will be more posts with more advanced content. Especially map and flatMap have a lot of interesting use cases, which I will show you when I am brave enough to look at Monads.

Next post will compare classes in Java and Scala. Until then!

Next Story — From Java to Scala: A New Paradigm
Currently Reading - From Java to Scala: A New Paradigm

From Java to Scala: A New Paradigm


Ruby and Objective-C are the last two new programming languages I learned. Both are very different from my core language, Java, when it comes to style and syntax, but they are both imperative languages. This time I wanted something different. I wanted to learn a new way of thinking, a new paradigm.

A developer solves problems all day long, and sometimes all night. Usually, it is the developer with the most knowledge and context for a problem who will solve it the quickest, and produce the most elegant solution. In my last role, where we used both Java and Ruby, I picked up a few functional programming tricks, which required a lot less code than the imperative equivalent.

Functional programming is not a new paradigm, it’s been around since the 1930s, but it is not as popular as object oriented programming (OOP) and other derivatives of imperative programming. At least not from a commercial perspective, but this is all changing, and several ‘new’ functional languages have popped up lately.

I choose Scala, which supports both functional programming and OOP. This way, I can learn a new paradigm and a new language at the same time.

Why Scala?

If you want to learn a functional programming language there are a number of other options than Scala. Clojure, another member of the JVM family, has a fantastic community and immutability is built into the language. Haskell and Erlang are another two popular functional languages, but neither runs inside the JVM.

One of the key advantages offered by JVM membership is interoperability with Java. It means you can start using Scala in a legacy Java application without having to make any changes to the old code. New, leaner and more coherent modules can be written in Scala.

Scala supports both functional programming and OOP. To a purist functional programmer this might be a big no no, but for someone who wants to introduce a new paradigm into a organisation this is a big benefit. It will be easier to win over a sceptical team if you can drip feed them elegant and succinct solutions to problems using functional programming paradigms. Remember what I told you earlier about expanding your toolset to solve problems easier? If OOP offers a better solution to a problem, then use that, and vice versa. Scala makes all this possible.

Type-safety is to some a curse word, but it is hard to ignore the benefits it provides. For smaller applications it makes less of a difference, but when you are working on larger systems catching silly type errors at compile time saves a lot of time. Not to mention how much easier it makes refactoring when a type is known. Scala is of course statically typed.

From a commercial point of view Scala is now considered a ‘safe’ language to use. A number of large organisations have proven it can be used successfully to produce scalable solutions. As a programmer you learn a lot of things you never get a chance to use, but it is nice to know there is a glimmer of hope.

What is functional programming?

“Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data.”

Excerpt From: Nilanjan Raychaudhuri. “Scala in Action.”.

  • functions not objects, classes or procedures are the basic building blocks
  • higher order functions can accept another function as an argument and/or return a function.
  • pure functions only rely on their input to compute a result and have no memory or IO related side effects. Calling a pure function over and over again with the same arguments will produce the same result.
  • immutability once a value is assigned it cannot be reassigned, and to change the state of an object you have to create a new instance of it.

The above are a brief explanation of the fundamentals behind functional programming. Meaning, if not supported by a language it is not a functional programming language. Below, as a teaser for future articles, is a list of often supported features.

  • tail call optimisation
  • pattern matching
  • closures
  • list comprehensions
  • type inference
  • monads

Why do you need all that?

  • immutability is important for several reasons. First of all it ensures trust. Once created you know your object won’t change and you can safely let others use it. More importantly, an immutable object is thread-safe. Since its state cannot change it can be accessed by multiple threads without risk of dead locks or race conditions.
  • pure functions are easily testable as they are guaranteed to produce the same result when called with the same arguments. Trust, is again a factor as you know calling a pure function won’t have any side effects. They also promote separation of concerns, meaning a pure function only has one meaning. This makes them shorter, easier to understand and ideal building blocks.
  • higher order functions reduces the amount of boiler plate code a programmer has to write. A Java developer is guaranteed to notice the difference. The end result is more readable code which favours intent over step by step instructions. Steve Yegge’s Execution in the Kingdom of Nouns, is an insightful and funny article on the topic.

A Practical Demonstration

Let’s see how higher order functions reduces boiler plate code when creating a JButton with an ActionListener.

JButton pressMe = new JButton(“Press Me”); pressMe.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent event) {
System.out.println(“You pressed me!”);
}
});

If addActionListener was a higher order function which would accept another function as a parameter we could have in Scala written:

val pressMe = new JButton(“Press Me”)
pressMe.addActionListener(
(e:ActionEvent) => println(“You pressed me!”))

This could be reduced even further as Scala’s type-inference is clever enough to figure out the type for you.

(e) => println(“You pressed me!”)

The last example demonstrates how Scala is inherently less verbose than Java and how intent is favoured over needlessly detailing every step. Imagine a very simple e-commerce system with only two classes: Orders and Items. For the purpose of displaying the total cost of an order we can call totalCost.

First in Java:

public class Item { 
private int cost;
public Item(int cost) {
this.cost = cost;
}
public int getCost() {
return cost;
}
}
public class Order {
private List<Item> items;
public Order(List<Item> items) {
this.items = items;
}
public List<Item> getItems() {
return items;
}
public int totalCost() {
int totalCost = 0;
for (Item item : getItems()) {
totalCost += item.getCost();
}
return totalCost;
}
}

Then in Scala:

class Item(val cost: Int)
class Order(val items: List[Item]) {
def totalCost(): Int = items.map(e => e.cost).sum
}

What’s important here is instead of a for loop we use the map function, which applies the function supplied to each element in the list of items. The result is a list of costs, which is then added together by the sum function.

Stay tuned for more examples as I progress with Scala and functional programming.

Sign up to continue reading what matters most to you

Great stories deserve a great audience

Continue reading