Serendip Web Studio

最後のC言語での実装の2問が残っているけれども、一旦これで終了とする。
2008年の11月に開始したので約1年と1ヶ月ちょっとかかったことになる。

計算機プログラムの構造と解釈
posted with amazlet at 09.12.29

ジェラルド・ジェイ サスマン ジュリー …

Processing.js で JavaScript を使って Drawing をしてみる。

processing.init.js をロードすることで type が application/processing の <script> タグの中に記述されたコードが Processing で実行できるようになる。
以下のコードのデモ
<script src="./processing.init.js" type="text/javascript"></script>
<script src="./processing.min.js" type="text/javascript"></script>

<script type="application/processing">
Circle circles = new Circle[50];

void setup() {
size(500, 500);
frameRate(15);
for (int i = 0; i< circles.length; i++) {
circles[i] [...]…

問題5.50
4.1節の超循環評価器を compile-and-go させる。
primitive-procedures に必要な手続きを追加していく。
また、let が定義されていなかったので基本手続きに let を追加する。
レジスタ計算機シミュレータの make-new-machine は性能監視機能を追加したものを使った。
環境へ基本…

問題5.49
式を "読み込み(read-eval-print-loop)"、それを"翻訳(compile)"し、結果のコードを"アセンブリ(assemble)"して実行し、結果を"印字(print-result)"する。
(load "./register_machine.scm")
(load "./compiler.scm")

(define (empty-arglist) ‘())

(define (last-operand? ops)
(null? (cdr ops)))

(define (adjoin-arg arg arglist)
(append arglist (list arg)))

(define the-global-environment (setup-environment))

(define (get-global-environment)
the-global-environment)

(define (make-compiled-procedure entry env)
(list ‘compiled-procedure entry env))

(define (compiled-procedure? proc)
(tagged-list? proc ‘compiled-procedure))

(define (compiled-procedure-entry c-proc)
(cadr c-proc))

(define (compiled-procedure-env c-proc)
(caddr c-proc))

(define (make-register-machine) register-machine)

(define operations
(list (list [...]…

問題5.48
;; 環境に compile-and-run を基本手続として追加する。
(define (setup-environment2)
(extend-environment
(list ‘compile-and-run)
(list (list ‘primitive compile-and-run))
(setup-environment)))

;; setup-environment2 を呼び出すように変更する。
(define (compile-and-go expression)
(let ((instructions
(assemble (statements
[...]…

問題5.47
元の翻訳系では翻訳した手続きが合成手続き（解釈される手続き）を呼び出せない。
$ gosh
gosh> (load "./ece4compiler.scm")
#t
(compile-and-go
‘(begin
(define (g x) (+ x 10))
(define (f x) (g x))))

(total-pushes = 0 max-depth = 0)
;;; EC-Eval value:
ok

;;; EC-Eval input:
(f 1) ; <= 翻訳した手続き g を呼び出す

(total-pushes = 5 max-depth = 3)
;;; EC-Eval value:
11

;;; EC-Eval input:
(define (g x) (+ x 20)) ; [...]…

Fibonacci でのプッシュ回数、最大スタック深さを翻訳版、解釈版、特殊目的版で比較する。
プッシュ回数の比較

n
翻訳版
解釈版
特殊目的版
翻訳版と解釈版の比率
翻訳版と特殊目的版の比率

3
27
128
8
4.741
0.296

4
47
240…

演習3-1
元の binsearch と改良版 binsearch2 とで実行時間の差を比べる。
#include <stdio.h>
#include <time.h>
#define MAXSIZE 0×100000

int binsearch(int x, int v[], int n);
int binsearch2(int x, int v[], int n);

int main(int argc, char *argv[])
{
int v[MAXSIZE];
int i;
time_t t;

for (i=0; i<MAXSIZE; i++) {
[...]…

問題5.45
push回数

n
翻訳版
解釈版
翻訳版と解釈版の比率
特殊目的版
翻訳版と特殊目的版の比率

3
19
80
4.211
4
0.211

4
25
112
4.480
6
0.240

5
31
144
4.645
8
0.258

6
37
176
4.757
10
0.270

7
43
208
4.837
12
0.279

8
49
240
4.898
14
0.286

30
181
944
5.215
58…

翻訳したコードを受け取った場合の処理を追加し、コードを翻訳して REPL 呼び出す手続きを追加する。
実行には以下のファイル群を利用する。

compiler.scm (5.5節の翻訳系)
ece4compiler.scm (5.4節の積極制御評価器計算機)
eval4ece.scm (4.1節の超循環評価器)
register_machine.scm (5.2節のレジスタ計算…