This makes it sound like you’re saying that’s why functional programming was created, which isn’t the case. I assume you mean that this is why it’s gained popularity but I don’t really agree with that - it’s certainly valuable but most functional programmers will never touch threads. I’d argue that programs without state are just easier to reason about and debug and for most software this is where the value comes from.

Right, isn't the fundamental trade-off between programmer efficieny and runtime efficiency?

Immutable structures are easier to reason about, but almost always run slower than their mutable counterparts.

The holy grail would be immutable structures that are equally performant, but I'm not sure that's even mathematically possible in general.

In Scala you can add a "@tailrec" annotation to recursive functions. The annotation means that the function is guaranteed to recurse efficiently (without growing the stack) OR that the compiler will give an error telling you why it can't be guaranteed. I could imagine a similar annotation like "@withmutation" for functions where you want to guarantee efficient in-place mutation at runtime. As it is, when I run into performance pain points in Scala I redo the critical bits with (manually written) while-loops and imperative mutation.

[1] Unless you later attach a debugger and expect to be able to observe V1 and V2 simultaneously. But I presume this sort of issue already comes up and is somehow dealt with regarding other compiler optimizations.

Haskell didn't invent linear types. Eg Clean had them for ages to do IO. (They didn't use Monads in Clean.)

When eg a Haskell program runs, its supposedly immutable datastructures get mutated all the time. For example laziness is one way that happens.

Another example is that a (pure) Scheme program will overwrite the same memory addresses over and over again while it is running, just like a C program would. Conceptually, no mutation happens, it's just that the garbage collector constantly frees up memory that will be get re-used immediately.

There are many cases where there won't be a single difference in performance and there are a bunch of cases where immutable structures will be way faster than mutable ones.

Have you maybe written this backwards? It's literally not possible for this to be true.

Mutable data structures have strictly more operations that they're allowed to do, how would they be slower? At very worst they could ignore modifications and be exactly as fast as an immutable data structure.

When you need a state that you can rollback, an immutable data structure lets you share the parts of the structure that didn't change between states. That's what ZFS does and that's also how many transactional databases store data.

A mutable data structure would need an entire copy at each state change or it would need to store deltas and apply them backwards when you rollback. Both options are significantly slower than the immutable data structure (where rollback means updating a single pointer).

And I'm pretty sure that if ZFS creates an updated version of some immutable node, under the hood it does this via something that resembles a memcpy() followed by a mutable modification of one or more struct members.

Also no one claims there's one immutable data structure that's faster than all mutable data structures. That's a ridiculous strawman argument.

I'm talking about the internal implementation of those data structures, not about their API. Neither C nor C++ have built-in immutable data structures, so those persistent data structures with their immutable API are implemented using mutable C structs or C++ classes.

> Also no one claims there's one immutable data structure that's faster than all mutable data structures. That's a ridiculous strawman argument.

No, you're misunderstanding what I said: For any given abstract functionality or interface (like a key->value map, or a graph composed of vertices and edges), there exists a mutable data structure which is at least as fast as all immutable data structures that provide the same interface. That's because the set of mutable data structures is a strict superset of (i.e., contains all) the set of immutable data structures.

First of all, yes they do, you can use const on structs and objects and methods to ensure your C/C++ data structure is immutable.

But this is moot anyway:

> so those persistent data structures with their immutable API are implemented using mutable C structs or C++ classes

ZFS isn't something that's in memory, it's a file system… It's a data structure on disk, it's language-agnostic.

> That's because the set of mutable data structures is a strict superset of (i.e., contains all) the set of immutable data structures.

In theory, that's true. It's just a useless fact.

We use immutable data structures because they have benefits. Using the same data structure without immutability may just render it worse as a software tool. So people don't use immutable data structures with the immutability removed.

Immutable data structures are shaped by trade-offs like any other design.

The most obvious operation that's much faster for an immutable data structure is cloning.

