Standard MLのモジュール（structure）とシグネチャ（signature）の構文の違い

これは[ML Advent Calendar 2017](https://adventar.org/calendars/2142)の13日目の記事です。
4日目の @keigoi さんの[記事](https://qiita.com/keigoi/items/c2d5e07a7b0bae49b18d)に触発されて書きました。

この記事は特に新規性があるわけではなく、SMLのモジュールの紹介記事です。

# Standard MLとは

Standard ML（以下、SML）は[The Definition of Standard ML (Revised)](https://mitpress.mit.edu/books/definition-standard-ml)にて形式的に定義されているプログラミング言語です。
この定義の内容は、ネット上に[PDF](http://sml-family.org/sml97-defn.pdf)が公開されています。

SMLの定義に対して、数多くのコンパイラが実装として存在しています。
[Standard ML Family](http://sml-family.org/)を見ると、16種類ものコンパイラがあげられています。
個人的には、おそらく一番メジャーな[SML/NJ](http://www.smlnj.org/)、生成される実行ファイルが高速な[Mlton](http://www.mlton.org/)、日本製の[SML#](http://www.pllab.riec.tohoku.ac.jp/smlsharp/)などが有名どころでしょうか。

# SMLのモジュールシステムの概要

SMLももちろんモジュールシステムを持っています。
よく使われる方法としては、型とその型に対する操作をまとめたものを、モジュールとして提供します。
例えば、`List`モジュールは、`'a list`型と、`length`関数などを提供しています。

SML/NJでは`open List`、SML#では`open List`や`structure L = List`などを、REPLで評価するとモジュールの内容を見ることができます。

この記事では、コードとそのコードをREPLで実行した例をあげます。
実行はSML# 3.4.0にて行っています。
REPLでの実行例では、入力待ちを表す`#`や`>`もそのまま記述します。

```shell-session:実行例
$ smlsharp
SML# 3.4.0 (2017-08-31 19:31:44 JST) for x86_64-pc-linux-gnu with LLVM 3.7.1
# [1, 2, 3];
val it = [1, 2, 3] : int list
# length;
val it = fn : ['a. 'a list -> int]
```

```shell-session:実行例
# structure L = List;
structure L =
  struct
    datatype 'a list = :: of 'a * 'a list | nil
    val getItem = fn : ['a. 'a list -> ('a * 'a list) option]
    val hd = fn : ['a. 'a list -> 'a]
    val @ = fn : ['a. 'a list * 'a list -> 'a list]
    val last = fn : ['a. 'a list -> 'a]
    val all = fn : ['a. ('a -> bool) -> 'a list -> bool]
    val length = fn : ['a. 'a list -> int]
    val collate = fn : ['a. ('a * 'a -> order) -> 'a list * 'a list -> order]
    val map = fn : ['a,'b. ('a -> 'b) -> 'a list -> 'b list]
    val drop = fn : ['a. 'a list * int -> 'a list]
    val mapPartial = fn : ['a,'b. ('a -> 'b option) -> 'a list -> 'b list]
    val filter = fn : ['a. ('a -> bool) -> 'a list -> 'a list]
    val foldl = fn : ['a,'b. ('a * 'b -> 'b) -> 'b -> 'a list -> 'b]
    val nth = fn : ['a. 'a list * int -> 'a]
    val null = fn : ['a. 'a list -> bool]
    val app = fn : ['a. ('a -> unit) -> 'a list -> unit]
    val partition = fn : ['a. ('a -> bool) -> 'a list -> 'a list * 'a list]
    val exists = fn : ['a. ('a -> bool) -> 'a list -> bool]
    val rev = fn : ['a. 'a list -> 'a list]
    val foldr = fn : ['a,'b. ('a * 'b -> 'b) -> 'b -> 'a list -> 'b]
    val revAppend = fn : ['a. 'a list * 'a list -> 'a list]
    val concat = fn : ['a. 'a list list -> 'a list]
    val tabulate = fn : ['a. int * (int -> 'a) -> 'a list]
    exception Empty = List.Empty
    val take = fn : ['a. 'a list * int -> 'a list]
    val find = fn : ['a. ('a -> bool) -> 'a list -> 'a option]
    val tl = fn : ['a. 'a list -> 'a list]
  end
```

# おおまかな、シグネチャの構文

SMLではモジュールのインタフェースとして、シグネチャを宣言することができます。
シグネチャにはモジュールが持っている必要がある型や値や関数やモジュールを書くことができます
シグネチャはよく`.sig`拡張子のファイルに書かれます。

例えば、先人に習って純粋なスタックを作ろうとします。
スタックは、スタックの型、空のスタックの値、スタックに対する操作（push/pop）が必要です。
SMLでは下記のように書けます。

```sml:STACK.sig
signature STACK =
sig
  type 'a stack
  val create : unit -> 'a stack
  val push : 'a * 'a stack -> 'a stack
  val pop : 'a stack -> 'a * 'a stack
end
```

# おおまかな、ストラクチャの構文

シグネチャは必要な型や関数などの名前を宣言するだけで、実装はありませんでした。
SMLでのモジュール内容の実装は、ストラクチャと呼ばれる構文で行います。
ストラクチャは`.sml`拡張子のファイル1個に1つ書かれることが多いです。

例えば先の例であげたシグネチャ`STACK`に対する実装は、以下のように与えることができます。
また、使用例も一緒に書きます。

```sml:Stack.sml
structure Stack : STACK =
struct
  type 'a stack = 'a list
  fun create () = nil
  fun push (x, s) = x :: s
  fun pop nil = raise Empty
    | pop (h::t) = (h, t)
end
```

```shell-session:実行例
# Stack.push (1, Stack.create ());
val it = [1] : int list
```

# モジュールとシグネチャの構文の違い

[先人の「let? val? コロン？イコール？」](https://qiita.com/keigoi/items/c2d5e07a7b0bae49b18d#let-val-%E3%82%B3%E3%83%AD%E3%83%B3%E3%82%A4%E3%82%B3%E3%83%BC%E3%83%AB)にならって、SMLでもモジュールとシグネチャの構文を比較してみます。

| どこで | モジュール内 | シグネチャ内 |
| :-- | :-- | :--- |
| val | val x = exp | val x : t |
| fun | fun f x = exp | val f : t1 -> t2 |
| type | type t1 = t2 | type t1 = t2 または type t1 |
| structure | structure A : S = struct ... end | structure A : S 
| signature | 書けない | 書けない |

SMLでは`structure`と`signature`が明確に別な構文として用意されているため、先人があげていたようなOCamlでの`module`と`module type`のような悩みは起こりにくいと思います。
一方で、SMLの宣言には`val`と`fun`と別々な構文が用意されていますが、シグネチャ内では`val`のみしか書けません。
個人的には、このあたりが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)