Does immutability in functional programming really exist?

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.
• I disagree with you when you say there are no variables in functional code. There are variables in the mathematical sense of “A quantity that may assume any one of a set of values”. They are not mutable, sure, but neither are they in mathematics. – Édouard Jan 24 '15 at 21:26
• I think your confusion is because you're thinking about functional languages abstractly. Just take any program in Haskell - e.g. a program that reads a list of numbers from the console, quick-sorts it and outputs it - and figure out how it works and how it disproves your suspicions. There is no way to really clear things up without looking at examples of actual programs rather than philosophizing. You'll find plenty of programs in any Haskell tutorial. – jkff Feb 21 '15 at 19:02
• @jkff What are you trying to say? That Haskel has non functional features. The question is not about Haskell, but about functional programming. Or are you asserting that all that is functional? How? So what should be wrong with philosophizing, as you say. In what way is abstraction confusing? The OP question is a very sensible one. – babou Feb 24 '15 at 17:46
• @babou I'm trying to say that the best way to understand how a purely functional programming language can efficiently implement algorithms and data structures is to look at examples of algorithms and data structures efficiently implemented in a functional programming language. It seems to me that OP was trying to understand how it is conceptually possible - I think the fastest way to understand that is to look at examples, rather than read a conceptual explanation, no matter how detailed. – jkff Feb 25 '15 at 4:31
• One way to look at functional programming is to say that it is programming without side effects. You can do that in your "trendy" language of choice. Just don't avoid all reassignments: e.g. in Java, all of your variables will be final and all of your methods will be read-only. – reinierpost Sep 19 '16 at 13:22

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.

• I feel like you conveniently ignored what might be arguably the most important point in @Pithikos's post, which is the space issue -- functional programs use more space than imperative ones (you can't write in-place algorithms and such) – user541686 Jan 24 '15 at 21:00
• This simply not true. The lack of mutation is largely made up for by sharing and to top all of that the size difference you refer to is aubsurdly small with modern compilers. Most code on lists in haskell is effecientlly in place or uses no memory at all. – Jake Jan 24 '15 at 23:41
• I think you misrepresent ML somewhat. Yes, I/O can happen anywhere, but the way new information is introduced into existing structures is tightly controlled. – dfeuer Jan 25 '15 at 4:42
• @Pithikos, There are variables all over the place; they're just different from what you're accustomed to, as Édouard indicated. And things are continually being allocated and garbage collected. Once you actually get into functional programming, you'll get a better sense of how it actually goes. – dfeuer Jan 25 '15 at 4:47
• It is true that there exist algorithms which have no purely functional implementation with the same time complexity as the best known imperative implementation - e.g. the Union-Find datastructure (and, um, arrays :) ) I imagine there are also cases like this for space complexity. But these are exceptions - most common algorithms/datastructures have implementations with equivalent time and space complexity. It's a subjective matter of programming style and (to a constant factor) of quality of the compiler. – jkff Feb 21 '15 at 19:00

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.

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.

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.

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.

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.

• "Functional programs are, like any programs, really functions mapping integers to integers." How is, say, Minecraft, really a function mapping integers to integers? – David Richerby Feb 20 '15 at 22:27
• Easily. Every byte can be interpreted as a binary integer. A state in a computer is a collection of bytes. A program, even Minecraft, manipulates a computers state, mapping it from one state to another. – Jeppe Hartmund Feb 21 '15 at 22:44
• User input doesn't seem to fit into this world. – David Richerby Feb 21 '15 at 22:49
• User input is part of a computers state. It doesn't just exist on your screen. – Jeppe Hartmund Feb 21 '15 at 22:55