- “The UTF-8 decoding fast path for ASCII only characters was removed and replaced with a memcpy if the entire string is ASCII.” The fast path would still be useful for mostly-ASCII strings, which are extremely common (unless UTF-8 has become a no-op?).

Is it really extremely common to have strings that are mostly-ASCII but not completely ASCII? I would agree that pure ASCII strings are extremely common. Regards, Martin

...

- “The UTF-8 decoding fast path for ASCII only characters was removed and replaced with a memcpy if the entire string is ASCII.” The fast path would still be useful for mostly-ASCII strings, which are extremely common (unless UTF-8 has become a no-op?).

Is it really extremely common to have strings that are mostly-ASCII but not completely ASCII? I would agree that pure ASCII strings are extremely common. Mostly ascii is pretty common for western-european languages (French, for instance, is probably 90 to 95% ascii). It's also a risk in english, when

On 2011-08-23, at 10:55 , Martin v. Löwis wrote: the writer "correctly" spells foreign words (résumé and the like).

...

...

Is it really extremely common to have strings that are mostly-ASCII but not completely ASCII? I would agree that pure ASCII strings are extremely common. Mostly ascii is pretty common for western-european languages (French, for instance, is probably 90 to 95% ascii). It's also a risk in english, when the writer "correctly" spells foreign words (résumé and the like).

I know - I still question whether it is "extremely common" (so much as to justify a special case).

Well, it's: - all natural languages based on a variant of the latin alphabet - but also, XML, JSON, HTML documents... - and log files... - in short, any kind of parsable format which is structurally ASCII but and can contain arbitrary unicode So I would say *most* unicode data out there is mostly-ASCII, even when it has Japanese characters in it. The rationale is that most unicode data processed by computers is structured. This optimization was done when trying to improve the speed of text I/O.

In the PEP 393 approach, if the string has a two-byte representation, each character needs to widened to two bytes, and likewise for four bytes. So three separate copies of the unrolled loop would be needed, one for each target size.

Do you have three copies of the UTF-8 decoder already, or do you a use a stringlib-like approach? Regards Antoine.

Le mardi 23 août 2011 à 13:51 +0200, "Martin v. Löwis" a écrit :

...

This optimization was done when trying to improve the speed of text I/O.

So what speedup did it achieve, for the kind of data you talked about?

Since I don't have the number anymore, I've just saved the contents of https://linuxfr.org/news/le-noyau-linux-est-disponible-en-version%C2%A030 as a "linuxfr.html" file and then did: $ ./python -m timeit "with open('linuxfr.html', encoding='utf8') as f: f.read()" 1000 loops, best of 3: 859 usec per loop After disabling the fast path, I ran the micro-benchmark again: $ ./python -m timeit "with open('linuxfr.html', encoding='utf8') as f: f.read()" 1000 loops, best of 3: 1.09 msec per loop so that's a 20% speedup.

...

Do you have three copies of the UTF-8 decoder already, or do you a use a stringlib-like approach?

It's a single implementation - see for yourself.

So why would you need three separate implementation of the unrolled loop? You already have a macro named WRITE_FLEXIBLE_OR_WSTR. Even without taking into account the unrolled loop, I wonder how much slower UTF-8 decoding becomes with that approach, by the way. Instead of testing the "kind" variable at each loop iteration, using a stringlib-like approach may be a better deal IMO. Of course we would first need to have various benchmark numbers once the current PEP 393 implementation is complete. Regards Antoine.

Well, things have to be done in order: 1. the PEP needs to be approved 2. the performance bottlenecks need to be identified 3. optimizations should be applied.

Sure, but the whole point of the PEP is to improve performance (I am dumping "memory consumption" in the "performance" bucket). That is, I suppose it will get approval based on its demonstrated benefits.

I'm not sure what you mean by "stringlib-like" approach - if you are talking about templating, I'd rather avoid this for maintainability reasons, unless significant improvements can be demonstrated. Torsten had a version that used macros for that, and it was a pain to debug.

The point of templating is precisely to avoid macros, so that the code is natural to read and write and the compiler gives you the right line number when it finds an error. Regards Antoine.

On Tue, Aug 23, 2011 at 11:21 PM, Victor Stinner wrote:

Le 23/08/2011 15:06, "Martin v. Löwis" a écrit :

...

Well, things have to be done in order: 1. the PEP needs to be approved 2. the performance bottlenecks need to be identified 3. optimizations should be applied.

I would not vote for the PEP if it slows down Python, especially if it's much slower. But Torsten says that it speeds up Python, which is surprising. I have to do my own benchmarks :-)

As Martin noted, cache misses hurt performance so much on modern processors that making things use less memory overall can actually be a speed optimisation as well. Guessing where the remaining bottlenecks are is unlikely to be effective - profiling of the preliminary implementation will be needed. However, the idea that reducing the size of pure ASCII strings (which include all the identifiers in most code) by a factor of 2 or 4 (or so) results in a net speed increase definitely sounds plausible to me, even for non-string processing code. Cheers, Nick. -- Nick Coghlan   |   ncoghlan@gmail.com   |   Brisbane, Australia

Terry Reedy writes:

The current UCS2 Unicode string implementation, by design, quickly gives WRONG answers for len(), iteration, indexing, and slicing if a string contains any non-BMP (surrogate pair) Unicode characters. That may have been excusable when there essentially were no such extended chars, and the few there were were almost never used.

Well, no, it gives the right answer according to the design. unicode objects do not contain character strings. By design, they contain code point strings. Guido has made that absolutely clear on a number of occasions. And the reasons have very little to do with lack of non-BMP characters to trip up the implementation. Changing those semantics should have been done before the release of Python 3. It is not clear to me that it is a good idea to try to decide on "the" correct implementation of Unicode strings in Python even today. There are a number of approaches that I can think of. 1. The "too bad if you can't take a joke" approach: do nothing and recommend UTF-32 to those who want len() to DTRT. 2. The "slope is slippery" approach: Implement UTF-16 objects as built-ins, and then try to fend off requests for correct treatment of unnormalized composed characters, normalization, compatibility substitutions, bidi, etc etc. 3. The "are we not hackers?" approach: Implement a transform that maps characters that are not represented by a single code point into Unicode private space, and then see if anybody really needs more than 6400 non-BMP characters. (Note that this would generalize to composed characters that don't have a one-code-point NFC form and similar non-standardized cases that nonstandard users might want handled.) 4. The "42" approach: sadly, I can't think deeply enough to explain it. There are probably others. It's true that Python is going to need good libraries to provide correct handling of Unicode strings (as opposed to unicode objects). But it's not clear to me given the wide variety of implementations I can imagine that there will be one best implementation, let alone which ones are good and Pythonic, and which not so.

Terry Reedy writes:

Excuse me for believing the fine 3.2 manual that says "Strings contain Unicode characters."

The manual is wrong, then, subject to a pronouncement to the contrary, of course. I was on your side of the fence when this was discussed, pre-release. I was wrong then. My bet is that we are still wrong, now.

For the purpose of my sentence, the same thing in that code points correspond to characters,

Not in Unicode, they do not. By definition, a small number of code points (eg, U+FFFF) *never* did and *never* will correspond to characters. Since about Unicode 3.0, the same is true of surrogate code points. Some restrictions have been placed on what can be done with composed characters, so even with the PEP (which gives us code point arrays) we do not really get arrays of Unicode characters that fully conform to the model.

strings are NOT code point sequences. They are 2-byte code *unit* sequences.

I stand corrected on Unicode terminology. "Code unit" is what I meant, and what I understand Guido to have defined unicode objects as arrays of.

Any narrow build string with even 1 non-BMP char violates the standard.

Yup. That's by design.

...

Guido has made that absolutely clear on a number of occasions.

It is not clear what you mean, but recently on python-ideas he has reiterated that he intends bytes and strings to be conceptually different.

Sure. Nevertheless, practicality beat purity long ago, and that decision has never been rescinded AFAIK.

Bytes are computer-oriented binary arrays; strings are supposedly human-oriented character/codepoint arrays.

And indeed they are, in UCS-4 builds. But they are *not* in Unicode! Unicode violates the array model. Specifically, in handling composing characters, and in bidi, where arbitrary slicing of direction control characters will result in garbled display. The thing is, that 90% of applications are not really going to care about full conformance to the Unicode standard. Of the remaining 10%, 90% are not going to need both huge strings *and* ABI interoperability with C modules compiled for UCS-2, so UCS-4 is satisfactory. Of the remaining 1% of all applications, those that deal with huge strings *and* need full Unicode conformance, well, they need efficiency too almost by definition. They probably are going to want something more efficient than either the UTF-16 or the UTF-32 representation can provide, and therefore will need trickier, possibly app-specific, algorithms that probably do not belong in an initial implementation.

...

And the reasons have very little to do with lack of non-BMP characters to trip up the implementation. Changing those semantics should have been done before the release of Python 3.

The documentation was changed at least a bit for 3.0, and anyway, as indicated above, it is easy (especially for new users) to read the docs in a way that makes the current behavior buggy. I agree that the implementation should have been changed already.

I don't. I suspect Guido does not, even today.

Currently, the meaning of Python code differs on narrow versus wide build, and in a way that few users would expect or want.

Let them become developers, then, and show us how to do it better.

PEP 393 abolishes narrow builds as we now know them and changes semantics. I was answering a complaint about that change. If you do not like the PEP, fine.

No, I do like the PEP. However, it is only a step, a rather conservative one in some ways, toward conformance to the Unicode character model. In particular, it does nothing to resolve the fact that len() will give different answers for character count depending on normalization, and that slicing and indexing will allow you to cut characters in half (even in NFC, since not all composed characters have fully composed forms).

...

It is not clear to me that it is a good idea to try to decide on "the" correct implementation of Unicode strings in Python even today.

If the implementation is invisible to the Python user, as I believe it should be without specially introspection, and mostly invisible in the C-API except for those who intentionally poke into the details, then the implementation can be changed as the consensus on best implementation changes.

A naive implementation of UTF-16 will be quite visible in terms of performance, I suspect, and performance-oriented applications will "go behind the API's back" to get it. We're already seeing that in the people who insist that bytes are characters too, and string APIs should work on them just as they do on (Unicode) strings.

...

It's true that Python is going to need good libraries to provide correct handling of Unicode strings (as opposed to unicode objects).

Given that 3.0 unicode (string) objects are defined as Unicode character strings, I do not see the opposition.

I think they're not, I think they're defined as Unicode code unit arrays, and that the documentation is in error. If the documentation is correct, then Python 3.0 was released about 5 years too early, because correct handling of those objects as arrays of Unicode characters has never been implemented or even discussed in terms of proposed code that I know of. Martin has long claimed that the fact that I/O is done in terms of UTF-16 means that the internal representation is UTF-16, so I could be wrong. But when issues of slicing, len() values and so on have come up in the past, Guido has always said "no, there will be no change in semantics of builtins here".

Antoine Pitrou writes:

On Thu, 25 Aug 2011 01:34:17 +0900 "Stephen J. Turnbull" wrote:

...

Martin has long claimed that the fact that I/O is done in terms of UTF-16 means that the internal representation is UTF-16

Which I/O?

Eg, display of characters in the interpreter.

...

Eg, display of characters in the interpreter.

I don't know why you say it's "done in terms of UTF-16", then. Unicode strings are simply encoded to whatever character set is detected as the terminal's character set.

I think what he means (and what I meant when I said something similar): I/O will consider surrogate pairs in the representation when converting to the output encoding. This is actually relevant only for UTF-8 (I think), which converts surrogate pairs "correctly". This can be taken as a proof that Python 3.2 is "UTF-16 aware" (in some places, but not in others). With Python's I/O architecture, it is of course not *actually* the I/O which considers UTF-16, but the codec. Regards, Martin

...

PEP 393 abolishes narrow builds as we now know them and changes semantics. I was answering a complaint about that change. If you do not like the PEP, fine.

No, I do like the PEP. However, it is only a step, a rather conservative one in some ways, toward conformance to the Unicode character model.

I'd like to point out that the improved compatibility is only a side effect, not the primary objective of the PEP. The primary objective is the reduction in memory usage. (any changes in runtime are also side effects, and it's not really clear yet whether you get speedups or slowdowns on average, or no effect).

...

Given that 3.0 unicode (string) objects are defined as Unicode character strings, I do not see the opposition.

I think they're not, I think they're defined as Unicode code unit arrays, and that the documentation is in error.

That's just a description of the implementation, and not part of the language, though. My understanding is that the "abstract Python language definition" considers this aspect implementation-defined: PyPy, Jython, IronPython etc. would be free to do things differently (and I understand that there are plans to do PEP-393 style Unicode objects in PyPy).

Martin has long claimed that the fact that I/O is done in terms of UTF-16 means that the internal representation is UTF-16, so I could be wrong. But when issues of slicing, len() values and so on have come up in the past, Guido has always said "no, there will be no change in semantics of builtins here".

Not with these words, though. As I recall, it's rather like (still with different words) "len() will stay O(1) forever, regardless of any perceived incorrectness of this choice". An attempt to change the builtins to introduce higher complexity for the sake of correctness is what he rejects. I think PEP 393 balances this well, keeping the O(1) operations in that complexity, while improving the cross- platform "correctness" of these functions. Regards, Martin

On Wed, Aug 24, 2011 at 10:50 AM, "Martin v. Löwis" wrote:

Not with these words, though. As I recall, it's rather like (still with different words) "len() will stay O(1) forever, regardless of any perceived incorrectness of this choice".

And indexing/slicing will also be O(1).

An attempt to change the builtins to introduce higher complexity for the sake of correctness is what he rejects. I think PEP 393 balances this well, keeping the O(1) operations in that complexity, while improving the cross- platform "correctness" of these functions.

+1, I am comfortable with the balance struck by the PEP. -- --Guido van Rossum (python.org/~guido)

Terry Reedy writes:

Please suggest a re-wording then, as it is a bug for doc and behavior to disagree.

Strings contain Unicode code units, which for most purposes can be treated as Unicode characters. However, even as "simple" an operation as "s1[0] == s2[0]" cannot be relied upon to give Unicode-conforming results. The second sentence remains true under PEP 393.

...

...

For the purpose of my sentence, the same thing in that code points correspond to characters,

Not in Unicode, they do not. By definition, a small number of code points (eg, U+FFFF) *never* did and *never* will correspond to characters.

On computers, characters are represented by code points. What about the other way around? http://www.unicode.org/glossary/#C says code point: 1) i in range(0x11000) <broad definition> 2) "A value, or position, for a character" <narrow definition> (To muddy the waters more, 'character' has multiple definitions also.) You are using 1), I am using 2) ;-(.

No, you're not. You are claiming an isomorphism, which Unicode goes to great trouble to avoid.

I think you have it backwards. I see the current situation as the purity of the C code beating the practicality for the user of getting right answers.

Sophistry. "Always getting the right answer" is purity.

...

The thing is, that 90% of applications are not really going to care about full conformance to the Unicode standard.

I remember when Intel argued that 99% of applications were not going to be affected when the math coprocessor in its then new chips occasionally gave 'non-standard' answers with certain divisors.

In the case of Intel, the people who demanded standard answers did so for efficiency reasons -- they needed the FPU to DTRT because implementing FP in software was always going to be too slow. CPython, IMO, can afford to trade off because the implementation will necessarily be in software, and can be added later as a Python or C module.

I believe my scheme could be extended to solve [conformance for composing characters] also. It would require more pre-processing and more knowledge than I currently have of normalization. I have the impression that the grapheme problem goes further than just normalization.

