How could a computer program do anything if everything is immutable?

Question

I feel this is a bad question because I probably do not understand what I am talking about. In my effort to learn about functional programming, I became stumped on understanding the idea of immutable stuff. I have been using C# as a hobby for years and I think I do not even understand OOP principles very well. I use a class as a bucket of public and private data with methods pinned to it. It's partially mutable and partially immutable I guess? So I sort of want to step away from comparing and contrasting OOP and pure FP for a second and just think about "mutable" (can change) and "immutable" (cannot change) stuff.

People say it is good to make things immutable and I believe them. But how can a program do anything if you cannot change data? Whether you're talking FP or OOP, it seems that you need at least one giant mutable data structure (like a database) since all your functions or objects are immutable. But that sounds very impractical. I can think of it this way: x = f1(f2(f3(f4(f5( y ))))) where y is the user input and x is the output. The program is the immutable functions 1 through 5. But again, this appears very impractical. I think I understand the benefits of immutable things but I just don't understand how to use them properly for a large program.

Again, consider me a baby in the programming world. I would appreciate book or book chapter recommendations. And feel free to tell me if I'm asking the wrong question.

Answer 1

Mutable:

public void DoubleArray(int[] array)
{
    for (int i=0; i<array.length; i++)
        array[i] *= 2;
}

Immutable:

public int[] DoubleArray(int[] array)
{
    int[] result = new int[array.length];

    for (int i=0; i<result.length; i++)
        result[i] = array[i] * 2; 

    return result;
}

See the difference? The immutable code is perfectly feasible. In fact, this is how strings are treated in many languages, including Java and C#.

Some nice things about immutability:

1. Your code is easier to reason about, particularly in a multi-threaded context, because you don't have to worry about anything being modified.

2. You get a running history of "changes."

3. You can "memoize," which can actually improve performance.

Answer 2

Here's what most people seem to miss about immutability. Consider the following function:

def factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1)

This function is completely immutable. So does n ever change? Yes and no. One instance of n doesn't change, but you quite frequently get a completely new n and the reference to the old n is lost. n can even simultaneously refer to different values in different threads or different levels of the stack within the same thread.

This is how immutable programs 'change' things. Multiply this effect by every function in the program and there is quite a bit of apparent change going on, but within any given function everything is constant. It's almost paradoxical.

Answer 3

You are correct that perfectly immutable program, one that relies only on it's input when started wouldn't be much useful.

But the idea of immutability is not to make program completely immutable, it is to abstract the mutable state away and push the mutable state to the edges of the program. This way, the actual core of the program, the one written by a programmer of an application can be immutable. There will still be mutability, but it will be hidden in libraries. Which means that programmer won't come into contact with (arguably dangerous) mutable state.

I'm not an expert on functional programming and immutable state, but two ideas come to mind.

IO monad is how input/output of functinal/immutable program can read and write into it's mutable state. Imagine a function readCharacter():Func<IO,Char>, this function when called, returns another function, which reads IO and returns character. The whole point of this is that many such function, which work on IO, can be compose together which would result into something like Program(IO). This program then takes IO into its outpu and it's inside can be perfectly immutable, pure and won't know it is actually doing side effects.

Second idea is that of reactive programming. In this paradigm, the central concept is that of stream of events. Those events can be inputs like keypresses, mouse clicks or files received over the network, or outputs, like changing text on a screen or sending a file. Then, methods can be applied to those streams to filter them, transform them, join them and do all kind of shenanigans with them. Then, your program could very well be one that has one input of stream of events and one output of stream of events and everything in the middle is immutable and pure. The mutability is hidden in the implementation of the streams and methods operating on those streams. This is how functional/immutable UIs can be made.