MLtonを使ってみる

MLton という Standard ML のコンパイラが、結構速いバイナリを生成する
と Twitter で聞いたので、どんなものか試します。

MLton の読み方がわかりませんね。FAQ によると、

"MLton" is pronounced in two syllables, with stress on the first syllable.
The first syllable sounds like the word mill (as in "steel mill"), the
second like the word tin (as in "cookie tin").

http://mlton.org/Pronounce

なので、「ミルティン」でいいと思うのですが。

インストール

web ページからバイナリを圧縮したものをダウンロードして、
/ で展開してインストールします。
ソースコードもダウンロードできますが、MLton をビルドするのに
MLton を使っているので完動品(?)がないとだめっぽいです。
セルフホスティングなのでしょうか。

素数判定

素数判定するコードを書きます。適当に大きな数、100000 から 200000 の
間にある素数を列挙させて、どれくらい時間がかかるかをみます。

判定法について

ミラー・ラビン法を使って判定します。[2, (sqrt n)] で割るという
方法以外で、私が書けるのはこれだけなので。
ミラー・ラビン法については Wikipedia で調べてください。

Wikipedia には実装についての説明もありますが、私にはよくわかりませんでした。

SICP、計算機プログラムの構造と解釈の一章に素数判定の節があって、
その節の演習問題でミラー・ラビン法で判定する手続きを書け、という
ものがあります。ここで示されている「expmod に 0 を返させる」という
方針が私にはわかりやすかったので、これに基づいて書きます。

またね

といったところでお時間となってしまいましたので、
いったんここで切りますね。
次回は Standard ML でミラー・ラビン法を使った素数判定をする関数を
書いて、MLton でライブラリを使うのに苦労した、という話を書きます。