「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年に先送りしたに過ぎません。

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

続きを読む →

Standard MLのIOとLunarMLのIO

プログラムにとって入出力は大事です。入出力機構がないと、計算の入力を受け取ることも、出力を出すこともできません。

Standard MLにも当然入出力に使う型と関数が定められています。例えば、print 関数は標準出力に文字列を出力し、flushします。TextIO や BinIO などのモジュールを使うと、ファイルの読み書きを行うこともできます。

LunarMLも、これらのモジュールを一部実装しています。しかし、今の実装はやっつけなので、もっとしっかりした（準拠度の高い）実装にしたいです。

Standard MLの入出力

Standard MLの入出力はいくつかのレイヤーに分かれています。

一番高いレイヤーが「手続き的入出力」すなわち IMPERATIVE_IO や TEXT_IO や BinIO です。これらは

  • 手続き的な入力
  • 手続き的な出力
  • ストリームのリダイレクト

などの機能を提供します。

手続き的入出力は、ストリーム入出力のラッパーと思えます。手続き的入出力のストリームの型はストリーム入出力の型を使うと

type instream = StreamIO.instream ref
type outstream = StreamIO.outstream ref

という風に理解できるでしょう。

ストリーム入出力は STREAM_IO で表されます。機能的には、

  • 関数的な（遅延リスト的な）入力
  • 手続き的な出力
  • バッファリング

を提供します。「関数的な入力」というのは、例えば「一文字読み取る」関数が

val input1 : instream -> (elem * instream) option

という型を持ち、「入力に与えられたストリーム」とは別の「一文字読み取った後のストリーム」を返すということです。同じストリームに input1 を複数回適用すると同じ結果が得られることが期待されます。

ストリーム入出力の下にあるのがプリミティブ入出力です。プリミティブ入出力 PRIM_IO は、システムコールを抽象化したものだと思えます。機能的には、

  • バッファリングなしの、手続的な入出力
  • ノンブロッキングIO（オプション）
  • ランダムアクセス（オプション）
  • OSのファイル記述子へのアクセス（オプション）
    • ファイル記述子に対しては、等価性比較、ハッシュ値の取得、大小比較ができることが想定されています。

があります。ただし、プリミティブ入出力はあくまでインターフェースを定めるものであり、特定のシステムコールに紐づいたものではありません。特定のシステムコールを呼び出すプリミティブ入出力の実装を提供するのは openIn とか stdIn とかを提供する側の役目です。

Standard MLにはこのほかに、OSのシステムコールに対応する型と関数が規定されています。

LunarMLの入出力

LunarMLは、スクリプト言語の提供する入出力機能をラップしてStandard MLの型と関数として見せたいです。スクリプト言語の提供する入出力機能とは、Luaで言えば io モジュール、Node.jsで言えば Readable/Writable などのストリームです。

スクリプト言語の提供する入出力機能をシステムコールとみなしてプリミティブ入出力として提供できれば良かったのですが、現実にはそううまくはいきません。スクリプト言語の提供する入出力機能にはバッファリングがあるのに対して、プリミティブ入出力にはバッファリングはありません。具体的には出力ストリームのflush操作がプリミティブ入出力にはないのです。書き込み操作の度にflushすればエミュレートできるかもしれませんが、ストリーム入出力のレイヤーでバッファリングを再実装するのかという問題もあります。

今考えているプランは、ストリーム入出力を単なるプリミティブ入出力のラッパーとするのではなく、内部実装として「プリミティブ入出力、あるいはスクリプト言語の提供する（バッファリングされた）ストリーム」の2択を持てるようにする案です。ストリームからプリミティブ入出力のインターフェースを得る場合は、ファイル記述子っぽいものを含めて、逆の操作（ストリーム入出力の構築）を行うときに「スクリプト言語の提供するストリーム」を復元できるようにします。ファイル記述子としては、スクリプト言語の提供するストリームと独自に割り当てる整数をハッシュテーブルで対応させて管理することにします。

まあ、言葉にするのは簡単ですが（これでも結構考えたのですが）、実装するのは面倒くさいです。少しずつやっていきます。

LunarMLの構文をイケイケにするために

Standard MLとLunarMLの関係について、前にこういう記事を書きました。

Standard MLに対する拡張のアイディア

この時は割と互換性重視でしたが、しかし、クソリプおじさんからの批判に耐えるにはもう少し抜本的な改革が必要そうです。非互換性を厭わずに構文を変えるならどういう構文にしたら良いでしょうか。

