Doing Unicode right, part 2

Note: this post won't have anything to do with what I said I'd write in my next post.

Previously, I was a bit vague with what I wanted from my Unicode library. I'm going to invent a new term for what I want, since existing terms don't match this: Factor should be a Unicode-friendly language. "Unicode-perfect" only gets 1 relevant Google hit, so I think I'm safe in choosing this term. Currently, there are no Unicode-perfect programming languages, though there have been many attempts. A programming language is Unicode-perfect if:

1. There are correct I/O routines for dealing with Unicode (this is the easy part).


2. All programs written in the language (that don't have obvious bugs or purposely look at things at a low level) are Unicode-conformant, as defined by the Unicode standard. It shouldn't take any effort at all for the programmer to make their programs this way.


3. All scripts defined by Unicode are correctly processed (though not necessarily displayed) with no special handling by the programmer. This includes scripts outside the Basic Multilingual Plane (BMP) and scripts added in the most recent version of Unicode.


4. Using Unicode should cause no significant performance penalty

A side note: it's funny that most Unicode libraries and programming languages talk about "Unicode support" rather than "Unicode conformance." This is probably because Unicode support is not defined anywhere. Any program that has UTF-8 or UTF-16 I/O (even if it's buggy) can claim "Unicode support", but few things actually conform to the standard. Conformance is a goal because it lets programs have predictably correct behavior in all supported languages. Conformance does not require that everything is supported. It only requires that everything claimed supported is. For example, I do not plan to support word breaking properties, but as long as I don't claim to do so, my programs can still be Unicode-conformant

It is possible to process Unicode properly in any Turing-complete programming language. But will developers want to do it? Say a programmer is using C to write a program which they initially believe will only be used with ASCII. For efficiency and ease of writing, they use a null-terminated char * to represent the string. If the programmer later decides to use Unicode, they have a number of decisions to make: which Unicode library will they use? What encoding will be used internally? Additionally, all existing operations used for processing strings will have to be switched to the new Unicode version.

Now I can hear all you Pythonistas, Perl Monks and Java and C# programmers saying, "My language is Unicode-perfect!" No it's not. You're wrong, and it's not just about lack of support for obscure scripts. None of those languages really hides the encoding of strings from the programmer. If you index a string, an operation available and commonly used in all of those languages, the result may be a surrogate pair or UTF-8 octet rather than a character. One solution to this problem is to make all strings in UTF-32, so all code points can be represented directly. Another solution is to make some strings 8-bit when characters with code points U+0000..U+00FF are used and 32-bit for everything else, though this becomes complicated when strings are mutable, as they are in Factor.

One prickly issue is normalization. According to the Unicode standard, "A process shall not assume that the interpretations of two canonical-equivalent character sequences are distinct." Basically, this means that if the canonical decomposed normalization form (NKD) of two strings is equal, the strings should be treated as equal. Now, if a language is going to be Unicode-perfect, it has to let programmers not care about this. The easiest way to handle this is to put all strings in NFD internally, when strings are created and read from streams. (On output, strings should be converted to NFC so the greatest number of programs can process them.) But the only way to assure that strings stay NFD while inside the language is to make them immutable. Otherwise a user may, for example, insert a precomposed character into a string, making it no longer in NFD. This might be how it's done in Java or Python or other languages with immutable strings, but I'm not sure. In Factor, if this approach were to be taken, many changes would have to be made, but they would all be internal. All string mutations would take place in sbufs, and >string would normalize. This requires a fast normalization algorithm, but I think that's possible, since in many cases, normalization is a no-op.

The other option, which is very undesirable, is to not have strings under any sort of normalization and make the programmer put it in a normalized form. This is very problematic, though. For one, normalization only changes behavior in a few edge cases, but it requires time operate, so careless programmers may be tempted to skip it. Another problem is that it breaks abstraction: most programmers don't know that NFD exists, and they shouldn't have to. The third problem is where to place the normalization operation. One option is immediately after operations which construct strings. Another option is immediately before operations which rely on equality of strings. It may be tempting to do something like : string-map map normalize ; inline or : string= [ normalize ] 2apply = ; to make these options easier, but there are far too many words which use strings to make this practical.

