Unicode -- issues and recommendations

My apologies for the length of this. I am trying both to be careful and
to explain rationale as I go in support of a higher quality discussion.

As always, accept what portion of this you find helpful and feel free to
abandon the whole thing.

I haven't reviewed the circa 2000 discussion on this list on this topic.
I'm going to try to translate our current outcome for BitC into C--
terms. I'm hardly a UNICODE expert, but as layman go I'm more informed
than I ever really wanted to be. Much of what I have learned is due to
Mark Miller.



ISSUES

There are really three distinct issues to consider, and the options for
handling them have a range of complexities:

1. Support for Unicode identifiers.

2. Support for front end expression of Unicode literals.

3. Representation of Unicode strings, which is really a runtime
   design issue.

The reason that all of this is complicated is that there are a range of
implementation choices that have been made by existing runtimes. In
fairness to the current state of existing language runtimes, many of
them adopted Unicode 2.1 before it was recognized that 16 bit code
points would be insufficient. The decision, viewed then, seemed much
cleaner than it has actually turned out to be in hindsight.

To confuse matters, the UNICODE people recently issued a downright
absurd recommendation on string manipulation, apparently because they
don't grok the "cord" data structure. They share this distinction with
W3C, which could not agree on a character indexing and encoding policy
in common between XML and XSLT!


Note that if any of this is adopted, section 3.1 must be rephrased. :-)


IDENTIFIERS

Broadly, Java got this right. The Unicode specification has two
character classes that correspond to "first identifier char" and
"continuing identifier char". Various i18n libraries provide decent
support for this. So far as I can tell, the best design position is the
following:

  1. The C-- specification is to follow the Unicode recommendation
     on this issue. The specification in question is the Unicode
     Standard Annex #31:

	http://www.unicode.org/reports/tr31/tr31-5.html

     This is (with some additional characters) the standard adopted by
     Java, and I believe by C#. It is backwards compatible with all
     of the ASCII identifier standards that I know about.

     For purposes of the C-- specification, this would constitute
     a revision to section 3.3.2. See the corresponding text of the
     Java standard.

  2. As an interim step, some well-defined library that implements
     the recommendation (modulo bugs) is to be used. I recommend some
     variant of IBM's ICU library.

  3. For now, the specification should state that identifiers
     are constrained to the ASCII subset represented in UTF-8 with
     the traditional [a-z_][a-z0-9_]* rule (which is a subset of the
     Unicode guideline).

  4. I see that the current document adds some other characters,
     notably '.', '$', and '@'. If these aren't already in the
     relevant UNICODE character sets, simply grandfather them.
     Java did something similar, as does BitC.


Impact summary: suitable changes in the lexer, sort all identifiers
(where required) internally according to code points, ignoring language
sensitive encodings. For internal purposes, use normalization C, which
is the nearly universal choice. It actually doesn't matter much what
normalization you use, so long as you choose one. [I need to double
check the statement that Normalization C is the de practico standard.]

LITERALS

Character Size:

I don't think that C-- can take a position on character size. The
concrete options are:

  1. Only support ascii characters (7 bit). If you have to pick and
     interim solution, choose this one, because all 7-bit ASCII
     characters are valid UTF-8 encodings with the same meaning.

  2. Choose ISO-LATIN-1 characters (8 bit). This is hopelessly bad,
     because there is no viable path from here to Unicode.

  3. Choose position (1) above, but relabel it "the UTF-8 encoded
     ASCII subset of UNICODE. This is nice because it has a zero
     cost of development. :-)

All other choices require selection of a larger character code point
size. For characters, there are two possible choices:

  16 bit:  What everybody did as of Unicode 2.1, before we
	   noticed that this actually wasn't big enough.

	   This is how Java got into the very odd position
	   of expressing 32-bit Unicode using vectors of 16-bit
	   code points. Note that this breaks character indexing
	   utterly.

	   Historical aside: this was also the common choice
	   for wchar_t prior to the introduction of shift-JIS.
	   Essentially all modern C runtimes now define wchar_t
	   as a 32-bit quantity, which should be viewed as a
	   strong, experimentally validated hint about the right
	   answer if you are free to make a choice that is not
	   constrained by considerations of compatibility.

  32 bit:  This is the right choice unless you have a compatibility
	   constraint with existing environments, for the simple reason
	   that all currently known code points actually *fit* in
	   this representation.

	   Because Java made their commitment at the time of the
	   Unicode 2.1 standard, I believe the current awkward state
	   of affairs is that characters in the extended Unicode planes
	   simply cannot be represented at all in a Java character,
	   and must be treated as strings. This does not seem like
	   a desirable constraint for C--.

