M.Hiroi's Home Page
http://www.geocities.jp/m_hiroi/

Functional Programming

[ Home ]

WHAT'S NEW


CONTENTS


お気楽 Standard ML of New Jersey 入門

CONTENTS

Yet Another SML/NJ Problems


はじめに

Standard ML of New Jersey (SML/NJ) は ML (Meta Language) という関数型プログラミング言語の一つです。ML は 1970 年代後半に Edinburgh 大学で定理証明を行うシステム Edinburgh LCF を記述するため、R. Minler 博士を中心に開発された言語です。その後、改良が重ねられ、いくつかの ML 処理系が作られました。SML/NJ はその一つで、AT&T の MacQueen 氏と Princeton 大学の Appel 氏によって作成された実用的な ML 処理系です。

SML/NJ は次のサイトからダウンロードできます。Windows 用のバイナリが用意されているので、とても簡単にインストールすることができます。

関数型言語というと Lisp (Common Lisp, Scheme) が有名です。Lisp の場合、データに型はありますが、変数に型はありません。これに対し ML は強く型づけされた言語で、コンパイル時に静的な型チェックを行うことで、多くのエラーを検出することができます。

ML で一番有名な機能は「型推論」でしょう。ML はプログラムから変数などのデータ型を見つけてくれるので、プログラマが型を宣言する必要はほとんどありません。推論できない場合にかぎり、ML は型宣言を要求します。この機能により、ML は静的な型チェックを行う「型付きの言語」でありながら、 Lisp のような柔軟なプログラミングが可能になっています。この他にも、パターンマッチング、多相型関数、モジュール・システムなど、ML には興味深い機能がたくさんあります。

●簡単なベンチマーク (改訂 2012/05/20)

SML/NJ はプログラムをネイティブコードにコンパイルして実行するので、バイトコードにコンパイルする処理系よりもプログラムを高速に実行することができます。その実行速度ですが、たらいまわし関数を使って調べてみました。

リスト:たらいまわし関数 (SML/NJ)

fun tak(x, y, z) = 
  if x <= y then z
  else tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))

(* 時間計測用 *)
fun tak_exec(x, y, z) =
  let 
    val a = Timer.startRealTimer()
  in
    tak(x, y, z);
    Timer.checkRealTimer( a )
  end

SML/NJ の場合、プログラムを入力すると自動的にコンパイルされます。対話モードの場合、use "ファイル名"; と入力すると、ファイルをロードしてプログラムがコンパイルされます。SML/NJ を実行するときに、"C> sml ファイル名" のようにコマンドラインからファイル名を入力してもかまいません。

それでは実行結果を示します。tak(20, 10, 0) を計算しました。使用した SML/NJ のバージョンは 110.74 です。比較のため、Ruby, Python, CLISP (Common Lisp), SBCL (Common Lisp), Gauche (Scheme), OCaml (ocamlc, ocamlopt), GCC (C言語) の実行結果を示します。 GCC, SBCL, ocamlopt, SML/NJ 以外の処理系はプログラムをバイトコードにコンパイルするものです。

表 : tak(20, 10, 0) の結果
処理系
Python (ver 2.7.3)14.51
Ruby (ver 1.9,3)11.35
CLISP (ver 2.48)5.71
Gauche (ver 0.9.2)4.65
ocamlc (ver 3.12.1)3.14
SBCL (ver 1.0.55)0.94
SML/NJ (ver 110.74)0.57
GCC -O (ver 4.5.3)0.37
SBCL (最適化)0.34
GCC -O2 (ver 4.5.3)0.30
ocamlopt (ver 3.12.1)0.16

SML/NJ は SBCL (Common Lisp) より速い結果になりましたが、GCC と OCaml にはかないませんでした。ただし、SBCL は最適化オプションを指定すると SML/NJ よりも速くなります。最適化オプションを指定したプログラムは拙作のページ Common Lisp Programming をお読みください。興味のある方は、ほかのプログラムでも試してみてください。

-- 改訂 --------
2012/05/20 たらいまわし関数の実行結果を更新

参考文献と URL

関数型言語全般

  1. 「関数型言語」に関するFAQ形式の一般的説明, (住井英二郎さん)
  2. 函数プログラミングのエッセンスと考え方(PDF). (小笠原啓さん)
  3. 関数プログラミング入門, (田中英行さん)

Standard ML of New Jersey

  1. Jeffrey D.Ullman (著), 神林靖 (訳), 『プログラミング言語ML』, 株式会社アスキー, 1996
  2. Ravi Sethi (著), 神林靖 (訳), 『プログラミング言語の概念と構造』, アジソンウェスレイ, 1995
  3. 児玉靖司, 『SML 演習 The Meta Language』, http://yk.i.hosei.ac.jp/
  4. 大黒学, 『初級 ML 講座』, 無料チュートリアル:プログラミング

『お気楽 Standard ML of New Jersey 入門』の著作権は筆者「広井誠 (Makoto Hiroi) 」が保持します。無断使用や無断転載は禁止いたします。お気楽 Standard ML of New Jersey 入門で作成したプログラムはフリーソフトウェアとします。ご自由にお使いください。プログラムの改造や配布もご自由にどうぞ。その際は、出典を明記してくださるようお願いいたします。

ただし、これらのプログラムは無保証であり、使用したことにより生じた損害について、作者「広井誠 (Makoto Hiroi) 」は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。

Copyright (C) 2005-2012 Makoto Hiroi
All rights reserved.

[ Home ]