🔖

JavaScriptにコンパイルするCommon Lisp処理系

2023/12/10に公開

Common Lisp

tech

Lisp Advent Calendar 10日目の記事です。
言語実装アドベントカレンダーの方も枠が空いていたのでその記事でもあります。

以前、valtanというJavaScriptを出力するCommon Lisp処理系を作っていました。
https://github.com/cxxxr/valtan

作っていた動機としてはReactを使ったwebアプリケーションをCommon Lispで書きたかったからです。

デモ

React Tutorialにある三目並べをCommon Lispに移植したものをコンパイルし、動かしてるところです。

三目並べに対応するCommon Lispのコードはこれです。

ブートストラップ

Common LispからJavaScriptにコンパイルするコードは全てCommon Lispで書きました。
最初に使っていたCommon Lisp処理系はsbclでしたが、ある程度動くようになってきてからはvaltan自身でvaltanのコンパイラをコンパイルするようにしました。

パス

コンパイラは2フェーズ構成です。

一つ目のフェーズでCommon LispのコードをASTに変換(hirと呼ぶ, high level ir)、オプションとしてhirを最適化します
二つ目のフェーズでhirをJavaScriptに変換していました。

また、一つ目と二つ目の間でhirをlir(low level ir)に変換してフローグラフを作成しSSA最適化を行うという処理を挟んだこともありましたが、結局使いませんでした。

最適化

ブラウザを開いたタイミングで、Common Lispの標準の定義をJavaScriptに変換したものが全て読み込まれるため、コンパイラ性能がとても影響してきます。
最初の実装はとてつもなく効率が悪く、ブラウザを開いてindex.htmlの読み込みが終わり、画面に表示されるまで10秒以上かかっていました。
そのため、ある程度の最適化は必須でした。

一番効いていた部分としては、クロージャでした。
たとえば以下のような関数呼出の引数がifの場合、一対一でJavaScriptに変換するためにはifの文を式にする必要があります。

(f (if <test> <then> <else>))

f((function () { 
  if (<test>) { 
    return <then>
  } else {
    return <else>
  }
})())

これを三つ組に近い形式に変換するだけで数倍高速化されました。

var TMP1 = <test>;
var TMP2;
if (TMP1) {
  TMP2 = <then>;
} else {
  TMP2 = <else>;
}
f(TMP2);

goto

Common Lispの全てのループはマクロ展開され、最終的にtagbody/goを使ったgotoの形式に落し込まれますが、JavaScriptにはgotoが存在しません。
そのため、最初はgotoをステートマシンにしていました。
これも、パフォーマンス上の問題になっており、遅くなっていた要因の一つでした。
回避策として、特定の形式のgotoをパターンマッチして無限ループの形式に逆変換します。

例えば一番単純な例だと以下のようになります。

Common Lisp: (loop ...)
=> Common Lisp: (tagbody start ... (go start))
=> 内部表現: (:loop ... (:recur)) // clojureのloop/recurと同じ末尾再起形式
=> javascript: for (;;) { ... }

コードはこのあたりにあります。

この他にもいくつかのパターンを変換しています。

その他の最適化

定数畳み込み
- 変更されないローカル変数
- if, progn, let等
- (+ 1 2) などの組込み関数と定数の組合せ
関数のインライン展開

他に試そうとした事

AST -> Control flow graph -> SSA最適化
といったことを試しました。

ただ最終的にJavaScriptに変換するので、低級な表現からJavaScriptへの高級な表現に変換するための逆コンパイラも必要になり、面倒で頓挫しました(ここまでやったことでパフォーマンスが十分改善されたというのもあります)

開発環境

実際に使ってみようとすると、コンパイラを書く以外に開発環境を整える必要がありました。

エディタ

Lemというテキストエディタを作っているので、Lem用のvaltanの拡張機能を用意しました。

websocketでブラウザとエディタが通信をし、関数の再定義時に再コンパイルした結果をエディタからブラウザに送信し、ブラウザはその関数をevalして置き換え、それがreactコンポーネントなら即座に画面に反映される、という振舞いをします。

source map

ランタイムエラーがブラウザ上で出ると、エラー内容やスタックトレースがブラウザ上で見れますが、コンパイル後のJavaScriptのコードを見るのは苦痛です。
そのため、元のCommon Lispのコードとのマッピングをする必要があり、javascriptの出力とセットでsource mapを用意する必要があります。
ただ、Common Lispにはsource mapのライブラリが存在せず自分で用意しないといけません。
https://github.com/cxxxr/cl-source-map/

これはmozillaのsource-mapを参考にしました。

テスト

ANSI Common Lispの仕様を見たしているか、というテストが世の中に存在します。
valtanではsacla-testsというテストケースを使っています。

たとえばconsなら以下のようになっています。

これらの式を一つ一つread/evalをして、真偽値を確認します。
valtanでのevalはvaltan自身でコンパイルをし、実行するのでとても遅く、テストケースを全て走らせのに数十分ほどかかります。

おわりに

活発に開発してたのは2019年から2020年にかけてで、かなり長い間放置してしまっていますが、思い出しながらまとめました。
また再開したいですね。