The goal of functional programming

Question

I has always been thinking this, but I need a confirmation: The purpose of functional programming is to make written program becomes a mathematical proof. Once a program is correctly written, it is "proved" and is expected to work the same in any environment. This is why in FP, immutable is needed, otherwise there's no guarantee for the correctness of the "proof", because state changes can introduce unexpected behaviors.

Am I correct on the basis of Functional Programming?

Answer 1

You're not far off base but I wouldn't say it that way. I think the main goal of functional programming is to allow programmers to reason about their code more easily. We aren't always going to be able to have a formal poof of correctness, and indeed, most functional programmers don't construct one for their programs. But functional programs are still easier to reason about, in my opinion, and that's the goal. But how and why?

Static vs. dynamic

Static concepts are related to code as it is laid out as you read it in the file. Dynamic concepts are related to how data flows through your program from one place to another. People think much better statically than they do dynamically. This argument is made by Dijkstra in his seminole paper Go To Statement Considered Harmful. The argument is that it is hard to understand code if you need to keep track of how the code pointer flows about dynamically. You need to basically walk through the execution of the code. This is an argument for requiring that at least the code pointer behave in a more static way. Hence most programming languages do not implement GOTO but instead allow IF, FOR, and WHILE, to name a few. This is called structured programming. These are easier to reason about because they are more static.

The argument made by functional programmers is that functional programs are one step more restricted, one step more static, and thus one step easier to reason about. In a functional program your code is an expression that evaluates to a value, not a series of statements that mutates so state that you need to keep track of in your head in order to understand what happens to it and thus what it will eventually become.

I'm not saying functional programming makes this trivial, but the argument is that it's easier. Let's try this out in a small example. Expressions are composed of sub-expressions and one could evaluate said sub-expressions in order to understand their values first before understanding the value of the entire expression. Let's try to do this with a simple functional program with a bug. The following is some Haskell code.

size l =
    if null l
    then 1
    else 1 + size (tail l)

total l =
    if null l
    then 0
    else (head l) + total (tail l)

average l = total l / size l

Let's say I evaluate "average [1,2,3]" and I get "1.5". That's not right! What can I do? Well "average [1,2,3]" reduced to "1.5". If I break apart the definition for average into the two expressions that make it up, "total l" and "size l". I know the argument l is [1,2,3] so I will evaluate "total [1,2,3]" and get "6". That looks right but "size [1,2,3]" is "4". Ah! I know my bug is in the size function. So I would follow that down, end up with "size [] == 1" and realize my base case is incorrect. I should have written "then 0".

In contrast this very helpful reasoning strategy does not work in imperative programming. The reason is that one cannot extract a sub-statements from a process that is modifying state in order to understand it in isolation. A statement is meaningless outside of the context of its environment. Let's take a look at a C program with the equivalent bug.

int average (int *l) {
    int total = 0;
    int size = 1;
    int i;
    for (i = 0; i < sizeof(l); i++) {
        total = total + l[i];
        size = size + 1;
    }
    return total / size;
}

I have the same bug here as I did last time but now how can I reduce this to a simpler problem to debug my code? The statement "size = size + 1" is one sub-statement of my program but that has no meaning outside of its context. I can't ensure that this sub-statement of my program is functioning properly on its own. I need to walk carefully through the code, potentially using a debugger and tracing local state to watch it change. This is a very dynamic process. Humans think much better statically.

Testability

Functional programming is also easier to unit test. Take, for example, my average function from before. All of the sub-expressions I mentioned like "size [] == 0" and "size [1,2,3] == 3" would make perfect unit tests. Especially if they are things I know I have made mistakes on before!

Imagine if I try to refactor this program or make it more efficient. It'll be nice to have lots of the smaller parts automatically tested. Unit testing is certainly possible in imperative programming, and people do it all the time, but if you have a function that takes data in, returns data out, and always behaves the same way, nothing is easier to unit test than that.

Use functional programming when you can

For these reasons I think people even in imperative languages should be writing as much of their code as possible in a functional way to make it easier to test. There's no reason to be black and white about it. It's a tool, not a religion. Doing functional programming half way can greatly increase the testability and maintainability of your code.

Further reading

One great paper written on this topic, and indeed one where I have drawn a lot of inspiration in answering your question is Why Functional Programming Matters by John Huges. Also if you want to go through an entire curriculum designed for beginner programmers I highly recommend How to Design Programs. It really focuses on making writing coding easier by unit testing and dividing up your program into small, understandable subtasks. In doing so I feel it highlights what makes functional programming so powerful.