secd Machine DUM, RAP

scheme

再帰的な定義のためのインストラクション,DUM, RAP を一応実装した。まだ怪しいところがある。

  • RAP は set-car! を使って環境を書き換える。結果として循環構造を持ったリストができる。（※この時点で間違っている可能性あり。例がほとんどなく自信無し）
  • ともかくもRAPとコンパイル側とを実装し、letrec が動くようになった。
gosh> (compile () '(letrec ((fib
                      (lambda (n)
                        (if (< n 2)
                            n
                            (+ (fib (- n 1))
                               (fib (- n 2)))))))
                     (fib 23)))
(DUM NIL LDF (LDC 2 LD (1 . 1) < SEL (LD (1 . 1) JOIN) (NIL LDC 2 LD (1 . 1) - CONS LD (2 . 1) AP NIL LDC 1 LD (1 . 1) - CONS LD (2 . 1) AP + JOIN) RTN) CONS LDF (NIL LDC 23 CONS LD (1 . 1) AP RTN) RAP)

追記。コンパイル結果が循環構造を持っている訳では無く、実行時に発生する。

fib 23 を gauche と secd machine 版で比較する。

gosh> (time (letrec ((fib
                      (lambda (n)
                        (if (< n 2)
                            n
                            (+ (fib (- n 1))
                               (fib (- n 2)))))))
              (fib 23)))
;(time (letrec ((fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (-  ...
; real   0.030
; user   0.020
; sys    0.000
28657

gosh> (time (run '(letrec ((fib
                      (lambda (n)
                        (if (< n 2)
                            n
                            (+ (fib (- n 1))
                               (fib (- n 2)))))))
              (fib 23))))
;(time (run '(letrec ((fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (f ...
; real  11.876
; user  11.540
; sys    0.120
((28657 . s) e c d)
stop

0.03 sec vs 11.87 sec。素晴らしいことに、ざっと400倍も遅い。あぁ、ネイティブコンパイラの時には fib だけは凌駕できていたというのに。