Anatomy of functional programming
Tags: scala, functional
Published: 2019-02-21 10:05:48

---
title: "Anatomy of functional programming"
published: true
description: "What is functional programming ?"
tags: [Scala, fp, functional]
canonical_url: "http://geekocephale.com/blog/2018/10/08/fp"
series: "Functional programming atlas"
---

[Check my articles on my blog [here](http://geekocephale.com/blog/)]

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.

- Part 1: [Anatomy of functional programming](https://dev.to/mmenestret/anatomy-of-functional-programming-1bpg)
- Part 2: [Anatomy of an algebra](https://dev.to/mmenestret/anatomy-of-an-algebra-3cd9)
- Part 3: [Anatomy of a type class](https://dev.to/mmenestret/anatomy-of-a-type-class-440j)
- Part 4: [Anatomy of semi groups and monoids](https://dev.to/mmenestret/anatomy-of-semigroups-and-monoids-22i8)
- Part 5: [Anatomy of functors and category theory](https://dev.to/mmenestret/anatomy-of-functors-and-category-theory-2gf0)
- Part 6: Anatomy of the tagless final encoding - Yet to come !

# 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:

- _Determinism_: _pure functions_ will __always return the same output when given the same inputs__. Consequently, they cannot use non-local variables, global mutable states, perform IO, and so on

    - `def add(a: Int, b: Int): Int = a + b` is deterministic, it will always return the same output value when given the same input values
    - `def rand(a: Int): Int = Random.nextInt(a)` is not, each call may return different values
    - A function returning `Unit` should be a __huge code smell__, as it is does nothing else than _side effecting_ (execept if it only returns Unit and nothing else, but I doubt you would want to do that...) ! It a determinism's nemesis !

- _Totality_: _pure functions_ from type `A => B` (`A` is called the _domain_ and `B` the _co-domain_), __have to be defined for every value of its domain__, here for every value of type `A`

    - `def divide(a: Int, b: Int): Int = a / b` is not total, it will crash if `b == 0`
    - `def safeDivide(a: Int, b: Int): Option[Int] = Try(a / b).toOption` is total by handling undefined case with `None`

- _Referential transparency_: _pure functions_ calls __should be replacable by their results__ anywhere they are used __without altering the rest of the program__

```scala
    def launchTheMissiles: Unit = ???
    def formattingMyStuff(s: String): String = {
        launchTheMissiles
        s.toUpperCase
    }
```

Here we cannot replace any calls to `formattingMyStuff("hi")` by `"HI"` without altering the rest of the program, because `formattingMyStuff` performs a side effect, `launchTheMissiles`. We know that by replacing `formattingMyStuff("hi")` by `"HI"`, the missiles won't be launched.

With `def purelyFormattingMyStuff(s: String): String = s.toUpperCase` howerver, any call to it could be replaced directly by the uppercased argument and we know that the program would work the same way it did before.

To go even further, a _referentialy transparent_ function should be replaceable by a lookup table associating directly its inputs to its output.

Since `def boolToString(b: Boolean): String = if (b) "That's true !" else "That's wrong..."` is referencially transparent, it is replaceable by the following lookup table without altering the rest program:

Input | Output
--- | ---
`true` | "That's true !"
`false` | "That's wrong..."

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:

- A function returning an `Option[Int]` is in fact just returning an `Int` but it adds explicitly to that `Int` the __effect__ of being able to fail by wrapping it in an `Option`
- A function returning an `Either[String, Int]` is in fact just returning an `Int` but it adds explicitly to that it the __effect__ of potentialy returning a `String` instead (which is often used to describe a failure with its reason), by wrapping it in an `Either[String, Int]`
- A `Task[Int]` or `IO[Int]` (these are more or less the same thing), returns a __computation that is not run yet but that will produce an `Int` or fail, when executed__, which is often used to explicitly represent a value that is obtained by doing an _IO_. It is the description of the things to do to produce that `Int`, but it hasn't started yet.
- A lot of other effects can be encoded that way but going in details is some other blog post material (you can find a lot of related resources [here](https://github.com/mmenestret/fp-ressources/blob/master/README.md))

## Data philosophy

### Data / behavior relationship

_OOP_ and _FP_ have two different approaches when it comes to data/behavior relationship:

- _Object oriented programming_ often __combines data and behavior__ by mixing them into classes that:
    - Store data as an internal state
    - Expose methods that act on it and may mutate it

```scala
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 !"
}
```

- _Functional programming_ aims to completely __separate data from behavior__ by:
    - Defining types ([ADT](https://dev.to/mmenestret/anatomy-of-an-algebra-3cd9) on one side that expose no behavior and only holds data
    - Functions taking values of some of these types as inputs, acting on them and outputting values of some of those types (leaving the input values unchanged)

```scala
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:

- New cases to existing types
- New behaviors (functions) over existing types

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_

- 👍 : Adding new cases to an existing _data type_
    - A new _class_ _extending_ the existing _class / interface_
- 👎 : Adding a new behavior over an existing _data type_
    - A new _method_ on the appropriate _super class / interface_ which impacts every single _sub classes_

Base case:

```scala
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_:

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

Adding a new behavior over an existing _data type_:

```scala
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_

- 👎 : Adding new cases to an existing _data type_
    - A new _type_ to your existing _sum type_ (cf: [Anatomy of an algebra](https://dev.to/mmenestret/anatomy-of-an-algebra-3cd9) which impacts every _functions_ over that _data type_ (you'll have to handle that new case)
- 👍 : Adding a new behavior over an existing _data type_
    - A new _function_, nothing more

Base case:

```scala
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_:

```scala
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_:

```scala
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.

- That is _mutability_, and thus, should be avoided in _functional programming_:

```scala
var meaningOfLife = 41
meaningOfLife = meaningOfLife + 1
```

- That piece of data is _immutable_:

```scala
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:

```scala
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](https://www.youtube.com/watch?v=GqmsQeSzMdw) 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:

- If you had these two equations:

```
    2x - 3y  = 12
    y + 2x   = 180
```

- Then you could isolate `x` the first one:

```
    2x - 3y = 12
    2x      = 12 + 3y
    x       = (12 + 3y ) / 2
```

- And then simply __replace__ `x` in the rest of your reasoning by its value:

```
    y + 2x                  = 180
    y + 2 * (12 + 3y) / 2   = 180
    y + 12 + 3y             = 180
    4y                      = 168
    y                       = 42
```

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](https://www.ibm.com/developerworks/library/j-ft4/index.html))

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:

- Trivial refactoring

    - You know that you can change this red brick by that blue one if it respects the same contract without affecting at all the rest of your construct for obscure reasons (side effects, mutability, ...)

- Composability

    - You can build a construct on one side, another on the other side and plug them together to make a new, more complex, construct safely that behaves as you would expect
    - That's exactly what you'll do with your pure functions, you know they take inputs, compute and return outputs and __nothing__ else, thus you can safely compose them and build up more and more complexity fearlessly

- Easier testability
    
    - You can easily test if a piece does what it is expected to since it does nothing more than being, well, a simple, independent, side effect free, piece !

## Crystallizing design patterns

To end with _FP_ benefits, there is this curious thing called [_Curry–Howard correspondence_](https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_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:

- Global states
- Concurrency
- Computation parallelization
- Computation failure
- Validation accumulation
- Asynchronism
- Sequentiallity
- ...

You can find here a list of how _FP_ constructs corresponds to _OOP_ classical design patterns: [Lambda, the ultimate pattern factory](https://github.com/thma/LtuPatternFactory).

Pretty convenient !

# More material

If you want to keep diving deeper, some interesting stuff can be found on my [FP resources list](https://github.com/mmenestret/fp-ressources) and in particular:

- [What Referential Transparency can do for you - Luka Jacobowitz](https://www.youtube.com/watch?v=X-cEGEJMx_4&feature=youtu.be&t=228)
- [Constraints Liberate, Liberties Constrain — Runar Bjarnason](https://www.youtube.com/watch?v=GqmsQeSzMdw)
- [Functional Design Patterns - Scott Wlaschin](https://www.youtube.com/watch?v=srQt1NAHYC0)
- [Propositions as Types - Philip Wadler](https://www.youtube.com/watch?v=IOiZatlZtGU)

# Conclusion

To sum up, we saw:

- What actually _is_ __functional programming__ and that is what about manipulating __immutable data__ with __pure functions__
- Then we saw what were _side effects_, _pure functions_ and _immutability_
- The liberties that _FP_ constraints gives you (equationnal reasoning, predictability, composability, easier refactoring, easier testability, etc.)
- That it exists a bridge between the world of _Mathematical logic_ and _computation_ and how that bridge is used to give us powerful constructs
- How some of these constructs can address real world problems you would have solved with cumbersome, hand crafted, design patterns otherwise

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 !