JavaScriptで説明するオーバーロード解決

型クラスの話をしました。

• 入門的ではない型クラスの話：Haskellの型クラスがぁ (´^｀;)
• オーバーロードは何故にかくも難しいのか：Haskellの成功と失敗
• Haskellの型クラスに関わるワークアラウンド

Haskellの型クラスは元祖・型クラス*1なんですが、なんか残念な仕様です。整合性が歪んでいる理由は、オーバーロード機能を優先しているからです。その分、構造としての型を記述する機能は犠牲になっています。トレードオフだから仕方ないけど。

ところで、オーバーロードの解決（多義性の解決）って、どうやるんでしょうか？ そのメカニズムをJavaScriptのサンプルコードを使って説明します。

なお、「多相とオーバーロードはどう違うか」とかの話は、どうでもいい割に議論すると消耗してバカバカしいので一切触れません。（ちなみに、「並列と並行の違い」なんて議論も時間の無駄。暇つぶし以上の意味はない。）

内容：

1. オーバーロード
2. C++の仮想関数テーブル
3. 型情報を引数として渡す
4. 実装関数のまとめ方を変えてみる
5. Haskellの型クラス
6. 最後に

オーバーロード

オーバーロード（overload(ing)）とは、単一の記号・名前を異なる複数の意味で使用することです。異なる複数の意味を持つ記号・名前を多義的記号・名前（overloaded symbol/identifier）と呼びます。この記事で扱う記号・名前は関数名だけです。話題は多義的関数名ですね。

JavaScriptでは、次のようにして名前と意味（関数の実体）を結びつけます。

var times = function(n, m) {return n*m};

次の例は、timesという名前に異なる2つの関数を結びつけようとしています。

// 数の掛け算
var times = function(n, m) {return n*m};
// 文字列の繰り返し連接
var times = function(s, m) {
              var r = "";
              for (var i = 0; i < m; i++) {r += s};
              return r;
            };

しかし、最初の定義は二番目の定義で上書きされてしまい、同時に2つのtimesは存在できません。timesという1つの名前に2つの機能を持たせたいなら、次のように書けます。

var times = function(x, m) {
  // 数の掛け算
  if (typeof x === 'number') {return x*m}
  // 文字列の繰り返し連接
  if (typeof x === 'string') {
    var r = "";
    for (var i = 0; i < m; i++) {r += x};
    return r;
  }
  throw "Type Error";
};

実行時の型振り分け（type case）が出来ないプログラミング言語や、「引数の型は、数か文字列かハッキリしないとダメ」と融通が効かないプログラミング言語では、こうはいきません。

そもそも、人間がif文／case文で振り分けるのはひど過ぎます。もっとマシな方法が欲しいですよね。オーバーロード機能は、1つの名前に対する異なる複数の意味を上手に管理するメカニズムを提供します。多義的記号・名前（ここでは多義的関数名）に対して、適切な意味を決定します。この「意味の決定」がオーバーロードの解決です。

C++の仮想関数テーブル

まず、C++や同系統の言語で使われているvtbl（仮想関数テーブル）方式を見てみましょう。

// overload-sample.cpp
#include <iostream>

class Base {
public:
    void hello() {
        std::cout << "Hello, world.\n";
    }
    virtual void introduceMyself() {
        std::cout << "Hi, my name is Base.\n";
    }
};

class Derived : public Base {
public:
    // 明示的に宣言しなくても、このメソッドはvirtual
    void introduceMyself() {
        std::cout << "Yo, I'm Derived.\n";
    }
    void morning() {
        std::cout << "Good morning, world.\n";
    }
};

int main() {
    Base *p1 = new Base();
    Base *p2 = new Derived();
    Derived *p3 = new Derived();
    p1->hello();
    p1->introduceMyself();
    // p1->morning(); // Baseはmorning()を持たないのでコンパイルエラー
    p2->hello();
    p2->introduceMyself();
    // p2->morning(); // Baseはmorning()を持たないのでコンパイルエラー
    p3->hello();
    p3->introduceMyself();
    p3->morning();
    return 0;
}

コンパイルして実行すると：

$ g++ overload-sample.cpp
$ ./a.exe

Hello, world.

Hi, my name is Base.

Hello, world.

Yo, I'm Derived.

Hello, world.

Yo, I'm Derived.

Good morning, world.
$

上記のC++コードをJavaScriptにコンパイルするなら、次のようになるでしょう。

