OCamlにおけるガード付きメソッド
Guarded Methods in OCaml (xvw.lol)
要約
OCamlでは、特定のメソッドに対してレシーバー(self)に制約を課す「ガード付きメソッド」を直接定義することは構文上できません。この記事では、型等価性証拠(type equality witness)を用いてこれをエンコードする方法を解説します。ガード付きメソッドは、メソッド呼び出し時にレシーバーが特定の制約を満たす場合にのみ実行可能にする機能であり、型安全性を高める上で有用です。
全文翻訳
ガード付きメソッドは、特定のメソッドに対してのみレシーバー(self)に制約をアタッチすることを可能にし、これらのメソッドはレシーバーがそれらの制約(ガード)を満たしている場合にのみ呼び出すことができます。 OCaml は、構文上、この種のメソッドを直接定義することを許可していません。この記事では、型等価性証明を使用してそれらをエンコードする方法を見ていきます。
問題提起
言語(JavaやOCamlのように型チェックがプログラム実行前に行われるもの)がパラメトリック多相(Javaのジェネリクス)を導入する場合、型変数を制約することが可能な場合があります。例えば:
class MyClass<T extends S> { ... }
MyClassを、型変数TがSのサブタイプであると仮定することでジェネリックにします。問題は、制約がクラス全体に適用されることです。しかし、時には、制約が特定のメソッドにのみ適用されるようにしたい場合があります。例えば、リストを表すMyListクラスがあるとしましょう:
class MyList<A> extends ArrayList<A> {
public int length() {
return this.size();
}
}
[[1, 2, 3], [4, 5]]のようなリストを[1, 2, 3, 4, 5]というリストにするflattenメソッドをどのように定義できるでしょうか?クラスレベルに制約を置くと、リストを「常にリストのリスト」に強制することになり、非常に制限的です。このようなメソッドを実装するために、理論的には3つのアプローチが利用可能です。
メソッドをクラスの外に移動する
最初のアプローチは最も明白です。「ごまかす」ために、メソッドをクラス本体の外(例えば、静的コンテキストやコンパニオンオブジェクト)に移動します:
class MyList<A> extends ArrayList<A> {
public static <A> MyList<A> flatten(MyList<MyList<A>> list) {
// Flatten's implementation
}
public int length() {
return this.size();
}
}
このアプローチは機能し、特別な儀式を必要としません。しかし、開発者はどのメソッドがクラス本体にあり、どのメソッドが静的コンテキストにあるかを追跡する必要があります。さらに、オブジェクト指向プログラミングの主な議論の1つとして提示されることが多い、インスタンスへのメッセージ送信という体系的なアプローチを壊します。
拡張メソッド
Kotlin(およびC#など)は拡張メソッドを提供しており、これは既存のクラスを拡張することを可能にする(JavaではfinalであるStringクラスに動作を追加するのに非常に役立つ)だけでなく、レシーバーの定義においてより柔軟性を提供します。例えば、Kotlinではflattenを次のように書くことができます:
class MyList<A> : ArrayList<A> { ... }
fun <A> MyList<MyList<A>>.flatten() = ...
このソリューションはほぼ完璧に見えますが、メソッドはクラスの外に定義する必要があり、拡張からアクセスできるようにするために、クラスの特定のメンバーをパブリックにする必要があるかもしれません(リーキーアブストラクションの可能性に見えます)。しかし、それは体系的なメッセージ送信アプローチを維持しつつ、レシーバーのよりきめ細かな修飾を可能にします。
ガード付きメソッド
最後のアプローチはおそらく最もイデオロギー的であり、メソッド定義をクラス内に保持します。エスケープした抽象化を強制しません。これはガード付きメソッドのアイデアであり、メソッド定義レベルでジェネリックパラメータに制約を追加する機能です。想像上の構文では(このコードは構文的に無効ではないためコンパイルされますが、意図した効果は得られません):
class MyList<A> : ArrayList<A>() {
fun length() = size
fun <B> MyList<MyList<B>>.flatten() =
// Implémentation de flatten
}
これは古典的な拡張メソッドと大きく異ならないように見えますが(クラス本体内の構文が十分であることを示す)、以前に提起されたすべての問題に対処します:
- 通常のメソッドよりもレシーバーを正確に特徴づけることができる
- 通常のメッセージ送信を壊さない
- 利用可能なメンバーの恩恵を受け続ける(表現をエスケープしない)
ガード付きメソッドは必要と思われるにもかかわらず、残念ながら、それらの定義を許可する主流の言語は知りません。それは非常に残念です。幸いなことに、OCamlではそれらをエンコードすることが可能です。
OOP/FP対称性:理論と実践
ガード付きメソッドは一般的なプログラミング言語では非常に珍しいため、Gabriel Schererによるプレゼンテーション「The Object-Oriented/Functional-Programming symmetry: theory and practice」のスライドを読んでいる間に、その存在を比較的最近知りました。
このプレゼンテーションを推奨します。静的型付け関数型プログラミングとオブジェクト指向プログラミングのツールの対称性を示しています。この対称性は何度も観察・研究されていますが、このプレゼンテーションは包括的でアクセスしやすく(そして比較的偏見がなく、両アプローチの長所と短所を議論しています)。残念ながらプレゼンテーションではカバーされていませんが(時間はしばしばプレゼンターの敵です)、スライドにはガード付きメソッドに関する完全なセクションが含まれています。元の例は、古典的な関数型スタイルでのflatten関数の実装と、オブジェクト指向の世界でのflattenメソッドの実装との間の対称的な観察を示しています。
type 'a list = ...
let rec length : 'a list -> int = ...
let rec concat : 'a list -> 'a list -> 'a list = ...
let rec flatten : 'a list list -> 'a list = function
| [] -> []
| x::xs -> x @ flatten xs
そして、オブジェクト指向の世界にいる場合のflattenメソッドの実装です。これはまさにこのノートで紹介された問題です。質問は、flattenはどのような型を持つべきかということです。
class type ['a] olist = object
method length : int
method concat : 'a olist -> 'a olist
method flatten : ???
end
そこで彼は、flattenメソッドにガードを暗示するこの構文を提案しています:
method flatten : 'b olist with 'a = 'b olist
この構文はガード付きメソッドを記述でき、次のように一般化できます:method method_name : return_type with generic_type = other_type。モジュールの代入と同様に、andを使用して複数のジェネリックに対する制約を指定できます。例えば、2つの型でパラメータ化されたクラスの場合:method foo : string with 'a = string and b = int:class ['a, 'b] t。
さらに、この構文は特定の動作をエレガントに定義することも可能にします。例えば、olist型の場合、リストの要素が整数であればsumメソッドを提供できます:
class type ['a] olist = object
method length : int
method concat : 'a olist -> 'a olist
method flatten : 'b olist with 'a = 'b olist
method sum : int with 'a = int
end
これらすべては驚異的に聞こえますが、残念ながら、この構文はOCamlでは利用できません。それは腹立たしいです!心配しないでください、いくつかの小さなツールを使用してエンコードすることが可能です。
OCamlにおけるガード付きメソッド
ガード付きメソッドをエンコードするために使用すべきツールのアイデアはかなり明確でしたが、いくつかのコーナーケースに遭遇した後、OCamlコミュニティで質問は決してせず、常に広範囲に回答してくれる人に助けを求めました:Florian Angeletti、別名Octachron。(ちょっとした面白い注釈:
octachronはMIDIドラムシーケンサーの名前なので、彼のニックネームをGoogleで検索すると、提案にはすぐにoctachron ocamlが含まれました)。
私たちの目標は、特定のメソッドに制約を追加できるようにすることです。これにより、それらはレシーバーの型がそれを満たしている場合にのみアクセス可能になります。言語構文を変更せずに、制約をモデリングすることは、追加のパラメータを提供することで構成できます。言い換えれば、証拠を提供したいのです。
型等価性証明を提供する
言語に汎用代数的データ型が導入されて以来、型等価性証明を定義するかなり簡単な方法があります:
type (_, _) eq =
| Refl : ('a, 'a) eq
eq型は、唯一のコンストラクタReflを持ち、型チェッカーには知られていない型等価性を表現することを可能にします。Reflの値は等しい2つの型を関連付けるものしか構築できないため、スコープ内でReflをインスタンス化することは、それらの型が等価であることを保証します。例えば:
type other_int = int
let _ : (int, other_int) eq = Refl
(* これで、[int = other_int]の証明が得られました。*)
この例はやや人工的です。なぜなら、ここではコンパイラはint = other_intであることをよく知っているからです。しかし、コンパイラがこれを知ることができない場合があります。例えば、実行時にデータが提供される場合、型チェッカーが型の情報を持っていないことは完全に理にかなっています。または、型の表現が抽象化によって隠されている場合です。
この記事の目的はeqを掘り下げることではないので、Reflの値を構築できれば、構文的に異なる2つの型が実際には等しいという保証が得られることを覚えておきましょう。
eqで制約する
リストのオブジェクトAPIを提供する例に戻りましょう。そのインターフェースは次のとおりです:
class type ['a] obj_list =
object ('self)
method length : int
method append : 'a list -> 'a obj_list
method uncons : ('a * 'self) option
method flatten : ???
end
flattenに型を与えるために、'a(obj_listクラスの型パラメータ)がリストであることを課したいのです。つまり、'aが'b list型であるという証明を保証したいのです。つまり、'aと'b listが、構文的には異なるものの、等しいことを保証することです。それは簡単です:('a, 'b list) eq型の値を要求するだけです:
method flatten : ('a, 'b list) eq -> 'b list
これで、レシーバーがa list of somethingであることを制約するflattenメソッドを記述したリストのインターフェースができました。具体的にobj_listを実装するクラスを実装してみましょう。
インターフェースobj_listの実装
最初(length、append、uncons)のメソッドは実装が簡単です:
let my_list (list : 'a list) =
object (self : 'a obj_list)
val l = list
method length = List.length l
method append x = {<l = List.append l x>}
method uncons = match l with [] -> None | x :: xs -> Some (x, {<l = xs>})
method flatten = ???
end
次にflattenに焦点を当てましょう。リストを再帰的にたどり、各要素を前の要素に連結します。例えば、[[1]; [2]; [3]]は[1] @ [2]; [3]になります。ややノイズの多いアノテーションを超えて、トリック全体はReflをインスタンス化して'a = 'b listであることを証明することにあります。
method flatten : 'b. ('a, 'b list) eq -> 'b list =
let rec aux : type a b. a #obj_list -> (a, b list) eq -> b list =
fun list witness -> match list#uncons with
| None -> []
| Some (head_list, xs) ->
let flatten_list : b list =
let Refl = witness in head_list
in flatten_list @ aux xs witness
in aux self
ガード付きメソッドsumの追加
これで特定のメソッドを制約できるようになりました。整数のリストの合計を生成するsumメソッドを追加してみましょう!まず、インターフェースにsumを追加します。今回は、型パラメータをintに制約したいです。これを行うには、型等価性証明として('a, int) eqを取るだけです:
class type ['a] obj_list =
object ('self)
method length : int
method append : 'a list -> 'a obj_list
method uncons : ('a * 'self) option
method flatten : ('a, 'b list) eq -> 'b list
method sum : ('a, int) eq -> int
end
次に、fold_left関数の使用であるsumメソッドを実装できます。
method sum : ('a, int) eq -> int =
let aux : type a. a list -> (a, int) eq -> int = fun list Refl ->
List.fold_left (fun acc x -> acc + x) 0 list
in aux l
sumの実装は、追加の型変数を導入しないため、flattenの実装よりも論理的に簡単です。そして、さまざまなメソッドをテストできます。'a list obj_list型のオブジェクトにflattenを呼び出し、int obj_list型のオブジェクトにsumを呼び出すことができます。
let a = my_list [ [ 1 ]; [ 2 ]; [ 3 ] ]
let _ = assert ([ 1; 2; 3 ] = a#flatten Refl)
let b = my_list [ 1; 2; 3; 4 ]
let _ = assert (10 = b#sum Refl)
間違った型のガード付きメソッドを適用しようとすると、例えばリストa(型は'a list obj_list)を合計しようとすると、プログラムはコンパイルされません。これは、課された制約を尊重せずにガード付きメソッドを呼び出そうとしているため、当然の結果です。
1 | let _ = a#sum Refl
^^^^
Error: This expression has type (int list, int list) eq
but an expression was expected of type (int list, int) eq
Type int list is not compatible with type int
まさに期待される動作です!これで、型等価性証明を介してレシーバーの型を制約するメソッドを定義できるようになりました。ミッション完了!
結論
ガード付きメソッドがすべての静的型付けOOP言語に存在しないのは驚くべきことです。なぜなら、それらはメッセージパッシングセマンティクスを維持しながら、より多くのメソッドを表現することを可能にするからです。オブジェクト指向言語のヘビーユーザー(OCamlは私が定期的に使用する唯一の言語です)ではないため、ガード付きメソッドの構文サポートを提供する言語は知りません。しかし、最近、Nicolas Rinaudoに指摘されて、言語Scalaが同様のエンコーディングを使用していることを知りました。ただし、型等価性証明は暗黙的に提供されるため、呼び出しが軽量化され、ユーザーが手動でReflを提供する必要がなくなります。
エンコーディングはやや重いですが、ガード付きメソッドの定義を簡略化するためにネイティブ言語サポートを想像することもできますが、明示的に型等価性証明を操作することで、それらをエンコードできます。それは有用でしょうか?OCamlではOOPプログラミングはめったに推奨されないため、おそらくそうではないでしょうが、等価性証明の具体的で実用的なユースケースを示すのはまだ楽しかったです!