Does immutability in functional programming really exist?

Question

Although I work as a programmer in my daily life and use all the trendy languages (Python, Java, C, etc) I still have no clear view of what functional programming is. From what I've read, one property of functionally languages is that data structures are immutable. For me this alone raises a lot of questions. But first I will write a bit of what I understand of immutability and if I'm wrong, feel free to correct me.

My understanding of immutability:

• When a program starts it has fixed data structures with fixed data
• One can't add new data to these structures
• There are no variables in the code
• You can merely "copy" from the already data or currently calculated data
• Because of all above, immutability adds huge space complexity to a program

My questions:

1. If data structures are supposed to remain as they are (immutable), how the hell does someone add a new item in a list?
2. What is the point in having a program that can't get new data? Say you have a sensor attached to your computer that wants to feed data to the program. Would that mean that we can't store the incoming data anywhere?
3. How is functional programming good for machine learning in that case? Since machine learning builds from the assumption of updating the program's "perception" of things - thus storing new data.

Answer 1

When a program starts it has fixed data structures with fixed data

This is a bit of a misconception. It has a fixed form and a fixed set of rewrite rules but these rewrite rules can explode into something much larger. For instance the expression [1..100000000] in Haskell is represented by a very small amount of code but its normal form is massive.

One can't add new data to these structures

Yes and no. The purely functional subset of a language like Haskell or ML can't get data from the outside world but any language for practical programming has a mechanism for inserting data from the outside world into the purely functional subset. In Haskell this is done very carefully but in ML you can do this whenever you want.

There are no variables in the code

This is pretty much true but don't confuse this with the idea that nothing can be named. You name useful expressions all the time and constantly reuse them. Also both ML and Haskell, every Lisp I have tried, and hybrids like Scala, all have a means of creating variables. They just are not commonly used. And again the purely functional subsets of such languages don't have them.

You can merely "copy" from the already data or currently calculated data

You can perform calculation by reduction to normal form. The best thing to do is probably to go write programs in a functional language to see how they do in fact perform calculations.

For instance "sum [1..1000]" is not a calculation I want to perform but it is quite handily done by Haskell. We gave it a small expression that had meaning to us and Haskell gave us out the corresponding number. So it definitely performs calculation.

If data structures are supposed to remain as they are (immutable), how the hell does someone add a new item in a list?

You don't add a new item to a list, you create a new list out of the old one. Because the old one can't be mutated it is perfectly safe to use it in the new list, or whereever else you want. Much more data can be safely shared in this schema.

What is the point in having a program that can't get new data? Say you have a sensor attached to your computer that wants to feed data to the program. Would that mean that we can't store the incoming data anywhere?

As far as user input goes, any practical programming language has a way of getting user input. This happens. However there is a fully functional subset of these languages that you write most of your code in and you reap the advantages in this way.

How is functional programming good for machine learning in that case? Since machine learning builds from the assumption of updating the program's "perception" of things - thus storing new data.

This would be the case for active learning but most machine learning I have worked with (I work as a code monkey in a machine learning group and have done so for a few years) has a one time learning process where all the training data is loaded in at once. But for active learning you can't do things 100% purely functionally. You are going to have to read in some data from the outside world.

Answer 2

Immutability or mutability are not a concepts that make sense in functional programming.

The computational context

This is a very good question that is an interesting follow up (not a duplicate) to another recent one: What is the difference between assignment, valuation and name binding?

Rather that replying to your statements one by one, I am trying here to give you a structured overview of what is at stakes.

There are several issues to be considered to answer you, including:

• What is a model of computation, and what concepts make sense for a given model

• What is the meaning of the words you are using, and how does it depend on the context

Functional programming style seems silly because you see it with an imperative programmer eye. But it is a different paradigm, and your imperative concepts and perception are alien, out of place. The compilers have no such prejudices.

But the end conclusion is that it is possible to write programs in a purely functional way, including for machine learning, thought functional programming does not have the concept of storing data. I seem to disagree on this point with other answers.

In the hope a few will be interested despite the length of this answer.

Computational paradigms

The question is about functional programming (aka applicative programming), a specific model of computation, whose theoretical and simplest representative is the lambda calculus.

If you stay at a theoretical level, there are many models of computation: the Turing machine (TM), the RAM machine and others, the lambda calculus, combinatory logic, recursive function theory, semi-Thue systems, etc. The more powerful computational models have been proved equivalent in terms of what they can address, and that is the gist of the Church-Turing thesis.

An important concept is reducing models to each other, which is the basis for establishing the equivalences that lead to the Church-Turing thesis. Seen from a programmers perspective, reducing one model to another is pretty much what is usually called a compiler. If you take logic programming as your model of computation, it is quite different from the model provided by the PC you bought in a store, and the compiler does translate programs written in logic programming language to the computational model represented by your PC (pretty much the RAM computer).

However, it does not mean that the two models do things the same ways, or that a concept meaningful for one can be transferred as such to another. Typically, a computation step in a TM has little relation to a ($\beta$-)reduction step in Lambda Calculus, though they are inter-translatable. The concept of optimal evaluation of lambda expression is quite remote from complexity issues in TM models.

In practice, the programming languages that we use tend to mix concepts from different theoretical origins, trying to do it so that selected parts of a programs can benefit from the properties of some model where appropriate. Similarly, people building systems may choose different languages for different components, to best suit the language to the task at hand.

Hence, you seldom see a programming paradigm in a pure state in a programming language. Programming languages are still classified according to the dominant paradigm, but properties of the language may be affected when concepts from other paradigms are involved, often blurring distinctions and conceptual issues.

Typically, languages like Haskell and ML or CAML are considered functional, but they can allow for imperative behavior ... Else why would one talk of the "purely functional subset"?

