LunarMLの進捗2021

この記事は ML (Meta Languages) Advent Calendar 2021 の8日目の記事です。

数年前からLunarMLというStandard MLコンパイラーを作っています。この記事では、LunarMLの今年の進捗を報告します。

https://github.com/minoki/LunarML

LunarMLの進捗状況は、ちょくちょくこのブログでも報告してきました：

今年の進捗まとめ

まず、去年の段階では「1+2がコンパイルできるようになった」と言って記事にしていたという状態でした。print 関数を追加してHello worldができるようになったのは今年の話です。

翻って現在では、SML ’97の言語機能は一通り実装したところまで辿り着いたので、思えば遠くへ来たものだなあと思います。まだまだ「標準ライブラリーの拡充」や「セルフホストの実現」「JavaScriptターゲットの実装」など、道は果てしなく続いているわけですが……。

この一年で実装した機能はたくさんありますが、敢えて挙げるとすれば、モジュールシステムでしょう。structure, signature, functorなどです。今年の初め頃はstructureのsの字もありませんでした。

直近の進捗

前回の進捗報告記事（10月30日）ではfunctorの実装ができたことを報告しました。その後もちょいちょい機能拡充を進めているので報告します。

複数ファイルのコンパイル：ML Basis system

Standard MLには標準化された複数ファイルコンパイルの方法がありません。とはいえ、規模の大きなプログラムを書くにはプログラムを複数のファイルに分けて記述することが不可欠です。

というわけで、それぞれの処理系はそれぞれ複数ファイルコンパイルの仕組みを提供しています。SML/NJではCompilation Manager, MLtonやMLKitではML Basis system, SML#ではSMIという仕組みで複数ファイルのコンパイルをサポートしています。

LunarMLでも何らかの方法で複数ファイルのコンパイルに対応したいところです。LunarML自身はMLtonでコンパイルしており、必然的にML Basis systemを使っているので、LunarML自身もML Basis systemに対応するのが自然な発想です。

というわけで、ML Basis systemに対応させました。

ML Basis systemの最も単純な使い方は、拡張子mlbのファイルに

$(SML_LIB)/basis/basis.mlb
file1.sml
file2.sml
file3.sml

という風にファイル名を並べて書くやり方です。この書き方では、各ファイルが連結されたかのように順番に実行されます。後ろに書いたファイルからは前に書いたファイルの宣言が見えます。

MLBファイルからは他のMLBファイルを読み込むこともできます。通常は標準ライブラリー $(SML_LIB)/basis/basis.mlb を始めに読み込むことになるでしょう。

MLBファイル中でのソースファイルへの言及は宣言として扱われます。宣言は local 宣言を使うことによりスコープの管理ができます。例えば、

$(SML_LIB)/basis/basis.mlb
local
  file1.sml
in
  file2.sml
end
file3.sml

と書くと file2.sml からは file1.sml の宣言が見えますが、 file3.sml からは file1.sml の宣言が見えなくなります。SMLのコア言語やモジュール言語の local と同様ですが、MLBファイルの local ではsignatureとfunctorもスコープの管理の対象となります。

一度読み込まれたMLBファイルはキャッシュされます。例えば

$(SML_LIB)/basis/basis.mlb
$(SML_LIB)/basis/basis.mlb
$(SML_LIB)/basis/basis.mlb
foo.sml

と書いても $(SML_LIB)/basis/basis.mlb の読み込みは一度しか行われません。

このほか、basis式というのもありますが割愛します。

ML Basis systemには条件コンパイルのような機能はなく、環境によって処理を変えたい場合はpath mapという仕組み（$(FOO) みたいな変数）で読み込むファイルを切り替えます。path mapがLunarMLの標準ライブラリー記述の需要を十分に満たしてくれるかはまだ分かりません。

コンパイル時にフラグで制御したい項目の例として、現段階では、標準ライブラリーでIntInf（後述）を提供するか（LargeIntをIntInfにするかInt64にするか）というのがあります。スクリプト言語のソースコードを出力する処理系としては、多倍長整数の実装を出力コードに含めるかは選べるようにしたいところです。

ユーザー定義のオーバーロード

SMLでは + や < などのいくつかの組み込み演算子（組み込み関数）が組み込み型についてオーバーロードされています。演算子オーバーロードが提供される組み込み型は

