2011年に読んだ論文紹介 または私は如何にして心配するのを止めて静的に型付けされたオブジェクト指向言語を愛するようになったか

書いた人: ると

書いた日: 2011年12月18日

今年読んだ面白CS論文紹介カレンダーの5日目の記事です。

もくじ

  1. Sound polymorphic type inference for objects または私は如何にして心配するのを止めて静的に型付けされたオブジェクト指向言語を愛するようになったか
  2. Covariance and Contravariance: Conflict without a Cause 共変と反変: 理由無き対立
  3. What is Object-Oriented Programming? バック・トゥ・ザ・オブジェクト・オリエンテッド・プログラミング

Sound polymorphic type inference for objects

Jonathan Eifrig, Scott Smith, and Valery Trifonov. 1995. Sound polymorphic type inference for objects. In Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications (OOPSLA '95). 169-184. DOI=10.1145/217838.217858

要約

オブジェクト指向言語のための健全で完全な型推論アルゴリズムを作ったよ。制約を全ては解かずに残すけどね。

型推論ができないということの意味

私は今まで「型推論はできなくったって、わかりきったことを何度も書く必要があってちょっとめんどうなだけ」と思ってました。メタプログラミングをしたり極度に抽象的なライブラリを書いたりする場合はともかく、普通のアプリケーションを書く場合は適切な型はプログラマにとって自明なものなんだと思っていました。

でもそんなことはありませんでした。

それはひどくあたりまえのことで中学生でも知ってるはずのことです。

例えばScalaで商品情報を取ってくるDAOとそのファクトリを考えます。(Scalaを知らない人のために: traitとは実装も書けて多重継承できるインターフェースのようなものです)

// インターフェース
trait ItemsDAOFactory {
  def createItemsDAO(): ItemsDAO

  trait ItemsDAO {
    def allItems: Set[Item]
  }
}

// JDBCで取ってくる実装
trait JDBCItemsDAOFactory extends ItemsDAOFactory {
  def createItemsDAO(): ItemsDAO = new JDBCItemsDAO

  class JDBCItemsDAO extends ItemsDAO {
    def allItems: Set[Item] = {
      // JDBCで商品情報を取ってくる
    }
  }
}

非常にシンプルです。

また、ここにキャッシュを追加するのも簡単です。

// キャッシュする実装
trait CachingItemsDAOFactory extends ItemsDAOFactory {
  // 註: abstract overrideは親traitのメソッドが抽象メソッドでも
  //     実際にミックスインする際にミックスイン先のクラスや、
  //     先にミックスインされたtraitでメソッドが定義されていれば
  //     それをsuperを通じて参照できるようにするための宣言
  abstract override def createItemsDAO(): CachingItemsDAO = {
    new CachingItemsDAO(super.createItemsDAO())
  }

  class CachingItemsDAO(baseDAO: ItemsDAO) extends ItemsDAO {
    def allItems: Set[Item] = {
      // baseDAOの結果をキャッシュして返す
    }

    def invalidateCache() {
      // キャッシュを破棄する
    }
  }
}

// JDBCで取ってきた商品情報をキャッシュする実装のファクトリ
class ConcreteFactory extends
      JDBCItemsDAOFactory with
      CachingItemsDAOFactory {
  // 註: CachingItemsDAOFactoryのcreateItemsDAOは
  //     JDBCItemsDAOFactoryのcreateItemsDAOを上書きする。
}

ここでDAOにキャッシュを破棄するメソッドを追加しておきました。キャッシュの破棄は計算機科学の2大難問の1つであり重要です。実際のコードではキャッシュは適当なタイミングで自動で破棄するので必要ないのですが、将来もしかしたら破棄のタイミングを詳細に制御する必要が出てくるかもしれません。そのためキャッシュを破棄するメソッドはpublicにして、createItemsDAOの返り値の型はCachingItemsDAOに変更しました。

ここまでは何の問題もありません。全ては完璧です。こんな幸福な日常がずっと続くと思ってました。

しかし破滅はすぐにやってきました。

実は時間限定商品があり、特定の時間以外は隠しておく必要があったのです。私はいつものようにtraitを1つ作って追加しました。

// 現在時刻に売ってる商品だけを返す実装
trait FilterByTimeItemsDAOFactory extends ItemsDAOFactory {
  abstract override def createItemsDAO(): ItemsDAO = {
    new FilterByTimeItemsDAO(super.createItemsDAO())
  }

  class FilterByTimeItemsDAO(baseDAO: ItemsDAO) extends ItemsDAO {
    def allItems: Set[Item] = {
      // baseDAOの結果の中から、現在時刻に売ってる商品だけを返す
    }
  }
}

// JDBCで取ってきた商品情報をキャッシュして
// 現在時刻に売ってる商品だけを返す実装のファクトリ
class ConcreteFactory extends
      JDBCItemsDAOFactory with
      CachingItemsDAOFactory with
      FilterByTimeItemsDAO {
  // 註: CachingItemsDAOFactoryのcreateItemsDAOは
  //     JDBCItemsDAOFactoryのcreateItemsDAOを上書きする。
  //
  //     FilterByTimeItemsDAOのcreateItemsDAOは
  //     CachingItemsDAOFactoryのcreateItemsDAOを上書きする。
}

でもこれはコンパイルできません。CachingItemsDAOFactoryのcreateItemsDAOはCachingItemsDAOを返すと言っているのに、それを上書きするFilterByTimeItemsDAOのcreateItemsDAOはただのItemsDAOを返すと言っています。これでは通りません。

ではFilterByTimeItemsDAOをCachingItemsDAOの子クラスにしたらよいでしょうか。しかしそれではせっかく分かれていた実装が台無しです。

Scalaではtraitを使ってこの問題を回避できるのですが、その話はまた今度にするとして、型の問題を考えます。

使いもしないのにキャッシュを破棄するメソッドを公開したばっかりにコンパイラに嫌われてしまいました。メソッドの型の変更は重大な意味を持っていたのです。「メソッドの型を変更して綺麗な上書きを諦める」、「綺麗に上書きできるようにしてメソッドの型の変更を諦める」この2つはもっと慎重に選択するべきでした。

これは本当にあたりまえのことでJavaを覚えたての中学生でも知ってるはずです。

でも、本当にそれはこのメソッドのシグネチャを考える上で必要なことなんでしょうか。

だって型というのは実装する側と呼び出す側の都合であって両者が合意すればなんでもいいはずです。それをまだ呼び出す側も無いうちに本当に決めないといけないんでしょうか。

このメソッドのシグネチャを考える時点でプログラム全体を見回して将来も見据えて適切な型なんて選べっこありません。あらゆる可能性を考え出してしまって、ちいさなプログラムさえももう型が付けられません。

しっかりと事前に設計して、ある程度以上は見切りを付けて型を決めてしまうのが現実世界のプログラマなんだろうとか強がってみても何も支えがないままコードを書いていくのは苦痛です。

なんでこんなことになったんでしょうか。

それはこの型を付けておけば大丈夫という最も一般的な型が無いからです。

この最も一般的な型の有無は型推論の可否を大きく左右します。最も一般的な型が推論できればコンパイラはその型を付けられるのですが、そのような型が無ければコンパイラはどの型を付けたらよいのかわからず困ってしまいます。

しかし、最も一般的な型の有無は機械にとっての型推論の可否以上の意味を持っていました。最も一般的な型が無いといういことは、人間もそこに書く型を決定できないという意味でもあったんです。

これは極めて当然のことで、でも当然だからなお悲しくて、そんな悲しいことをぼくは知らなかった。

もうオブジェクト指向はおしまいなのでしょうか。それともおしまいなのは静的な型付けの方でしょうか。希望はないのでしょうか。

オブジェクト指向でも型推論はできる

そんな声に答えてくれるのがこの論文です。

ちゃんと変更可能な参照もあって、再帰もあって、継承と動的ディスパッチもあるオブジェクト指向言語において、健全で完全な、つまりプログラム中に型を全く書かなくても型推論ができるというのがこの論文です。でもどうやって?

その秘密はいくつかあります。

秘密その1 型変数に対する制約を残す

最も重要なのは型を拡張して、普通の型+型変数に対する制約の集合とする点です。型変数に対する制約というのはJavaで言うところの<T extends Foo>みたいなのです。

普通の型推論では型変数に対する制約を沢山作って、それを全て解決して型を決めます。しかしここで制約を全ては解決せずに、制約を制約のまま残しておきます。つまり制約同士が矛盾しないかだけ調べてあとは制約を型の横に書いておきます。

問題を半分放り投げてしまったようでちょっとずるい気もしますが、これを許してしまえば多くの問題は解決します(ちなみにJavaの型推論でも一部制約を残します)。

秘密その2 構造的な型を使う

それから型はJavaなどで使われているノミナルな型(アヒルと宣言されたものだけがアヒルである)ではなく、構造的な型(アヒルのように歩くと宣言され、アヒルのように鳴くと宣言されたものはアヒルである)を使う点もあります。

構造的な型はダックタイピング(アヒルのように歩き、アヒルのように鳴くものはアヒルである)と似ていますが、コンパイル時にメソッドがちゃんとあるかどうかチェックできるれっきとした型です。

クラス単位で型を表現するノミナルな型と違い、メソッド単位で型を表現できる構造的な型により、型の制約をより細かい粒度で指定できます。

秘密その3 実装の継承と型の親子関係を分ける

そして最後に、クラスを継承したからといって型を継承するとは限らなくしたという点です。つまり継承は純粋に実装の再利用だけであって、親クラスのインスタンスの代わりに子クラスのインスタンスを使えるとは限りません。その代わり各メソッドの型に互換性があれば継承関係にないクラスのインスタンスでも代わりに使えます。つまり部分型は純粋に構造的に判定します。

これにより、子クラスが型の制約を強めて、孫クラスが型の制約をゆるめるようなコードも書けるようになります。

まとめ

以上のような、Javaなどとは大分異なったアプローチを取ることで健全で完全な型推論を手に入れています。

もちろん欠点もあって、例えば型の制約はとても大きくなり、しかも冗長な制約が含まれますのでとても読みにくくなってしまいます。制約を単純化する手法は(少なくともこの論文の時点では)まだ不完全です。また、制約をなるべく後で解こうとするのでプログラムを作っている途中ではエラーを発見できないかもしれませんし、エラーメッセージもわかりにくくなってしまうかもしれません。

それでも、「オブジェクト指向でも最も一般的な型はある」というこの事実があればそれを支えにして私達はコードを書いていけるでしょう。

論文にはその他、この型システムを持つ言語をオブジェクト指向でない言語に変換して健全性を示したりしています。明日からもコードを書いていくために是非読んでみて下さい。

Covariance and Contravariance: Conflict without a Cause

Giuseppe Castagna. 1995. Covariance and contravariance: conflict without a cause. ACM Transactions on Programming Languages and Systems (TOPLAS). 17, 3 (May 1995), 431-447. DOI=10.1145/203095.203096

要約

サブクラスにおいてより緩い型の引数をとるメソッドを書くのと、よりきつい型の引数をとるメソッドを書くのは意味が違っていて、どちらかだけが正しいという訳じゃないよ。

メソッドの引数の型 共変と反変のどっちが正しい?

さて、安心して静的に型付けされたオブジェクト指向言語を使えるようになったところで、もう少しオブジェクト指向言語の型について調べたくなりました。そこでオブジェクト指向言語の型で重要となる「共変」と「反変」についての論文を読んでみました。

オブジェクト指向言語において、共変とか反変というのはサブクラスでメソッドなどの型を変える際の変え方の種類です。例えばJavaでファイルからオブジェクトを読んでくるメソッドが次のように宣言されていたとします。

class FooFactory {
    public Foo readFromFile(BufferedReader input) {
        ...
    }
}

class Foo {
    ...
}

そしてサブクラスで次のようなメソッドで上書きしたとします。

class BarFactory extends FooFactory {
    public Bar readFromFile(Reader input) {
        ...
    }
}

class Bar extends Foo {
    ...
}

このとき、メソッドの返り値の型はFooからBarに変わっています。メソッドを持つクラスの型がFooFactoryからBarFactoryという風に親クラスから子クラスになると共に、返り値の型も親クラスの型から子クラスの型になったため、この様子を「共に変わる」と書いて共変と呼びます。

一方で引数の型はBufferedReaderからその親インターフェースであるReaderになっています。メソッドを持つクラスの型がFooFactoryからBarFactoryという風に親クラスから子クラスになるのに反して、引数の型は子クラスの型から親インターフェースの型になったのでこの様子を「反して変わる」と書いて反変と呼びます。

Javaにおいてはメソッドを上書きする際には返り値の型は共変にして、引数の型は反変にする必要があります。

メソッドを呼ぶ側から考えると、Fooを返すと約束されていたところでFooのサブクラスであるBarを返されても問題ありません。しかしBarを返すと約束されていたところでその親クラスであるFooを返されると、Barにしかないメソッドを呼べないので困ってしまいます。そのため返り値の型は共変にする必要があります。

同様に引数についても、BufferedReaderが必要と言われていたのが後でReaderでもいいと言われてもそのままBufferedReaderを渡せるので問題ありません。しかしReaderでいいと言われていたのに後からBufferedReaderが必要と言われたら困ってしまいます。そのため引数の型は反変にする必要があります。

しかし、引数の型は共変にするべき、と言う人もいます。Eiffelという言語やO2というオブジェクトデータベースシステムでは共変だそうです。

例えば2つのオブジェクトの等しさを判定するメソッドを考えてみます(ここでは例にJavaを使っていますが、Javaのequalsのことは忘れてください)。

class Foo {
    public boolean equals(Foo other) {
        ...
    }
}

親クラスのFooの場合は単純ですね。Fooを受け取って等しければtrueを返します。ではそのサブクラスBarの場合はどうでしょうか。

引数の型は反変でなければならないとすると、引数の型はFooかObjectでないといけなそうです。

class Bar extends Foo {
    public boolean equals(Foo other) {
        ...
    }
}

でもBar同士の等しさを判定したいのですから、引数の型もBarであるべきじゃないでしょうか。

class Bar extends Foo {
    public boolean equals(Bar other) {
        ...
    }
}

このような対立する2つの意見があり、しばしば論争になっていたそうです。ではどちらが正しいのでしょうか。

反変は部分型の作成、共変は特殊化したメソッドの作成

そんな問題に答えを出すのがこの論文です。実はその2つは対立するものではないというのが論文の主張です。

反変は部分型の作成

反変な型でメソッドを書いた場合はそれはメソッドの上書きです。元のメソッドは新しいメソッドで隠されます。

親クラスの全てのメソッドについて引数の型が反変で返り値の型が共変であるメソッドを持っているというのは子クラスが親クラスの子である条件となります。

共変は特殊化したメソッドの作成

一方で共変な型でメソッドを書いた場合それはメソッドのオーバーロードとなります。元のメソッドと新しいメソッドは共存します。

さて、Javaにおいては動的なディスパッチに使われるのはレシーバの型のみで、オーバーロードは静的な型によりコンパイル時に決定されます。しかしもし引数の型も含めて動的にディスパッチする(マルチメソッド)としたらどうなるでしょうか。

するとBar同士を比較するときには常にBarのequalsが使われて、Foo同士、またはFooとBarを比較する時はFooのequalsが使われます。

つまり共変な型によるメソッドの定義は、引数の型が特定の組み合わせであるという特殊な場合用のメソッドの追加と言えます。つまり特殊化です。

まとめ

以上のように共変な引数の型によるメソッドの定義と、と反変な引数の型によるメソッドの定義の違いをマルチメソッドの枠組みで整理しています。

論文ではさらに一般的にメソッドの一部の引数のみを動的ディスパッチに使う場合を考えています。是非読んでみてください。

What is Object-Oriented Programming? (1991 revised version)

Bjarne Stroustrup. 1991. What is Object-Oriented Programming? (1991 revised version). In Proceedings of 1st European Software Festival.
Bjarne Stroustrup. 1988. What Is Object-Oriented Programming?. IEEE Software. 5, 3 (May 1988), 10-20. DOI=10.1109/52.2020 (古い方)

Scalaでがしがしプログラムを書いていたところ、そもそもオブジェクト指向言語ってなんだろうという疑問が湧いてきました。Scalaはトレイトという機構を使った高度なオブジェクト指向の機構を多用する言語です。しかし同時に不変なオブジェクトを多用する言語でもあります。Rubyの父であるまつもとゆきひろ氏はオブジェクト指向について「最低限の条件は『アイデンティティがある』ことである」としています。しかし不変なオブジェクトにとってオブジェクトのアイデンティティはあまり重要でありません。Scalaが不変なオブジェクトの利用を進めていくと、それはもうオブジェクト指向言語ではなくなってしまうのでしょうか。

そんな疑問に答えてくれる(かもしれない)のがこの論文です。

この論文はC++の父であるBjarne Stroustrup氏が「オブジェクト指向プログラミングとは何なのか」を説明した論文です。俗に言う「カプセル化・継承・ポリモーフィズム」の元になったと言われている論文です。しかし実は、この論文におけるオブジェクト指向プログラミングの定義はこの3つではありません(少なくとも直接そう明言してはいません)。

そもそもプログラミング言語が特定の機能をサポートするってどういうこと?

「オブジェクト指向って何?」とか「オブジェクト指向プログラミングって何?」と10人に聞くときっと30種類ぐらい答が返ってくると思います。先に挙げた「カプセル化・継承・ポリモーフィズム」や「オブジェクトのアイデンティティ」の他に「メッセージパッシング」とか色々あります。

それから「オブジェクト指向言語って何がある?」と10人に聞いてもきっと50種類ぐらい答が返ってくるでしょう。C++, Smalltalk, Java, Ruby, JavaScriptあたりはいいとして、Perl, PHP, Common Lispあたりになってくるとちょっと怪しくなってきます。果てはCもGObjectがあるからオブジェクト指向言語だと言う答も返ってくるでしょう。

そもそもチューリング完全なプログラミング言語ならどんな言語でもオブジェクト指向プログラミングはできるという意見も出てくるでしょう。

この論文の素晴しいところは、そもそも「プログラミング言語が特定のプログラミングスタイルをサポートする」とはどういうことなのかの定義から始まるところです。

この論文では、「プログラミング言語は、特定のプログラミングのスタイルが手ごろに(ほどよく簡単で、安全で、効率良く)使用できるようになる機能を持つときにそのプログラミングのスタイルをサポートする」と定義しています。

一方で、そのようなプログラムを書くのに異常な努力や異常な技能を必要とする言語はその手法をサポートしないと言い、その言語は単にその手法の使用を可能にするだけであると定義しています。

この点を明確にした上で、まずオブジェクト指向でないデータ隠蔽やデータ抽象を紹介してその後オブジェクト指向プログラミングとは何なのかを示しています。そしてその後、データ抽象やオブジェクト指向プログラミングをサポートするために必要な機能を紹介して、さらには既存のマシンやOSで実現する上での制約も示しています。

データ隠蔽 そしてデータ抽象

データ隠蔽というのはデータの実装を隠してしまって、データの操作のみを公開するものです。例として整数のスタックをJavaで書いてみると次のようになります(ここではまだオブジェクト指向でない、Javaとしては不自然な書き方をします)。

public class IntStackModule {
    private static final int SIZE = 1024;
    private static int[] stack = new int[SIZE];
    private static int top = 0;

    public static void push(int value) {
        stack[top++] = value;
    }

    public static int pop() {
        return stack[--top];
    }
}

スタックの実装は外部から隠蔽されて、pushとpopというメソッドだけが公開されています。

ではここで複数のスタックを扱えるようにしてみましょう。データ隠蔽ではデータを1つのモジュールの中に全て閉じ込めますので、スタックIDからスタックへのマップを持つようにします。

public class IntStackModule {
    private static final int SIZE = 1024;
    private static Map<StackID, int[]> stacks
        = new HashMap<StackID, int[]>;
    private static Map<StackID, int> tops
        = new HashMap<StackID, Integer>;

    public static class StackID {
    }
    
    public static StackID createStack() {
        ...
    }

    public static void push(StackID id, int value) {
        ...
    }

    public static int pop(StackID id) {
        ...
    }

    public static void destroy(StackID id) {
        ...
    }
}

一応使えるようになりました。でもこのスタックは他のデータ型と異なるデータ管理をしています。スタックの削除を自分で忘れずにやらないといけないですし、スタックを削除した後にそのスタックにアクセスするようなコードを書いても実行時まで気付きません。本来ならJavaにはGCがあるのでこのようなことは気にしなくてもよいはずです。

そこでデータ抽象を導入します。データ抽象というのは新しいデータ型を他のデータ型と同じように使えるようにすることです。データ抽象を使ってスタックを書くと次のようになります。

public class IntStack {
    private static final int SIZE = 1024;
    private int[] stack = new int[SIZE];
    private int top = 0;

    public void push(int value) {
        ...
    }

    public int pop() {
        ...
    }
}

大分オブジェクト指向プログラミングに近づいてきましたね。

データ抽象の問題

データ抽象で今度は図形クラスを定義してみます。まだオブジェクト指向じゃないので継承とかは使えません。

public class Shape {
    private static enum Type {
        Rectangle, Circle, ...
    }
    private Type type;
    private int x;
    private int y;
    private int width; // 矩形用
    private int height; // 矩形用
    private int radius; // 円用
    ...

    public Shape(...) {
        ...
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
    
    public void draw(Canvas canvas) {
        switch (type) {
        case Rectangle:
            ...
        case Circle:
            ...
        ...
        }
    }
}

データ抽象では、1つのShapeクラスが全種類の図形について知らなければなりません。そしてプログラムを変更するにはShapeクラスを直接変更するしかありません。これは不便です。

オブジェクト指向プログラミング

問題はgetXやgetYのような図形一般の性質と、各図形固有の性質を分けて書けなかった点です。そしてこの2つの区別を表現してその利点を活用するのがオブジェクト指向プログラミングであると定義しています。

では図形クラスをオブジェクト指向で書いてみましょう。といってもオブジェクト指向言語のプログラマの方には何のこともないいたって普通の定義です。

public abstract class Shape {
    private int x;
    private int y;

    public Shape(...) {
        ...
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
    
    public abstract void draw(Canvas canvas);
}

public class Rectangle extends Shape {
    private int width;
    private int height;

    public Rectangle(...) {
        ...
    }

    public void draw(Canvas canvas) {
        ...
    }
}

public class Circle extends Shape {
    private int radius;

    public Circle(...) {
        ...
    }

    public void draw(Canvas canvas) {
        ...
    }
}

データ隠蔽から始めて無事オブジェクト指向プログラミングまで戻ってこられました。

まとめ

ここではオブジェクト指向プログラミングの定義の部分に絞って駆け足で紹介しました。元論文にはデータ隠蔽・データ抽象・オブジェクト指向プログラミングがどんなプログラミングパラダイムなのかもう少し詳細に書いてありますし、実装する上で必要な機構についても論じています。また、その機能を使わない場合にはオーバーヘッドはなるべく無いようにするとか、ユーザも使わない機能は勉強しなくてもいいようにするとか、現在のC++の設計の基礎となっている考え方も紹介されています。オブジェクト指向プログラミングってなんだろうと疑問に思っていた人はぜひ読んでみてください。

大まとめ

以上、オブジェクト指向プログラミング関連の論文3本でした。どれも古い論文で今となっては当たり前のことも含まれていますが、改めて読んでみるとけっこうおもしろいことが書いてあったり、今まで伝聞でなんとなくしか知らなかったことがちゃんと分ったりします。

続いては@chunjpさんです。