Then one can claim that, you can do this or that in my functional programming language, but it is not really answering a question on functional programming when it is relying on what can be considered extra-functional.

The answers should be more precisely related to a specific paradigm, without the extras.

What is a variable?

Another problem is the use of terminology. In mathematics a variable is an entity that stand for an undetermined value in some domain. It is used for various purposes. Used in an equation, it may stand for whatever value such that the equation is verified. This vision is used in logic programming under the name of "logical variable", probably because the name variable already had another meaning when logic programming was developed.

In traditional imperative programming, a variable is understood as some kind of container (or memory location) that can memorise the representation of a value, and possibly get its current value replaced by another one).

In functionnal programming, a variable has the same purpose it does in mathematics as a place-holder for some value, yet to be provided. In traditional imperative programming this role is actually played by constant (not to be confused with literals which are determined value expressed with a notation specific to that domain of values, such as 123, true, ["abdcz",3.14]).

Variables of whatever kind, as well as constant, may be represented by identifiers.

The imperative variable can have its value changed and that is the basis for mutability. The functional variable cannot.

Programming languages usually allow for larger entities to be build from the smaller ones in the language.

Imperative languages allow for such constructs to include variables and that is what gives you mutable data.

How to read a program

A program is fundamentally an abstract description of your algorithm is some language, whether a pragmatic design, or a paradigmatically pure language.

In principle, you can take every statement for what it is supposed to mean abstractedly. Then the compiler will translate that to some appropriate form for the computer to execute, but that is not your problem in first approximation.

Of course, reality is a bit harsher, and it is often good to have some idea of what happens so as to avoid structures that the compiler will not know how to deal with for efficient execution. But that is already optimization ... which compilers can be very good for, often better than programmers.

Functional programming and mutability

Mutability is based on the existence of imperative variables that can contains values, to be changed by assignment. Since these do not exist in functional programming, everything can be seen as immutable.

Fuctional programming deals exclusively with values.

Your first four statements on immutability are mostly correct, but describe with imperative view something that is not imperative. It is a bit like describing with colors in a world where every one is blind. You are using concepts that are alien to functional programming.

You have only pure values, and an array of integers is a pure value. To get another array that differs only in one element, you have to use a different array value. Changing an element is just a concept that does not exists in this context. You may have a function that has an array and some indices as argument, and returns a result that is an almost identical array which differs only where indicated by the indices. But it is still an independent array value. How are these value represented is not your problem. Maybe they "share" a lot in the imperative translation for the computer ... but that is the compiler's job ... and you do not even want to know for what kind of machine architecture it is compiling.

You do not copy values (it make no sense, it is an alien concept). You just use values that exist in the domains you have defined in your program. Either you describe them (as literals) or they are the result of applying a function to some other values. You can give them a name (thus defining a constant) to make sure the same value is used in different places in the program. Note that function application should not be perceived as a computation but as the result of the application to the given arguments. Writing 5+2 or writing 7 amounts to the same. Which is consistent with the previous paragraph.

There are no imperative variables. No assignment is possible. You can bind names to values only (to form constants), unlike imperative languages where you can bind names to assignable variables.

Whether that has a cost in complexity is totally unclear. For one thing, you reference to complexity concerns imperative paradigms. It is not defined as such for functional programming, unless you choose to read your functional program as an imperative one, which is not the intent of the designer. Indeed the functional view is intended to let you not worry about such issues and concentrate on what is being computed. It is a bit like specification versus implementation.

The compiler has to take care of implementation, and to be smart enough to best adapt what is to be done to the hardware that will do it, whatever it is.

I am not saying programmers never worry about that. I am also not saying that programming languages and compiler technology are as mature as we might wish them to be.

Answering the questions

1. You do not modify existing value (alien concept), but compute new values that differ where desired, possibly by having one extra element it it is a list.

2. The program can get new data. The whole point is how you express that in the language. You can for example consider that the program works with one specific value, possibly unbounded in size, which is called the input stream. It is a value that is supposed to be sitting there (whether it is already known fully or not is not your problem). Then you have a function that returns a pair composed of the first element of the stream, and the rest of the stream.

   You can use that to build networks of communicating components in a purely applicative way (coroutines)

3. Machine learning is just another problem when you have to accrete data and modify values. In functional programming you do not do that: you just compute new values that differ appropriately according to the training data. The resulting machine will work as well. What you worry about is computing time and space efficiency. But, again, that is a different issue, that ideally should be dealt with by the compiler.

Final remarks

It is quite clear, from the comments or the other answers, that practical functionnal programming languages are not purely functional. That is a reflection on the fact that our technology is still to be improved, especially where compiling is concerned.

Is it possible to write in a purely applicative style? The answer has been known for about 40 years and it is "yes". The very purpose of denotational semantics as it appeared in the 1970's was precisely to translate (compile) languages into purely functional style, deemed better understood mathematically and thus considered a better fundation to define the semantics of programs.

The interesting aspect ot it is that imperative programming structure, including variables, can be translated into a functional style by introducing appropriate domains of values, such as a data store. And despite the functional style, it remains surprisingly similar to the code of actual compilers written in imperative style.

Answer 3

It is a misconception that functional programs can't store data, and I don't think Jakes answer really explained this very good.

Functional programs are, like any programs, really functions mapping integers to integers. Any imperative program operating on mutable data structures have a functional counterpart. This is just another means of achieving the same end.

The functional way of storing experiment data from some source would be calling the storing function with the data structure as argument and outputting a concatenation of the existing data structure and the new data and thus data is stored without the notion of mutable data structures.

From my own experience, I think the concept of immutable data structures are leading conventional developers to think that there are certain things that are impractical or even impossible to do in a functional setting. This is not the case.