末尾呼び出し最適化 その2
input
- 末尾かどうか？
- 末尾までに消費したスタック
output
- FRAME の削除
- SHIFT の挿入
分からない動作
列挙
| pass3/$local-assign | val は tail => #f |
| pass3/$global-assign | val は tail => #f |
| pass3/$seq | begin の末尾だけ tail を受け継ぐ。それ以外は #f |
| pass3/$asm-xx-arg | #f |
| pass3/$if | test は #f 。then/else は受け継ぐ |
| pass3/$define | val は #f |
| pass3/compile-arg | #f |
| pass3/$call | 引数のコンパイルは #f 。body は引数の数+LET_FRAMEサイズ。SHIFT発行 |
| pass3/$labmda | 引数の数 |
| pass3/$let | tail?だったら vars-length + 2 を足す |
はじめよう
末尾呼び出しがうまく行く例を見ながら考える。
(define (a x) x) ((lambda (o p q r) (a 3)) 3 4 5 6)
VM から見ると
- frame 作成
- 引数の o p q r の push
- 引数 3 の push
- 引数3 を 4 個分 shift （つまり o p q r）を捨てる
- a にジャンプ
- a から return で 3 を片付け、frame の戻り先へ。
コンパイラから見ると
- 末尾で呼び出される手続き a は他の手続きと全く同じコンパイル結果。
- 末尾位置の a の呼び出し時には frame 作らない
- 末尾位置の a の呼び出しの直前に o p q r の数だけ SHIFT で消す。
という感じか。
コンパイラは「スタックからどれだけの引数をさっくり消さないといけないか？」を持ち回っている。（lambda に入るとリセットされる）
ここまで rev563。
(let ([o 2] [p 3] [q 4] [r 5]) (a 3))
これは末尾呼び出しだが、外側に lambda がないと末尾呼び出し最適化は行わない。（と思う。）
例えば以下のようなものが末尾呼び出し最適化されれば良い。
((lambda (o p q r) (let ([x 1]) (a 3))) 2 3 4 5)
これは現状の Mosh でも OK 。
さて問題は何だっけか。$map1 がスタックオーバーフローするな。
(define (my-map1 f l) (if (null? l) l (cons (f (car l)) (my-map1 f (cdr l))))) (my-map1 (lambda (x) x) (vector->list (make-vector 10000 3)))
これは gosh や ypsilon ではスタックオーバーフローにならない。うーなぜだ。
http://d.hatena.ne.jp/higepon/20081027/1225087816
ここの議論で shiro さんのコメントにより原因が分かる。スタックオーバーフローはエラーではなくて自動伸長するのか。（OSが用意するネイティブスタックと同じだね）
というわけでやることは主に2つ
- stack自動伸長を実装する。
- shift 1 0 は発行しなくてもよい。
