Standard MLのモジュールとシグネチャの機能

これは[ML Advent Calendar 2017](https://adventar.org/calendars/2142)の15日目の記事です。
13日目の私の[記事](https://qiita.com/keita44_f4/items/399eb270b9261ae1330c)の続きになります。

本稿ではSMLのモジュール・シグネチャについて、より細かな機能を紹介いたします。

# ファンクタ

先人の例であるOCmalでは、モジュールは第一級であり、関数や値と同等にモジュールを取り扱うことができます。
一方で、SMLのモジュールは第一級ではなく、モジュールがSMLコア（関数や式）とは切り離されて定義されています。
よって、モジュールを受け取ったり返したりするような関数を`fun`構文で作ることはできません。
しかしその代わりに、モジュールを受け取ったり返したりするために、SMLではモジュール専用のファンクタという機能が用意されています。

ファンクタを使うには、受け取るのと返すモジュールを記述します。[^1]
例えば、実行時に単相のスタックを作るファンクタ`MakeMonoStack`は以下のように書けます。
`ELEM`はファンクタ引数のモジュールを指定するシグネチャです。
`MONOSTACK`はファンクタ返り値のモジュールを指定するシグネチャです。

[^1]: 実際は多くの複雑な派生構文の組み合わせによって構文が拡張されています。それにより、ファンクタはモジュールを受け取る形だけでなく、`val x`や`type t`などを受け取る形でも書けます。後者のように書くと、内部では`struct ... end`が追加されて、モジュールを受け取るファンクタとして評価されています。

```sml
signature ELEM = sig type elem end
signature MONOSTACK =
sig
  type t
  type stack
  val create : unit -> stack
  val push : t * stack -> stack
  val pop : stack -> t * stack
end
functor MakeMonoStack (E : ELEM) : MONOSTACK =
struct
  type t = E.elem
  type stack = t list
  fun create () = nil
  fun push (x, s) = x :: s
  fun pop nil = raise Empty
    | pop (h::t) = (h, t)
end
```

ファンクタを利用してモジュールを受け取るには、以下のように関数適用のような構文を使用します。
関数適用と違って、括弧は省略できません。
ファンクタ`MakeMonoStack`にモジュール`Elem`を与えて、新たなモジュール`MyStack`を生成しています。

```sml
structure Elem = struct type elem = int end
structure MyStack = MakeMonoStack (Elem)
val s = MyStack.create ()
val s = MyStack.push (0, s)
val (x, s) = MyStack.pop s
```

# 不透明なシグネチャ制約

## 前章`MonoStack`や前記事`Stack`の問題点

前章で作ったファンタクタ`MakeMonoStack`をREPLで入力してみると、下記のようにプリントされます。
同様に、前記事で作ったモジュール`Stack`を少しだけ改変した`MonoStack`も入力してみます。

```shell-session
# functor MakeMonoStack (E : ELEM) : MONOSTACK =
> struct
>   type t = E.elem
>   type stack = t list
>   fun create () = nil
>   fun push (x, s) = x :: s
>   fun pop nil = raise Empty
>     | pop (h::t) = (h, t)
> end;
functor MakeMonoStack
  (sig
    type elem
  end)
  :
    sig
      type stack = 'elem list
      type t = 'elem
      val pop : 'elem list -> 'elem * 'elem list
      val create : unit -> 'elem list
      val push : 'elem * 'elem list -> 'elem list
    end
```

```shell-session
# structure MonoStack : MONOSTACK =
> struct
>   type t = int
>   type stack = t list
>   fun create () = nil
>   fun push (x, s) = x :: s
>   fun pop nil = raise Empty
>     | pop (h::t) = (h, t)
> end;
structure MonoStack =
  struct
    type stack = t list
    type t = int
    val pop = fn : t list -> t * t list
    val create = fn : unit -> t list
    val push = fn : t * t list -> t list
  end
```

プリント内容を見てみると、スタックがリスト型と表示されています。
つまり、モジュールの使用者に実装内容が見えてしまっており、悪意ある攻撃をする余地が残されています。
これはファンクタとモジュールのどちらでも同じ問題を抱えています。
前の記事のモジュール`Stack`も、スタックに対してプリンタが`int list`と表示していました。

例えばこのとき、以下のようなことができてしまいます。
自分で用意したリストを使って`MonoStack.push`ができてしまっています。
つまり、使用者が好きなようにスタックを改変できてしまいます。
これでは困る場合があります。

```shell-session
# val s = MonoStack.push (2, [0]);  (* 勝手に用意した[0] *)
val s = [2, 0] : int list
# (* ↑なんと、型チェックを通過してしまう！！ *)
```

## モジュール内の型を隠蔽する

そこでSMLでは、モジュールの型を隠蔽する機能が用意されています。
原文ではこの機能を「opaque constraint」と呼ばれ、日本語では「不透明なシグネチャ制約」と呼ばれています。
不透明な制約を使うには、先程の例でストラクチャにシグネチャを宣言した箇所の`:`を`:>`に変えます。

```sml
structure MonoStack :> MONOSTACK = (* ここが:>になっている！ *)
struct
  type t = int
  type stack = t list
  fun create () = nil
  fun push (x, s) = x :: s
  fun pop nil = raise Empty
    | pop (h::t) = (h, t)
end
```

このスタックを使って先ほどと同じようなアタックを試みると、下記のような実行結果になります。

```shell-session
# structure MonoStack :> MONOSTACK =
> struct
>   type t = int
>   type stack = t list
>   fun create () = nil
>   fun push (x, s) = x :: s
>   fun pop nil = raise Empty
>     | pop (h::t) = (h, t)
> end;
structure MonoStack =
  struct
    type stack  <hidden>
    type t  <hidden>
    val pop = fn : stack -> t * stack
    val create = fn : unit -> stack
    val push = fn : t * stack -> stack
  end
# val s = MonoStack.create ();
val s = _ : MonoStack.stack
# val s = MonoStack.push (2, [0]);
(interactive):176.8-176.30 Error:
  (type inference 016) operator and operand don't agree
  operator domain: MonoStack.t * MonoStack.stack
          operand: 'CTYJ::{int, int8, int16, int64,...}
                   * 'CTYZ::{int, int8, int16, int64,...} list
```

先ほどの例とは違って、スタックの型が`<hidden>`と表示され、実体がプリントされなくなりました。
また、リストを使って`MonoStack.push`しようとすると、型エラーが起こっています。
つまり、`MonoStack.stack`型の実装は隠されれ、モジュールの外では`MonoStack.stack`型と`MonoStack.list`型とは違う型として見えるようになりました。
これにより、使用者は`MonoStack.create`や`MonoStack.push`でしか`MonoStack.stack`を作ることができなくなりました。

# 一部の型だけ透明制約にする

これで型隠蔽でき、安全なスタックが作れました、とは行きません。
先ほどの例をよく見ると、もう一つ問題点があります。
モジュール`MonoStack`を使って、空のスタックを作って、`MonoStack.push`してみましょう。

```shell-session
# val s = MonoStack.create ();
val s = _ : MonoStack.stack
# val s = MonoStack.push (1, s);
(interactive):178.8-178.28 Error:
  (type inference 016) operator and operand don't agree
  operator domain: MonoStack.t * MonoStack.stack
          operand: 'CUZI::{int, int8, int16, int64,...} * MonoStack.stack
```

なんと`MonoStack.push`が型エラーで弾かれてしまいます。
これは`:>`によって、モジュール内部のすべての型が不透明制約になってしまっているからです。
本当は、`MonoStack.stack`は不透明制約に、`MonoStack.t`は透明制約にしたいです。
このように、シグネチャに不透明制約と透明制約の両方の型を混在させたいことがよくあります。

これを解決するために、SMLでは`where`構文を使って以下のように記述します。

```sml
(* シグネチャの後ろにwhere type t = int、を追加した！ *)
structure MonoStack :> MONOSTACK where type t = int =
struct
  type t = int
  type stack = t list
  fun create () = nil
  fun push (x, s) = x :: s
  fun pop nil = raise Empty
    | pop (h::t) = (h, t)
end
```

これをREPLで動作させると、以下のようになります。
想定通り、`MonoStack.stack`の型だけが`<hidden>`になり、`MonoStack.t`型は`int`型であることが公開されています。
先ほど失敗した`MonoStack.push`も想定通りの動作をしてくれます。

```shell-session
# structure MonoStack :> MONOSTACK where type t = int =
> struct
>   type t = int
>   type stack = t list
>   fun create () = nil
>   fun push (x, s) = x :: s
>   fun pop nil = raise Empty
>     | pop (h::t) = (h, t)
> end;
structure MonoStack =
  struct
    type stack  <hidden>
    type t = int
    val pop = fn : stack -> t * stack
    val create = fn : unit -> stack
    val push = fn : t * stack -> stack
  end
# val s = MonoStack.create ();
val s = _ : MonoStack.stack
# val s = MonoStack.push (1, s);
val s = _ : MonoStack.stack
```

# モジュール・シグネチャの展開

大規模なプログラムを作成していると、他のモジュールやシグネチャの内容を再利用したいときがあります。
例えばよく使うのは、既にあるモジュールに新たな関数を追加して、新しいモジュールをつくる場合です。
先ほどのモジュール`MonoStack`に、スタックの空判定をする関数`isEmpty`を追加してみましょう。
これは、以下のように書けます。

```sml
signature MONOSTACK' =
sig
  include MONOSTACK  (* includeですでにあるシグネチャを使う *)
  val isEmpty : stack -> bool
end
structure MonoStack' =
struct
  open MonoStack  (* openですでにあるストラクチャを使う *)
  fun isEmpty stack =
    let val _ = pop stack in false end
    handle Empty => true
end
```

新たな関数`isEmpty`を追加したシグネチャ`MONOSTACK'`とモジュール`MonoStack'`を定義しました。
ただし、元の`MonoStack`が不透明なシグネチャ制約のため、ここではスタックのデータ構造にアクセスできません。
そのため、例外処理をハックすることで、空判定を行っています。

`include`はシグネチャ内でのみ使える構文で、シグネチャの中身が評価されて展開されます。[^5]
一方で、`open`は通常の宣言としても使えます。
これは、モジュール内の関数や型を、モジュール名のプレフィクス無しに呼び出せるようにするための構文です。
モジュール内で使えば、既存モジュールの中身が展開され再利用ができます。

[^5]: ここで言う展開はマクロではなく、評価による展開が行われます。

REPLで評価してみると、下記のようになります。
シグネチャやモジュールが拡張できている様子を確認できます。

```shell-session
# signature MONOSTACK' =
> sig
>   include MONOSTACK
>   val isEmpty : stack -> bool
> end;
signature MONOSTACK' =
  sig
    type stack
    type t
    val create : unit -> stack
    val push : t * stack -> stack
    val pop : stack -> t * stack
    val isEmpty : stack -> bool
  end
# structure MonoStack' =
> struct
>   open MonoStack
>   fun isEmpty stack =
>     let val _ = pop stack
>     in false end
>     handle Empty => true
> end;
structure MonoStack' =
  struct
    type stack  <hidden>
    type t = int
    val create = fn : unit -> stack
    val push = fn : t * stack -> stack
    val pop = fn : stack -> t * stack
    val isEmpty = fn : stack -> bool
  end
# val b = MonoStack'.isEmpty (MonoStack'.create ());
val b = true : bool
```

# 型の共有[^4]

さらに大規模なプログラムを作成していると、より複雑な型の制約をつけたくなってきます。
既存のモジュールから新しいモジュールを作るとき、ただし一部の型が一緒の制限をつけたいことがあります。[^3]

そんな場合はSMLの`sharing`を使います。
例えば下記のようなシグネチャが記述できます。
このシグネチャ`AB`では、モジュールAにある`A.ta`型とモジュールBにある`B.tb`型が同値である制約をかけています。

```sml
signature AB =
sig
  structure A : sig type ta end  (* モジュールAはta型を持つ *)
  structure B : sig type tb end  (* モジュールBはtb型を持つ *)
  sharing type A.ta = B.tb  (* A.taとB.tbが同じ型という制約がつく *)
end
```

[^3]: コンパイラやパーサジェネレータなどの規模にならないと、そんなことは無いかもですが。例えば、[マップやセットのキーを共有したり](https://github.com/smlsharp/smlsharp/blob/49f32e7e2b0d383b8ca7a0641b594fd49fbe9fe0/src/compiler/data/name/main/LOCAL_ID.sig#L10)、[パーサジェネレータにおいてLexerとParserのtoken型を共有したり](https://github.com/smlsharp/smlsharp/blob/master/src/ml-yacc/src/yacc.grm.sig#L56)、[CharとChar関係モジュールでchar型を同値として取り扱ったり](https://github.com/smlsharp/smlsharp/blob/53653f4bb19464aa3448e4b23a8d75c39d71d890/src/basis/main/TEXT.sig#L10)などの例があります。

[^4]: SMLの`sharing`機能の日本語記事はなかったので、おそらく本稿が世界初だと思います（言い過ぎ）。

# まとめ

本稿ではSMLのモジュール・シグネチャで使える構文と機能を紹介しました。

- モジュールは第一級ではなく、動的モジュールを作る専用機能としてファンクタが用意されている。
- 透明なシグネチャ制約」と「不透明なシグネチャ制約」を使って、シグネチャ内の型の公開・隠蔽を行う。
- モジュールの展開には`open`を、シグネチャの展開には`include`を使う。
- シグネチャ内で同値な型を指定するためには`sharing`を使う。

個人的な感想として、OCamlやHaskellに比べると、SMLの利用者は少ない感触を受けています。
今後、こういった記事から興味を持って、SMLerが一人でも多く増えることを祈っています。[^2]

[^2]: 具体的にはSMLのお仕事がもっと増えて、自分がSMLで簡単に食っていけるくらいに増えてください、増えろ。

# 参考文献

前記事と同じです。

1. [Robin Milner, Mads Tofte, Robert Harper and David Macqueen. (1997). The Definition of Standard ML, Revised Edition. The MIT Press.](https://mitpress.mit.edu/books/definition-standard-ml)
    - [Amazon](http://amzn.to/2AW2arU)
2. [大堀 淳. (2001). プログラミング言語Standard ML入門. 共立出版.](http://www.kyoritsu-pub.co.jp/bookdetail/9784320120242)
    - [Amazon](http://amzn.to/2BHEWcp)

# ソースコード

- [Github](https://github.com/yonta/sml-strucuture-tutorial)