Scheme - レジスタ計算機での計算(翻訳系(翻訳したコードと評価機のインターフェース(Fibonacci数、解釈と翻訳, 特殊目的, 性能, 最大スタック深さ, プッシュ回数)))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルドエイブルソン (著)ジュリーサスマン (著)
ジェラルド・ジェイサスマン (著)
Harold Abelson (原著)Julie Sussman (原著)
Gerald Jay Sussman (原著)和田英一 (翻訳)

開発環境

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

計算機プログラムの構造と解釈[第2版](ハロルドエイブルソン (著)、ジュリーサスマン (著)、ジェラルド・ジェイサスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田英一 (翻訳)、翔泳社、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の5(レジスタ計算機での計算)、5.5(翻訳系)、5.5.7(翻訳したコードと評価機のインターフェース)、解釈と翻訳、問題 5.46.を解いてみる。

その他参考書籍

問題 5.46.

コード(BBEdit, Emacs)

sample46.scm

#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-

(load "./eceval.scm")

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

sample46_1.scm

#!/usr/bin/env gosh
;;-*- coding: utf-8 -*-

(load "./simulator.scm")

(define fibonacci-machine
  (make-machine
   (list (list '< <) (list '- -) (list '+ +))
   '((assign continue (label fib-done))
     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)))

(for-each
 (lambda (i)
   ((fibonacci-machine 'stack) 'initialize)
   (set-register-contents! fibonacci-machine 'n i)
   (start fibonacci-machine)
   (print "fib(" i ") = " (get-register-contents fibonacci-machine 'val))
   (print-statistics fibonacci-machine))
 '(0 1 2 3 4 5 6 7 8 9 10))

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

$ ./sample46.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:
(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))
(total-pushes = 3 maximum-depth = 3)

;;; EC-Eval value:
ok

;;; EC-Eval input:
(fib 0)
(total-pushes = 16 maximum-depth = 8)

;;; EC-Eval value:
0

;;; EC-Eval input:
(fib 1)
(total-pushes = 16 maximum-depth = 8)

;;; EC-Eval value:
1

;;; EC-Eval input:
(fib 2)
(total-pushes = 72 maximum-depth = 13)

;;; EC-Eval value:
1

;;; EC-Eval input:
(fib 3)
(total-pushes = 128 maximum-depth = 18)

;;; EC-Eval value:
2

;;; EC-Eval input:
(fib 4)
(total-pushes = 240 maximum-depth = 23)

;;; EC-Eval value:
3

;;; EC-Eval input:
(fib 5)
(total-pushes = 408 maximum-depth = 28)

;;; EC-Eval value:
5

;;; EC-Eval input:
(fib 6)
(total-pushes = 688 maximum-depth = 33)

;;; EC-Eval value:
8

;;; EC-Eval input:
(fib 7)
(total-pushes = 1136 maximum-depth = 38)

;;; EC-Eval value:
13

;;; EC-Eval input:
(fib 8)
(total-pushes = 1864 maximum-depth = 43)

;;; EC-Eval value:
21

;;; EC-Eval input:
(fib 9)
(total-pushes = 3040 maximum-depth = 48)

;;; EC-Eval value:
34

;;; EC-Eval input:
(fib 10)
(total-pushes = 4944 maximum-depth = 53)

;;; EC-Eval value:
55

;;; EC-Eval input:
(exit)
$ ./sample46_1.scm
fib(0) = 0
(total-pushes = 0 maximum-depth = 0)
fib(1) = 1
(total-pushes = 0 maximum-depth = 0)
fib(2) = 1
(total-pushes = 4 maximum-depth = 2)
fib(3) = 2
(total-pushes = 8 maximum-depth = 4)
fib(4) = 3
(total-pushes = 16 maximum-depth = 6)
fib(5) = 5
(total-pushes = 28 maximum-depth = 8)
fib(6) = 8
(total-pushes = 48 maximum-depth = 10)
fib(7) = 13
(total-pushes = 80 maximum-depth = 12)
fib(8) = 21
(total-pushes = 132 maximum-depth = 14)
fib(9) = 34
(total-pushes = 216 maximum-depth = 16)
fib(10) = 55
(total-pushes = 352 maximum-depth = 18)
$

プッシュ回数
n	解釈	翻訳	特殊目的	翻訳/解釈	特殊目的/解釈
0	16	7	0	0.4375	0
1	16	7	0	0.4375	0
2	72	17	4	0.2361	0.0556
3	128	27	8	0.2109	0.0625
4	240	47	16	0.1958	0.0667
5	408	77	28	0.1887	0.0686
6	688	127	48	0.1846	0.0698
7	1136	207	80	0.1822	0.0704
8	1864	337	132	0.1808	0.0708
9	3040	547	216	0.1799	0.0711
10	4944	887	352	0.1794	0.0712

最大スタック深さ
n	解釈	翻訳	特殊目的
0	8	3	0
1	8	3	0
2	13	5	2
3	18	8	4
4	23	11	6
5	28	14	8
6	33	17	10
7	38	20	12
8	43	23	14
9	48	26	16
10	53	29	18
k(> 1)	5k + 3	3k - 1	2k - 2

翻訳/解釈: 3/5

特殊目的/解釈: 2/5

Kamimura's blog

2015年1月13日火曜日

Scheme - レジスタ計算機での計算(翻訳系(翻訳したコードと評価機のインターフェース(Fibonacci数、解釈と翻訳, 特殊目的, 性能, 最大スタック深さ, プッシュ回数)))

0 コメント:

コメントを投稿