Prior art on modeling characters of variable lengths

Question

In some encodings such as UTF-8, characters are of variable length in bytes. It's a bit like a tagged union, but the exact size could be computed, so the next element in a string could follow immediately, with the cost of making it almost read-only, with few, but necessary exceptions.

Many languages just work on the bytes (or two-byte pairs for UTF-16), that is, incomplete characters, and defer Unicode-related operations to libraries. Many other languages don't expose low-level interfaces for characters in strings, and use 1-character strings to represent characters when the notion of characters is needed. Some other languages make stand alone characters a different thing of fixed lengths from characters in strings.

There are also languages like Raku, which change the idea of characters to refer to grapheme clusters, so a zalgo character could be in arbitrary length, making it more complicated.

Are there previous attempts to make variable length encodings internally supported, while also having a character type that could refer to such a variable length character in a string?

(I'm thinking about the question more like how tagged unions aka sum types could be extended, instead of how strings should be implemented, which might be acceptable as a special case otherwise.)

Answer 1

Swift

Swift’s Character type represents an extended grapheme cluster. As you mention in your question, this means a single Character can be arbitrarily long.

For more information about how Swift’s strings work, see this dramatically more extensive answer by Bbrk24.

Answer 2

The main way this is done (with some variation) in modern programming languages is to have your String type store an array of bytes that have special indexing so when you ask for the nth element of the string, you get the character starting at the nth byte. The downside of this is you don't get O(1) character indexing (but it turns out you generally don't need this), but the upside is that your string is memory efficient (as opposed to UTF-32) and doesn't require re-formatting when you read/write strings to files or the web.

Answer 3

Two approaches that come to mind would be:

1. Allow an immutable string type to hold an array of bytes, halfwords, or words, depending upon whether all code points are within the range 0..0x7F or 0..0xFFFF. This will be somewhat inefficient for handling a strong that contains a million code points in the range 0..0x7F and one outside the range 0..0xFFFF, but for many purposes this approach can work well. I think it's a shame that Java didn't adopt this approach since using a char[] backing array for ASCII text doubles the caching footprint, and the cost of that will often exceed the cost of dispatch to select byte-based versus half-word-based string code.

2. Allow an immutable string type to hold an array of references to string segments, along with an optional array of the starting offsets thereof within the larger string, whose storage method may be determined individually. This can work well if the programming language provides separate operators that produce strings which are likely to be persisted, versus strings which are likely to be used only temporarily. The observable semantics of both operators would be identical, but inappropriate use of the "temporary result" operators may degrade garbage-collection efficiency.

Although most benefits from the latter approach would have nothing to do with the ability to mix character encodings, allowing composite strings to have different portions use different encodings would be relatively trivial once they can be assembled from nested composite strings.

Answer 4

It would certainly be possible to model a string purely as a list of variable length "character" values, e.g. using a linked list structure, or an array of fixed-sized references. However, there is a very strong reason not to implement a language this way: strings are used much more than characters.

Many languages or language implementations spend a lot of time looking at how strings can be implemented more efficiently, in terms of memory, access, modification, and so on. They may have multiple internal representations, either transparent to the user, or exposed as different types (e.g. a "StringBuilder" optimised for manipulation, vs a "String" optimised for storage and comparison).

Building a "character" type first, then combining multiple characters into a string, makes for a nice abstraction on paper, but is very impractical for these optimisations. It's much more useful to start at the other end - how to efficiently work with strings - and then work backwards to what "character" access is needed.

So, if a "character" (or "code point", "grapheme", "rune", etc) type exists at all, it may well be a wrapper around a string, e.g. a string of its own with a constrained length, or a a special pointer to a "slice" of another string.