OCamlで相互再帰な型を二つのModuleにわける方法二つ
Essentials of Programming LanguageをOCamlで実装するのをぼちぼちとすすめている。
前回LETを実装した時「式を評価した結果の値」を表す型とその型に対する関数を集めたVal
と「変数とそれに対応する値の対応関係を保持する環境」のモジュールEnv
を作った。
上記の説明からも推測できると思うが、Env
の定義にVal.t
が使われている:
type t = (string * Val.t) list
次に実装するPROC言語では第一級関数が定義できる。関数が変数の値となりえるのでVal.t
のバリアントの一つとしてProc
が追加される。そしてそのProc
はクロージャを持つ、つまり変数環境を保持する必要がある。
type t = Num of int | Bool of bool | Proc of string * Exp.t * Env.t
しかしEnv
の定義にVal.t
が使われており、Val.t
の定義にEnv.t
を使おうとすると相互再帰になってしまう。どうしよう。
解決策が二つわかった(一つは@camloebaさんに教えてもらった。ありがとうございます!)のでメモ。
相互再帰的なモジュール
一つ目のやりかたはモジュール自体を相互再帰的にしてしまうことだ。
PROC言語はその方法で実装してみた:
Valenv.ml
というモジュールでmodule rec ... and ...
という構文を使ってVal
とEnv
を相互再帰的に実装する:
module rec Val : sig type t = Num of int | Bool of bool | Proc of string * Exp.t * Env.t val to_str : t -> string end = struct type t = Num of int | Bool of bool | Proc of string * Exp.t * Env.t let to_str = function | Num n -> string_of_int n | Bool b -> if b then "True" else "False" | Proc _ -> "Proc" end and Env : sig type t val empty : t val find : t -> string -> Val.t option val extend : t -> string -> Val.t -> t end = struct type t = (string * Val.t) list let empty = [] let rec find env s = match env with | [] -> None | (s', v')::env' -> if s = s' then Some v' else find env' s let extend env s v = (s, v)::env end
あとはValenv.mli
でsignatureだけ明示して、Val.ml
とEnv.ml
でinclude Valenv.Val
、include Valenv.Env
するだけ。
少々かったるい点としては相互再帰的モジュールはValenv.ml
内で実装を定義するときもsignatureが必要なので同じものが.ml
と.mli
で重複すること。
相互再帰的な型を定義し、それを使ってモジュールを定義する
相互再帰的な型とモジュールについてツイッターでつぶやいたら以下のようにご教示いただいた:
こんにちは。それをおすすめします。再帰モジュールにしてもいいですが、実装ファイルを分けれるわけでもなく、あまり嬉しくないです
— Jun Furuse 🐫🌴 (@camloeba) 2019年6月3日
type t1 = Foo of t2 and t2 = Bar of t1
— Jun Furuse 🐫🌴 (@camloeba) 2019年6月3日
module A = struct
type t = t1 = Foo of t2
...
end
module B : sig
type t
end = strucr
type t = t2
...
end
とかできます
type t = t1 = Foo of t2
の構文が私が躓いていたポイントで、こう書かないとA.Foo x2
のようにコンストラクタが使えなくなってしまう。
LETREC言語はこのデザインで実装してみた:
Valenv.ml
はこんな感じ:
type valt = Num of int | Bool of bool | Proc of string * Exp.t * envt and envt = Empty | Extend of string * valt * envt | ExtendRec of string * string * Exp.t * envt module Val = struct type t = valt = Num of int | Bool of bool | Proc of string * Exp.t * envt let to_str = function | Num n -> string_of_int n | Bool b -> if b then "True" else "False" | Proc _ -> "Proc" end module Env = struct type t = envt let empty = Empty let rec find env s = match env with | Empty -> None | Extend (s', v', env') -> if s = s' then Some v' else find env' s | ExtendRec (fname, arg, body, env') -> if s = fname then Some (Val.Proc (arg, body, env)) else find env' s let extend env s v = Extend (s, v, env) let extend_rec env f a b = ExtendRec (f, a, b, env) end
Valenv.mli
にはvalt
の具体型、envt
の抽象型そしてVal
とEnv
のsignatureを書く:
type envt type valt = Num of int | Bool of bool | Proc of string * Exp.t * envt module Val : sig type t = valt = Num of int | Bool of bool | Proc of string * Exp.t * envt val to_str : t -> string end module Env : sig type t = envt val empty : t val find : t -> string -> valt option val extend : t -> string -> valt -> t val extend_rec : t -> string -> string -> Exp.t -> t end
Val.ml
とEnv.ml
でinclude Valenv.Val
、include Valenv.Env
するだけなのはPROCと同じ。
雑考
実はValenv
ではvalt
とenvt
の定義だけをしてVal.ml
とEnv.ml
で各モジュールの内容を定義できれば、と考えていたのだが、その場合うまくenvt
を抽象型にする方法が思い浮かばなかったので断念。Env.ml
の中ではenvt
の実装を使う必要があるので・・・ C++のFriend的な定義ができれば(Env
モジュールがVarenv
の実装に特権的にアクセスできるような指定ができれば)解決するのだが、そういう言語機能はなさそう。