Why is shared mutable state considered bad? Isn't it an accurate reflection of the universe we live in?

No, it is not an accurate reflection. SMS leads to spooky action at a distance. With SMS, I can nail together two pieces of wood in Toronto, and unexpectedly, a house collapses in Los Angeles. SMS enables unpredictable non-local effects. I can't rely on local reasoning to understand what a program is doing.

Indeed. An important feature of the physical world is the limited range of most interactions. I have been wondering for a while if anyone has taken up this principle for programming. Something like a language where two functions can share state only if they are geometrically close in some way. For a text file based language, that doesn't make much sense, of course. Smalltalk is a bit like that if you present the class hierarchy as a tree with the methods as the ultimate leafs. Instance variables then are shared state of a subtree.

Not exactly what you are proposing, but: Orca is in a way geometric programming. Perhaps also some Factory simulation games, like Factorio? And redstones in Minecraft. https://wiki.xxiivv.com/#orca https://www.pcgamer.com/see-what-a-factorio-factory-looks-like-after-500-hours-of-work/

With SMS, I can nail together two pieces of wood in Toronto, and unexpectedly, a house collapses in Los Angeles.

I mean, if a butterfly flaps its wings in Brazil we get a hurricane off the coast of Florida, so that seems legit to me. 😉

I guess OOP tries to give a limit with encapsulation @Konrad Hinsen. You have local variables, class variables, modules. Doesn’t seem to work great if we look at the outcome of most projects.

@Daniel Garcia No, I think OOP is close to the worst case scenario. In Alan Kay's definition of OOP: 1. Everything is an object. There are no values, only references to mutable objects. 2. Objects encapsulate their state. 3. All computation occurs by sending messages to objects. The problem is #1: everything is a mutable object. This creates the problem I described. You could crash the original Smalltalk system by evaluating 'true becomes: false', which modifies the 'true' object so that it has the same object identity and behaviour as 'false'.

My beads language is based on mutable state. has no objects, no messages. It solves many problems, and certainly Konrad's suggestion that the functions should be geometrically close applies to the screen drawing aspect of the mutable state. In a graphical interactive product, you have your program's state, then there is the state of the drawing system (which is tied by necessity to the OS) which is derived from your state, and having geometric proximity, or at least a clear 1:1 mapping between the code that draws and the screen model is a immense benefit with regards to clarity.

@Daniel Garcia Perhaps the problem with OO is that it introduces locality in code space but not in data space. Any object can send any message to any other object. There is no notion of distance between objects.

@Konrad Hinsen it reminded me of this project http://zells.org. It has some spacial visualizations, but I don’t think it has a way to constrain data space. I haven’t checked in a while, maybe it has some more stuff now

Thanks @Daniel Garcia and @Garth Goldwater for those pointers!

@Konrad Hinsen One of the core ideas in the original formulation of OOP is to make shared mutable state pervasive and inescapable. That was the point of the story about

true becomes: false

. @Daniel Garcia In Smalltalk, objects encapsulate their state, at least in theory. But if you send a message to an object to query its state, the object has no choice but to return another mutable object in answer to the query. Which the caller can then mutate, possibly by accident. If an object returns one of its instance variables in response to a query (which might be the simplest way to write the code), then the caller can mutate the object's internal state without going through the object's message interface. Which could make the object's internal state invalid. So OOP creates this huge problem with shared mutable state, which can be mitigated by design patterns, coding hygiene, and additional language complexity.

Even though I like the ideas in OOP, I do agree with @Doug Moen that in the current tools and languages, you end with accidentally shared state without consistency checks. However I think the fundamental ideas of encapsulation and identity/state are useful perspectives and the ideas are perhaps incompletely explored. One variant is erlang-style - state really hidden because messages are always values. Another is messaging via a tuplespace. Another one might be a recursive design (e.g. inner objects + their tuple space complete encapsulated inside an outer one). IOW, I don't think identity and state themselves are problematic as starting points, but it is how they are coupled and driven forward in time.