符号つき整数型：int, IntN.int, IntInf.int
符号なし整数型：word, WordN.word
浮動小数点数型：real, RealN.real
文字型：char, WideChar.char
文字列型：string, WideString.string

です。

処理系の実装方法としては、これら全てをコンパイラーの組み込みとする、という方針がありうるでしょう。しかし、型と演算全てをコンパイラーに組み込むのは大変です。なるべく多くの部分をSMLで記述するライブラリー部分に追い出したいのが人情です。特に、 IntInf はSMLで記述できれば異なるターゲット間で使い回しができます。

別の方法は、SMLで書かれた型と演算について組み込み演算子のオーバーロードを可能にする特別な指令を用意することです。

structure IntInf = struct
  ...
end
(* ここに特別な指令を書くことによって IntInf.int について組み込み演算子のオーバーロードができるようになる *)

LunarMLでは後者の方法を採用します。現在の構文は

structure IntInf = struct
  ...
end
_overload "Int" [IntInf.int]
  { + = IntInf.+
  , - = IntInf.-
  , * = IntInf.*
  , div = IntInf.div
  , mod = IntInf.mod
  , abs = IntInf.abs
  , ~ = IntInf.~
  , < = IntInf.<
  , <= = IntInf.<=
  , > = IntInf.>
  , >= = IntInf.>=
  }

という感じになっています。これは内部的に使うことを想定された機能なので、構文は予告なく変更されることがあります。

SMLでは組み込み演算子だけではなくリテラルもオーバーロードの対象になります。LunarMLは現時点でリテラルのオーバーロードには未対応です。

組み込み関数の呼び出し

Standard MLの関数は基本的には引数を一つだけ受け取ります。複数の引数を受け取る関数というのは、タプルを受け取る関数 int * int -> int か、関数を返す関数（カリー化） int -> int -> int として表現されます。

さて、LunarMLではいくつかの機能を組み込み関数として定義しています。例えば、Int.+ : int * int -> int はSML自身で実装するのは難しいでしょう。

組み込み関数の実体は、コンパイラー自身に内蔵するか、オブジェクトコードと直接リンクできる言語（ネイティブコードを出力する処理系ならCやアセンブリー、LunarMLの場合はLua）で書くのが通常かと思います。ここで、組み込み関数自身を第一級の値として使えるようにするには、組み込み関数も実行時に実体を持ち、SMLの呼び出し規約に従う必要があります。

そのため、少し前までのLunarMLではそれぞれの組み込み関数についてLuaで

function __Int_add(x, y)
  ...
end
function _Int_add(t)
  return __Int_add(t[1], t[2])
end

というコードを書いていました。_Int_add が Int.+ の実体です。LunarMLの関数は「ただ一つの引数を受け取り、ただ一つの値を返すLuaの関数」にコンパイルされるので、_Int_add もただ一つの引数（2要素タプル；Luaではテーブル）を受け取ります。

しかし、組み込みの二項演算というよく使われる関数呼び出しにいちいちタプルを構築するのは無駄です。幸い、LunarMLでは最適化によって Int.+ (x, y) のような呼び出しでタプルを構築しない（Luaの __Int_add を2引数で呼び出す）ようにできるのですが、そうすると今度は _Int_add を用意するのが馬鹿らしくなります。Int.+ の利用のされ方が全て関数呼び出しの形であれば _Int_add を出力ファイルに書き込まない、ということができれば良いのですが、LunarMLでは現在のところLuaコードに対する不要コード削除を実装していません。

あるいは、Int.+ が関数呼び出し以外の形で（エスケープする形で）利用されていたらその都度 function(t) return __Int_add(t[1], t[2]) end というコードを埋め込む、というやり方もできると思いますが、Int.+ が値として複数回利用されている場合は生成コードの増大に繋がります。

LunarMLではSMLコードに対する不要コード削除はすでに実装しているので、Int.+ をSML側で定義すればこれらの問題は解消します。

structure Int = struct
  fun x + y = (* compiler magic で定義する *)
end

もっと汎用的には、「複数の引数を取る組み込み関数をSML的な実体を用意せずに書けるようにする」のが目標となります。

