2006-05-12

Schemeのコンパイラがあったので使ってみた。名前がなんとも憎らしい。

The CHICKEN Scheme Compiler

とりあえずベンチマークということで、たらい回し関数。

;; tak.scm
(define (tak x y z)
  (if (<= x y) y
    (tak (tak (- x 1) y z)
         (tak (- y 1) z x)
         (tak (- z 1) x y))))

(tak 13 5 0)

これをインタプリタ（Gauche）とコンパイラそれぞれで実行。

% time gosh tak.scm
19.050u 0.069s 0:20.49 93.2%    0+0k 0+4io 0pf+0w
% csc -O3 tak.scm
% time ./tak
16.663u 0.503s 0:18.30 93.7%    0+0k 0+2io 0pf+0w

あまり差がでないことに驚き。インタプリタの開始、終了のオーバーヘッドだってそれなりにあるだろうに。

ついでにC言語でもやってみる

/* tak.c */
int tak(int x, int y, int z) {
    return (x <= y)? y:
        tak(tak(x - 1, y, z),
            tak(y - 1, z, y),
            tak(z - 1, y, z));
}

int main() { return tak(13,5,0); }

% gcc -O3 tak.c
% ./a.out
Segmentation fault
0.011u 0.041s 0:00.36 13.8%     0+0k 0+0io 0pf+0w

Segmetation fault（たぶんスタックオーバーフロー）で即死。そういえば Mac OS X はスタックサイズが8192KBで固定だった。あとでFreeBSD上でやってみるか。

で、ここですごいのは、C言語で書かれたほぼプリミティブな要素しかないプログラムでさえスタックが溢れるほどの再帰の深さなのに、Schemeで書いた方はちゃんと完了しているということ。コンパイル後も遅延評価をはじめとした動的最適化がちゃんと行えているということか。そう考えると、むしろインタプリタの優秀さが目立ってくる。計算量は偉大なのだ。

"Chicken"という名には「インタプリタでも十分なのにわざわざコンパイラ使うやつはチキン野郎だ」といった意味も含まれているのかもしれない*1。

追記（含訂正）

C言語版で、3つ目のtak関数呼び出しのパラメータの渡し方がおかしかった。なんとも初歩的な恥ずかしいミスである。

実行してみるとすんなりと終わった。ちうことで、上述の件は過大評価か。とりあえず、Schemeでコンパイラを使う奴がチキンなのは変わりなさそう。動的最適化の能力を得るにはもっと大きな数値をパラメータに与えてみないと結論は出ないかもしれないが、そこまで計算機をぶんまわす余裕は無し。

*1:FAQには名前の由来っぽいものは見当たらなかった

おびなたん☆

コンパイラを使うチキン野郎

追記（含訂正）

松井の怪我