多相バリアントを使いこなそう(4)

前回までで多相バリアントの基本的な機能は説明してきました。そこで今回は、多相バリアントのとても重要な応用についてお話したいと思います。それは、場合分け構造の拡張問題です。

場合分け構造の拡張は難しい

例えば、次のようなコードがあったとします。

module Card = struct
  type t = Num of int | Jack | Queen | King
  let num = function
      Num i -> i
    | Jack -> 11
    | Queen -> 12
    | King -> 13
end

Card.tには4種類の場合分けがあり、それらに対してnumという操作が定義されています。このような場合分け構造+操作に対して、

1. 静的で安全に(キャストせず)、
2. 元のコードを一切変更せず、
3. 新しい場合分けを加え、
4. 新しい操作も加えた
5. 新しい場合分け構造を定義する

にはどうすればいいか？という既存コードの再利用と拡張に関する問題を考えてみます。具体的には、Card.tにJokerという場合分けを導入(CardEx.t)し、Card.t型かCardEx.t型の値を受け取って、順番的に次の値(Kingの次はJoker、次はNum 1といった)を返す関数nextを加えたいとします。
例えば、(静的型付けの)オブジェクト指向言語でnumというメソッドを持つCardというインターフェイスクラスを作って、Num, Jack, Queen, KingというCardインターフェイスを実装したクラスを作ったとしましょう。この構成なら、新しい場合分けを加えるのはとても簡単で、Cardインターフェイスを実装したクラスを一つ加えればよい訳です。ところが、Num型のオブジェクトに対しても使える新しい操作(メソッド)を(安全に)加えようとすると、どうしても既存のコードに手を入れなければななりません。これではダメです。
一方で、上記のCardモジュールに対して操作を加えることは簡単です。Card.t型の引数を受け取る関数nextを新しく定義すれば、既存のコードに一切変更を加えずに操作を拡張できます。ところが、Card型に新しく場合分けを加えようとしても、元のコードを変更せざるを得ません。
さらに言うと、visitorパターンを使っても操作は加えられるけど場合分けは無理とか、visitorパターンと型変数でごにょごにょとかはあるのですが、「場合分けと操作を同時に拡張するのは、構成上難しい(もしくはかなり複雑)」と言えます。
ところが、多相バリアントが状況を一変させます。次のコードを見てください。

# module Card = struct
     type t = [ `Num of int | `Jack | `Queen | `King ]
     let num = function
         `Num i -> i
       | `Jack -> 11
       | `Queen -> 12
       | `King -> 13
  end;;
# module CardEx = struct (* 拡張Card型 *)
     type t = [ Card.t | `Joker ] (* 新しい場合分けを増やす *)
     let num = function
         #Card.t as c -> Card.num c  (* #多相バリアント型名で、一気にパターンマッチできる *)
      | `Joker -> 0
     let next = function (* 新しい関数 *)
         `Num i when i < 10 -> `Num (i + 1)
      |  `Num _ -> `Jack
      |  `Jack -> `Queen
      |  `Queen -> `King
      |  `King -> `Joker
      |  `Joker -> `Num 1
end;;

拍子抜けするぐらい簡単で素直なこのプログラムは、上の条件を全て満たしています。確認していきましょう。

1. 静的で安全に(もちろん!)
2. 既存のコードを改造せず(Card.tが多相バリアントになっていますが、元々こうしておくという前提で)、
3. `Jokerという新しい場合分けを加え、
4. nextという新しい操作を加え、
5. CardExという新しい構造を定義できています。

意外かもしれませんが、このような表現が可能であることは結構すごいことなのです。OCaml素晴しい。

Expression Problem

実はこの問題は、"Expression Problem"と呼ばれている問題なのです。1998年に、モナドで有名なかのPhilip WadlerがGeneric Javaに関する議論でメーリングリストに投稿した次の文章が有名です。
http://www.daimi.au.dk/~madst/tool/papers/expression.txt

The Expression Problem is a new name for an old problem. The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts). For the concrete example, we take expressions as the data type, begin with one case (constants) and one function (evaluators), then add one more construct (plus) and one more function (conversion to a string).
:
Expression Problemは、古くから言われている問題の言い替えに過ぎない。その目的は、静的な型付けの下で、場合分けのデータ構造に対して、新しい場合分けとその場合に対する新しい処理を、元のソースコードに手を加えることなく拡張定義することだ。具体的な例として、式をデータ構造(最初は定数だけ)、式の評価関数を一つの処理と考え、これに足し算と新しい処理(文字列への変換)を加えてみたい。
:
Whether a language can solve the Expression Problem is a salient indicator of its capacity for expression. One can think of cases as rows and functions as columns in a table. In a functional language, the rows are fixed (cases in a datatype declaration) but it is easy to add new columns (functions). In an object-oriented language, the columns are fixed (methods in a class declaration) but it is easy to add new rows (subclasses). We want to make it easy to add either rows or columns.
:
ある言語がこのExpression Problemを解決できるかどうかは、その言語の表現能力を示す顕著な指標だ。行と列を持つ表を考えると、いうなれば場合分けを行、処理を列と捉えることができる。関数型言語では、列(処理)を加えることは簡単だけれども、行は(データ型宣言により)固定されてしまう。オブジェクト指向言語では、新しい行(サブクラス)を加えることは簡単だけれども、列は(メソッド定義により)固定されてしまう。我々は、行と列の両方を簡単に加えたいのだ。

この文章に続いてWadlerはVisitorパターンと型パラメータを応用したGeneric Javaを用いた解決方法を提示しています。興味のある方は参照してみてください。

要約

• 場合分け構造の拡張問題はExpression Problemと呼ばれており、解決する事は難しいか、かなり複雑。
• 多相バリアント型は、Expression Problemを簡潔に解決できる優れた手法。

今回はちょっと概念的なお話になってしまいましたが、次回は多相バリアントのライトウェイトな使い方について触れてみたいと思います。

[おまけ]
私は詳しく知りませんが、ScalaはExpression Problemを綺麗に解決できるらしいです。