12
$\begingroup$

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.)

$\endgroup$
13
  • 1
    $\begingroup$ I’m not sure I understand the question: isn’t Raku an example of a “previous attempt to make variable length encodings internally supported, while also have a character type that could refer to such a variable length character in a string”? Or are you just looking for other examples? $\endgroup$
    – Alexis King
    Aug 15, 2023 at 18:11
  • $\begingroup$ @AlexisKing I don't know Raku that much, and only found it for this question. But as how I understand it, it doesn't seem to have a character type. Of course Unicode processing could be done well using indexes in many languages. But I'm looking for cases where the variable length characters are modeled as an actual type in the language's design in string processing. $\endgroup$
    – user23013
    Aug 15, 2023 at 18:24
  • $\begingroup$ Related/superset?: How have modern languages dealt with Unicode strings? $\endgroup$
    – Michael Homer
    Aug 15, 2023 at 18:40
  • $\begingroup$ I don't think you are likely to see very much, if anything, that works like this, because these 'characters' likely won't behave the way you expect. For instance, if you catenate two grapheme clustres, the result may be a single grapheme clustre. So it's not clear what value a 'character' abstraction would provide. $\endgroup$
    – Moonchild
    Aug 15, 2023 at 21:27
  • $\begingroup$ @Moonchild Err... yes, but it's still a question for the code point units in encodings such as UTF-8. $\endgroup$
    – user23013
    Aug 15, 2023 at 21:32

4 Answers 4

9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ While I don't think strings are internally stored as a list of characters as I originally expected in the question in Swift, the good idea is views. With views I could indeed simulate any expected behaviors, and get the implementation details encapsulated. It doesn't provide tools like type-checking for programmers to implement similar things in this language, though. $\endgroup$
    – user23013
    Aug 15, 2023 at 19:29
1
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ I think the question is about a character type, which this answer does not address. It also seems to half-conflate bytes and characters in the indexing section, but without addressing the type issue I don’t think the rest matters. $\endgroup$
    – Michael Homer
    Aug 17, 2023 at 18:43
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ This question asks for prior art; you’ve described a rationale here, but not identified any previous work in the terms of the question currently. $\endgroup$
    – Michael Homer
    Oct 28, 2023 at 20:08
  • $\begingroup$ @MichaelHomer My intention was to show why it's unlikely to find such an example. $\endgroup$
    – IMSoP
    Oct 28, 2023 at 21:12
  • $\begingroup$ Clearly there are such examples, though, mentioned elsewhere on this page. $\endgroup$
    – Michael Homer
    Oct 28, 2023 at 21:28
  • $\begingroup$ @MichaelHomer It seemed to me that the examples being given didn't match what the question was asking for, and this was my attempt to explain why. Maybe I've misunderstood the question. $\endgroup$
    – IMSoP
    Oct 28, 2023 at 21:52
  • $\begingroup$ The core stated question seems to be “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?”, which Swift certainly seems to be an example of (internal variable-length encodings: yes; has a character type representing these: yes). This answer might make the case that that’s incorrect and it’s actually impossible to do this, which would be a valid frame challenge, but it doesn’t quite get to that point either. $\endgroup$
    – Michael Homer
    Oct 28, 2023 at 22:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .