自作SML処理系進捗：Hello Lua!

minoki/LunarML: A Standard ML compiler that produces Lua

進捗

前回の記事以降の進捗を書いてみる。

プロジェクト名を DamepoML から LunarML に変えた。
字句解析・構文解析時にソース位置を記録し、エラーメッセージに出力できるようにした。
- 型推論時のエラーはまだ。
ユーザー定義のデータ型をサポートした。
- equalityは未実装。
例外をサポートした。
- raise, handle, exception
名前空間としてのstructureをサポートした。
- signature, functorは未実装。
標準ライブラリーの拡充：SMLでも書けるようにした。
テストの用意
- 実行と出力結果のテストだけではなく、コンパイルが通らないことのテストも書ける。
Lua FFIに着手した。

structureのコンパイル方法は悩んだが、コンパイル時のあるフェーズ以降では所属するstructureに関わらず全てフラットな名前空間に配置するようにした。つまり、

structure Foo = struct
val x = "foo"
end;
print x;

は

local Foo_x = "foo" -- 実際は変数名は違う
io.write(Foo_x)

というコードにコンパイルされ、

local Foo = {
  x = "foo"
}
io.write(Foo.x)

とはならない。この辺の動作はfunctorとの兼ね合いや後述するLuaでのローカル変数の数の関係で、再考するかもしれない。

未実装な言語機能としては

withtype (derived form)
abstype
- Successor MLで規定されているようなderived formとして実装するつもりである。
signature
functor

などがある。

Luaでのローカル変数の数

Luaをコンパイル先言語として使う場合に注意すべきこととして、ローカル変数の数が200を超えるとエラーになるということがある。

Luaコードを手書きする場合はこの制限に引っかかることはそうそうないだろうし、回避方法もいくつか知られている。

しかし、コンパイラーでLuaコードを自動生成する場合はコンパイラーが注意しなければならない。

なお、ローカル変数の個数の制限の対象となるのは「その時点でスコープに入っている変数（シャドーイングされたものも含む）」であり、do-endによりスコープを外れたものは考慮されない。

つまり、

local a
local a
...
local a

と local a を202行並べたものはエラーとなるが、

do local a end
do local a end
...
do local a end

と do local a end を202行並べたものはエラーとならない。

なので、生存期間の短い変数はdo-endでスコープを狭くしてやるという手がある。

Lua FFI

コンパイル先がLuaであるということは、Luaの機能を何らかの形で呼び出せる必要がある。これは応用上も重要だし、標準ライブラリーをSML自身で記述する上でも重要だ。このための方式はいくつか考えられる。

コード片を埋め込む方式
呼び出したい関数名を指定する方式（C FFIみたいな）
Luaの世界に対するAPIを用意する方式
SMLの世界とLuaの世界をつなぐグルーコードをLuaで書けるようにする方式（参考：PureScript）

「コード片を埋め込む方式」だと埋め込んだコード中の自由変数（グローバル変数への参照）とSMLコンパイラーが生成した変数名が被ってしまう可能性がある。埋め込んだLuaコードをパースするか、プログラマーに自由変数のリストを明示させるようにすれば回避できるかもしれないが面倒くさい。

呼び出したい関数名を指定する方式は、C FFIによく見られるやつだ。C言語のように呼び出したい機能が関数の形で定義されている場合は良いが、Luaは関数以外にも「テーブルの参照」とか「組み込みの演算子」とか色々あるので機能的に不十分だと考えられる。

Luaの世界に対するAPIを用意する方式というのは、

structure Lua : sig
  type value
  val sub : value * value -> value (* t[k] *)
  val set : value * value * value -> unit (* t[k] = v *)
  val global : string -> value (* _ENV[x] *)
  val call : value -> value vector -> value vector (* f(args) *)
  val method : value * string -> value vector -> value vector (* f:name(args) *)
  val fromInt : int -> value
  val fromString : string -> value
  val newTable : unit -> value
  val function : (value vector -> value vector) -> value
end

という風に「Luaの値を表す型 value」と「Luaの各種構文に対応する組み込み関数」を用意する方式だ。

グルーコード方式というのはPureScriptがやっているやつで、PureScriptの場合で説明すると、PureScriptのソースファイルとは別に付随するJavaScriptファイルを用意して、JavaScriptファイルにはPureScriptから呼び出す関数定義を書く、という方式だ。

色々勘案した結果、とりあえずは「Luaの世界に対するAPIを用意する」という案で行くことにした。今のところこんなコードが動く：

val io_write = Lua.sub (Lua.global "io", Lua.fromString "write");
Lua.call io_write (vector [Lua.fromString "Hello Lua", Lua.fromString "!\n"]);

Luaの関数は複数の値を受け取り、複数の値を返す（多値）。そのためにLuaの関数は value vector -> value vector として見えるようにしている。ただLuaの多値は緩い（足りない値はnilで埋められるし余った値は捨てられる）のに対しSMLのvectorは長さについて厳格である。Luaの挙動を真似る adjust : int * value vector -> value vector みたいな関数を用意すると良いかもしれない。

SML/NJやMLton, Moscow MLなどはvectorに対するリテラル表記 #[1, 2, 3] やパターン #[pat1, pat2, pat3] を用意している。Lua FFIでvectorを活用していくのであればこれらの拡張を実装するという手もあるかもしれない。

ちなみに、method関数の型は中置記法として使えば

infix :::
val op ::: = Lua.method
val results = (obj ::: "foo") args (* Luaで言うところの obj:foo(args) *)

という風にLuaの表記を真似られるように選んだ。Luaの記法がコロン1つ : なのに対しSMLではコロン1つもコロン2つも予約済みなのが残念なところだが……。

