Scala Tutorials Part #9 - Introduction to functional programming

Intro to Functional Programming in Scala

The functional programming paradigm is becoming pretty famous in the recent years due its elegance and performance characteristics.

This is part 9 of the scala tutorial series. Check here for the full series.

In the previous 8 parts of this series, I would not have touched the functional programming side of scala at all and that is because if you are new to this paradigm (which the majority of the world is) then the language, environment can be a little overwhelming to learn along with the completely new and difficult paradigm and that is the reason why I did not touch them in the beginning itself. Since we have covered the object oriented programming side to somewhat depth, it will be slightly easier to understand.

: This article has been translated to chinese by ChanZong Huang, you can check it out here

Index

• Taking a look at moore’s law in 2017
• What is a programming paradigm?
• Understanding the von-neumann programming style
• What’s wrong with von-neumann style
• Map reduce & Immutability
• Pure functions in scala
• Higher level abstractions & avoiding conceptualizing programs word by word

Taking a look at moore's law in 2017

Moore’s law is a projection that talks about the number of transistors in a circuit doubles every two years. It is quite recently that chip manufacturers such as Intel , AMD and many others realized that moore’s law can be respected by increasing core counts rather than focusing on single core clock speed.

The below graph shows the performance per core and how it scaled year on year.

Image Source : Wikipedia commons

We can see that the performance per core is kind of stalled at around 3 Ghz and has not seen the growth that was there previously.

Here is another graph which talks about the core counts increase in relation with the clock speed increase.

Data from Kunle Olukotun, Lance Hammond, Herb Sutter, Burton Smith, Chris Batten and Krste Asanovic

It is evident that moore’s law is now achieved by increasing number of cores rather than single core clock speed increase.

This hardware issue has become a software problem now and programs/operating systems must be inherently better at multi-core utilization.

How is this related to functional programming? The F.P paradigm gives programs the ability to solve this problem in the best way possible along with a host of other benefits. Read on to find out more.

What is a programming paradigm?

Quoting from wikipedia,

Programming paradigms are a way to classify programming languages according to the style of computer programming

It is different from design patterns which are necessarily higher level abstractions and mostly independent of the language.

A programming paradigm is built right into the language, just like C does not support classes/objects in the OOP sense and pointers are not supported by java.

There are hundreds of programming languages in the world and what is common to all of them is some kind of a paradigm associated with the language.

Java is object oriented, C is procedural although you can do procedural programming in Java, but it is largely focused on object oriented programming.

If you are not familiar with different paradigms then I would highly recommend that you take Stanford CS107 - Programming Paradigms, which gives you an excellent overview of the popular paradigms out there.

Understanding the von-neumann programming style

Imperative programming/Object oriented programming is based on something called Von Neumann architecture which is a computer architecture depicting various parts of a computer as below.

Image Source : Wikimedia commons

Today’s programming style has a strong correlation with the above architecture.

• Program variables Computer storage cells(Registers)

• Control statements Jump instructions

• Assignment statements Fetch/Store instructions

• Expressions Memory reference/Arithmetic instructions

If you have studied/programmed in assembly before, then the above instructions would be familiar to you. In any case if assembly/CPU/registers sound like greek and latin to you then perhaps a refresher on computer architecture would be of great help. The course goes very deep into architectures, but should give you a very good idea of what we are talking about.

Programs written in assembly or imperative languages are called as instruction sequences where they present step by step instructions for the computer to execute.

This concept has shaped programming languages like C/, C++, Java, C# to a great extent.

What's wrong with von-neumann style

So what is wrong with von neumann’s style and why do we need a new paradigm?

This is addressed in the classic research paper can programming be liberated from von-neumann style by John Backus

It is a little long for a research paper, but I highly recommend that you read it. Many of the concepts might not make sense to you now, but it will definitely make sense later.

Understanding what is wrong with von neumann style coding requires in-depth knowledge of functional programming so that we can compare and contrast them. In the following sections, we will take a look at several functional programming constructs/concepts which can help us understand.

Map reduce & Immutability

When the big data explosion happened, map reduce was at its core. Introduction to hadoop and map reduce is one good source to start learning hadoop and map reduce.

We are going to see a very small example of how map reduce works in Apache Spark. The syntax is not much important but the concepts behind it are.

Below is a simple working code snippet that does the famous word count problem.

val textFile = sc.textFile("hdfs://...")
val counts = textFile.flatMap(line => line.split(" "))
                 .map(word => (word, 1))
                 .reduceByKey(_ + _)
counts.saveAsTextFile("hdfs://...")

Map reduce comes in two phases, i.e the Map phase and the reduce phase.

For our understanding, let’s assume that below is the content on which we must perform word count i.e count how many times each word has occurred in a given dataset.

This is one of few movies that are truly timeless. And it's entertaining and moving, no matter how many times you view it.

The only other movie I have ever seen that effects me as strongly is To Kill a Mockingbird. Both movies leave me feeling cleaner for having watched them.

It is a simple film, yet it has an everlasting message.

