lispの自作VMへのコンパイラ。
この記事はKobeUniv Advent Calendar 2015の20日めの記事です。 今回は、僕が書いているlisp処理系をどう実装したかについて書こうと思います。 完成が間に合わなかったので、できたら後日公開します。
実装したこと、してないこと
搭載機能
- vm(スタックマシン)上で動作
- 継続を第一級オブジェクトとして使える。call/cc
実装中
- 健全なマクロ
未実装
- 末尾再帰最適化
- その他最適化
とりあえず後述するcps変換を入れないで階乗をコンパイル するとこんなかんじになりました。
00: FUNCTION 3 01: SETG fact 02: STOP 03: LAMBDA0: 04: LOADL 0,0 05: ARGS 1 06: LOADG zero? 07: CALL 08: IF 2 09: PUSH 1 10: FORWORD 13 11: LOADL 0,0 12: LOADL 0,0 13: PUSH 1 14: ARGS 2 15: LOADG - 16: CALL 17: ARGS 1 18: LOADG fact 19: CALL 20: ARGS 2 21: LOADG * 22: CALL 23: RET
(+ (+ a b ) (+ c d ) )
00: LOADG a 01: LOADG b 02: FUNCTION 21 03: ARGS 3 04: LOADG + 05: CALL 06: STOP 07: LAMBDA0: 08: LOADL 0,0 09: ARGS 1 10: LOADG return 11: CALL 12: RET 13: LAMBDA1: 14: LOADL 1,0 15: LOADL 0,0 16: FUNCTION 7 17: ARGS 3 18: LOADG + 19: CALL 20: RET 21: LAMBDA2: 22: LOADG c 23: LOADG d 24: FUNCTION 13 25: ARGS 3 26: LOADG + 27: CALL 28: RET
ほとんど最適化してないので括弧が少しあるだけでだいぶ大きくなりますね。 ちなみに、cps変換いれなかったら14行のコードに成りました。倍以上です。
やったこと
スタックマシンへのコンパイルは、コードがリスト構造なので いくつかの法則にもとづいて変換するだけです。
例えば、関数適用だと、
( F 1 2 3 )
PUSH 1 PUSH 2 PUSH 3 ARG 3 LOADG F CALL
ifはこんなかんじ
(if #t 2 3 )
PUSH #t if 2 PUSH 2 FORWORD 2 PUSH 3
(※)ifの右についている数字は、falseだった場合コードのアドレス進ませる量で、 FORWORDも右の数だけコードを進ませる命令です。
cps変換
今回は、継続の実装のためにCPS変換を使いました。 以前作ったのは、VMの情報をまるごと保存しておいて, 継続呼び出し時に現在の内容を上書きするものでした。 VMに手を入れなくてすむのはありがたい。
( + PROC1 (+ PROC2 PROC3 ) )
これの評価順序は、 PROC1を評価する -) PROC2を評価する -) PROC3を評価する -) PROC2の結果とPROC3の結果を足す -) その結果とPROC1とを足す となっています。 これの"-)"ごとにlambdaでくるんでしまいます。 すると以下のようなコードになります
(PROC1 (lambda (z1) (PROC2 (lambda (z2) (PROC3 (lambda (z3) ( + z2 z3 (lambda (z4) (+ z1 z4 ...) ) ) ) ) ) ) ) )
この変換をするとすべての関数呼び出しで継続が引数が最後にくるので 組み込み関数も変換する必要があります。
(define (k-add a b k ) (k (+ a b ) ) )
lambda式も継続とります。
(lambda (ARGS k ) (k BODY ) )
VMが太らなくてすみましたが、コードがかなり太ってしまいました。 関数呼び出しも増えました。 僕は、継続実装のために使いましたが、 この形式は様々な最適化しやすい形ですし、β 簡約で少しは短くできるそうなので うまくやればいいことがあるかもしれませんね。
おわり
やったことをはしょりまくって説明しただけでしたorz マクロ実装間に合いませんでしたorz 最適化できませんでしたorz