さて、単にLua側のAPIを呼び出すだけではなく、SMLで書いた関数をLuaの世界に公開したい（Luaから利用できるモジュールをSMLで書きたい）となると少し話は変わってくる。Luaの慣習として、モジュールはグローバル変数を変更するようなことはせず、ファイル自体の返り値として関数等を含むテーブルを返すようになっている。

これを踏まえると、Luaへの値のエクスポートの方法としては

モジュールを表すテーブルを用意して逐次関数を登録していく
トップレベルの宣言に「Lua側にエクスポートする」ことを表すマーカーを書けるようにする
コンパイルの際に（ビルド用の記述ファイル等で）エクスポートするシンボルを指定できるようにする

などが考えられる。

セルフホストへの道のり

SMLの機能が整ってきたので、そろそろセルフホストへの道筋を夢想してもいいだろう。

言語機能面では、現在のLunarMLで使っているが未実装な機能としてはsignature, functorが大きい。これらはML-Yaccと各種Map/Set (BinaryMapFn, BinarySetFn)だけで使っているので、

signature, functorを真面目に実装する
ML-Yaccを辞めてパーサーを手書きし（できるのか？）、各種Map/Setはコードのコピペ（コード生成？）で頑張る

のいずれかの方法で解消できる。

オレオレ拡張案

Successor MLや他の処理系にある拡張を取り入れるのも良いが、独自の拡張を考えるのも楽しい。（これらの拡張は未実装である。悪しからず）

十六進浮動小数点数リテラル

浮動小数点数オタクとしてこれは欲しい。

SML標準では 0x1p23 というソース文字列は整数リテラル 0x1 と識別子 p23 という2つのトークンとして解釈される。この解釈を変えるというのは破壊的変更となる。

ところで、SMLのリテラルは、値の範囲によって型に制約がかかる。例えば 0w256 : Word8.word は不正な型付けだし、 "\256" は8ビット文字列型にはならない。

十六進浮動小数点数リテラルは二進浮動小数点数の値を正確に記述できるのがウリなので、「十六進浮動小数点数リテラルはその値を正確に表現できる型がつく」という制約を課すのは自然な発想だろう。つまり、 0x1.0000_01p0 : Real32.real や 0x1p1024 : Real64.real は不正な型付けである、とする。

Unicode文字列リテラル

SML ’97での新機能の一つが、文字列リテラル中での \uxxxx エスケープ（x は十六進）である。また、Successor MLでは \Uxxxxxxxx という記法が追加された。これらはUnicode文字を表すことを意図している。

が、しかし！SML標準の文字型 char は8ビットであり、文字列型 string は8ビット文字列である。SML Basisの仕様 https://smlfamily.github.io/Basis/char.html には「Char.maxOrd = 255」と書かれている。

（JVM / JavaScript / CLRにコンパイルする場合はこの規定は邪魔だし実際MLjやSML.NETは Char.maxOrd = 65535 としているようだが、今はその話は置いておいて）

では、Unicodeエスケープ \uxxxx はどうコンパイルされるのか？ "\u3042" : string という式はどうなるのか？

答えは「コンパイルが通らない」である。SMLのリテラルは値の範囲によって型に制約がかかると先程書いたが、\u0100 あるいは \256 以上の文字を含む文字列リテラルには string 型はつかない、というのが答えとなる。もっと幅の広い文字列型、例えば WideString.string を提供している処理系（例：MLton）であれば "\u3042" : WideString.string はコンパイルが通るだろう。

しかし、固定長文字コードは過ぎ去りし夢、現在のUnicodeは可変長エンコード、特にUTF-8が主流である。\uxxxx をUTF-8としてエンコードされた string 型へコンパイルしてはいけないのだろうか？

残念ながら、The Definitionでは \ddd も \uxxxx も「The single character with number …」として規定している。“character” の定義は場合により色々あるが、SMLの場合は char 型、Unicode的に言えばcode unitを指していると考えるのが妥当だろう。つまり、 "\u0080" と "\128" は同じ文字列を表すし、一つの \uxxxx からなる文字列リテラルを size で計った長さは必ず1となるべきなのだ。

（ちなみに、SML#は仕様（の筆者の解釈）に反し \uxxxx をUTF-8でエンコードするようだ。）

つまり、UTF-8でエンコードされた文字列リテラルをSMLで「いい感じに」書く方法は存在しない！

存在しないなら（拡張として）作ればいいじゃない、ということで、「可変長の文字列にエンコードされるエスケープシーケンス」 \u{xxxx} を実装したい。この記法はJavaScriptやLuaでお馴染みだろう。

条件コンパイル

現在のコンパイル先はLuaだが、Luaと一口に言っても色々ある。Lua 5.2以前とLua 5.3以降は整数型やビット演算で大きく変わった。LuaJITはLua 5.1ベースな代わりにC FFIが使える（それに付随して64ビット整数が使えたりする）。将来はJavaScript等の他の言語もサポートしたい。

そうすると、ターゲットごとに標準ライブラリーの一部が微妙に違う、ということになる。もちろん、ターゲットごとに標準ライブラリーとして異なるファイルを読み込む、という手もあるがファイルが増えるのは煩雑だ。

というわけで、何らかの条件コンパイルの手段が欲しい。

今後の目標

機能面ではかなり整ってきたと思うが、やることはまだまだある。

標準ライブラリーの充実
より自然なLuaコードを出力できるようにする
dead code eliminationの実装（標準ライブラリーを増やすにつれて出力が増える、というのは頂けないので）
その他最適化の実装
signature, functorの実装

AtCoderの問題の解答をSMLで書いて自作処理系でLuaへコンパイルして提出する、というのもそろそろできそうな気がする。

Spread the love

雑記帳

人生やっていき