プログラミング言語における文字列

プログラミングにおいて文字列 (string) 型は課題であり続けた。

• 文字列の内部表現は何か？　ASCII で5文字の文字列や、日本語で5文字の文字列は、どれほどメモリを消費するか？
• 文字列の個々の要素は可変か？
• 文字数の計算はどのように取得できるか？　その計算コストは？
• プログラミング言語処理系が定義する文字列の扱いをよく理解せず、普通にコーディングしたとき、ちゃんと特殊な文字も正しく処理してくれるか？　どこを注意しなければならないか？

古くからの文字列の歴史を調べることはしない。簡単に代表的ないくつかのプログラミング言語について、まとめる。

Unicode

Unicode の長い歴史については語らず、今回の話で関係することだけを語る。

Unicode は世界中のすべての文字を表現できることを試みた文字コード規格である。エンコーディング形式としては、UTF-8, UTF-16, UTF-32 の３種類を定義している。それぞれコードユニット（文字を表現するのに使われる最小限のビット列単位。参照: Glossary - Unicode）が異なっていて、UTF-8 は1バイト、UTF-16 は2バイト、UTF-32 は4バイトとなっている。

UTF-8 は1バイトのコードユニットで、ASCII の上位互換のエンコーディング形式である。ASCII の範囲は1バイトで、ASCII と同一の文字コードによって表現される。ASCII の範囲外は2-4バイトで表現される（本当は5-6バイトでの表現も定義されているがこれは Unicode 範囲外）。１文字の長さが可変であるため、文字数はコードユニット数と別に計算する必要があるし、インデクシングの計算コストも O(n) になる（ASCII 範囲内の文字列だと分かっていれば、コードユニット単位でインデクシングして O(1) になる最適化をしている実装はある）。現状、世界のファイル形式としてもっともよく利用されている。

UTF-16 は2バイトのコードユニットで、多くの基本的な文字が2バイトで表現される。それ以外の文字はサロゲートペアというコードユニット２つ、すなわち4バイトで表現される。たとえば “😆” という絵文字はサロゲートペアで表現される文字の例になる。UTF-16 が危険なのは、「多くの基本的な文字」はコードユニットごとに１文字なので、コードポイント単位と文字単位を同一視して扱ってしまっても「基本的には」問題にならず、結果的にそのままリリースしてしまいがちなことだ。ASCII 範囲内の文字列を表現する場合は UTF-8 の２倍の保存領域を消費してしまうが、ASCII 範囲外の文字列を表現する場合は UTF-8 と同等くらいか UTF-16 よりも保存領域を消費しないですむ。また、「サロゲートペアを無視すれば」、コードユニットの数がそのまま文字数になる単純性もある。

UTF-32 は4バイトのコードユニットで、すべての文字が4バイトで表現される。コードユニット単位と文字単位は同一なので、文字の扱いで問題が発生することはない。ただし、ほとんどの文字列で UTF-8, UTF-16 より保存領域を消費してしまい、特に ASCII 範囲内の文字列については UTF-8 の４倍である。

Unicode についてきちんと考えると、結合文字、異体字セレクタ、ゼロ幅接合子などの特殊な話があって、それも含めると文字の扱いはより難しいが、その話は今回取り扱わない。

C, C++

C言語の文字列 char[] は、単純な可変なバイト配列である。C言語の文字列は特殊なヌル文字 \0 で終端するルールになっており、\0 までの文字数を数えることで文字列長を計算できる。可変といったが、リテラル文字列は immutable である。

• 文字列の内部表現: バイト列 (エンコーディングは自由だが現実的には UTF-8)。ただし終端を指す \0 の1バイトも必要となる。
• 文字列の可変性: 可変。
• 文字数: 終端を指す \0 までの文字数を計算する。ASCII の範囲であれば単純にバイト数を計算すればよいし（strlen()）、UTF-8 の範囲であれば UTF-8 エンコーディングの仕様に従ってマルチバイト文字も正しく計算すればよい。そのため n をバイト数または文字数とすれば O(n)。
• 文字列の扱い: バイト列でしかないため、要素アクセスも文字数計算も注意が必要。

ただ C は、そもそもライブラリ側が char[] でなく wchar[] を利用していたり、文字列長も保持した独自の構造体型を作っていたりすることも多い。wchar は2バイトまたは4バイトになるため、現実的にはエンコーディングは UTF-16 または UTF-32 になる。UTF-16 の場合はサロゲートペアの扱いに注意しないといけないし、UTF-32 の場合はさすがに通常のユースケースでは無駄にメモリを食いすぎる。また、プラットフォームによって wchar が2バイトになるか4バイトになるか異なる時点で、まともにクロスプラットフォームで扱える型でない。

