OCaml で return 相当の処理を実装する

※この記事は 2016年02月15日 に Qiita に投稿したものです。

OCaml には return 文（または式）がありません。 OCaml の関数は最後に評価された式の値を戻り値とします。ですので、戻り値に関しては return が不要なのですが、関数の実行の中断（脱出）もできません。

ですが、 Jane Street Core に含まれる with_return 関数が同等の処理を実装しています。このソースをいきなり読むのは初級者には難しかったんで、実現したい仕様からコードを逆算して考えていきます。なお、以降のコードは Core に依存しません。

まずは、関数の使い方です。次のような使い方を想定しています。ソースは common.mli のコメントから、 Core に依存しない形に修正しています:

let find f l =
  with_return (fun r ->
    List.iter (fun x -> if f x then r.return (Some x)) l;
    None
  )

これは List.find の実装例です。実際の Core.Std.List.find は with_return を使っていませんので、あくまで一例です。 return を含める処理をクロージャーで書いて、それを with_return に渡します。 List.find は再帰で簡単に書けますが、 return のある言語に慣れている人にとってはこちらのコードの方がわかりやすいかもしれません。

では、 with_return の実装方法を考えていきます。その前に、使い方を示しておいてなんですが、上の例では r.return のように、 return 関数はレコード r のメンバーです。でも r は必要なのか？ return 関数のみを渡せばいいんじゃないのか？と私は思ったので、その使い方を想定してみます:

let find f l =
  with_return (fun return ->
    List.iter (fun x -> if f x then return (Some x)) l;
    None
  )

多少シンプルになりました。これで考えてみます。

with_return は引数に関数を一つ受け取りますから、こんな感じで始まりますね。

let with_return f = ..

次に、 f に渡す return 関数を考えます。 with_return なんてクッションを置かずに一つの関数で return を済ませられればいいのですが、さすがに無理です。仕方がないので f 内で return を使ってもらいます。 return は関数内で実装するとして、こんな感じです:

let with_return f =
  let return value = .. in
  f return (* あとはなんとかして戻り値を処理したい *)

今度は、 return を呼んだら関数 f を脱出する処理です。そんな処理を書けるのか？と言えば、そこは例外を利用すればいけます。例外を上げれば f を脱出できますから、その例外を捕捉すればいけそうです。例外は専用の型を別途用意するとします:

exception Return of 'a

let with_return f =
  let return value =
    raise (Return value)
  in
  try f return with
  | Return value -> .. (* 戻り値の処理 *)
  | exn -> raise exn (* 他の例外だったらスルーしとこう *)

List.find の例くらいなら問題なくいけそうな気が...コンパイルできない。どうやら exception Return of 'a はコンパイルできないようです。

# exception Return of 'a;;
Error: Unbound type parameter 'a

型変数 'a が宣言されていないとのエラーですが、例外に型変数は指定できません。 OCaml の例外の型は exn で、ユーザー定義の例外は exn の型コンストラクタとして扱われます。偉そうに言ってますが、私はナチュラルに間違えました。

exn は型変数を持たないので、 exception Return of 'a の 'a は無効です。定義するなら、 exception Return of string のように具体的な型を指定する必要があります。関数の性質上、特定の型に絞ると使いにくいので、この方法ではだめそうです。

これを解決するにはどうするか。例外のデータ型に型変数を指定できないなら、どうにかして戻り値の型ごとの例外を定義してはどうでしょう。でも、

exception Return_string of string
exception Return_bool of bool
exception Return_int of int
..

let with_return_string f = ..
let with_return_bool f = ..
let with_return_int f = ..

などと、型ごとに例外と関数を定義するのは面倒ですし、 with_return を内部で使う関数の型を抽象化しにくくなります。ここでの例で言えば、

let find f l =
  with_return (fun return ->
    List.iter (fun x -> if f x then return (Some x)) l;
    None
  )

'a list -> ('a -> bool) -> 'a option としたい find 関数の型が、次のように型別の with_return を使うことによって、

let find f l =
  (* 戻り値は文字列 *)
  with_return_string (fun return ->
    List.iter (fun x -> if f x then return (Some x)) l;
    None
  )

string list -> (string -> bool) -> string option のように限定されてしまいます。仕方がないから find も型ごとに find_string, find_bool...と用意するとなると、さすがにこれでは使いにくい。

できるならば、 with_return の呼び出し箇所に応じて、戻り値の型に合わせた例外を自動的に定義したい。そんなことが可能なのかと言えば、できるらしいです。局所的抽象型 (locally abstract types) という仕様で、関数内でのみ有効な抽象型を扱えます。ただし関数内では例外を定義できませんので、モジュール定義と組み合わせます。つまり、（戻り値の型を含む）例外を含むモジュールを関数内で定義する、ということです。わからない？ごもっともです。要するに次の形で書けます:

let with_return (type value) f = 
  let module M = struct
    exception Return of value
  end in
  let return value =
    raise (M.Return value)
  in
  try f return with
  | M.Return value -> value
  | exn -> raise exn

