SICP 読み (350) 5.5 翻訳系
昨年中で終わる、と言ったはずなのにもう一月が終わる。残りはあと三頁なんですが終端は遥か彼方。とりあえず_解釈と翻訳_な部分の理解は微妙ですが問題に着手。
問題 5.45
ええと、5.37 は 337p で 5.14 は 318p にある。あと_特殊目的の階乗計算機_なコードは 304p に。
とりあえず、解釈系にて動作を見てみる
gosh> (add-load-path ".") ("." "/usr/share/gauche/site/lib" "/usr/share/gauche/0.8.7/lib") gosh> (load "load-eceval-compiler") #t gosh> (load "ch5-compiler") #t gosh> (define true #t) true gosh> (define false #f) false gosh> (start-eceval) ;;; EC-Eval input: (define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1))))) (total-pushes = 3 maximum-depth = 3) ;;; EC-Eval value: ok ;;; EC-Eval input: (factorial 5) (total-pushes = 176 maximum-depth = 23) ;;; EC-Eval value: 120 ;;; EC-Eval input:
面倒なので最初から。今度は翻訳してみる。
gosh> (add-load-path ".") ("." "/usr/share/gauche/site/lib" "/usr/share/gauche/0.8.7/lib") gosh> (load "load-eceval-compiler") #t gosh> (load "ch5-compiler") #t gosh> (define true #t) true gosh> (define false #f) false gosh> (compile-and-go '(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1))))) ) (total-pushes = 0 maximum-depth = 0) ;;; EC-Eval value: ok ;;; EC-Eval input: (factorial 5) (total-pushes = 37 maximum-depth = 17) ;;; EC-Eval value: 120 ;;; EC-Eval input:
これはこれは。ちょっと連続で数値を取ってみます。
;;; EC-Eval input: (factorial 1) (total-pushes = 13 maximum-depth = 5) ;;; EC-Eval value: 1 ;;; EC-Eval input: (factorial 2) (total-pushes = 19 maximum-depth = 8) ;;; EC-Eval value: 2 ;;; EC-Eval input: (factorial 3) (total-pushes = 25 maximum-depth = 11) ;;; EC-Eval value: 6 ;;; EC-Eval input: (factorial 4) (total-pushes = 31 maximum-depth = 14) ;;; EC-Eval value: 24 ;;; EC-Eval input: (factorial 5) (total-pushes = 37 maximum-depth = 17) ;;; EC-Eval value: 120 ;;; EC-Eval input: (factorial 6) (total-pushes = 43 maximum-depth = 20) ;;; EC-Eval value: 720
ええと、total-pushes は (+ 10 (* 3 n)) で maximum-depth は (+ 2 (* 3 n)) か。解釈系についてもう一度。
;;; EC-Eval input: (factorial 1) (total-pushes = 48 maximum-depth = 11) ;;; EC-Eval value: 1 ;;; EC-Eval input: (factorial 2) (total-pushes = 80 maximum-depth = 14) ;;; EC-Eval value: 2 ;;; EC-Eval input: (factorial 3) (total-pushes = 112 maximum-depth = 17) ;;; EC-Eval value: 6 ;;; EC-Eval input: (factorial 4) (total-pushes = 144 maximum-depth = 20) ;;; EC-Eval value: 24 ;;; EC-Eval input: (factorial 5) (total-pushes = 176 maximum-depth = 23) ;;; EC-Eval value: 120 ;;; EC-Eval input: (factorial 6) (total-pushes = 208 maximum-depth = 26) ;;; EC-Eval value: 720 ;;; EC-Eval input:
total-pushes は (+ 16 (* 32 n)) で maximum-depth は (+ 8 (* 3 n)) か。深さは同じ傾きですが total は凄い差だな。これは space 的にはさほどの差はないけど time なソレが全然違う、という事になるのか。
続き
eceval に図 5.11 な手続きを評価させようと必死に試行錯誤してたんですが、参照してた問題 5.14 で答えがある事に先ほど気がつきました。若年性痴呆と言っても過言ではないのだろうか。
しかもすげぇ色々ぐだぐだ書きなぐってたりするんですが、全て抹消。ちなみに出力は以下の模様。
gosh> (f 'start) (n = 5) (val = 120) (total-pushes = 8 maximum-depth = 8) (n = 4) (val = 24) (total-pushes = 6 maximum-depth = 6) (n = 3) (val = 6) (total-pushes = 4 maximum-depth = 4) (n = 2) (val = 2) (total-pushes = 2 maximum-depth = 2) (n = 1) (val = 1) (total-pushes = 0 maximum-depth = 0) done gosh>
これは (- 2 (* 2 n)) というか (* 2 (- n 1)) というか。
で
又ワケワカらなくなり始めてます。まずコードの比という意味を行数と勘違い。翻訳したソレは分かるけど解釈系はどうしてるんだっけ??という所でドロ沼。