Cloning, say, an array in a mutable system takes O(n) time. Cloning in an immutable system is just returning the pointer (or whatever pointer + length struct you're using to represent an array).

Cloning a mutable array is also O(1) if you use copy-on-write.

Yes. Yes it is. The structures have different performance characteristics for different operations.

Note that this is just an example of the idea that mutable structures can achieve anything immutable structures can, by just treating them as if they're immutable. While you're using copy-on-write, your mutable array can be cloned in constant time and updated in linear time, presenting the exact characteristics of an immutable array.

The mutable "equivalent" algorithm is much nastier, though, since, after you do the cloning, you'll need to create the new object (the slow, O(n) clone) as soon as you want to update either the new structure or the old one. In the functional paradigm, this is also the case -- but you're always generating a new object that you're about to use, as opposed to generating a new object because something else somewhere else in the code was watching you. For example, if you have an array, and you update it (forcing it to be realized), and then you update it a second time, you can't rely on the first time you updated it to prove that the second update will be fast. Maybe it was cloned between the updates.

Even when you aren't writing concurrent code, mutability will prevent the CPU from using its internal concurrency to execute it faster.

Also, immutable data structures can include caches that are extremely simple whereas mutable data structure would face the problem if cache invalidation if they tried.

And a mutable data structure that would operate as if it's immutable? That's a nice recipe for an epic disaster.

Do you mean to say the compiler will insert locks? As far as I'm aware, on AMD64/Intel64, the processor won't lock the bus for ordinary loads and stores unless an instruction has the lock prefix. The processor is otherwise perfectly happy to let different cores observe loads and stores to different addresses in different orders (except for stores being reordered past each other).

> Even when you aren't writing concurrent code, mutability will prevent the CPU from using its internal concurrency to execute it faster.

For an out-of-order superscalar machine, mutability has nothing to do with it; register renaming takes care of that. The things to watch out for are tight dependencies chains.

If you're referring to loads and stores, store-forwarding and coalescing can spare you from having to hit the cache repeatedly for reads and writes to the same location.

I think you're right, it's the compiler that'll insert the locks according to the semantics of the language.

> For an out-of-order superscalar machine, mutability has nothing to do with it;

Yes it does, because it creates data dependencies. If a piece of code B loads the contents of memory where a piece of code A writes that's before B, then you can never execute B before or in parallel with A.

This is a description of what a data dependency is; I'm still not sure what your point is regarding mutable data structures specifically.

Now, call it mutable, but don't change a thing. Congratulations, it's now a mutable data structure that's exactly as fast as your favorite immutable one.

_But_ you now have extra opterations you can perform to optimize slow parts if you can. You have strictly more power than you started with, because you can modify data. You don't have to, but you can.

Just don't make any bad optimizations. If some attempt to make it better instead makes it worse, go back to the starting point and try something else.

The point is that this procedure applies to anything. Immutable data structures are a strict subset of mutable ones. Every immutable data structure is open to moving any number of steps, in any direction, in the space of data structures. It's _purely_ extra freedom that immutable data structures don't have.

If you want specific ones, first things that would come to mind for me is to start with any immutable tree impl, and start adding small mutable ~caching things on top. Batch up updates a bit to try to avoid repeated deep traversals maybe. You can do this without adding much complexity at all, and it's very flexibly for whatever operations or access patterns you want to improve.

I get that you can imagine it. I'm saying it wouldn't work in practice.

No it won't, not at the myriads of places they're needed when there are mutations all over the place.

Of course there are mutations in FP, so of course sometimes we need write locks and use things like CAS.

The point is not that FP doesn't use them, but that it uses them far less because they are needed only in a very limited number of places.

When I write code with STM, for example, the only uses of locks or CAS are in the STM engine, not in my Haskell code, and not even in my compiled code, because my code only ever reads memory that's immutable, and immutable data structures.

When I write pure code, there are no locks at all. And that makes it trivial to execute in parallel, either out of order or on several cores.

And why are you saying that requiring more memory would make a program slower? I don't see the link.

At the hardware level, transforming a numerical array M1 into M2 by mutation in-place requires a certain number of memory reads and writes. Leaving the old matrix M1 untouched and returning M2 as a new value (in the immutable style) means that you require at least as many memory accesses as before, but cache locality is likely worse because you're not updating the same address region you are reading from. So I'd expect numerical simulations based on immutable programming techniques to run slower than current simulation tools (like NAMD, AMBER, GROMACS) that perform mutation in-place.

I'd be interested to see benchmarks.

> Functional programming is a reaction from the shift to the dangerous quadrant of the immutable-mutable/unshared-shared "Magic Quadrant" chart.

I might rather say "The recent focus on adapting functional programming is a reaction...". Functional programming itself is nearly as old as the modern computer (McCarthy's first LISP paper was published in 1960), but your phrasing kind of suggests that the entirety of FP is a recent innovation.

What's new is the scale of software being developed right now. Developers simply can't afford to create mutable and shared state as if their program was just another desktop program, executed on a computer disconnected from the internet.

Sooner or later we learn that focusing on the human value of code (I mean, making the code clear, concise and simple to read) pays off way better on the long run rather than optimizing for CPU cycles or memory footprint.

It's a shame D's pure modifier (to statically guarantee purity) isn't available in many other languages. [0] SPARK Ada has something similar in that functions must always be pure, forcing procedures to be used for impure functionality. [1] edit I think that's mistaken, SPARK appears to permit functions to read globals but not to modify them.

edit John Carmack has written about this kind of thing. From [2]:

> if a function only references a piece or two of global state, it is probably wise to consider passing it in as a variable. It would be kind of nice if C had a "functional" keyword to enforce no global references.

[0] https://dlang.org/spec/function.html#pure-functions

[1] https://learn.adacore.com/courses/intro-to-spark/chapters/01...

[2] https://cbarrete.com/carmack.html

  // 500 variables shared by everything
  main loop
    "task" 1
    "task" 2
    "task" 3
    ...
    "task" n

There's also more basic stuff like IORef which represents an assignable variable [2]. Again, you're constrained to use this in IO contexts.

Etc.

Haskell basically just forces you to do that thing someone else in this thread mentioned: Write functional APIs, allow side effects but make them explicit and confined to very specific places.

[1]: https://hackage.haskell.org/package/primitive-0.7.4.0/docs/s... [2]: https://hackage.haskell.org/package/base-4.16.3.0/docs/Data-...

Sure it was. While it didn't force devs to stop using mutable state, you just called out that it -did- force them to move that state out of the service and into something with ACID guarantees, and write their server code in a way that was far more stateless. That sounds like a win to me?

Saying "that tends to ensure what is and isn't side effect free is massively obfuscated" really depends on the ORM; if it's an ORM that tries to make an RDMBS "quick" like an object, then I agree (this is something I hate about Django's ORM), but if it's a query builder style ORM then I disagree, as it basically creates a DSL that wraps around the SQL which is already purely functional.

What I'm getting at is that we shouldn't conflate what should take credit for creating sanity in how applications persist state. I think that credit should go to the RDBMS because it exposes the power of the benefits you ascribe to FP, to any programming language that can bind to an RDBMS. If that is the case, what do you really need FP for in general purpose line of business software engineering?

The change is technically in your call stack, but it’s indirect and not necessarily related to your code.

If it were immutable data, then some distant code that holds a reference can’t mutate it unless that data is explicitly marked as mutable.

To me, immutable data is a guarantee that a variable keeps its value, unless I explicitly say it can change (eg by wrapping it in a mutable “box” whose content can be changed). This way, I always know whether I’m giving something write access or only read access. Technically this can be achieved without immutable types (eg constant parameters, pass by value or just documented API promises) but having immutable data as per of the language gives an extra layer of guarantee that’s harder to violate and therefore more predictable.

That is why I like immutable by default, even in single threaded code.

The solutions to concurrency pretty much all involve staying out that quadrant as much as possible. Immutability isn't the only solution. Another is to confine all variables to one thread. Erlang, for instance, superficially uses immutability to achieve this, but a deeper reason it achieves it is that there is simply no way for a "thread" (what Erlang calls "process") to modify a variable that another thread can see; this is sufficient. (See what Elixir does.) Rust implements a super-rich system of variable ownership that allows you to implement the constraint that no variable can be unexpectedly just modified by an arbitrary thread in a far richer fashion than just hard-locking all memory to a particular owner thread. This is also sufficient. I program a lot in Go, and while it lacks compiler support for forcing you to stay out of that quadrant, my code runs at high concurrency rates precisely because I've learned how to stay out of there, and my code looks very Erlang-ish when you look at the concurrency patterns in play.

An unfortunate overreaction, I agree.

Does everything have to become dumb to make it safe?

I don’t think trying to avoid shared mutable state is dumb. It’s deliberately choosing a safer default, just like not allowing all references to be null or not accepting the string "123" where an integer like 123 is needed.

Sometimes it can be useful to have shared mutable state, or to make a reference nullable, or to accept different types of data and quietly reinterpret them the same way internally. But these are inherently more dangerous styles of programming — they create opportunities for mistakes that are otherwise systematically prevented — so it seems reasonable to encourage the safer alternatives unless there is a good reason not to use them, and to make the more dangerous choices the ones you have to make explicitly.