(type value) という謎の記述が局所的抽象型です（ OCaml 3.12 からの機能で、全然最新ではないんですが）。これは引数ではなくて、関数内でのみ有効な抽象型 value の宣言です。 value という特定の型があるわけではないです。

前述のように、関数内では例外を直接定義できません。そのためモジュール定義と組み合わせたのが

let module M = struct
  exception Return of value
end in

のコードです。この struct は何なのか？モジュール定義で書くアレじゃないのか？そうです、モジュールの定義（というか生成）です。ここで戻り値用の例外 Return を含む新しいモジュール M を生成してます。実はモジュールはファーストクラスオブジェクトで、値として操作可能、動的に生成できます（詳しくは RWO の First Class Modules を参照してください）。静的型付けの OCaml で動的にモジュールを生成ってなに？と混乱しそうだったら、モジュールというものを深く考え過ぎているのかもしれません。静的に型付けすることと、動的に（実行時に）モジュールオブジェクトを生成するのは、それぞれ別の処理です。

ややこしい説明は続きます。そのモジュール定義に含まれた例外で抽象型 value を指定していますが、先を見た方がわかりやすいでしょう。例外 Return を使っている箇所はここです（引数の value と type value は名前が同じですが、前者は値、後者は型で、名前空間が異なる別のデータです。同じ名前を使う必要はありません）:

let return value =
  raise (M.Return value)

引数（ユーザーが戻り値とする値）を例外 Return でラップして、例外を上げます。従って引数 value の型は、局所的抽象型の value です。これでどうなるのかと言うと、「実行時に戻り値の型用の例外を含むモジュールが生成され、型推論時に例外の型が決定される」とすればいいんでしょうが、説明されるよりコードを理解する方が早いかもしれませんね。

これで一応の機能はできました。これ以降ですが、 Core の実装では with_return から渡される関数 return の呼び出しを with_return の実行内に制限しています。 Core に依存しない形にしてみると、こんな感じです:

let with_return (type value) f = 
  let module M = struct
    exception Return of value
  end in
  let is_alive = ref true in
  let return value =
    if not !is_alive then
      failwith "already returned";
    raise (M.Return value)
  in  
  try 
    let value = f return in
    is_alive := false;
    value
  with exn ->
    is_alive := false;
    match exn with
    | M.Return value -> value
    | _ -> raise exn

with_return に渡す関数の呼び出し後に return 関数を呼び出すとエラー（例外だけど）にします。そうする理由は with_return の実装の隠蔽でしょうか。万が一 return が with_return 外に持ち越されてしまった場合に思わぬ箇所で例外が上がってしまうとか、あるいは例外 Return がローカルなモジュールに定義されているので、ユーザーからは例外 Return を捕捉する方法がないとか。特にコメントが書かれていませんので、私の OCaml レベルではわかりません。ただ、 Core でも failwith 使っとくんだなとはわかりました。

さて、最後は型です。これまでの実装だと、 with_return の型はこうです。

val with_return : (('a -> 'b) -> 'a) -> 'a

('a -> 'b) が return 関数の型です。ここなんですが、もちろん return 関数が取る引数 'a は戻り値として渡す型です。では、 return 関数の戻り値 'b は何でしょう？ややこしいようですが、例えば return true という式があったら、その戻り値は何でしょうか。 bool ではないです。というのは、 return 関数は必ず例外を上げるからです:

let return value =
  if not !is_alive then
    failwith "already returned";
  raise (M.Return value)

return 関数で最後に評価されるのは、例外を上げる raise 関数です。 raise の型は exn -> 'a で、 return 関数の戻り値もここに関係します。で、この戻り値 'a は何なのか？

例外を上げてしまいますから、 raise から戻り値は返ってきません。それなら unit にしてもよさそうに見えますが、 'a であるのは対になる式と型を合わせるためかと思います。例を出しますと、 val bool_of_string : string -> bool はこう実装できます:

let bool_of_string = function
  | "true" -> true
  | "false" -> false
  | _ -> raise (Invalid_argument "bool_of_string")

上二つのパターンマッチ後の値が bool であるのに、最後のパターンマッチが raise で終わっても問題ないのは、 raise の型が exn -> 'a だからです。この場合ですと、'a は bool に置き換えられます。もし raise の戻り値が unit であれば、実際には使われない適当な値を書く必要が出てきます。 'a のおかげで余計なコードを書かなくて済むというわけです。

というわけで話を return 関数に戻しますと、 ('a -> 'b) の 'b は raise の戻り値です。深く考える必要はない..かもしれませんが、こういう手続き的なコードを書くとしたらどうなるでしょうか？

(* 実用的な意味はありません *)
let map f l =
  with_return (fun return ->
    if List.length l = 0 then
      return None; (* ポイント *)
    let map = List.map (fun x ->
      match f x with
      | None -> return None
      | Some x' -> x') l
    in
    Some map
  )

この関数の私が意図した型は

('a -> 'b option) -> 'a list -> 'b list option

です。ところが、このコードを型注釈なしにコンパイルすると、

('a -> unit option) -> 'a list -> unit list option

こう推論されます。なぜ unit になるかと言えば、最初の return 呼び出しの戻り値が unit だからです。従って次の return も unit 、従って x' も unit であり、従って f は ('a -> unit option) と推論されます。これでは困るので、次のように型注釈をつけてコンパイルしてみます。

let map f l : ('a -> 'b option) -> 'a list -> 'b list option = ..

するとコンパイルエラーが出ました。

Error: This expression has type unit list option
       but an expression was expected of type
         ('a -> 'b option) -> 'a list -> 'b list option

まあ、そりゃそうですね。最初の return 呼び出しの戻り値が unit であることに変わりませんから。と、このように複数箇所で return を使う場合は、戻り値を揃えないといけません。

しかし、これは少々トリッキーな方法で解決できるようです。とは言え Obj.magic のようなチートではなく、高ランク多相とかランクN多相とか言われる型表現を、多相レコードで表します。 Core のコメントには、こう書きたいんだけど ML の表現力では無理だから多相レコードを使ったとあります。

(* エラーですよ *)
val with_return : 'a. (('a -> ('b. 'b)) -> 'a) -> 'a

