6 ms·

Can you explain how you think strings should work?

deleted 3y ago
[deleted]
klodolph 3y ago
I think the main alternative design is to treat strings like in Rust or Go. The problem with the “array of code points” idea is that you end up with the most general implementation, which is a UTF-32 string, and then you end up with the fastest implementation, which is a UTF-8 string, and maybe throw in UCS-2 for good measure. These all have the same asymptotic performance characteristics, but allow ASCII strings (which are extremely common) to be stored with less memory. The cost is that now you have two or three different string representations floating around. This approach is used by Python and Java, for example. The Rust / Go approach is to assume that you don’t need O(1) access to the Nth code point in a string, which is probably reasonable, since that’s rarely necessary or even useful. You get a lot of complexity savings from only using one encoding, and the main tradeoff is that certain languages take 50% more space in memory. Python and Java both date back to an era where fixed-width string encodings were the norm.
- gautamcgoel 3y ago
  Thanks for your response. Personally I fall into the "strings are arrays of bytes" camp (which is also shared by Go). A difference between my view and that of the Go designers is that I don't feel that it is important to support Unicode by default and am perfectly happy to assume that every character corresponds to a single byte. Obviously that makes internationalization harder, but the advantage is that strings are much simpler to reason about. For example, the number of characters in the string is simply the length of the string. I would be fine having a separate Unicode string type in the standard library for those instances when you really need Unicode; this design makes the common case much simpler at the expense of making the rare case harder. I also don't see that mutability is such a huge deal unless you absolutely insist that your language support string interning.
  - saghm 3y ago
    "strings are arrays of bytes" combined with the assumption that "characters are a single byte" sounds basically the same as the "array of code points" that the parent comment is disagreeing with
    - foolswisdom 3y ago
      Code points are not bytes.
      - saghm 3y ago
        Sure, but if you're insisting that the string be represented as one byte per character, you end up with the exact same properties with "array of code points" and "array of bytes"
        bruce511 3y ago
        Sort-of, but no, because code points are not characters. There's a big difference between "get the 5th code point" and "get the 5th character". Because multiple code points can be used in a single character, it not possible to do random-character-access in a unicode-encoded string.
        foolswisdom 3y ago
        No, it's impossible to do random access to retrieve a character, if you are dealing with code points, because code points do not have a fixed byte size. I thought this a good intro <https://tonsky.me/blog/unicode/ https://tonsky.me/blog/unicode/>.
  - bschwindHN 3y ago
    > this design makes the common case much simpler at the expense of making the rare case harder In the age of emoji (and uhhhh, everyone who doesn't use English as their main language), I don't think your "rare case" is really that rare.
- tayo42 3y ago
  Working with strings is one of the most common complaints about rust though. Unless your only talking about the implemtation of it?
  - klodolph 3y ago
    Would love to hear what you think the complaints come from. They seem fine to me, and I have voiced plenty of criticism about the other parts of Rust. They work more or less how I expect—you have an array of bytes, which can either be a reference (&str) or owned / mutable / growable (String). The only unusual thing about Rust is that it validates that the bytes are UTF-8.
    - tayo42 3y ago
      Mostly around usability and learning curve. I wasnt sure if the post was meant as a total endorsement of rusts strings or just the encoding aspect of them
  - dralley 3y ago
    What people complain about with Rust strings are that there are so many different types, like &str vs String, and OsString / OsStr. The encoding of the strings isn't the issue.
    - csande17 3y ago
      Encoding might not be the whole issue, but "Rust mandates that the 'string' type must only contain valid UTF-8, which is incompatible with every operating system in the world" is the reason why OsString is a separate type.
      - dralley 3y ago
        The only encoding which is compatible with "every operating system in the world" is no enforced encoding at all, and you can do very little "string-like" operations with such a type. Even Python, well-known for being a very usable language, distinguishes between strings (which are unicode, but not utf-8 necessarily) and bytes, which you need to use if you're interacting directly with the OS. The only real difference between the two is really the looseness with which Python lets you work with them, by virtue of being dynamically typed and having a large standard library that papers over some of the details.
- neonsunset 3y ago
  Rust and Go string implementations are very different. Rust strings are safe, have rich API and prevent you from corrupting their contents unless you go out of your way to do so. Go strings are a joke and won't do any validation if you slice them incorrectly and are extremely bare bones.
o11c 3y ago
Unfortunately, strings cross at least 3 different problems: * charset encoding. Cases worth supporting include Ascii, Latin1, Xascii, WeirdLegacyStatefulEncoding, WhateverMyLocaleSaysExceptNotReally, UTF8, UTF16, UCS2, UTF32, and sloppy variants thereof. Note that not supporting sloppiness means it is impossible to access a lot of old data (for example, `git` committers and commit messages). Note that it is impossible to make a 1-to-1 mapping between sloppy UTF-8 and sloppy UTF-16, so if all strings have a single representation (unless it is some weird representation not yet mentioned), it is either impossible to support all strings encountered on non-Windows platforms, or impossible to support all strings encountered on non-Windows platforms. I am a strong proponent of APIs supporting multiple compile-time-known string representations, with transparent conversion where safe. * ownership. Cases worth supporting: Value (but finite size), Refcounted (yes, this is important, the problem with std::string is that it was mutable), Tail or full Slice thereof, borrowed Zero-terminated or X(not) terminated, Literal (known statically allocated), and Alternating (the one that does SSO, switching between Value and Refcounted; IME it is important for Refcounted to efficiently support Literal). Note that there is no need for an immutable string to support Unique ownership. That's 8 different ownership policies, and if your Z/X implementation doesn't support recovering an optional owner, you also need to support at least one "maybe owned, maybe borrowed" (needed for things like efficient map insertion if the key might already exist; making the insert function a template does not suffice to handle all cases). It is important that, to the extent possible, all these (immutable) strings offer the same API, and can be converted implicitly where safe (exception: legacy code might make implicit conversion to V useful, despite being technically wrong). (there should be some Mutable string-like thing but it need not provide the API, only push/pop off the end followed by conversion to R; consider particularly the implementation of comma-separated list stringification) * domain meaning. The language itself should support at least Format strings for printf/scanf/strftime etc. (these "should" be separate types, but if relying on the C compiler to check them for you, don't actually have to be). Common library-supported additions include XML, JSON, and SQL strings, to make injection attacks impossible at the type level. Thinking of compilers (but not limited to them), there also needs to be dedicated types for "string representing a filepath" vs "string representing a file's contents" (the web's concept of "blob URL" is informative, but suffers from overloading the string type in the first place). Importantly, it must be easy to write literals of the appropriate type and convert explicitly as needed, so there should not be any file-related APIs that take strings. (related, it's often useful to have the concept of "single-line string" and "word" (which, among other cases, makes it possible to ); the exact definition thereof depending on context. So it may be useful to be able to tag strings as "all characters (or, separately, the first character or the last character (though "last character" is far less useful)) are one of [abc...]"; reasonably granularity being: NUL, whitespace characters individually, other C0 controls, ASCII symbols individually, digit 0, digit 1, digits 2-7, digits 8-9, letters a-f, letters A-F, letters g-z, letters G-Z, DEL, C1 controls, other latin1, U+0100 through U+07FF, U+0800 through U+FFFF excluding surrogates, low surrogates, high surrogates, and U+10000 through U+10FFFF, and illegal values U+110000 and higher (maybe splitting 31-bit from 32-bit?) (several of these are impossible under certain encodings and strictness levels). Actually supporting all of this in the compiler proper is complicated and likely to be deferred, but thinking about it informs both language and library design. Particularly, consider "partial template casting")
chubot 3y ago
The short answer is somewhere between Go and Rust strings, which are newer languages that use UTF-8 for interior representation, and also favor it for exterior encoding. Roughly speaking, Java and JavaScript are in the UTF-16 camp, and Python 2 and 3 are in the code points camp. C and C++ have unique problems, but you could also put them in the code points camp. So there are at least 3 different camps, and a whole bunch of weird variations, like string width being compile-time selectable in interpreters. More details here: https://www.oilshell.org/blog/2023/06/ysh-design.html#text https://www.oilshell.org/blog/2023/06/ysh-design.html#text and here: https://www.oilshell.org/blog/2023/06/surrogate-pair.html#history-windows-infected-javascript-json-and-python https://www.oilshell.org/blog/2023/06/surrogate-pair.html#hi... A main design issue is that string APIs shouldn't depend on a mutable global variable -- the default encoding, or default file system encoding. That's an idea that's a disaster in C, and also a disaster in Python. It leads to buggy programs. Go and Rust differ in their philosophies, but neither of them has that design problem.
librasteve 3y ago
Raku introduced the concept of NFG - Normal Form Grapheme - as a way to represent any Unicode string in its logical ‘visual character’ grapheme form. Sequences of combining characters that don’t have a canonical single codepoint form are given a synthetic codepoint so that string methods including regexes can operate on grapheme characters without ever causing splitting side effects. Of course there are methods for manipulating at the codepoint level as well.

deleted 3y ago

[deleted]

I think the main alternative design is to treat strings like in Rust or Go. The problem with the “array of code points” idea is that you end up with the most general implementation, which is a UTF-32 string, and then you end up with the fastest implementation, which is a UTF-8 string, and maybe throw in UCS-2 for good measure. These all have the same asymptotic performance characteristics, but allow ASCII strings (which are extremely common) to be stored with less memory. The cost is that now you have two or three different string representations floating around. This approach is used by Python and Java, for example. The Rust / Go approach is to assume that you don’t need O(1) access to the Nth code point in a string, which is probably reasonable, since that’s rarely necessary or even useful. You get a lot of complexity savings from only using one encoding, and the main tradeoff is that certain languages take 50% more space in memory. Python and Java both date back to an era where fixed-width string encodings were the norm.

gautamcgoel 3y ago
Thanks for your response. Personally I fall into the "strings are arrays of bytes" camp (which is also shared by Go). A difference between my view and that of the Go designers is that I don't feel that it is important to support Unicode by default and am perfectly happy to assume that every character corresponds to a single byte. Obviously that makes internationalization harder, but the advantage is that strings are much simpler to reason about. For example, the number of characters in the string is simply the length of the string. I would be fine having a separate Unicode string type in the standard library for those instances when you really need Unicode; this design makes the common case much simpler at the expense of making the rare case harder. I also don't see that mutability is such a huge deal unless you absolutely insist that your language support string interning.
- saghm 3y ago
  "strings are arrays of bytes" combined with the assumption that "characters are a single byte" sounds basically the same as the "array of code points" that the parent comment is disagreeing with
  - foolswisdom 3y ago
    Code points are not bytes.
    - saghm 3y ago
      Sure, but if you're insisting that the string be represented as one byte per character, you end up with the exact same properties with "array of code points" and "array of bytes"
      - bruce511 3y ago
        Sort-of, but no, because code points are not characters. There's a big difference between "get the 5th code point" and "get the 5th character". Because multiple code points can be used in a single character, it not possible to do random-character-access in a unicode-encoded string.
      - foolswisdom 3y ago
        No, it's impossible to do random access to retrieve a character, if you are dealing with code points, because code points do not have a fixed byte size. I thought this a good intro <https://tonsky.me/blog/unicode/ https://tonsky.me/blog/unicode/>.
- bschwindHN 3y ago
  > this design makes the common case much simpler at the expense of making the rare case harder In the age of emoji (and uhhhh, everyone who doesn't use English as their main language), I don't think your "rare case" is really that rare.
tayo42 3y ago
Working with strings is one of the most common complaints about rust though. Unless your only talking about the implemtation of it?
- klodolph 3y ago
  Would love to hear what you think the complaints come from. They seem fine to me, and I have voiced plenty of criticism about the other parts of Rust. They work more or less how I expect—you have an array of bytes, which can either be a reference (&str) or owned / mutable / growable (String). The only unusual thing about Rust is that it validates that the bytes are UTF-8.
  - tayo42 3y ago
    Mostly around usability and learning curve. I wasnt sure if the post was meant as a total endorsement of rusts strings or just the encoding aspect of them
- dralley 3y ago
  What people complain about with Rust strings are that there are so many different types, like &str vs String, and OsString / OsStr. The encoding of the strings isn't the issue.
  - csande17 3y ago
    Encoding might not be the whole issue, but "Rust mandates that the 'string' type must only contain valid UTF-8, which is incompatible with every operating system in the world" is the reason why OsString is a separate type.
    - dralley 3y ago
      The only encoding which is compatible with "every operating system in the world" is no enforced encoding at all, and you can do very little "string-like" operations with such a type. Even Python, well-known for being a very usable language, distinguishes between strings (which are unicode, but not utf-8 necessarily) and bytes, which you need to use if you're interacting directly with the OS. The only real difference between the two is really the looseness with which Python lets you work with them, by virtue of being dynamically typed and having a large standard library that papers over some of the details.
neonsunset 3y ago
Rust and Go string implementations are very different. Rust strings are safe, have rich API and prevent you from corrupting their contents unless you go out of your way to do so. Go strings are a joke and won't do any validation if you slice them incorrectly and are extremely bare bones.

o11c 3y ago

Unfortunately, strings cross at least 3 different problems: * charset encoding. Cases worth supporting include Ascii, Latin1, Xascii, WeirdLegacyStatefulEncoding, WhateverMyLocaleSaysExceptNotReally, UTF8, UTF16, UCS2, UTF32, and sloppy variants thereof. Note that not supporting sloppiness means it is impossible to access a lot of old data (for example, `git` committers and commit messages). Note that it is impossible to make a 1-to-1 mapping between sloppy UTF-8 and sloppy UTF-16, so if all strings have a single representation (unless it is some weird representation not yet mentioned), it is either impossible to support all strings encountered on non-Windows platforms, or impossible to support all strings encountered on non-Windows platforms. I am a strong proponent of APIs supporting multiple compile-time-known string representations, with transparent conversion where safe. * ownership. Cases worth supporting: Value (but finite size), Refcounted (yes, this is important, the problem with std::string is that it was mutable), Tail or full Slice thereof, borrowed Zero-terminated or X(not) terminated, Literal (known statically allocated), and Alternating (the one that does SSO, switching between Value and Refcounted; IME it is important for Refcounted to efficiently support Literal). Note that there is no need for an immutable string to support Unique ownership. That's 8 different ownership policies, and if your Z/X implementation doesn't support recovering an optional owner, you also need to support at least one "maybe owned, maybe borrowed" (needed for things like efficient map insertion if the key might already exist; making the insert function a template does not suffice to handle all cases). It is important that, to the extent possible, all these (immutable) strings offer the same API, and can be converted implicitly where safe (exception: legacy code might make implicit conversion to V useful, despite being technically wrong). (there should be some Mutable string-like thing but it need not provide the API, only push/pop off the end followed by conversion to R; consider particularly the implementation of comma-separated list stringification) * domain meaning. The language itself should support at least Format strings for printf/scanf/strftime etc. (these "should" be separate types, but if relying on the C compiler to check them for you, don't actually have to be). Common library-supported additions include XML, JSON, and SQL strings, to make injection attacks impossible at the type level. Thinking of compilers (but not limited to them), there also needs to be dedicated types for "string representing a filepath" vs "string representing a file's contents" (the web's concept of "blob URL" is informative, but suffers from overloading the string type in the first place). Importantly, it must be easy to write literals of the appropriate type and convert explicitly as needed, so there should not be any file-related APIs that take strings. (related, it's often useful to have the concept of "single-line string" and "word" (which, among other cases, makes it possible to ); the exact definition thereof depending on context. So it may be useful to be able to tag strings as "all characters (or, separately, the first character or the last character (though "last character" is far less useful)) are one of [abc...]"; reasonably granularity being: NUL, whitespace characters individually, other C0 controls, ASCII symbols individually, digit 0, digit 1, digits 2-7, digits 8-9, letters a-f, letters A-F, letters g-z, letters G-Z, DEL, C1 controls, other latin1, U+0100 through U+07FF, U+0800 through U+FFFF excluding surrogates, low surrogates, high surrogates, and U+10000 through U+10FFFF, and illegal values U+110000 and higher (maybe splitting 31-bit from 32-bit?) (several of these are impossible under certain encodings and strictness levels). Actually supporting all of this in the compiler proper is complicated and likely to be deferred, but thinking about it informs both language and library design. Particularly, consider "partial template casting")

chubot 3y ago

The short answer is somewhere between Go and Rust strings, which are newer languages that use UTF-8 for interior representation, and also favor it for exterior encoding. Roughly speaking, Java and JavaScript are in the UTF-16 camp, and Python 2 and 3 are in the code points camp. C and C++ have unique problems, but you could also put them in the code points camp. So there are at least 3 different camps, and a whole bunch of weird variations, like string width being compile-time selectable in interpreters. More details here: https://www.oilshell.org/blog/2023/06/ysh-design.html#text https://www.oilshell.org/blog/2023/06/ysh-design.html#text and here: https://www.oilshell.org/blog/2023/06/surrogate-pair.html#history-windows-infected-javascript-json-and-python https://www.oilshell.org/blog/2023/06/surrogate-pair.html#hi... A main design issue is that string APIs shouldn't depend on a mutable global variable -- the default encoding, or default file system encoding. That's an idea that's a disaster in C, and also a disaster in Python. It leads to buggy programs. Go and Rust differ in their philosophies, but neither of them has that design problem.

librasteve 3y ago

Raku introduced the concept of NFG - Normal Form Grapheme - as a way to represent any Unicode string in its logical ‘visual character’ grapheme form. Sequences of combining characters that don’t have a canonical single codepoint form are given a synthetic codepoint so that string methods including regexes can operate on grapheme characters without ever causing splitting side effects. Of course there are methods for manipulating at the codepoint level as well.