すごい勢いでSchemeコンパイラを作りたい

yunicomp

nmoshは、単体でR6RSスクリプトを展開(expand)するためのライブラリを備えている。ここでいうexpandとはマクロの処理のことで、これを使うことでnmoshのsyntax-caseとかsyntax-rulesの実装を簡単に流用できる。
世間的には、Schemeサブセットのコンパイラは比較的簡単に作ることが出来るとされている。

↑で説明しているのはCPS変換とクロージャ変換だが、Schemeを作るのに必要な残りの部分はMoshのものをそのまま流用することができる(はず - 例外のハンドリングのために、かなりトリッキーな手法が必要になる)ので、これらを流用すれば、フルに機能するR6RS Schemeも簡単に実装できるように思える。
...と書くと思いつきのように見えるが、要するに、MoshのVMを使わずにMoshのライブラリ構築を行えるようにすることは意味がある。多分、一切の最適化を行わなくても、Moshで実行する場合より2〜3倍遅い程度の速度で上手いこと動くだろう。
(VMでの実行よりも早くなりそうだが、実際にはCPS変換やクロージャ変換をナイーブに行うのはそれなりにパフォーマンスに影響する。実用的なコンパイラを作るよりはJITの方が望ましいアプローチと考えられる。)
というわけで、今後はmoshのconfigureを待ってる間はコンパイラを書くことにした(Cygwinだと一度のビルドにそれなりに時間が掛かる)。

define, letの置き換え

まず、最低限必要な、defineとletの置き換えを実装した。

defineは単純にset!に置き換える。expanderは、defineの出現箇所が適切かどうかなどの判定を予め行っているため、もうdefineとset!を区別する必要性は無い(追記:間違い。)。
同じ名前のdefineが出てきたら困るが、幸いなことにexpanderは全ての*1シンボルを固有の名前にリネームしてしまうので、同じ名前が別の意味で出てくることは無い。90 minutes 〜でも同様の変換を行っている。

(define a 10) => (set! a 10)

もう一つ、letの置き換えもほぼ自明で、expanderの出力するプログラムにはletが含まれるが、この形式のものしか無い。

(let ((a b)) body ...) => ((lambda (a) body...) b)

変換プログラムも簡単に作ることが出来る。注意点はquoteの中は変換しないこと。quoteに当たったら変換を打ち切るようにする。

(define (transform form)
  (if (pair? form)
    (case (car form)
      ((quote) form) ; STOP transform
      ((define) (macro-define form))
      ((let) (macro-let form))
      (else (transform-begin form)))
    form))

変換は再帰的に呼ばなければならないことにも注意する。つまり、letやdefineを変換した場合、その本体部分も続けて変換する必要がある。

; convert define to set!
(define (macro-define form)
  (let ((name (cadr form))
        (body (cddr form)))
    (if (symbol? name) ; check...
      `(set! ,name ,@(transform-begin body))
      (error 'macro-define "ERROR!"))))

変換後のコードの性質

主にexpanderの働きによって、元のR6RSに比べれば大幅に単純なコードが出てくる。つまり、

  • 特殊形式はset!、if、begin、quote、lambdaだけ
  • シンボルはすべてリネームされている。つまり、同じ名前で異なる意味になるシンボルは無い。
    • ただし、set!によって"場所によって"シンボルの意味が変わる可能性は有ることに注意。
  • ライブラリ等も全て解決されている。

あと、R6RSの非常に便利な性質、『外部ライブラリは常にimmutable』も考慮に値する。要するに、listやcall/ccのような組み込み手続きの意味は実行中に上書きされることは無い(もし上書きするようなコードを書いた場合は、expanderがエラーとして検出する)。

次 : CPS変換

次はコードをCPS変換する。コードをCPS変換すると、全てのlambdaはパラメタが一つ増え、呼び出しの時には継続の値も同時に渡すようになる。
Schemeの上でこれらを考えるとき、ホスト(今回の場合Mosh)のcall/ccと、ここで出てくる継続は"全く"関係無い事に注意する。ここでの継続はMoshから(= 我々から)見ると、本当に単なる値でしかない。(CPS変換を行った後、全てのlambdaを抽出して番号をつけるので、最終的に継続の値とは単なる番号になってしまう。)

*1:R5RSプログラムをexpandする場合は例外で、これの対応は後回しにする。