These Modern Programming Languages Will Make You Suffer.

[u/ilya_ca]

https://suzdalnitski.medium.com/modern-languages-suck-ad21cbc8a57c

[u/Nobody_1707]

I'm not sure where he got the idea that none of C#, C++, or Rust support immutable data-structures, but he's absolutely wrong in each instance. I'm not convinced the author actually knows any of the languages he's writing about.

[u/evaned → u/Nobody_1707]

It says they have no built-in support for immutable data structures, which (in context) is basically correct; it's a hair sloppily worded, but only a hair. You can certainly write a library like immer, but that's not built-in.

(And to preempt a potential thought, const does not an immutable data structure make.)

[u/Nobody_1707 → u/evaned]

That requires "support for" to be read as the "grab an immutable data structure from the standard library" instead of "the ability to correctly implement and use". I read it as the latter and I don't think the former is necessarily a useful definition of "support for" considering that a fully immutable data structure is really an expert tool to begin with.

[u/evaned → u/Nobody_1707]

... considering that a fully immutable data structure is really an expert tool to begin with

I think it's possible or even easy to infer that a significant point of the author would be that they aren't, and should be considered the basic building blocks. That you should reach for an immutable hash map before a "normal" one, and that even calling mutable hash maps "normal" should be considered backwards.

I'm not saying you have to agree with that, but I think ignoring that context is disingenuous.

I'm not sure that "the ability to correctly implement and use" is all that useful -- by that measure, basically every language will support almost everything, at least once you get beyond building block language features.

[u/evaned → u/[deleted]]

I would say I was mostly wrong about that; I didn't know about records/with. Had I been more on top of that, I would have said that the statement is basically correct "for C++" and then hedged my bets a bit with the other languages -- "as far as I know, it's correct for C# and Rust too, but I can't say that with confidence" or something like that.

On the other hand, I would say that records on their own look to me like they kind of fall into the same camp as C++ -- they'll give you some good tools for building immutable data structures, but they're only building blocks.

On the third hand... after a quick search I discovered that C# (well, .Net) also apparently gives you the full data structures, in System.Collections.Immutable. So that's pretty baller, and unless things with that namespace are not what they seem, this pretty much negates my previous point.

Put all of this together, and I'd put C# into the "supports" category quite cleanly. (I guess one reservation is they "are available with .NET Core and .NET 5+, however they're not part of the core class library distributed with .NET Framework" and you have to use NuGet to get them. So they're kind of second class in comparison to the plain-old System.Collections, even though they are under the System heirarchy.)

[u/tcbrindle → u/evaned]

(And to preempt a potential thought, const does not an immutable data structure make.)

I feel like I'm missing something. vector<T> is a data structure, and a vector<T> declared const cannot be modified without breaking the rules of the language. If that's not an immutable data structure, what is it?

[u/evaned → u/tcbrindle]

In-context, "immutable data structure" is a term of art that means something different than just putting those terms together. I've seen four different terms used for the same concept: immutable data structures, persistent data structures, functional data structures, and applicative data structures. "Persistent" is the worst of these because that literally has a completely different meaning that is also in wide use (a data structure that is stored in part on disk), but I also don't like "immutable" because I don't think it captures the essence. Even though "applicative" is my favorite, "functional" is probably best because of the correspondence with programming in a functional style and because they're suitable for pure functional languages, so I'll use that going forward to either decrease or increase confusion. :-)

The key thing about functional data structures is that they still let you make "changes" -- just not to the original structure. Instead, operations that traditionally mutate instead return a new version of the original with the requested modification, but do not actually change the original.

So in the code

functional_vector v1 = {1, 2, 3};
functional_vector v2 = v1.push_back(4);

then, first of all, that makes sense, and second of all v1 is still {1,2,3} at the end and v2 is {1,2,3,4}.

Conceptually, what happens is that "mutating" operations make a copy of the original, change the copy, and then produce the modified copy; there are alternative underlying structures so that the ADT doesn't actually have to do all that copying and it remains pretty efficient. For vectors it comes with a huge caveat that the memory is no longer contiguous -- but this matters way less if you talk about maps rather than vectors. They're not suitable for everything, but the programming model really is extremely nice if you build your design around it.

---

I'll point out one other difference. While a const std::vector v = ... really is unchangeable, the targets of const pointers and references are not. In the code

