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();
  }
}

Enter fullscreen mode Exit fullscreen mode

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!");
  }

Enter fullscreen mode Exit fullscreen mode

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);
  }

Enter fullscreen mode Exit fullscreen mode

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

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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)

Enter fullscreen mode Exit fullscreen mode

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

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

Enter fullscreen mode Exit fullscreen mode

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)

Enter fullscreen mode Exit fullscreen mode

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)

Enter fullscreen mode Exit fullscreen mode

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')
}

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

We can rewrite this as:

A -> W -> R, W'

Enter fullscreen mode Exit fullscreen mode

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')

Enter fullscreen mode Exit fullscreen mode

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

A -> IO R

Enter fullscreen mode Exit fullscreen mode

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.

原文链接：Notes on “Erik Meijer: Functional Programming”