Because some environments will impose compatibility constraints, the
back end simply should not take a position on character size. If there
is no other need to distinguish characters from integers, then it should
be left to the front end to choose bits8/bits16/bits32 as appropriate.
If there *is* a need to differentiate them at the kind level, I suggest
char8/char16/char32, but again don't take a position on which one is
"the" character.

Section 3.3.5 gets the interim solution right for legal literal values
(not clear if this was by intent) by specifying that the legal
characters are ASCII (7 bit) rather than ISO-Latin-1 (8-bit). However,
the decision to make character literals be bits8 by default was
unfortunate, because the vast majority of code points cannot be
represented this way.

Rather than break compatibility, I would add a new option to the TARGET
directive (section 4.7):

	charsize N

where N is one of "8", "16", or "32", and describes the default
character literal size. This should NOT imply that a string literal is a
vector of this element size. For backwards compatibility, an unspecified
charsize should default to 8.


Character Literals:

C-- is in the very fortunate position that it is an intermediate form.
In consequence, it is okay to take a position on the lexical encoding of
character literals that has nothing to do with the selection of code
point size. This decision is purely a lexical matter. It is not a
position on the *representation* of strings or characters.

Because of this, there is a clearly preferred answer: UTF-8. This is
preferred for several reasons:

  1. It is the densest encoding available in most of the world.
  2. In those parts of the world where it is NOT a dense encoding,
     (e.g. China) longer encodings are required in any case.
  3. It is sufficiently easy to emit.
  4. Nearly all editors that understand international character
     sets at all understand this representation.

So my suggestion is to state that a literal value can either be
initialized from an unsigned integer, which is interpreted as its
ordinal code point, or from a suitably quoted UTF-8 character.

If a quoted UTF-8 character constant is presented, the compiler should
range check the value just as it would for an integer literal. You don't
get to squeeze 32 bits into a 16 bit value type. Sorry.

String Literals:

>From a lexical perspective, the same argument for UTF-8 as a
lexical-level representation applies. In fact, the compactness rationale
is even more compelling, but the *use* of this representation is much
more problematic. The problem is that (a) whatever lexical
representation is selected must be expanded back into the target
environment string representation, but (b) we want to choose one that is
decently compact and handled well by editors for the sake of human
readability.

My suggestion is as follows:

1. In the absence of decoration, a string constant appearing in the
input is interpreted as and re-emitted as a UTF-8 sequence, this being
by far the most common solution and the only sensible choice of variable
width encoding that is semantically sound. This is backwards compatible
with today's C-- specification.

2. Strings may be annotated with one of UTF-8, UTF-16, UTF-32, or UTF-C
(check me on the last) with the meaning that the UTF-8 string lexeme
should be expanded as a vector of UTF-8 or UTF-16 code points (with
suitable range tests), a vector of UTF-32 code points, or a vector of
16-bit code points that do the screwed up 32-bit encoding adopted by
Java and C# (No hidden value judgments here!)

The key point: the C-- input representation should be chosen for editor
and compiler convenience, and need not match the target representation.

It *may* be desirable to add another TARGET directive to express a
default here. My sense is that explicit annotation in this case is not
lexically or visually cumbersome, and that explicit expression of intent
is therefore desirable.


RUNTIME STRING REPRESENTATION

This is where things get depressingly interesting. The basic reason that
people advocate 16-bit code points for UNICODE (absent a compatibility
issue) is that (a) 32 bit code points for everything will double your
total data size statically, and in some cases also at runtime, and (b)
people don't understand the "cord" data structure. Or, in some cases,
they have a compatibility requirement.

>From an implementation perspective, cords (sequences of character
vectors, each vector having a single element representation that may not
agree with its neighbors) are the right thing to do. They can provide
log-n indexing (where n is the number of distinct cords) and lookup
without sacrificing compactness. IBM has done a very nice utility
implementation of this for Java in the ICU package which is enough to
make any sensible programmer remove the Java string class from their
library entirely.

>From a runtime design perspective, however, a cord is a fairly complex
language-level datatype, and it probably isn't a good idea for the C--
implementation to dictate a representation for them.

My suggestion: duck.

If the front end wants a flat representation and can specify the desired
size, well and good, and the C-- backend should facilitate this much.
This allows the front end to express each cord fragment as an
appropriately represented literal.

If the front end wants literals emitted with some fancy cord-like
structure, it should break the string(s) up into a set of homogeneous
sequences and emit the appropriate homogeneous sub-literals and
connective structure by hand.

One could certainly add function along these lines to C-- in a future
revision, but it does not seem well motivated at this time, nor is there
an obviously "right" representation to choose.


Regards,


shap