Scheme - 翻訳系の概観(特殊目的計算機とスタック演算、翻訳系の性能と改良(Fibonacci数))

計算機プログラムの構造と解釈
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.46.を解いてみる。

その他参考書籍

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

問題 5.46.

解釈する性能の計測には問題5.29を参照。register5.14.scmは問題5.14のコード。

コード(BBEdit)

sample.scm

(load "./eval.scm")
(load "./compiler5.44.scm")

(compile-and-go
'(define (fib n)
   (if (< n 2)
       n
       (+ (fib (- n 1)) (fib (- n 2))))))

入出力結果(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:
(fib 0)

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

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

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

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

(total-pushes = 17 maximum-depth = 5)
;;; EC-Eval value:
1

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

(total-pushes = 27 maximum-depth = 8)
;;; EC-Eval value:
2

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

(total-pushes = 47 maximum-depth = 11)
;;; EC-Eval value:
3

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

(total-pushes = 77 maximum-depth = 14)
;;; EC-Eval value:
5

;;; EC-Eval input:
(fib 6)

(total-pushes = 127 maximum-depth = 17)
;;; EC-Eval value:
8

;;; EC-Eval input:
(fib 7)

(total-pushes = 207 maximum-depth = 20)
;;; EC-Eval value:
13

;;; EC-Eval input:
(fib 8)

(total-pushes = 337 maximum-depth = 23)
;;; EC-Eval value:
21

;;; EC-Eval input:
(fib 9)

(total-pushes = 547 maximum-depth = 26)
;;; EC-Eval value:
34

;;; EC-Eval input:
(fib 10)

(total-pushes = 887 maximum-depth = 29)
;;; EC-Eval value:
55

;;; EC-Eval input:
End of input stream reached.
Moriturus te saluto.
$ 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 "./register5.14.scm")

;Loading "./register5.14.scm"... done
;Value: lookup-prim

1 ]=> 
(define (print a)
  (display a))

;Value: print

1 ]=> 
(define fib-machine
  (make-machine
   (list (list '< <) (list '- -) (list '+ +) (list 'print print)
         (list 'newline newline) (list 'read read))
   '(loop
      (assign continue (label fib-done))
      (initialize)
      (assign n (op read))
    fib-loop
      (test (op <) (reg n) (const 2))
      (branch (label immediate-answer))
      (save continue)
      (assign continue (label afterfib-n-1))
      (save n)
      (assign n (op -) (reg n) (const 1))
      (goto (label fib-loop))
    afterfib-n-1
      (restore n)
      (restore continue)
      (assign n (op -) (reg n) (const 2))
      (save continue)
      (assign continue (label afterfib-n-2))
      (save val)
      (goto (label fib-loop))
    afterfib-n-2
      (assign n (reg val))
      (restore val)
      (restore continue)
      (assign val
              (op +) (reg val) (reg n))
      (goto (reg continue))
    immediate-answer
      (assign val (reg n))
      (goto (reg continue))
    fib-done
       (perforrint-statistics)
       (perform (op newline))
       (goto (label loop)))))

;Value: fib-machine

1 ]=> (start fib-machine)
0
0
(total-pushes = 0 maximum-depth = 0)
1
1
(total-pushes = 0 maximum-depth = 0)
2
1
(total-pushes = 4 maximum-depth = 2)
3
2
(total-pushes = 8 maximum-depth = 4)
4
3
(total-pushes = 16 maximum-depth = 6)
5
5
(total-pushes = 28 maximum-depth = 8)
6
8
(total-pushes = 48 maximum-depth = 10)
7
13
(total-pushes = 80 maximum-depth = 12)
8
21
(total-pushes = 132 maximum-depth = 14)
9
34
(total-pushes = 216 maximum-depth = 16)
10
55
(total-pushes = 352 maximum-depth = 18)
End of input stream reached.
Moriturus te saluto.
$

Fibonacci数について。

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

プッシュ回数とその比
n	翻訳版	解釈版	比
0	7	16	0.4375
1	7	16	0.4375
2	17	72	0.2361
3	27	128	0.2109
4	47	240	0.1958
5	77	408	0.1887
6	127	688	0.1845
7	207	1136	0.1822
8	337	1864	0.1807
9	547	3040	0.1799
10	887	4944	0.1794

最大スタック深さとその比
n	翻訳版	解釈版	比
0	3	8	0.375
1	3	8	0.375
2	5	13	0.3846
3	8	18	0.4444
4	11	23	0.4783
5	14	20	0.7
6	17	33	0.5152
7	20	38	0.5263
8	23	43	0.5349
9	26	48	0.5417
10	29	53	0.5472

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

プッシュ回数とその比
n	特殊目的	解釈版	比
0	0	16	0
1	0	16	0
2	4	72	0.0556
3	8	128	0.0625
4	16	240	0.0667
5	28	408	0.0686
6	48	688	0.0698
7	80	1136	0.0704
8	132	1864	0.0708
9	216	3040	0.0711
10	352	4944	0.0712

最大スタック深さとその比
n	特殊目的	解釈版	比
0	0	8	0
1	0	8	0
2	2	13	0.1538
3	4	18	0.2222
4	6	23	0.2609
5	8	20	0.4
6	10	33	0.303
7	12	38	0.3158
8	14	43	0.3256
9	16	48	0.3333
10	18	53	0.3396

特殊目的のコード対解釈されるコードの比と、翻訳するコード対解釈されるコードの比について。(n = 10の場合)

プッシュ回数とその比
特殊/解釈	翻訳/解釈	比
0.0712	0.1794	0.3968

最大スタックの深さとその比
特殊/解釈	翻訳/解釈	比
0.3396	0.5472	0.6206

特殊目的版が遥かに優れている。

Kamimura's blog

2014年1月10日金曜日

Scheme - 翻訳系の概観(特殊目的計算機とスタック演算、翻訳系の性能と改良(Fibonacci数))

0 コメント:

コメントを投稿