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


これはML Advent Calendar 2017の13日目の記事です。
4日目の @keigoi さんの記事に触発されて書きました。

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

Standard MLとは

Standard ML(以下、SML)はThe Definition of Standard ML (Revised)にて形式的に定義されているプログラミング言語です。
この定義の内容は、ネット上にPDFが公開されています。

SMLの定義に対して、数多くのコンパイラが実装として存在しています。
Standard ML Familyを見ると、16種類ものコンパイラがあげられています。
個人的には、おそらく一番メジャーなSML/NJ、生成される実行ファイルが高速なMlton、日本製のSML#などが有名どころでしょうか。

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

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

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

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

実行例
$ 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]
実行例
# 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では下記のように書けます。

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に対する実装は、以下のように与えることができます。
また、使用例も一緒に書きます。

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
実行例
# Stack.push (1, Stack.create ());
val it = [1] : int list

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

先人の「let? val? コロン?イコール?」にならって、SMLでもモジュールとシグネチャの構文を比較してみます。

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

SMLではstructuresignatureが明確に別な構文として用意されているため、先人があげていたようなOCamlでのmodulemodule typeのような悩みは起こりにくいと思います。
一方で、SMLの宣言にはvalfunと別々な構文が用意されていますが、シグネチャ内ではvalのみしか書けません。
個人的には、このあたりがSMLでうっかり打ち間違うポイントだと思います。
また、モジュールやシグネチャ内では、シグネチャ宣言を書くことができません。

この先の話題

ファンクタ、不透明な制約、一部の透明な制約、型の共有など、SMLのモジュールには他にも様々な機能があります。
それらについては、書いていたところ長くなってしまったので、次回の記事でまとめます。

参考文献

  1. Robin Milner, Mads Tofte, Robert Harper and David Macqueen. (1997). The Definition of Standard ML, Revised Edition. The MIT Press.
  2. 大堀 淳. (2001). プログラミング言語Standard ML入門. 共立出版.

ソースコード