A-normal form 再学習 その6 - Scheme VM

scheme

define の normalize を変えた。a-normalize-name ではなくて a-normalize-with-kが良い。
こうでないと inline 時の手続きの大きさが把握できない。

現状を整理。

  • A-reduction が動くようになった。
  • inline が正しく行われているかを見よう。
    • 短めの手続き

簡単な inline 展開

(define (kar obj) (car obj))

(print
 (kar '(a . b)))

と思ったら quote の扱いがおかしい。
quote は value? => #t であること、normalize は (k m)を返すことを追加して対応。

ついでに

(beta-reduction '(car '(a . b)))

の結果がおかしい。
list ではないものに map を使っているからか。

(define (map-pair proc p)
  (let loop ([p p])
    (cond [(null? p) '()]
          [(pair? p)
           (cons (proc (car p)) (loop (cdr p)))]
          [else (proc p)])))

自前で用意したけど標準手続きでありそうだよなあ。

inline 展開後

(define kar (lambda (G62) (car G62)))
(let1 G63 (begin (car '(a . b))) (print G63))

不十分だが同じ動作をするコードが得られた。
この材料だけではなんとも考察しがたいのでもう一例

(define	 (kar obj) (car obj))

(print
 (kar (kar '((a . b) . c))))

=>

(define kar (lambda (G62) (car G62)))
(let1 G63 (begin (car '((a . b) . c)))
  (let1 G64 (begin (car G63))
    (print G64)))

気になるのは

  • この文脈では begin は省略可能。（コンパイル結果には影響ないけど）
  • A-reduction の結果 let1 を2つ経由しているのだけど遅くならない?

かな。速度は計測すれば良かろう。

named let のバグ

計測のために named let でループを作ったがコンパイルエラーになるバグがあったので修正。

named let の実行バグ

正しいコードなのに実行できない。これは VM のバグ。
スタックオーバーフローだった。 tail call がうまく行っていないな。
あああ。a-normalize の結果、tail call が tail call ではなくなってしまっているな。

(a-normalize
 '(begin (+ 1 2) (+ 2 3)))

=>

(let1 G1066 (+ 1 2) (let1 G1068 (+ 2 3) (begin G1066 G1068)))

これはつまり、let1, let, begin, lambda などの最後の body は正規化しないのが良いということ?
進むにつれて全然自信がなくなる＞＜。
落ち着け落ち着け。


正規化により末尾呼び出しであるという情報が失われるのが問題。現在のコードでこの問題が起こるのは begin のときだけ。
良く見たら begin の normalize は定義してなかった。
まずは安易に正規化しても何も変わらないとしてみようか。意図通り動いた。
末尾以外は正規化しても良いと思うが、そこは ToDo ということで。

計測

(define (kar obj) (car obj))

(let loop ([i 1])
  (if (= i 10000)
      i
      (begin (kar (kar '((a . b) . c)))
             (loop (+ i 1)))))

を inline 展開したら 50% ほど速くなった。
すごくない？

というわけで単純な場合は良い成果が出ることが分かった。