6 ms·

I think the main (and almost the only) reason to have distinct string type is performance, not for the ease of programming. Many string operations are useful a

by shiro 17y ago

I think the main (and almost the only) reason to have distinct string type is performance, not for the ease of programming. Many string operations are useful as a general list operations as well, including regular expression matcher. (Note: Some people emphasize importance of O(1) access of string access by index, but using integer index is also a performance hack. If search operations can return some way to point to the substring you don't need integer indexes.) Another minor reason is to display; people prefer reading sequence of characters in a string syntax. If you have a statically typed language it is easy to display a list of chars in string syntax instead of list syntax. For a dynamically typed language with heterogeneous lists, it can be a performance penalty to check whether a list entirely consists of characters or not at runtime. So, in a sense, it is also about a performance. (Note: Having a syntax for strings has nothing to do with having distinct type for strings. The string syntax can be just a syntax sugar.) But performance is important, of course. One thing very common in string (a list of characters) but not very common in general lists is concatenation. To be precise, lazy language programmers use list concatenation without a guilt, but eager language programmers tend to avoid it since it may cause unnecessary copying of lists. So for the eager evaluation languages, it makes sense to have a string type that has very cheap concatenation operation (e.g. using tree representation) internally.

amix 17y ago
Performance and ease of use are the main reasons why strings should be first class citizens. Strings are one of the most used data structures and most of today's popular languages have very good support for them, encodings of them and manipulation of them. C does not have that good support for them. Ignoring strings and labeling them as "a list of integers" is a step backward, since a lot of the data we have today is textual and will continue to be textual in the future.
- aaronblohowiak 17y ago
  computers exist to serve humans, and strings are the best way for them to communicate to their masters..
- shiro 17y ago
  Having dynamic typing makes the discussion complicated, so let's assume we have a cheap way to know the type of a given object. In one world, you get an object of type [Char] ---means a list of characters--- and you can apply all sorts of list operations on it, and all sorts of operations specialized to [Char]. You can add a type alias String to the type [Char]. In the source file you can write "string" and it is read as a list of six characters. On the output the same list is printed as "string". In another world, you get an object of type String, which is distinct type from a list of characters. Type String has all sorts of useful operations. But if you want to apply a generic list algorithm, you have to either duplicate the code, or coerce the string into a list. Conversely, if you have a list of characters and want to pass it to a string library function, say, regexp matcher, you have to coerce it to a string. Which is easier? As nostrademons commented, one way is to implement a generic interface so that you can write a generic algorithm on top of both list of characters and Strings, but that's actually the same thing I'm saying. I say "list" as some data structure on which you can peek the head, the tail, and you can add an element in front of existing one. I don't care how it is represented---if the runtime or the compiler can find out the list only contains ASCII characters, it can freely store the entire list in an octet array. In a sense, I say "list" as "data structures that implement the list interface". Now, suppose if you have such a smart runtime/compiler. Suppose you can have specialized functions on [Char], apart from generic list. Do you still think having distinct string type is for ease of use? In reality we don't have such sufficient smart runtime/compiler, so we compromise. That's the distinct string type.
  - amix 17y ago
    I would prefer if strings were treated as a list of characters and NOT as a list of integers (as they are in Erlang)...! I.e. your reasoning does not really apply to Erlang.
    - shiro 17y ago
      Oh, I thought you were arguing with my proposition: Distinct string type is for performance and not for ease of programming. I agree that conflating [Char] and [Integer] is not good. That's a different story.
ubernostrum 17y ago
"Many string operations are useful as a general list operations as well, including regular expression matcher." Except this falls apart when dealing with Unicode -- if your regex wants to match "ä", for example, treating strings as lists means you'll miss at least one possible way of representing that in Unicode (it may be a single code point, or it may be two -- an "a" with a combining diaresis).
- shiro 17y ago
  That is a sort of tangent problem you have to deal with whichever you have distinct string type or list-of-character strings. You may canonicalize, or you delegate stuff to intermediate library.
  - barrkel 17y ago
    It's not a tangent problem. It's at the very core of what a string is. I think you're confusing a representation of a string with what a string actually is, because it is convenient for your mental model of programming to believe - as an act of faith - that strings are lists of characters. Strings are just blobs of data that encode human-interpretable text. There is no underlying symmetry which proves that they fit into a monadic concept of a list, and indeed, they don't fit particularly well there. Built-in string types can do things like warn that literal strings aren't convertible into target string type, at compile time; that an assignment from one string type to another may lose information, etc. Different string types may use different encodings, etc.
    - shiro 17y ago
      Hm. I'm assuming internal string representation is canonicalized and independent from specific external encodings (or implementation hides it). I'm not sure what you mean by "target string type".
      - barrkel 17y ago
        In part it is motivated by my experience in Delphi of moving from a so-called AnsiString (encoded in current Windows code page) to UnicodeString (encoded in UTF-16) between Delphi 2007 and Delphi 2009. I implemented the initial RTL routines and helped with some of the compiler support. Delphi has multiple string types to handle all the backward compatibility issues. Ancient Pascal strings are limited to 255 characters; AnsiString (current code page), WideString (a COM BSTR), UnicodeString, and things like Utf8String (magic UTF-8 code page), etc. Assignments between the different strings perform conversions, and cause warnings for possible data-loss. The more you learn about how strings work, including the international aspects, legacy aspects, OS-specific aspects, conversions at source code -> executable -> runtime -> I/O boundaries, etc., the more you appreciate the situation really isn't trivially reducible to simple lists of characters.
nostrademons 17y ago
"Many string operations are useful as a general list operations as well, including regular expression matcher." The way to get around that is to have some concept of interfaces in the language, and then have a generic Sequence type that strings, arrays, lists, and a bunch of other concrete types all implement. This makes your sequence operations even more polymorphic, eg. you can have them work on ropes, iterators, tree traversals, etc. The real problem with the list representation for strings is memory consumption. English UTF-8 text in a byte array takes one byte per code point. English unicode text in a list where each code point is an immediate 32-bit int takes up 8 bytes per character. That's a factor of 8 difference in memory consumption. And more memory means you can't fit as much into cache. There's a huge difference between being able to keep all your strings in L2 cache vs. having to go to main memory, particularly for string manipulations, which may need to touch a lot of different memory locations without a lot of locality. "Some people emphasize importance of O(1) access of string access by index, but using integer index is also a performance hack. If search operations can return some way to point to the substring you don't need integer indexes." Also, UTF-8 usually means you have to give up O(1) indexing. Your string may have multi-byte characters, which you can't discover unless you iterate through it. In practice, this doesn't matter. The vast majority of string slices chop a few characters off from either the beginning or the end. You can do Boyer-Moore on byte sequences and return the byte offset instead of the character offset. Most other indexing operations involve some sort of iteration over the string anyway. The only real pathological case is when you need to find the midpoint of a string repeatedly.
barrkel 17y ago
Strings aren't lists of characters. In that misconception, many common coding errors lie. For example, you might think that reversing a string is equivalent to reversing its characters. It's not. Similarly, you might think that indexing a string is the same as indexing a list. It's not. Etc etc.
- voidpointer 17y ago
  That very much depends on your definition of a String. I'm not sure what you mean by reversing a string not being equal to reversing its characters. It's certainly not always equal to reversing its bytes (depending on the encoding). Same goes for Strings that are implemented with UTF-16 characters (e.g. Java, win32 wchar_t etc.) all suffer from bad abstractions driven by implementation/efficiency concerns.
  - fhars 17y ago
    His point is that the reverse of the two character unicode string "LATIN-SMALL-LETTER-O COMBINIG-DIAERESIS" is not "COMBINING-DIAERESIS LATIN-SMALL-LETTER-O", but the original "LATIN-SMALL-LETTER-O COMBINIG-DIAERESIS". Blame it on the unicode consortium, but that is the way it is.
    - voidpointer 17y ago
      I wouldn't necessarily blame it on the unicode consortium but rather on the assumption that a character in a programming language should conform to the notion of a character in UCS-4 or some other unicode encoding. From a programming language perspective, I think it would be ideal if strings could always be viewed as lists of encoding independent characters, such that reversing this list is equivalent to reversing the string. If you want to be able to maintain a one-to-one mapping to unicode, you will need to use unique characters for an "ä" and an "a with combining-diaeresis" but ideally that should be hidden from the user of the language. Thus, in my ideal world, both "LATIN-SMALL-LETTER-O-WITH-DIAERESIS" and "LATIN-SMALL-LETTER-O COMBINING-DIAERESIS" would each be one single element of a list of characters which is a string.
    - 17y ago

by shiro 17y ago

amix 17y ago

Performance and ease of use are the main reasons why strings should be first class citizens. Strings are one of the most used data structures and most of today's popular languages have very good support for them, encodings of them and manipulation of them. C does not have that good support for them. Ignoring strings and labeling them as "a list of integers" is a step backward, since a lot of the data we have today is textual and will continue to be textual in the future.

aaronblohowiak 17y ago
computers exist to serve humans, and strings are the best way for them to communicate to their masters..
shiro 17y ago
Having dynamic typing makes the discussion complicated, so let's assume we have a cheap way to know the type of a given object. In one world, you get an object of type [Char] ---means a list of characters--- and you can apply all sorts of list operations on it, and all sorts of operations specialized to [Char]. You can add a type alias String to the type [Char]. In the source file you can write "string" and it is read as a list of six characters. On the output the same list is printed as "string". In another world, you get an object of type String, which is distinct type from a list of characters. Type String has all sorts of useful operations. But if you want to apply a generic list algorithm, you have to either duplicate the code, or coerce the string into a list. Conversely, if you have a list of characters and want to pass it to a string library function, say, regexp matcher, you have to coerce it to a string. Which is easier? As nostrademons commented, one way is to implement a generic interface so that you can write a generic algorithm on top of both list of characters and Strings, but that's actually the same thing I'm saying. I say "list" as some data structure on which you can peek the head, the tail, and you can add an element in front of existing one. I don't care how it is represented---if the runtime or the compiler can find out the list only contains ASCII characters, it can freely store the entire list in an octet array. In a sense, I say "list" as "data structures that implement the list interface". Now, suppose if you have such a smart runtime/compiler. Suppose you can have specialized functions on [Char], apart from generic list. Do you still think having distinct string type is for ease of use? In reality we don't have such sufficient smart runtime/compiler, so we compromise. That's the distinct string type.
- amix 17y ago
  I would prefer if strings were treated as a list of characters and NOT as a list of integers (as they are in Erlang)...! I.e. your reasoning does not really apply to Erlang.
  - shiro 17y ago
    Oh, I thought you were arguing with my proposition: Distinct string type is for performance and not for ease of programming. I agree that conflating [Char] and [Integer] is not good. That's a different story.

ubernostrum 17y ago

"Many string operations are useful as a general list operations as well, including regular expression matcher." Except this falls apart when dealing with Unicode -- if your regex wants to match "ä", for example, treating strings as lists means you'll miss at least one possible way of representing that in Unicode (it may be a single code point, or it may be two -- an "a" with a combining diaresis).

shiro 17y ago
That is a sort of tangent problem you have to deal with whichever you have distinct string type or list-of-character strings. You may canonicalize, or you delegate stuff to intermediate library.
- barrkel 17y ago
  It's not a tangent problem. It's at the very core of what a string is. I think you're confusing a representation of a string with what a string actually is, because it is convenient for your mental model of programming to believe - as an act of faith - that strings are lists of characters. Strings are just blobs of data that encode human-interpretable text. There is no underlying symmetry which proves that they fit into a monadic concept of a list, and indeed, they don't fit particularly well there. Built-in string types can do things like warn that literal strings aren't convertible into target string type, at compile time; that an assignment from one string type to another may lose information, etc. Different string types may use different encodings, etc.
  - shiro 17y ago
    Hm. I'm assuming internal string representation is canonicalized and independent from specific external encodings (or implementation hides it). I'm not sure what you mean by "target string type".
    - barrkel 17y ago
      In part it is motivated by my experience in Delphi of moving from a so-called AnsiString (encoded in current Windows code page) to UnicodeString (encoded in UTF-16) between Delphi 2007 and Delphi 2009. I implemented the initial RTL routines and helped with some of the compiler support. Delphi has multiple string types to handle all the backward compatibility issues. Ancient Pascal strings are limited to 255 characters; AnsiString (current code page), WideString (a COM BSTR), UnicodeString, and things like Utf8String (magic UTF-8 code page), etc. Assignments between the different strings perform conversions, and cause warnings for possible data-loss. The more you learn about how strings work, including the international aspects, legacy aspects, OS-specific aspects, conversions at source code -> executable -> runtime -> I/O boundaries, etc., the more you appreciate the situation really isn't trivially reducible to simple lists of characters.

nostrademons 17y ago

"Many string operations are useful as a general list operations as well, including regular expression matcher." The way to get around that is to have some concept of interfaces in the language, and then have a generic Sequence type that strings, arrays, lists, and a bunch of other concrete types all implement. This makes your sequence operations even more polymorphic, eg. you can have them work on ropes, iterators, tree traversals, etc. The real problem with the list representation for strings is memory consumption. English UTF-8 text in a byte array takes one byte per code point. English unicode text in a list where each code point is an immediate 32-bit int takes up 8 bytes per character. That's a factor of 8 difference in memory consumption. And more memory means you can't fit as much into cache. There's a huge difference between being able to keep all your strings in L2 cache vs. having to go to main memory, particularly for string manipulations, which may need to touch a lot of different memory locations without a lot of locality. "Some people emphasize importance of O(1) access of string access by index, but using integer index is also a performance hack. If search operations can return some way to point to the substring you don't need integer indexes." Also, UTF-8 usually means you have to give up O(1) indexing. Your string may have multi-byte characters, which you can't discover unless you iterate through it. In practice, this doesn't matter. The vast majority of string slices chop a few characters off from either the beginning or the end. You can do Boyer-Moore on byte sequences and return the byte offset instead of the character offset. Most other indexing operations involve some sort of iteration over the string anyway. The only real pathological case is when you need to find the midpoint of a string repeatedly.

barrkel 17y ago

Strings aren't lists of characters. In that misconception, many common coding errors lie. For example, you might think that reversing a string is equivalent to reversing its characters. It's not. Similarly, you might think that indexing a string is the same as indexing a list. It's not. Etc etc.

voidpointer 17y ago
That very much depends on your definition of a String. I'm not sure what you mean by reversing a string not being equal to reversing its characters. It's certainly not always equal to reversing its bytes (depending on the encoding). Same goes for Strings that are implemented with UTF-16 characters (e.g. Java, win32 wchar_t etc.) all suffer from bad abstractions driven by implementation/efficiency concerns.
- fhars 17y ago
  His point is that the reverse of the two character unicode string "LATIN-SMALL-LETTER-O COMBINIG-DIAERESIS" is not "COMBINING-DIAERESIS LATIN-SMALL-LETTER-O", but the original "LATIN-SMALL-LETTER-O COMBINIG-DIAERESIS". Blame it on the unicode consortium, but that is the way it is.
  - voidpointer 17y ago
    I wouldn't necessarily blame it on the unicode consortium but rather on the assumption that a character in a programming language should conform to the notion of a character in UCS-4 or some other unicode encoding. From a programming language perspective, I think it would be ideal if strings could always be viewed as lists of encoding independent characters, such that reversing this list is equivalent to reversing the string. If you want to be able to maintain a one-to-one mapping to unicode, you will need to use unique characters for an "ä" and an "a with combining-diaeresis" but ideally that should be hidden from the user of the language. Thus, in my ideal world, both "LATIN-SMALL-LETTER-O-WITH-DIAERESIS" and "LATIN-SMALL-LETTER-O COMBINING-DIAERESIS" would each be one single element of a list of characters which is a string.
  - 17y ago