（まあクソリプおじさんが前の記事を読んでいたかは定かではないのですが。人が百も承知なことに対して上から目線でご高説を垂れるからクソリプなのです。釈迦に説法という言葉もありますね。）

続きを読む →

LunarML: LuaやJavaScriptを出力するStandard MLコンパイラー

本日、私がこの数年開発しているStandard MLコンパイラー「LunarML」の最初のバージョン（v0.1.0）をリリースしました。というわけで、この記事ではLunarMLを紹介します。

はじめに

型のないプログラミング言語で大きなソフトウェアを作るのは辛いです。しかし、動作環境の都合で型のない言語を使わざるを得ない状況が世の中にはあります。この状況を改善できるのが、静的型のある言語で書かれたプログラムを型のない言語のコードへ変換するコンパイラーです。トランスパイラーと呼ばれることもあります。

WebではJavaScriptしか使えない状況が長く続いたため、JavaScriptへコンパイルする処理系は多数登場しました。しかし、それ以外のスクリプト言語、例えばLuaを出力するコンパイラーはまだ少ないように思います。そこで、静的型のある言語からLuaへ変換できるコンパイラーを新しく作ることにしました。

入力とする言語については、新しく作るのではなく、既存の言語を利用することにしました。私はML系の言語が好きなのでML系の言語をいくつか検討した結果、Standard MLを選びました。Standard MLは以下の特徴を持った言語です：

  • 強力な型推論
  • 正格評価
  • カプセル化とコードの再利用を可能にするモジュールシステム
  • 標準（The Definition）と、それに準拠した複数の処理系

機能

LunarMLはSML ’97の（モジュールシステムを含む）全ての機能と、Successor MLのいくつかの機能を実装しています。独自の拡張機能もいくつか実装しています。

標準ライブラリーはまだ不完全ですが、LunarML自身をコンパイルできる程度には揃っています。

複数ファイルからなるプロジェクトのために、MLtonやMLKitと互換性のあるML Basis systemを実装しています。

もちろん、LuaやJavaScriptの世界とのやりとりもできます。

いくつかのバックエンドでは、限定継続も利用できます。限定継続は非同期プログラミングに有用です。

ビルドとインストール

LunarMLは以下のGitHubリポジトリーで開発されています：

ビルドするにはMLtonとLuaが必要です。

$ git clone https://github.com/minoki/LunarML.git
$ cd LunarML
$ make
$ bin/lunarml compile example/hello.sml
$ lua example/hello.lua
Hello world!

インストールには make install を使います。デフォルトでは /usr/local にインストールされますが、PREFIX 変数を指定してインストール先を変更することもできます。

$ make install PREFIX=/opt/lunarml
$ export PATH=/opt/lunarml/bin:$PATH
$ lunarml --help

自分でビルドする代わりに、コンパイル済みスクリプト、もしくはDockerイメージを利用することもできます。コンパイル済みスクリプトはリリースされたtarballに含まれます。

コンパイル済みスクリプトをNode.jsで実行する場合の手順は次のようになります。

$ curl -LO https://github.com/minoki/LunarML/releases/download/v0.1.0/lunarml-0.1.0.tar.gz
$ tar xf lunarml-0.1.0.tar.gz
$ cd lunarml-0.1.0
$ make install-precompiled-node PREFIX=/opt/lunarml
$ export PATH=/opt/lunarml/bin:$PATH
$ lunarml compile example/hello.sml
$ lua example/hello.lua
Hello world!

スクリプトにコンパイルしたLunarMLはとても遅いので気をつけてください。実用の際はMLtonでネイティブコンパイルしたものを利用することをお勧めします。

Dockerイメージを利用する場合は次の手順になります。

$ docker pull ghcr.io/minoki/lunarml:latest
$ docker run --rm --platform linux/amd64 -v "$(pwd)":/work -w /work ghcr.io/minoki/lunarml:latest lunarml compile example/hello.sml
$ lua example/hello.lua
Hello world!

簡単なコードをコンパイルしてみる

Standard MLのHello worldは次のようになります：

print "Hello world!\n";

Luaにコンパイルしてみましょう。実行にはLua 5.3またはLua 5.4が必要です。

$ lunarml compile hello.sml
$ lua hello.lua
Hello world!