現代において C, C++ はナイーブに利用されるような言語でなくなっているので、利用するときは文字列の扱いについては自己責任でいいだろうと思う。

Java, Kotlin

Java の文字列は、不可変な UTF-16 文字列である。Java 8 までは内部的にも特に最適化は施されていない。通常の要素アクセスや文字列長のメソッドは、単に16ビットのコードユニットごとに１つの要素として扱うため、サロゲートペアの問題が発生する。正しく文字数を計算するには str.codePointCount(0, str.length) を使う。正しく文字列を文字の列として扱うには str.codePoints() を使う。

fun main() {
    val s = "こんにちは😆"
    println(s)
    println("s.length(): "  + s.length)
    println("s.split(\"\"): " + s.split(""))
    s.forEachIndexed { i, c -> println("s[" + i + "]: " + c) }

    println("s.codePointCount(): " + s.codePointCount(0, s.length))
    s.codePoints().forEach { c -> println("s.codePoints(): %c".format(c)) }
}

// こんにちは😆
// s.length(): 7
// s.split(""): [, こ, ん, に, ち, は, ?, ?, ]
// s[0]: こ
// s[1]: ん
// s[2]: に
// s[3]: ち
// s[4]: は
// s[5]: ?
// s[6]: ?
// s.codePointCount(): 6
// s.codePoints(): こ
// s.codePoints(): ん
// s.codePoints(): に
// s.codePoints(): ち
// s.codePoints(): は
// s.codePoints(): 😆

Java 9 (2017) からは、Compact Strings という内部的な最適化が実装されている。Java 9 からの文字列は、不可変なバイト配列とエンコーディング情報からなる。文字列の中身が Latin-1 （ASCII の拡張）の範囲内であれば１バイト１文字の Latin-1 としてバイト配列に格納することで、以前よりコンパクトに保存される。文字列の中身が Latin-1 の範囲を超えていれば１バイト２文字（サロゲートペア除く）の UTF-16 としてこれまで通りバイト配列に格納する。後述するが、Python は Java より早く、かつ UTF-32 まで対応してサロゲートペア問題をなくした形で、同様のことを実現している。

C#, F#

C# や F# の基盤である .NET の文字列は、Java と同じで不可変な UTF-16 文字列である。

open System

let s = "こんにちは😆"
Console.WriteLine("s.Length: {0}", s.Length)
Console.WriteLine("s.ToCharArray(): {0}", String.Join(", ", s.ToCharArray()))

let info = new Globalization.StringInfo(s)
Console.WriteLine("info.LengthInTextElements: {0}", info.LengthInTextElements)

let e = Globalization.StringInfo.GetTextElementEnumerator(s)

while e.MoveNext() do
    Console.WriteLine("e.GetTextElement(): {0}", e.GetTextElement())

// s.Length: 7
// s.Split(): String[]
// e.GetTextElement(): こ
// e.GetTextElement(): ん
// e.GetTextElement(): に
// e.GetTextElement(): ち
// e.GetTextElement(): は
// e.GetTextElement(): 😆

特に Java (JVM) と変わらない。Compact Strings については issue で議論されているが、現状では実装されていないみたいだ。それとは別に UTF8String 型を導入しようという話が進んでいるが、UTF8String 型は string 型と互換性があるわけでないので（同じようなインタフェースは持つが、.NET は structural typing でないから、string 型を要求するところに UTF8String 型を渡すことができない）、あまり嬉しい話でもない。

JavaScript, TypeScript

JavaScript の文字列は、Java 同様に不可変な UTF-16 文字列であり、16ビットのコードユニットごとに１つの要素として扱う。JavaScript は名前ほど Java っぽい言語ではないが、この点についてだけは Java の問題をそのまま引き継いでいる。Chrome や Node.js で採用されている JavaScript 処理系 V8 では、内部的な最適化をかなり施して多様な文字列型を実装しており、その中には Python や Java の Compact Strings のような最適化も含まれるようだ。

ECMAScript Language Specification: 6.1.4 The String Type:

The String type is the set of all ordered sequences of zero or more 16-bit unsigned integer values (“elements”) up to a maximum length of 2^53 - 1 elements. The String type is generally used to represent textual data in a running ECMAScript program, in which case each element in the String is treated as a UTF-16 code unit value.

