実装から学ぶ型クラス…Groovyで型クラスを実現することを例にして

これは2014年のG*アドベントカレンダーの第23日目の記事のつもりでしたが、12時すぎてしまいましたorz。
f:id:uehaj:20141224031845p:plain:right:w200

HaskellやScalaやRustには型クラスという言語機能があり、個人的感想として、理解が難しかったものの一つです。いわく、インターフェースのようなもの。いわく、オープンクラスのようなもの、など。
わからなければ作ってみるのが一番です。なのでGroovyで型クラスを実装してみました。
ソースはこちら。
ただし実用的なものではなく、学習用です。また実装したのは概念のコア部分のみで、言語によって詳細は異なることに注意ください。

型クラスとは何か

型クラスとは、多相型・ジェネリクス型の型引数(仮型引数)に対して、「ある型に対して可能な操作の集合」を、制約として与え、またそれらの操作が可能であるという保証を、「クラスの継承関係」とは無縁の方法で与えるものです。

別の言い方で言うと、「クラスにデータを従属させる」「メソッドとデータを一体として管理する」「代入可能性を、クラス継承関係で与える」というようなOOPの考えかたの侵襲を拒否し、クラス継承を使用せずに、型引数を制約する方法です。

型クラスが無い場合、たとえばGroovyにおいてメソッドジェネリクスを使用した以下のコード

static<T> void runSomething(T a) {
   a.run()
}

を、正しいコードとして静的型チェックを通すためには、

static<T implements Runnable> void runSomething(T a) {
   a.run()
}

のように「TはRunnableを継承している」と指定します。Runnableという操作の集合による制約を、引数aの型Tに対して行ない、それによってaに対して特定の操作ができるという保証もしています。
これはこれで良いのですが、型クラスが必要になる動機は、ジェネリクス型変数の制約はしたいのだが、このようなクラス継承の使用を避けたいということです。

クラス継承による制約の何が嫌なのか

なぜ避けたいかといえば、

クラス継承がないから(Haskellの場合)
多相型変数Tを「<T extends XXX>」のように制限するためには、TがXXXのサブクラスか実装クラスとして宣言されている必要がある。もし、渡したい引数のクラスがもともとそのように定義されていない場合、
- Tとして渡すクラスのソースを変更してimplements XXXを追加したりメソッドを追加する。しかし使用用途によって都度クラス定義が変化させたり、追記していかなければならないのが嫌
- Tとして渡すクラスを継承し、XXXを実装するクラスを定義して、新規インスタンス作ってメンバをコピーして渡す。でもコピーでは意味が変わってしまうので嫌(ラッパーと同程度、もしくはそれ以上に嫌)。Scalaのnew with Traitも同様。
- Tとして渡すクラスから継承させることがなんらかの理由(プリミティブ型であったり、finalクラスである場合)で不可能だったり、嫌であるなら、以下の何れかの方法でラッパークラスを使う：
  - XXXを継承するクラスのメンバーとしてTを定義する。
  - Groovyのトレイトの動的proxy。
- →でもラッパーを導入するとアイデンティティが破壊されるのでいやだ。オーバーヘッドが嫌だ。
関数型プログラミングスタイルの一流派としてあり得る方針としての「データと関数の分離」に反するので嫌なのだ
「継承不要」「ラッパー不要」というのはパラメトリック多相*1で普通にできていた話なのに、制約を付けようとした時点で必要になるというのは嫌だ。なるべく同じようにやりたい
なんでもクラスにするという基本方針がそもそもの間違いで、どう覆い隠そうとしてもシンプルさが損なわれる(本質的批判)
オブジェクトが保持するvtableへのリファレンスなどのメモリコスト、vtableを介在したメソッド呼び出しの実行時コストを避けたい*2。また、データ型のメモリイメージ表現のC言語などとの互換性を常に保持したい*3。
仮想関数による多態性イラネ。ていうより、原語では同じ単語で多相性とかぶってるかぶってる。
操作のレシーバーという概念は非対称でいやだ。レシーバーと他の引数、戻り値の型に非対称性があり、数学的概念の記述などでの一般性を阻害する

など。まるでイヤイヤ期の幼児のような、嫌だ嫌だ、の連発です。まあ嫌なのだからしょうがない。私もこう列挙されると嫌な気になってきます。

型クラスの仕組みの4段階

型クラスの仕組みを以下の4段階で考え、Groovyで実装していきます。

(1)型クラスを定義する
(2)型クラスのインスタンス化
(3)型クラスで制約した多相型引数を含む型の引数をとる関数を定義する
(4)型クラスで制約した多相型引数を含む型の引数をとる関数を呼び出す

