文字列について

日本語を扱うことはGaucheの当初からの目標であった。それも、出来れば日本語に限らず、多国語対応にしたいなと。問題は実装だ。

固定長か可変長か

最近のScheme処理系の多くはUCS-2にも対応しつつある。 Unicodeで一応コードは決まっているし、固定長だし、一番簡単な解決法ではあるのだが、Gaucheの目的からみた場合に、色々と不都合もあるのだ。

ちゃんと多国語を扱うには、16bitじゃ足りなかろう。かと言って全てをUCS-4で扱うのは無駄が多すぎるよな。何と言っても、扱うデータの大部分は1バイトに収まるだろうし。サロゲートペアを導入してUTF-16として扱うとすると、固定長という最大のメリットが無くなってしまう。
I/O性能。数10MBくらいの、日本語がちょっとだけ混じったログファイルを読み込んで加工して書き出す、なんてことが私の業務では多発するんで、 I/Oの性能が気になる。データファイルは互換性やらなんやらで、おそらく将来に渡っても可変長エンコーディングで書かれているだろう。それを読み込む度に固定長エンコーディングに変換して、書き出す時にまた変換するのか?

また、基本的に文字列は1文字＝1バイト固定長であるとして扱い、そのオブジェクトをマルチバイト文字列として解釈するライブラリを別に作るという手もある。複数の漢字コード系の変換プログラムなんてのはこういう実装の方が作りやすいし、標準の関数は固定長を扱うように最適化できる。ただ、やっぱりstring-refで日本語が壊れずに扱えて欲しいというのが当初からの願望であるので、この方式は見送った。

そもそも、固定長で文字列を扱うメリットってなんだろか。インデックスでのアクセスがコンスタントタイムでできるってことは、そんなに重要だろうか。少なくとも私の環境では「1カラム目から5カラム目までは行番号」などというようなデータを扱うことはまず無い。文字列の中身を扱うのは、まずほとんどの場合、頭から一文字づつ取って来たり書き出す逐次アクセスか、検索をかけてそこから部分文字列を取り出したり置換したりするという処理である。

このうち、逐次アクセスについては、私はこれまでもstring-portを使って来た。 string-refだと1回毎にバウンダリチェックも入るわけで、それより内部に現在のポインタを持てるstring-portの方が速いでしょ、というわけだ。実際、STkではstring-portの方が速い。

検索にしても、どうせ返って来たインデックスをsubstringに渡すだけなのだったら対象となる部分文字列へのポインタをmatch objectとして返すようにした方が手っとり早い。 scshのmatch-condや、 textutils のrxmatchインタフェースはそういう発想で、インデックスは直接扱わなくても良いようにできる (必要ならばmatch objectから取り出せば良い)。

少なくともインデックスアクセスがコンスタントタイムで出来る、ということは実用上 (私の業務上) それほどメリットでは無いのだ。

逆に、可変長の表現にして困ることは何だろう。

文字列の破壊的操作が行なわれ、文字列長が変わってしまう場合。
(string-set! "ABC" 1 #\あ) ==> "AあC"
などの場合に、一文字だけ書き換えるというわけにはいかない。
文字列検索。最初から見てかないと文字境界が分からないようなエンコーディング (2バイト文字の2バイト目と次の2バイト文字の1バイト目とがvalidな文字を構成し得るような場合)だと、Boyer-Mooreなどの高速アルゴリズムが使えなくなる。 EUC-JPなんかはこれでダメ。UTF-8なら大丈夫か。
正しい文字列として解釈できないバイト列をどう扱うか。入力にはどんなバイト列が来るかもわからないし、また、コード変換系をScheme自身で書こうとしたら故意にそのようなバイト列を作成する必要が出て来る。

Gaucheでは、これらの弱点は以下に述べるような対応でカバー出来ると考え、可変長表現を採用した。必ずしも定量的評価をしたわけでは無いので、将来時間があれば固定長での実装もしてみてI/O性能など測ってみたくはある。

Gaucheでの文字列表現

Gaucheでの文字列は、文字数lengthと文字列のサイズ(バイト数)size を別々に保持している。文字列の実体は別にアロケートされて、ポインタstartが文字列の先頭を指す。そこからsizeバイト分がこの文字列の実体である。 NUL終端されているとは限らない。また、実体中にNULが入っていても良い。

文字列の実体はread onlyである。文字列への破壊的操作を行なうと、常に新しいメモリがアロケートされ、内容が(変更を伴って)コピーされ、 startが新しいメモリを指すように変更される。従って、最初にmake-stringで文字列をアロケートしてstring-set! で一文字づつ埋めて行くようなコードはものすごーく遅い。output string portを使うべし。

Read only storageという選択

一文字の変更であっても文字列全部をコピーする、というのは恐ろしげに聞こえるかもしれないが、そもそもstring-set!ってそんなに使わないだろうという目論見がある。 regexpでマッチした部分を置換するという使い方の方が多いだろうし、それならばいずれにせよコピーはするわけだ。

一方、文字列の実体をread onlyにすることには大きなメリットがある。部分文字列が実体を共有できるのだ。Boehm-GCのおかげで、実体のfree()に気をつかう必要もない。そして、少なくとも私の業務では、部分文字列を作成するという操作は非常に多い。regexpのsubmatchである。

これも定量的な評価をしたわけでは無いが、後者のメリットが前者のデメリットに優るのでは、というのが私の考えである。

不完全文字列

全てのバイト列が可変長エンコーディングとして正しく解釈できるわけではない。定義されていないコードポイントを指している場合はまだ可変長文字列として扱えるが、そのエンコーディングではどうにも解釈しようの無いバイトシーケンスというのが外部から入って来る可能性がある。

Gaucheではこのような文字列をincomplete stringと呼び、そのようにマークされる。文字列操作系の関数は、incomplete stringを可能な限りあたかも1バイト固定長文字列のように扱う。 incomplete stringとcomplete stringが接合された場合、結果はincomplete stringになる。これは次のような、少々驚くべき結果をもたらすかもしれない。

  ;; Suppose A is an incomplete string with length 8,
  ;; and B is a complete string with multibyte character.
  (string-length A) ==> 8
  (string-length B) ==> 4   ;; e.g. B == "あいうえ"

  (string-length (string-append A B)) ==> 16  ;; if B is in EUC-JP

incomplete stringはそのような文字列が外部から与えられた場合のほか、 string-byte-set! や output string port に write-byte することで故意に作成することもできる。コード変換系をSchemeで書く場合は使わざるを得ないだろう。

なお、length == size である場合とincomplete stringはともに 1バイト固定長なので、例えばstring-refはこれらのケースでは先頭からスキャンするのではなく配列参照を行なう。オーバヘッドは1〜2回の条件分岐のみなんで、扱う文字列の多くがこれらのカテゴリならば、可変長にしたペナルティはあんまり無いんじゃなかろうか、という、これも定量的な裏付けの無い期待なんだけど。

エンコーディングルール

内部エンコーディングはコンパイル時に選択する。新しいエンコーディングに適応させるためには、いくつかのマクロを定義すれば良い。効率の良い処理のために、いくつかの仮定を置いた。

1文字に使うバイト数の上限が定義できる
ASCII文字の範囲は常にASCIIコードで表現される
最初のバイトを見れば、全部で何バイト使うかわかる
1バイト文字は、2バイト以上を使う文字のどのバイトとも一致しない
文字に直した場合、29bit integerの範囲に収まる