ECMAScript operations that do not interpret String contents apply no further semantics. Operations that do interpret String values treat each element as a single UTF-16 code unit. However, ECMAScript does not restrict the value of or relationships between these code units, so operations that further interpret String contents as sequences of Unicode code points encoded in UTF-16 must account for ill-formed subsequences. Such operations apply special treatment to every code unit with a numeric value in the inclusive range 0xD800 to 0xDBFF (defined by the Unicode Standard as a leading surrogate, or more formally as a high-surrogate code unit) and every code unit with a numeric value in the inclusive range 0xDC00 to 0xDFFF (defined as a trailing surrogate, or more formally as a low-surrogate code unit) using the following rules:

• A code unit that is not a leading surrogate and not a trailing surrogate is interpreted as a code point with the same value.
• A sequence of two code units, where the first code unit c1 is a leading surrogate and the second code unit c2 a trailing surrogate, is a surrogate pair and is interpreted as a code point with the value (c1 - 0xD800) × 0x400 + (c2 - 0xDC00) + 0x10000. (See 11.1.3)
• A code unit that is a leading surrogate or trailing surrogate, but is not part of a surrogate pair, is interpreted as a code point with the same value.

const s = "こんにちは😆"
console.log("string: " + s);
// "string: こんにちは😆"
console.log("length: " + s.length);
// "length: 7"
console.log("split: " + s.split(''));
// "split: こ,ん,に,ち,は,�,�"
for (let i = 0; i < s.length; i++) console.log("s[" + i + "]: " + s[i]);
// "s[0]: こ"
// "s[1]: ん"
// "s[2]: に"
// "s[3]: ち"
// "s[4]: は"
// "s[5]: �"
// "s[6]: �"

for (let c of s) console.log("for: " + c);
// "for: こ"
// "for: ん"
// "for: に"
// "for: ち"
// "for: は"
// "for: 😆"
console.log("[...s]: " + [...s]);
// "[...s]: こ,ん,に,ち,は,😆"
console.log("[...s].length: " + [...s].length);
// "[...s].length: 6"

文字数の計算方法は、String length - MDN などを見ると [...str].length という方法が紹介されている。ただこれは文字列を Unicode 文字の配列に分解生成してその長さを計算しており、配列生成のメモリコストがかかるのでないかというのが気になる。JavaScript 処理系によってはそこは最適化されているかもしれないが、そうでない場合、Go における utf8.RuneCountInString(string) int のような関数が必要なんじゃないかと思える。

Common Lisp

HyperSpec によれば、Common Lisp の文字列とは文字のベクタ（１次元配列）である。ベクタであるため、文字を変更することはできるが、文字数が変わるような変更はできない。「文字」が Unicode 全文字を指しているのか UTF-16 コードポイントなのか ASCII 文字なのかは実装依存だが、ここでは、活発に開発されていてネイティブコードコンパイルする高速な Common Lisp 実装 SBCL を対象とする。

