On Wed, 26 Sep 2007, Aaron Denney wrote:

It's true that time-wise there are definite issues in finding character boundaries.

UTF-16 has no advantage over UTF-8 in this respect, because of surrogate pairs and combining characters. Code points, characters, and glyphs are all different things, and it's very difficult to represent the latter two as anything other than a string of code points. Tony. -- f.a.n.finch http://dotat.at/ IRISH SEA: SOUTHERLY, BACKING NORTHEASTERLY FOR A TIME, 3 OR 4. SLIGHT OR MODERATE. SHOWERS. MODERATE OR GOOD, OCCASIONALLY POOR.

On Sep 26, 2007, at 11:06 AM, Aaron Denney wrote:

...

UTF-16 has no advantage over UTF-8 in this respect, because of surrogate pairs and combining characters.

Good point.

Well, not so much. As Duncan mentioned, it's a matter of what the most common case is. UTF-16 is effectively fixed-width for the majority of text in the majority of languages. Combining sequences and surrogate pairs are relatively infrequent. Speaking as someone who has done a lot of Unicode implementation, I would say UTF-16 represents the best time/space tradeoff for an internal representation. As I mentioned, it's what's used in Windows, Mac OS X, ICU, and Java. Deborah

On Thu, Sep 27, 2007 at 06:39:24AM +0000, Aaron Denney wrote:

On 2007-09-27, Deborah Goldsmith wrote:

...

Well, not so much. As Duncan mentioned, it's a matter of what the most common case is. UTF-16 is effectively fixed-width for the majority of text in the majority of languages. Combining sequences and surrogate pairs are relatively infrequent.

Infrequent, but they exist, which means you can't seek x/2 bytes ahead to seek x characters ahead. All such seeking must be linear for both UTF-16 *and* UTF-8.

You could get rapid seeks by ignoring the UTFs and representing strings as sequences of chunks, where each chunk is uniformly 8-bit, 16-bit or 32-bit as required to cover the characters it contains. Hardly anyone would need 32-bit chunks (and some of us would need only the 8-bit ones).

2007/9/27, Duncan Coutts :

...

Infrequent, but they exist, which means you can't seek x/2 bytes ahead to seek x characters ahead. All such seeking must be linear for both UTF-16 *and* UTF-8.

And in [Char] for all these years, yet I don't hear people complaining. Most string processing is linear and does not need random access to characters.

Well, if you never heard anyone complaining about [Char] and never had any problem with it's slowness, you're probably not in a field where the efficiency of a Unicode library is really a concern, that's for sure. (I know that the _main_ problem with [Char] wasn't random access, but you must admit [Char] isn't really a good example to speak about efficiency problems) -- Jedaï

On 2007-09-27, Duncan Coutts wrote:

In message wnoise@ofb.net writes:

...

On 2007-09-27, Deborah Goldsmith wrote:

...

On Sep 26, 2007, at 11:06 AM, Aaron Denney wrote:

...

...

UTF-16 has no advantage over UTF-8 in this respect, because of surrogate pairs and combining characters.

Good point.

Well, not so much. As Duncan mentioned, it's a matter of what the most common case is. UTF-16 is effectively fixed-width for the majority of text in the majority of languages. Combining sequences and surrogate pairs are relatively infrequent.

Infrequent, but they exist, which means you can't seek x/2 bytes ahead to seek x characters ahead. All such seeking must be linear for both UTF-16 *and* UTF-8.

And in [Char] for all these years, yet I don't hear people complaining. Most string processing is linear and does not need random access to characters.

Yeah. I'm saying the differences between them are going to be in the constant factors, and that these constant factors will differ between workloads. -- Aaron Denney -><-

Sorry for the long delay, work has been really busy... On Sep 27, 2007, at 12:25 PM, Aaron Denney wrote:

On 2007-09-27, Aaron Denney wrote:

...

...

Well, not so much. As Duncan mentioned, it's a matter of what the most common case is. UTF-16 is effectively fixed-width for the majority of text in the majority of languages. Combining sequences and surrogate pairs are relatively infrequent.

Infrequent, but they exist, which means you can't seek x/2 bytes ahead to seek x characters ahead. All such seeking must be linear for both UTF-16 *and* UTF-8.