/*
 * class Base
 */
function Base_hello(_this) {
  console.log("Hello, world.\n");
}

var vtblBase = {
  "introduceMyself" : function(_this) {
    console.log("Hi, my name is Base.\n");
  }
};

// Baseのコンストラクタ
function Base() {
  this.vptr = vtblBase;
}

/*
 * class Derived
 */
var vtblDerived = {
  "introduceMyself" : function(_this) {
    console.log("Yo, I'm Derived.\n");
  }
};

function Derived_morning(_this) {
  console.log("Good morning, world.\n");
}

// Derivedのコンストラクタ
function Derived() {
  this.vptr = vtblDerived;
}

/*
 * main
 */
function main() {
  var p1 = new Base();
  var p2 = new Derived();
  var p3 = new Derived();
  Base_hello(p1);
  p1.vptr["introduceMyself"](p1);

  Base_hello(p2);
  p2.vptr["introduceMyself"](p2);

  Base_hello(p3);
  p3.vptr["introduceMyself"](p3);
  Derived_morning(p3);
  return 0;
}

ブラウザのJavaScriptコンソールで実行すると：

> main()

  Hello, world.

  Hi, my name is Base.

  Hello, world.

  Yo, I'm Derived.

  Hello, world.

  Yo, I'm Derived.

  Good morning, world.

  0

コンパイルの要点をまとめると：

1. 仮想でないメソッドは大域関数にコンパイルする。クラス名を接頭辞にすることによりオーバーロードは（コンパイル時に静的に）解決される。
2. メソッドに対応する大域関数の最初の引数にはthisオブジェクトが入る。今回の例では第1引数が使われてないが、インスタンスオブジェクトのデータメンバー（フィールド、プロパティ）にアクセスする際に第1引数が必要。
3. 仮想メソッドの実装関数は、クラスごとの仮想関数テーブル（vtblBaseとvtblDerived）に格納される。単一の仮想メソッド名に対する複数の実装が、複数のテーブルに分散されて格納される。
4. オブジェクトには、vptrというデータメンバーがあり、所属するクラスの仮想関数テーブルを指すように初期化される。
5. 仮想でないメソッド呼び出しは、対応する大域関数を呼び出す。
6. 仮想メソッド呼び出しは、インスタンスオブジェクトのvptrからvtbl（仮想関数テーブル）を特定し、関数名をキーにして実装関数を引いて実行する。こうして仮想メソッドのオーバーロードが（実行時に動的に）解決される。

仮想メソッドの呼び出しは、p.vptr["methodName"](p) という形ですが、C言語で書くなら (p->vptr)[METHOD_NAME](p) のようになります。METHOD_NAMEは文字列名前ではなくて番号です。p->vptrが仮想関数テーブルの先頭になるので、テーブル（配列）へのインデックスアクセスです。

多重継承があるともっとややこしくなりますが、同じ名前に複数の実装があるときの決定方式の基本はこんな感じです。

型情報を引数として渡す

先に例に出したtimesの例をもう一度考えてみます。

// 数の掛け算
function times(x:number, m:number) {return x*m}

// 文字列の繰り返し連接
function times(x:string, m:number) {
  var r = "";
  for (var i = 0; i < m; i++) {r += x};
  return r;
}

前と少し違っているのは、関数の引数に型宣言が付いていることです（TypeScriptならこう書けます）。呼び出すときに第1引数の型が分かれば、どちらの実装を動かすかを判断できます。

もし第1引数がvptrを持つオブジェクトであるなら、C++のvtbl（仮想関数テーブル）方式がそのまま使えます。次のようにコンパイルすればいいでしょう。

var vtblNumber = {
  "times": function (x, m) {return x*m}
};

var vtblString = {
  "times": function (x, m) {
    var r = "";
    for (var i = 0; i < m; i++) {r += x};
    return r;
  }
};

function times(x, m) {
  return x.vptr["times"](x, m);
}

しかし、数値データはvptrのようなメタ情報を持ってないのが普通です。vptrがなければ、第1引数からvtblを知ることは出来ません。もしコンパイラや実行環境が第1引数の型を知っているなら、その型のvtblを、呼び出す関数に渡してあげればいいでしょう。関数は、vtblを受け取る引数を余分に持つことになります。

var vtblNumber = {
  "times": function (x, m) {return x*m}
};

