電話はいきなり鳴り出すから暴力的だ。もうちょっと心の準備をさせて欲しい。
Haskellにどうしても馴染めないのは、記法が入れ子的じゃないからだ。その点Lispは素敵だ。
Lispは素敵だけど、中置演算子くらいは欲しい。それに、手続き名を第一引数に後置する形式の呼び出しも欲しい。(filter (lambda (n) (zero? (modulo n 2))) lis)よりも@LIS.filter({&0 %% 2 = 0})の方が読みやすい、と思う。手続き名の後置という点においてもっとも重要なのは、データと手続き名との視覚的な配置だ。それが「メソッド呼び出し」あるいは「メッセージ送信」であるとか、手続き名が第一引数の名前空間に支配されるとかいったことは別にたいした問題にならない。なんなら、@LIS.filter({&0 %% 2 = 0})がfilter(@LIS, {&0 %% 2 = 0})という関数呼び出しの構文糖であったって構わない。
手続き名の後置は、データを二回三回変形するような処理をするとき、特に重要になる。(car (cdr lis))よりも@LIS.rest.leadの方が分かりやすいってのはほとんど間違いない。手続きの名前が現れるのと同じ順で情報が流れるから、つまり視覚的な流れと処理の流れが一致するからだ。
「N重リストについてのmap関数を返す関数」はKinkでは以下のように書ける。
`nmapper := { .(`N)
{ .(`LIST, `f)
nm(@N, @LIST)
@@ `nm := { .(`NN, `LL)
if(@NN = 0, {f(@LL)}, {
@LL.map({nm(@NN - 1, &0)})
})
}
}
};
`map1 := nmapper(1);
dump(map1((0, 1, 2, 3), {&0 * 2}));
# => (0, 2, 4, 6)
`map2 := nmapper(2);
dump(map2(((0, 1, 2, 3), (4, 5, 6)), {&0 * 2}));
# => ((0, 2, 4, 6), (8, 10, 12))
Haskellでは少なくとも簡単には書けない。mapの型は(a->b) -> [a] -> [b]、map.mapの型は(a->b) -> [[a]] -> [[b]]とことなる。したがって、引数に応じてことなる深さの多重リストのmap関数を返すためには、型情報のうちリストの深さが、実行時の値によってパラメータ化できなければならない。これはHaskellの型システムの想定を超える。Kinkは型がどうだとかいかめしいことを言わないから、書ける。
カリー化されたmap関数を使えばもうちょっと簡単に書ける。
Proc`curry := { .(`proc, `N)
@N.case(
0 -> {proc()},
Any -> {
{ .(`E) {proc(@E, .. &args)}.curry(@N - 1)}
}
)
};
Proc`uncurry := { .(`PROC)
{&args.fold(@PROC, {&0.call(&1)})}
};
`nmapper := { .(`N)
{ .(`LIST, `f) [@curriedmap ** @N].uncurry.call(@f, @LIST)}
@@ `curriedmap := {&1.map(&0)}.curry(2)
};
AbstractList#addはUnsupportedOperationExceptionを投げるようになっている。これは、「要素を参照したり変更したりはできるけど、追加はできないよ」というようなリストを実現するためだ。Arrays#asListの戻り値が、まさにこのようなリストだ。つまり、正しいList型の値だからといって、addメソッドが使えるとは限らない。リストの要素が変更可能か否か、追加可能か否か、削除可能か否かといった情報は、Javaのコレクション・フレームワークの型システムから漏れる。
参照メソッドだけを記述したListインタフェース、変更メソッドを追加したModifiableListインタフェース、追加および削除メソッドを追加したVariableSizeListインタフェースっていう感じに分ければより「正しく」なるけど、面倒くさいだろうな。
List#subListはリストの部分のビューを返す。これはすげえ重要なメソッドだ。というかこのメソッドがないと、Listでしゃれたことは何もできない。単に伸縮可能な配列というに過ぎなくなってしまう。
練習のためにクイックソートを書いた。
public static <T extends Comparable<T>> void quickSort(List<T> list) {
if (list.size() <= 1) {
return;
}
T pivot = list.get(list.size() / 2);
int left = 0, right = list.size() - 1;
while (true) {
while (list.get(left).compareTo(pivot) < 0) {
++left;
}
while (list.get(right).compareTo(pivot) > 0) {
--right;
}
if (left >= right) {
break;
}
T tmp = list.get(left);
list.set(left++, list.get(right));
list.set(right--, tmp);
}
quickSort(list.subList(0, left));
quickSort(list.subList(left, list.size()));
}
マーチン・ファウラーの『リファクタリング』を読んでいる。いい本だとは思うんだけど、あんまりスイスイ読み進めてしまえるので、五千円の元が取れない感じがある。
Javaでは、thisにfooという名前のフィールドがあったとき、fooとして参照できる。同名の引数や一時変数があったとき、これは混乱とバグの元になる。ファウラーはこれに対処するために、フィールド名にアンダースコアを前置しているみたいだ。こんな風に。
public class Employee {
private final int _id;
private final String _name;
public Employee(int id, String name) {
_id = id;
_name = name;
}
public int getId() { return _id; }
public String getName() { return _name; }
}
MFCのm_と同じだけど、あんまりいい方針だと思えない。フィールドは常にthis.を前置して参照すればいいじゃん。
public class Employee {
private final int id;
private final String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() { return this.id; }
public String getName() { return this.name; }
}
こっちの方が明瞭に意図が分かるし、命名規約ではなく文法に頼っている点で強固だ。
同じように、thisのメソッドを呼び出す際にも、this.foo()というように、this.を前置するようにしている。こっちはフィールドにおけるほどのメリットはないけど、thisを暗黙の文脈として扱うのではなく、明示する方が素敵な気がする。
コムソートの理屈がよく分からなかったので実装してみた。
/** Sorts the list by the comb sort algorithm. */
public static <T extends Comparable<? super T>> void
combSort(List<T> list) {
int gap = nextGap(list.size());
while (true) {
boolean swapped = false;
for (int i = 0; i + gap < list.size(); i++) {
if (compare(list, i, i + gap) > 0) {
swap(list, i, i + gap);
swapped = true;
}
}
if (gap == 1 && !swapped) {
return;
}
gap = nextGap(gap);
}
}
private static int nextGap(int prev) {
if (prev <= 1) {
return 1;
}
final double SHRINK = 1.3;
int gap = (int) (prev / SHRINK);
return (gap == 9 || gap == 10 ? 11 : gap);
}
private static <T extends Comparable<? super T>> int
compare(List<T> list, int i, int j) {
return list.get(i).compareTo(list.get(j));
}
private static <T> void swap(List<T> list, int i, int j) {
T work = list.get(i);
list.set(i, list.get(j));
list.set(j, work);
}
なるほど理屈は分かったんだけど、これって最悪計算量がO(n log n)であることは保証されてるのか？うまいこと櫛が通らずに、gap = 1での走査が何度も続くようだと、最悪計算量はバブルソートと同じO(n^2)に近づいてしまうはずだ。実際、gapを小さくするための除数（上記リスト中のSHRINK）が大きすぎるなら、最悪計算量は明らかに跳ね上がる。SHRINK = 1.3なら大丈夫だという理由がよく分からない。というか英語版Wikipediaの記事では、「原論文の著者たちは、いくつかのランダムなリストについて試してみた上で、ちょうどいい感じの除数として1.3を提案した
」とある。そんないい加減な！さらに、SHRINK = 1/(1-exp(-phi)) = 1.247330950103979ならさらにいい感じだよ、という記述があって、「要出典」タグがついている。
同様の疑問についてcomp.theoryに投稿があった。この記事でRevueltaさんは、除数が9/7 = 1.28571428571429以上の時にはgap = 1で複数回の走査が必要になる場合がみつかったけど、それより小さい除数についてはなんだか分からない、と述べている。
ヒープソートも実装してみたよ。
/** Sorts the list by the heap sort algorithm. */
public static <T extends Comparable<? super T>> void
heapSort(List<T> list) {
for (int parent = (list.size() - 1) / 2; parent >= 0; parent--) {
consHeap(list, parent);
}
for (int size = list.size(); size > 1; size--) {
swap(list, 0, size - 1);
consHeap(list.subList(0, size - 1), 0);
}
}
/* Requires that children are proper heaps. */
private static <T extends Comparable<? super T>> void
consHeap(List<T> list, int me) {
while (me * 2 + 1 < list.size()) {
int l = me * 2 + 1, r = me * 2 + 2;
int child = (r >= list.size() || compare(list, l, r) >= 0 ? l : r);
if (compare(list, me, child) >= 0) {
return;
}
swap(list, me, child);
me = child;
}
}
なるほどこれは綺麗だ。
スタックは可変長配列とスタックポインタを組み合わせて実装できる。また、単方向連結リストでも実装できる。スタックを使う際に、それが配列で実装されているのか、連結リストで実装されているのかを気にする必要はない。
ソフトウェアの世界には、この種の抽象化の層がたくさんある。すべての層を把握することは無理だけど、層があるんだってことが理解できないと苦労するはずだ。
Javaにおける「クラスの継承」の内実は、「型の引き継ぎ」と「実装の引き継ぎ」に分離できる。
Dogが抽象クラスAnimalを継承するとき、「型の引き継ぎ」に関して以下のようなことが言える。
以上の事柄は、インタフェースによる型の引き継ぎについてもまったく同じようにいえる。
「実装の引き継ぎ」に関しては以下のようなことがいえる。
これは委譲によっても同じことができる。
abstract class Animal {
public void howl() {
System.out.println("foo!");
}
}
class Dog extends Animal {
...
}
の代わりに、
interface Animal {
public void howl();
}
class Dog implements Animal {
private final HowlStrategy howler = new BowHowlStrategy();
public void howl() {
this.howler.howl();
}
}
とかって感じで。つまり、クラスの継承による実装の引き継ぎは、委譲の自動化だといえる。
結局のところ、型の引き継ぎはインタフェースでいけるし、実装の引き継ぎは委譲でやれるから、クラスの継承はぜったいに必要ってわけじゃないよ、ってことが分かる。だいたい、実装の引き継ぎについていえば、サブクラスの側のオーバーライドで制御できちゃうし。
ただし、クラスの継承を前提にしないといまいちうまく行かない例がある。まず、Object#cloneのように、メソッドが「オブジェクトそのもの」に関するメタ情報を参照する場合、委譲ではうまく解決できない。もっともこのような機能は、System.clone(someObject)みたいに、関数的手続きでもって実現すればいいのかもしれない。ていうかcloneの場合にはそっちの方がうまく行きそうだ。
もうひとつはStringみたいに、処理系の内部で中身のデータに触っちゃってそうなもの。この場合、インタフェースと実装を分離することはできない。常にString#getCharsをとおして中身に触るよ、ってな約束にすれば、Stringインタフェースを実装するあらたな文字列クラスを作る、なんてこともできるけど、効率の観点からすると現実的じゃない。Javaの型システムの上では、文字列の不変性という暗黙のインタフェースを強制できない点でも問題がある。Stringみたいなクラスは、なかばプリミティヴ型なわけだ。
lethvertさんの昔のエントリに関連する議論があった。
Kinkの型システムについて考察する予定。
JavaScriptは邪魔者扱いだった昔の印象のせいで、食わず嫌いで触っていなかったんだけど、あちこちでコード片なんかを見ると、相当クールな言語みたいだ。クロージャが簡単に書けるみたいだし、プロトタイプベースっぽい考え方もあるらしくって、Kinkと共通するところが多そうだ。
昨日と今日がくっついてゆく世界で！
Kinkの継承システムは以下のとおり。nankaからFOOというフィールドを探すとき、まずnanka自身の持ち物から探し、みつからなければnanka.basesから、深さ優先探索する。Stuff.basesの中身は空であり、他のあらゆるオブジェクトのbasesを手繰っていくと必ずStuffに行き着く。
クラスベースの言語なら「スーパークラスのフィールドをサブクラスが引き継ぐ」とか「クラスに実装されたメソッドをインスタンスから使える」とかってのを、プロトタイプベースな言語たるKinkでは、この継承システム一本でやる。
Kinkに静的な型システムはない。あるのは実行時のダック・タイピングだ。
`add := { .(`X, `Y) @X + @Y}
addに渡すふたつの引数は、どのオブジェクトを継承していようがしていなかろうが別に構わない。ただ、@X@op_addが存在して、@Yをうまいこと扱えればそれでいい。そうでなければ、実行時に例外が投げられる。
つまり、ある値の型はその値の実装の如何によって実行時に判断される。ここで継承は関係ない。
公式な型システムはダック・タイピングだが、Kinkにはもうひとつ、継承関係にもとづく型システムがある。たとえばText#atは整数値を引数として要求するんだけど、その「整数値」ってのはIntegerを継承した値じゃないといけない。「あたかも整数であるかのように振舞う値」では駄目だ。例外が投げられる。これはText#atが、整数値が持ってる隠しフィールドからJavaのBigIntegerを引っ張り出して使ってるからだ。このフィールドが存在するってことは継承関係によって保証される。Kinkレベルでそれっぽく振舞われても困るわけ。
これは、JavaのStringがインタフェースにはできないっぽいのと同じ理由だ。
ちょっとずつ違った文脈で、継承関係を利用する型っぽいシステムが他にも少しある。たとえば例外の階層的分類を実現するためにも継承関係を使ってる。
ダック・タイピングにおいて継承と型とは直接的な関係はない。ただ、継承によってある機能が実装されるなら、それによってそのオブジェクトがある型を満たすようになる。
継承関係を利用してあるオブジェクトに機能を実装するためのメソッド集みたいなオブジェクトを、トレイトと呼ぶ。
CompareTrait`op_lt := { .(`X, `Y)
[@X <=> @Y].case(
Lesser -> {True},
Equal -> {False},
Greater -> {False}
)
};
Rational`op_cmp := { .(`X, `Y)
# #numerは分子を、#denomは分母を返すと思いねえ。
@X.numer * @Y.denom <=> @Y.numer * @X.denom
};
# Rationalの継承元にCompareTraitが追加される。
Rational.add_base(CompareTrait);
dump(rational(1, 3) < rational(1, 2)); # => True
dump(rational(2, 3) < rational(1, 2)); # => False
つまりadd_baseはop_ltメソッドをCompareTraitからRationalにコピってるのと一緒だ。委譲するためのコードを手動でいちいち書くんじゃなくて、単にコピっちゃえば楽じゃん、ってのがトレイト。
コピっちゃうのと同じだってんなら、継承システムを使わずに、ほんとにコピっちゃえばいいんじゃない？上の例ならRational`op_lt := CompareTrait@op_ltってすればいい。Kinkの継承システムが多重継承なのはトレイトのためなんだけど、トレイトの導入を値のコピーにしちゃえば、単一継承で済むようになる。探索順序がどうたらこうたら考えなくていいし、循環継承に気をつける必要もなくなる。
単一継承も結局のところ委譲の自動化であり、コピーなわけだけど、これは多分そのまま残す方がいいだろう。Kinkはプロトタイプベース言語なので、有象無象の整数値とIntegerの関係もまた継承関係だ。整数が作られるたびにIntegerのメソッドをぜんぶコピーする、なんてしてたら馬鹿っぽい。ここでは、委譲の自動化としての継承が確かに便利だ。これに対して、IntegerがCompareTraitからメソッドを引っ張ってくる、なんてのは、ひとつのプログラムの中でせいぜい一回やるくらいのことなので、ここがコピーになっても大した負荷はない。