JavaScriptにコンパイルして、Node.jsで動かすこともできます：

$ lunarml compile --nodejs-cps hello.sml
$ node hello.mjs
Hello world!

フィボナッチ数を計算する（遅い）コードは以下のようになります：

fun fib 0 = 0
  | fib 1 = 1
  | fib n = fib (n - 1) + fib (n - 2);
print ("fib 10 = " ^ Int.toString (fib 10) ^ "\n");
$ lunarml compile --lua fib10.sml
$ lua fib10.lua
fib 10 = 55
$ lunarml compile --nodejs fib10.sml
$ node fib10.mjs
fib 10 = 55

標準で多倍長整数も使えます。Luaがターゲットの場合は自前の実装を、JavaScriptがターゲットの場合は BigInt を使います。

fun fact 0 : IntInf.int = 1
  | fact n = n * fact (n - 1);
print ("50! = " ^ IntInf.toString (fact 50) ^ "\n");
$ lunarml compile --lua fact50.sml
$ lua fact50.lua
50! = 30414093201713378043612608166064768844377641568960512000000000000
$ lunarml compile --nodejs fact50.sml
$ node fact50.mjs
50! = 30414093201713378043612608166064768844377641568960512000000000000

HaMLetをコンパイルしてみる

HaMLetという、Standard MLのリファレンス実装を謳う処理系があります。これをLunarMLで動かしてみましょう。

$ git clone https://github.com/rossberg/hamlet.git
$ cd hamlet/
$ make hamlet.mlb SYSTEM=mlton
$ lunarml compile --lua-continuations hamlet.mlb
$ lua hamlet.lua
HaMLet 2.0.0 - To Be Or Not To Be Standard ML
[loading standard basis library]
- 1 + 1;
val it = 2 : int
- OS.Process.exit OS.Process.success : unit;

もちろん、JavaScriptへコンパイルすることもできます。

$ lunarml compile --nodejs-cps hamlet.mlb
$ node hamlet.mjs
HaMLet 2.0.0 - To Be Or Not To Be Standard ML
[loading standard basis library]
- "Hello " ^ "world!"; 
val it = "Hello world!" : string
- OS.Process.exit OS.Process.success : unit;

Luaコードの生成

LunarMLはデフォルトではLua 5.3/5.4向けのコードを出力します。--lua オプションで明示的に指定することもできます。

--luajit オプションにより、LuaJIT向けコードを出力することもできます。

Luaの機能はLuaモジュールのAPIを介して呼び出すことができます。現状はあまり使いやすいものではないので、将来的にはもっと便利な方法を導入するかもしれません。

--lib オプションにより、Luaモジュールを生成することもできます。export という名前の変数またはモジュールで定義した内容がエクスポートされます。

出力されたコードは人間可読というわけではありません。人間可読なコードを生成するのは目標には入っていませんが、それでもデバッグの観点からもう少し読みやすいコードを生成したいです。

JavaScriptコードの生成

LunarMLはJavaScriptコードを出力することもできます。現状は実行にNode.jsが必要で、ブラウザーでは動きません。--nodejs または --nodejs-cps オプションを利用します。

Node.jsのAPIは多くが非同期的です。一方、Standard MLの入出力関数は同期的です。この違いを吸収するため、LunarMLは --nodejs-cps オプションが利用された場合はプログラムに対してCPS変換と呼ばれる処理を行っています。--nodejs オプションが指定された場合はCPS変換を行わず、代わりに入出力関数を制限しています。

JavaScriptの機能はJavaScriptモジュールのAPIを介して呼び出すことができます。これも、将来的にはもっと便利な方法を導入するかもしれません。

--lib オプションにより、ESモジュールを生成することもできます。export という名前の変数またはモジュールで定義した内容がエクスポートされます。

LunarMLの標準の文字列型 string はJavaScriptの世界では Uint8Array を使って表現されます。JavaScriptの文字列はLunarMLでは WideString.string 型として利用できます。

今後の計画

LunarMLはまだまだ未完成で、今後実装したい機能はたくさんあります。いくつか挙げます。

  • 標準ライブラリーの充実
  • Successor MLの機能をより多く実装する
  • REPLとインタープリター
  • Online compiler
  • バックエンドの追加
    • ブラウザー向けJavaScript
    • PHP
    • WebAssembly with GC
  • パッケージ管理システム

最後に、GitHubのリポジトリにスターを頂けると嬉しいです：