Alan Kay's original pitch for Object Oriented Programming included the idea that "the real world" is made of stateful objects, therefore a programming model where there are no values, and everything is a reference to a stateful object, must be more natural, and if it's more natural, then it's a better style of programming. The argument seems like an example of the naturalistic fallacy. 45 years later, I think this idea is old and busted. What's actually important is the amount of cognitive load that you must take on in order to understand a program. If you have to simulate all of the state in the entire program, in your head, in order to understand it, that's bad. If the language provides guarantees that permit you to reason locally about the meaning of code, then that's good. After decades of OOP, the problems with that model are now evident, and that's why functional programming is on the rise. Pure functions (in a pure functional language) are guaranteed to compute a result based only on the argument values, so they are easy to reason about. Erlang provides a lot more scoping and control over mutable state than Smalltalk does, so it's an improvement.

aren't functional programming and OOP just 2 different tools to be used when the tool fits the job? the obvious example where pure functions fail is databases. You can't pass in an immutable copy of a petabyte database and get a new copy out. Not saying OOP solves that issue. Only that pure functions are not a solution there.

Alan Kay's original pitch for Object Oriented Programming included the idea that "the real world" is made of stateful objects, therefore a programming model where there are no values, and everything is a reference to a stateful object, must be more natural, and if it's more natural, then it's a better style of programming.

Do you have a source for this? Object based metaphors pop up all over different domains, not just the physical world. Even the final products of any programming - buttons that push, windows that move, pictures that can be cropped, shipped around etc. - are all virtual objects. People don't want pure functions, they want their computers to have state and be able to manipulate it. This doesn't mean programming has to be OO, of course. But perhaps it means we should start with objects as an underlying substrate (directly modifying these would be considered primitive) and then work up to pure transforms or other ideas that operate on this substrate. So I don't think OO and FP are mutually exclusive, but more like clusters of concepts - some of which can be integrated. This is not just for personal computers but also large scale services. Once you compile and run an FP program, it becomes an object 'in the large'. Because when you zoom out from a single program to a whole system, all the microservices, monoliths, databases, etc. are objects of a kind (have state + communicate via messaging). Again, what we ended up building and reasoning about are object-based models. So does it mean we've just kicked the can down the road? Regarding 'local reasoning' and 'simulating in your head', what I feel is any single programming paradigm is going to fail in some scenario because there will always be some cross-cutting concerns (no matter what kind of slices form the program). So no single paradigm is going to work in all cases - perhaps we should thing about multi-perspective as a base requirement. E.g. a system where you can query the computer about the relationship between one entity and another. And query the system also about the effects of a change to an entity you are about to make. We're way past the point of scaling where mental reasoning can work for us.

The high level concern is communication. For example, "mutable local state is bad" is referring to how it's hard to understand the interactions between disparate units. The historical mistake is that we conflated day to day communication patterns with physical properties. Put another way, abstractions are useful because of what they hide. For example A stack is a good type because it has a well known structure and interaction with the underlying components of the system. A stack in a multi concurrent threaded environment will need to reason about how it will handle multiple requests. A stack in distributed system will need to reason about late requests. A good implementation of a stack will hide what it can while fulfilling its basic contract and make it clear what it can't A "person" is not a good type because it has no known structure or interaction with the underlying system. How a person behaves when they get a late message isn't a good model for how the system should behave given a request about a person that comes in late. It has no abstraction layer over the system and it fails to be an effective one over the business data.

I didn't quite get the Person vs Stack example. Surely you want a system that can represent Persons?