...

Speaking as someone who has done a lot of Unicode implementation, I would say UTF-16 represents the best time/space tradeoff for an internal representation. As I mentioned, it's what's used in Windows, Mac OS X, ICU, and Java.

I guess why I'm being something of a pain-in-the-ass here, is that I want to use your Unicode implementation expertise to know what these time/space tradeoffs are.

Are there any algorithmic asymptotic complexity differences, or all these all constant factors? The constant factors depend on projected workload. And are these actually tradeoffs, except between UTF-32 (which uses native wordsizes on 32-bit platforms) and the other two? Smaller space means smaller cache footprint, which can dominate.

Yes, cache footprint is one reason to use UTF-16 rather than UTF-32. Having no surrogate pairs also doesn't save you anything because you need to handle sequences anyway, such as combining marks and clusters. The best reference for all of this is: http://www.unicode.org/faq/utf_bom.html See especially: http://www.unicode.org/faq/utf_bom.html#10 http://www.unicode.org/faq/utf_bom.html#12 Which data type is best depends on what the purpose is. If the data will primarily be ASCII with an occasional non-ASCII characters, UTF-8 may be best. If the data is general Unicode text, UTF-16 is best. I would think a Unicode string type would be intended for processing natural language text, not just ASCII data.

Simplicity of algorithms is also a concern. Validating a byte sequence as UTF-8 is harder than validating a sequence of 16-bit values as UTF-16.