(defvar s "こんにちは😆")
(length s)
;; 6
(dotimes (i (length s)) (print (char s i)))
;; #\HIRAGANA_LETTER_KO
;; #\HIRAGANA_LETTER_N
;; #\HIRAGANA_LETTER_NI
;; #\HIRAGANA_LETTER_TI
;; #\HIRAGANA_LETTER_HA
;; #\SMILING_FACE_WITH_OPEN_MOUTH_AND_TIGHTLY-CLOSED_EYES
(setf (char s 4) #\わ)
s
;; "こんにちわ😆"

Character and String Types | SBCL によれば、現在の SBCL は Unicode 全文字に対応している。

Objects of type simple-base-string have the header word with widetag, then a word for the length, and after that a sequence of 8-bit char-code bytes. The system arranges for there to be a null byte after the sequence of lisp character codes.

Objects of type (simple-array character (*)), where this is a distinct type from simple-base-string, have the header word with widetag, length, and then a sequence of 32-bit char-code bytes. Again, the system arranges for there to be a null word after the sequence of character codes.

(simple-array character (*)) というのは simple-string のことで、通常の文字列（char の simple-array）はこれになる。一方、simple-base-string は base-char の simple-array であり、base-char というのは8ビット範囲内の文字である。ただ普通に文字列を作ると、ASCII （8ビット）範囲内だとしてもそれは Unicode 文字列になる。ASCII シンボルを文字列化したりすると、simple-base-string が登場する。

(type-of "foobar")
;; (SIMPLE-ARRAY CHARACTER (6))
(type-of (symbol-name :foobar))
;; (SIMPLE-BASE-STRING 6)

Common Lisp にしても Scheme にしても、文字列が可変な文字ベクタであることが足を引っ張っているように思われ、不可変であれば CPython のような実装にもできた。

Scheme

Scheme の文字列は、R7RS によれば文字のシーケンスである。Common Lisp 同様、文字を別の文字の変更することができる。ただし R7RS ではリテラルや symbol->string の返り値は immutable な可能性があるとあり、すべての文字列が mutable なわけではない。R7RS では「文字」の定義は Common Lisp 同様に実装依存だが、Gauche では通常（コンパイル時に別エンコーディングにもできるが）UTF-8 を内部表現として Unicode 全文字に対応する。

(define s "こんにちは😆")
(string-length s)
;; 6
(string-for-each (lambda (c) (display c) (newline)) s)
;; こ
;; ん
;; に
;; ち
;; は
;; 😆
(string-set! s 5 #\わ)
;; *** ERROR: attempted to modify an immutable string: "こんにちは😆"

(define a (make-string 5 #\😆))
(string-set! a 3 #\😁)
;; "😆😆😁😆😆"

Gauche の文字列表現については 文字列について | Gauche に詳しい。大昔にこの文書を呼んで、わたしは納得したし強い影響を受けた。これで R*RS が文字列を immutable にしていれば、よかったのだが。

Pharo Smalltalk

Pharo Smalltalk では、文字列 String は ArrayedCollection のサブクラスである。String は ByteString と WideString（と Symbol）というサブクラスがあり、１バイトの範囲内であれば ByteString になり、そうでなければ WideString になる。WideString は Unicode 全文字に対応しており、内部表現は String variableWordSubclass: #WideString ... というクラス宣言から類推すると、ワード配列なんだろうと思う。つまり64ビット環境では、1文字64ビットの可能性がある……。文字列は通常 mutable だが、リテラル文字列は immutable である。

s := 'こんにちは😆'
s size "6"
s asArray "{$こ. $ん. $に. $ち. $は. $😆}"

s class "WideString"

s at: 5 put: $わ "ModificationForbidden"

t := 'foobar' "'foobar'"
t class "ByteString"

u := String new: 5
u at: 1 put: $f
u "'f    '"
u class "ByteString"
u at: 2 put: $あ
u class "WideString"

u 変数について試している箇所はほかのプログラミング言語では見られない挙動をしており、最初 ByteString クラスだったオブジェクト u が、ASCII 範囲外の文字をセットすることで WideString クラスに置き換わっている。Smalltalk に become: メソッドのような強力なメタプログラミング機能を有することは有名だが、ここでそんなことが行われているのはやりすぎにも思える。文字列が mutable だと面倒な話にしかならないことの証左。

Python

Python の文字列は Unicode 文字列で、内部表現としては最適化が施されていて単純でないが、ともかく現在はサロゲートペアも正しく扱ってくれる。Python 文字列は不可変であるため、すべての文字が8バイトで表現できる範囲であれば UCS1 (UTF-8) で、すべての文字が16バイトで表現できる範囲であれば UCS2 (UTF-16) で、そうでなければ UCS4 (UTF-32) で保存されている、というのが今の CPython の実装だったかと思う（3.2 までの CPython は、ビルド時点で UTF-16 か UTF-32 に決め打ちだった時代があった。UTF-16 でビルドされていれば、サロゲートペアの扱いが JavaScript と同様だった）。利用者は何も気にせず UCS4 (UTF-32) で保存されていると思って扱えばよい。しかし最適化されているため、ただの ASCII 文字列はメモリを食わないので安心できる。

s = "こんにちは😆"
print(s)
# こんにちは😆
print(len(s))
# 6
print(list(s))
# ['こ', 'ん', 'に', 'ち', 'は', '😆']
for i in range(0, len(s)): print('s[{}]: {}'.format(i, s[i]))
# s[0]: こ
# s[1]: ん
# s[2]: に
# s[3]: ち
# s[4]: は
# s[5]: 😆

Ruby

Ruby の文字列は、可変であり、かつ、文字列オブジェクトごとに自身のエンコーディング情報を持っている。通常は、デフォルト UTF-8 エンコーディングになっており、もちろん１文字の長さはまったく統一されていないため、インデクシングのオーダーが O(1) でなく O(n) になるはずだが、それは現実的な問題にはなりづらいとして許容されていると思う。文字列長（＝文字数）自体は毎回計算しているのでなく、あらかじめ計算しておいた文字数をフィールドに保存しているはず。デフォルト以外のエンコーディングを扱うのはちょっと別の話かつ多分別の複雑さが出て来るので、ここでは無視する。

s = 'こんにちは😆'
puts(s)
# こんにちは😆
puts(s.length)
# 6
puts(s.encoding)
# UTF-8
p(s.split(''))
# ["こ", "ん", "に", "ち", "は", "😆"]
s.length.times { |i| puts("s[#{i}]: #{s[i]}") }
# s[0]: こ
# s[1]: ん
# s[2]: に
# s[3]: ち
# s[4]: は
# s[5]: 😆

Go

Go の文字列は、不可変の UTF-8 文字列である。len(s) や s[i] はバイト単位で扱うため注意が必要だが、Unicode 文字の配列である []rune に変換して処理したり unicode/utf8 ライブラリを利用したりすれば、正しく処理できる。特に for i, r := range s は Unicode 文字ごとにループして、現在のバイト単位の位置と現在の Unicode 文字を変数に代入する。「文字列 != 文字の配列」であるため注意が必要なのは JavaScript と同様。

package main

import (
	"fmt"
	"strings"
	"unicode/utf8"
)

func main() {
	s := "こんにちは😆"
	fmt.Printf("s: %s\n", s)
	fmt.Printf("len(s): %d\n", len(s))
	fmt.Printf("utf8.RuneCountInString(s): %d\n", utf8.RuneCountInString(s)) // len([]rune(s))
	fmt.Printf("strings.Split(s, \"\"): %v\n", strings.Split(s, ""))
	for i := 0; i < len(s); i++ {
		fmt.Printf("s[%d]: %x\n", i, s[i])
	}
	for i, r := range s {
		fmt.Printf("rune %d in s: %c\n", i, r)
	}
}
// s: こんにちは😆
// len(s): 19
// utf8.RuneCountInString(s): 6
// strings.Split(s, ""): [こ ん に ち は 😆]
// s[0]: e3
// s[1]: 81
// s[2]: 93
// s[3]: e3
// s[4]: 82
// s[5]: 93
// s[6]: e3
// s[7]: 81
// s[8]: ab
// s[9]: e3
// s[10]: 81
// s[11]: a1
// s[12]: e3
// s[13]: 81
// s[14]: af
// s[15]: f0
// s[16]: 9f
// s[17]: 98
// s[18]: 86
// rune 0 in s: こ
// rune 3 in s: ん
// rune 6 in s: に
// rune 9 in s: ち
// rune 12 in s: は
// rune 15 in s: 😆

Rust

Rust については全然知らないので今回調べてみただけで、詳細は間違っているかもしれない。Rust の文字列も Go の文字列と同様で、UTF-8 で表現される。str.len() はバイト列での扱いになるが、str.chars() によって Unicode 文字のイテレータ化をしてから操作すれば、正しく文字数や文字アクセスもできる。JavaScript の [...str] と違って返す型はイテレータなので、まともに実装されていれば変にメモリを消費することはない。通常の文字列である str は不可変だが、それとは別の std::string::String は可変である。主に、いわゆる StringBuilder 的な処理をするときに使われるようだ。

fn main() {
    let s = "こんにちは😆"; // &str
    println!("s: {}", s);
    println!("s.len(): {}", s.len());
    println!("s.split(\"\"): {:?}", s.split("").collect::<Vec<&str>>());
    for c in s.bytes() {
        println!("s.bytes(): {}", c)
    }

    println!("s.chars().count(): {}", s.chars().count());
    for c in s.chars() {
        println!("s.chars(): {}", c)
    }
}

// s: こんにちは😆
// s.len(): 19
// s.split(""): ["", "こ", "ん", "に", "ち", "は", "😆", ""]
// s.bytes(): 227
// s.bytes(): 129
// s.bytes(): 147
// s.bytes(): 227
// s.bytes(): 130
// s.bytes(): 147
// s.bytes(): 227
// s.bytes(): 129
// s.bytes(): 171
// s.bytes(): 227
// s.bytes(): 129
// s.bytes(): 161
// s.bytes(): 227
// s.bytes(): 129
// s.bytes(): 175
// s.bytes(): 240
// s.bytes(): 159
// s.bytes(): 152
// s.bytes(): 134

// s.chars().count(): 6
// s.chars(): こ
// s.chars(): ん
// s.chars(): に
// s.chars(): ち
// s.chars(): は
// s.chars(): 😆