We only have one kind of computer today, the Von Neumann-Turing machine, which modifies memory. All the CPU's use registers for speed, and all programs shuffle data to and from registers where the computations are performed. Since all programs devolve ultimately to mutable state, there is nothing wrong whatsoever with mutable state; it is how machines actually work. So any language that claims to not use mutable state is merely concealing the mapping from pure functions to mutable state. The inventor of FP, John Backus, had a goal of creating interchangeable parts, and he felt that reducing mutable state would make things more combineable. However, 50 years later his original proposals haven't worked out. There is no evidence that people can take a chunk of Haskell code or any other FP language and inject it into another program easily. So something was missing in his formulation, and best not to rely too much on an incomplete theory.

So any language that claims to not use mutable state is merely concealing the mapping from pure functions to mutable state.

Abstraction is the central idea that underlies high level programming languages. There is nothing "mere" about it.

The inventor of FP, John Backus, had a goal of creating interchangeable parts, and he felt that reducing mutable state would make things more combineable. However, 50 years later his original proposals haven't worked out. There is no evidence that people can take a chunk of Haskell code or any other FP language and inject it into another program easily.

"no evidence"? The fact that you can do this is why I fell in love with functional programming, and it's a central part of my mental experience when I am writing functional code. Here's a quote from Backus that you might be referencing:

Associated with the functional style of programming is an algebra of programs whose variables range over programs and whose operations are combining forms. This algebra can be used to transform programs and to solve equations whose "unknowns" are programs in much the same way one transforms equations in high school algebra. These transformations are given by algebraic laws and are carried out in the same language in which programs are written.

Haskell people call this "equational reasoning". It works. It's high school algebra, applied to programs. It's what you do when you think and program in the functional style. In principle, you can use this kind of reasoning when programming in any language. But imperative languages are not designed with equational reasoning in mind: a lot of algebraic laws are just broken and don't work, which makes them frustrating and klunky to use. You are forced to think imperatively, which sucks, although it's a necessary evil when you are doing performance tuning. Functional languages are specifically designed to have a large set of algebraic laws, which makes them much more satisfying to use if you think this way when you program.

Good discussion! Recall that the question is "why is local mutation considered bad, doesn't it reflect the world we live in"? To build off parts of this thread, would it be fair to say rather that People handling Incidental local mutation is disadvantages. That is, if can use some higher level of abstraction to reason and delegate lower level state changes to the computer then it's a win? E.g using map over a for loop. Mutations happen in the real world, but we're not trying to build the world. We're trying to model a very small fraction of it. @shalabh I want a system that can hold information about a person. I can use a stack, list or graph to do that because those data structures have a synergy with the hardware , an API that is more widely understood, and shared underlying principles that can be used in composing. You can put validations on those ds to ensure integrity while keeping the access pattern to them universally understood.

I think one way to think about the mutation issue (in a more physical than theoretical sense) is really just about figuring out causation: we have an incorrect state, and we want to figure out why it happened. with shared mutable state it's hard with existing tools to hunt down all the possible sources of state change. when we originally designed the system, we had a model of change in our heads that we didn't map correctly to the particular properties of our really existing system—which probably required a question like "How and why do these things change and happen (eg, what are the possible behaviors of this AWS API function)—which sure seems a lot like the same kind of causation question functional programming is an attempt to make causation questions easier by restricting the types of changes that a given piece of code can make. that's one approach to the causation question. another might be a debugging or program simulation tool-or an explicit list of dependencies like the observer pattern

The "functional mindset" (equational reasoning) and the "imperative mindset" are two quite different ways of thinking when you are programming. Perhaps this claim that shared mutable state is "natural" and "corresponds to the real world" is really just a way of saying that you are more comfortable thinking in the imperative mindset. Over on the #CKC6FM9DF channel, we are learning category theory, which is the mathematical structure that underlies a lot of the algebraic laws and equational reasoning in Haskell. A relevant quote from a recent post: "It turns out that many of the ideas of category theory come almost directly from the real world." Sounds familiar. That quote resonates with me, because at this point, I feel more comfortable with equational reasoning for most programming tasks, and my intuition tells me that the basic algebraic laws that functional programs obey also apply in a lot of real world situations outside of programming. For example, in math, addition is commutative and associative, which means that the order in which I count a set of objects (eg, the socks in my sock drawer) doesn't affect the answer. In a pure functional language, addition is also commutative and associative (modulo floating point roundoff errors), but once you add shared mutable state to a language, then these properties are lost: f(x)+g(x) is no longer equivalent to g(x)+f(x) because the order in which you call the functions now matters and can affect the result.