'a. と 'b. のピリオド付き型変数は、型変数の宣言です（この文法は存在しますが、このようには書けません）。何の意味が？というと、型変数のスコープを指定できます。というかしたいんだけど OCaml ではできないので、あくまで疑似コードです。

val with_return : 'a. (('a -> ('b. 'b)) -> 'a) -> 'a
                   |            +---+              |
                   |             'b                |
                   +-------------------------------+
                                 'a

これがどう return に影響すると言うのか？ return の型は ('a -> 'b) でした。 OCaml では（他の言語について詳しくないのでこういう書き方をしてます）、型変数は関数の実装全体で有効です。ですので、一旦 'a と 'b が決定してしまえば、残りの return 呼び出しも同じ型とみなされます。しかし上の宣言が有効だとすれば、 'b の有効範囲は return の戻り値に限定されます。 'b は関数の型には影響せず、 return の呼び出し箇所ごとに決定されるわけです。従って前述の例のように、 return の戻り値が unit である箇所とそうでない箇所があっても、それぞれで 'b が決定されるので問題ないということになります。おそらくこれを高ランク多相とかランクN多相と言うのだと思いますが、 OCaml ユーザーにはプログラミング in OCaml の「 12.5.4 多相メソッド」の項が参考になるかと思います。

さて、繰り返したように上記の仕様は OCaml で実装できないのですが、多相フィールドを持つレコードを使うとなんとかなります。それが次の定義です。

type 'a return = { return : 'b. 'a -> 'b }

'b. 以外のコードは特に問題ないでしょう。問題は return : 'b. 'a -> 'b の部分です。 'b. が型変数のスコープだと言われても、それがどうこの定義に関係するのか？

これまでに登場した return の型は 'a -> 'b でした。ここでもそれは変わりません。ところが、 'b は左辺に登場しません。 'b は return 関数呼び出しの文脈でのみ具体化され、レコードに影響しません。多相メソッドとも言い、繰り返しますが、詳しくはプログラミング in OCaml の「 12.5.4 多相メソッド」の項が参考になるかと思います。

ともかく、この多相フィールドを使うことで、 'a. (('a -> ('b. 'b)) -> 'a) -> 'a のような型変数のスコープを用意できます。というわけで、 'a return 型は return 関数を持つレコードで、 'a は return 関数に渡す戻り値の型です。そして、最終的に with_return 関数の型はこうなります。

val with_return : ('a return -> 'a) -> 'a

以上です。まさか with_return 関数一つに、局所的抽象型、ファーストクラスモジュール、多相フィールドと、濃い仕様がいくつも詰まってるとは思いませんでした。 Core を使う分にはここまで把握しなきゃならないことはないと思いますので、臆せず OCaml と Core にチャレンジしていただければと思います（なかなかそんな人いないか..）。

最後に、実際のコードを引用しておきます。途中で参照されている Exn モジュールは Core の API ですので、そこだけ raise に置き換えれば Core 非依存にできます。 OCaml レベルを上げたければ、この関数に頼らない方がいいんじゃないかなと思います。

type 'a return = { return : 'b. 'a -> 'b }

let with_return (type a) f =
  let module M = struct
    (* Raised to indicate ~return was called.  Local so that the exception is tied to a
       particular call of [with_return]. *)
    exception Return of a
  end in
  let is_alive = ref true in
  let return a =
    if not !is_alive
    then failwith "use of [return] from a [with_return] that already returned";
    Exn.raise_without_backtrace (M.Return a);
  in
  try
    let a = f { return } in
    is_alive := false;
    a
  with exn ->
    is_alive := false;
    match exn with
    | M.Return a -> a
    | _ -> raise exn