Yes and yes. But now you're talking about database lookups for every character (to determine if it's a composing character). Efficiency of a generic implementation isn't going to happen. Anyway, in Martin's rephrasing of my (imperfect) memory of Guido's pronouncement, "indexing is going to be O(1)". And Nick's point about non-uniform arrays is telling. I have 20 years of experience with an implementation of text as a non-uniform array which presents an array API, and *everything* needs to be special-cased for efficiency, and *any* small change can have show-stopping performance implications. Python can probably do better than Emacs has done due to much better leadership in this area, but I still think it's better to make full conformance optional.

On Thu, Aug 25, 2011 at 12:29 PM, Guido van Rossum wrote:

Now I am happy to admit that for many Unicode issues the level at which we have currently defined things (code units, I think -- the thingies that encodings are made of) is confusing, and it would be better to switch to the others (code points, I think). But characters are right out.

Indeed, code points are the abstract concept and code units are the specific byte sequences that are used for serialisation (FWIW, I'm going to try to keep this straight in the future by remembering that the Unicode character set is defined as abstract points on planes, just like geometry). With narrow builds, code units can currently come into play internally, but with PEP 393 everything internal will be working directly with code points. Normalisation, combining characters and bidi issues may still affect the correctness of unicode comparison and slicing (and other text manipulation), but there are limits to how much of the underlying complexity we can effectively hide without being misleading. Cheers, Nick. -- Nick Coghlan   |   ncoghlan@gmail.com   |   Brisbane, Australia

On Thu, Aug 25, 2011 at 1:11 PM, Guido van Rossum wrote:

...

With narrow builds, code units can currently come into play internally, but with PEP 393 everything internal will be working directly with code points. Normalisation, combining characters and bidi issues may still affect the correctness of unicode comparison and slicing (and other text manipulation), but there are limits to how much of the underlying complexity we can effectively hide without being misleading.

Let's just define a Unicode string to be a sequence of code points and let libraries deal with the rest. Ok, methods like lower() should consider characters, but indexing/slicing should refer to code points. Same for '=='; we can have a library that compares by applying (or assuming?) certain normalizations. Tom C tells me that case-less comparison cannot use a.lower() == b.lower(); fine, we can add that operation to the library too. But this exceeds the scope of PEP 393, right?

Yep, I was agreeing with you on this point - I think you're right that if we provide a solid code point based core Unicode type (perhaps with some character based methods), then library support can fill the gap between handling code points and handling characters. In particular, a unicode character based string type would be significantly easier to write in Python than it would be in C (after skimming Tom's bug report at http://bugs.python.org/issue12729, I better understand the motivation and desire for that kind of interface and it sounds like Terry's prototype is along those lines). Once those mappings are thrashed out outside the core, then there may be something to incorporate directly around the 3.4 timeframe (or potentially even in 3.3, since it should already be possible to develop such a wrapper based on UCS4 builds of 3.2) However, there may an important distinction to be made on the Python-the-language vs CPython-the-implementation front: is another implementation (e.g. PyPy) *allowed* to implement character based indexing instead of code point based for 2.x unicode/3.x str type? Or is the code point indexing part of the language spec, and any character based indexing needs to be provided via a separate type or module? Regards, Nick. -- Nick Coghlan   |   ncoghlan@gmail.com   |   Brisbane, Australia

On 25/08/11 14:29, Guido van Rossum wrote:

Let's get things right so users won't have to worry about code points vs. code units any more.

What about things like the surrogateescape codec that deliberately use code units in non-standard ways? Will tricks like that still be possible if the code-unit level is hidden from the programmer? -- Greg

On Wed, Aug 24, 2011 at 8:34 PM, Greg Ewing wrote:

What about things like the surrogateescape codec that deliberately use code units in non-standard ways? Will tricks like that still be possible if the code-unit level is hidden from the programmer?

I would think that it should still be possible to explicitly put surrogates into a string, using the appropriate \uxxxx escape or chr(i) or some such approach; the basic string operations IMO shouldn't bother with checking for well-formed character sequences (just as they shouldn't care about normal forms). But decoding bytes from UTF-16 should not leave any surrogate pairs in, since interpreting those is part of the decoding. I'm not sure what should happen with UTF-8 when it (in flagrant violation of the standard, I presume) contains two separately-encoded surrogates forming a valid surrogate pair; probably whatever the UTF-8 codec does on a wide build today should be good enough. Similarly for encoding to UTF-8 on a wide build if one managed to create a string containing a surrogate pair. Basically, I'm for a garbage-in-garbage-out approach (with separate library functions to detect garbage if the app is worried about it). -- --Guido van Rossum (python.org/~guido)

On Thu, Aug 25, 2011 at 7:28 PM, Isaac Morland wrote:

On Thu, 25 Aug 2011, Guido van Rossum wrote:

...

I'm not sure what should happen with UTF-8 when it (in flagrant violation of the standard, I presume) contains two separately-encoded surrogates forming a valid surrogate pair; probably whatever the UTF-8 codec does on a wide build today should be good enough. Similarly for encoding to UTF-8 on a wide build if one managed to create a string containing a surrogate pair. Basically, I'm for a garbage-in-garbage-out approach (with separate library functions to detect garbage if the app is worried about it).

If it's called UTF-8, there is no decision to be taken as to decoder behaviour - any byte sequence not permitted by the Unicode standard must result in an error (although, of course, *how* the error is to be reported could legitimately be the subject of endless discussion).  There are security implications to violating the standard so this isn't just legalistic purity.

You have a point. The security issues cannot be seen separate from all the other issues. The folks inside Google who care about Unicode often harp on this. So I stand corrected. I am fine with codecs treating code points or code point sequences that the Unicode standard doesn't like (e.g. lone surrogates) the same way as more severe errors in the encoded bytes (lots of byte sequences already aren't valid UTF-8). I just hope this doesn't require normal forms or other expensive operations; I hope it's limited to rejecting invalid use of surrogates or other values that are not valid code points (e.g. 0, or >= 2**21).

Hmmm, doesn't look good:

Python 2.6.1 (r261:67515, Jun 24 2010, 21:47:49) [GCC 4.2.1 (Apple Inc. build 5646)] on darwin Type "help", "copyright", "credits" or "license" for more information.

...

...

...

'\xed\xb0\x80'.decode ('utf-8')

u'\udc00'

...

...

...

Incorrect!  Although this is a narrow build - I can't say what the wide build would do.

For reasons of practicality, it may be appropriate to provide easy access to a CESU-8 decoder in addition to the normal UTF-8 decoder, but it must not be called UTF-8.  Other variations may also find use if provided.

See UTF-8 RFC: http://www.ietf.org/rfc/rfc3629.txt

And CESU-8 technical report: http://www.unicode.org/reports/tr26/

Thanks for the links! I also like the term "supplemental character" (a code point >= 2**16). And I note that they talk about characters were we've just agreed that we should say code points... -- --Guido van Rossum (python.org/~guido)

Isaac Morland, 26.08.2011 04:28:

On Thu, 25 Aug 2011, Guido van Rossum wrote:

...

I'm not sure what should happen with UTF-8 when it (in flagrant violation of the standard, I presume) contains two separately-encoded surrogates forming a valid surrogate pair; probably whatever the UTF-8 codec does on a wide build today should be good enough. Similarly for encoding to UTF-8 on a wide build if one managed to create a string containing a surrogate pair. Basically, I'm for a garbage-in-garbage-out approach (with separate library functions to detect garbage if the app is worried about it).

If it's called UTF-8, there is no decision to be taken as to decoder behaviour - any byte sequence not permitted by the Unicode standard must result in an error (although, of course, *how* the error is to be reported could legitimately be the subject of endless discussion). There are security implications to violating the standard so this isn't just legalistic purity.

Hmmm, doesn't look good:

Python 2.6.1 (r261:67515, Jun 24 2010, 21:47:49) [GCC 4.2.1 (Apple Inc. build 5646)] on darwin Type "help", "copyright", "credits" or "license" for more information.

...

...

...

'\xed\xb0\x80'.decode ('utf-8') u'\udc00'

Incorrect! Although this is a narrow build - I can't say what the wide build would do.

Works the same for me in a wide Py2.7 build, but gives me this in Py3: Python 3.1.2 (r312:79147, Sep 27 2010, 09:57:50) [GCC 4.4.3] on linux2 Type "help", "copyright", "credits" or "license" for more information.

...

...

b'\xed\xb0\x80'.decode ('utf-8') Traceback (most recent call last): File "<stdin>", line 1, in <module> UnicodeDecodeError: 'utf8' codec can't decode bytes in position 0-2: illegal encoding

Same for current Py3.3 and the PEP393 build (although both have a better exception message now: "UnicodeDecodeError: 'utf8' codec can't decode bytes in position 0-1: invalid continuation byte"). Stefan

M.-A. Lemburg wrote:

Simply going with UCS-4 does not solve the problem, since even with UCS-4 storage, you can still have surrogates in your Python Unicode string.

Yes, but in that case, you presumably *intend* them to be treated as separate indexing units. If you didn't, there would be no need to use surrogates in the first place. -- Greg

...

What is non-conforming about comparing two code points?

Unicode conformance means treating characters correctly.

Re-read the text. You are interpreting something that isn't there.

...

Seriously, what does Unicode-conforming mean here?

Chapter 3, all verses. Here, specifically C6, p. 60. One would have to define the process executing "s1[0] == s2[0]" to be sure that even in the cases cited in the previous paragraph non-conformance is occurring

No, that's explicitly *not* what C6 says. Instead, it says that a process that treats s1 and s2 differently shall not assume that others will do the same, i.e. that it is ok to treat them the same even though they have different code points. Treating them differently is also conforming. Regards, Martin

Am 25.08.2011 11:39, schrieb Stephen J. Turnbull:

"Martin v. Löwis" writes:

...

No, that's explicitly *not* what C6 says. Instead, it says that a process that treats s1 and s2 differently shall not assume that others will do the same, i.e. that it is ok to treat them the same even though they have different code points. Treating them differently is also conforming.

Then what requirement does C6 impose, in your opinion?

In IETF terminology, it's a weak SHOULD requirement. Unless there are reasons not to, equivalent strings should be treated differently. It's a weak requirement because the reasons not to treat them equivalent are wide-spread.

- Ideally, an implementation would *always* interpret two canonical-equivalent sequences *identically*. There are practical circumstances under which implementations may reasonably distinguish them. (Emphasis mine.)

Ok, so let me put emphasis on *ideally*. They acknowledge that for practical reasons, the equivalent strings may need to be distinguished.

The examples given are things like "inspecting memory representation structure" (which properly speaking is really outside of Unicode conformance) and "ignoring collation behavior of combining sequences outside the repertoire of a specified language." That sounds like "Special cases aren't special enough to break the rules. Although practicality beats purity." to me. Treating things differently is an exceptional case, that requires sufficient justification.

And the common justification is efficiency, along with the desire to support the representation of unnormalized strings (else there would be an efficient implementation).

