Geekcephale

/**
  * Scala developer @Ebiznext,
  * SNUG co-organizer.
  * Exalted about FP and maintaining
  * A list of great ressources !
  */
val me = SoftwareDeveloper(
  firstname = "Martin",
  name      = "Menestret",
  email     = "here",
  twitter   = "@mmenestret"
)

» Blog posts

» Talks

» FP learning resources

8 October 2018

Anatomy of functional programming

by Myself

I will try to group here, in an anatomy atlas, basic notions of functional programming that I find myself explaining often lately into a series of articles.

The idea here is to have a place to point people needing explanations and to increase my own understanding of these subjects by trying to explain them the best I can. I’ll try to focus more on making the reader feel an intuition, a feeling about the concepts rather than on the perfect, strict correctness of my explanations.

What is functional programming ?

A general definition

To begin our anatomy atlas of functional programming, the first question would be: what is functional programming ?

I would define it that way:

A style of programming which aims to avoid side effects by using, as much as possible, pure functions that manipulate immutable data.

As much as possible, here, means everywhere except, if needed, in your main function.

That way, almost your entire code base is said to be “pure” and has the nice properties we’ll see after.

Your main is the only “impure” part but you drastically reduced the portion of your code you have to be extra careful with.

The definition we gave for functional programming introduced the notions of side effects, pure functions and immutable data that we are going to explain.

A general purpose of functional programming would be to reduce, as much as possible, the moving parts of your software.

Side effects

A function should have only one effect: the effect of computing its return value.

Any other effects triggered by that function are side effects (logging, printing, inputs and outputs of any kinds, and so on).

Functional programming does not forbid to do IO or logging, but it encourages to do it explicitly rather than in secret, hidden in functions, without publicly declaring it.

Pure functions

Pure functions are somehow a computational analogy of mathematical function.

Purity rules

Pure functions have to respect a set of simple rules:

Now you can tell how functions that respect those rules limit the moving parts of your software.

They do what their signatures tell they do, and they only do that. They don’t move other stuff around.

How to do “real world” stuff then ?

You tell me that the one and only function effect should only be to allocate memory and to use some processor power to compute its result ? And nothing else ?

Without the ability to do IO, to encode randomness or to fail, it might be pretty hard to do any real world work…

Of course, functional programming lets you do all that but it asks you do to it explicitly.

Here are some examples:

Data philosophy

Data / behavior relationship

OOP and FP have two different approaches when it comes to data/behavior relationship:

case class Player(nickname: String, var level: Int) {
    def levelUp(): Unit          = { level = level + 1 }
    def sayHi(): String          = s"Hi, I'm player $nickname, I'm lvl $level !"
}

case class Player(nickname: String, level: Int)

object PlayerOperations {
    def levelUp(p: Player): Player = p.copy(level = p.level + 1)
    def sayHi(p: Player): String   = s"Hi, I'm player ${p.nickname}, I'm lvl ${p.level} !"
}

Expression problem

The expression problem is about how a language behaves when it comes to add to an existing code base:

And if they manage to do that without having to modify the existing code.

The idea behind the expression problem is to compare how languages and programming paradigms tackle these problems.

OOP and FP have both a different answer to that problem.

Object oriented programming paradigm

Base case:

trait MyType { def behavior: String }

final case class A() extends MyType { override def behavior: String = "I'm A" }
final case class B() extends MyType { override def behavior: String = "I'm B" }

Adding a new case to an existing data type:

final case class C() extends MyType { override def behavior: String = "I'm C" }

Adding a new behavior over an existing data type:

trait MyType { 
    def behavior: String
    def newBehavior: String
}

Now you have to get back to every single classes extending MyType to implement newBehavior.

Functional programming paradigm

Base case:

sealed trait MyType
final case class A() extends MyType
final case class B() extends MyType

def behavior(m: MyType): String = m match {
    case A() ⇒ "I'm A"
    case B() ⇒ "I'm B"
}

Adding a new case to an existing data type:

final case class C() extends MyType

Now you have to get back to every functions over MyType to pattern match on the new case.

Adding a new behavior over an existing data type:

def newBehavior(m: MyType): String = m match {
    case A() ⇒ ???
    case B() ⇒ ???
  }

Immutable Data

That one is simple: a value is said to be immutable if, once evaluated, there is no way to change it.

var meaningOfLife = 41
meaningOfLife = meaningOfLife + 1

val meaningOfLife = 42
meaningOfLife = meaningOfLife + 0
//<console>:12: error: reassignment to val
//       meaningOfLife = meaningOfLife + 0

If you really have to use mutability, say for performance reasons, I encourage you to do it with caution, by isolating and encapsulating the mutation in an immutable construct such as:

val magic = {
    var mutableMagic = 0
    mutableMagic = 42
    mutableMagic
}

That way you know that mutability won’t spread and your moving part is contained in a non moving one.

Benefits of FP

For now, what we saw about FP was more or less only constraints.

But functional programming shouldn’t be only seen a set of constraints, as Runar Bjarnason would say, constraints buy you a lot of freedom.

That may not seem obvious but I’ll try to explain why.

Equationnal reasoning

Pure functions, while being restrictive allow you to reason about your program in a way that would not be possible otherwise, it is called equational reasoning.

It means that, once you figure out that f(x) = something, then everywhere f(x) appears, you can simply replace it by something and keep reducing your problematic complexity thay way as far as you need.

Equationnal reasoning allows you to follow the logic of your program by replacing your function calls by their results, exactly how you’d do when trying to solve a mathematical equation:

That’s a powerful way to reason about complex problems.

Without pure functions, you would have to analyze every single function calls, check if those functions do anything more than returning their results, keep a mental track of that other things they do, and keep analyzing while trying not to forget what you just witnessed.

That’s a good example about how constraints on one side give you a lot of freedom on other sides.

Predictable data

As your data is immutable, it is easier to keep track of its state, since its state doesn’t change. The only way to create data is by using its constructor (in a broad sense) and that, also, reduces a lot your software’s moving parts.

You know for sure that, when using a piece of data, it has not been modified in the meantime by something else, you can rely on it.

If you isolate the places where changes occur by severely restricting mutation, you create a much smaller space for errors to occur and have fewer places to test. (Neal Ford)

Morever, it gives you thread safety by design, your data will never be in an unknown or undesirable state, which is huge in our more and more concurrent applications.

Playing with Lego

In addition to equational reasoning and immutability, I’ll try to show you what else FP brings to you your code with an analogy.

Do you remember how it was to play with Lego ? Well FP lets you play with functions the way you did with Lego pieces.

You had plenty of pieces that do or don’t fit together, each pieces being solid, immutable, and doing one single, simple thing.

Just as pure functions do.

It gives you:

Crystallizing design patterns

To end with FP benefits, there is this curious thing called Curry–Howard correspondence which is a direct analogy between mathematical concepts and computational calculus (which is what we do, programmers).

This correspondence means that a lot of useful stuff discovered and proven for decades in Math can then be transposed to programming, opening a way for a lot of extremely robust constructs for free.

In OOP, Design patterns are used a lot and could be defined as idiomatic ways to solve a given problems, in specific contexts but their existences won’t save you from having to apply and write them again and again each time you encounter the problems they solve.

Functional programming constructs, some directly coming from category theory (mathematics), solve directly what you would have tried to solve with design patterns.

The classical functional programming toolbox gives you constructs to handle, almost for free:

You can find here a list of how FP constructs corresponds to OOP classical design patterns: Lambda, the ultimate pattern factory.

Pretty convenient !

More material

If you want to keep diving deeper, some interesting stuff can be found on my FP resources list and in particular:

Conclusion

To sum up, we saw:

I’ll try to keep that blog post updated. If there are any additions, imprecision or mistakes that I should correct or if you need more explanations, feel free to contact me on Twitter or by mail !

tags: Scala - Functional programming