In light of ongoing discussions of Parrot's string model, I've decided
to prepare a document spelling out my general viewpoint on the subject
of strings. It's intended also to supply a self-consistent set of
terminology. It will frame my future comments. Some notes:

1) This is explicitly arguing for one viewpoint, not against another.
(That is, I've not included any such arguments.)
2) I've written it in a manner which doesn't directly mention Parrot,
so that I can use it in other contexts.
3) There are two separate issues with respect to Parrot: the strings
semantics, and the internal representation/implementation. This
addresses only the former. It also doesn't include an API
recommendation. This is because the semantics need to be sorted out
first.
4) There are a few topics yet-to-be-covered.
5) I should probably provide a (much shorter) synopsis.

----------------------------------------------------------------------
What's a String?

This article is intended to clarify some concepts related to strings.
The motivation is that they are a frequent source of confusion for
developers, working in various programming language. This lays out a
framework for thinking about strings--a viewpoint, if you will. It
reflects a conceptual model that's already embraced by some programming
environments, but even those environments often lack a detailed
explanation. This document also aims to disambiguate various
terms--clarifying some and providing self-consistent definitions of
others which are used inconsistently in different contexts.

So, what is a string?

In the most general sense, a string is a data type in a programming
language, meant to model text. It's meant to allow manipulation,
viewing, analysis, searching, of the stuff you read, or which computer
programs read on your behalf.

A bit more concretely:

     Definition: A string represents a sequence of abstract characters.

So we can't go much further until we say a few words about what a
"character" is. But the two important words to remember from that
definition are "represents" and "characters". (And, "sequence" is
important too, but you won't overlook that one.)

What's a character?

A character, in fuzzy terms, is the smallest unit of meaning in a
language.
A character is an abstract concept. Characters are things like letters,
numbers, punctuation marks, the Japanese symbol for "middle"--stuff
like that. The concept of a character is supposed to capture an
intuitive notion--the notion ususally understood by the common language
speaker. (We are, after all, modelling what's essentially text--the
stuff that humans read. That's the whole point.) That said, precisely
determining what constitutes a character, and what doesn't, is
essentially a judgement call, and a decision. Fortunately, essentially
all existing standards agree on this, in a general sense. For instance,
the lowercase "a" and the uppercase "A" are considered to be different
characters, but stylistic variants (the letter "a" in different fonts,
for instance) are not (instead, they're just different graphical
representations of the same abstract character). These could have been
modelled differently--you could consider "a" and "A" just variants of
the same character. But, as it turns out, no one does it that way.

And I mention that now to prepare you for some arbitrariness--some
conventions that could have gone another way, but which are actually
still intuitively meaningful.

Notice that we haven't said anything about how a computer program (or
language) might model a character. That's important. So far we've just
said *what* a computer program is trying to model, not how it might do
it.

And also, just to hit the point home, we're not talking about the
"char" datatype in C. To keep things clear, we'll refer to that as a
"byte", when it comes up.

What is Unicode?

At this point I'd better explain what "Unicode" means, before I slip
and use the word. People like to throw the word around a lot, and it's
not always clear which of the following related (but different) things
they mean. There are at least 6 different possibilities:

1) The Unicode Consortium, a group of companies and organizations that
got together to sort out the handling of international text. ("Sort
out" in the sense of making it trivial to allow production of text
documents containing a mixture of different langauges, rather than
nearly impossible.)

2) The standard produced by that group, currently at version 4.0.

3) The character model which forms the basis of that standard, and
which also forms the basis of what I'm talking about here.

4) The database of character properties (or the properties themselves)
assembled by the Unicode Consortium. These properties are things like,
"this character has an uppercase version over here", "this character
represents the decimal digit 3", etc.

5) A family of encodings (word defined below) used for the interchange
of international text between computer programs (by mean of files or
network transmissions, for instance). Often, "Unicode" is used to refer
to a specific one; that usage is inherently ambiguous, but harkens back
to the first version of the Unicode standard, which defined only one
encoding.

6) International (multi-language) text handling, in general. This usage
arises because internaltionalization-aware applications tend to base
their implementations on the Unicode character model, and tend to
support the Unicode encodings. But it's important to recognize this
usage, because sometimes the term "Unicode" is used in contexts which
don't involve any of the above per se, but rather just indicate an
awareness and handling of international text issues.

Of these, really (3) is the only one which someone could really
"disagree" with. (That is, the consortium, standard, database, and
encodings exist and are precisely defined--there's nothing
philosophical there to reject.) But the other important point is that
these are all separate things--sometimes people will cite the need to
support other encodings as an argument against the character model,
which doesn't follow logically.

So the string/character model I'm espousing is based largely on the
Unicode Character Model, but it would be misleading to say that I'm
advocating, "use Unicode". (What would that mean, anyway?) But it's (3)
that does the conceptual heavy lifting, and (4) which does the grunt
work. Or, (3) is the concept, and (4) is the details.

I'll try to avoid using the word "Unicode" by itself, to avoid
confusion, but if I do, then I'm probably referring to the Unicode
Standard, or something it specifies.

So let's review. A string is a concrete thing--a data type in a
language; it represents a sequence of (abstract) characters, a
character is a unit of meaning in a language, and a character has
properties which have been collected into a database. To go a bit
further, the fundamental question you can ask a string is, "what's your
Nth character". All else flows from that.

What's a code point?

So if the fundamental question you can ask a string is, "what's your
Nth character", we have to talk a bit about how one would
programmatically express that answer--that is, what sort of data type
is/can/should be use to represent a character? Fundamentally, a
character can of course be represented opaquely--in an object-oriented
language, you could have character object. That's quite reasonable. As
it turns out, people find it convenient to programmatically represent a
character by an integer (think "whole number", not a specific data type
here). It's convenient for several reasons--it's compact and easy to
refer to in speech. And if the fundamental thing you can ask a string
is what its Nth character is, then the fundamental things you do with a
character is look up its properties, and test it for equality against
other characters. So if you just go through and give each character a
little serial number, then you can find the properties of a character
by using its number as an index into a property table (i.e., character
3's properties are at slot number 3 in the table), and you can tell
that 2 characters are different characters by checking whether they are
represented by different numbers.

A number used to represent a character like this is called a "code
point". Which number you choose to assign to which character is
fundamentally arbitrary--its one and only use is as a unique lookup
key. The letter "A" could be assigned the number 1, or 42, or 31337, or
2001, or anything else. It doesn't matter. Now, various standards have
numbered various characters in various ways, though many don't actually
think in these terms, so to be clear if you are going to refer to
"character number 42" or "the code point for the letter 'A'", then you
really need to point out what numbering scheme you are talking about.
Fortunately, the Unicode Standard has numbered *all* of them--it's
given a number to essentially every character in every
digitally-represented langauge in the world. Since its numbering scheme
is comprehensive, and since the numbering scheme is arbitrary, without
loss of generality we are going to use the Unicode standard's numbering
scheme for the rest of this discussion, and we'll go ahead and pretend
it's the only one. So when we say, "the code point for the letter 'A'",
we'll mean the code point that the Unicode Standard assigns to it,
which (in case you are wondering by now) is 65. (See, the number itself
is not very interesting!)

So, let's review again. For various practical reasons, it's preferable
to programatically represent characters using integers, you have to
pick an arbitrary numbering scheme, and somebody's done that, and it's
a good one. This numbering scheme defines a one-to-one correspondence
between numbers (code points) and characters, and that makes it
tempting to pretend that characters *are* numbers. But it's important
to keep in the back of your mind an awareness that the numbers merely
help you pick out the characters, and it's the characters themselves
which are important, and characters are *abstract*--they never actually
live inside of a computer program. [Note: Of course, some numbers don't
represent any character--there are only so many characters. So to be
mathematically precise, there's a one-to-one correspondence between a
subset of integers and all characters.]

What's an encoding

So, what we've convered so far is the type of stuff you need to work
with text in-memory. We can use the number 65 to represent the letter
"A", and we have a properties database to tell us whether A is a
number, or whitespace, or whatever.

But, text being what it is, people tend to want to save it to disk, or
transfer it between applications. That is, they want to do IO
operations on strings.

Now as it turns out, IO is alway an operation which involves bytes.
Even if your IO is hidden under an abstraction layer, at the bottom
you're always reading and writing bytes. Strings are not,
fundamentally, bytes. So how do you create bytes from some high-level
construct like a string? You define a serialization algorithm, that's
how. That's an encoding:

     Definition: An encoding is a mapping from sequences of abstract
character to sequences of bytes (and vice versa).

Since we've said that a string is supposed to represent a sequence of
abstract characters, we could also just say, "An encoding is a mapping
from strings to sequences of bytes (and vice versa)."

*Important Note*: This is, in particular, an area where there is much
conflicting and inconsistent terminology. The concept that I just
defined is the exact same thing that the Unicode Standard refers to as
a "Character Map". That would probably be the preferred term, since I
don't believe it's been used elsewhere with a differing meaning. But,
it's not a commonly used term, so I'm going to use "encoding" instead,
with some hesitation, so that someone jumping into the middle of this
discussion has a chance of figuring out what I'm talking about. My
usage of "encoding" matches the usage of the XML specification, and the
Objective-C Foundation framework. Java and MIME use the word "charset"
for the same concept, and IANA uses "character set". Others use the
term "character set" for something different. But the important thing
to remember is just that, for the purposes of this document, I'm using
the definition above, and when you are reading elsewhere and encounter
any of those terms, you should look for a definition of what is meant
there.

The absolutely crucial thing the remember about an encoding is that it
defines an interchange format--that's 100% what it's for. It's purpose
is to let you communicate textual data between processes (or, store it
to the filesystem for later retrieval by some process). Encodings have
nothing, fundamentally, to do with any sort of in-memory representation
of a string.

The other thing to remember about an encoding is that there are lots of
them--lots and lots of national and industry standard define lots of
different ones. They tend to have names like, "ASCII" or "ISO-8859-1"
or "Shift-JIS" or "Big5" or "UTF-8".

The reason there are so many of them is that, in the early days of
computing, most everyone got it into their heads that they needed to
represent textual data using only one byte per character, which meant
that an encoding could only handle 256 different characters. This was
fine for English (and in fact ASCII only encodes 128 characters), but
as soon as you hit Europe you needed more characters--for French and
German and Greek and Icelandic and Polish and Turkish and so on. You
need more than 256 characters to handle all of that, so different
encodings where invented to handle different collections of characters.
This doesn't sound so bad, and it's fine as long as everyone just talks
to the guy next door, but it quickly turns into a mess if you try to
step outside--you can't create a single text document with words from
multiple languages (for some combinations), and (potentially worse)
when you read in a file created by someone else, you need to know what
encoding they used (that is, you need metadata, of the sort supplied by
MIME and HTTP headers, but not supplied by most filesystems). This
wasn't fun for anyone.

The obvious thing to do, in retropect, was to come up with a different
plan, one which would allow you to handle all languages without a
separate song-and-dance for each one. That's in fact what the Unicode
Consortium came together to do. And they did it. It was an enormous
undertaking.

Okay, back to the point. Not only are there lots of different
encodings, but by their nature most only know how to encode strings
containing a limited collection of characters. ASCII, for example,
doesn't know how to encode Japanese Kanji. But the Unicode Standard
defines a collection of encodings (UTF-8, UTF-16, and UTF-32, with big-
and little-endian variant of the latter two) which can encode strings
containing basically any character.

It's important to take a moment to point out how general the above
definition of "encoding" is, and what it doesn't imply:

1) As mentioned, an encoding doesn't have to know how to encode every
possible string. And reciprocally, not every sequence of bytes will be
decodable by every encoding.

2) Although an encoding is really a pair of algorithms (one to
serialize, one to de-serialize), that doesn't imply that an encoding
has to be strictly invertible. That is, if I encode a string into a
sequence of bytes, and then decode that sequence of bytes into a
string, I might not get back the same string I started with. For
example, and encoding might, conceptually, strip accent characters.

3) An encoding doesn't necessarily operate on a character-by-character
basis. That is, the bytes to encode "ab" might not be the concatenation
of the bytes to encode "a" with the bytes to encode "b". It's even
possible, based on the above definition, that an encoding might be able
to encode the string "ab", but not the string "ba". (In practice, I
don't know if this ever occurs "in the wild".)

So the key points here are: (1) an encoding is all about IO, (2) not
all encodings guarantee data integrity, and (3) the Unicode encodings
_do_ guarantee data integrity. Another important point is that the
choice of an encoding is a crucial piece of metadata for bytes
undergoing IO, and thus it's the sort of thing which is indicated
explicitly in higher-level protocols and formats (HTTP, MIME, and XML,
to name a few), and it is almost always indicated *by name*. IANA
mantiains a registry of these, and many protocols use the IANA names to
specify encodings.

Another important point: The Unicode Character Model (unlike many other
standards) thinks of the process of going from strings to bytes as a
multi-step process. That's useful from a pedagogical point of view, but
in fact no one much cares about the results of the intermediate steps.
(That is, Unicode describes the process as: characters --> code points
--> code units --> bytes, and I'm saying that the code units aren't
very useful to think about.) The reason for this is very
simple--encodings are only about data interchange, and data interchange
protocols and formats want to specify the encoding with a single name,
which picks out the whole strings-to-bytes mapping. They don't much
care if two different encodings could be thought of as agreeing on one
of those steps, and differing on another. If you're writing a library
to convert between sequences of bytes in different encodings, then this
can also be useful (to minimize code duplication), but it really has
nothing to do with the semantics of a string.

What's a Character Set?

As mentioned above, some people use the term "character set" to mean
what I'm calling "encoding".

In my usage, a "character set" is something simpler--it's a set of
characters, in the mathematical sense of "set". It's an unordered
collection of characters. The letter "A", the comma, and the Japanese
character for "middle"--there, that's a character set. The Unicode
Standard uses the term "abstract character repertoire" for this notion.
That's actually less ambigous terminology, but quite a mouthful. I'll
try to use "repertoire".

A character set, in this sense, isn't a terribly interesting concept,
and it's a good term to stay away from, given the ambiguity. But people
often say things like, "the ASCII character set". Now, in my usage, the
ASCII standard primarily defines an encoding. However, subject to a few
caveats mentioned above, an encoding implicitly picks out a character
set--specifically, the set of characters that it can encode. So in
light of this, I can meaningfully say "the ASCII character set", and
talk about "how the Shift-JIS encoding handles characters in the
ISO-8859-1 character set". I mentioning this not to particularly
encourage the usage, but because you'll hear it, and because it's a bit
less awkward to say than things like, "how the Shift-JIS encoding
handles characters encodable in the ISO-8859-1 encoding". And also,
it's convenient to say, "ASCII characters" (through a small abuse of
language) to talk about "ABC...", even in the context of another
encoding.

Wow, so we've covered a lot of ground. Let's sum up again: Conceptually
strings model a sequence of abstract characters--that's their job.
Encodings (or Character Maps) define interchange formats, and are only
important to IO--to let you transmit strings between processes (via the
network or via files). Encodings are basically algorithms, but in usage
they tend to be identified by conventional names.

What's a Locale?

One of the things that people like to do with strings is to manipulate
them. Two prototypical things they want to do are case transformations
(uppercasing and lowercasing) and sorting. And they also want to do
things like create string representations of numbers and dates, and the
inverse--interpret strings as representing numbers and dates.

