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

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

その他参考書籍

問題 5.45-a.

コード(BBEdit, Emacs)

sample45.scm

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

(load "./eceval.scm")

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

sample14.scm

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

(load "./simulator.scm")

(define factorial-machine
  (make-machine
   (list (list '= =) (list '- -) (list '* *))
   '((assign continue (label fact-done))
     fact-loop
     (test (op =) (reg n) (const 1))
     (branch (label base-case))
     (save continue)
     (save n)
     (assign n (op -) (reg n) (const 1))
     (assign continue (label after-fact))
     (goto (label fact-loop))
     after-fact
     (restore n)
     (restore continue)
     (assign val (op *) (reg n) (reg val))
     (goto (reg continue))
     base-case
     (assign val (const 1))
     (goto (reg continue))
     fact-done)))

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

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

$ ./sample45.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:
(factorial 6)
(total-pushes = 37 maximum-depth = 17)

;;; EC-Eval value:
720

;;; EC-Eval input:
(factorial 7)
(total-pushes = 43 maximum-depth = 20)

;;; EC-Eval value:
5040

;;; EC-Eval input:
(factorial 8)
(total-pushes = 49 maximum-depth = 23)

;;; EC-Eval value:
40320

;;; EC-Eval input:
(factorial 9)
(total-pushes = 55 maximum-depth = 26)

;;; EC-Eval value:
362880

;;; EC-Eval input:
(factorial 10)
(total-pushes = 61 maximum-depth = 29)

;;; EC-Eval value:
3628800

;;; EC-Eval input:
(define (factorial n)
  (if (= n 1)
      1
      (* (factorial (- n 1)) n)))
(total-pushes = 3 maximum-depth = 3)

;;; EC-Eval value:
ok

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

;;; EC-Eval value:
1

;;; EC-Eval input:
(factorial 2)
(total-pushes = 48 maximum-depth = 13)

;;; EC-Eval value:
2

;;; EC-Eval input:
(factorial 3)
(total-pushes = 80 maximum-depth = 18)

;;; EC-Eval value:
6

;;; EC-Eval input:
(factorial 4)
(total-pushes = 112 maximum-depth = 23)

;;; EC-Eval value:
24

;;; EC-Eval input:
(factorial 5)
(total-pushes = 144 maximum-depth = 28)

;;; EC-Eval value:
120

;;; EC-Eval input:
(factorial 6)
(total-pushes = 176 maximum-depth = 33)

;;; EC-Eval value:
720

;;; EC-Eval input:
(factorial 7)
(total-pushes = 208 maximum-depth = 38)

;;; EC-Eval value:
5040

;;; EC-Eval input:
(factorial 8)
(total-pushes = 240 maximum-depth = 43)

;;; EC-Eval value:
40320

;;; EC-Eval input:
(factorial 9)
(total-pushes = 272 maximum-depth = 48)

;;; EC-Eval value:
362880

;;; EC-Eval input:
(factorial 10)
(total-pushes = 304 maximum-depth = 53)

;;; EC-Eval value:
3628800

;;; EC-Eval input:
(exit)
$ ./sample14.scm 
1! = 1
(total-pushes = 0 maximum-depth = 0)
2! = 2
(total-pushes = 2 maximum-depth = 2)
3! = 6
(total-pushes = 4 maximum-depth = 4)
4! = 24
(total-pushes = 6 maximum-depth = 6)
5! = 120
(total-pushes = 8 maximum-depth = 8)
6! = 720
(total-pushes = 10 maximum-depth = 10)
7! = 5040
(total-pushes = 12 maximum-depth = 12)
8! = 40320
(total-pushes = 14 maximum-depth = 14)
9! = 362880
(total-pushes = 16 maximum-depth = 16)
10! = 3628800
(total-pushes = 18 maximum-depth = 18)
$

プッシュ回数
n	解釈	翻訳	特殊目的
1	16	7	0
2	48	13	2
3	80	19	4
4	112	25	6
5	144	31	8
6	176	37	10
7	208	43	12
8	240	49	14
9	272	55	16
10	304	61	18
k	32k - 16	6k + 1	2k - 2

翻訳/解釈: 3/16

特殊目的/解釈: 1/16

最大スタック深さ
n	解釈	翻訳	特殊目的
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	5k + 3	3k	2k - 2

翻訳/解釈: 3/5

特殊目的/解釈: 2/5

Kamimura's blog

2015年1月12日月曜日

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

0 コメント:

コメントを投稿