Though it may be difficult, it is not impossible for a programming language to be Unicode-perfect. It is my goal to achieve this for Factor.

Update: Funny, it turns out some people actually read this blog. Thanks for all your comments, though I'd like it if people wrote their name or a suitable pseudonym when commenting.

An anonymous commenter suggested that C under Plan 9 might be Unicode-perfect, since the OS and all libraries use Unicode to the core. That's definitely a possibility, though there are two possible problems: 1, a stupid programmer could manipulate strings without the new library that allows UTF-8 strings, and 2, programs written this way aren't cross-platform. Still, neither of these kills its utility.

Schlenk suggested that Tcl(/Tk), while not perfect, might be good. A cursory glance at it makes it appear that Unicode can be completely ignored by the programmer. This leads to a different issue: how does the programmer specify input/output encodings? But I'm sure they have this worked somehow. Another thing is that many of the websites that I read about Tcl and Unicode contained common fallacies like that Unicode is a 16-bit encoding (it is 21-bit), or that a UTF-8 can contain up to 6 octets, specifying a 32-bit character (it can only contain 4 octets which stands for a 21-bit character). But this error isn't necessarily reflected in Tcl's implementation.

For Factor .89 (Factor .88 should come out in a few days), Slava has promised to make strings immutable, and conversion from a sbuf to another sequence to normalize. Operations like append and map, when operating on strings to create strings, will first form an sbuf. The sbuf will be converted to a string, normalizing it. This will make all strings normalized (I chose the NFD normalization form) unless you do something deliberately evil like [ code-pushing-a-precomposed-char ] { } make >string. It should be noted that for most output operations, strings will be converted to NFC form (except for Mac OS pathnames).

Doing Unicode right, part 1

When I found out that Factor didn't really support Unicode, I decided to implement it myself. One goal in this is to do Unicode right, where other programming languages had terrible bugs, exposing programmers to surrogate pairs, casing complications and other quirks of Unicode. My other goal is to spend absolutely no money in doing it. Unicode is a free standard, so it should not cost anything to get the necessary information about it. I started to read Unicode Explained every time I went to Barnes and Noble, so I could figure out how to accomplish it. This shouldn't be too hard, should it? It's only a character encoding...

