<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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?</p>
<p>(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.)</p>

<strings><unicode><union-types>
Prior art on modeling characters of variable lengths
CC BY-SA 4.0
2023-09-21T19:06:20.247Z
UTF-16 may be more complicated than you realize.\* Unicode defines more than 2^16 different code points. Not all of them can be represented by a single pair of bytes. https://en.wikipedia.org/wiki/UTF-16 \[\*You wrote, "...two byte pairs..." I wasn't sure whether I should parse that as "two byte-pairs" or as "two-byte pairs."\]
Solomon Slow
CC BY-SA 4.0
2023-09-21T21:25:19.690Z
@SolomonSlow It means, some languages work on two-byte pairs for UTF-16, just like how most languages work on bytes for UTF-8.
user23013
CC BY-SA 4.0
2023-09-22T00:18:13.983Z
Oh Foo! I completely missed what you were _really_ saying, which I guess 
is, that in many programming languages, the run-time support for "string" data types is _unaware_ of encodings, and that they leave the problem of understanding strings at the character-by-character level (as opposed to the byte-by-byte or int16-by-int16 level) to libraries that are not essential to the language itself. Am I right?
Solomon Slow
CC BY-SA 4.0
2023-09-22T07:35:22.163Z
@SolomonSlow Yes.
user23013
CC BY-SA 4.0
2023-10-25T19:16:36.963Z
Does this answer your question? [How have modern language designs dealt with Unicode strings?](https://langdev.stackexchange.com/questions/1493/how-have-modern-language-designs-dealt-with-unicode-strings)
Ginger
CC BY-SA 4.0
2023-10-25T19:48:12.280Z
@Ginger This question is more specific. And it doesn't compare Unicode with single byte encodings as your edit may imply. It compares Unicode implementations which hide the details about characters because some logic about bytes can't be easily extended, and the ones which still have the notion of characters.
user23013
CC BY-SA 4.0
2023-10-28T13:52:12.547Z
Your first sentence is a bit of a muddle, and I'm not sure if it's your understanding that's muddled, or just the way you've phrased it. UTF-8 encodes Unicode code points ("characters", in one definition of that overloaded term) as one to four bytes; it does not encode "ASCII extensions", and it definitely doesn't encode UTF -16, which is a *different* way of encoding the same repertoire of code points. The only relationship to ASCII is that Unicode takes its first 127 code points from ASCII, and UTF-8 is designed such that those have the same binary representation in UTF-8 as ASCII.
IMSoP
CC BY-SA 4.0
2023-10-28T16:16:15.293Z
@IMSoP For some reasons someone thinks it was unclear without that part in the parentheses, and tried to edit it to something else. Now I edited that part out to avoid discussions about the details.
user23013
CC BY-SA 4.0
2023-08-15T18:11:50.807Z
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?
Alexis King
CC BY-SA 4.0
2023-08-15T18:24:50.197Z
@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.
user23013
CC BY-SA 4.0
2023-08-15T18:40:43.593Z
Related/superset?: [How have modern languages dealt with Unicode strings?](https://langdev.stackexchange.com/q/1493/133)
Michael Homer
CC BY-SA 4.0
2023-08-15T21:27:28.250Z
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.
Moonchild
CC BY-SA 4.0
2023-08-15T21:32:03.820Z
@Moonchild Err... yes, but it's still a question for the code point units in encodings such as UTF-8.
user23013
<p>It would certainly be possible to model a string purely as a list of variable length &quot;character&quot; values, e.g. using a linked list structure, or an array of fixed-sized references. However, there is a very strong reason <em>not</em> to implement a language this way: <strong>strings are used much more than characters</strong>.</p>
<p>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 &quot;StringBuilder&quot; optimised for manipulation, vs a &quot;String&quot; optimised for storage and comparison).</p>
<p>Building a &quot;character&quot; 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 <em>backwards</em> to what &quot;character&quot; access is needed.</p>
<p>So, if a &quot;character&quot; (or &quot;code point&quot;, &quot;grapheme&quot;, &quot;rune&quot;, etc) type exists at all, it may well be a wrapper <em>around</em> a string, e.g. a string of its own with a constrained length, or a a special pointer to a &quot;slice&quot; of another string.</p>

CC BY-SA 4.0
2023-10-28T19:36:39.263Z
2023-10-28T19:36:39.263Z
IMSoP
CC BY-SA 4.0
2023-10-28T20:08:54.910Z
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.
Michael Homer
CC BY-SA 4.0
2023-10-28T21:12:29.277Z
@MichaelHomer My intention was to show why it's unlikely to find such an example.
IMSoP
CC BY-SA 4.0
2023-10-28T21:28:10.810Z
Clearly there *are* such examples, though, mentioned elsewhere on this page.
Michael Homer
CC BY-SA 4.0
2023-10-28T21:52:23.930Z
@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.
IMSoP
CC BY-SA 4.0
2023-10-28T22:01:14.830Z
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.
Michael Homer
CC BY-SA 4.0
2023-10-28T22:03:07.003Z
Raku seems to do all the hard parts given here while not bothering to have the actual character type, so not strictly meeting the criteria - that could be relevant too if the modelling is the issue.
Michael Homer
CC BY-SA 4.0
2023-10-28T22:40:13.780Z
@MichaelHomer As I understand it, Swift is an example of the last bullet: the "character" type only exists as a special type of slice when iterating a "view" of the string, it's not actually a constituent of the string. But I agree, I probably haven't linked my argument to the question as well as I could have.
IMSoP
CC BY-SA 4.0
2023-10-28T22:52:58.233Z
Perhaps the question is unclear; I read it as setting up two forks, Swift ticking off both of them, and I don’t read being a storage constituent of the string as part of it, but if it reads differently to you then it may be too ambiguous and need editing. Swift’s Character type is *not* just a string slice, though, it’s an independent data type.
Michael Homer
CC BY-SA 4.0
2023-10-29T07:48:24.763Z
Swift is borderline. And I certainly hopes to see something better. And I intended to at least try to create something if there weren't good examples.
user23013
<p>The main way this is done (with some variation) in modern programming languages is to have your <code>String</code> type store an array of bytes that have special indexing so when you ask for the <code>nth</code> 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.</p>

CC BY-SA 4.0
2023-08-17T15:51:13.457Z
2023-08-17T15:51:13.457Z
Oscar Smith
CC BY-SA 4.0
2023-08-17T18:43:13.560Z
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.
Michael Homer
<p>Two approaches that come to mind would be:</p>
<ol>
<li><p>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 <code>char[]</code> 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.</p>
</li>
<li><p>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 &quot;temporary result&quot; operators may degrade garbage-collection efficiency.</p>
</li>
</ol>
<p>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.</p>

CC BY-SA 4.0
2023-10-24T15:23:45.383Z
2023-10-24T15:23:45.383Z
supercat
<h1>Swift</h1>
<p><a href="https://developer.apple.com/documentation/swift/character" rel="noreferrer">Swift’s <code>Character</code> type</a> represents an extended grapheme cluster. As you mention in your question, this means a single <code>Character</code> can be arbitrarily long.</p>
<p>For more information about how Swift’s strings work, see <a href="https://langdev.stackexchange.com/a/1506">this <em>dramatically</em> more extensive answer</a> by Bbrk24.</p>

CC BY-SA 4.0
2023-08-15T18:31:52.957Z
2023-08-15T19:00:20.537Z
2023-08-15T19:00:20.537Z
Alexis King
CC BY-SA 4.0
2023-08-15T19:29:27.307Z
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.
user23013
# Prior art on modeling characters of variable lengths
Posted by: username_0 on 2023-08-15
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.)
**Tags:** strings unicode union-types
> **Comments:**
> **username_4**: 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?  
> **username_0**: @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.  
> **username_5**: Related/superset?: [How have modern languages dealt with Unicode strings?](https://langdev.stackexchange.com/q/1493/133)  
> **username_6**: 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.  
> **username_0**: @Moonchild Err... yes, but it's still a question for the code point units in encodings such as UTF-8.  
> **username_1**: UTF-16 may be more complicated than you realize.\* Unicode defines more than 2^16 different code points. Not all of them can be represented by a single pair of bytes. https://en.wikipedia.org/wiki/UTF-16 \[\*You wrote, "...two byte pairs..." I wasn't sure whether I should parse that as "two byte-pairs" or as "two-byte pairs."\]  
> **username_0**: @SolomonSlow It means, some languages work on two-byte pairs for UTF-16, just like how most languages work on bytes for UTF-8.  
> **username_1**: Oh Foo! I completely missed what you were _really_ saying, which I guess 
is, that in many programming languages, the run-time support for "string" data types is _unaware_ of encodings, and that they leave the problem of understanding strings at the character-by-character level (as opposed to the byte-by-byte or int16-by-int16 level) to libraries that are not essential to the language itself. Am I right?  
> **username_0**: @SolomonSlow Yes.  
> **username_2**: Does this answer your question? [How have modern language designs dealt with Unicode strings?](https://langdev.stackexchange.com/questions/1493/how-have-modern-language-designs-dealt-with-unicode-strings)  
> **username_0**: @Ginger This question is more specific. And it doesn't compare Unicode with single byte encodings as your edit may imply. It compares Unicode implementations which hide the details about characters because some logic about bytes can't be easily extended, and the ones which still have the notion of characters.  
> **username_3**: Your first sentence is a bit of a muddle, and I'm not sure if it's your understanding that's muddled, or just the way you've phrased it. UTF-8 encodes Unicode code points ("characters", in one definition of that overloaded term) as one to four bytes; it does not encode "ASCII extensions", and it definitely doesn't encode UTF -16, which is a *different* way of encoding the same repertoire of code points. The only relationship to ASCII is that Unicode takes its first 127 code points from ASCII, and UTF-8 is designed such that those have the same binary representation in UTF-8 as ASCII.  
> **username_0**: @IMSoP For some reasons someone thinks it was unclear without that part in the parentheses, and tried to edit it to something else. Now I edited that part out to avoid discussions about the details.  
---
## 4 answers
### Answer by username_4 on 2023-08-15. Score: 9 | Accepted answer
# Swift

[Swift’s `Character` type](https://developer.apple.com/documentation/swift/character) 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](https://langdev.stackexchange.com/a/1506) by Bbrk24.
> **Comments:**
> **username_0** (2023-08-15): 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.  
---
### Answer by username_3 on 2023-10-28. Score: 1
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.
> **Comments:**
> **username_5** (2023-10-28): 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.  
> **username_3** (2023-10-28): @MichaelHomer My intention was to show why it's unlikely to find such an example.  
> **username_5** (2023-10-28): Clearly there *are* such examples, though, mentioned elsewhere on this page.  
> **username_3** (2023-10-28): @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.  
> **username_5** (2023-10-28): 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.  
> **username_5** (2023-10-28): Raku seems to do all the hard parts given here while not bothering to have the actual character type, so not strictly meeting the criteria - that could be relevant too if the modelling is the issue.  
> **username_3** (2023-10-28): @MichaelHomer As I understand it, Swift is an example of the last bullet: the "character" type only exists as a special type of slice when iterating a "view" of the string, it's not actually a constituent of the string. But I agree, I probably haven't linked my argument to the question as well as I could have.  
> **username_5** (2023-10-28): Perhaps the question is unclear; I read it as setting up two forks, Swift ticking off both of them, and I don’t read being a storage constituent of the string as part of it, but if it reads differently to you then it may be too ambiguous and need editing. Swift’s Character type is *not* just a string slice, though, it’s an independent data type.  
> **username_0** (2023-10-29): Swift is borderline. And I certainly hopes to see something better. And I intended to at least try to create something if there weren't good examples.  
---
### Answer by username_7 on 2023-08-17. Score: 1
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.
> **Comments:**
> **username_5** (2023-08-17): 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.  
---
### Answer by username_8 on 2023-10-24. Score: 1
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.
---
