April 18, 2019

FP for OO - Part 1

What is FP anyway?

Previous Post: https://blog.marktranter.com/fp-introduction/

The common and trite definition of Functional Programming is:

programming with functions.

I've used jargon styling here because the meaning of the word function in FP is more specific than in other paradigms.

What is a function?

To qualify as a function, a "function" (or method or procedure) must:

  • Be deterministic. Same output for the same input. Every time.
  • Be total. Return an output for every input. So no null or throw.
  • Have no side-effects. Meaning they do not modify anything outside of their own scope.
  • Be referentially transparent: that is, defined such that we can evaluate an entire function by simply substituting in it's variables. i.e.
    f(x) = x2 + 2x + 1
    f(2) = 22 + (2.2) + 1
    f(2) = 4 + 4 + 1
    f(2) = 9
    So no mutable variables!

If a "function" is a function, then we say it is a Pure Function. From now on, I will remove the jargon styling from the word.

From now on, if I use the word function, I mean a Pure FunctionTM

The other core component of FP is composition.


Composition is in jargon styling here because it's meaning is somewhat different, and much simpler, than the meaning of "composition" in Object Oriented programming.

When we talk about composition in OO, we mean that one class contains another class to help do it's job.

However in FP when we use the term composition, we just mean "and then".

For example, lets imagine we're writing a simple console app that takes some input, parses it to an integer, and then outputs the factors of that integer.

Our imperative code might look something like this...

class Imperative {

    static String getInput(String prompt) { return whatever(); }
    static int parseInt(String i) { return whatever(); }
    static int[] getFactors(int i) { return whatever(); }
    static void printFactors(int[] factors) { whatever(); }

    public static void showFactorsImperative(String[] args) {
        String  input           = getInput("Enter Int");
        int     parsedInput     = parseInt(input);
        int[]   factors         = getFactors(parsedInput);

However, using composition, we can redefine our program like this:

object Functionalish {

  val getInput:     String => String      = ???
  val parseInt:     String => Int         = ???
  val getFactors:   Int => Seq[Int]       = ???
  val printFactors: Seq[Int] => Unit      = ???

  val program: String => Unit =
    getInput andThen parseInt andThen getFactors andThen printFactors

  def main(args: Array[String]): Unit = program("Enter Int")

This example will compile in Scala. It is perfectly valid syntax. So andThen is our composition operator. It allows us to compose two functions into a single function.

To formalise it:
(A => B) andThen (B => C) == A => C.
This is the definition of function composition.

Ignoring the obvious flaws in our program, notice that the compiler will check everything for us. It validates that the inputs and outputs are compatible.

So if our functions are pure functions, then we can be 100% sure that our program will run and terminate correctly.

So what?

This is important so I'll labour the point.

If we can define a program in terms of the composition of pure functions, we can use the compiler to help check the correctness of our program.

We don't throw, so we won't have exceptions.
We don't use null so we won't see NullPointerExceptions.
We don't have side effects or random values so we can ensure no RuntimeExceptions.
We can statically determine that our program is correct.
Even better: we can ask the type checker to determine this for us!!

The importance of being Pure.

Imagine if parseInt in the above threw an error. Or it returned null. The compiler could not give us any correctness guarantees. It would still compile, but it would fail at runtime.

Nulls and Exceptions are completely opaque to the type system. And this is why FP places such a high importance on purity.

If you take one thing from this blog series: Typed functional programming, allows us to use the type-checker to help check our program's correctness. If you're lazy like me, then this is awesome.

However there are still some big questions about our above program.

  1. The type system cannot tell us if we have implemented our getFactors function correctly.1
  2. What if the input contains an invalid int?
  3. If we have user input at all, then how can can we have determinism? (Free Will debates aside)
  4. If we can't have side-effects, how can we do anything interesting at all? So what is the fucking point?

To answer:

  1. We write tests. Yes, we still write tests.
  2. We'll find out shortly in this series.
  3. (And 4) We'll find out later in this series.

So to recap. Functional Programming is just doing composition with pure functions. It lets the type-checker do half of our job for us.


Next Up: https://blog.marktranter.com/the-m-word/

1 There probably is some way using dependent types with Agda or Idris. Or maybe even Scala. But is beyond the scope of this series. That is: I don't know how to do it.


Intro - https://blog.marktranter.com/fp-introduction/
What is FP - https://blog.marktranter.com/what-is-functional-programming/
The M Word - https://blog.marktranter.com/fp-in-oo/