totally agree in principle and the category theory lectures are already proving very addictive but I think we can't pretend that all our tasks can be reduced to counting or similar—if you've observed your house has caught fire, or that other state in the world has changed then your behavior might also...(not to argue that you can't manage that functionally, just that mutable state is (repeating a cliche at this point) a fact of life and there are different options for dealing with it)

Just re-reading this conversation new ideas occurred to me. We don’t really have mutable state in the world as we do in programming, because in the real world we have strict time that “overwrites” old things. So if your house burns, as in the example above, there can’t be some persons holding to old “not burned house” and others to the burned house. Everyone shares the same reference. That seems more inclined with functional programming.

mutable state is (repeating a cliche at this point) a fact of life and there are different options for dealing with it

Agreed. "Shared mutable state" (SMS) is only one of the options for dealing with mutable state. SMS is strongly associated with OOP. You put all of your mutable state into objects, and the objects are organized into a graph, which usually contains cycles. That graph of object references makes shared mutable state unavoidable. An interesting alternative to OOP is data-oriented design (DOD). In this paradigm, you put all of your data into a centralized hierarchical data structure, analogous to a relational database. Application logic is kept separate from the data. DOD seems to be associated with systems level programming in C++ and Rust; the video game version is called Entity Component Systems. The claimed benefits of DOD are performance (better cache coherence, better multi-core performance) and maintainability (it's easier to evolve the code in response to changing requirements: you aren't constantly refactoring a class hierarchy). Some DOD practitioners are also claiming smaller code size, which is great if you are compiling to WASM. It's better for Rust programming, because cyclic object graphs in OOP "break the borrow checker", plus Rustacians are interested in performance and maintainability. I'm still trying to get a handle on DOD. Because of that central hierarchical data structure, it doesn't seem to require shared mutable state, and it seems compatible with pure functional programming. It also looks more compatible with GPU programming, because OOP object graphs aren't feasible on a GPU. So I'm investigating these ideas in the context of my Curv project, which can be considered a pure functional language for programming GPUs. A while back, somebody posted a reference to Raph Levian's Druid, a data oriented GUI framework in Rust. There is also Elm, which is a pure functional language for creating GUIs. The Elm Architecture seems to have some resemblance to DOD.

@Daniel Garcia the similarity with the real world is the concept of identity. Is it the same house in the future or a different one? Philosophically you can say either one.. maybe it's a different house every moment as those atoms travel through time. But conceptually it can be considered the "same house" even when you actually modify it, rebuild a wall, etc. It's the human mental model of the world that maintains the concept of identity.

Object based metaphors pop up all over different domains, not just the physical world. Even the final products of any programming - buttons that push, windows that move, pictures that can be cropped, shipped around etc. - are all virtual objects. People don't want pure functions, they want their computers to have state and be able to manipulate it.

People also want see changes what is have been made, go back in history and undo things. In general: reason about mutations. It's a bit ironic that systems that are pro mutation have actually much harder time to reason about them. Those aspects are therefore currently under shipped in real world products.

Clearly shared mutable state is not even negotiable in programming, otherwise we'd have no disks, no databases, no GUIs, no 3D worlds, no social media.. basically nothing apart from addition and the like. But poor ole' shared mutable state is the victim of two fallacies: (a) Imperative programming gets messy when trying to do concurrency and several threads of control have access to shared mutable state, giving rise to the fallacy that it's the shared mutable state's fault, not the many threads having write access. (b) Functional programming is clean and does concurrency in a way you can predict, but it doesn't have a concept of shared mutable state, giving rise to the fallacy that shared mutable state must be bad because FP is clean and doesn't have it. But shared mutable state isn't bad: all we need to do is (a) prevent concurrent write access, and (b) combine FP and shared mutable state in a clean model.

@Duncan Cragg: Clearly shared mutable state is not even negotiable in programming, otherwise we'd have no disks, no databases, no GUIs, no 3D worlds, no social media.. basically nothing apart from addition and the like.

When we say that "shared mutable state is bad", we are not denying the existence of reality. Far from it. We are taking a position on the semantics of expressions in high level programming languages. I think there might be some confusion around what claims are being made. Maybe the issues can be clarified with a slight change in terminology. How about "SMS semantics" or "SMS expression semantics" instead. Some researchers making these claims might use the term "imperative semantics", but I don't like that, it's too broad. My research project is a pure functional language that supports (a growing subset of) imperative style programming, but doesn't have SMS semantics. Of course computers and programs have state that changes over time, but languages with SMS semantics are maybe not the best tools for dealing with state. SMS languages are based on an idealized model of computation where computers have a single core, there is a global memory store where all words of memory have the same cost of access, and there is no networking. That worked well in the past, but not today. Once these assumptions are violated, the model breaks down. The canonical example of the failure of SMS semantics is multithreaded programming. The simple, obvious extension of SMS to support concurrency is shared memory with locks, and that is a nightmare to program with. One response is to patch and extend SMS to work around the problems. Rust supports safe concurrent programming, but at a large cost in language complexity. Another response is to look for simpler, more powerful alternatives to SMS, and that's what some of us in the Future Of Coding group are doing.

Another distinction here is "multithreaded" vs "concurrent": as you say, ground level reality has shared mutable hard disks, but in common use the disks are partitioned into "files" mostly touched by one program at a time. Within any given program, similar issues arise, where even if you are doing things strictly in sequence(a node.js callbacked event loop for instance) having global variables is still a recipe for two independent operations causing havoc upon each other.

@Doug Moen

languages with SMS semantics are maybe not the best tools for dealing with state.

As I said, a language that doesn't allow many threads simultaneous write access would presumably still have your "SMS semantics" (? not sure what exactly that is?). And why can't you add this "SMS semantics" to FP in a clean model?

Hm, I think if you define "multiple threads" as "in the scope of multiple closures", then you've just recreated the "shared" part of the initial "shared mutable state is bad" claim. Local Mutable State is certainly fine!

Sharing is not the problem, consistency is. It's just that many ways that let you share put the full burden of consistency on you. So what are the ideas that let us share but maintain consistency, visibility, introspection, reasoning, etc.

Well these ideas go back at least to 1978 with Backus in his Turing Award lecture (https://www.thocp.net/biographies/papers/backus_turingaward_lecture.pdf) in the form of "Applicative State Transition". A variant was outlined in "Out of the Tar Pit" as "Functional Relational Programming". The model is incredibly simple: just take a state and transform it to the next state using a clean declarative rule/transformation/rewrite/function/reduction. This can be done in parallel as long as you manage partitions of the state per thread.

Has anyone ever attempted to describe a whole system (equivalent to a computer, with user interaction, network communication, etc.) without explicit mutable shared state? My impression is that functional programming has been most succesfull in the small, at the level of well-defined abstractions close to mathematics. At the systems level, there's functional reactive programming for user interfaces, but it's much less mainstream. It doesn't sound impossible to extend this idea to a complete system, but has it been done?

@Duncan Cragg said "Clearly shared mutable state is not even negotiable in programming, otherwise we'd have no GUIs" "Shared mutable state" is a paradigm that many, but not all, programming languages are based on. You are saying that GUIs cannot be programmed in a language that does not support shared mutable state. Elm is a pure functional language for building GUIs. You are saying that Elm cannot exist. I don't think you believe it, but you keep saying it. So there must be a communication breakdown in this thread, or a misunderstanding somewhere.

I'm not familiar with Elm but from scanning this TODO MVC https://github.com/evancz/elm-todomvc/blob/master/src/Main.elm#L121 it appears to use the paradigm of passing a 'model' object to an 'update' function which could be argued essentially introduces state. If two calls to 'update' can be run concurrently (i.e. called with the same input model) it seems one of them will essentially be ignored, no? (I'm assuming Elm is actually single threaded?)

In shared-mutable-state languages, functions can have side effects. What this means is: there is a global pool of shared mutable state, and any function call can implicitly modify any part of the global state. The key is "implicitly". This behaviour doesn't have to be encoded in the function's type, and you are not required to pass an argument to the function indicating what state it has access to. In a pure functional language, there are no side effects. Instead, all data dependencies are explicit. To transform a piece of state, you pass the state as an argument to a function, it transforms the state, and returns the modified state as a result. (As @Duncan Cragg mentioned a few posts ago.) @Konrad Hinsen: I haven't researched pure functional operating systems. However, I think they would be based on [capabilities](https://en.wikipedia.org/wiki/Capability-based_security). You don't want to put all of your operating system state into a single undifferentiated pool. You want to partition this state into small pieces, and reference them using capabilities. The functional equivalent of a system call would consume one or more capabilities as arguments, modify state referenced by those capabilities, then return zero or more capabilities as results. By "consume", I mean that capabilities would be non-copyable, and once a capability is consumed, the program no longer has access to it. A typical system call would consume a capability, modify the state referenced by the capability, then return a new capability that references the updated state.

@Doug Moen Thanks for the explanations! I did a quick search session on "purely functional operating system", but found nothing but (1) speculation/theory, (2) writing an OS in a functional language, and (3) functional package managers (Nix/Guix).

@Doug Moen just joined and this your top level comment made my day! Mind if I screenshot and share?

@opeispo go ahead

Just an idea: How immutability changes game for types? Let's say you have a tuple and you push there one more item like it would be a list. In mutable world you are just broke original type for everyone who had "tuple reference" already. On immutable world you have no constraint so in it's completely ok to convert between types with modifications. Or should you use hashmap or list of tuples? Effectively those are same if we ignore duplicate keys (and ordering) but we can take those details into account with functions that we use. For example we would have separated functions for list of tupel/hashmap: AddAndKeepDuplicate and AddIfNotExist. If you use latter one hashmap implementation can be used at runtime etc.Sometimes it's nice to know that structure is strictly stack but when doing traditional business glue code in F# I have noticed that there is quite a lot trivial conversions. So what it would look like if we would keep detailed knowledge how to do X in a functions itself instead of data structure?

Does this get into dependent types?

@Daniel Hines I think these ideas can play nicely together but are not strictly related.

Is this lenses? BTW I think eliminating trivial conversions is a nice goal. Most languages fail at this.. FP or not.

@shalabh mm how would you solve trivial conversions with lenses? Easier questions please 😄

It feels like we're discussing polymorphism now. If your system is limited to types which all share the same polymorphic functions, you need less many conversions.

@Niko Autio said So what it would look like if we would keep detailed knowledge how to do X in a functions itself instead of data structure?

@Drewverlee said If you system is limited to types which all share the same polymorphic functions, you need less many conversions.

In "Data Oriented Design", unlike OOP, you represent application data using dumb data structures and generic data types, and you put all of your application logic into functions, instead of into classes. You have far fewer data types, and fewer conversions. The Cell programming language uses relations, rather than objects, to model application data, and it claims benefits for the relational model over the object-oriented model. Once again, you use a small set of generic data types to describe your data, and application logic is separated from the data. Here are the Cell data types: http://cell-lang.net/data.html

The Cell language is DOA IMHO, as it doesn't include any drawing or event primitives in the language. The idea of a language that puts you back to the Terminal era seems retrograde. You gotta at least offer a 2D graphics primitive set so you can make a graphical interactive product. If you are doing pure computation you already have Python and hordes of other such languages.