var vtblString = {
  "times": function (x, m) {
    var r = "";
    for (var i = 0; i < m; i++) {r += x};
    return r;
  }
};

function times(vptr, x, m) {
  return vptr["times"](x, m);
}

> times(vtblString, "A", 4)

  "AAAA"

> times(vtblNumber, 3, 4)

  12

この方式だと、timesという名前の関数は実際に存在します。次の特徴があります。

1. 元の第1引数の型情報（この場合はvtbl）を渡すための引数が追加されている。
2. この関数は実際の仕事はしない。型情報を使って実装関数を特定して仕事を振り分けるだけ。

実装関数のまとめ方を変えてみる

前の節の例で、オーバーロードされた関数（多義的名前を持つ関数）timesの実装関数（実際の仕事を行う関数）は、vtblString["times"] と vtblNumber["times"] でした。引数の型ごとにvtblを作ってました。実装関数のまとめ方、つまりvtblの編成方法を変えてみみます。

var vtblTimes = {
  "number": function (x, m) {return x*m},
  "string": function (x, m) {
    var r = "";
    for (var i = 0; i < m; i++) {r += x};
    return r;
  }
};

function times(typeId, x, m) {
  return vtblTimes[typeId](x, m);
}

> times("string", "A", 4)

  "AAAA"

> times("number", 3, 4)

  12

型ごとにvtblを作るのではなくて、多義的関数名に対してひとつのvtblを作っています。この場合、vtblから特定の実装関数を選び出すキーは型名になります*2。

オブジェクト指向だと、メソッドは型（クラス）に“所属する”イメージがあります。実際、型ごとにvtblが作られます。しかし、多義的関数ごとにvtblを持ってもかまいません。なんだったら、単一のvtblにすべての実装関数を詰め込んだっていいです。

var vtbl = {
  "times" : {
    "number": function (x, m) {return x*m},
    "string": function (x, m) {
      var r = "";
      for (var i = 0; i < m; i++) {r += x};
      return r;
    }
  },
  "addOne" : {
    "number": function (x) {return x + 1},
    "string": function (x) {return x + "One"}
  }
};

function times(typeId, x,  m) {
  return vtbl["times"][typeId](x, m);
}
function addOne(typeId, x,  m) {
  return vtbl["addOne"][typeId](x, m);
}

> times("number", 3, 4)

  12

> times("string", "A", 4)

  "AAAA"

> addOne("number", 5)

  6

> addOne("string", "hello")

  "helloOne"

いずれの場合でも、timesの第1引数（型情報）は、コンパイラ／インタプリタが自動的に計算し埋めるので*3、ユーザー（プログラマ）からは見えなくなります。

Haskellの型クラス

さて、Haskellの型クラスです。次を例題とします。

import Data.Maybe

class Eql a where
  eql :: a -> a -> Bool

class (Eql a) => TotOrd a where
  lt :: a -> a -> Bool

instance Eql Int where
  eql n m = n == m

instance TotOrd Int where
  lt n m = n < m

member :: (Eql a) => a -> [a] -> Bool
member x [] = False
member x (y:ys) = if eql x y then True else member x ys

findGe :: (TotOrd a) => a -> [a] -> Maybe a
findGe x []  = Nothing
findGe x (y:ys) = if eql x y || lt x y then Just y else findGe x ys

既に定義済みのEq, Ordとかぶらないように、例題の型クラスはEql, TotOrd（total order）としています。話を簡単にするために、関数の最初の引数*4の型だけを見てオーバーロードを解決することにします。また、リスト型のような型パラメータを持つ型（型構成子）は扱いが面倒なので割愛します。

Haskellとオブジェクト指向の用語法にズレがあるので注意しましょう。

Haskell	オブジェクト指向言語
型クラス	インターフェイス
型インスタンス	インターフェイスを実装したクラス
データ値	オブジェクト

Haskellの場合もvtblと同様なテーブルを使いますが、テーブルを辞書（dictionary）と呼びます。多義的関数は、辞書を引数にもらって仕事の振り分けをします。型クラスで宣言されたメソッド名（多義的関数名）ごとに、振り分け関数を作ります。JavaScriptにしてみると：

/*
class Eql a where
  eql :: a -> a -> Bool
*/
function eql(dic, x, y) {
  return dic["eql"](x, y);
}

/*
class (Eql a) => TotOrd a where
  lt :: a -> a -> Bool
*/
function lt(dic, x, y) {
  return dic["lt"](x, y);
}