It wasn't hard to get a finite state machine working to decode UTF-8 and UTF-16, and it wasn't hard to write an encoder either, using make (though I may refactor that out). But then, I decided to do case conversion, opening a can of worms. After a bit of research (it really doesn't say anything on the internet on this outside of the standard itself) I found out that unicode.org hosts a web-accessable text database of Unicode characters in a file called UnicodeData.txt, including their upper and lower forms. Since I was doing Unicode right and everything, I decided to use Unicode 5.0, not 2.0 like most things do. And to make transition easy, I got all data directly from these files without any code generation (as I did for libs/xml/char-classes.factor) and with minimal hard coding.

For most characters, this maps cleanly 1:1, but for just a few (maybe 100) there are multi-letter translations for upper or lower case. These are defined in a separate file called SpecialCasing.txt. For example, in German, "Fuß" >upper ==> "FUSS". Though this is a little difficult, it ultimately worked out fine. This is about as far as I've gotten. For a small subset of these (around 15) there are conditional mappings: a word ending in a sigma, when made into lower case, must end in a final sigma; in Lithuanian, Azeri and Turkish, there are oddities with dots on I (and sometimes J). Some of the mappings are duplicated in the Turkish/Azeri section and the main UnicodeData.txt and I have no idea why. Additionally, the file format in SpecialCasing.txt changed in 5.0 from 4.0, but I can't figure out what the new semantics are. The strangest thing is, actually, the fact that the Lithuanian, Turkish and Azeri mappings are locale-dependent, that is, the language of the text must be known. But the whole point of Unicode to allow multilingual texts. How is this compatable?

I would look at the Unicode standard itself to resolve these issues (there's not exactly a big Unicode developer community I can tap into), but the most recent version available online is 4.0, and the format of SpecialCasing.txt is incompatible. The website lists the table of contents and says that links to PDFs will be made as soon as the standard is put up on the website. But it's been two months since the book was released, and theses are computer people: they should be capable of getting it on the website. Buying the book (or having someone else buy it for me) is out of the question; that would not be in keeping with my second goal.

To see my progress so far, look in a factor distribution in libs/unicode. In the next update, I'll discuss Unicode equivalence forms and why they make no sense at all.

More string parsing?

While I was writing my XML parser, I swore that I would never again write anything that involved string parsing. I quickly broke that promise, and the next two libraries I wrote were a CSV (comma-separated values) parser and a UTF-8/16 encoder/decoder. The good thing about these is that they'll be useful. I'm planning on using the CSV parser, for example, in fixing a complicated spreadsheet for a volunteer association I'm in (the version of Excel I have exports to CSV but not XML). Both the Unicode encodings and CSV are relatively simple, but I implemented the encodings in two different ways. For CSV, I used the imperative parsing model that I described in previous blog entries. To make this cleaner, I split off a new module, libs/state-parser, accompanied by better documentation.

This way, I was able to build a working program, but the problem with this approach is that it is imperative. This makes it so that the order in which words appear matter not only in terms of stack effect but also side effect. You might think in a language like Factor, where flow of control is extremely easy to determine, this is not a problem. However, it is. In this particular case, I needed to look at two characters to determine what to do next, the current character and the previous character. To look at both of these requires a state change, one which I don't always want to happen. It took a while to fully diagnose this issue and I tried about 5 different ways until I found one which fixed it.

I implemented Unicode differently. For this, I used a design pattern known as a sentinel, which helps me cross-cut pointcutting concerns by instantiating objects which encapsulate the state of the parser [Enough OO jargon for you?]. I never mutate these, and the program is purely functional except for the use of make (which could trivially be changed into a less efficient map [ ] subset, sacrificing efficiency and some terseness but making it functional). Writing this code was practically error-free, and the errors that existed could easily be diagnosed and fixed. I always sorta knew in my mind that it's better to write programs in a functional style than an imperative style, but this really proved it to me. Here's the code for decoding UTF-16LE.

TUPLE: new ;
TUPLE: double val ;
TUPLE: quad2 val ;
TUPLE: quad3 val ;

: bad-char CHAR: ? ;

GENERIC: (utf16le) ( char state -- state )
M: new (utf16le)
    drop <double> ;
M: double (utf16le)
    over -3 shift BIN: 11011 = [
        over BIN: 100 bitand 0 =
        [ double-val swap BIN: 11 bitand 8 shift bitor <quad2> ]
        [ 2drop bad-char , <new> ] if
    ] [ double-val swap 8 shift bitor , <new> ] if ;
M: quad2 (utf16le)
    quad2-val 10 shift bitor <quad3> ;
M: quad3 (utf16le)
    over -2 shift BIN: 110111 = [
        swap BIN: 11 bitand 8 shift
        swap quad3-val bitor HEX: 10000 + , <new>
    ] [ 2drop bad-char , <new> ] if ;

: utf16le ( state string -- state string )
    [ [ swap (utf16le) ] each ] { } make ;

If you're still reading my blog at this point, I'm genuinely impressed that you put up with such a boring series of posts.

Factor's make

One of the more unique features of Factor is a word called make. It's used for generating sequences easily where it wouldn't work to use a literal, a sequence initializer, or something that operates on an existing sequence. In its simplest form, make can be used like

[ 1 , 2 , 3 , ] { } make

which is equivalent to { 1 2 3 }. The word , appends the top of the stack to an invisible array, which is outputted at the end. Of course, , can be used in a loop, and you can even call another word to add elements to the loop. For example,

: add-all ( seq -- ) [ , ] each ;
[ 3 add-all 4 add-all ] { } make

which generates { 0 1 2 0 1 2 3 }. [Note: this takes advantage of a curious property of Factor, that numbers themselves are sequences representing the range 0..n-1] add-all turns out to be a pretty useful word, so it's actually included in the Factor standard library under the name % (with a more efficient implementation). So the previous code could be rewritten [ 3 % 4 % ] { } make. These names may seem obscure at first, but you'll get used to them quickly.

The importance of this is that, with make, you can do many complex things in constructing sequences that would be much more annoying when explicitly passed around. An example of this is take-until, defined with the imperative parsing code in previous entries and make as:

: take-until ( quot -- string )
    #! Take the substring of a string starting at spot
    #! from code until the quotation given is true and
    #! advance spot to after the substring.
    [ [
        dup slip swap dup [ get-char , ] unless
    ] skip-until ] "" make nip ;

Here's another example: say you want to write a function that takes a number and outputs the string "The answer to [whatever the number is] squared is [the number squared].". Factor doesn't require complicated string interpolation or inefficient multiple concatenations as other languages would; instead, it uses make. The word # converts a number to a string and then appends it to the current product of make. The code is below:

: square-description ( num -- )
    [
        "The answer to " %
        dup #
        " squared is " %
        sq #
        "." %
    ] "" make ;

When used in this way, "" make turns out rather like the C function sprintf. In other cases, like most uses of { } make, it ends up acting as a substitute for Lisp's ` (quasiquote).

make isn't any sort of magical builtin; it's actually implemented in very simple Factor code. It is in the vocabulary namespaces and defined as such:

: make ( quot exemplar -- seq )
    >r [
        V{ } clone building set
        call
        building get
    ] with-scope
    r> like ; inline

In English, all that does is make a new empty vector, place it in the building variable (which is dynamically scoped), call the given quotation, retrieve the variable, and convert the contents to the given exemplar. It operates inside a new scope so any outside definition of building is unchanged, and make's value for it is invisible after the word is run.

Obviously, something's missing: how do elements get on this new sequence? The answer is that , puts them on. Its implementation is even simpler than that of make:

: , ( elt -- ) building get push ;

and that is basically all there is to make

Update: That's not all, folks! There's also a way to push a whole sequence, all at once, onto the building. How? Using a word cryptically called %:

: % ( seq -- ) building get push-all ;

The push-all word is an in-place append.

Imperative parsing with abstractions

Here's somewhat of a confession: after writing a non-trivial library centered around parsing, I still know nothing about parsing strings. My attempts to wrap my head around what exactly an LALR(1) parser is and any little basic aspect of the theory of parsing have been in vain. I still struggle with using simple parser combinators (like the ones doublec has created).

So for my XML library, I created my own system of parsing which may or may not be original or useful. All of the below examples cah be run, in Factor, by requiring the module libs/xml and USEing state-parser. The source code can be found in the Factor distribution in libs/xml/state-parser.factor.

This way of parsing evolved very slowly. At first, it was just something like this:

SYMBOL: code
SYMBOL: spot
: get-char ( -- char )
    spot get code get nth ;
: next ( -- )
    spot inc ;

I used variables instead of the stack because a lot of the code, which processed this, didn't care about the code or spot. Really, only those two words care. This is the basis for a bunch of abstraction that I can build on it later, for example the combinator skip-until, the basic form of which is below:

: skip-until ( quot -- ) ! quot: ( -- ? )
    [ call ] keep swap [ drop ] [
        next skip-until
    ] if ; inline

This calls next until the quotation returns something other than f. It turned out to be really useful in parsing, allowing further devices to be built on top of it easily, like take-until, which does the same thing but records the characters skipped. From this, something like take-char is simple to write. This word skips the parser until the specified character is reached, and returns the string passed:

: take-char ( char -- string )
    [ dup get-char = ] take-until nip ;

After building abstractions like this, I was able to build a parser for XML relatively painlessly. The parser itself is in libs/xml/tokenize.factor, and it does no string operations directly at all. I think it is a type of recursive decent parser, but I'm not sure.

Because of this abstraction, I was able to change the inner workings of next and get-char twice, the first time to add information about the line and column of any errors encountered, and the second time to operate on streams instead of strings. This didn't require any changes at all to tokenize.factor. I'm planning on changing it again, but still, only a few of these basic, underlying words will be affected, and higher-level code will not be changed.

I've heard people say that it's tough to write a parser by hand. This was probably simpler than it could have been because of the relative simplicity of XML's grammar. This isn't really a Factor-specific solution, just something in general: with significant abstraction, and the ability to write higher-order functions, I don't think anything is too dificult to do "by hand" in an adequate programming language.



------
PS. To those of you who commented on this blog and I never responded: Sorry; I didn't really expect anyone to read this blog so I never checked it for comments. To Sam, about the combinators: Your implementation might work, but it won't compile in Factor's current implementation. In designing the XML parser and associated utilities, speed was a concern, and that means letting as much as possible compile. This particular thing doesn't work because you are manipulating quotations at runtime. In general, the word curry is good for that, and should probably be used in this case.

To Ray Cromwell, I know Google didn't really drop its API, but it's not issuing any new keys for the SOAP API, so as far as I'm concerned, that's gone. As far as the new AJAX API, I was under the impression that that can only be accessed client-side, so for all applications that want to do something like remove the ads or analyze rankings, it doesn't work.

XML combinators

I really need to work on making my writing make sense, because I think my last post failed at that. The XML library that I've written has a lot of combinators defined for processing, and in this blog post, I'm going to try to describe them as well as I can.

The basic idea behind the XML combinators is to let XML be processed the same way Lispers (and Factorers) have always processed lists and other sequences: with map each find subset and now,inject. These operations are slightly more complicated when used with a tree structure like XML, rather than a flat sequence as the operations were originally designed for. Fortunately, Factor's generic word system makes this relatively easy.

There's one consideration necessary in designing these that I wasn't happy with: since I had to iterate over all nodes, not just the leaf nodes. In all combinators, the result can be affected by which order is used. I made a relatively arbitrary decision and said that first the parent nodes were processed and then the leaves.

A note before the code of xml-each, the simplest of the combinators: this uses Factor's generic words, which dispatch only on the top of the stack. xml-each must dispatch on the class of the XML tag, not the quotation. However, the Factor convention for combinators is that the quotation is on the top of the stack, because this looks better syntactically. So I need to do a swap before entering the generic word. That said, here's the combinator:

GENERIC: (xml-each) ( quot tag -- ) inline
M: tag (xml-each)
    [ swap call ] 2keep
    tag-children [ (xml-each) ] each-with ;
M: object (xml-each)
    swap call ;
M: xml-doc (xml-each)
    delegate (xml-each) ;
: xml-each ( tag quot -- ) ! quot: tag --
    swap (xml-each) ; inline

The rest of the combinators are implemented in much the same way, with only trivial changes to make different ones. Unlike some combinators (see my previous post) this is very simple to implement, not in small part because I have existing combinators to help. (Unfortunately, it doesn't seem to be possible to abstract a general "lift" combinator (analogous to liftM in Haskell for monads) to turn each into xml-each and map into xml-map, despite the similarities between them).

A really simple usage of xml-each is [ write-item ] xml-each, which prints out each element of the given XML tag, document, or other type of element.

As a more in-depth example, xml-find (which works just like find, but without returning an index) is used to implement the equivalent of .getElementByID(), called get-id:

: get-id ( tag id -- elem )
    swap [
        dup tag? [
            "id" prop-name-tag
            [ string? ] subset concat
            over =
        ] [ drop f ] if
    ] xml-find nip ;

(Note: one weakness of the XML utilities that currently exist is that it's annoying to deal with XML tag attributes, though this should be fixed when I do more real work using them)

Designing combinators in Factor

Factor's a great programming lanugage, but one of the more annoying points of Factor is that it can be difficult to write complicated combinators, the Factor/Joy term for higher order functions. Here's one that I wrote recently. See if you can tell what it does:

: map-replace ( seq pred map -- )
    pick dup length [ ! ( seq pred map elt i )
        >r swap >r rot >r ! ( pred elt | seq map i )
        [ swap call ] 2keep rot ! ( pred elt ? | seq map i )
        [
            r> r> swap >r rot >r ! ( elt map | pred seq i )
            [ call ] keep ! ( new-elt map | pred seq i )
            r> r> r> rot >r rot >r ! ( new-elt seq i | map pred )
            swap [ set-nth ] keep ! ( seq | map pred )
            r> r> swap ! ( seq pred map )
        ] [
            drop r> swap r> r> drop ! ( seq map pred )
        ] if
    ] 2each 3drop ; inline

I showed this code to Slava Pestov, the creator of Factor, and he didn't understand it. This is ridiculously illegible, and the funny part is, it only has five words that actually *do* anything, and the rest just move stuff around the stack. I put these words in bold and italics.

This code looks complicated but it actually does a pretty simple thing. Given a mutable sequence, this code takes two quotations, a predicate and a map. On each element, the predicate is applied to the element. If the result is not f, the map quotation is run with the element, and that value is put in the place where the element used to be. An example of this is

{ 1 2 3 } dup [ 2 = ] [ 3 + ] map-replace .

which outputs { 1 5 3 }. I wrote this up as part of some code to change XML code in place, as a supplement to xml-map, which makes a new tree entirely.

To simplify this, I wrote a new combinator which takes only one quotation. This quotation is run on the element. If the result is f, nothing happens to the element. But if it is something else, the item is set to the resulting value. This can be written as:

: map-replace2 ( seq quot -- )
    over dup length [ ! ( seq quot elt i )
        >r rot >r swap [ call ] keep ! ( result quot | seq i )
        swap [ ! ( quot result | seq i )
            r> r> swap [ set-nth ] keep ! ( quot seq )
        ] [ ! ( quot | seq i )
            r> r> drop ! ( quot seq )
        ] if* swap
    ] 2each 2drop ; inline

In the end, it turned out all of this was almost completely pointless. Apparently, the Factor standard library already has a word called inject, which is like map, except it works in place. This is basically what I wanted all along, I was just making the mistake of premature optimization, shying away from setting each element individually because I thought it'd be too costly. inject is defined as

: inject ( seq quot -- )
    over length [
        [ -rot change-nth ] 3keep
    ] repeat 2drop ; inline

Using inject, Slava implemented my first map-replace as

: (map-replace) ( pred quot elt -- newelt )
    [ -rot slip ] keep rot [ swap call ] [ nip ] if ;

: map-replace ( seq pred quot -- )
    rot
    [ pick pick >r >r (map-replace) r> r> rot ] inject
    2drop ;

but at this point, it looks like like inject will be enough by itself. Now, going back to the original purpose, it is really simple to lift this to operate on XML trees rather than just sequences. xml-inject now joins the existing combinators xml-each xml-map and xml-find, all of which were very simple to implement given the existing parallel combinators on sequences:

GENERIC: (xml-inject) ( quot tag -- ) inline
M: tag (xml-inject)
    tag-children [
        swap [ call ] keep
        swap [ (xml-inject) ] keep
    ] inject ;
M: object (xml-inject) 2drop ;
M: xml-doc (xml-inject) delegate (xml-inject) ;
: xml-inject ( tag quot -- ) ! quot: tag -- tag
    swap (xml-inject) ; inline

Update: Note that in the current version of factor, inject is called change-each. Also, when writing new combinators now, it's very often useful to include a new word called curry, which I described here.