Standard ML」タグアーカイブ

LunarMLの近況/中間言語に型をつける

私が作っているStandard MLコンパイラー、LunarMLの近況報告記事です。LunarMLに関する直近の記事は

でした。

400スター

GitHubスター数が400に到達しました。ありがとうございます(執筆時点では402に増えています)。まだスターをつけていない方は https://github.com/minoki/LunarML でスターをつけることができます。

スターが350に到達したのは2024年10月、300に到達したのは2024年5月のことだったようです。

(本プロジェクト限定というわけではありませんが)GitHub Sponsorsにも触れておくと、現在は @toyboot4e さんと @kevin-kmetz さんにスポンサーしていただいています。ありがとうございます。

https://github.com/sponsors/minoki

中間言語に型をつけたい:型をつける動機付け

JavaScript連携の記事で、

JavaScriptの Promisethen はコールバックが Promise(正確にはThenable)を返したら更にそれを待ち受ける挙動をします。モナドのbindみたいな感じです。この仕様があると ('a promise) promise みたいな型をいい感じに扱えないので、Standard MLの世界のコードが Promise の中身として Promise を返そうとした場合はラッパーを噛ませるようにします。

と書きました。「Promise の中身として Promise (より正確には Thenable)を返そうとした場合はラッパーを噛ませる」の部分をコードで説明すると、次のような関数 wrapThenable, unwrapThenable の呼び出しを適宜噛ませる形になります:

function ThenableWrapper(x) {
    this.payload = x;
}
function wrapThenable(x) {
    if (typeof x === "object" && typeof x.then !== "undefined") {
        return new ThenableWrapper(x);
    } else {
        return x;
    }
}
function unwrapThenable(x) {
    if (x instanceof ThenableWrapper) {
        return x.payload;
    } else {
        return x;
    }
}

JavaScriptの通常の Promise との相互運用を可能にするため、値が Thenable ではない場合は元の値を活用します。

しかし、Promise の操作をするたびに必ず wrapThenable の呼び出しを挟むというのはダサいです。値の型が stringint など、明らかに Thenable ではないことがわかっている場合は、呼び出しを省略したいです。そのためには、最適化が進んだ段階でもコードの型情報を保持しておくことが必要です(インライン化によって型が判明する状況を考慮する)。現状のLunarMLでは最適化はCPS中間言語に対して行っているので、CPS中間言語を型付きにすることが必要です。

型情報の別の用例を挙げます。次のコードを考えます:

(* val foo : unit -> unit
   val bar : unit -> string *)
val x : unit = foo ()
val _ = bar x

xunit 型の変数で、情報を保持していません。こんなコードを書く人はいないと思われるかもしれませんが、最適化の結果としてこういうコードが現れることは十分にあり得ます。

この場合、ソース中の x という変数を出力コードに反映させるのは無駄です。特に、Luaではローカル変数は貴重な資源なので、節約したいです。そこで、「型が unit の変数の使用は値 () で置き換える」という変換が考えられます。

そんな感じで、中間言語、特にCPS中間言語に型がついていると便利そうです。

中間言語に型をつけたい:作業

LunarMLの中間言語は

  • ソース(Standard ML)→(いくつかの前処理と型検査)
  • →型付き中間言語→(モジュールの脱糖、オーバーロードとequality typeの脱糖)
  • →System Fωライクな中間言語→(パターンマッチの脱糖)
  • →System Fωライクな中間言語→(CPS変換)
  • →CPS中間言語→(各種最適化)
  • →CPS中間言語→(ネストされた式の回復)
  • →ネストした式のある中間言語→(変換)
  • →LuaやJavaScriptのコード→(変換)
  • →最終的なLuaやJavaScriptのコード

という流れになっています。

従来は、System Fωライクな中間言語までは型がついていて、CPS中間言語には型がないという状況でした。3月ごろに、System Fωライクな中間言語の型検査器を実装しました。

今回、CPS中間言語を型付きにして、型検査器も実装しました。

型付きのCPS変換はしっくりくる先行研究が少なくて、なかなか難航しました。LunarMLの型付きCPSメモにいくつかメモりましたが。

最終的には、「型抽象と型適用は、通常の関数と関数適用と同様に扱う(ただしフラグをつけて区別できるようにする)」「最適化をある程度かけた段階で、多相型を消去する。完全に型を消去するのではなく、漸進的型付けのAnyのような感じで置き換える。その後再び最適化をかける」という形にしました。

最初は中間言語に対する型検査器はなくても良いかなと思っていましたが、型に関するバグがあったときに型検査器がないとエスパーでデバッグする羽目になり、しんどかったです。なので、結局型検査器を実装しました。実装したらしたで無限にバグが見つかってしんどいことになりましたが。

型周りのバグの発見には、過去に書いたテストが役に立ちました。テストは資産です。

悪いニュースとして、CPS中間言語に型をつけたことで、コンパイルが遅くなったり、メモリ使用量が増大したりしています。中間言語の型検査をやめれば時間の増加は軽減されると思いますが、テスト時はしっかり検査したいので、テストの所要時間は減らせなさそうです。

ML Family Workshop

今年のICFPはシンガポールでの開催で、それと併設で10月16日にML Family Workshopというのが開催されます。学会誌なんかは出ない、インフォーマルな集まりのようです。

このML Family WorkshopにLunarMLの話を応募したところ、通りました。というわけで、行ってきます。

このところLunarMLの作業を頑張っているのは、ML Family Workshopで話せる内容を少しでも増やしたいという気持ちからです。ですがCPS中間言語の型付けに時間を使いすぎた感があるので、そろそろ資料作成と発表練習をしないといけません。

バージョン0.3.0

ML Family Workshopの前になるか後になるかは不明ですが、そろそろ新しいバージョンとしてリリースしても良いかもしれないと思っています。ユーザー視点ではJavaScript周り(Promise連携とか)が新機能になるかと思います。GitHub Actionsでビルドする仕組みを整えたので、MLtonでビルドしたバイナリーも配布できると思います。

良いコンパイラーは親切なエラーメッセージを出さなければならない:LunarMLの場合

プログラミング言語の静的解析の良い点として、一回の解析で複数の誤りを検出できる(場合がある)点があります。実行時エラーしか出ない言語だったら、一回の実行で一個のエラーに遭遇して、修正して、またエラーに遭遇して、ということを繰り返さなければなりません。

言い換えると、遭遇した最初の誤りでコンパイルが停止してしまうようなコンパイラーは、いくら静的な型システムを備えていても、動的言語並みの貧弱な開発体験しか得られないということです。コンパイルの手間がかかる分むしろマイナスです。

コンパイラーではなく言語サーバーでも同じことで、ソースコードの最初の誤りで解析が停止してしまう言語サーバーからは貧弱な開発体験しか得られないでしょう。

検出できるエラーの個数だけではなく、エラーメッセージの親切さも、結構開発体験を左右するのではないかと思います。よくある誤りに対して的確なエラーメッセージを出すことができれば、ユーザーがエラーの原因で悩む手間が省けます。

一つの言語仕様に対して複数のコンパイラーが存在する状況で、エラーメッセージの品質はコンパイラー間での差別化の要素になり得ます。この記事では、Standard MLコードに対して良いエラーメッセージを出す工夫について考えてみます。

続きを読む

LunarMLとJavaScriptの連携について

久しぶりにLunarMLの話題です。LunarMLは、私が作っているStandard MLコンパイラーです。

最近は、JavaScriptとの連携に関する機能を追加しています。Webで使えるようにするのと、Promise/async/await周りの統合をいい感じにすることを目標にしています。

続きを読む

never型があると便利か(言語処理系実装者の観点から)

TypeScriptをはじめとするいくつかのプログラミング言語には、never型という型がある。この型は典型的には「制御を返さない関数」の返り値として使われる:

function f(x: string): never {
    console.error(x);
    throw new Error();
}

never型は型システム的には「値を持たない型」「任意の型の部分型」として特徴づけられる。

他のプログラミング言語、例えば私が作っているLunarMLにもnever型があると便利だろうか?

続きを読む

LunarMLと文字列フォーマット

LunarMLをLuaの代替として使う際、Luaの機能を自然に使えると良さそうです。例えば、文字列フォーマット関数 string.format を呼び出す際には現状では引数の型キャストが必要ですが、フォーマット文字列にいい感じの型をつければキャストが不要になるのではないでしょうか。

ML系言語の仲間であるOCamlには、フォーマット文字列が期待される文脈で特別な型付けを行う機能があります。LunarMLでも似たようなことをするといいのではないか、というわけで検討します(検討するだけならタダなので)。

続きを読む

LunarML/Standard MLのブートストラップ問題

LunarMLを含む多くのStandard MLコンパイラーはStandard ML自身で記述されています。すでに動くStandard ML処理系があればSMLで書かれたコンパイラーを動かせますが、Standard ML処理系のない新しいプラットフォームでStandard MLコンパイラーを動かしたい場合はどうすればいいでしょうか?

続きを読む

プログラミングではたまにエスパー力が必要になることがある

プログラミングをやっていると、たまにエスパー力が必要になることがあります。つまり、不可解な現象に遭遇し、少ない手がかりで問題を解決しなければならない状況です。

私はLunarMLという言語処理系を趣味で作っているのですが、今回はそれの開発中に遭遇した出来事を取り上げます。

続きを読む

西暦2262年問題に対処するべきか

西暦2038年問題はみなさんご存知ですよね。2038年1月19日午前3時14分7秒(UTC)を過ぎると 世界中のUNIXがばくはつする問題 time_t が符号付き32ビットなプログラムで現在時刻を正しく扱えなくなる問題です。

C言語の time_t は典型的にはUnix epoch(UTCで1970年1月1日午前0時)からの経過時間(うるう秒は考慮しない)を秒単位で保持しており、それが\(2^{31}-1\)に到達するのが2038年1月19日午前3時14分7秒(UTC)なわけですね。

2038年は割と近い将来なので、モダンなC処理系では time_t を64ビット整数にするなどの対応を行なって2038年問題を乗り切ろうとしています。

それでも、時刻を固定長整数で表現する限り、いつか限界が来ます。「time_t を64ビット整数にする」という対応は、問題を西暦2038年から西暦292277026596年に先送りしたに過ぎません。

そして、時刻の表現を「秒単位」ではなくもっと細かい単位にするとこの限界はもっと早くやってきます。この記事では、時刻の表現をどういう刻みで何ビットにすると限界がいつになるのかを検討してみます。

続きを読む