Notes on "Erik Meijer: Functional Programming"
Tags: functional, java, haskell
Published: 2020-10-15 12:18:30

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:
```java
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.
```java
  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.
```java
  int example() {
    return g(5) + g(5);
  }
```

So you go ahead and refactor out the repeated code and get this:
```java
  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`:
```java
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)`:
```haskell
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:
```haskell
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:
```haskell
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.
```haskell
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:
```haskell
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.