関数型言語の勉強にSICPを読もう - (66) 4章 - 超言語的抽象(222ページ) C++でSchemeインタプリタを作ろう15
問題4.6
letのサポートを入れようという話。
letはlambdaを使って等価変換ができる。
例えば
(let ((a "hello") (b "good bye")) (display a) (display b))
は
((lambda (a b) (display a) (display b)) "hello" "goodbye")
となる。
なのでTranslatorの時点で let式を見つけたら、Letオブジェクト生成する。
で、Letのeval時に Lambda式に変換してから evalする。
こんな感じ。
Application* Let::expand()
{
Lambda* lambda = new Lambda(body_, variables_);
return new Application(lambda, values_);
}
Object* Let::eval(Environment* env)
{
Object* application = expand();
return application->eval(env);
}
問題4.7
let*の話。
(let* ((a 3) (b (+ a 3)) (c (- b 1))) (display c))
let* では左から順に評価されて、左側の変数を参照できる。
これを let で表現して let*をインタプリタでサポートせよという問題。
let*は let の入れ子でかけると思う。
(let ((a 3))
(let ((b (+ a 3)))
(let ((c (- b 1)))
(display c))))こんな感じで。
Let* を Letに変換する部分を書いて（もちろん再帰）、きちんと動いた。
なんだかマクロを実装した方が早いんじゃないかという気もしなくもない。
でもまあSICPではマクロが出てこないから微妙。
計算機プログラムの構造と解釈
posted with amazlet on 06.05.31
関数型言語の勉強にSICPを読もう - (66) 4章 - 超言語的抽象(222ページ) C++でSchemeインタプリタを作ろう15
いろいろな構文が動いたので悪ノリしてパフォーマンスを測定してみたら恐ろしい罠が!
計測対象
(begin
(define count (lambda (x)
(if (= 5000 x)
x
(begin
(count (+ x 1))))))
(display (count 0)))条件分岐・変数の参照・再帰・値の比較などなどの要素を盛り込んであります。
結果
Gaucheでは一瞬で実行が終わるのに、数十秒かかる。。。
どうして遅いのか?
ループの回数を増やすと極端に遅くなるということから、変数のlookupのあたりが怪しいなぁとあたりをつけます。
で、gprof を使って見たところ。
% cumulative self self total time seconds seconds calls us/call us/call name 49.79 4.65 4.65 37537506 0.12 0.21 monash::Frame::lookup(monash::Variable*)
やはりlookupに時間がかかっていますね。ん？callの回数が37,537,506 回！
今のlookupは FrameのリストからFrameを取り出してhashmapで変数を名前からlookupします。
そのFrameに変数が見つからなければ、次のFrameに対して同じことをやります。
例えば + をlookupした場合、最上位のFrameに束縛されているので、Frameのリストを最後までたどってやっと変数が見つかります。
で、問題は5000回目のループの時点でFrameのリストの要素が5000個あって、更に最悪の場合その全ての要素に対してlookupするという状況が発生するということです。
再帰呼び出しで、再帰の回数分Frameができてしまうのがしょうがないならば、変数のlookup処理を工夫すれば良さそうです。
例えば、グローバルなhashmapにlookupテーブルを作っておけばかなり速くなると思う。
再帰の回数分Frameができるってのは結局 inlineで展開しているようなもので何かおかしい気がするけどもう少し考えてみます。
竹内関数
コメントにて竹内関数というものを教えていただいた。
どうもこの関数はベンチマーク関数として有名らしい。
(begin
(define tak (lambda (x y z)
(cond
((> x y) (tak (tak (- x 1) y z) (tak (- y 1) z x) (tak (- z 1) x y))) (#t y)))) (tak 12 6 0))一瞬で終わった。これは速かった。
ん？でも tak の戻り値がGacheの結果と違うなぁ。
計算機プログラムの構造と解釈
posted with amazlet on 06.05.31
