LunarMLの進捗と妄想

LunarML進捗：signatureの実装に向けての続き。6月中旬以降の進捗を報告する。

前回以降、signatureの実装を進めたのと、インライン化の実装を進めた。また、拡張機能としてvector expressionとvector patternを実装した。

7月、8月は色々あってそれほど作業が進まなかった。

前回書いたSML ’97の主要な機能のうち未実装だった4つの状況は、

withtype: 実装済み
- signature中のwithtype (Successor ML)にも対応
abstype: 未実装
signature: 実装中
functor: 未実装

となった。

signatureの進捗

signatureのうち、transparent constraintは実装した。opaque constraintはまだである。

signature関連のderived formのうち、sharing structureは未実装となっている。

opaque constraintやfunctor, あるいはpackaged modulesをF-ing modulesに則って実装するには、型をpackする順番が重要になるだろう。SMLでは

sig
  eqtype t
  eqtype u
  type v = t
end

と

sig
  eqtype v
  eqtype u
  type t = v
end

はsignatureとして同一視される。一方はtがtype aliasで、もう一方はそうではないにも関わらず。なので、これらをpack, unpackする際に2つの型（t=v, u）の順番を一貫させなければならない。

インライン化とval recと強連結成分分解

SML Basisには

infix 3 o
infix 0 before
fun (f o g) x = f (g x) (* ('b -> 'c) * ('a -> 'b) -> 'a -> 'c *)
fun x before () = x (* 'a * unit -> 'a *)
fun ignore _ = () (* : 'a -> unit *)

という定義がある。これらの呼び出しをいちいち関数呼び出しにコンパイルするのはいかにもアホらしい。コンパイルの際にはインライン化して関数呼び出しを除去したい。

なので、インライン化の実装を進めている。ただ、再帰関数は素直にインライン化するとえらいこと（コンパイル時の無限ループ）になりそうである。なので、val recで定義される再帰関数はインライン化の対象から外す。

しかし、そうすると「val recで定義したけど実は再帰呼び出ししていない」という関数のインライン化が行われなくなってしまう。また、実の所funはval recに脱糖されるので、さっき書いた o, before, ignore はいずれもインライン化の対象から外れてしまう。

それでは困るので、val rec ... and ... 宣言はコンパイルの途中でなるべく細かい単位に分割する＆再帰呼び出しをしていない場合はrecではないvalに変換するようにした。この際に使うのが強連結成分分解 (Strongly Connected Component) である。手元にあった競プロの本（いわゆる蟻本）を見ながら実装してみた。競プロはコンパイラー作成の役に立つ。

グラフ理論っぽいアルゴリズムといえば、datatypeのequalityを判定する際にもグラフ理論っぽいアルゴリズムを使った（単純な走査ではあったが）。

nullableとMONO_OPTION

nullのある言語ではSMLで言うところの t option を t | null （nullとのunion型あるいはnullable）という風に表現することがある。LunarMLが対象としているLuaにもnilというnullっぽい値があるので、これを利用できると良い。

ただ、一般の型についてのnullableはoption型とは性質が違う。option型は多段にすることができるが、nullableを多段にすると潰れてしまう：(t | null) | null = t | null

RustやMLtonのように全ての多相をコンパイル時に単相化するのであれば t がnullになり得ない型の場合のみnullableを活用することができるが、LunarMLではその予定はない。

そこで考えられるのが、nullになり得ないことが既知の型についてのnullableを個別に提供することだ。具体的には、次のsignatureを持つstructureを個々のプリミティブ型について提供する：

signature MONO_OPTION = sig
  type option (* ≈ SOME of elem | NONE *)
  type elem
  val some : elem -> option
  val none : option
  val getOpt : option * elem -> elem
  val isSome : option -> bool
  val valOf : option -> elem (* may raise Option.Option *)
  val filter : (elem -> bool) -> elem -> option
  val join : option Option.option -> option
  val app : (elem -> unit) -> option -> unit
  val map : (elem -> elem) -> option -> option (* monomorphic *)
  val mapPartial : (elem -> option) -> option -> option (* monomorphic *)
  val compose : (elem -> elem) * (elem -> option) -> elem -> option (* monomorphic *)
  val composePartial : (elem -> option) -> (elem -> option) -> elem -> option (* monomorphic *)
  val toOption : option -> elem Option.option
  val fromOption : elem Option.option -> option
end
structure IntOption :> MONO_OPTION where type elem = int
structure WordOption :> MONO_OPTION where type elem = word
structure RealOption :> MONO_OPTION where type elem = real
structure StringOption :> MONO_OPTION where type elem = string

このインターフェースでは、例えば StringOption.option 型が string | null に相当する。実際の実装ではnullableを使っても良いし、通常のoption型のようにボックス化しても良い。

まあ、このインターフェースではmapの際に要素の型を変えるようなことはできない（柔軟性が低い）という欠点があるし、そこまでしてnullable（に期待される効率の良い表現）を利用したいかという問題はあるだろう。

中間言語に対するデバッグ：pretty printとか型検査

インライン化やval recの分解等の最適化はSystem Fωライクな中間言語に対して行っている。そのため、最適化が正しく行われていることを確認するために中間言語をpretty printしたい。また、型がついているというメリットを活かして中間言語に対する型検査もデバッグの上で有益だろう。しかし実装が面倒くさい。

Lua以外のターゲット言語の検討

せっかくスクリプト言語を出力するコンパイラーを作ってLuaしか吐けません、というのは勿体無いので、いずれはLua以外の言語も出力できるようにしたい。なので色々検討している。検討するだけ（実装を伴わない）なら楽しいものである。

LunarMLの目標は「型なしスクリプト言語しか使えない環境に静的型とその他もろもろML系言語の恩恵をもたらす」なので、「その言語しか使えない状況」があるというのがターゲット言語の選定条件である。SMLで書いた単体のプログラムを動かしたいなら他のSML処理系なりLunarMLのLuaバックエンドを使えば良いだけなので…。

こういう検討というか妄想はかなり前の段階からやっているので、以前の記事と被っている内容もあるかもしれない。

JavaScript

Webで普遍的に使えるプログラミング言語はJavaScriptしか使えない状況が長く続いた（最近はWebAssemblyが勃興してきているけど）ので、「JavaScriptしか使えない状況がある」という条件は満たしている。

あと、アプリケーション埋め込み用の言語としてもJavaScriptは結構人気だと思う（Luaと並んでツートップ？）。

SMLのコンパイルターゲットとしてのJavaScriptの問題は、

末尾呼び出し最適化が事実上期待できない（ので自前で末尾再帰のループへの変換なりトランポリンなりしなければならない）
- 一応規格（ECMAScript）では規定されているがJavaScriptCoreしか実装していないので事実上使えない
SMLのstringは8ビット単位と規定されているのに対しJavaScriptの文字列は16ビット単位である
- SML側に寄せてUint8Arrayでstringを実装するか、SMLの規定を破ってJavaScriptの文字列をstringとするか
- 昔Haxeを触ったときに文字列の扱いがターゲット依存なことで苦しめられたので、自分の処理系では文字列をなるべくターゲット依存にはしたくない、あるいは文字列型の違いを吸収する上手い仕組みを提供したい

である。

もちろんWebだけではなくNode.jsターゲットも考慮する。Denoも面白そう。

あとはECMAScript 2015よりも前のバージョン（i.e. ES3しか使えないWSH/JScript）を考慮するかどうかも問題である。WebならES2015どころかES2020（BigIntやglobalThisがある）さえ期待できそうだが、化石は化石のままである。（しかし「OSに標準で付属するスクリプト言語処理系」はターゲットとして美味しい…）

Scheme

Schemeは末尾呼び出し最適化があるしコンパイルターゲットとしてはそんなに苦労しなさそうである。

しかし検討すべき事柄がないわけではない：

Schemeでレコードのようなデータ構造を表現するにはvectorを使う（よね？）。これはレコード型ごとにラベルを辞書順でソートして整数のインデックスを割り振れば良いだけなのだが、仮にレコード多相を実装する場合はラベル→インデックスの表を別途用意して隠しパラメーターで渡すような工作が必要となる。
Schemeの文字列は概ねUnicode（R7RS smallを確認した感じ）で、真っ当な処理系なら21ビット単位の列として扱える（R7RS smallではUnicodeのサブセット、Latin-1やBMPのみに対応する処理系も認められている。これは不安要素）。ので、SMLの8ビット文字列をどうするかという問題がある。SML側の規定を破ってSchemeの文字列を使うか、SMLの規定に忠実にbytevectorを使うか…。
細かいことだけどSMLのlistをLispの（consで表される）listにマップできるといいよね。単方向リスト同士仲良くしましょう。

そもそも問題となるのは、Schemeでなければならない状況（Schemeインタープリターを埋め込んだ環境）がそんなにあるかという問題だ。筆者がすぐに思いつくのはGNU GuileとGIMP (Script-Fu)くらいである。

Emacs Lisp

Emacsのスクリプト言語といえばEmacs Lispである。Emacsパッケージを書く際にSMLが使えると嬉しいのでは！？（ほんまか）（妄想するだけならタダ）

Emacs Lispについて筆者は「-*- lexical-binding:t -*- と書いておくと変数のスコープがレキシカルになる」くらいしか調べていない。

https://www.gnu.org/software/emacs/manual/html_node/elisp/Variable-Scoping.html

Python

Pythonももちろんコンパイルターゲットになりうるだろう。

しかし、Pythonにコンパイルできて嬉しいのか？という問題はある。Pythonを埋め込んだアプリケーションってそんなに知らない。Pythonの強みといえば資産だが、それにアクセスするには結局Python流の文法要素（クラスとかメソッド呼び出しとかキーワード引数とか配列のインデックスとか）を持っていなければならないのではないか。

ちなみにPython 3の文字列はUnicodeコードポイント（21ビット、サロゲート許容）の列である。なので、SMLの文字列をどのようにマッピングするかという問題がある。strかbytesか。

PHP

PHPなら効率的に動かせるレンタルサーバーとか、WordPressプラグインとか、PHPが必要な場面はそこそこありそうである。

PHPの文字列は8ビット列らしいので、SMLの文字列は素直にマッピングできそうである。

手続き的な中間言語

SMLは式指向なのに対して、Luaは文指向である。Luaは式の中で条件分岐することができない（値がfalsyでないことを仮定すればand-orを使ったトリックがあるが）し、評価順（SMLは左から右と定まっているのに対しLuaでは未規定・処理系依存である）を強制するには一つの式を複数の文にコンパイルする必要がある。

この際、現在のコード生成器ではSystem Fωライクな中間言語から直接Luaコード（厳密にはインデントの深さを考慮して、擬似的なトークン列）を出力している。ちなみに、うまくやろうとすると何故かコード生成器の一部をCPS変換する必要性が発生した。

しかし、Luaあるいは手続き型言語特有の変換（Luaのローカル変数の数の制限をかいくぐったり、よりLuaらしいコードを出力するための変換をしたり）や最適化を実装することを考えると、System FωとLuaの間に手続き的な中間言語を一段挟むべきかもしれない。

その中間言語はLuaにべったり寄せるべきか、それとも他のターゲット言語を考慮してある程度普遍性があるものにするべきか、悩んでいる。

パーサーコンビネーターの利用

現在のLunarMLでは字句解析器は手書き、パーサーはML-Yaccを使っている。ML-Yaccを使うとmlyacc-libへの依存が発生する。LunarMLがセルフホストできるようにするためには、ユーザーに別途mlyacc-libを用意してもらうか、mlyacc-libを（MLtonがやっているように）添付する必要がある。

しかしそれは面倒なので、なるべくmlyacc-libには依存したくない。これはすなわちML-Yaccを使わずにパーサーを書く、ということである。

ML-Yaccじゃないパーサージェネレーターを用意したり、完全に手書きのパーサーを書くのは大変そうなので、パーサーコンビネーターの利用を考えている。SMLで書かれた既存のパーサーコンビネーターはいくつかあるようだが、LunarMLのニーズに合致するかはわからないので、勉強も兼ねて自分で一つ作ってみたい。

不安要素としては、エラー回復やエラーメッセージがどうなるか、パース速度がどうなるか、などがある。

いずれにせよ、パーサーコンビネーターではfunctorを使うことになるだろうし、セルフホストを真面目に考えるのはfunctorを実装した後になるだろう。

逐次的コンパイル（REPLとか）

現在のLunarMLでは、プログラム全体を一括でコンパイルする設計になっている。これではプログラムが逐次的に与えられる状況、例えばREPLに対応できない。

REPLは他のSML処理系（SML/NJやSML#）に任せればいいじゃないか、という考えもあるかもしれないが、SML処理系同士の互換性というのは細かいところまで見るとそこまで高くないし、自分の処理系と互換性のあるREPLは自分で用意するしかない。

しかしそうするとコンパイラーの構造が複雑になりそうで、どうしたものか。

あと、REPLを提供するならreadlineみたいなやつと連携させたいが、どうしたものか。

雑記帳

人生やっていき

LunarMLの進捗と妄想

signatureの進捗

インライン化とval recと強連結成分分解

nullableとMONO_OPTION

中間言語に対するデバッグ：pretty printとか型検査

Lua以外のターゲット言語の検討

JavaScript

Scheme

Emacs Lisp

Python

PHP

手続き的な中間言語

パーサーコンビネーターの利用

逐次的コンパイル（REPLとか）

コメントを残すコメントをキャンセル

signatureの進捗

インライン化とval recと強連結成分分解

nullableとMONO_OPTION

中間言語に対するデバッグ：pretty printとか型検査

Lua以外のターゲット言語の検討

JavaScript

Scheme

Emacs Lisp

Python

PHP

手続き的な中間言語

パーサーコンビネーターの利用

逐次的コンパイル（REPLとか）

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル