リネームとサブタイプと置換原則

みずしまさんから、一言ではこたえにくいご質問・ご意見をいただいたので、この機会に新しいエントリーを書きます。自分用メモも兼ねており、以前書いたエントリーへのリンクをたくさん含んでいます。

「なんで多重継承はそんなに嫌われるのか？ ちょっくら分析してみるか」において、リスコフの置換原則を引き合いに出しました。リスコフの置換原則については、「クラス継承、リスコフの置換原則、部分集合の型」でも述べています。しかし僕は、リスコフ女史が本来どういう意図と表現で、どのような言明をしたかを正確には知りません。間接伝聞で誤解しているかも。

ですが、「本来」の詮索はおいといて、「リネームとサブタイプと置換原則」にまつわる状況を実例付きで説明することにします。「インスティチューション」という言葉を表だっては出しませんが、僕の気持ちとしては、インスティチューション入門も意図しています。「もっと型理論」の続きみたいな感じかな。

内容：

1. 言葉と記法の準備
2. インターフェースの実例
3. リネーム
4. 指標射
5. モデル（＝実装クラス）のリダクト操作
6. セオリーでプログラマの気持ちを表す
7. もう一回くらいは続くでしょう

●言葉と記法の準備

毎度毎度愚痴っていることですが、用語法がいっぱいありすぎてやんなる。おおざっぱな対応表↓

オブジェクト指向	代数／余代数	計算科学（の一流派）
インターフェース	演算子記号一式	指標
型の名前	-	ソート
クラス	余代数	モデル
状態空間	台集合	-
制約、契約	公理系	仕様、セオリー

僕が割とよく使う言葉は：

• インターフェース＝指標
• インターフェースの実装クラス＝指標のモデル
• クラスの制約条件＝表明＝仕様

「セオリー」って言葉は次の意味で使います； 適当な演繹系（deductive/deduction/proof system）を想定して、論理式で書かれた仕様から導出（形式的に証明）される論理式の全体をセオリーと呼ぶ。セオリーTは演繹で閉じた集合になります（A⊆T, A|-ψ ならば ψ∈T。ψは論理式）。

以下で、「インターフェース（＝指標）」のように、丸括弧と等号で同義語／類義語を示すことにします。

ソート、指標、セオリーについては、

• ソートと指標と型、実例をまじえて

で述べています。上記エントリーの説明でだいたい間に合うと思いますが、実はこの話題は何度も扱っていて、

• 極大（無矛盾）セオリー

が、記号論理から見ての記述です。ただし、

• 「完全性／不完全性」は多重定義のし過ぎ！
• 極大と無矛盾は冗長表現ではなかった

に補足があるので、正確さを気にかけるなら、これらも目を通したほうがいいかもしれません。

• 論理とはなにか？ (3)

にも、別な角度からのセオリーの説明があります。（「論理式、演繹系、セオリー」に補足を書きました。）

• 古典論理は可換環論なんだよ

は、セオリーの代数的な扱いです（プログラミングの話には、たいてい不要）。その手短なまとめとしては、

• 仕様、公理系、セオリー

に対応表があります。

●インターフェースの実例

次のインターフェース（＝指標）を考えます。

interface AB {

 int a();

 void b();

}

それと、次のインターフェース：

interface IJK {

 boolean i();

 void j();

 int k();

}

こんなものを見せられても何のイメージも湧かないでしょ。そうです、インターフェースというものは本質的にまったく無意味なものです。それでも、int, void, booleanに意味を見いだす人がいるかもしれないので、いっそ、次のようにしましょうか。

interface AB {

 t a();

 u b();

}
interface IJK {

 s i();

 u j();

 t k();

}

記号の集合S = {s, t, u}をソートの集合と呼びます。S^*×S（上付き星はクリーネスター）の元((α₁, ..., α_n), β)を、α₁, ..., α_n->β とも書き、プロファイルと呼びます*1。α₁, ..., α_n, β は、s, t, uのどれかです。

そうすると、インターフェース（＝指標）とは、メソッド名（＝演算子記号）にプロファイルを対応させたものです。ABやIJKは、次のような関数（＝写像）とみなせます。

AB : {a, b} → S*×S

 AB(a) = (->t) = ((), t)

 AB(b) = (->u) = ((), u)
IJK : {i, j, k} → S*×S

 IJK(i) = (->s) = ((), s)

 IJK(j) = (->u) = ((), u)

 IJK(k) = (->t) = ((), t)

別な言い方をすると、インターフェースとは、メソッド名（＝演算子記号）集合と、それに付随したプロファイル割り当てのことです。例に出てきたプロファイルはやたらに簡単ですが、(t, t->t) = ((t, t), t), (s, t, t->s) = ((s, t, t), t) とかもプロファイルです。

●リネーム

リネームとは、記号集合の各記号に別の記号（たまたま同じ記号でもよい）を対応させることです。rename oldName to newName または use oldName as newName を、newName |→ oldNameで表しましょう。oldNameとnewNameの順序が逆みたいですが、このほうが少し楽ができます。（[追記]と書きましたが、向きはあまり気にしないほうがいいです。この節の最後の追記も参照。[/追記]）

例えば、新しい記号集合{peek, next}の記号peekとnextに、peek |→ a, next |→ b と対応させることがリネームです。このリネーム、つまり rename a to peek, rename b to next に従って interface AB の内容を書き換えてみると：

 ï½”peek();

 u next();

これは、写像とみなしたリネーム{peek |→ a, next |→ b}と、写像とみなしたインターフェース（＝指標）{a |→(->t), b |→ (->u)}の結合（＝合成）として得られたインターフェースです。「少し楽ができます」とは、この定式化のことです。

ただし、ややこしいことには、型の名前（＝ソート）のリネームは、oldSort |→ newSort と考えたほうがいいのです（でも、あまり気にしなくていいです）。例えば、S = {s, t, u}に対して、{s |→ boolean, t |→ int, u |→ void } というリネームをABに施すと：

 int a();

 void b();

メソッド名（＝演算子記号）も型の名前（＝ソート）もリネームして、ABというインターフェース名自体もByteInputStreamにリネームすると、

interface ByteInputStream {

 int peek();

 void next();

}

名前の効果は実に恐ろしい！ これで明確なイメージを持ってしまう人がいるでしょう。が、そのイメージが正しいなんて保証も根拠もどこにもありません。interface AB が無意味であったのと同様に、interface ByteInputStream も無意味なのです。このあたりの話は：

• 今風の型理論入門（本編）
• デュアルプログラミングとエクソシストゲーム

に書いてあります。

[追記]リネームを写像と考えるとき、上で述べたように NewNames → OldNames と考えるのが便利なときもありますが、これはケースバイケースです。次節で導入する指標射は、OldNames → NewNames になっています。エイリアスまで考えると、NewNames → OldNames という部分写像（未定義があってもよい写像）とするのが一般性がありますが、まー、その場その場で向きを適切に選べばいいでしょう。[/追記]

●指標射

リネームは記号集合のあいだの写像なので、σ:{peek, next} → {a, b}とかρ:{s, t, u} → {boolean, int, void}のようにも書きます。

以下では、ソートの集合Sとしては、いかにも無意味な{s, t, u}はやめて、S = {boolean, int, void}に戻して、3つのソート記号には常識的な意味を割り当てます。もう無意味な記号ではなくて、「あのboolean」「あのint」「あのvoid」と思っていいですよ。ただし、インターフェース（＝指標）のメソッド名（＝演算子記号）は相変わらず無意味です。

これから、以下の2つのインターフェース（＝指標）を例に使いましょう。

interface ByteInputStream {

 int peek();

 void next();

}
interface IJK {

 boolean i();

 void j();

 int k();

}

interface ByteInputStream のメソッド名（＝演算子記号）の集合{peek, next}から、interface IJK のメソッド名（＝演算子記号）の集合{i, j, k}への写像{peek |→ k, next |→ j}を考えます。この写像はリネームみたいなもんですが、次の特徴を持ちます。

1. 前もって定義されていた2つのインターフェース（＝指標）の、メソッド名（＝演算子記号）集合のあいだの写像である。
2. 写像として単射である*2。
3. だが、全単射（双射）である必要はない。
4. メソッド名（＝演算子記号）への型（＝プロファイル）割り当てを保つ。

上の条件を満たすメソッド名（＝演算子記号）の集合のあいだの写像を指標射（signature morphism）と呼びます。指標射は、σ、ρ、τなどのギリシャ小文字で表現するのが慣例です。σ = {peek |→ k, next |→ j}とすると、これは指標（＝インターフェース）ByteInputStreamから指標IJKへの指標射なので、σ:ByteInputStream → IJK とも書きます。矢印記号がいろいろな意味で多用されているので注意してください。

●モデル（＝実装クラス）のリダクト操作

いま、interface IJKの実装クラスFooIJKがあったとします。

class FooIJK implements IJK {

  public boolean i() {

    return true;

  }

  public void j() {}

  public int k() {

    return 0;

  }

}

このFooIJKは、当然にinterface ByteInputStreamの実装クラスにはなっていません。しかし、与えられた指標射 σ = {peek |→ k, next |→ j} に従って、ByteInputStreamの実装クラスを機械的に作り出すことができます。

class FooByteInputStream implements ByteInputStream {

  private final IJK ijk;

  public FooByteInputStream() {

    ijk = new FooIJK();

  }

  public int peek() {

    return ijk.k(); // peek |→k

  }

  public void next() {

    ijk.j(); // next |→ j

  }

}

指標射σとFooの実装FooIJKから、ByteInputStreamの実装FooByteInputStreamが必ず作れます。このため、作られた実装FooByteInputStreamを、σ^*(FooIJK) とか FooIJK|_σとか書きます。そして、FooIJKからFooByteInputStreamを作り出す操作を、指標射σに沿ったリダクト（reduct）操作*3といいます。リダクトとは、実装の本体には手を加えずインターフェース（メソッド名）だけを変更することです。GoFのAdapterパターンですね。

指標（＝インターフェース）の実装をモデルとも呼びます。そして、任意の指標Σ(総和ではなくて、単なるギリシャ大文字）のモデルの全体をMod[Σ]と書きます*4。Mod[IJK]は、interface IJKの実装クラスの全体、Mod[ByteInputStream]は、interface ByteInputStreamの実装クラスの全体です。

指標射σ:ByteInputStream → IJK に対するリダクト操作σ^*は、Mod[IJK]に属するIJKのモデル（実装）に、Mod[ByteInputStream]に属するByteInputStreamのモデルを対応付けるので、σ^*:Mod[IJK] → Mod[ByteInputStream]という写像になります。σとσ^*では、矢印の向きが逆転していることに気を付けてください*5。

●セオリーでプログラマの気持ちを表す

ここからがやっと本論です。

interface ByteInputStream と interface IJK は、IJKのほうがメソッドが多いですが、peek ←→ k, next ←→ j と対応付ければ似たようなものです。

interface ByteInputStream {

 int peek();

 void next();

}
interface IJK {

 boolean i();

 void j();

 int k();

}

しかし、IJKをいきなり見せられたときと、ByteInputStreamをいきなり見せられたときでは、心理的な印象は異なります。また、使用例として次の２つのメソッドを示されたらどうでしょう。

// ByteInputStream bisの使用例

int readByte() {

 int x = bis.peek();

 bis.next();

 return x;

}
// IJK ijkの使用例

int h() {

 int x = ijk.k();

 ijk.j();

 return x;

}

IJKは謎のままですが、ByteInputStreamがなんであるかは「分かってしまった」つもりになります。これは、名前の効果です。では、名前がどのような効果をもたらしているか、フォーマルに定式化できるでしょうか？

名前からなにかを連想して意味を理解してしまうのはプログラマの心のなかで起こる現象です。それをマジメに定式化するのはとてつもなく難しいことです。なので、ここでは安直な仮定を設けます。その仮定とは、「人間の知的能力は論理機械とみなせる」というものです。これは作業仮説で、僕も本気で信じているわけではありません。

この作業仮説に従えば、名前や事例から、論理式（logical formula/statement/sentence）の集合がプログラマの心のなかに生まれることになります。論理式の集合をセオリーと呼びますから、プログラマの思い／期待／想定などはセオリーとして定式化できることになります。

interface ByteInputStreamは、暗黙にセオリーを伴っていると考えられます。一方のinterface IJKは、自然に発生するセオリーを持ってないわけです。名前／事例／説明などの効果も含めてインターフェースを取り扱いたいなら、単なる“無意味な構文”としてのインターフェースだけでなく、セオリーも一緒に考えたものを対象にする必要があります。ここでは、その対象＝セオリー付きインターフェースを仕様と呼ぶことにします。

無意味な構文としてのインターフェースの実装なら、その実装には何の条件も付きません。が、通常プログラマは意味を持つ仕様を実装しているのです。仕様にはセオリー＝論理式の集合が付いているので、それらの論理式（＝制約条件、表明）を満たすように気を使うのです。この状況については、

• 今風の型理論入門（本編）
• デュアルプログラミングとエクソシストゲーム

を見てください。

また、いま述べた仕様こそが“型概念”であることは、次のエントリーに書いてあります。

• もっと型理論
• 下層ほど複雑でリッチ -- 型階層

●もう一回くらいは続くでしょう

いままで説明した概念／言葉をまとめておきます。

オブジェクト指向	計算科学（の一流派）
インターフェース	指標
基本型の名前	ソート
メソッド名	演算子記号
メソッドの引数と戻り値の型	プロファイル
インターフェースのリネームを許す拡張	指標射
インターフェースの実装	指標のモデル
インターフェースの変換	リダクト
1つの制約条件	論理式
常識や了解事項なども含めた意味的制約	セオリー
インターフェースとその意味	仕様

素材はだいぶ揃ってきました。まだ説明してないのは、リダクト（＝インターフェースの変換）の双対である論理式（＝制約条件）の変換（トランスレーション）です。指標射にともなうリダクトとトランスレーションがハッキリと認識できれば、リネームや置換原則の状況を把握することができます。

もう一回あれば説明が一段落するかな。

*1:プロファイルは、メソッドのシグニチャにほぼ対応します。ですが、「シグニチャ」という言葉は指標と混乱するので使いません。

*2:[この注は削除]単射であることは本質的ではありません。リネーム以外にメソッド名のエイリアスも認めることにすれば、単射の条件を外せます。

*3:reductという単語は、普通の辞書には載ってないようです.

*4:ブラケットを使ったのは、Mod[Σ]がindexed categoryになるから。とはいっても、今回はMod[Σ]を圏とは考えずに、対象類であるモデルの集まりだけを相手にします。

*5:Modは指標の圏から、圏の圏Catへの反変関手になっています。今回は、Mod[Σ]はモデルの集合なので、Modは圏Setへの反変関手です。