LunarMLでは、_primCall "名前" (引数1, 引数2, ..., 引数n) という構文で組み込み関数の呼び出しを書けるようにしました。引数の周りの丸括弧は構文の一部で、引数はタプルではありません（_primCall "名前" { 1 = 引数1, ... } や _primCall "名前" arg とは書けない）。

これを使うと、例えば Word.+ : word * word -> word は

structure Word = struct
  fun x + y = _primCall "Word.+" (x, y)
end

と定義できます。一方 Int.+ は

structure Int = struct
  fun x + y = _primCall "call2" (_primVal "Int.+", x, y)
end

となっています。call2というのはLuaの f(x, y) のような2引数関数呼び出しに相当し、_primVal "Int.+” はLuaの __Int_add 関数を指します。

これで、「Luaで書かれた部分」を削減することができるようになりました。

（こんな実装の詳細を堂々と語ってどうすんのじゃ、って感じですが）

多倍長整数（IntInf）の実装

多倍長整数があると便利です。オーバーフローの心配をせずに整数演算ができます。プログラミング言語によっては、標準で多倍長整数を提供しているものがあります。

Standard MLにも、必須ではないものの多倍長整数がIntInfストラクチャーという形で規定されています。コンパイルターゲットであるLuaには標準の多倍長整数はないので、LunarMLでIntInfを提供するとしたら実装を自前で用意することになります。

IntInfはオプショナルな機能なので、IntInfを提供しなくてもStandard ML処理系を名乗ることができます。しかし、LunarMLでは、自前で用意してでもIntInfを提供することにしました。理由は以下です：

多倍長整数があると数学っぽいプログラムを動かせて楽しい。
LunarML自身の実装にIntInfを使いたいと思っている（リテラル周り）。一方で将来的にはLunarMLで自身をコンパイルできるようにしたいが、そうするとLunarMLでIntInfを提供する必要がある。

多倍長整数の実装は、Luaで用意するやり方とSMLで用意するやり方が考えられます。Luaで書かれた多倍長整数の実装は既に色々あるので、短期的にはLuaで用意した方が楽でしょう。しかし、LunarMLでは、SMLでIntInfを実装することにしました。これは、今後他の言語（JavaScriptとか）をターゲットにする際にSMLであれば実装をそのまま使いまわせるからです。

既に述べたように、IntInfは組み込み演算子とリテラルのオーバーロードの対象であり、純粋なSMLで提供することはできません。そこは先述した独自拡張の _overload 宣言でゴニョゴニョします。

というわけで、Knuthの本を参考にしつつSMLでIntInfを実装しました。乗算に素朴な筆算のアルゴリズムを用いているため、遅いです。

今のところ、テストプログラムとして

フィボナッチ数1000個の計算
階乗の計算1000個
ウィルソンの定理で1000未満の素数を列挙
ベルヌーイ数100個の計算
- Standard MLの標準に多倍長整数はあっても有理数は規定されていないので、有理数演算は自前です。

などが動いています（test/mlbasis/should_run/以下）。この他、暗号関係のアルゴリズムや、浮動小数点数のエミュレート、円周率計算などできることは色々あるはずです。

今後やること

前回の進捗報告と被りますが、今後やりたいことを列挙していきます。

標準ライブラリーの充実
- Standard ML Basis Libraryの必須の部分はなるべく提供するようにしたいです。
パターンマッチの改良
- 網羅性とか冗長性とかの判定、コード生成の改良等です。
Successor MLへの対応
- 便利そうなやつを追加したいです。
コンパイルの高速化
- IntInfを実装したらめちゃくちゃ遅くなりました。高速化したいです。
より良い最適化
- より自然で効率の良いLuaコードを出力できるようにしたいです。
LuaJITターゲットの実装
- 現行のコード生成器はLua 5.3以降を対象としており、LuaJITやLua 5.2では動作しません。なので、LuaJITターゲットも別途実装したいです。
JavaScriptターゲットの実装
- WebとかNode.jsとかで動いたらいいなあ。
セルフホストの実現
- Standard MLでコンパイラーを書いているからには是非ともやりたいです。
- 標準ライブラリーを拡充して、ML-Yaccの利用とsmlnj-libの利用をどうにかすればいけそうです。

今年の残り、それから来年もゆる〜くやっていこうと思っていますので、よろしくお願いします。

Spread the love

雑記帳

人生やっていき