型インスタンス宣言ごとに1つの辞書を作ります。dicXxxという名前で辞書を作ることにします。ただし、「EqlクラスのInt」と「TotOrdクラスのInt」のように、同じデータ型が複数の型クラスに属するので、辞書のネーミングパターンは、dic〈型クラス名〉$〈データ型名〉にします。

/*
instance Eql Int where
  eql n m = n == m
*/
var dicEql$Int = {
  "eql": function(n, m) {return n == m}
}

/*
instance TotOrd Int where
  lt n m = n < m
*/
var dicTotOrd$Int = {
  "lt": function(n, m) {return n < m}
}

これで、多義的関数を使う準備は出来ました。コンパイラは、多義的関数の名前とその多義的関数の所属するクラスを記憶してます。

コンパイラが、多義的関数を内部で使っているユーザー定義関数を見つけると、その関数を次の方針で書き換え（プログラム変換し）ます。

• ユーザー定義関数に、辞書を渡す引数を追加する。
• 多義的関数の呼び出しに対して、辞書を渡すようにする。

member関数は内部でeqlを使用してるいるので、Eql型クラスの辞書を必要とします。次のようになります。

/*
member :: (Eql a) => a -> [a] -> Bool
member x [] = False
member x (y:ys) = if eql x y then True else member x ys
*/
function member(dicEql, x, ys) {
  if (ys.length === 0) {return false}
  var y = ys.shift();
  if (eql(dicEql, x, y)) {
    return true;
  } else {
    return member(dicEql, x, ys);
  }
}

> member(dicEql$Int, 3, [1, 2, 3, 4])

  true

> member(dicEql$Int, 3, [1, 2, 0, 4])

  false

ユーザー定義関数が、色々な多義的関数を使っていて、それらが複数の型クラスに属するとき、複数の辞書を渡す必要があります。findGe関数は、Eql型クラスのeql多義的関数と、TotOrd型クラスのlt多義的関数を使っています。したがって、findGe関数のコンパイル結果は2つの追加引数を持ちます。

/*
findGe :: (TotOrd a) => a -> [a] -> Maybe a
findGe x []  = Nothing
findGe x (y:ys) = if eql x y || lt x y then Just y else findGe x ys
*/
function findGe(dicEql, dicTotOrd, x, ys) {
  if (ys.length === 0) {return null}
  var y = ys.shift();
  if (eql(dicEql, x, y) || lt(dicTotOrd, x, y)) {
    return y;
  } else {
    return findGe(dicEql, dicTotOrd, x, ys);
  }
}

> findGe(dicEql$Int, dicTotOrd$Int, 3, [1, 2, 3, 4])

  3

> findGe(dicEql$Int, dicTotOrd$Int, 3, [1, 2, 0, 4])

  4

> findGe(dicEql$Int, dicTotOrd$Int, 3, [1, 2, 0, 1])

  null

実験では手動で辞書を渡していますが、コンパイラの型推論機能によりどの辞書を渡すかは決定できるので、ユーザー（プログラマ）からは辞書のやり取りは見えなくなります。

最後に

オーバーロード機能を使うために、そのメカニズムを知っている必要はありません。しかし、日常的比喩や衒学的ウンチクで解釈しようとすると、無意味な思弁的考察や不毛な議論に陥ったりします。僕は、そのテの似非哲学的な能書きをだいぶ嫌っているので、ドライなメカニズムから理解するアプローチになります。

メカニズムの観点から見れば、「多相」と呼ぼうが「オーバーロード」と呼ぼうが、オブジェクト指向だろうが関数型だろうが、そんな区分は別にどうでもいいじゃん、と思います。

*1:"How to make ad-hoc polymorphism less ad hoc" Philip Wadler and Stephen Blott (1988) で提唱されてすぐに実装されたので、既に四半世紀を越える使用実績です。

*2:CLOS（Common Lisp Object System) の総称関数では、実装関数へのディスパッチを高速化するため、総称関数ごとにメモ化テーブル（キャッシュ）を持たせてました。（今でもそうかな？）

*3:Coqでは、暗黙の引数を自動的に埋めるか、ユーザーが手で指定するかを制御できます。@funcのようにアットマークを付けると、手動の引数渡しになります。

*4:Haskellの関数はカリー化されているため、引数と言えば最初の引数だとも言えます。