If our process is working with an external process (the OS's file system driver) whose definition includes the statement that "File names are sequences of Unicode characters", then C6 says our process must compare canonically equivalent sequences that it takes to be file names as the same, whether or not they are in the same normalized form, or normalized at all, because we can't assume the file system will treat them as different.

It may well happen that this requirement is met in a plain Python application. If the file system and GUI libraries always return NFD strings, then the Python process *will* compare equivalent sequences correctly (since it won't ever get any other representations).

*Users* will certainly take the viewpoint that two strings that display the same on their monitor should identify the same file when they use them as file names.

Yes, but that's the operating system's choice first of all. Some operating systems do allow file names in a single directory that are equivalent yet use different code points. Python then needs to support this operating system, despite the permission of the Unicode standard to ignore the difference.

I'm simply saying that the current implementation of strings, as improved by PEP 393, can not be said to be conforming.

I continue to disagree. The Unicode standard deliberately allows Python's behavior as conforming.

I would like to see something much more conformant done as a separate library (the Python Components for Unicode, say), intended to support users who need character-based behavior, Unicode-ly correct collation, etc., more than efficiency.

Wrt. normalization, I think all that's needed is already there. Applications just need to normalize all strings to a normal form of their liking, and be done. That's easier than using a separate library throughout the code base (let alone using yet another string type). Regards, Martin

"Martin v. Löwis" writes:

Am 25.08.2011 11:39, schrieb Stephen J. Turnbull:

...

"Martin v. Löwis" writes:

...

No, that's explicitly *not* what C6 says. Instead, it says that a process that treats s1 and s2 differently shall not assume that others will do the same, i.e. that it is ok to treat them the same even though they have different code points. Treating them differently is also conforming.

Then what requirement does C6 impose, in your opinion?

In IETF terminology, it's a weak SHOULD requirement. Unless there are reasons not to, equivalent strings should be treated differently. It's a weak requirement because the reasons not to treat them equivalent are wide-spread.

There are no "weak SHOULDs" and no "wide-spread reasons" in RFC 2119. RFC 2119 specifies "particular circumstances" and "full implications" that are "carefully weighed" before varying from SHOULD behavior. IMHO the Unicode Standard intends a full RFC 2119 "SHOULD" here.

Yes, but that's the operating system's choice first of all. Some operating systems do allow file names in a single directory that are equivalent yet use different code points. Python then needs to support this operating system, despite the permission of the Unicode standard to ignore the difference.

Sure, and that's one of several such reasons why I think the PEP's implementation of unicodes as arrays of code points is an optimal balance. But the Unicode standard does not "permit" ignoring the difference here, except in the sense that *the Unicode standard doesn't apply at all* and therefore doesn't forbid it. The OSes in question are not conforming processes, and presumably don't claim to be. Because most of the processes Python interacts with won't be conforming processes (not even the majority of textual applications, for a while), Python does not need to be, and *should not* be, a conforming Unicode process for most of what it does. Not even for much of its text processing. Also, to the extent that Python is a general-purpose language, I see nothing wrong and lots of good in having a non-conformant code point array type as the platform for implementing conforming Unicode library(ies). But this is not user/developer-friendly at all:

Wrt. normalization, I think all that's needed is already there. Applications just need to normalize all strings to a normal form of their liking, and be done. That's easier than using a separate library throughout the code base (let alone using yet another string type).

But many users have never heard of normalization. And that's *just* normalization. There is a whole raft of other requirements for conformance (collation, case, etc). The point is that with such a library and string type, various aspects of conformance to Unicode, as well as conformance to associated standards (eg, the dreaded UTS #18 ;-) can be added to the library over time, and most users (those who don't need to squeeze every ounce of performance out of Python) can be blissfully unaware of what, if anything, they're conforming to. Just upgrade the library to get the best Unicode support (in terms of conformance) that Python has to offer. But for the reasons you (and Guido and Nick and ...) give, it's not reasonable to put all that into core Python, not anytime soon. Not to mention that as a work-in-progress, it can hardly be considered stable enough for the stdlib. That is what Terry Reedy is getting at, AIUI. "Batteries included" should mean as much Unicode conformance as we can reasonably provide should be *conveniently* available. The ideal (given the caveat about efficiency) would be *one* import statement and a ConformingUnicode type that acts "just like a string" in all ways, except that (1) it indexes and counts on characters (preferably "grapheme clusters" :-), (2) does collation, regexps, and the like conformant to the Unicode standard, and (3) may be quite inefficient from the point of view of bit- shoveling net applications and the like. Of course most of (2) is going to take quite a while, but (1) and (3) should not be that hard to accomplish (especially (3) ;-).

...

I'm simply saying that the current implementation of strings, as improved by PEP 393, can not be said to be conforming.

I continue to disagree. The Unicode standard deliberately allows Python's behavior as conforming.

That's up to you. I doubt very many users or application developers will see it that way, though. I think they would prefer that we be conservative about what we call "conformant", and tell them precisely what they need to do to get what they consider conformant behavior from Python. That's easier if we share definitions of conformant with them. And surely there would be great joy on the battlements if there were a one-import way to spell "all the Unicode conformance you can give me, please". The problem with your legalistic approach, as I see it, is that if our definition is looser than the users', all their surprises will be unpleasant. That's not good.

On Thu, Aug 25, 2011 at 2:39 AM, Stephen J. Turnbull wrote:

If our process is working with an external process (the OS's file system driver) whose definition includes the statement that "File names are sequences of Unicode characters",

Does any OS actually say that? Don't they usually say "in a specific normal form" or "they're just bytes"?

then C6 says our process must compare canonically equivalent sequences that it takes to be file names as the same, whether or not they are in the same normalized form, or normalized at all, because we can't assume the file system will treat them as different.  If we do treat them as different, our users will get very upset (eg, if we don't signal a duplicate file name input by the user, and then the OS proceeds to overwrite an existing file).

The solution here is to let the OS do the check, e.g. with os.path.exists() or os.stat(). It would be wrong to write an app that checked for file existence by doing naive lookups in os.listdir() output. -- --Guido van Rossum (python.org/~guido)

On 8/24/2011 7:29 PM, Guido van Rossum wrote:

(Hey, I feel a QOTW coming. "Standards? We don't need no stinkin' standards."http://en.wikipedia.org/wiki/Stinking_badges :-)

Which deserves an appropriate, follow-on, misquote: Guido says the Unicode standard stinks. ˚͜˚ <- and a Unicode smiley to go with it!

On Wed, Aug 24, 2011 at 3:06 AM, Terry Reedy wrote:

Excuse me for believing the fine 3.2 manual that says "Strings contain Unicode characters." (And to a naive reader, that implies that string iteration and indexing should produce Unicode characters.)

The naive reader also doesn't know the difference between characters, code points and code units. It's the advanced, Unicode-aware reader who is confused by this phrase in the docs. It should say code units; or perhaps code units for narrow builds and code points for wide builds. With PEP 393 we can unconditionally say code points, which is much better. We should try to remove our use of "characters" -- or else we should *define* our use of the term "characters" as "what the Unicode standard calls code points". -- --Guido van Rossum (python.org/~guido)

On Thu, Aug 25, 2011 at 6:40 PM, Ezio Melotti wrote:

On Fri, Aug 26, 2011 at 1:54 AM, Guido van Rossum wrote:

...

On Wed, Aug 24, 2011 at 3:06 AM, Terry Reedy wrote:

...

Excuse me for believing the fine 3.2 manual that says "Strings contain Unicode characters." (And to a naive reader, that implies that string iteration and indexing should produce Unicode characters.)

The naive reader also doesn't know the difference between characters, code points and code units. It's the advanced, Unicode-aware reader who is confused by this phrase in the docs. It should say code units; or perhaps code units for narrow builds and code points for wide builds.

For UTF-16/32 (i.e. narrow/wide), talking about "code units"[0] should be correct.  Also note that:   * for both, every "code unit" has a specific "codepoint" (including lone surrogates), so it might be OK to talk about "codepoints" too, but   * only for wide builds every "codepoints" is represented by a single, 32-bits "code unit".  In narrow builds, non-BMP chars are represented by a "code unit sequence" of two elements (i.e. a "surrogate pair").

The more I think about it the more it seems to me that the biggest problem is that in narrow builds it is ambiguous whether (unicode) strings contain code units, i.e. are *encoded* code points, or whether they contain (decoded) code points. In a sense this is repeating the ambiguity of 8-bit strings in Python 2, which are sometimes assumed to contain ASCII or Latin-1 (i.e., code points with a limited range) or UTF-8 (i.e., code units). I know that by now I am repeating myself, but I think it would be really good if we could get rid of this ambiguity. PEP 393 seems the best way forward, even if it doesn't directly address what to do for IronPython or Jython, both of which have to deal with a pervasive native string type that contains UTF-16. IIUC, CPython on Windows will work just fine with PEP 393, even if it means that there is a bit more translation between Python strings and the OS native wchar_t[] type. I assume that the data volumes going through the OS APIs is relatively constrained, since data actually written to or read from a file will still be bytes, possibly run through a codec (if it's a text file), and not go through one of the wchar_t[] APIs -- the latter are used for things like filenames, which are much smaller.

Since "code unit" refers to the *minimal* bit combination, in UTF-8 characters that needs 2/3/4 bytes, are represented with a "code unit sequence" made of 2/3/4 "code units" (so in UTF-8 "code units" and "code points" overlaps only for the ASCII range).

Actually I think UTF-8 is best thought of as an encoding for code points, not characters -- the subtle difference between these two should be of no concern to the UTF-8 codec (unless it is a validating codec).

...

With PEP 393 we can unconditionally say code points, which is much better. We should try to remove our use of "characters" -- or else we should *define* our use of the term "characters" as "what the Unicode standard calls code points".

Character usually works fine, especially for naive readers.  Even Unicode-aware readers often confuse between the several terms, so using a simple term and pointing to a more accurate description sounds like a better idea to me.

We may well have no choice -- there is just too much documentation that naively refers to characters while really referring to code units or code points.

Note that there's also another important term[1]: """ Unicode Scalar Value. Any Unicode code point except high-surrogate and low-surrogate code points. In other words, the ranges of integers 0 to D7FF16 and E00016 to 10FFFF16 inclusive. """

This seems to involve validation. I think all validation should be sequestered to specific APIs (e.g. certain codecs) and the string type should not care about it. Depending on what they are doing, applications may have to be aware of many subtleties in order to always avoid generating "invalid" (or not well-formed-- what's the difference?) strings.

For example the UTF codecs produce sequences of "code units" (of 8, 16, 32 bits) that represent "scalar values"[2][3]:

Chapter 3 [4] says: """ 3.9 Unicode Encoding Forms The Unicode Standard supports three character encoding forms: UTF-32, UTF-16, and UTF-8. Each encoding form maps the Unicode code points U+0000..U+D7FF and U+E000..U+10FFFF to unique code unit sequences. [...]

I really don't mind whether our codecs actually make exceptions for surrogates (lone or otherwise). The only requirement I care about is that surrogate-free strings round-trip correctly. Again, apps that want to conform to the requirements regarding surrogates can implement their own validation, and certainly at some point we should offer a validation library as part of the stdlib -- but it should be up to the app whether and when to use it.

 D76 Unicode scalar value: Any Unicode code point except high-surrogate and low-surrogate code points.      • As a result of this definition, the set of Unicode scalar values consists of the ranges 0 to D7FF and E000 to 10FFFF, inclusive.  D77 Code unit: The minimal bit combination that can represent a unit of encoded text for processing or interchange. [...]  D79 A Unicode encoding form assigns each Unicode scalar value to a unique code unit sequence. """

On the other hand, Python Unicode strings are not limited to scalar values, because they can also contain lone surrogates.

Right.

I hope this helps clarify the terminology a bit and doesn't add more confusion, but if we want to use the Unicode terms we should get them right.  (Also note that I might have misunderstood something, even if I've been careful with the terms and I double-checked and quoted the relevant parts of the Unicode standard.)

I'm not more confused than I was, but I think we should reduce the number of Unicode terms we care about rather than increase them. If we only ever had to talk about code points and encoded byte sequences I'd be happy -- although in practice we also need to acknowledge the existence of characters that may be represented by multiple code points, since islower(), lower() etc. may need these (and also the re module). Other concepts we may have to at least acknowledge include various normal forms, equivalence, and collation sequences (which are language-dependent?). It would be lovely if someone wrote up an informational PEP so that we don't all have to lug around a copy of the Unicode standard.

Best Regards, Ezio Melotti

[0]: From the chapter 3 [4],  D77 Code unit: The minimal bit combination that can represent a unit of encoded text for processing or interchange.    • Code units are particular units of computer storage. Other character encoding standards typically use code units defined as 8-bit units—that is, octets.      The Unicode Standard uses 8-bit code units in the UTF-8 encoding form, 16-bit code units in the UTF-16 encoding form, and 32-bit code units in the UTF-32 encoding form. [1]: http://unicode.org/glossary/#unicode_scalar_value [2]: Apparently Python 3 raises an error while encoding lone surrogates in UTF-8, but it doesn't for UTF-16 and UTF-32. From the chapter 3 [4],  D91: "Because surrogate code points are not Unicode scalar values, isolated UTF-16 code units in the range 0xD800..0xDFFF are ill-formed."  D92: "Because surrogate code points are not included in the set of Unicode scalar values, UTF-32 code units in the range 0x0000D800..0x0000DFFF are ill-formed." I think this should be fixed. [3]: Note that I'm talking about codecs used to encode/decode Unicode strings to/from bytes here, it's perfectly fine for Python itself to represent lone surrogates in its *internal* representations, regardless of what encoding it's using. [4]: Chapter 3: http://www.unicode.org/versions/Unicode6.0.0/ch03.pdf

-- --Guido van Rossum (python.org/~guido)

IronPython and Jython can retain UTF-16 as their native form if that makes interop cleaner, but in doing so they need to ensure that basic operations like indexing and len work in terms of code points, not code units, if they are to conform.

That means that they won't conform, period. There is no efficient maintainable implementation strategy to achieve that property, and it may take well years until somebody provides an efficient unmaintainable implementation.

Does this make sense, or have I completely misunderstood things?

You seem to assume it is ok for Jython/IronPython to provide indexing in O(n). It is not. However, non-conformance may not be that much of an issue. They do not conform in many other aspects, either (such as not supporting Python 3, for example, or not supporting the C API) that they may well chose to ignore such a minor requirement if there was one. For BMP strings, they conform fine, and it may well be that Jython eithers either don't have non-BMP strings, or don't care whether len() or indexing of their non-BMP strings is "correct". Regards, Martin

On Fri, Aug 26, 2011 at 3:29 AM, Stefan Behnel wrote:

"Martin v. Löwis", 26.08.2011 11:29:

...

You seem to assume it is ok for Jython/IronPython to provide indexing in O(n). It is not.

I think we can leave this discussion aside.

(And yet, you keep arguing. :-)

Jython and IronPython have their own platform specific constraints to which they need to adapt their implementation. For a Jython user, it means a lot to be able to efficiently pass strings (and other data) back and forth between Jython and other JVM code, and it's not hard to guess that the same is true for IronPython/.NET users. After all, the platform integration is the very *reason* for most users to select one of these implementations.

Right.

Besides, what if these implementations provided indexing in, say, O(log N) instead of O(1) or O(N), e.g. by building a tree index into each string? You could have an index that simply marks runs of surrogate pairs and BMP substrings, thus providing a likely-to-be-somewhat-compact index. That index would obviously have to be built, but so do the different string representations in post-PEP-393 CPython, especially on Windows, as I have learned.

Eek. No, please. Those platforms' native string types have length and slicing operations that are O(1) and work in terms of 16-bit code points. Python should use those. It would be awful if Java and Python code doing the same manipulations on the same string would come to different conclusions because Python tried to paper over surrogates. I dug up some evidence for Java, at least: http://download.oracle.com/javase/1,5.0/docs/api/java/lang/CharSequence.html... """ length int length() Returns the length of this character sequence. The length is the number of 16-bit chars in the sequence. Returns: the number of chars in this sequence """ This is quite explicit about counting 16-bit code units. I've found similar info about .NET, which defines "char" as a 16-bit quantity and string length in terms of the number of "char" items.

Would such a less severe violation of the strict O(1) rule still be "not ok"? I think this is not such a clear black-and-white issue. Both implementations have notably different performance characteristics than CPython in some more or less important areas, as does PyPy. At some point, the language compliance label has to account for that.

Since you had to ask, I have to declare that, indeed, non-O(1) behavior would not be okay for those platforms. All in all, I don't think we should legislate Python strings to be able to support 21-bit code points using O(1) indexing. PEP 393 makes this possible for CPython, and it's been said that PyPy can follow suit. But it'll be a "quality-of-implementation" issue, not built into the language spec. -- --Guido van Rossum (python.org/~guido)

On Fri, Aug 26, 2011 at 10:13 AM, Paul Moore wrote:

On 26 August 2011 18:02, Guido van Rossum wrote:

...

Eek. No, please. Those platforms' native string types have length and slicing operations that are O(1) and work in terms of 16-bit code points. Python should use those. It would be awful if Java and Python code doing the same manipulations on the same string would come to different conclusions because Python tried to paper over surrogates.

*That* is actually the erroneous assumption I had made - that the Java and .NET native string type had code point semantics (i.e., took surrogates into account). As that isn't the case, my comments aren't valid - and I agree that having common semantics (and hence exposing surrogates) is too important to lose.

Those platforms probably *also* have libraries of operations to support writing apps that conform to the Unicode standard. But those apps will have to be aware of the difference between the "naive" length of a string and the number of code points of characters in it.

On the other hand, that pretty much establishes that whatever PEP 393 achieves in terms of allowing all builds of CPython to offer code point semantics, the language definition can't mandate it.

The most severe consequence to me seems that the stdlib (which is reused by those other platforms) cannot assume CPython's ideal world -- even if specific apps sometimes can. -- --Guido van Rossum (python.org/~guido)

On Fri, Aug 26, 2011 at 2:29 AM, "Martin v. Löwis" wrote:

...

IronPython and Jython can retain UTF-16 as their native form if that makes interop cleaner, but in doing so they need to ensure that basic operations like indexing and len work in terms of code points, not code units, if they are to conform.

That means that they won't conform, period. There is no efficient maintainable implementation strategy to achieve that property, and it may take well years until somebody provides an efficient unmaintainable implementation.

...

Does this make sense, or have I completely misunderstood things?

You seem to assume it is ok for Jython/IronPython to provide indexing in O(n). It is not.

Indeed.

However, non-conformance may not be that much of an issue. They do not conform in many other aspects, either (such as not supporting Python 3, for example, or not supporting the C API) that they may well chose to ignore such a minor requirement if there was one. For BMP strings, they conform fine, and it may well be that Jython eithers either don't have non-BMP strings, or don't care whether len() or indexing of their non-BMP strings is "correct".

I think this is fine. I had been hoping that all Python implementations claiming compatibility with version 3.3 of the language reference would be free of worries about surrogates, but it simply doesn't make sense. And yes, I'm well aware that PEP 393 is only for CPython. It's just that I had hoped that it would get rid of some of Tom C's specific complaints for all Python implementations; but it really seems impossible to do so. One consequence may be that the standard library, to the extent it is shared by other implementations, may still have to worry about surrogates and other issues inherent in narrow builds or other 16-bit-based string types. We'll cross that bridge when we get to it. -- --Guido van Rossum (python.org/~guido)

On Fri, Aug 26, 2011 at 3:57 PM, Terry Reedy wrote:

On 8/26/2011 5:29 AM, "Martin v. Löwis" wrote:

...

...

IronPython and Jython can retain UTF-16 as their native form if that makes interop cleaner, but in doing so they need to ensure that basic operations like indexing and len work in terms of code points, not code units, if they are to conform.

My impression is that a UFT-16 implementation, to be properly called such, must do len and [] in terms of code points, which is why Python's narrow builds are called UCS-2 and not UTF-16.

I don't think anyone else has that impression. Please cite chapter and verse if you really think this is important. IIUC, UCS-2 does not allow surrogate pairs, whereas Python (and Java, and .NET, and Windows) 16-bit strings all do support surrogate pairs. And they all have a len or length function that counts code units, not code points.

...

That means that they won't conform, period. There is no efficient maintainable implementation strategy to achieve that property,

Given that both 'efficient' and 'maintainable' are relative terms, that is you pessimistic opinion, not really a fact.

...

it may take well years until somebody provides an efficient unmaintainable implementation.

...

Does this make sense, or have I completely misunderstood things?

You seem to assume it is ok for Jython/IronPython to provide indexing in O(n). It is not.

Why do you keep saying that O(n) is the alternative? I have already given a simple solution that is O(logk), where k is the number of non-BMP characters/codepoints/surrogate_pairs if there are any, and O(1) otherwise (for all BMP chars). It uses O(k) space. I think that is pretty efficient. I suspect that is the most time efficient possible without using at least as much space as a UCS-4 solution. The fact that you and other do not want this for CPython should not preclude other implementations that are more tied to UTF-16 from exploring the idea.

Maintainability partly depends on whether all-codepoint support is built in or bolted on to a BMP-only implementation burdened with back compatibility for a code unit API. Maintainability is probably harder with a separate UTF-32 type, which CPython has but which I gather Jython and Iron-Python do not. It might or might not be easier is there were a separate internal character type containing a 32 bit code point value, so that interation and indexing (and single char slicing) always returned the same type of object regardless of whether the character was in the BMP or not. This certainly would help all the unicode database functions.

Tom Christiansen appears to have said that Perl is or will use UTF-8 plus auxiliary arrays. If so, we will find out if they can maintain it.

Their API style is completely different from ours. What Perl can maintain has little bearing on what Python can. -- --Guido van Rossum (python.org/~guido)

On Aug 26, 2011, at 8:51 PM, Terry Reedy wrote:

On 8/26/2011 8:42 PM, Guido van Rossum wrote:

...

On Fri, Aug 26, 2011 at 3:57 PM, Terry Reedy wrote:

...

...

My impression is that a UFT-16 implementation, to be properly called such, must do len and [] in terms of code points, which is why Python's narrow builds are called UCS-2 and not UTF-16.

I don't think anyone else has that impression. Please cite chapter and verse if you really think this is important. IIUC, UCS-2 does not allow surrogate pairs, whereas Python (and Java, and .NET, and Windows) 16-bit strings all do support surrogate pairs. And they all

For that reason, I think UTF-16 is a better term that UCS-2 for narrow builds (whether or not the above impression is true).

I agree. It's weird to call something UCS-2 if code points above 65535 are representable. The naming convention for codecs is that the UTF prefix is used for lossless encodings that cover the entire range of Unicode. "The first amendment to the original edition of the UCS defined UTF-16, an extension of UCS-2, to represent code points outside the BMP." Raymond

On Mon, 29 Aug 2011 12:43:24 +0900 "Stephen J. Turnbull" wrote:

Since when can s[0] represent a code point outside the BMP, for s a Unicode string in a narrow build?

Remember, the UCS-2/narrow vs. UCS-4/wide distinction is *not* about what Python supports vs. the outside world. It's about what the str/ unicode type is an array of.

Why would that be? Antoine.

The problem with a narrow build (whether for space efficiency in CPython or for platform compatibility in Jython and IronPython) is not that we have no UTF-16 codecs. It's that array ops aren't UTF-16 conformant.

Sorry, what is a conformant UTF-16 array op? Thanks Antoine.

On Tue, Aug 30, 2011 at 7:55 PM, Stephen J. Turnbull wrote:

Antoine Pitrou writes:

 > Sorry, what is a conformant UTF-16 array op?

For starters, one that doesn't ever return lone surrogates, but rather interprets surrogate pairs as Unicode code points as in UTF-16.  (This is not a Unicode standard definition, it's intended to be suggestive of why many app writers will be distressed if they must use Python unicode/str in a narrow build without a fairly comprehensive library that wraps the arrays in operations that treat unicode/str as an array of code points.)