それぞれに付いてモノイド型クラスのコードを例にして解説します。
ちなみに、今回サンプルとしては以下の型クラスを作っています。

型クラス

interface Monoid<T> {
interface Functor<F> {
interface Applicative<A> extends Functor<A> {
interface Monad<M> extends Applicative<M> {
interface Show<T> {
trait Eq<T> { // One of eq or neq, or both should be overriden.
trait Ord<T> extends Eq<T> {

インスタンス
class OptionalMonoid<T> implements Monoid<Optional<T>> {
class ListFunctor implements Functor<List> {
class OptionalFunctor implements Functor<Optional> {
class ListApplicative extends ListFunctor implements Applicative<List> {
class ListMonad extends ListApplicative implements Monad<List> {
class IntShow implements Show<Integer> {
class StringShow implements Show<String> {
class ListShow<T> implements Show<List<T>> {
class IntEq implements Eq<Integer> {
class IntOrd implements Ord<Integer> {

(1)型クラスを定義する

モノイド型クラスを定義します。型引数に適用する制約を定義するものです。

@TypeChecked
interface Monoid<T> {
    def T mappend(T t1, T t2);
    def T mempty();
}

このようにします。Tではなくdef Tなのは、なぜかそうしないとコンパイルが通らないから。
見るとわかるように普通のインターフェースです。ここでインターフェースにする理由は、継承が使えるからです。例えば、Monad extends Functorのように型クラスを継承することができます。

これは先程の「クラス継承を不要としたい」に反するように思えますが、実際にはthisからのオフセットによるインスタンス変数の参照やアクセス、thisを介した仮想テーブル(vtable)とその呼び出しの機構は完全に不要で、メソッド置き場として使っているにすぎません。なので、ここでクラス継承を使用するのは便宜的なもので、本来なら、staticメソッドにして、staticメソッドを継承階層をたどって探索してくれる仕組みをAST変換で作り込めば良いところです*4が、手をぬきます(Scalaではobjectにするところ)。Monoidはデータメンバを持たない(インターフェースなので持てませんが、classで実装したとしても持たせない)ことに注意ください。

ここでやっていることをまとめると、

操作の集合をクラスのインスタンスメソッドとして定義する。このクラスをジェネリクス型引数の制約として使用する。これが型クラスである。このクラスから継承したいかなるクラスにおいても、データをインスタンス変数として定義することはない(本質的)。
ここで定義したメソッドの間では相互に呼び出しあうことができる
メソッドの本体を別に定義しても良い。Groovyのtraitが便利に使えるだろう。

(2)型クラスのインスタンス化

型クラスのインスタンス化とは、制約を与えたいデータ型が、ある型クラス制約を満たす、という宣言であり、満たせるようにするための操作を補充します。
以下では、String型がMonoid型クラスの制約を満たすように、「StringのMonoid型クラスのインスタンス」を作成します。

def instance_Monoid_java$lang$String_ = new Monoid<String>() {
    @Override String mappend(String i1, String i2) {
        i1+i2
    }
    @Override String mempty() {
        ""
    }
}

型クラスのインスタンスを保持する変数名を、「instance_Monoid_java$lang$String_ 」という決められた規約に従うものにしておきます。これはスコープの探索をサボるためです。変数名がインスタンスを決め、同名のインスタンスがあれば、内側の物が勝ちます*5。この変数名の変数をstatic importすることも可能であることも期待します。

ここまでは、何の変哲もない標準のGroovyの機能で実現することです。

(3)型クラスで制約した多相型引数を含む型の引数をとる関数を定義する

さて、準備した型クラスMonoidの制約を使って、多相関数を定義してみます。
以下のようにします。

@TypeChecked
class Functions {
    static <T> T mappend(T t1, T t2, Monoid<T> dict=Parameter.IMPLICIT) { dict.mappend(t1,t2) }
    static <T> T mempty(Monoid<T> dict=Parameter.IMPLICIT) { dict.mempty() }
}

引数「Monoid<T> dict=Parameter.IMPLICIT)」が本実装における型クラス制約の宣言であり、意味は、mappendの返り値と、引数で使用する型変数Tは、Monoidという型クラスの制約を満たす必要がある、ということです。

dictは型クラスMonoid型の、型クラスのインスタンスが渡ってくる引数ですが、こちら側から見ると関数の名前空間だと思ってください。引数にあたえられた名前空間に転送します*6。複数の型クラスが引数に与えられたら区別して振り分けます*7。
IMPLICITは以下のように定義してあるただの定数で、AST操作の際のマーカーとして機能します。

class Parameter {
    static final Object IMPLICIT = null
}

ちなみにここで、mappend,memptyが型クラスインスタンスの同名メソッドを呼び出しているだけの関数なのは、無駄に感じるかもしれません。その意味では、ちょっと例がわるくて、Monoid型クラス制約のついた型引数を使った、任意の静的関数が定義できます。ここでmappendやemptyをstatic関数として定義してるのは、利便のため、ユーティティ関数としてこれらをstatic空間にexportしていると思ってください。Haskellだと、インスタンス宣言で、staticな型クラスインスタンスがモジュール内グローバルに存在を開始し、関数呼び出しはそのモジュール内グローバルな空間からマッチする名前が呼ばれることになるんですよね。このGroovy型クラス実装は、Scalaでも同様だと思いますが、名前空間として機能する型クラスインスタンスを明示的に扱うので、1つクッションが入る場合があるということです。善し悪しはあるでしょうが、Haskellの方がシンプルなのは確実です。

(4)型クラスで制約した多相型引数を含む型の引数をとる関数を呼び出す

ここからが、そしてここのみが、山場です。:)

先程定義した関数を呼び出します。以下のようにします。

import static Functions.*
 :
@TypeChecked(extensions='ImplicitParamTransformer.groovy')
  :
        String s = mempty()
        assert s == ""
        assert mappend("a","b") == "ab"

このコードが静的型チェックのもとでコンパイル・実行できます。

ソースコードの表面上は、関数定義での仮引数Monoid<T> dictに対応する実引数は与えていませんが、暗黙に型クラスのインスタンスが補充されて呼び出されます。これをやってるのが今回作ったImplicitParamTransformerであり、カスタム型チェッカ(型チェッカ拡張)でありながら、型チェッカであることを踏み越えて、以下を実行します。

ジェネリクス型を使っている静的メソッド呼び出しにおいて、その静的メソッド定義で「IMPLICIT」をパラメータ初期値で使用しているなら、そのパラメータに、ジェネリクス型から定まる変数名を挿入する。呼び出しが、「mappend("a","b")」であるなら、mappendの定義が