When you give the above sentences as a text file input to the above code, it is going to give out the unique words in the set and how many times they appeared in the given set. For example the word movies appeared twice in the set.

Let’s understand the word count example one line at a time.

val textFile = sc.textFile("hdfs://...")

First we are reading a text file from HDFS. This text file contains contents similar to the example given above.

Then the syntax begins to get weird, I have specifically chosen the scala part of the code instead of java since it would be better to explain the concepts.

flatMap, map is part of the collections library in scala. I am not going to explain them in detail since they are extensive topics of their own, but rather focus on what they do.

Lets understand with the below example,

It is a simple film, yet it has an everlasting message.

Walking through the steps

For simplicity we assume that the input words are all converted to lower case before it is processed by the map reduce task.

• The output of the flatMap would be individual words it,is,a,simple ….
• map then takes the individual words then maps them into a key value pair (it,1),(is,1),(a,1) ….
• reduceByKey does what it is named after. It takes the words for example (it,1) and the next (it,1) and then combines them into (it,2).

Image Source : Wikipedia commons

The most important part of this entire process is that the input data once given cannot be changed i.e it is immutable and if the spark workers are configured correctly can easily scale to multiple cores or even multiple machines.

Immutable objects are thread safe considering that their content cannot be changed. Thread safety is directly related to parallelism and multi-core/multi-machine performance/scalability. If there are too many locks then they slow down the entire operation and if there are no locks then it will lead to wrong results.

To eliminate this, we need immutable programming concepts so that there is no thread safety needed. In scala immutability implies thread safety.

In other languages it may or may not mean the same. Case classes are classic examples of immutable objects/classes in scala. Except the creation part, they can be passed around multiple threads and wont cause any thread safety issues since the data cannot be changed.

We already saw in the case classes chapter that changing the values of a case class variable after creation leads to a compile time exception and they can be identified easily.

This is one of the reason why immutability is favoured in Scala as opposed to mutable programming constructs.

Pure functions in scala

The core of functional programming is pure functions. At first glance this is confusing since the questions “Aren’t methods the same as functions”. Turns out that they are not the same in scala.

Note : We will only briefly touch upon the notion of functions. There is lot more to it which will be explained in future articles.

In functional programming world, a pure function is one which has no side effects.i.e it is only dependant upon the input parameter and does not mutate state elsewhere.

A function is considered not pure if it does one or more of the following.

• Variable mutation in current function/class or in some other class
• Printing to console of anywhere else
• Saving data to a database

There are more benefits. At first thought, one would think that if I can’t do any of the above then how the heck can I write any code?

In functional languages there are monads to handle I/O, but that is an advanced concept which we will cover later. But keep in mind that scala is multi-paradigm, the programmer can choose which style depending upon the problem at hand.

The aim of FP is not to remove mutability but rather reduce them, so that it can have various performance benefits.

Let’s look at an example

val x = math.sin(10)

The sin function in the scala.math package can be considered as a pure function. Wait, this mutates the variable right? Actually no, this returns a new value and does not change the passed in value.

  val init = 10

  val x = math.sin(init)

  println(x)
  //init does not change
  println(init)

Java programmers might argue that for objects it is pass by reference and in that case would the function be impure? It could be, but the function is only taking in primitive types. This is slightly different in scala where there is only call by value and call by name (we will explore later)

Pure functions can be incredibly helpful, they have several advantages as below.

• No thread safety required since no mutability involved
• Reduces the cognitive load of your code . More on this in later tutorials.
• Since they don’t depend on any external resource, they provide excellent encapsulation i.e one need not understand what is happening underneath to use them.

Higher level abstractions & avoiding conceptualizing programs word by word

The key to tackling complexity is abstractions. This is the main concept that was described by the paper presented by John backus and not necessarily multi-threading and horizontal scaling. This has become famous recently because of moore’s law and single core processor performance seeing a limit.

We can take code from the map reduce example as a good example of abstraction.

  val x = List(10,20,30,40)

  val y = x.map( i => i* 3)

  println(y)

This is a map transformation which multiplies each element in the list by 3 and gives a new list.

With a traditional for loop this is a little tedious.

import scala.collection.mutable.ListBuffer

object Runnable extends App {

  val x = List(10,20,30,40)

  val mutable = new ListBuffer[Int]

  for (e <- x) {
    mutable += (e * 3)
  }

  println(mutable.toList)

}

Since List is an immutable data structure we need to introduce an additional mutable data structure called ListBuffer. This already breaks the immutability principle that we discussed before, also the functional version is a lot more cleaner.

Now the runtime can take this piece of code and perform lot of optimizations on it when compared to a for loop and the that’s the power of higher level constructs.

To summarize what we have seen so far in this article,

• We have seen why functional programming has become famous recently and the significance of moore’s law.
• Why immutability is important to thread safety and performance
• We saw the concept of pure functions and what are its advantages
• Higher level constructs and their importance

This is beginning of a very long but rewarding journey into the world of functional programming. There are many more core concepts to cover, but this post is focused on why this is a big deal.

Until next time