Now as it turns out, different people want to do these things in
different ways--think of "1/31/2004" v. "31/1/2004" v. "2004-1-31".

Consequently, that means the sorting algorithms and number formatting
algorithms need to know which way you want to do things (and which way
I want to do them). Traditionally that means that these types of
algorithms need to take a parameter (explicitly or implicitly) to
specify this choice. Traditionally, this parameter is called a
"locale".

Now this word can cause a lot of confusion. It doesn't need to. In the
most concrete sense, a "locale" just specifies a set a algorithms and
settings--things like the format to use for dates, the comparison
operation to use for sorting, and the characters to use for the decimal
and thousands separators for numbers (think of "1,000.50" v.
"1.000,50"). In fact, to reflect this definition, I'm going to coin a
new term. I'm going to call this a "Text Preferences Set", or "TPS" for
short, to emphasize this defintion.

Now where the complexity tends to come in also explains where the term
"locale" came from. People, as it turns out, don't (often) sit around
thinking up new sort orderings, or new formats to display numbers and
dates. More often, they want to do these things in a way that matches
the custom of some language or country or region--they want to sort
strings to match somebody's phone book or dictionary. Consequently,
they find it convenient to specify a TPS by specifying a langauge or
country, and use notations such as "en" for English and "en_US" for US
English (v. British English). But from an API perspective, this is just
a way to go look up a TPS--once you have one, it doesn't much matter
where it came from (looked up by some name or build up
programmatically, piecemeal), you just use it.

Sorting, and Tailorings

Now as I hinted at above, people in different countries like to sort
strings in different ways. Fair enough. That makes it sound like I need
to define a whole bunch of binary string comparison functions--one for
each different custom. One for German, one for Swedish, one for
English, one for Japanese, etc. As it turns out, there's a more compact
way to do this.

The Unicode Standard defines a base collation algorithm (sort
algorithm)--you can use it to sort strings composed of any characters
at all, but it doesn't necessarily give you an order that matches any
particular langauge's custom (though for many languages it's at least
reasonable). This is called the Unicode Collation Algorithm. Now, this
algorithms supports the concept of "tailorings"--tweaks to change the
sort behavior for certain characters (or sequences of characters). The
idea is that you start with the UCA, and supply one set of tailorings
to get the customary English sort order, another set to get the German
sort order, etc. There are three really nice things about this
approach:

1) Rather than writing a whole new algorithm, you just tweak a base
algorithm, and these tweaks are usually data-driven. (That is, they
usually take the form of modifications to a weighting table, rather
than an algorithmic difference.)

2) Under any set of tailorings, you can sort strings containing any
characters. So, you can meaningfully talk about how Japanese words sort
under the English tailorings (or English locale or traditional English
TPS). It's just that, naturally, the sorting of Japanese words won't
differ under English v. German sorting rules (but sorting of some
English words might), and English words probably won't sort differently
under Japanese v. Taiwanese sorting rules (but Japanese and Chinese
words might).

3) In contexts where you don't know what language is relevant, you have
a reasonable fallback sort order.

So for sorting, a language (or more generally, a TPS) just provides a
bit of tuning on top of a default algorithm, and you can sort with or
without taking language into account.

Now, it's important to note that the UCA isn't just sorting in terms of
the numerical values of the Unicode code points assigned to charactes.
But you can sort this way too--it's sometimes called "binary
order"--and it can make sense to do this in situations where you don't
much care _what_ the sort order is, just that you have something
canonical (for instance, so that you can count duplicates in a list).
The reason you might want to use binary order in cases like this is
that it's faster, and simpler to implement. (Also, you might know that
it's an acceptable sort order for your problem domain--maybe you're
sorting part numbers, for instance.)

So, another sum-up: A TPS (or "locale") is a set of preferences
relating to how you want to carry out certain string operations, and
often these preferences take the form of "tailorings" or tweaks on top
of a base algorithm.

Another place where this sort of thing comes up is with case
mappings--how you uppercase or lowercase strings depends somewhat on
language-based conventions.