    static <T> T mappend(T t1, T t2, Monoid<T> dict=Parameter.IMPLICIT) { dict.mappend(t1,t2) }

であるので、実引数の型から型引数の実際の型を推論・解決させて、Tにjava.lang.Stringを束縛して、IMPLICITに対応する引数を、Monoid<String>型のinstand_Monoid_java$lang$Stringという名前の変数の参照に変換します。ついでに、ごく限定されたターゲット型推論を、「String s = mempty()」の形のとき実行し、

    static <T> T mempty(Monoid<T> dict=Parameter.IMPLICIT) { dict.mempty() }

では、戻り値が代入される変数の型がStringであることから、Mooid<T>の型がMonoid<String>であると推論させ、変数名を決定します。

最終的には、これらのmappend,memptyは以下の呼び出しと等価になり実行されます。

String s = mempty(instance_Monoid_java$lang$String_ )
assert s == ""
assert mappend("a","b",instance_Monoid_java$lang$String_ ) == "ab"

要はScalaのimplicitパラメータの機能を実行していることになります。Scalaの場合は変数名は無意味で型だけで探索するわけですが、特定の型を持った変数定義の探索が面倒なので変数名に型情報をエンコーディングしてスコープ解決させています。

直感的な説明

型クラスのざっくりイメージ的な理解の仕方としては、クラスベースOOPでは、データ型にvtableを組み込み不可分にしていたのを、ひっぺがして、動的な束縛機能を除去して、本当にそれが必要になる最後のタイミング、つまり多相関数呼び出しの時点まで結合を持ち越して、そしてその時点で多相型を解決の枠組みでインスタンスを選定し、別引数で渡し、関数の名前空間として使うということです。

他にやるべきこと

あとはいろんなシンタックスシュガーを導入できると思いますが、学習用としてはここらで打ち止めておきます。

問題点

不都合がありまして、モジュール化ができてません。たとえばEqクラスとかOrdクラスとかそれぞれを別クラスにしたかったのですが、一つの大きな誤算として、多相型のメソッドをstatic importしてもジェネリクス情報が得られません。

class Functions {
    static <T> T mappend(T t1, T t2, Monoid<T> dict=Parameter.IMPLICIT) { dict.mappend(t1,t2) }
      :

を、

import static Functions.mappend

すると、引数や返り値のジェネリクス情報が呼び出しコード上の処理段階で不明になります。なので(4)でのジェネリクスの推論ができません。解決策はなんでしょうね。クラスファイルに残っているジェネリクス情報をリフレクションとかでたどるんでしょうかね。たいへんなのでこれ以上の追求は個人的にはあきらめます。

おまけ： Higher-kind Generics

Groovyでは、型引数をとる型構築子を型引数に(いわゆる高階型変数(Higher-kind Generics))したときに期待する動作を行います。たとえば、今回以下のようなコードが書けています。

@TypeChecked
interface Applicative<A> extends Functor<A> {
    public <T> A<T> pure(T t)
    public <T,R> A<R> ap(A<Function<T,R>> func, A<T> a) // <*> :: f (a -> b) -> f a -> f b 
}

ここでAは引数を取れる型引数であり、たとえばMaybeやListなどを与えることができます。これはJavaのジェネリクスでは(少なくともJava8では)できないことです。これができることによって得られる抽象化能力は、非常に大きいものです。モナドはこれがあるから型クラスになり得るのです。

とはいえ、これをもってGroovyでHigher-kind Genericsができる、と言ってよいかどうかは、微妙です。というのも、しなければならないことは「期待する動作を行う」だけではないからです。具体的には、上記を継承するインスタンスで、上記のジェネリクス条件を満たさないオーバーライド定義したときに、型エラーになること、が必要だと思っています。実際試してみると、Groovy 2.4-beta-xでは期待したようにエラーにはならないケースがあるようです。

エラーチェックが正しく出来ないなら、型チェックがなされない=動いてしまう、という結果になるのは明らかです。綿密に調べてもしバグならバグ報告したいところですが、できておりません。
ということで結論は保留です。今のところわかりません。

まとめ

型クラスの基本は実装がわかれば理解できる
- ただし言語ごとの実装戦略や、シンタックスの差異は当然あるのでそこは別途。
型クラスの構成部品はOOPから流用可能だが、コンセプト的に根本的に相入れないからこそ、型クラスが存在する
型クラス=FPではない。その実現に寄与する周辺機能にすぎない。但し静的型および多相型に強く結びついた重要で強力な機能である。FPにおける型クラスは、OOPにおけるクラス継承に比するべき概念である(クラス継承はOOPに必須ではない、ということとも同型)。
Groovyはコンパイラやランタイムに手を入れずに、カスタム型チェッカやAST変換でかなりのことができる
静的型や多相型に関してもある程度のことができる。ただし、静的型チェッカの多相型処理を読み込むのは覚悟がいる。
Groovy2.xの静的型チェッカの多相型サポートは、激しく進歩している。Javaのそれより強いのは間違いない。
カスタム型チェッカ(型チェッカ拡張)は、フルのAST変換を書くのにくらべて非常に便利。ただし実行フェイズや、ハンドラを書けるイベントが決まっているので目的とする処理に適合しない可能性がある。

おまけ2：アドホック多相

アドホック多相という言葉は使いませんでしたが、これはこういうことなんじゃないかと思っています(オレオレ理解)。。

パラメトリック多相：処理対象のデータ型の特定をしないで処理を記述できるような、処理記述の柔軟性。ただし、処理対象となるデータに対して実施できるのは、ポインタ操作やバイトコピーなど、内容や構造に依存しないような操作のみに限る。典型的にはコンテナへの出し入れ対象として扱うだけ、とか。
アドホック多相：目的は同様だが、パラメトリック多相では達成できない、「データの内容に依存した処理」を可能とするために、データと独立した「操作の集合」を事前に定義し、それを関数呼び出し時のデータ引数を渡す時に、引数データの付随情報として与える。(その際に操作の集合の選定を多相型の型推論で元にして自動的に実行する。)

これらの概念は、実装方式とは独立である。たとえばパラメトリック多相についてポインタで実現するケースもあると思うが、型毎に関数実体を適切なタイミングで生成して使っても良いであろう。

*1:パラメトリック多相とは、型引数の制約が無い場合、つまりコンテナに入れる、出す、といった、データ固有の操作を行わない引数を多相にするときに使える。

*2:可能かどうかは実装による。

*3:余談になるが、多言語間呼び出しでは、OOPが長期的には無価値であることが実証されてきたと言うしかない。CORBA/RMIを見よ。SOAPを見よ。WebAPIはメソッドを持たないJSONを返す

*4:@InheritConstructorはすでに似たようなことをしているのでそれを真似すればよい。

*5:Scalaとの相違点：確かScalaでは衝突をコンパイル時エラーにするんじゃなかったかな。

*6:この振り分けは、Haskellなどのイレイジャではないジェネリクス環境で理想的な条件下であれば、静的に決定できるとされている。未確認だが。

*7:Groovyのwith句を使っても良い。

uehaj's blog

Grな日々 - GroovyとかGrailsとかElmとかRustとかHaskellとかReactとかFregeとかJavaとか -