(I'd also like to see a reference to the Mac OS X encoding. I know that the filesystem interface is UTF-8 (decomposed a certain a way). Is it just that UTF-16 is a common application choice, or is there some common framework or library that uses that?)

UTF-16 is the native encoding used for Cocoa, Java, ICU, and Carbon, and is what appears in the APIs for all of them. UTF-16 is also what's stored in the volume catalog on Mac disks. UTF-8 is only used in BSD APIs for backward compatibility. It's also used in plain text files (or XML or HTML), again for compatibility. Deborah

On Oct 2, 2007, at 5:11 AM, ChrisK wrote:

Deborah Goldsmith wrote:

...

UTF-16 is the native encoding used for Cocoa, Java, ICU, and Carbon, and is what appears in the APIs for all of them. UTF-16 is also what's stored in the volume catalog on Mac disks. UTF-8 is only used in BSD APIs for backward compatibility. It's also used in plain text files (or XML or HTML), again for compatibility.

Deborah

On OS X, Cocoa and Carbon use Core Foundation, whose API does not have a one-true-encoding internally. Follow the rather long URL for details:

http://developer.apple.com/documentation/CoreFoundation/Conceptual/ CFStrings/index.html?http://developer.apple.com/documentation/ CoreFoundation/Conceptual/CFStrings/Articles/StringStorage.html#// apple_ref/doc/uid/20001179

I would vote for an API that not just hides the internal store, but allows different internal stores to be used in a mostly compatible way.

However, There is a UniChar typedef on OS X which is the same unsigned 16 bit integer as Java's JNI would use.

UTF-16 is the type used in all the APIs. Everything else is considered an encoding conversion. CoreFoundation uses UTF-16 internally except when the string fits entirely in a single-byte legacy encoding like MacRoman or MacCyrillic. If any kind of Unicode processing needs to be done to the string, it is first coerced to UTF-16. If it weren't for backwards compatibility issues, I think we'd use UTF-16 all the time as the machinery for switching encodings adds complexity. I wouldn't advise it for a new library. Deborah

I would like to, again, strongly argue against sacrificing compatibility with Linux/BSD/etc. for the sake of compatibility with OS X or Windows.

Ehm? I've used to think MacOS is a sort of BSD...

On Oct 2, 2007, at 8:44 AM, Jonathan Cast wrote:

I would like to, again, strongly argue against sacrificing compatibility with Linux/BSD/etc. for the sake of compatibility with OS X or Windows. FFI bindings have to convert data formats in any case; Haskell shouldn't gratuitously break Linux support (or make life harder on Linux) just to support proprietary operating systems better.

Now, if /independent of the details of MacOS X/, UTF-16 is better (objectively), it can be converted to anything by the FFI. But doing it the way Java or MacOS X or Win32 or anyone else does it, at the expense of Linux, I am strongly opposed to.

No one is advocating that. Any Unicode support library needs to support exporting text as UTF-8 since it's so widely used. It's used on Mac OS X, too, in exactly the same contexts it would be used on Linux. However, UTF-8 is a poor choice for internal representation. On Oct 2, 2007, at 2:32 PM, Stefan O'Rear wrote:

UTF-8 supports CJK languages too. The only question is efficiency, and I believe CJK is still a relatively uncommon case compared to English and other Latin-alphabet languages. (That said, I live in a country all of whose dominant languages use the Latin alphabet)

First of all, non-Latin countries already represent a large fraction of computer usage and the computer market. It is not at all "relatively uncommon." Japan alone is a huge market. China is a huge market. Second, it's not just CJK, but anything that's not mostly ASCII. Russian, Greek, Thai, Arabic, Hebrew, etc. etc. etc. UTF-8 is intended for compatibility with existing software that expects multibyte encodings. It doesn't work well as an internal representation. Again, no one is saying a Unicode library shouldn't have full support for input and output of UTF-8 (and other encodings). If you want to process ASCII text and squeeze out every last ounce of performance, use byte strings. Unicode strings should be optimized for representing and processing human language text, a large share of which is not in the Latin alphabet. Remember, speakers of English and other Latin-alphabet languages are a minority in the world, though not in the computer-using world. Yet. Deborah

I do not believe that anyone was seriously advocating multiple blessed encodings. The main question is *which* encoding to bless. 99+% of text I encounter is in US-ASCII, so I would favor UTF-8. Why is UTF-16 better for me?

All software I write professional have to support 40 languages (including CJK ones) so I would prefer UTF-16 in case I could use Haskell at work some day in the future. I dunno that who uses what encoding the most is good grounds to pick encoding though. Ease of implementation and speed on some representative sample set of text may be. -- Johan

Stefan O'Rear wrote:

On Tue, Oct 02, 2007 at 11:05:38PM +0200, Johan Tibell wrote:

...

...

I do not believe that anyone was seriously advocating multiple blessed encodings. The main question is *which* encoding to bless. 99+% of text I encounter is in US-ASCII, so I would favor UTF-8. Why is UTF-16 better for me? All software I write professional have to support 40 languages (including CJK ones) so I would prefer UTF-16 in case I could use Haskell at work some day in the future. I dunno that who uses what encoding the most is good grounds to pick encoding though. Ease of implementation and speed on some representative sample set of text may be.

UTF-8 supports CJK languages too. The only question is efficiency

Due to the additional complexity of handling UTF-8 -- EVEN IF the actual text processed happens all to be US-ASCII -- will UTF-8 perhaps be less efficient than UTF-16, or only as fast? Isaac

On Tue, 2007-10-02 at 21:45 -0400, Brandon S. Allbery KF8NH wrote:

...

Due to the additional complexity of handling UTF-8 -- EVEN IF the actual text processed happens all to be US-ASCII -- will UTF-8 perhaps be less efficient than UTF-16, or only as fast?

UTF8 will be very slightly faster in the all-ASCII case, but quickly blows chunks if you have *any* characters that require multibyte.

What benchmarks are you basing this on? Doubling your data size is going to cost you if you are doing simple operations (searching, say), but I don't see UTF-8 being particularly expensive - somebody (forget who) implemented UTF-8 on top of ByteString, and IIRC, the benchmarks numbers didn't change all that much from the regular Char8. -k

Lots of people wrote:

I want a UTF-8 bikeshed! No, I want a UTF-16 bikeshed!

What the heck does it matter what encoding the library uses internally? I expect the interface to be something like (from my own CompactString library):

fromByteString :: Encoding -> ByteString -> UnicodeString toByteString :: Encoding -> UnicodeString -> ByteString The only matter is efficiency for a particular encoding.

I would suggest that we get a working library first. Either UTF-8 or UTF-16 will do, as long as it works. Even better would be to implement both (and perhaps more encodings), and then benchmark them to get a sensible default. Then the choice can be made available to the user as well, in case someone has specifix needs. But again: get it working first! Twan

On Wed, 2007-10-03 at 00:01 +0200, Twan van Laarhoven wrote:

Lots of people wrote:

...

I want a UTF-8 bikeshed! No, I want a UTF-16 bikeshed!

What the heck does it matter what encoding the library uses internally?

+1 jcc

...

What the heck does it matter what encoding the library uses internally?

+1 It can even use a non-standard encoding scheme if it wants.

Sounds good to me. I (think) one of my initial questions was if the encoding should be visible in the type of the UnicodeString type or not. My gut feeling is that having the type visible might make it hard to change the internal representation but I haven't yet got a good example to prove this. -- Johan

On Wed, Sep 26, 2007 at 11:25:30AM +0100, Tony Finch wrote:

On Wed, 26 Sep 2007, Aaron Denney wrote:

...

It's true that time-wise there are definite issues in finding character boundaries.

UTF-16 has no advantage over UTF-8 in this respect, because of surrogate pairs and combining characters.

Combining characters are not an issue here, just the surrogate pairs, because we're discussing representations of sequences of Chars (Unicode code points).

On Thu, Sep 27, 2007 at 07:26:07AM +0000, Aaron Denney wrote:

On 2007-09-27, Ross Paterson wrote:

...

Combining characters are not an issue here, just the surrogate pairs, because we're discussing representations of sequences of Chars (Unicode code points).

You'll never want to combine combining characters or vice-versa? Never want to figure out how much screen space a sequence will take? It _is_ an issue.

It's an issue for a higher layer, not for a compact String representation.

On Thu, 27 Sep 2007, Ross Paterson wrote:

Combining characters are not an issue here, just the surrogate pairs, because we're discussing representations of sequences of Chars (Unicode code points).

I dislike referring to unicode code points as "characters" because that tends to imply a lot of invalid simplifications. Tony. -- f.a.n.finch http://dotat.at/ IRISH SEA: SOUTHERLY, BACKING NORTHEASTERLY FOR A TIME, 3 OR 4. SLIGHT OR MODERATE. SHOWERS. MODERATE OR GOOD, OCCASIONALLY POOR.

I have often found myself wishing for a small extension to the syntax of Haskell 'data' declarations. It goes like this: data <as usual> = <as usual> | ... | <as usual> +++ where type <tvar> = <type> type <tvar> = <type> ... deriving <as usual> Even something like binary search trees would, to me, be clearer as data BST key val = Empty | Fork key val bst bst where type bst = BST key val because this establishes an *essential* identity between the 3rd and 4th Fork argument types, rather than an "accidental" identity. I can't set this up using 'type' outside the 'data' declaration, because it has to refer to the type arguments of BST. Semantically, this is just an abbreviation mechanism with no consequences of any kind outside the 'data' declaration itself. The only point would be to make reading and writing 'data' declarations easier, especially large ones.

Thomas Conway writes:

On 9/27/07, ok wrote:

...

I have often found myself wishing for a small extension to the syntax of Haskell 'data' declarations. It goes like this: ['where' clause to allow locally defined names in type declarations]

Nice.

Quite a few times I've found myself declaring type synonyms for this reason, but you end up polluting the global namespace.

+1 vote.

Data with where? You haven't heard about GADTs? http://en.wikibooks.org/wiki/Haskell/GADT http://www.haskell.org/haskellwiki/Generalised_algebraic_datatype Jerzy Karczmarczuk

Tomasz Zielonka wrote:

On 9/27/07, jerzy.karczmarczuk@info.unicaen.fr wrote:

...

Thomas Conway writes:

...

On 9/27/07, ok wrote:

...

I have often found myself wishing for a small extension to the syntax of Haskell 'data' declarations. It goes like this: ['where' clause to allow locally defined names in type declarations]

Nice.

Quite a few times I've found myself declaring type synonyms for this reason, but you end up polluting the global namespace.

+1 vote. Data with where? You haven't heard about GADTs?

I think that you haven't read the question carefully, because "where" in GADTs is simply a syntactic sugar. However, this seems to be available already with GADTs and type equality constraints:

data BST key val where Empty :: BST key val Fork :: (bst ~ BST key val) => key -> val -> bst -> bst -> BST key val

It's a pity you can't use bst (or a type synonym) instead of the last "BST key val".

Indeed. GADT syntax looks like a type signature (except for strictness annotations, which presently aren't part of function syntax!) but apparently the (->)s and result-type aren't type-signature, because type-synonyms can't be used for them. I tried. (because there were several GADT constructors with slightly different signatures, so I made a type-synonym with an argument to try to shorten them). It seems a pity to me too. Isaac

On 9/27/07, Albert Y. C. Lai wrote:

jerzy.karczmarczuk@info.unicaen.fr wrote:

...

Data with where? You haven't heard about GADTs?

To avoid clashing with GADT's "where", I propose to rename ok's keyword to "wherein", or "wheretype", or something

data B k v = E | F b b wherein type b = B k v

data B k v = E | F b b wheretype b = B k v

I'm not sure there is a clash. data B k v where ... is easily distinguished from data B k v = ... where ... -- Dave Menendez http://www.eyrie.org/~zednenem/

Thomas Conway wrote:

Although Richard's proposal was simpler, I reckon it's worth discussing whether the where clause should allow normal type/data/newtype declarations, effectively introducing a new scope. There are obviously some type variable quantification and name resolution issues that should yield several conference papers.

data RelaxedTree key val = Leaf Bal [(key,val)] | Node Bal [(key,RelaxedTree key val)] where data Bal = Balanced | Unbalanced

Is Bal visible outside data RelaxedTree? If so, why not put it at the top level. If not, are Balanced and Unbalanced visible? If not, then there is no way to construct a RelaxedTree. If so, then you could not give a type annotation to x = Balanced.

data Tree key val = Leaf key val | Node BST key val BST where type BST = Tree key val

The type synonym example is much easier because it is effectively syntactic sugar, and although BST is not visible, Tree key val is. But is let allowed as well, if we want to restrict the visibility of BST to just the Node constructor? Type synomym of a type variable OK? data Tree key val = let BST = key in Leaf BST val -- perversely called BST | let BST = Tree key val in Node BST key val BST

On 9/28/07, ok wrote:

Now there's a paper that was mentioned about a month ago in this mailing list which basically dealt with that by splitting each type into two: roughly speaking a bit that expresses the recursion and a bit that expresses the choice structure.

Would you like to give a link to that paper? (the following is a bit offtopic) In the 1995 paper[1]: "Bananas in Space: Extending Fold and Unfold to Exponential Types", Erik Meijer and Graham Hutton showed a interesting technique: Your ADT: data Expr env = Variable (Var env) | Constant Int | Unary String (Expr env) | Binary String (Expr env) (Expr env) can be written without recursion by using a fixpoint newtype combinator (not sure if this is the right name for it): newtype Rec f = In { out :: f (Rec f) } data Var env = Var env String data E env e = Variable (Var env) | Constant Int | Unary String e | Binary String e e type Expr env = Rec (E env) example = In (Binary "+" (In (Constant 1)) (In (Constant 2))) You can see that you don't have to name the recursive 'Expr env' explicitly. However constructing a 'Expr' is a bit verbose because of the 'In' newtype constructors. regards, Bas van Dijk [1] http://citeseer.ist.psu.edu/293490.html

On 2007-09-26, Johan Tibell wrote:

If UTF-16 is what's used by everyone else (how about Java? Python?) I think that's a strong reason to use it. I don't know Unicode well enough to say otherwise.

The internal representations don't matter except in the case of making FFI linkages. The external representations do, and UTF-8 has won on that front. -- Aaron Denney -><-

On 2007-09-26, Johan Tibell wrote:

On 9/26/07, Aaron Denney wrote:

...

On 2007-09-26, Johan Tibell wrote:

...

If UTF-16 is what's used by everyone else (how about Java? Python?) I think that's a strong reason to use it. I don't know Unicode well enough to say otherwise.

The internal representations don't matter except in the case of making FFI linkages. The external representations do, and UTF-8 has won on that front.

It could matter for performance. However, you can encode your UnicodeString into any external representation you want for your I/O needs, including UTF-8.

Right. I was trying to say "other languages internal representations shouldn't affect the choice of those doing a Haskell implementation." -- Aaron Denney -><-

In message <1190825044.9435.1.camel@jcchost> Jonathan Cast writes:

On Wed, 2007-09-26 at 09:05 +0200, Johan Tibell wrote:

...

If UTF-16 is what's used by everyone else (how about Java? Python?) I think that's a strong reason to use it. I don't know Unicode well enough to say otherwise.

I disagree. I realize I'm a dissenter in this regard, but my position is: excellent Unix support first, portability second, excellent support for Win32/MacOS a distant third. That seems to be the opposite of every language's position. Unix absolutely needs UTF-8 for backward compatibility.

I think you're talking about different things, internal vs external representations. Certainly we must support UTF-8 as an external representation. The choice of internal representation is independent of that. It could be [Char] or some memory efficient packed format in a standard encoding like UTF-8,16,32. The choice depends mostly on ease of implementation and performance. Some formats are easier/faster to process but there are also conversion costs so in some use cases there is a performance benefit to the internal representation being the same as the external representation. So, the obvious choices of internal representation are UTF-8 and UTF-16. UTF-8 has the advantage of being the same as a common external representation so conversion is cheap (only need to validate rather than copy). UTF-8 is more compact for western languages but less compact for eastern languages compared to UTF-16. UTF-8 is a more complex encoding in the common cases than UTF-16. In the common case UTF-16 is effectively fixed width. According to the ICU implementors this has speed advantages (probably due to branch prediction and smaller code size). One solution is to do both and benchmark them. Duncan

On 26 Sep 2007, at 7:05 pm, Johan Tibell wrote:

If UTF-16 is what's used by everyone else (how about Java? Python?) I think that's a strong reason to use it. I don't know Unicode well enough to say otherwise.

Java uses 16-bit variables to hold characters. This is SOLELY for historical reasons, not because it is a good choice. The history is a bit funny: the ISO 10646 group were working away defining a 31-bit character set, and the industry screamed blue murder about how this was going to ruin the economy, bring back the Dark Ages, &c, and promptly set up the Unicode consortium to define a 16-bit character set that could do the same job. Early versions of Unicode had only about 30 000 characters, after heroic (and not entirely appreciated) efforts at unifiying Chinese characters as used in China with those used in Japan and those used in Korea. They also lumbered themselves (so that they would have a fighting chance of getting Unicode adopted) with a "round trip conversion" policy, namely that it should be possible to take characters using ANY current encoding standard, convert them to Unicode, and then convert back to the original encoding with no loss of information. This led to failure of unification: there are two versions of Å (one for ordinary use, one for Angstroms), two versions of mu (one for Greek, one for micron), three complete copies of ASCII, &c). However, 16 bits really is not enough. Here's a table from http://www.unicode.org/versions/Unicode5.0.0/ Graphic 98,884 Format 140 Control 65 Private Use 137,468 Surrogate 2,048 Noncharacter 66 Reserved 875,441 Excluding Private Use and Reserved, I make that 101,203 currently defined codes. That's nearly 1.5* the number that would fit in 16 bits. Java has had to deal with this, don't think it hasn't. For example, where Java had one set of functions referring to characters in strings by position, it now has two complete sets: one to use *which 16-bit code* (which is fast) and one to use *which actual Unicode character* (which is slow). The key point is that the second set is *always* slow even when there are no characters outside the basic multilingual plane. One Smalltalk system I sometimes use has three complete string implementations (all characters fit in a byte, all characters fit in 16 bits, some characters require more) and dynamically switches from narrow strings to wide strings behind your back. In a language with read-only strings, that makes a lot of sense; it's just a pity Smalltalk isn't one. If you want to minimize conversion effort when talking to the operating system, files, and other programs, UTF-8 is probably the way to go. (That's on Unix. For Windows it might be different.) If you want to minimize the effort of recognising character boundaries while processing strings, 32-bit characters are the way to go. If you want to be able to index into a string efficiently, they are the *only* way to go. Solaris bit the bullet many years ago; Sun C compilers jumped straight from 8-bit wchar_t to 32_bit without ever stopping at 16. 16-bit characters *used* to be a reasonable compromise, but aren't any longer. Unicode keeps on growing. There were 1,349 new characters from Unicode 4.1 to Unicode 5.0 (IIRC). There are lots more scripts in the pipeline. (What the heck _is_ Tangut, anyway?)