That sounds like a contradiction -- it wouldn't be a UTF-16 array if you couldn't tell that it was using UTF-16. -- --Guido van Rossum (python.org/~guido)

On 8/30/2011 11:03 PM, Stephen J. Turnbull wrote:

Guido van Rossum writes:

...

On Tue, Aug 30, 2011 at 7:55 PM, Stephen J. Turnbull wrote:

...

...

For starters, one that doesn't ever return lone surrogates, but rather interprets surrogate pairs as Unicode code points as in UTF-16. (This is not a Unicode standard definition, it's intended to be suggestive of why many app writers will be distressed if they must use Python unicode/str in a narrow build without a fairly comprehensive library that wraps the arrays in operations that treat unicode/str as an array of code points.)

That sounds like a contradiction -- it wouldn't be a UTF-16 array if you couldn't tell that it was using UTF-16.

Well, that's why I wrote "intended to be suggestive". The Unicode Standard does not specify at all what the internal representation of characters may be, it only specifies what their external behavior must be when two processes communicate. (For "process" as used in the standard, think "Python modules" here, since we are concerned with the problems of folks who develop in Python.) When observing the behavior of a Unicode process, there are no UTF-16 arrays or UTF-8 arrays or even UTF-32 arrays; only arrays of characters.

Thus, according to the rules of handling a UTF-16 stream, it is an error to observe a lone surrogate or a surrogate pair that isn't a high-low pair (Unicode 6.0, Ch. 3 "Conformance", requirements C1 and C8-C10). That's what I mean by "can't tell it's UTF-16". And I understand those requirements to mean that operations on UTF-16 streams should produce UTF-16 streams, or raise an error. Without that closure property for basic operations on str, I think it's a bad idea to say that the representation of text in a str in a pre-PEP-393 "narrow" build is UTF-16. For many users and app developers, it creates expectations that are not fulfilled.

It's true that common usage is that an array of code units that usually conforms to UTF-16 may be called "UTF-16" without the closure properties. I just disagree with that usage, because there are two camps that interpret "UTF-16" differently. One side says, "we have an array representation in UTF-16 that can handle all Unicode code points efficiently, and if you think you need more, think again", while the other says "it's too painful to have to check every result for valid UTF-16, and we need a UTF-16 type that supports the usual array operations on *characters* via the usual operators; if you think otherwise, think again."

Note that despite the (presumed) resolution of the UTF-16 issue for CPython by PEP 393, at some point a very similar discussion will take place over "characters" anyway, because users and app developers are going to want a type that handles composition sequences and/or grapheme clusters for them, as well as comparison that respects canonical equivalence, even if it is inefficient compared to str. That's why I insisted on use of "array of code points" to describe the PEP 393 str type, rather than "array of characters".

On topic: So from reading all this discussion, I think this point is rather a key one... and it has been made repeatedly in different ways: Arrays are not suitable for manipulating Unicode character sequences, and the str type is an array with a veneer of text manipulation operations, which do not, and cannot, by themselves, efficiently implement Unicode character sequences. Python wants to, should, and can implement UTF-16 streams, UTF-8 streams, and UTF-32 streams. It should, and can implement streams using other encodings as well, and also binary streams. Python wants to, should, and can implement 8-bit, 16-bit, 32-bit, and 64-bit arrays. These are efficient to access, index, and slice. Python implements a veneer on some 8-bit, 16-bit, and 32-bit arrays called str (this will be more true post-PEP 393, although it is true with caveats presently), which interpret array elements as code units (currently) or codepoints (post-PEP), and implements operations that are interesting for text processing, with caveats. There is presently no support for arrays of Unicode grapheme clusters or composed characters. The Python type called str may or may not be properly documented (to the extent that there is confusion between the actual contents of the elements of the type, and the concept of character as defined by Unicode). From comments Guido has made, he is not interested in changing the efficiency or access methods of the str type to raise the level of support of Unicode to the composed character, or grapheme cluster concepts. The str type itself can presently be used to process other character encodings: if they are fixed width < 32-bit elements those encodings might be considered Unicode encodings, but there is no requirement that they are, and some operations on str may operate with knowledge of some Unicode semantics, so there are caveats. So it seems that any semantics in support of composed characters, grapheme clusters, or codepoints-stored-as-<32-bit-code-units, must be created as either an add-on Python package (in Python) or C extension, or a combination. It could be based on extensions to the existing str type, or it could be based on the array type, or it could based on the bytes type. It could use an internal format of 32-bit codepoints, PEP 393 variable-size codepoints, or 8- or 16-bit codeunits. In addition to the expected stream operations, character length, indexing, and slicing operations, additional more complex operations would be expected on Unicode string values: regular expressions, comparisons, collations, case-shifting, and perhaps more. RTL and LTR awareness would add complexity to all operations, or at least variants of all operations. The questions are: 1) Is anyone interested in writing a PEP for such a thing? 2) Is anyone interested in writing an implementation for such a thing? 3) How many conflicting opinions and arguments will be spawned, making the poor person or persons above lose interest? Brainstorming ideas (which may wander off-topic in some regards, but were all inspired by this discussion): BI-0: Tom's analysis makes me think that the UTF-8 encoding, since it is smallest on the average language, and an implementation based on a foundation type of bytes or 'B' arrays, plus some side indexes of some sort, could be an appropriate starting point. UTF-8 is variable length, but so are composed characters and grapheme clusters. Building an array, each of whose units could hold the largest grapheme cluster would seem extremely inefficient, just like 32-bit Unicode is extremely inefficient for dealing with ASCII, so variable length units seem to be an imperative part of a solution. At least until one thinks up BI-2. BI-1: Perhaps a 32-bit base, with the upper 11 bits used to cache character characteristics from various character attribute database lookups could be an effective alternative, but wouldn't eliminate the need for dealing with variable length units for length, indexing, and slicing operations. BI-2: Maybe a 32-bit base would be useful so that one high bit could be used to flag that this character position actually holds an index to a multi-codepoint character, and the index would then hold the actual codes for that character. This would allow for at most 2^31 (and memory limited) different multi-codepoint characters in a string (or perhaps per application, if the multi-codepoint characters are shared between strings), but would suddenly allow array indexing of grapheme clusters and composed characters... with double-indexing required for multi-codepoint character access. [This idea seems similar to one that was mentioned elsewhere in this thread, suggesting that private use characters could be used to represent multi-codepoint characters, but (a) doesn't infringe on private uses, and (b) allows for a greater number of multi-codepoint characters to be used.] BI-3: both BI-1 and BI-2 would also allow themselves to be built on top of PEP 393 str... allowing multi-codepoint-character-supporting applications to benefit from the space efficiencies of PEP 393 when no multi-codepoint characters are fed into the application. BI-4: Since Unicode has 21-bit codepoints, one wonders if 24-bit array elements might be appropriate, rather than 32-bit. BI-2 could still operate, with a theoretical reduction to 2^23 possible multi-codepoint characters in an application. Access would be less efficient, but still O(1), and 25% of the space would be saved. This idea could be applied to PEP 393 independently of multi-codepoint character support. BI-5: I'm pretty sure there are inappropriate or illegal sequences of combining characters that should not stand alone. One example of this is lone surrogates. Such characters out of an appropriate sequence could be flagged with a high-bit so that they could be quickly recognized as illegal Unicode, but codecs could be provided to allow them to round-trip, and applications could recognize immediately that they should be handled as "binary gibberish" in an otherwise Unicode stream. This idea could be applied to PEP 393 independently of additional multi-codepoint character support. BI-6: Maybe another high bit could be used with a different codec error handler instead of using lone surrogates when decoding not-quite-conformant byte streams (such as OS filenames). Sad we didn't think of this one before doing all the lone surrogate stuff. Of course, this solution wouldn't work on narrow builds, because not even surrogates can represent high bits above Unicode codepoints! But once we have PEP 393, we _could_ replace inappropriate use of lone surrogates, with use of out-of-the-Unicode-codepoint range integers, without introducing ambiguity in the interpretation of lone surrogates. This idea could be applied to PEP 393 independently of multi-codepoint character support. Glenn

On 8/31/2011 5:21 AM, Stephen J. Turnbull wrote:

Glenn Linderman writes:

...

From comments Guido has made, he is not interested in changing the efficiency or access methods of the str type to raise the level of support of Unicode to the composed character, or grapheme cluster concepts.

IMO, that would be a bad idea,

OK you agree with Guido.

as higher-level Unicode support should either be a wrapper around full implementations such as ICU (or platform support in .NET or Java), or written in pure Python at first. Thus there is a need for an efficient array of code units type. PEP 393 allows this to go to the level of code points, but evidently that is inappropriate for Jython and IronPython.

...

The str type itself can presently be used to process other character encodings:

Not really. Remember, on input codecs always decode to Unicode and on output they always encode from Unicode. How do you propose to get other encodings into the array of code units?

Here are two ways, there may be more: custom codecs, direct assignment

...

[A "true Unicode" type] could be based on extensions to the existing str type, or it could be based on the array type, or it could based on the bytes type. It could use an internal format of 32-bit codepoints, PEP 393 variable-size codepoints, or 8- or 16-bit codeunits.

In theory yes, but in practice all of the string methods and libraries like re operate on str (and often but not always bytes; in particular, codecs always decode from byte and encode to bytes).

Why bother with anything except arrays of code points at the start? PEP 393 makes that time-efficient and reasonably space-efficient as a starting point and allows starting with re or MRAB's regex to get basic RE functionality or good UTS #18 functionality respectively. Plus str already has all the usual string operations (.startswith(), .join(), etc), and we have modules for dealing with the Unicode Character Database. Why waste effort reintegrating with all that, until we have common use cases that need more efficient representation?

String methods could be reimplemented on any appropriate type, of course. Rejecting alternatives too soon might make one miss the best design.

There would be some issue in coming up with an appropriate UTF-16 to code point API for Jython and IronPython, but Terry Reedy has a rather efficient library for that already.

Yes, Terry's implementation is interesting, and inspiring, and that concept could be extended to a variety of interesting techniques: codepoint access of code unit representations, and multi-codepoint character access on top of either code unit or codepoint representations.

So this discussion of alternative representations, including use of high bits to represent properties, is premature optimization ... especially since we don't even have a proto-PEP specifying how much conformance we want of this new "true Unicode" type in the first place.

We need to focus on that before optimizing anything.

You may call it premature optimization if you like, or you can ignore the concepts and emails altogether. I call it brainstorming for ideas, looking for non-obvious solutions to the problem of representation of Unicode. I found your discussion of streams versus arrays, as separate concepts related to Unicode, along with Terry's bisect indexing implementation, to rather inspiring. Just because Unicode defines streams of codeunits of various sizes (UTF-8, UTF-16, UTF-32) to represent characters when processes communicate and for storage (which is one way processes communicate), that doesn't imply that the internal representation of character strings in a programming language must use exactly that representation. While there are efficiencies in using the same representation as is used by the communications streams, there are also inefficiencies. I'm unaware of any current Python implementation that has chosen to use UTF-8 as the internal representation of character strings (I'm also aware Perl has made that choice), yet UTF-8 is one of the commonly recommend character representations on the Linux platform, from what I read. So in that sense, Python has rejected the idea of using the "native" or "OS configured" representation as its internal representation. So why, then, must one choose from a repertoire of Unicode-defined stream representations if they don't meet the goal of efficient length, indexing, or slicing operations on actual characters?

Stephen J. Turnbull:

...  Eg, this is why the common GUIs for Unix (X.org, GTK+, and Qt) either provide or require UTF-8 coding for their text.

