ささださんの日記のツッコミではあまり長くなるのも何だったので
書かなかったのですが、mutable/immutableの議論には、言語仕様
レベルと実装レベルの2つのレイヤがあります。
プログラミングスタイルに影響を与えるのは主として前者、
実行効率に関しては後者ですね。

実装レベル、というのは、言語で扱う文字列オブジェクトがCのように
直接文字列の実体を指しているか、文字列の実体は別にあって
文字列オブジェクトはそこへのポインタでしかないか、という
違いです。後者の戦略を取る場合、言語としての文字列がmutableであっても、
実体はimmutableになっている、ということが有り得ます。

以下、実装レベルと言語設計レベルで分けて議論します。


実装レベル
=========


実体を別に持つ場合、異なる実装がいくつか考えられます。

[fix] 固定長文字の配列 (e.g. UCS-4の配列)
[var] 可変長文字の配列 (e.g. マルチバイト文字列、UTF-16の配列)
[lis] 文字オブジェクトのリスト
[tre] 短い文字配列をリーフに持つ木

これらについて、それぞれ実体がmutableなものを/m, immutableなものを/i
と表記し、典型的な文字列操作について定性的な比較をするとこんな感じでしょうか。

----------------------------------------------------------------

        逐次    添字   連結   1変更   N変更   検索   部分     N変更・再構築

fix/m    ◎     ◎     ×     ◎     n/a     ◎     ×        ×
fix/i    ◎     ◎     ×     n/a    n/a     ◎     ◎        ×
var/m    ○     ×     ×     n/a    n/a     ◎     ×        ×
var/i    ○     ×     ×     n/a    n/a     ◎     ◎        ×
lis/m    ◎     ×     ×     ×     ×      ○     ×        ×
lis/i    ◎     ×     ×     n/a    n/a     ○     ×(*1)    ×
tre/m    ○     △     ◎     △     △      ○     △        △
tre/i    ○     △     ◎     n/a    n/a     ○     ◎        ◎


操作：

   逐次:各文字への逐次アクセス       添字:文字インデックスによるアクセス
   連結:連結による文字列作成        1変更:1文字のみの(長さを変えない)変更
   N変更:N文字の(長さを変える)変更   検索: 部分文字列検索
   部分:部分文字列の取り出し         
   N変更・再構築: 長さを変える変更を、新たな文字列構築として行う

評価：
   ◎:  C・O(n)、小さめのC
   ○:  C・O(n)、大きめのC
   △:  O(log(n))
   ×:  O(n)
   n/a: 操作そのものが不可能

  (*1) 末尾を共有する文字列の場合◎、その他の場合×

----------------------------------------------------------------

どれが良いかはどの操作を多用するかによるのですが、文字列の長さを
変えない変更というのは現実的にあまり無いのではないか、と思います。
(例外はあらかじめ固定長配列をアロケートしておいてそれを埋めて行く
場合だが、それは逐次文字列構築と考えられる)。
特にUnicodeサポートを考えると、単純なcase foldingだって長さが
変わり得るので。従って、文字列の変更コストは「N変更・再構築」を
考えるべきでしょう。

とすると、どの方式も文字列実体をmutableにするメリットはあまりない
ということがわかります。特に、古典的な「固定長配列、mutable」という
実装は固定長変更を取ったら何も良いことがない。可変長変更を重視
するなら「木構造、immutable」、添字によるアクセスを重視するなら
「固定長配列、immutable」が有利です。可変長配列は固定長配列に
劣りますが、マルチバイト表現の場合、既存のライブラリやシステムコール
との親和性が高いという利点があります。


言語設計レベル
============

さて、言語使用者からすればこんな実装の詳細は気にしたくないわけです。
しかし文字列をブラックボックスとして扱った場合、上記のように実装に
よって操作にかかるコストが違いすぎる。だとすれば、実装による
差異がなるべく出にくいような抽象化ができるとベター、ということに
なります。

そういう視点からすれば、言語レベルでの文字列の変更を許す設計は
個人的にはやや不利だと思います。コストが低くなるわけではないのに、
1文字1バイト時代の固定長配列モデルが頭にあるプログラマにとってはコストが
低いと勘違いさせる要因になるからです。常に新しいインスタンスが生成
されると覚悟していればプログラマもあまり無茶はしないでしょう。

それでも変更を許したければ、処理系は単純な配列以上の実装を提供すべき
だと思います。木構造なら、 ループ内で s += "hoge" みたいなことを
やられてもたいして痛くありません。
(Ray Dillingerがテキスト処理を重視したSchemeでそういう実装を
採用しているそうです)。

もうひとつ、文字インデックスによるアクセスも、私は固定長配列時代の
悪習だと思います。逐次アクセスのイテレータと、検索/部分文字列取り出し/置換
のプリミティブがあればインデックスアクセスはほとんどの場合不要に
なるんではないかと思います (suffix array等を言語レベルで実装
したい場合に配列モデルが必要になるケースは考えられますが…)

--shiro

--
ML: yarv-dev quickml.atdot.net
使い方: http://www.atdot.net/~ko1/quickml