コメント等は 掲示板 にどうぞ
lethevertさんに言及いただいた 「Java(のGenerics)は(DのTemplateと比べて)便利だなあ」発言 ですが、 そういえば、この記事書いた後ひとに突っ込みもらって、用語の選択ミス等々で伝えたいことを 上手く伝えられてなかったっぽいと気づいたことを今思い出しました。 というわけで、今頃になってフォロー記事を書いてみます。
件の Finger Tree でも使われてましたが、純粋関数型データ構造を作るときに頻出のテクニックの一つとして、 "Non-uniform type" / "Non-uniform recursion" ていうのがあります （Nested datatype とか Polymorphic recursion とか別の名前で呼ばれることもあります）。 あ、まずその前に、Non- じゃない "Uniform type" / "Uniform recursion" っていうのは要するにごく普通の再帰的なデータ型/再帰関数 のことです。たとえばツリーとか。
class Tree<E> { E data; Tree<E> left, right; }Treeの定義にTreeが登場してる…つまり再帰的な定義なんですが、 この再帰の時に型パラメタの部分はいっしょ （Tree<E> の定義には Tree<E> を使っている） なことを指して、uniform と呼ばれています。
さて、Non-uniform recursion というのは…もうおわかりだと思いますが、 型パラメタを変えながら再帰すること。 例えば、「キュー Queue<E> を実装するのに、 Queue<List<E>> を使うとすごい高速！」 というファンキーな技があります。 （c.f. このPowerPoint の"Bootstrapped Queue"あたり。前９章の内容前提な上に口頭で補足するの前提な資料なので わかりにくいですが。スミマセン）
// Java
class Queue<E> { ... Queue<List<E>> impl; ... }
// D
class Queue(E) { ... Queue!(List!(E)) impl; ... }
// C++
template<typename E>
class Queue { ... Queue< List<E> >* impl; ... }
でですね、これは、Java の Generics なら普通に何も考えず↑こう書けば実装できます。 一方で C++ や D の Template だと、できません。テンプレートを型パラメタ毎に別々に実体化 しないといけないので、Queue<int> を使うには Queue<List<int>> が必要で、 Queue<List<int>> を使うには Queue<List<List<int>>> が必要で、 Queue<List<List<int>>> を使うには…（以下略。無限のテンプレート実体が 必要になっちゃうからです。Java ならイレイジャでの実装なので、パラメタが違ってても実体は１つです。
※本当かな？と思って実際にC++やDで書いてみる人向け注意。
単に↑のように再帰的にimplというメンバを定義するだけだと、implは使われないので実体化もされず、
無限ループもしません。何かimplを使うメンバ関数
（例えば、bool empty() { return !impl || impl->empty(); } とかなんとか）
を適当に実装して呼び出してみるとコンパイルが止まらなくなって楽しい気分になれます。
追記： ちゃんとしたサンプルとして Java版 Booststrapped Queue を
実装 sub/BtsQ.java
（遅延評価してないのであんまり意味ないけど）しました。
これを C++/D に移植してみるとコンパイルが止まらなくなって楽しい気分になれます。
「型を変えて適当にキャストを挟み込む」とか「実際に実行時に使われる再帰の段数は大抵logオーダーなので、 32段くらいで強制的に再帰をストップするようなテンプレートを書く」とか無理矢理なんとかする手は あるんですが、まあ不便ですよね、という。
「C# とか C++ とか」って書いてあったので反応してみた２。
が、C# とか C++ とかを使っていると、静的型があるのが苦しくて苦しくて仕方がない。 … (略) … これは単純にポリモーフィズムのお話で、静的型付け というよりは、nominal subtyping が 脳のリソースを大きく引っ張っていく割に、作りたいことの本質ではないから。 動的型付OOPLとか OCaml のような、structural subtyping のほうが ぜんぜん Lightweight に感じます。
from LLとOO - みねこあ
最初に結論から書いておくと、「C++ ほど Structural Polymorphism 大好きな言語を他に私は知らない。」 ので、↑と感じるとしたら C++ 的でない使い方で C++ を使っているか、 あるいは脳のリソースを引っ張っているというのは実は別の部分なのではないでしょうか…等々。 あとこれも最初にお断りとして、私 Smalltalk まったく知らないに等しいため Smalltalk と比較して どうかは判断がつかないので、引用部で例にあがっている動的型付OOPLの例としてRubyとPython、 あとOCamlをなんとなく念頭に置いて以下を書きました。
とっさに頭に浮かんだのは、「既存のStringクラスと互換性のある別の文字列クラスを作りました。
でも、それに対して既存のRegexpクラスで正規表現検索することができません。」
なんての（id:ku-ma-me:20070730）
が許されるのはLLまでだよねー。
String と同じメソッド群を 持ち同じように振る舞うならそれは String である…っていうと Duck Typing になっちゃうか、 えーとえーと、「Regexp が要求するあれとこれとそのメソッドを持ってれば全て正規表現検索対象にできます」 っていうのが Structural Typing 的な考え方であって、"String" っていう"特定の"クラスだけを 検索対象にできます、っていうのは Nominal Typing 的な考え方だと思います。 そしてもちろん、C++のregex は前者です。 果ては Xpressive みたいな、正規表現を文字列以外の方法で記述できる実装だと、 「文字」の「列」ですらなくても「文字とおなじようにふるまうもの」の「列」に対して正規表現 使えちゃったりとか。intの配列から、100未満の値が繰り返されてる部分を取り出し！
※ 正規表現という例は恣意的にすぎる、という指摘はアリだと思います。 例えば仮に 100% Pure Ruby で実装された正規表現エンジンがあったとすれば、 それはおそらく、当然のようにString互換のRopeなども検索対象にできるでしょう。 標準のRegexpがそれをできないのは、その部分は速度のためetcでCで実装されているためであり、 速度のためetcでStringのデータ表現を仮定しなければならないからだ、例外だ、という。 でも、いかなる都合であれ、その言語の使い手誰もが使う標準ライブラリという部分ですら貫けないような 概念はその言語の看板にはならないと思ってて、で、一方で、C++はありとあらゆるレベルで Structural な方式を貫くことができる言語ですし、実際「イマドキの」C++のコードはそのように作られていると思う。
※ それと、そうだ、"文字列"として最低 std::string と std::wstring と char* と wchar_t* の４種くらいは デフォルトで存在するので対応しなくちゃいけない大変面倒くさい状況だからこそ C++ はそんなことに なってるのではないか？という指摘もある程度その通りだと思いますが、それは原因に対する考察であって、 原因はどうであれ、とにかく結果としてC++のライブラリはやたらGenericだという結果に違いはないと思うのです。
そもそも STL （C++標準の、データ構造＆アルゴリズムのライブラリ）が 徹底して「あれとこれとそのメソッドを持ってるオブジェクト全てが処理対象です」という形式で 機能を提供しているのが始まりだと思うんですが、正規表現に限らず、あらゆる（というと言い過ぎですが） C++ のライブラリはこんな方向でできています。例えば asio (ネットワークI/O) のドキュメントなんかが、ちゃんとハイパーリンクされてて一番わかりやすいかも。 引数 SyncReadStream や MutableBufferSequence をクリックしてみるとわかるように、 「○○の派生クラスのインスタンスを引数として受け取ります」みたいなAPIではなく、 「read_someメソッドを提供しているオブジェクトならなんでも引数として受け取ります」という定義に なっています。そういうふうにできている。
まとめ。「C++ コミュニティから出てくるライブラリは、 特に2008年の今ならほとんどすべて、ユーザーから受け取る型を Structural に定義しています。 その徹底度合いは私の乏しい知識の中で知っている言語（動的静的を問わず）の中でも トップレベルに感じられます。そういう意味で、Structural Polymorphism は "C++ Way" と言えるのではないかと思います。」
「生きてるオブジェクト」を示す式 を見て、それだと解が一つに定まらないので "live はこれを満たす最小の集合とする" か何か 注釈つけないとダメじゃね？ と重箱の隅を突っつきたくなったんですけど、考えてるうちに、 これはこれでアリかと思えてきたりした朝でした。
この式を満たす最小の集合は、適当に日本語で言うと「Root からポインタをたどってたどりつける オブジェクト全部の集まり」になって、これが「生きてるオブジェクト」の定義として直感的に 意図されるものだと思います。じゃあ、その式を満たす最大の集合は何だろう。 これはたぶん、「Root もしくは循環参照してるオブジェクト、 からポインタをたどってたどりつけるオブジェクト全部の集まり」になる。 なんかこれはこれで、ある意味で、 というか何の工夫もない参照カウントGCから見て生きているオブジェクトという意味で、 意味があるような気がしなくもない。自己参照だけは検出できるような参照カウントGCだと、 また別の中間の解に落ち着いたり。
なお類題として
Na = {n ∈ String | (n="") or (∃nn∈Na. n="na"+nn)}
Oyatsu = {o ∈ String | (∃nn∈Na. o="Ba"+nn)}
"Bananananananana..." (無限文字列) は Oyatsu に入りますか問題などがあります。
不可思議２ Final Dungeon クリアしたー！ たしか、リリースされた頃ほぼ同じ時期に Cesteaju もリリースされてそっちにハマりまくっているうちに自分の記憶からフェードアウトしてたなあ、 というのをちょっと前に思い出して始めてみたのでした。 マイナスアイテムが致命的すぎるな上に種類多いのがきっついですが、敵を1～3発で倒せる ＆ 自分も 4～5 発くらいで倒される 程度に調整されてるバランスは結構テンポがよくて面白かった。