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言語はその方法で実装してみた：

github.com

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
module A = struct
type t = t1 = Foo of t2
...
end
module B : sig
type t
end = strucr
type t = t2
...
end
とかできます

— Jun Furuse 🐫🌴 (@camloeba) 2019年6月3日

type t = t1 = Foo of t2の構文が私が躓いていたポイントで、こう書かないとA.Foo x2のようにコンストラクタが使えなくなってしまう。

LETREC言語はこのデザインで実装してみた：

github.com

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の実装に特権的にアクセスできるような指定ができれば）解決するのだが、そういう言語機能はなさそう。