Another use for uppercasing or lowercasing in English is to perform
case-insensitive string comparison, so that "foo" and "FOO" and "Foo"
and "FoO" compare as the same. In English, you can either uppercase
everything before comparison, or lowercase everything--it doesn't much
matter which you do, the result will be the same. In other languages,
that's not necessarily the case. Conveniently, the Unicode Standard
defines a process called "case folding", which is designed to let you
do case-insensitive comparisons. Case folding transforms strings into
case-canonicalized representations (conceptually like uppercasing then
lowercasing everything), and it does this in a single,
non-language-sensitive way. So even though language is relevant to case
mappings, you can use case folding to do case-insensitive string
comparisons without specifying a language (or TPS).

So a take-away point here is that the Unicode Specification provides
infrastructure in a number of areas for doing operations in a
TPS-sensitive or TPS-insensitive manner, and provides a smooth
transtion between the two.

A note about Language

There's one thing about langauge-sensitive operations which people tend
to overlook, and which it vitally important: for string operations,
it's not the language _of_the_string_ which is important, it's the
language _of_the_reader_. The canonical example here is this: Consider
a list of names, some of them German, and some of them Swedish. I, as
an English-speaking reader, would want to see these sorted in the
_English_ sort order. I don't much care how Germans or Swedes would
sort them. My local phone book doesn't take the national origin of a
person into account when organzing the listing. It doesn't matter--the
point of having it sorted it to allow people in the US to look up a
name. This means that there isn't a problem of how to compare "English
strings" and "German strings"--the language of the sort operation, not
of the individual strings, determines the binary comparison algorithm
used in the sort. That also means that it's a non-problem to have a
single string containing words from different languages.

This also means that, in the US, the German word "STRASSE" (on a sign
or in the name of a company, for instance) would lowercase as
"strasse", even though in Germany it might be preferable to use
"straße".

What's a Grapheme Cluster?

More about this later, but briefly: As it turns out, certain langauges
have certain funny conventions about grouping sequences of characters
into what they see as one "thing". For instance, Spanish considers the
character sequence "ll" to be a separate letter (not two "l"'s), and
similarly for "rr". Now, they don't really treat them specially from an
"information processing" point of view--I don't believe that there are
any encodings which treat "ll" as a single character, and I don't think
that Spanish typewriters have a separate key for "ll". It's just that
they think of it as a separate letter--it shows up when they are
reciting the alphabet, and they see the word "llama" as containing four
letters (the first letter being called "ell-yay", with the word
pronounced "yama", not "lama"), and they would sort that word after
"luego" (because "ll" comes after "l").

The Unicode Standard calls this a "grapheme cluster", and (as mentioned
above) it's relevant to localized sorting and word-length counting.
This is a somewhat unfortunate term, since "grapheme" is a linguistics
term, and it means something different to linguists. Previous versions
of the Unicode Standard used to term "grapheme", but they've migrated
to using "grapheme cluster" to minimize confusion, though the standard
is still somewhat jumbled in this regard.

But the brief take-home idea here is: "grapheme cluster" ("grapheme"
for short, with reservations), in this context, is a sequence of one or
more characters (a range in a string) which natural-language users
would see as a unit. This is again a situation where language (or TPS)
is relevant, but where the Unicode Standard provides a default
TPS-independent implementation which allows for tailorings. So again
there's a smooth transition for language-independent to
language-dependent settings.

Also, importantly, a grapheme cluster is a notion built on top of
characters (it's a cluster of characters), and choosing a langauge lets
you refine how you break up a string into grapheme clusters, but it's
just a refinement--"adding a language into the mix" doesn't pick out a
different semantic construct, it just help you customize your choice of
what ranges make up single graphemes.

I haven't yet covered a few important topics, such as different
character sequences representing equivalent graphemes, canonical and
compatability equivalence, and Unicode normalization forms. I also
haven't said anything yet about concrete implementation or API
guidelines.

JEff