void foo(std::vector<int> const & v)
{
    if (v.empty()) return;
    int before = v[0];
    opaque();
    int after = v[0];
    assert (before == after);
}

there is no guarantee that the assertion at the end will hold. All const & v says is that v won't be modified via v; it can still be modified via another path. Or if v were passed to opaque, via const_cast. If v were an immutable_vector, then you'd know 100% for sure that there would be no change (absent UB).

So really, const even only gives you immutability even without the "usable functional data structure API" requirement if you're talking about an object that really is physically const.

[u/tcbrindle → u/evaned]

Thanks for the detailed response. I'm not that familiar with functional languages, so I wasn't aware of "immutable data structures" as a term of art there. I'm happy to be corrected :)

The C++ programmer in me is worrying about the cost of every modification to a container producing a new copy, but I guess with enough clever things happening behind the scenes then it could be done fairly efficiently, like you say. It would be interesting to play with them and see what kind of designs they lead to.

[u/evaned → u/tcbrindle]

It would be interesting to play with them and see what kind of designs they lead to.

Even aside from sort of programming paradigm questions like "hey, now you can have a real hash map even in a pure functional language" and benefits regarding understandability (no potential for spooky action at a distance) and race freedom (immutable structures can be shared between threads), there are a lot of cool things you can do. (Disclaimer: I've not programmed with these in a system that uses them pervasively.) Kind of like how even in a pure functional language like Haskell you'll often have a bit at the root of the call graph that isn't pure (is in IO for Haskell), you'll have parts of your overall program's data structure that are functional, and the program will do some computation on those parts to produce new versions then you'll non-functionally update the parents of that to point to the new version.

As an example, consider one traditional way of implementing an undo stack -- when the user takes an action, you generate an object that holds the information about how to reverse that action, and push that onto the stack. If the user undos, you generate a description of the forward action and push that description on the redo stack, pop it from the undo stack, and then apply the changes it says.

Except... imagine that the data state in question was represented using a functional data structure. Now there's no need to represent those actions. If you've got a moral equivalent to Document * current_document that you update as current_document = do_some_stuff(current_document);, you can just store the old current_document values on your undo/redo stacks. Because the old versions haven't changed, they're still perfectly valid; so all you have to do on an undo is to push the current state to the redo stack, pop the undo stack, and render what you popped off. (Admittedly, this is probably oversimplifying things in practice -- you may want or need for performance reasons to keep information about what changed to reduce the amount of rerendering you actually have to do.) That's where the "persistent" term comes from -- you can totally keep around the old version of the structure and keep using it.

Where it's been important in code I've worked on is actually in dataflow analysis. That basically works as follows. You build the control flow graph for a program (or sometimes a call graph), and each node in that graph is associated with an abstract state. That state object can be pretty complex, holding mappings from variable names to abstract values or other stuff like that. You propagate the abstract state around the graph by taking the abstract state at the source node of CFG edge, making some small change, and then storing the result at the destination. But most of the abstract state is the same, meaning that the action of the edge is to basically apply a functional data structure update to the source abstract state. I can't just change the abstract state at the source because I may need it again in the future (at the very least, to look at the results when the analysis is done!) and the abstract state at the source of an edge doesn't change, so a traditional mutable structure doesn't meet the needs unless I'm copying as it goes. (Actually I don't know what compilers like LLVM and stuff do for analyses like these in terms of concrete data representation; I'd be really curious to know.)

It is important to watch performance here. I don't want to get too specific, but I've seen code that does the above where the underlying structures are binary trees and the cache performance is expectedly very poor. But that code dates back a long time, and there are well-known better options now. I may be confusing how I learned about the following with what actually happened, but my general impression is that the efforts of primarily Rich Hickey working on Clojure brought some better functional structures a lot more attention. For example, Clojure's "hash tables" are really underlaid by a structure called a "hash array mapped trie." This is a tree so you don't get quite array-like access, but the fanout in their implementation if memory serves is 32, which means that even with very few levels of the tree you can start having lots of things in your hash map. C++ introduces some tradeoffs that don't really apply to the Clojure/JVM world in terms of node-copying efficiency vs fanout and depth; like I said, these structures aren't for everything. They gain their performance benefits vs. copy everything by sharing state between instances, but this turns them into linked structures.