Qt uses UTF-16 for its basic QString type. While QString is mostly treated as a black box which you can create from input buffers in any encoding, the only encoding allowed for a contents-by-reference QString (QString::fromRawData) is UTF-16. http://doc.qt.nokia.com/latest/qstring.html#fromRawData Neil

On 8/31/2011 10:12 AM, Guido van Rossum wrote:

On Wed, Aug 31, 2011 at 1:09 AM, Glenn Linderman wrote:

...

So from reading all this discussion, I think this point is rather a key one... and it has been made repeatedly in different ways: Arrays are not suitable for manipulating Unicode character sequences, and the str type is an array with a veneer of text manipulation operations, which do not, and cannot, by themselves, efficiently implement Unicode character sequences. I think this is too strong. The str type is indeed an array, and you can build useful Unicode manipulation APIs on top of it. Just like bytes are not UTF-8, but can be used to represent UTF-8 and a fully-compliant UTF-8 codec can be implemented on top of it.

This statement is a logical conclusion of arguments presented in this thread. 1) Applications that wish to do grapheme access, wish to do it by grapheme array indexing, because that is the efficient way to do it. 2) As long as str is restricted to holding Unicode code units or code points, then it cannot support grapheme array indexing efficiently. I have not declared that useful Unicode manipulations APIs cannot be built on top of str, only that efficiency will suffer.

On 8/31/2011 11:56 AM, Guido van Rossum wrote:

On Wed, Aug 31, 2011 at 11:51 AM, Glenn Linderman mailto:v%2Bpython@g.nevcal.com> wrote:

On 8/31/2011 10:12 AM, Guido van Rossum wrote:

...

On Wed, Aug 31, 2011 at 1:09 AM, Glenn Linderman mailto:v+python@g.nevcal.com wrote:

...

So from reading all this discussion, I think this point is rather a key one... and it has been made repeatedly in different ways: Arrays are not suitable for manipulating Unicode character sequences, and the str type is an array with a veneer of text manipulation operations, which do not, and cannot, by themselves, efficiently implement Unicode character sequences.

I think this is too strong. The str type is indeed an array, and you can build useful Unicode manipulation APIs on top of it. Just like bytes are not UTF-8, but can be used to represent UTF-8 and a fully-compliant UTF-8 codec can be implemented on top of it.

This statement is a logical conclusion of arguments presented in this thread.

1) Applications that wish to do grapheme access, wish to do it by grapheme array indexing, because that is the efficient way to do it.

I don't believe that should be taken as gospel. In Perl, they don't do array indexing on strings at all, and use regex matching instead. An API that uses some kind of cursor on a string might work fine in Python too (for grapheme matching).

The last benchmark I saw, regexp in Perl is faster than regexp in Python; that was some years back, before regexp in Perl supported quite as much Unicode as it does now; not sure if someone has done a recent performance benchmarks; Tom's survey indicates that the functionality presently differs, so it is not clear if performance benchmarks are presently appropriate to attempt to measure Unicode operations in regexp between the two languages. That said, regexp, or some sort of cursor on a string, might be a workable solution. Will it have adequate performance? Perhaps, at least for some applications. Will it be as conceptually simple as indexing an array of graphemes? No. Will it ever reach the efficiency of indexing an array of graphemes? No. Does that matter? Depends on the application.

2) As long as str is restricted to holding Unicode code units or code points, then it cannot support grapheme array indexing efficiently.

I have not declared that useful Unicode manipulations APIs cannot be built on top of str, only that efficiency will suffer.

But you have not proven it.

Do you disagree that indexing an array is more efficient than manipulating strings with regex or binary trees? I think not, because you are insistent that array indexing of str be preserved as O(1). I agree that I have not proven it; it largely depends on whether or not indexing by grapheme cluster is a useful operation in applications. Yet Stephen (I think) has commented that emacs performance goes down as soon as multi-byte characters are introduced into an edit buffer. So I think he has proven that efficiency can suffer, in some implementations/applications. Terry's O(k) implementation requires data beyond strings, and isn't O(1).

On Wed, Aug 31, 2011 at 5:58 PM, Neil Hodgson wrote:

[...] some text drawing engines draw decomposed characters ("o" followed by " ̈" -> "ö") differently compared to their composite equivalents ("ö") and this may be perceived as better or worse. I'd like to offer an option to replace some decomposed characters with their composite equivalent before drawing but since other characters may look worse, I don't want to do a full normalization.

Isn't this an issue properly solved by various normal forms? -- --Guido van Rossum (python.org/~guido)

Guido van Rossum:

On Wed, Aug 31, 2011 at 5:58 PM, Neil Hodgson wrote:

...

[...] some text drawing engines draw decomposed characters ("o" followed by " ̈" -> "ö") differently compared to their composite equivalents ("ö") and this may be perceived as better or worse. I'd like to offer an option to replace some decomposed characters with their composite equivalent before drawing but since other characters may look worse, I don't want to do a full normalization.

Isn't this an issue properly solved by various normal forms?

No, since normalization of all cases may actually lead to worse visuals in some situations. A potential reason for drawing decomposed characters differently is that more room may be allocated for the generic condition where a character may be combined with a wide variety of accents compared with combining it with a specific accent. Here is an example on Windows drawing composite and decomposed forms to show the types of difference often encountered. http://scintilla.org/Composite.png Now, this particular example displays both forms quite reasonably so would not justify special processing but I have seen on other platforms and earlier versions of Windows where the umlaut in the decomposed form is displaced to the right even to the extent of disappearing under the next character. In the example, the decomposed 'o' is shorter and lighter and the umlauts are round instead of square. Neil

Ok, I thought there was also a form normalized (denormalized?) to decomposed form. But I'll take your word.

If I understood the example correctly, he needs a mixed form, with some characters decomposed and some composed (depending on which one looks better in the given font). I agree that this sound more like a font problem, but it's a wide spread font problem and it may be necessary to address it in an application. But this is only one example of why an application-specific concept of graphemes different from the Unicode-defined normalized forms can be useful. I think the very concept of a grapheme is context, language, and culture specific. For example, in Chinese Pinyin it would be very natural to write tone marks with composing diacritics (i.e. in decomposed form). But then you have the vowel "ü" and it would be strange to decompose it into an "u" and combining diaeresis. So conceptually the most sensible representation of "lǜ" would be neither the composed not the decomposed normal form, and depending on its needs an application might want to represent it in the mixed form (composing the diaeresis with the "u", but leaving the grave accent separate). There must be many more examples where the conceptual context determines the right composition, like for "ñ", which is Spanish is certainly a grapheme, but in mathematics might be better represented as n-tilde. The bottom line is that, while an array of Unicode code points is certainly a generally useful data type (and PEP 393 is a great improvement in this regard), an array of graphemes carries many subtleties and may not be nearly as universal. Support in the spirit of unicodedata's normalization function etc. is certainly a good thing, but we shouldn't assume that everyone will want Python to do their graphemes for them. - Hagen

Glenn Linderman:

How many different iterators into the same text would be concurrently needed by an application?  And why? Seems like if it is dealing with text at the level of grapheme clusters, it needs that type of iterator.  Of course, if it does I/O it needs codec access, but that is by nature sequential from the starting point to the end point.

I would expect that there would mostly be a single iterator into a string but can imagine scenarios in which multiple iterators may be concurrently active and that these could be of different types. For example, say we wanted to search for each code point in a text that fails some test (such as being a member of a set of unwanted vowel diacritics) and then display that failure in context with its surrounding text of up to 30 graphemes either side. Neil

On 9/1/2011 2:15 AM, Stephen J. Turnbull wrote:

Glenn Linderman writes:

...

How many different iterators into the same text would be concurrently needed by an application? And why?

