Notes on "Erik Meijer: Functional Programming"

My notes on an interview of Erik Meijer talking about functional programming: https://www.youtube.com/watch?v=z0N1aZ6SnBk.

It's a super interesting interview. Erik is very articulate and gets straight to the heart of the problem without being overly theoretical. Here are some of my notes on the video.

12:50 - Java is dishonest about it's type signatures. For example int f() doesn't tell you whether f returns the same int each time it is called, or whether it does something in the background. Take for example the following functions:

public class Example {
  int f(int x) {
    return x + 5;
  }

  int g(int x) {
    return x + new Random().nextInt();
  }
}

Without looking at the implementation there's no way to know that g changes each time it's called.

Here's another example that says it returns an int, but actually never returns an int.

  int h(int x) {
    throw new RuntimeException("not an int!");
  }

Why is this problematic? Imagine you're working on the code in the following example. You might notice that there's some duplication going on and want to refactor it.

  int example() {
    return g(5) + g(5);
  }

So you go ahead and refactor out the repeated code and get this:

  int example() {
    int g5 = g(5);
    return g5 + g5;
  }

Great! We no longer compute g(5) twice so the function probably runs twice as fast! Unfortunately it's no longer correct though, because behind the scenes g is accessing global state. Inside the constructor of Random is a call to the OS clock in order to initialise the random number generator, which changes every time it's called.

This is a pretty contrived example, but it illustrates a real problem - it's not safe to refactor without first checking whether the implementation has side effects.

16:50 - FP is programming with mathematical functions. Every time a function is executed with the same inputs you always get the same result.

27:34 Some more examples. Assume we have the current time stored in a variable called Ticks:

static long Ticks // the current time

If we write the following functional-style code, this illustrates the problem before, that Ticks is side-effectful so returning a pair (x,x) is not the same as returning (Ticks, Ticks):

let x = Ticks // not a valid refactoring
in (x, x)

Suppose we do the following instead where we turn x into a lambda and call it twice:

let x = () => Ticks
in (x(), x())

That seems to have solved our problem, except that we could also make the following refactoring and be right back where we started:

let x = () => Ticks
let y = x
in (y, y)

Actually what we need is a way to model the sequential nature of the problem. We need the value of Ticks and then we need the value of Ticks again.

Let's say we have w to represent "the state of the world" and we make x a lambda that takes the state of the world and returns a pair containing Ticks and the state of the world.

let x = w => (Ticks, w)

We can call it like this, feeding in the current state of the world and getting back an updated state:

f(w) {
  (t, w') = x(w)
  (t', w'') = x(w')
  (t, t')
}

What we're trying to acomplish here is a sort-of "threading" through the state of the world w goes into x and comes out as a new state of the world w'. We thread it through again to get w''. Now we've made this sequential dependency explicit so that t and t' really must be different values of Ticks.

You can think about haskell in the following way. Imagine you have the following function:

 A,       W       ------------>   R,     W'

some   state of     function     result  new state
value  the world                         of the world

We can rewrite this as:

A -> W -> R, W'

Bracketing this slightly differently give us a function that takes an argument and returns a function that takes the world and returns a result and the state of the world.

A -> (W -> R, W')

Now we just hide the details of this "state of the world" thing behind a type called IO.

A -> IO R

Conclusion

I've skimmed many details here, and some of it was quite hand-wavy in the video too, but I think it really helps to build and intuition for why Monads exist (sequencing) and why it's a good idea to make computations with side-effects explicit.