Scheme - 翻訳系の概観(解釈と翻訳、特殊目的計算機とスタック演算)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• MIT/GNU Scheme (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の5(レジスタ計算機での計算)、5.5(翻訳系)、翻訳系の概観、5.5.7(翻訳したコードと評価器のインターフェース)、解釈と翻訳、問題 5.45-a.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 5.45-a.

問題5.27、問題5.14

コード(BBEdit)

sample.scm

(compile-and-go
'(define (factorial n)
   (if (= n 1)
       1
       (* (factorial (- n 1)) n))))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Saturday October 26, 2013 at 11:02:50 PM
  Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
  Edwin 3.116

1 ]=> (load "./eceval.scm")

;Loading "./eceval.scm"... done
;Value: start-eceval

1 ]=> (load "./sample.scm")

;Loading "./sample.scm"...
(total-pushes = 0 maximum-depth = 0)
;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial 1)

(total-pushes = 7 maximum-depth = 3)
;;; EC-Eval value:
1

;;; EC-Eval input:
(factorial 2)

(total-pushes = 13 maximum-depth = 5)
;;; EC-Eval value:
2

;;; EC-Eval input:
(factorial 3)

(total-pushes = 19 maximum-depth = 8)
;;; EC-Eval value:
6

;;; EC-Eval input:
(factorial 4)

(total-pushes = 25 maximum-depth = 11)
;;; EC-Eval value:
24

;;; EC-Eval input:
(factorial 5)

(total-pushes = 31 maximum-depth = 14)
;;; EC-Eval value:
120

;;; EC-Eval input:
End of input stream reached.
Moriturus te saluto.
$

factorial nについて。

翻訳版と解釈版について。

プッシュ回数とその比

n	翻訳版	解釈版	比
1	7	16	0.4375
2	13	48	0.2708
3	19	80	0.2375
4	25	112	0.2232
5	31	144	0.2152
10	61	304	0.2006
50	301	1584	0.1900
100	601	3184	0.1887
500	3001	15984	0.1877
1000	6001	31984	0.1876
5000	30001	159984	0.1875
10000	60001	319984	0.1875

近づく定数は約0.1875。

最大スタック深さとその比

n	翻訳版	解釈版	比
1	3	3	1
2	5	8	0.625
3	8	13	0.6153
4	11	18	0.6111
5	14	23	0.6666
10	29	53	0.5471
50	149	253	0.5889
100	299	503	0.5944
500	1499	2503	0.5988
1000	2999	5003	0.5994
5000	14999	25003	0.5998
10000	29999	50003	0.5999

近づく定数は約0.6。

特殊目的の計算機と解釈版について。

プッシュ回数とその比

n	特殊目的	解釈版	比
1	0	16	0
2	2	48	0.0415
3	4	80	0.05
4	6	112	0.0535
5	8	144	0.0555
10	18	304	0.5921
50	98	1584	0.0618
100	198	3184	0.0621
500	998	15984	0.0624
1000	1998	31984	0.0624
5000	9998	159984	0.0624
10000	19998	319984	0.0624

最大スタック深さとその比

n	特殊目的	解釈版	比
1	0	3	0
2	2	8	0.25
3	4	13	0.3076
4	6	18	0.333
5	8	23	0.3478
10	18	53	0.1509
50	98	253	0.3873
100	198	503	0.3936
500	998	2503	0.3987
1000	1998	5003	0.3993
5000	9998	25003	0.3998
10000	19998	50003	0.3999

特殊目的のコード対解釈されるコードの比と、翻訳するコード対解釈されるコードの比について。

プッシュ回数とその比

特殊/解釈	翻訳/解釈	比
0.0624	0.1875	0.3326

最大スタックの深さとその比

特殊/解釈	翻訳/解釈	比
0.4	0.6	0.6666

問題の通り、特殊目的計算機は、翻訳したコードよりも遥かに優れていることが分かる。