久しぶりの進捗報告です。
前回の記事：
目次
進捗
末尾再帰のループへの変換
再帰関数が自分自身を末尾呼び出ししている場合、ループ（再帰的な二級継続）に変換するようにしました。
細かいことを言うと、Luaの場合は while や for ではなくgoto にコンパイルされます。将来的には出力の読みやすさを考えて while とかを使うようにした方がいいかもしれません。
今のところは相互再帰には対応していません。原理的には可能ですが、Luaをターゲットにする場合、生成される関数が大きくなりすぎるのを懸念しています（JVMをターゲットにする話でバイトコードのサイズ制限に引っかかるのを読んだことがあります）。関数のサイズがそれなりに小さい場合にループへの変換を有効化するという選択肢はあると思いますが、「最初のリリース」の後になるでしょう。
エスケープしない関数や継続がタプルを受け取る場合にunpackする
SMLは関数の引数の個数は原則として一つで、複数の値を受け渡ししたい場合はタプル（レコード）や関数のカリー化を使います。しかし、複数の値を受け渡しできる言語にコンパイルする場合は、可能ならターゲット言語ネイティブの複数引数関数を使った方が効率的と考えられます。
そこで、
- 引数のタプルが常に射影の形で使われる
- 関数の場合は、常に直接呼び出しされる（この制限はwrapperを作ることによって緩和可能だが、現在はそうしていない）
- 継続の場合は、関数呼び出しに使われない
場合に、複数引数を使うようにしました。
例えば
fun foo (x, y, z) = ...
が3引数関数にコンパイルされるのはイメージしやすいと思いますが、継続にも同様の最適化がかかるので
val (x, y, z) = if ... then (1, 2, 3) else (3, 4, 5)
が一時的なタプルを作らないようになる、という恩恵もあります。
パターンマッチの網羅性検査と冗長性検査
Standard MLコンパイラーは網羅的ではないパターンマッチや冗長なパターンマッチを検出した場合に警告を出すことが望ましいですが、これまでのLunarMLはそれらを実装していませんでした。
網羅的ではないパターンマッチは例えばこんなやつで、
fun f x = case x of
[] => 0
| [_] => 1
| [_,_] => 2
(* f [1,2,3] はどうなる？（実行時には Match 例外が飛ぶが、コンパイル時にも警告が出るのが望ましい） *)
冗長なパターンマッチはこんなやつです：
fun g x = case x of
None => false
| _ => true
(* None はコンストラクターとして定義されていないので、任意の値にマッチして None という変数を束縛する。するとその後の _ は冗長となる。 *)
SMLはコンストラクターと変数が（Haskellとは違い）字句的に区別されませんが、冗長なパターンマッチには「コンストラクター名のtypoを検出する」という役割もあります。
いずれも、堅牢なプログラムを書くためにはコンパイラーが検出して警告を出すことが望ましいです。
パターンマッチの実装について調査したことは
にまとめています。今回参考にしたのは
- MARANGET, L. (2007). Warnings for pattern matching. Journal of Functional Programming, 17(3), 387-421. doi:10.1017/S0956796807006223
です。
というわけで、網羅性と冗長性に関する警告を出すようにしました。
現在のLunarMLではパターンマッチはifの羅列にコンパイルされます。もっと洗練された方法でのコンパイルも検討したいです。
Successor MLのパターンマッチ拡張はまだ実装しなくていいかな、という感じです。参考文献は（OCamlを意識しているので）or patternは扱っていますが、Successor MLにはnested matchというヤバいやつがいます。
型のドキュメンテーション
Haskellの「一行丸々使って型宣言を書く」というスタイルは素晴らしいです。ドキュメンテーションの一環としての役割もあり、コードを読む人間が型推論する必要がなくなります。
map :: (a -> b) -> [a] -> [b] map f xs = ...
Standard MLの場合、型を（プログラマーに向かって）明示したかったら変数に付随させるか、
fun map (f : 'a -> 'b) (xs : 'a list) : 'b list = ...
structureのsignatureを書く際に明示するか、ということになります。
structure List : sig val map : ('a -> 'b) -> 'a list -> 'b list end = struct
fun map f xs = ...
end
ですが、どちらもHaskellほどの簡潔さはありません。文法を拡張して良ければ
fun map : ('a -> 'b) -> 'a list -> 'b list
| map f xs = ...
みたいな書き方を追加することはできますが、LunarML以外の処理系でコンパイルできなくなってしまうので、コードを書く側としては採用しづらいです。
あるいは、コメントで書けば人間には分かりやすくなるでしょう：
(* map : ('a -> 'b) -> 'a list -> 'b list *)
fun map f xs = ...
ですが、コメントは所詮コメントなので、コンパイラーには無視されます。型が間違っていてもエラーどころか警告も出ません。
では、LunarMLが検査してくれる特殊なコメントを書けば良いのでは？というわけで、特殊なコメント形式を用意しました。既存のコメントと被るといけないので、明示的に有効にした場合にのみパースされます。
(*! val map : ('a -> 'b) -> 'a list -> 'b list *)
fun map f xs = ...
MLBファイルに ann "valDescInComments warn" みたいなアノテーションを書いた時、 (*! から始まるコメントは文法の一部として解釈されます。このコメントは val 宣言か fun 宣言の直前にある必要があります。まあ val 宣言だと val map : ('a -> 'b) -> 'a list -> 'b list = ... という風に型を書けるので、もっぱら fun 宣言で使うことが多いでしょう。
あくまでコメントという建前なので、この型コメントは型推論には影響を及ぼしません。また、実際の型よりも特殊化された型を書くと警告もしくはエラーになります。
(*! val fact : IntInf.int -> IntInf.int *) fun fact 0 = 1 | fact n = n * fact (n - 1) (* 型推論には影響を及ぼさないので実際の型は int -> int となり、型の不整合で警告（もしくはエラー） *) (*! val idInt : int -> int *) fun idInt x = x (* 実際の型 'a -> 'a よりも特殊な型をコメントに書いているので警告（もしくはエラー） *)
LunarML自身のコードで使っていた型のコメントをこの形式に置き換えると、今まで不正確な型を書いていた部分が何箇所か発見されました。
sequenceNonUnit
SMLの逐次実行式 (a; b) において、 a の型はなんでもアリです。これは、間違って (List.app f; b) と書いても「List.app の引数が足りないこと」を意味するエラーは出ないということです。
これは良くないので、MLtonには逐次実行の際に型が unit であることを検査し、 unit でなかったら警告またはエラーを出すモードがあります。
これをLunarMLにも実装しました。
その他
Standard MLの処理系を実装していると、他の処理系のバグを見つけることもあります。
HaMLet Sのパターン { ... = x } の網羅性検査がバグっていたので報告しました。迅速に修正していただけました。
MLtonの Word.scan の実装が間違っていたので報告しました。迅速に修正していただけました。
Successor MLの val rec でnested matchが禁止されていないことに気づいて報告しました。コメントは頂けましたが実際の対応はまだです。まあ私自身GitHub Issueに迅速に対応するタイプではないので、他人に対して修正が遅いとか文句を言う気はありません。
初回リリースに向けて
バージョン番号がつく最初のリリース（v0.1）に向けて最低限必要だと考えていた機能は、パターンマッチの冗長性・網羅性検査です。これらを実装したことで、機能的には整ったことになります。
ですが、気持ち的には何か物足りない気がします。リリースのためのラインを改めて引き直すならどこにするべきでしょうか。（そんなことを言ってると永遠のアルファ版になってしまいますが）
一つの目安は、SML#界隈のSMLUnitに含まれるBasis Libraryのテストが通ることかもしれません：
現在のLunarMLのBasis Libraryには色々足りないものがあるので（Date とか）、このテストは動きません。
ライブラリー以外では、パターンマッチのコンパイル方法を変えたいです。
リリースのためにはパッケージングも大事です。make installが動くようにした方が良さそうです。MLtonをインストール済みでない人にも手軽に動かしてもらえるようにバイナリーの配布も望ましいですが、それは面倒なので、JavaScriptにコンパイルしたものを配布してNode.jsで動かしてもらうという手も考えられます。
他の気持ち的なところでは、
- 破壊的変更はなるべく避けたいので、破壊的変更をなるべくリリース前に済ませておく
- 他人に読ませても恥ずかしくないソースコードにする
などがあります。
今年の夏は忙しくなりそうなので、リリースは秋以降になるかもしれません。
初回リリースには含めないこと
実装したい機能を全て実装していたらいつまで経っても初回リリースができません。なので、いくつかの機能は後回しにします。そういう「後回しにする機能」をいくつか挙げてみます。LunarMLの進捗2022 に書いたものと被るかもしれません。
- インタープリターの実装：その場で（スクリプト的に）実行できるようにする
- REPLの実装
- JavaScriptバックエンドのWeb対応
- 現状はNode.js専用です。
- コンパイラーやREPLをWebで試せるようにする
- より強力な最適化の実装
- Successor MLの機能：パターンマッチ拡張とか
- バックエンドの追加：PHP, JVM, CLI, WebAssembly with GC, Scheme, Emacs Lisp
- 候補を挙げるだけならいくらでもできますが、個人的なモチベーションの高さで言えばPHPが比較的高いかと思っています。
まあ妄想するだけなら楽しいですね。