A WYSIWYG editor for structured text (TeX, HTML) might want two (at least), one for the "source" window and one for the "rendered" window. One might want to save the state of the iterators (if that's possible) and cache it as one moves the "window" forward to make short backward motion fast, giving you two (or four, etc) more.

Sure. But those are probably all the same type of iterators — probably (since they are WYSIWYG) dealing with multi-codepoint characters (Guido's recent definition of grapheme, which seems to subsume both grapheme clusters and composed characters). Hence all of them would be using/requiring the same sort of representation, index, analysis, or some combination of those.

...

Seems like if it is dealing with text at the level of grapheme clusters, it needs that type of iterator. Of course, if it does I/O it needs codec access, but that is by nature sequential from the starting point to the end point.

`save-region' ? `save-text-remove-markup' ?

Yes, save-region sounds like exactly what I was speaking of. save-text-remove-markup I would infer needs to process the text to remove the markup characters... since you used TeX and HTML as examples, markup is text, not binary (which would be a different problem). Since the TeX and HTML markup is mostly ASCII, markup removal (or more likely, text extraction) could be performed via either a grapheme iterator, or a codepoint iterator, or even a code unit iterator.

On 8/31/2011 10:20 AM, Guido van Rossum wrote:

On Wed, Aug 31, 2011 at 1:09 AM, Glenn Linderman wrote:

...

The str type itself can presently be used to process other character encodings: if they are fixed width< 32-bit elements those encodings might be considered Unicode encodings, but there is no requirement that they are, and some operations on str may operate with knowledge of some Unicode semantics, so there are caveats. Actually, the str type in Python 3 and the unicode type in Python 2 are constrained everywhere to either 16-bit or 21-bit "characters". (Except when writing C code, which can do any number of invalid things so is the equivalent of assuming 1 == 0.) In particular, on a wide build, there is no way to get a code point>= 2**21, and I don't want PEP 393 to change this. So at best we can use these types to repesent arrays of 21-bit unsigned ints. But I think it is more useful to think of them as always representing "some form of Unicode", whether that is UTF-16 (on narrow builds) or 21-bit code points or perhaps some vaguely similar superset -- but for those code units/code points that are representable *and* valid (either code points or code units) according to the (supported version of) the Unicode standard, the meaning of those code points/units matches that of the standard.

Note that this is different from the bytes type, where the meaning of a byte is entirely determined by what it means in the programmer's head.

Sorry, my Perl background is leaking through. I didn't double check that str constrains the values of each element to range 0x110000 but I see now by testing that it does. For some of my ideas, then, either a subtype of str would have to be able to relax that constraint, or str would not be the appropriate base type to use (but there are other base types that could be used, so this is not a serious issue for the ideas). I have no problem with thinking of str as representing "some form of Unicode". None of my proposals change that, although they may change other things, and may invent new forms of Unicode representations. You have stated that it is better to document what str actually does, rather than attempt to adhere slavishly to Unicode standard concepts. The Unicode Consortium may well define legal, conforming bytestreams for communicating processes, but languages and applications are free to use other representations internally. We can either artificially constrain ourselves to minor tweaks of the legal conforming bytestreams, or we can invent a representation (whether called str or something else) that is useful and efficient in practice.

On 9/1/2011 12:59 AM, Stephen J. Turnbull wrote:

Glenn Linderman writes:

...

We can either artificially constrain ourselves to minor tweaks of the legal conforming bytestreams,

It's not artificial. Having the internal representation be the same as a standard encoding is very useful for a large number of minor usages (urgently saving buffers in a text editor that knows its internal state is inconsistent, viewing strings in the debugger, PEP 393-style space optimization is simpler if text properties are out-of-band, etc).

saving buffers urgently when the internal state is inconsistent sounds like carefully preserving a bug. Windows 7 64-bit on one of my computers happily crashes several times a day when it detects inconsistent internal state... under the theory, I guess, that losing work is better than saving bad work. You sound the opposite. I'm actually very grateful that Firefox and emacs recover gracefully from Windows crashes, and I lose very little data from the crashes, but cannot recommend Windows 7 (this machine being my only experience with it) for stability. In any case, the operations you mention still require the data to be processed, if ever so slightly, and I'll admit that a more complex representation would require a bit more processing. Not clear that it would be huge or problematical for these cases. Except, I'm not sure how PEP 393 space optimization fits with the other operations. It may even be that an application-wide complex-grapheme cache would save significant space, although if it uses high-bits in a string representation to reference the cache, PEP 393 would jump immediately to something > 16 bits per grapheme... but likely would anyway, if complex-graphemes are in the data stream.

...

or we can invent a representation (whether called str or something else) that is useful and efficient in practice.

Bring on the practice, then. You say that a bit to identify lone surrogates might be useful or efficient. In what application? How much time or space does it save?

I didn't attribute any efficiency to flagging lone surrogates (BI-5). Since Windows uses a non-validated UCS-2 or UTF-16 character type, any Python program that obtains data from Windows APIs may be confronted with lone surrogates or inappropriate combining characters at any time. Round-tripping that data seems useful, even though the data itself may not be as useful as validated Unicode characters would be. Accidentally combining the characters due to slicing and dicing the data, and doing normalizations, or what not, would not likely be appropriate. However, returning modified forms of it to Windows as UCS-2 or UTF-16 data may still cause other applications to later accidentally combine the characters, if the modifications juxtaposed things to make them look reasonably, even if accidentally. If intentionally, of course, the bit could be turned off. This exact sort of problem with non-validated UTF-8 bytes was addressed already in Python, mostly for Linux, allowing round-tripping of the byte stream, even though it is not valid. BI-6 suggests a different scheme for that, without introducing lone surrogates (which might accidentally get combined with other lone surrogates).

You say that a bit to cache a property might be useful or efficient. In what application? Which properties? Are those properties a set fixed by the language, or would some bits be available for application-specific property caching? How much time or space does that save?

The brainstorming ideas I presented were just that... ideas. And they were independent. And the use of many high-order bits for properties was one of the independent ones. When I wrote that one, I was assuming a UTF-32 representation (which wastes 11 bits of each 32). One thing I did have in mind, with the high-order bits, for that representation, was to flag the start or end or middle of the codes that are included in a grapheme. That would be redundant with some of the Unicode codepoint property databases, if I understand them properly... whether it would make iterators enough more efficient to be worth the complexity would have to be benchmarked. After writing all those ideas down, I actually preferred some of the others, that achieved O(1) real grapheme indexing, rather than caching character properties.

What are the costs to applications that don't want the cache? How is the bit-cache affected by PEP 393?

If it is a separate type from str, then it costs nothing except the extra code space to implement the cache for those applications that do want it... most of which wouldn't be loaded for applications that don't, if done as a module or C extension.

I know of no answers (none!) to those questions that favor introduction of a bit-cache representation now. And those bits aren't going anywhere; it will always be possible to use a "wide" build and change the representation later, if the optimization is valuable enough. Now, I'm aware that my experience is limited to the implementations of one general-purpose language (Emacs Lisp) of retricted applicability. But its primary use *is* in text processing, so I'm moderately expert.

*Moderately*. Always interested in learning more, though. If you know of relevant use cases, I'm listening! Even if Guido doesn't find them convincing for Python, we might find them interesting at XEmacs.

OK... ignore the bit-cache idea (BI-1), and reread the others without having your mind clogged with that one, and see if any of them make sense to you then. But you may be too biased by the "minor" needs of keeping the internal representation similar to the stream representation to see any value in them. I rather like BI-2, since it allow O(1) indexing of graphemes.

On Tue, Aug 30, 2011 at 11:03 PM, Stephen J. Turnbull wrote: [me]

 > That sounds like a contradiction -- it wouldn't be a UTF-16 array if  > you couldn't tell that it was using UTF-16.

Well, that's why I wrote "intended to be suggestive".  The Unicode Standard does not specify at all what the internal representation of characters may be, it only specifies what their external behavior must be when two processes communicate.  (For "process" as used in the standard, think "Python modules" here, since we are concerned with the problems of folks who develop in Python.)  When observing the behavior of a Unicode process, there are no UTF-16 arrays or UTF-8 arrays or even UTF-32 arrays; only arrays of characters.

Hm, that's not how I would read "process". IMO that is an intentionally vague term, and we are free to decide how to interpret it. I don't think it will work very well to define a process as a Python module; what about Python modules that agree about passing along array of code units (or streams of UTF-8, for that matter)? This is why I find the issue of Python, the language (and stdlib), as a whole "conforming to the Unicode standard" such a troublesome concept -- I think it is something that an application may claim, but the language should make much more modest claims, such as "the regular expression syntax supports features X, Y and Z from the Unicode recommendation XXX, or "the UTF-8 codec will never emit a sequence of bytes that is invalid according Unicode specification YYY". (As long as the Unicode references are also versioned or dated.) I'm fine with saying "it is hard to write Unicode-conforming application code for reason ZZZ" and proposing a fix (e.g. PEP 393 fixes a specific complaint about code units being inferior to code points for most types of processing). I'm not fine with saying "the string datatype should conform to the Unicode standard".

Thus, according to the rules of handling a UTF-16 stream, it is an error to observe a lone surrogate or a surrogate pair that isn't a high-low pair (Unicode 6.0, Ch. 3 "Conformance", requirements C1 and C8-C10).  That's what I mean by "can't tell it's UTF-16".

But if you can observe (valid) surrogate pairs it is still UTF-16.

And I understand those requirements to mean that operations on UTF-16 streams should produce UTF-16 streams, or raise an error.  Without that closure property for basic operations on str, I think it's a bad idea to say that the representation of text in a str in a pre-PEP-393 "narrow" build is UTF-16.  For many users and app developers, it creates expectations that are not fulfilled.

Ok, I dig this, to some extent. However saying it is UCS-2 is equally bad. I guess this is why Java and .NET just say their string types contain arrays of "16-bit characters", with essentially no semantics attached to the word "character" besides "16-bit unsigned integer". At the same time I think it would be useful if certain string operations like .lower() worked in such a way that *if* the input were valid UTF-16, *then* the output would also be, while *if* the input contained an invalid surrogate, the result would simply be something that is no worse (in particular, those are all mapped to themselves). We could even go further and have .lower() and friends look at graphemes (multi-code-point characters) if the Unicode std has a useful definition of e.g. lowercasing graphemes that differed from lowercasing code points. An analogy is actually found in .lower() on 8-bit strings in Python 2: it assumes the string contains ASCII, and non-ASCII characters are mapped to themselves. If your string contains Latin-1 or EBCDIC or UTF-8 it will not do the right thing. But that doesn't mean strings cannot contain those encodings, it just means that the .lower() method is not useful if they do. (Why ASCII? Because that is the system encoding in Python 2.)

It's true that common usage is that an array of code units that usually conforms to UTF-16 may be called "UTF-16" without the closure properties.  I just disagree with that usage, because there are two camps that interpret "UTF-16" differently.  One side says, "we have an array representation in UTF-16 that can handle all Unicode code points efficiently, and if you think you need more, think again", while the other says "it's too painful to have to check every result for valid UTF-16, and we need a UTF-16 type that supports the usual array operations on *characters* via the usual operators; if you think otherwise, think again."

I think we should just document how it behaves and not get hung up on what it is called. Mentioning UTF-16 is still useful because it indicates that some operations may act properly on surrogate pairs. (Also because of course character properties for BMP characters are respected, etc.)

Note that despite the (presumed) resolution of the UTF-16 issue for CPython by PEP 393, at some point a very similar discussion will take place over "characters" anyway, because users and app developers are going to want a type that handles composition sequences and/or grapheme clusters for them, as well as comparison that respects canonical equivalence, even if it is inefficient compared to str. That's why I insisted on use of "array of code points" to describe the PEP 393 str type, rather than "array of characters".

Let's call those things graphemes (Tom C's term, I quite like leaving "character" ambiguous) -- they are sequences of multiple code points that represent a single "visual squiggle" (the kind of thing that you'd want to be swappable in vim with "xp" :-). I agree that APIs are needed to manipulate (match, generate, validate, mutilate, etc.) things at the grapheme level. I don't agree that this means a separate data type is required. There are ever-larger units of information encoded in text strings, with ever farther-reaching (and more vague) requirements on valid sequences. Do you want to have a data type that can represent (only valid) words in a language? Sentences? Novels? I think that at this point in time the best we can do is claim that Python (the language standard) uses either 16-bit code units or 21-bit code points in its string datatype, and that, thanks to PEP 393, CPython 3.3 and further will always use 21-bit code points (but Jython and IronPython may forever use their platform's native 16-bit code unit representing string type). And then we add APIs that can be used everywhere to look for code points (even if the string contains code points), graphemes, or larger constructs. I'd like those APIs to be designed using a garbage-in-garbage-out principle, where if the input conforms to some Unicode requirement, the output does too, but if the input doesn't, the output does what makes most sense. Validation is then limited to codecs, and optional calls. If you index or slice a string, or create a string from chr() of a surrogate or from some other value that the Unicode standard considers an illegal code point, you better know what you are doing. I want chr(i) to be valid for all values of i in range(2**21), so it can be used to create a lone surrogate, or (on systems with 16-bit "characters") a surrogate pair. And also ord(chr(i)) == i for all i in range(2**21). I'm not sure about ord() on a 2-character string containing a surrogate pair on systems where strings contain 21-bit code points; I think it should be an error there, just as ord() on other strings of length != 1. But on systems with 16-bit "characters", ord() of strings of length 2 containing a valid surrogate pair should work. -- --Guido van Rossum (python.org/~guido)

On 8/31/2011 1:10 PM, Guido van Rossum wrote:

This is why I find the issue of Python, the language (and stdlib), as a whole "conforming to the Unicode standard" such a troublesome concept -- I think it is something that an application may claim, but the language should make much more modest claims, such as "the regular expression syntax supports features X, Y and Z from the Unicode recommendation XXX, or "the UTF-8 codec will never emit a sequence of bytes that is invalid according Unicode specification YYY". (As long as the Unicode references are also versioned or dated.)

This will be a great improvement. It was both embarrassing and frustrating to have to respond to Tom C.'s (and other's) issue with "Our unicode type is too vaguely documented to tell whether you are reporting a bug or making a feature request.

But if you can observe (valid) surrogate pairs it is still UTF-16. ... Ok, I dig this, to some extent. However saying it is UCS-2 is equally bad.

As I said on the tracker, our narrow builds are in-between (while moving closer to UTF-16), and both terms are deceptive, at least to some.

At the same time I think it would be useful if certain string operations like .lower() worked in such a way that *if* the input were valid UTF-16, *then* the output would also be, while *if* the input contained an invalid surrogate, the result would simply be something that is no worse (in particular, those are all mapped to themselves). We could even go further and have .lower() and friends look at graphemes (multi-code-point characters) if the Unicode std has a useful definition of e.g. lowercasing graphemes that differed from lowercasing code points.

An analogy is actually found in .lower() on 8-bit strings in Python 2: it assumes the string contains ASCII, and non-ASCII characters are mapped to themselves. If your string contains Latin-1 or EBCDIC or UTF-8 it will not do the right thing. But that doesn't mean strings cannot contain those encodings, it just means that the .lower() method is not useful if they do. (Why ASCII? Because that is the system encoding in Python 2.)

Good analogy.

Let's call those things graphemes (Tom C's term, I quite like leaving "character" ambiguous) -- they are sequences of multiple code points that represent a single "visual squiggle" (the kind of thing that you'd want to be swappable in vim with "xp" :-). I agree that APIs are needed to manipulate (match, generate, validate, mutilate, etc.) things at the grapheme level. I don't agree that this means a separate data type is required.

I presume by 'separate data type' you mean a base level builtin class like int or str and that you would allow for wrapper classes built on top of str, as such are not really 'separate'. For grapheme leval and higher, we should certainly start with wrappers and probably with alternate versions based on different strategies.

There are ever-larger units of information encoded in text strings, with ever farther-reaching (and more vague) requirements on valid sequences. Do you want to have a data type that can represent (only valid) words in a language? Sentences? Novels? ... I think that at this point in time the best we can do is claim that Python (the language standard) uses either 16-bit code units or 21-bit code points in its string datatype, and that, thanks to PEP 393, CPython 3.3 and further will always use 21-bit code points (but Jython and IronPython may forever use their platform's native 16-bit code unit representing string type). And then we add APIs that can be used everywhere to look for code points (even if the string contains code points), graphemes, or larger constructs. I'd like those APIs to be designed using a garbage-in-garbage-out principle, where if the input conforms to some Unicode requirement, the output does too, but if the input doesn't, the output does what makes most sense. Validation is then limited to codecs, and optional calls.

If you index or slice a string, or create a string from chr() of a surrogate or from some other value that the Unicode standard considers an illegal code point, you better know what you are doing. I want chr(i) to be valid for all values of i in range(2**21),

Actually, it is range(0X110000) == range(1114112) so that UTF-8 uses at most 4 bytes per codepoint. 21 bits is 20.1 bits rounded up.

so it can be used to create a lone surrogate, or (on systems with 16-bit "characters") a surrogate pair. And also ord(chr(i)) == i for all i in range(2**21).

for i in range(0x110000): # 1114112 if ord(chr(i)) != i: print(i) # prints nothing (on Windows)

I'm not sure about ord() on a 2-character string containing a surrogate pair on systems where strings contain 21-bit code points; I think it should be an error there, just as ord() on other strings of length != 1. But on systems with 16-bit "characters", ord() of strings of length 2 containing a valid surrogate pair should work.

And now does, thanks to whoever fixed this (withing the last year, I think). -- Terry Jan Reedy

Where I cut your words, we are in 100% agreement. (FWIW :-) Guido van Rossum writes:

On Tue, Aug 30, 2011 at 11:03 PM, Stephen J. Turnbull wrote:

...

Well, that's why I wrote "intended to be suggestive".  The Unicode Standard does not specify at all what the internal representation of characters may be, it only specifies what their external behavior must be when two processes communicate.  (For "process" as used in the standard, think "Python modules" here, since we are concerned with the problems of folks who develop in Python.)  When observing the behavior of a Unicode process, there are no UTF-16 arrays or UTF-8 arrays or even UTF-32 arrays; only arrays of characters.

Hm, that's not how I would read "process". IMO that is an intentionally vague term,

I agree. I'm sorry that I didn't make myself clear. The reason I read "process" as "module" is that some modules of Python, and therefore Python as a whole, cannot conform to the Unicode standard. Eg, anything that inputs or outputs bytes. Therefore only "modules" and "types" can be asked to conform. (I don't think it makes sense to ask anything lower level to conform. See below where I comment on your .lower() example.) What I am advocating (for the long term) is provision of *one* module (or type) such that if the text processing done by the application is done entirely in terms of this module (type), it will conform (to some specified degree, chosen to balance user wants with implementation and support costs). It may be desireable to provide others for sufficiently important particular use cases, but at present I see a clear need for *one*. Unicode conformance is going to be a common requirement for apps used by global enterprises. I oppose trying to make str into that type. We need str, just as it is, for many reasons.

and we are free to decide how to interpret it. I don't think it will work very well to define a process as a Python module; what about Python modules that agree about passing along array of code units (or streams of UTF-8, for that matter)?

Certainly a group of cooperating modules could form a conforming process, just as you describe it for one example. The "one module" mentioned above need not implement everything internally, but it would take responsiblity for providing guarantees (eg, unit tests) of whatever conformance claims it makes.

...

Thus, according to the rules of handling a UTF-16 stream, it is an error to observe a lone surrogate or a surrogate pair that isn't a high-low pair (Unicode 6.0, Ch. 3 "Conformance", requirements C1 and C8-C10).  That's what I mean by "can't tell it's UTF-16".

But if you can observe (valid) surrogate pairs it is still UTF-16.

In the concrete implementation I have in mind, surrogate pairs are represented by a str containing 2 code units. But in that case s[i][1] is an error, and s[i][0] == s[i]. print(s[i][0]) and print(s[i]) will print the same character to the screen. If you decode it to bytes, well, it's not a str any more so what have you proved? Ie, what you will see is *code points* not in the BMP. You don't have to agree that such "surrogate containment" behavior is so valuable as I think it is, but that's what I have in mind as one requirement for a "conforming implementation of UTF-16".

At the same time I think it would be useful if certain string operations like .lower() worked in such a way that *if* the input were valid UTF-16, *then* the output would also be, while *if* the input contained an invalid surrogate, the result would simply be something that is no worse (in particular, those are all mapped to themselves).

I don't think that it's a good idea to go for conformance at the method level. It would be a feature for apps that don't claim full conformance because they nevertheless give good results in more cases. The downside will be Python apps using str that will pass conformance tests written for, say Western Europe, but end users in Kuwait and Kuala Lumpur will report bugs.

An analogy is actually found in .lower() on 8-bit strings in Python 2: it assumes the string contains ASCII, and non-ASCII characters are mapped to themselves. If your string contains Latin-1 or EBCDIC or UTF-8 it will not do the right thing. But that doesn't mean strings cannot contain those encodings, it just means that the .lower() method is not useful if they do. (Why ASCII? Because that is the system encoding in Python 2.)

Sure. I think that approach is fine for str, too, except that I would hope it looks up BMP base characters in the case-mapping database. The fact is that with very few exceptions non-BMP characters are going to be symbols (mathematical operators and emoticons, for example). This is good enough, except when it's not---but when it's not, only 100% conformance is really a reasonable target. IMO, of course.

I think we should just document how it behaves and not get hung up on what it is called. Mentioning UTF-16

If you also say, "this type can represent all characters in Unicode, as well as certain non-characters", why mention UTF-16 at all?

Let's call those things graphemes (Tom C's term, I quite like leaving "character" ambiguous)

OK, but those definitions need to be made clear, as "grapheme cluster" and "combined character" are defined in the Unicode standard, and in fact mean slightly different things from each other.

-- they are sequences of multiple code points that represent a single "visual squiggle" (the kind of thing that you'd want to be swappable in vim with "xp" :-). I agree that APIs are needed to manipulate (match, generate, validate, mutilate, etc.) things at the grapheme level. I don't agree that this means a separate data type is required.

Clear enough.

There are ever-larger units of information encoded in text strings, with ever farther-reaching (and more vague) requirements on valid sequences. Do you want to have a data type that can represent (only valid) words in a language? Sentences? Novels?

No, and I can tell you why! The difference between characters and words is much more important than that between code point and grapheme cluster for most users and the developers who serve them. Even small children recognize typographical ligatures as being composite objects, while at least this Spanish-as-a-second-language learner was taught that `ñ' is an atomic character represented by a discontiguous glyph, like `i', and it is no more related to `n' than `m' is. Users really believe that characters are atomic. Even in the cases of Han characters and Hangul, users think of the characters as being "atomic," but in the sense of Bohr rather than that of Democritus. I think the situation for text processing is analogous to chemistry where the atom, with a few fairly gross properties (the outer electron orbitals) is the fundamental unit, not the elementary particles like electrons and protons and structures like inner orbitals. Sure, there are higher order structures like molecules, phases, and crystals, but it is elements that have the most regular and simply described behavior for the chemist, and it does not become any simpler for the chemist if you decompose the atom. The composed character or grapheme cluster is the analogue of the atom for most processing at the level of "text". The only real exceptions I can imagine are in the domain of linguistics.

I think that at this point in time the best we can do is claim that Python (the language standard) uses either 16-bit code units or 21-bit code points in its string datatype, and that, thanks to PEP 393, CPython 3.3 and further will always use 21-bit code points (but Jython and IronPython may forever use their platform's native 16-bit code unit representing string type). And then we add APIs that can be used everywhere to look for code points (even if the string contains code points), graphemes, or larger constructs. I'd like those APIs to be designed using a garbage-in-garbage-out principle, where if the input conforms to some Unicode requirement, the output does too, but if the input doesn't, the output does what makes most sense. Validation is then limited to codecs, and optional calls.

Clear enough. I disagree that that will be enough for constructing large-scale Unicode-conformant applications. Somebody is going to have to produce batteries for those applications, and I think they should be included in Python. I agree that it's proper that I and those who think the same way take responsibility for writing and implementing a PEP.

If you index or slice a string, or create a string from chr() of a surrogate or from some other value that the Unicode standard considers an illegal code point, you better know what you are doing.

I think that's like asking a toddler to know that the stove is hot. The consequences for the toddler of her ignorance are much greater, but the informational requirement is equally stringent. Of course application writers are adults who could be asked to learn, but economically I think it make a lot more sense to include those batteries. IMHO YMMV, obviously.

I want chr(i) to be valid for all values of i in range(2**21),

I quite agree (ie, for str). Thus I perceive a need for another type.

Le jeudi 01 septembre 2011 à 08:45 -0700, Guido van Rossum a écrit :

This is definitely thought of as a separate mark added to the e; ë is not a new letter. I have a feeling it's the same way for the French and Germans, but I really don't know. (Antoine? Georg?)

Indeed, they are not separate "letters" (they are considered the same in lexicographic order, and the French alphabet has 26 letters). But I'm not sure how it's relevant, because you can't remove an accent without most likely making a spelling error, or at least changing the meaning. Accents are very much part of the language (while ligatures like "ff" are not, they are a rendering detail). So I would consider "é", "ê", "ù", etc. atomic characters for the purpose of processing French text. And I don't see how a decomposed form could help an application. Regards Antoine.

The example given was someone who didn't agree with how a particular font rendered those accented characters. I agree that's obscure though.

I recall long ago that when the french wrote words in all caps they would drop the accents, e.g. ECOLE. I even recall (through the mists of time) observing this in Paris on public signs. Is this still the convention? Maybe it only was a compromise in the time of Morse code?

I think it is tolerated, partly because typing support (on computers and typewriters) has been weak. On a French keyboard, you have an "é" key, but shifting it gives you "2", not "É". The latter can be obtained using the Caps Lock key under Linux, but not under Windows. (so you could also write Éric's name "Eric", for example) That said, most typographies nowadays seem careful to keep the accents on uppercase letters (e.g. on book covers; AFAIR, road signs also keep the accents, but I'm no driver). Regards Antoine.

Guido van Rossum, 01.09.2011 18:31:

On Thu, Sep 1, 2011 at 9:03 AM, Antoine Pitrou wrote:

...

Le jeudi 01 septembre 2011 à 08:45 -0700, Guido van Rossum a écrit :

...

This is definitely thought of as a separate mark added to the e; ë is not a new letter. I have a feeling it's the same way for the French and Germans, but I really don't know. (Antoine? Georg?)

Indeed, they are not separate "letters" (they are considered the same in lexicographic order, and the French alphabet has 26 letters).

So does the German alphabet, even though that does not include "ß", which basically descended from a ligature of the old German way of writing "sz", where "s" looked similar to an "f" and "z" had a low hanging tail. IIRC, German Umlaut letters are lexicographically sorted according to their emergency replacement spelling ("ä" -> "ae"), which is also sometimes used in all upper case words ("Glück" -> "GLUECK"). I guess that's because Umlaut dots are harder to see on top of upper case letters. So, Latin-1 byte value sorting always yields totally wrong results. That aside, Umlaut letters are commonly considered separate letters, different from the undotted letters and also different from the replacement spellings. I, for one, always found the replacements rather weird and never got used to using them in upper case words. In any case, it's wrong to always use them, and it makes text harder to read.

...

But I'm not sure how it's relevant, because you can't remove an accent without most likely making a spelling error, or at least changing the meaning. Accents are very much part of the language (while ligatures like "ff" are not, they are a rendering detail). So I would consider "é", "ê", "ù", etc. atomic characters for the purpose of processing French text. And I don't see how a decomposed form could help an application.

I recall long ago that when the french wrote words in all caps they would drop the accents, e.g. ECOLE. I even recall (through the mists of time) observing this in Paris on public signs. Is this still the convention?

Yes, and it's a huge problem when trying to pronounce last names. In French, you'd commonly write LASTNAME, Firstname and if LASTNAME happens to have accented letters, you'd miss them when reading that. I know a couple of French people who severely suffer from this, because the pronunciation of their name gets a totally different meaning without accents. Stefan

On Fri, 02 Sep 2011 12:30:12 +1200 Greg Ewing wrote:

Guido van Rossum wrote:

...

I recall long ago that when the french wrote words in all caps they would drop the accents, e.g. ECOLE. I even recall (through the mists of time) observing this in Paris on public signs. Is this still the convention?

This page features a number of French street signs in all-caps, and some of them have accents:

http://www.happymall.com/france/paris_street_signs.htm

I don't think some American souvenir shop is a good reference, though :) (for example, there's no Paris street named "château de Versailles") Regards Antoine.

Antoine Pitrou wrote:

Le jeudi 01 septembre 2011 à 08:45 -0700, Guido van Rossum a écrit :

...

This is definitely thought of as a separate mark added to the e; ë is not a new letter. I have a feeling it's the same way for the French and Germans, but I really don't know. (Antoine? Georg?)

Indeed, they are not separate "letters" (they are considered the same in lexicographic order, and the French alphabet has 26 letters).

On the other hand, the same doesn't necessarily apply to other languages. (At least according to Wikipedia.) http://en.wikipedia.org/wiki/Diacritic#Languages_with_letters_containing_dia... -- Steven

On 9/1/2011 11:45 AM, Guido van Rossum wrote:

typewriter). Dutch does have one native use of the umlaut (though it has a different name, I forget which, maybe trema :-),

You remember correctly. According to https://secure.wikimedia.org/wikipedia/en/wiki/Trema_%28diacritic%29 'trema' (Greek 'hole') is the generic name of the double-dot vowel diacritic. It was originally used for 'diaerhesis' (Greek, 'taking apart') when it shows "that a vowel letter is not part of a digraph or diphthong". (Note that 'ae' in diaerhesis *is* a digraph ;-). Germans later used it to indicate umlaut, 'changed sound'.

when there are two consecutive vowels that would normally be read as a special sound (diphthong?). E.g. in "koe" (cow) the oe is two letters (not a single letter formed of two distict shapes!) that mean a special sound (roughly KOO). But in a word like "coëxistentie" (coexistence) the o and e do not form the oe-sound, and to emphasize this to Dutch readers (who believe their spelling is very logical :-), the official spelling puts the umlaut on the e. This is definitely thought of as a separate mark added to the e; ë is not a new letter.

So the above is trema-diaerhesis. "Dutch, French, and Spanish make regular use of the diaeresis." English uses such as 'coöperate' have become rare or archaic, perhaps because we cannot type them. Too bad, since people sometimes use '-' to serve the same purpose. -- Terry Jan Reedy

Guido van Rossum writes:

On Thu, Sep 1, 2011 at 12:13 AM, Stephen J. Turnbull wrote:

...

while at least this Spanish-as-a-second-language learner was taught that `ñ' is an atomic character represented by a discontiguous glyph, like `i', and it is no more related to `n' than `m' is.  Users really believe that characters are atomic.  Even in the cases of Han characters and Hangul, users think of the characters as being "atomic," but in the sense of Bohr rather than that of Democritus.

Ah, I think this may very well be culture-dependent.

I'm not an expert, but I'm fairly sure it is. Specifically, I heard from a TeX-ie friend that the same accented letter is typeset (and collated) differently in different European languages because in some of them the accent is considered part of the letter (making a different character), while in others accents modify a single underlying character. The ones that consider the letter and accent to constitute a single character also prefer to leave less space, he said.

But in a word like "coëxistentie" (coexistence) the o and e do not form the oe-sound, and to emphasize this to Dutch readers (who believe their spelling is very logical :-), the official spelling puts the umlaut on the e.

American English has the same usage, but it's optional (in particular, you'll see naive, naif, and words like coordinate typeset that way occasionally, for the same reason I suppose). As Hagen Fürstenau points out, with multiple combining characters, there are even more complex possibilities than "the accent is part of the character" and "it's really not", and they may be application- dependent.

Finally, my guess is that the Spanish emphasis on ñ as a separate letter has to do with teaching how it has a separate position in the localized collation sequence, doesn't it?

You'd have to ask Mr. Gonzalez. I suspect he may have taught that way less because of his Castellano upbringing, and more because of the infamous lack of sympathy of American high school students for the fine points of usage in foreign languages.

I'm also curious if ñ occurs as a separate character on Spanish keyboards.

If I'm reading /usr/share/X11/xkb/symbols/es correctly, it does in X.org: the key that for English users would map to ASCII tilde.

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 09/01/2011 02:54 PM, Antoine Pitrou wrote:

If you look at Wikipedia, it says: “El alfabeto español consta de 27 letras”. The Ñ is separate from the N (and so is it in my French-Spanish dictionnary). The accented letters, however, are not considered separately. http://es.wikipedia.org/wiki/Alfabeto_espa%C3%B1ol

(I can't tell you how annoying to type "ñ" is when the tilde is accessed using AltGr + 2 and you have to combine that with the Compose key and N to obtain the full character. I'm sure Spanish keyboards have a better way than that :-))

FWIW, I was taught that Spanish had 30 letters in the alfabeto: the 'ñ', plus 'ch', 'll', and 'rr' were all considered distinct characters. Kids-these-days'ly, Tres. - -- =================================================================== Tres Seaver +1 540-429-0999 tseaver@palladion.com Palladion Software "Excellence by Design" http://palladion.com -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.10 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAk5f2UQACgkQ+gerLs4ltQ4URACePSZzpoPAg2IIYZewsjbuplkK 0MgAoM7VfdQHzjBiU6Vr/MYPJ9U2qC3M =pvKn -----END PGP SIGNATURE-----

On Thu, 01 Sep 2011 12:38:07 -0700 Ethan Furman wrote:

...

FWIW, I was taught that Spanish had 30 letters in the alfabeto: the 'ñ', plus 'ch', 'll', and 'rr' were all considered distinct characters.

Kids-these-days'ly,

Not sure what's going on, but according to the article Antoine linked to those aren't letters anymore... so much for the cultural awareness portion of UNESCO.

That Wikipedia article also says: “Los dígrafos Ch y Ll tienen valores fonéticos específicos, y durante los siglos XIX y XX se ordenaron separadamente de C y L, aunque la práctica se abandonó en 1994 para homogeneizar el sistema con otras lenguas.” -> roughly: “the "Ch" and "Ll" digraphs have specific phonetic values, and during the 19th and 20th centuries they were ordered separately from C and L, but this practice was abandoned in 1994 in order to make the system consistent with other languages.” And about "rr": “El dígrafo rr (llamado erre, /'ere/, y pronunciado /r/) nunca se consideró por separado, probablemente por no aparecer nunca en posición inicial.” -> “the "rr" digraph was never considered separate, probably because it never appears at the very beginning of a word.” Regards Antoine.

On 9/1/2011 11:59 PM, Stephen J. Turnbull wrote:

I believe that the deprecation of the digraphs as separate letters occurred as the telephone became widely used in Spain, and the telephone company demanded an official proclamation from whatever Ministry is responsible for culture that it was OK to treat the digraphs as two letters (specifically, to collate them that way), so that they could use the programs that came with the OS.

The main 'standards body' for Spanish is the Real Academia Española in Madrid, which works with the 21 other members of the Asociación de Academias de la Lengua Española. wikimedia.org/wikipedia/en/wiki/Real_Academia_Española .wikimedia.org/wikipedia/en/wiki/Association_of_Spanish_Language_Academies While it has apparently been criticized as 'conservative' (which is well ought to be), it has been rather progressive in promoting changes such as 'ph' to 'f' (fisica, fone) and dropping silent 'p' in leading 'psi' (sicologia) and silent 's' in leading 'sci' (ciencia). -- Terry Jan Reedy

Greg Ewing writes:

I find it curious that pronunciation always seems to take precedence over spelling in campaigns like this. Nowadays, especially with the internet increasingly taking over from personal interaction, we probably see words written a lot more often than we hear them spoken. Why shouldn't we change the pronunciation to match the spelling rather than the other way around?

Because 90% of all people move their lips when reading. :-) More seriously, because almost nobody learns to read before learning to understand spoken language. Aural language is more primitive than written language.

Le 02/09/2011 05:59, Stephen J. Turnbull a écrit :

I believe that the deprecation of the digraphs as separate letters occurred as the telephone became widely used in Spain, and the telephone company demanded an official proclamation from whatever Ministry is responsible for culture that it was OK to treat the digraphs as two letters (specifically, to collate them that way), so that they could use the programs that came with the OS.

So this stuff is not merely variant by culture, but also by economics and politics. :-/

That is a truth for language matters and linguistics, as well as in other domains and sciences. Cheers

Greg Ewing, 02.09.2011 02:36:

Guido van Rossum wrote:

...

But in a word like "coëxistentie" (coexistence) the o and e do not form the oe-sound, and to emphasize this to Dutch readers (who believe their spelling is very logical :-), the official spelling puts the umlaut on the e.

Sometimes this is done in English too -- occasionally you see words like "cooperation" spelled with a diaresis over the second "o". But these days it's more common to use a hyphen, or not bother at all. Everyone knows how it's pronounced.

Right. There are so many words in the English language that you can't pronounce without knowing them, that the few words that fall into the above category really don't matter. Stefan

Paul Moore wrote:

IronPython and Jython can retain UTF-16 as their native form if that makes interop cleaner, but in doing so they need to ensure that basic operations like indexing and len work in terms of code points, not code units, if they are to conform. ... They lose the O(1) guarantee, but that's easily defensible as a tradeoff to conform to underlying runtime semantics.

I would only agree as long as it wasn't too much worse than O(1). O(log n) might be all right, but O(n) would be unacceptable, I think. -- Greg

On 8/26/2011 8:23 PM, Antoine Pitrou wrote:

...

I would only agree as long as it wasn't too much worse than O(1). O(log n) might be all right, but O(n) would be unacceptable, I think.

It also depends a lot on *actual* measured performance

Amen. Some regard O(n*n) sorts to be, by definition, 'worse' than O(n*logn). I even read that in an otherwise good book by a university professor. Fortunately for Python users, Tim Peters ignored that 'wisdom', coded the best O(n*n) sort he could, and then *measured* to find out what was better for what types and lengths of arrays. So not we have a list.sort that sometimes beats the pure O(nlog) quicksort of C libraries. -- Terry Jan Reedy

Am 27.08.2011 09:40, schrieb Steven D'Aprano:

Terry Reedy wrote:

...

On 8/26/2011 8:23 PM, Antoine Pitrou wrote:

...

...

I would only agree as long as it wasn't too much worse than O(1). O(log n) might be all right, but O(n) would be unacceptable, I think.

It also depends a lot on *actual* measured performance

Amen. Some regard O(n*n) sorts to be, by definition, 'worse' than O(n*logn). I even read that in an otherwise good book by a university professor. Fortunately for Python users, Tim Peters ignored that 'wisdom', coded the best O(n*n) sort he could, and then *measured* to find out what was better for what types and lengths of arrays. So not we have a list.sort that sometimes beats the pure O(nlog) quicksort of C libraries.

A nice story, but Quicksort's worst case is O(n*n) too.

In addition, timsort is O(n log n), which also makes it a real good O(n*n) sort :-) Regards, Martin

On Wed, Aug 24, 2011 at 1:22 AM, Stephen J. Turnbull wrote:

Well, no, it gives the right answer according to the design.  unicode objects do not contain character strings.  By design, they contain code point strings.  Guido has made that absolutely clear on a number of occasions.

Actually, the situation is that in narrow builds, they contain code units (which may have surrogates); in wide builds they contain code points. I think this is the crux of Tom Christian's complaints about narrow builds. Here's proof that narrow builds contain code units, not code points (i.e. use UTF-16, not UCS-2): $ ./python Python 2.7.2+ (2.7:498b03a55297, Aug 25 2011, 15:14:01) [GCC 4.4.3] on linux2 Type "help", "copyright", "credits" or "license" for more information.

...

...

import sys sys.maxunicode 65535 a = u'\U00012345' a u'\U00012345' len(a) 2

It's pretty clear that the interpreter is surrogate-aware, which to me indicates the use of UTF-16. Now in the PEP 393 branch: ./python Python 3.3.0a0 (pep-393:c60556059719, Aug 25 2011, 15:31:05) [GCC 4.4.3] on linux2 Type "help", "copyright", "credits" or "license" for more information.

...

...

import sys sys.maxunicode 1114111 a = '\U00012345' a '𒍅' len(a) 1

And some proof that this branch does not care about surrogates:

...

...

a = '\ud808' b = '\udf45' a '\ud808' b '\udf45' a + b '\ud808\udf45' len(a+b) 2

However: a = '\ud808\udf45'

...

...

a '𒍅' len(a) 1

Which to me merely shows it is smart when parsing string literals. (I expect that regular 3.3 narrow builds behave similar to the 2.7 narrow build, and 3.3 wide builds behave similar to the pep-393 build; I didn't have those lying around.) -- --Guido van Rossum (python.org/~guido)

On 8/24/2011 1:45 PM, Victor Stinner wrote:

Le 24/08/2011 02:46, Terry Reedy a écrit :

I don't think that using UTF-16 with surrogate pairs is really a big problem. A lot of work has been done to hide this. For example, repr(chr(0x10ffff)) now displays '\U0010ffff' instead of two characters. Ezio fixed recently str.is*() methods in Python 3.2+.

I greatly appreciate that he did. The * (lower,upper,title) methods apparently are not fixed yet as the corresponding new tests are currently skipped for narrow builds.

For len(str): its a known problem, but if you really care of the number of *character* and not the number of UTF-16 units, it's easy to implement your own character_length() function. len(str) gives the UTF-16 units instead of the number of character for a simple reason: it's faster: O(1), whereas character_length() is O(n).

It is O(1) after a one-time O(n) preproccessing, which is the same time order for creating the string in the first place. Anyway, I think the most important deficiency is with iteration:

...

...

from unicodedata import name name('\U0001043c') 'DESERET SMALL LETTER DEE' for c in 'abc\U0001043c': print(name(c))

LATIN SMALL LETTER A LATIN SMALL LETTER B LATIN SMALL LETTER C Traceback (most recent call last): File "", line 2, in <module> print(name(c)) ValueError: no such name This would work on wide builds but does not here (win7) because narrow build iteration produces a naked non-character surrogate code unit that has no specific entry in the Unicode Character Database. I believe that most new people who read "Strings contain Unicode characters." would expect string iteration to always produce the Unicode characters that they put in the string. The extra time per char needed to produce the surrogate pair that represents the character entered is O(1).

...

utf16.py, attached to http://bugs.python.org/issue12729 prototypes a different solution than the PEP for the above problems for the 'mostly BMP' case. I will discuss it in a different post.

Yeah, you can workaround UTF-16 limits using O(n) algorithms.

I presented O(log(number of non-BMP chars)) algorithms for indexing and slicing. For the mostly BMP case, that is hugely better than O(n).

PEP-393 provides support of the full Unicode charset (U+0000-U+10FFFF) an all platforms with a small memory footprint and only O(1) functions.

For Windows users, I believe it will nearly double the memory footprint if there are any non-BMP chars. On my new machine, I should not mind that in exchange for correct behavior. -- Terry Jan Reedy

For Windows users, I believe it will nearly double the memory footprint if there are any non-BMP chars. On my new machine, I should not mind that in exchange for correct behavior.

In addition, strings with non-BMP chars are much more rare than strings with all Latin-1, for which memory usage halves on Windows. Regards, Martin

[Apologies for sending out a long stream of pointed responses, written before I have fully digested this entire mega-thread. I don't have the patience today to collect them all into a single mega-response.] On Wed, Aug 24, 2011 at 10:45 AM, Victor Stinner wrote:

Note: Java and the Qt library use also UTF-16 strings and have exactly the same "limitations" for str[n] and len(str).

Which reminds me. The PEP does not say what other Python implementations besides CPython should do. presumably Jython and IronPython will continue to use UTF-16, so presumably the language reference will still have to document that strings contain code units (not code points) and the objections Tom Christiansen raised against this will remain true for those versions of Python. (I don't know about PyPy, they can presumably decide when they start their Py3k port.) OTOH perhaps IronPython 3.3 and Jython 3.3 can use a similar approach and we can lay the narrow build issues to rest? Can someone here speak for them? -- --Guido van Rossum (python.org/~guido)

Why would PEP 393 apply to other implementations than CPython? Regards Antoine. On Fri, 26 Aug 2011 00:01:42 +0000 Dino Viehland wrote:

Guido wrote:

...

Which reminds me. The PEP does not say what other Python implementations besides CPython should do. presumably Jython and IronPython will continue to use UTF-16, so presumably the language reference will still have to document that strings contain code units (not code points) and the objections Tom Christiansen raised against this will remain true for those versions of Python. (I don't know about PyPy, they can presumably decide when they start their Py3k port.)

OTOH perhaps IronPython 3.3 and Jython 3.3 can use a similar approach and we can lay the narrow build issues to rest? Can someone here speak for them?

The biggest difficulty for IronPython here would be dealing w/ .NET interop. We can certainly introduce either an IronPython specific string class which is similar to CPython's PyUnicodeObject or we could have multiple distinct .NET types (IronPython.Runtime.AsciiString, System.String, and IronPython.Runtime.Ucs4String) which all appear as the same type to Python.

But when Python is calling a .NET API it's always going to return a System.String which is UTF-16. If we had to check and convert all of those strings when they cross into Python it would be very bad for performance. Presumably we could have a 4th type of "interop" string which lazily computes this but if we start wrapping .Net strings we could also get into object identity issues.

We could stop using System.String in IronPython all together and say when working w/ .NET strings you get the .NET behavior and when working w/ Python strings you get the Python behavior. I'm not sure how weird and confusing that would be but conversion from an Ipy string to a .NET string could remain cheap if both were UTF-16, and conversions from .NET strings to Ipy strings would only happen if the user did so explicitly.

But it's a huge change - it'll almost certainly touch every single source file in IronPython. I would think we'd get 3.2 done first and then think about what to do here.

Le vendredi 26 août 2011 02:01:42, Dino Viehland a écrit :

The biggest difficulty for IronPython here would be dealing w/ .NET interop. We can certainly introduce either an IronPython specific string class which is similar to CPython's PyUnicodeObject or we could have multiple distinct .NET types (IronPython.Runtime.AsciiString, System.String, and IronPython.Runtime.Ucs4String) which all appear as the same type to Python.

But when Python is calling a .NET API it's always going to return a System.String which is UTF-16. If we had to check and convert all of those strings when they cross into Python it would be very bad for performance. Presumably we could have a 4th type of "interop" string which lazily computes this but if we start wrapping .Net strings we could also get into object identity issues.

Python 3 encodes all Unicode strings to the OS encoding (and the result is decoded) for all syscalls and calls to libraries: to the locale encoding on UNIX, to UTF-16 on Windows. Currently, Py_UNICODE is wchar_t which is 16 bits. So Py_UNICODE* is already a UTF-16 string. I don't know if the overhead of the PEP 393 (encode to UTF-16 on Windows) for these calls is important or not. But on UNIX, pure ASCII string don't have to be encoded anymore if the locale encoding is UTF-8 or ASCII. IronPython can wait to see how CPython+PEP 383 handles these problems, and how slower it is.

But it's a huge change - it'll almost certainly touch every single source file in IronPython.

With the PEP 393, it's transparent: the PyUnicode_AS_UNICODE encodes the string to UTF-16 (allocate memory, etc.). Except that applications should now check if an error occurred (check for NULL).

I would think we'd get 3.2 done first and then think about what to do here.

I don't think that IronPython needs to support non-BMP characters without using surrogates. Bug reports about non-BMP characters usually don't have use cases, but just want to make Python perfect. There is no need to hurry. PEP 393 tries to reduce the memory footprint. The effect on non-BMP character is just a *nice* border effect. Or was the PEP design to solve narrow build issues? Victor

I have a different question about IronPython and Jython now. Do their regular expression libraries support Unicode better than CPython's? E.g. does "." match a surrogate pair? Tom C suggests that Java's regex libraries get this and many other details right despite Java's use of UTF-16 to represent strings. So hopefully Jython's re library is built on top of Java's?

PS. Is there a better contact for Jython? The best contact for Unicode and Jython is Jim Baker (I added him to

On Fri, Aug 26, 2011 at 3:00 PM, Guido van Rossum wrote: the cc) - I'll do my best to answer though: Java 5 added a bunch of methods for dealing with Unicode that doesn't fit into 2 bytes - and looking at our code for our Unicode object, I see that we are using methods like the codePointCount method off of java.lang.String to compute length[1] and using similar methods all through that code to make sure we deal in code points when dealing with unicode. So it looks pretty good for us as far as I can tell. [1] http://download.oracle.com/javase/6/docs/api/java/lang/String.html#codePoint..., int) -Frank Wierzbicki

On 9/8/2011 6:15 PM, fwierzbicki@gmail.com wrote:

Oops, forgot to add the link for the gory details for Java and> 2 byte unicode:

http://java.sun.com/developer/technicalArticles/Intl/Supplementary/

This is dated 2004. Basically, they considered several options, tried out 4, and ended up sticking with char[] (sequences) as UTF-16 with char = 16 bit code unit and added 32-bit Character(int) class for low-level manipulation of code points. I did not see the indexing problem mentioned. I get the impression that they encourage sequence forward-backward iteration (cursor-based access) rather than random-access indexing. -- Terry Jan Reedy

On 9/9/2011 12:12 PM, fwierzbicki@gmail.com wrote:

On Thu, Sep 8, 2011 at 10:39 PM, Terry Reedy wrote:

...

On 9/8/2011 6:15 PM, fwierzbicki@gmail.com wrote:

...

Oops, forgot to add the link for the gory details for Java and> 2 byte unicode:

http://java.sun.com/developer/technicalArticles/Intl/Supplementary/

This is dated 2004. Basically, they considered several options, tried out 4, and ended up sticking with char[] (sequences) as UTF-16 with char = 16 bit code unit and added 32-bit Character(int) class for low-level manipulation of code points.

I did not see the indexing problem mentioned. I get the impression that they encourage sequence forward-backward iteration (cursor-based access) rather than random-access indexing. Hmmm, sorry for the irrelevant link - my lack of expertise here is showing. What I do know is that we (meaning Jim Baker) are taking great pains to always use codepoints even for random access in our unicode code. I can't speak to the performance implications without some deeper study into what Jim has done.

I am curious how you index by code point rather than code unit with 16-bit code units and how it compares with the method I posted. Is there anything I can read? Reply off list if you want. -- Terry Jan Reedy

I, for one, am very interested. It sounds like the 'unicode' datatype in Jython does not in fact have O(1) indexing characteristics if the string contains any characters in the astral plane. Interesting. I wonder if you have heard from anyone about this affecting their app's performance? --Guido On Fri, Sep 9, 2011 at 12:58 PM, fwierzbicki@gmail.com wrote:

On Fri, Sep 9, 2011 at 10:16 AM, Terry Reedy wrote:

...

I am curious how you index by code point rather than code unit with 16-bit code units and how it compares with the method I posted. Is there anything I can read? Reply off list if you want. I'll post on-list until someone complains, just in case there are interested onlookers :)

There aren't docs, but the code is here: https://bitbucket.org/jython/jython/src/8a8642e45433/src/org/python/core/PyU...

Here are (I think) the most relevant bits for random access -- note that getString() returns the internal representation of the PyUnicode which is a java.lang.String

   @Override    protected PyObject pyget(int i) {        if (isBasicPlane()) {            return Py.makeCharacter(getString().charAt(i), true);        }

       int k = 0;        while (i > 0) {            int W1 = getString().charAt(k);            if (W1 >= 0xD800 && W1 < 0xDC00) {                k += 2;            } else {                k += 1;            }            i--;        }        int codepoint = getString().codePointAt(k);        return Py.makeCharacter(codepoint, true);    }

   public boolean isBasicPlane() {        if (plane == Plane.BASIC) {            return true;        } else if (plane == Plane.UNKNOWN) {            plane = (getString().length() == getCodePointCount()) ? Plane.BASIC : Plane.ASTRAL;        }        return plane == Plane.BASIC;    }

   public int getCodePointCount() {        if (codePointCount >= 0) {            return codePointCount;        }        codePointCount = getString().codePointCount(0, getString().length());        return codePointCount;    }

-Frank _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/guido%40python.org

-- --Guido van Rossum (python.org/~guido)

Well, I'd be interesting how it goes, since if Jython users find this acceptable then maybe we shouldn't be quite so concerned about it for CPython... On the third hand we don't have working code for this approach in CPython, while we do have working code for the PEP 393 solution... --Guido On Fri, Sep 9, 2011 at 3:38 PM, fwierzbicki@gmail.com wrote:

...

I, for one, am very interested. It sounds like the 'unicode' datatype in Jython does not in fact have O(1) indexing characteristics if the string contains any characters in the astral plane. Interesting. I wonder if you have heard from anyone about this affecting their app's performance? So far we haven't had any complaints - I'm not really sure how often Jython gets used with astral plane characters at this point, but I expect it will happen more in the future, especially once we put together a Jython 3 and Unicode support becomes a stronger expectation. Personally I'm hoping that in that time frame Java will come under pressure to provide a better answer (or we may need to

On Fri, Sep 9, 2011 at 2:21 PM, Guido van Rossum wrote: think in the same direction as Dino was thinking in an earlier part of this thread and make a more Python specific String type for Jython....)

-Frank

-- --Guido van Rossum (python.org/~guido)

I have a different question about IronPython and Jython now. Do their regular expression libraries support Unicode better than CPython's? E.g. does "." match a surrogate pair? Tom C suggests that Java's regex libraries get this and many other details right despite Java's use of UTF-16 to represent strings. So hopefully Jython's re library is built on top of Java's? Even bigger oops - I answered the thread questions and not this specific one. Currently Jython's re is a Jython specific implementation and so is not likely to benefit from the improvements in Java's re implementation. I think in terms of PEP 393 this should

On Fri, Aug 26, 2011 at 3:00 PM, Guido van Rossum wrote: probably be considered a bug that we need to fix... -Frank Wierzbicki