Frozen String Literals: Past, Present, Future?

In C, C++, and Rust, the question of "are strings in this language mutable or immutable?" isn't applicable, because those languages have transitive mutability qualifiers. So they only need a single string type, and whether you can mutate it or not depends on context. (C++ and Rust have multiple string types, but the differences among them aren't about mutability.) In languages without this feature, a given value is either always mutable or never mutable, and so it's necessary to pick one or the other for string literals.

Python strings aren’t even proper Unicode strings. They’re sequences of code points rather than scalar values, meaning they can contain surrogates. This is incompatible with basically everything: UTF-* as used by sensible things, and unvalidated UTF-16 as used in the likes of JavaScript, Windows wide strings and Qt.

> can be any of latin-1, UCS-2 or UCS-4, as described in PEP 393

My bad, I haven't seriously used Python for over 15 years now, so I stand corrected (and will clarify the post).

My main point stands though, Python strings have an internal representation, but it's not exposed to the user like Ruby strings.

> Article also says PHP has immutable strings. They are mutable, although often copied.

Same. Thank you for the correction, I'll update the post.

> There must surely be programs doing a lot of string building or in-place modification that would benefit from non-frozen.

The point is that the magic comment (or the --enable-frozen-string-literal) only applies to literals. If you have some code using mutable strings to iteratively append to it, flipping that switch doesn't change that. It just means you'll have to explicitly create a mutable string. So it doesn't change the performance profile.

In general, Ruby does allow mutable values in hash tables, with basically those semantics: https://docs.ruby-lang.org/en/3.4/Hash.html#class-Hash-label...

The copy-and-freeze behavior is a special case that applies only to strings, presumably because the alternative was too much of a footgun since programmers usually think of strings in terms of value semantics.

I don't think anyone likes the explicit .freeze calls everywhere; I think the case for frozen strings in Ruby is primarily based on performance rather than correctness (which is why it wasn't obvious earlier in the language's history that it was the right call), and the reason it's hard to make the default is because of compatibility.

> just document that the behavior becomes unspecified if keys are mutated while they are in the table.

> Make sure the behavior is safe: it won't crash or be exploitable by a remote attacker.

There is no such thing as unspecified but safe behaviour. Developers who can't predict what will happen will make invalid assumptions which will lead to security vulnerabilities when they are violated.

> Another solution is to put concatenation into your string type

Aah, the Erlang way of handling strings.

On Beam (Erlang's VM), that goes as deep as IO. It's perfectly fine to pass a (possibly nested) list of strings (whether charlists or binaries) to an IO function, and the system just knows how to deal with that.

> As noted a paragraph later, the Java compiler is able to detect and “fix” this, by rewriting the code to use a mutable string.

Does it actually do that nowadays? Back in my days it was incapable of lifting the builder out of loops, so for each iteration it would instantiate a builder with the accumulator string, append the concatenation, then stringify and reset the accumulator.

The linked docs don’t say anything about loops.

An option you did not mention, although not generally available to languages with advanced runtime, is that even if you have immutable strings you can realloc them if you know you're the only owner of that string (e.g. because they're refcounted, or can't be shared).

CPython does that, so a trivial concatenation loop is (amortised) linear (causing issues for alternate implementations when they have to run that). Swift might also be able to via COW optimisation.

Rust's string concatenation is a variant of this (though it has mutable strings anyway): `String::add` takes an owned value on the LHS, and the implementation just appends to the LHS before returning it:

    fn add(mut self, other: &str) -> String {
        self.push_str(other);
        self
    }

so repeated concatenation will realloc and amortize as if you were just `push_str`-ing in a loop (which maps directly to appending to the underlying buffer).

  impl AddAssign<&str> for String {
      #[inline]
      fn add_assign(&mut self, other: &str) {
          self.push_str(other);
      }
  }

  class str:
      def __iadd__(self, other):
          if sys.getrefcount(self) == probably 2, it’s fiddly:
              mutate self
          raise NotImplemented

Maybe I'm missing something, but I thought that when you "grow" an array or a string, eventually something under the hood needs to call realloc()? which allocates a bigger chunk of memory and copies the content O(n)? Why would it matter if you manually do alloc() and then memcpy() (replacing an immutable string with its concatenation) vs letting the runtime do it for you with realloc()?

You're basically describing the Rope. Fancier versions use self balancing trees, allowing other string operations to be fairly efficient too.

https://en.wikipedia.org/wiki/Rope_(data_structure)