(wat-aro)

生きてます

SICP 問題 5.31

どのタイミングで以下の式を評価する際にどのタイミング何を退避して復帰するか (f 'x 'y) 'x 'yはシンボルなのでこれ以上の評価が必要ないので 何も退避しなくてよい. ((f) 'x 'y) 'x 'yがシンボルなので上と同じく退避の必要ない. (f (g 'x) y) fを評価…

SICP 問題 5.30b

primitive-procedure のエラーもECEVAL上で扱えるようにする. まず基盤のschemeから手続きを登録するときに事前チェックするように変更する. もしエラーになるような引数が与えられた時には('failed . 'hoge-syntax-error)を返す. primitive-applyでvalに…

SICP 問題 5.30a

評価プロセスでのエラーをschemeでなくecevalで捕まえてREPLを継続する. ;;; 5.2 で実装したシミュレータ.トレース機能追加済み. ;;; 初めてassignするレジスタを登録していくタイプ (load "./register-machine-simulator.scm") ;;; 4.1で実装した評価器 …

SICP 問題 5.29

a: n≧2の時のfib(n)を計算するのに必要なスタックの最大深さのnを使った式を与えよ. b: 同じ条件でfib(n)のプッシュの総数を求める ;;; EC-Eval input: (define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))) (total-pushes = 3 maximum-depth …

SICP 問題 5.28

ev-sequenceで行っていた末尾再帰の最適化をやめた場合のfactorialの比較. 最適化をやめると反復的factorialはプッシュ回数が37n+1, 最大深さが3n+11. 再帰的factorialはそれぞれ,34n-16, 8n+3となった. 末尾再帰の最適化がないと末尾再帰的に書いても最…

SICP 問題 5.27

5.26と同じことを再帰的階乗計算で. ;;; EC-Eval input: (define (factorial-recur n) (if (= n 1) 1 (* (factorial-recur (- n 1)) n))) (total-pushes = 3 maximum-depth = 3) ;;; EC-Eval value: ok ;;; EC-Eval input: (factorial-recur 1) (total-push…

SICP 問題 5.26

監視つきスタックを使い,評価器の末尾再帰的特性を検討する. ;;; EC-Eval input: (define (factorial n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1)) (total-pushes = 3 maximum-d…

SICP 問題 5.25

4.2節の遅延評価器に基づいた正規順序の評価が使えるようにする. ;;; 5.2 で実装したシミュレータ.トレース機能追加済み. ;;; 初めてassignするレジスタを登録していくタイプ (load "./register-machine-simulator.scm") ;;; 4.1で実装した評価器 (load "…

SICP 5.4.4 積極制御評価器

;;; 5.2 で実装したシミュレータ.トレース機能追加済み. ;;; 事前に登録したレジスタを使用するのではなく,初めてassignするレジスタを登録していく(問題5.13). (load "./register-machine-simulator.scm") ;;; 4.1で実装した評価器 (load "./eval.scm") …

SICP 問題 5.24

condを派生式ではなく構文として実装する. ;; unevがcondの本体を保存.expはevalされる. ev-cond (assing unev (op cond-clauses) (reg exp)) ;((p1 e1) (p2 e2) ...)の形にする. (save continue) ;cond後の継続をsave (save env) ;現在の環境をsave (sa…

SICP 問題 5.23

レジスタマシン上に実装した評価器でcondとletを実装する. cond->ifのような構文変換器が機械演算として仮定してよいので,let->lambdaも使用する. eval-dispatch (test (op self-evaluating?) (reg exp)) (branch (label ev-self-eval)) (test (op variab…

SICP 問題 5.22

appendとappend!をレジスタマシン上に実装する. append (define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y)))) (define append (make-machine '(x y val continue) (list (list 'cons cons) (list 'null? null?) (list 'car car) (lis…

SICP 問題 5.21

schemeで書いた手続きのレジスタマシンを実装する. ;;; a ;;; 再帰的count-leaves (define (count-leaves tree) (cond ((null? tree) 0) ((not (pair? tree)) 1) (else (+ (count-leaves (car tree)) (coutn-leaves (cdr tree)))))) (define recur-count-le…

SICP 問題 5.20

(define x (cons 1 2)) (define y (list x y)) で作られたリスト構造の箱とポインタ表記,メモリーべ宇久田表現をかけ. freeポインタは最初p1にあるとする. 最後freeポインタはp4を指している. p1がxを,p2がyを表している.

SICP 問題 5.19

ラベルから何番目の命令の直前にブレークポイントを入れられるようにする. 実装した手続きのテストはREPLで試したが,テストの記述は省略. (define (set-breakpoint machine label n) ((machine 'set-breakpoint) label n)) (define (proceed-machine mach…

SICP 問題 5.18

レジスタの値をトレース出来るようにする ;;; registerがtraceを持ち,trace-onがメッセージパッシングされたらトレースする. (define (make-register name) (let ((contents '*unssaigned*) (trace (lambda (contents value) #f))) (define (dispatch mess…

SICP 問題 5.17

トレースログにラベルネームをつける. extract-labelsでlabelを見つけた時に('label labe-name)の形でinsts, labels両方に登録する. make-new-machineでtracing-labelを作り,そこに現在のラベルを登録する. *1の実行形式はそのまま(advanced-pc pc)でpc…

SICP 問題 5.16

命令トレースを出来るようにする. executeがtraceフラグを引数に取り,trace-onなら命令を印字し,trace-offなら#fを返す. (define (make-new-machine) (let ((pc (make-register 'pc)) (flag (make-register 'flag)) (stack (make-stack)) (the-instructi…

SICP 問題 5.15

命令数カウンタを追加する. (define (make-new-machine) (let ((pc (make-register 'pc)) (flag (make-register 'flag)) (stack (make-stack)) (the-instruction-sequence '()) (the-instruction-counter 0)) ;counterの追加 (let ((the-ops (list (list 'i…

SICP 問題 5.14

(define fact-machine (make-machine '(continue n val) (list (list '= =) (list '- -) (list '* *) (list 'print print)) '(controller (assign continue (label fact-done)) fact-loop (test (op =) (reg n) (const 1)) (branch (label base-case)) (save…

SICP 問題 5.13

make-machineでレジスタのリストを登録するのではなく, 命令の中で初めてassignされるときにレジスタを登録するように変更する. make-machineとmake-new-machineの変更だけですむ. ;;; register-namesを削除 (define (make-machine ops controller-text) …

SICP 問題 5.12

シミュレータのメッセージパッシングインターフェースを拡張し,以下の情報にアクセスできるようにする. ・命令の型で,格納されたすべての異なる命令のリスト ・エントリポイントの保持に使ったレジスタのリスト ・save, restoreされる異なるレジスタのリ…

SICP 問題 5.11-c

各レジスタがスタックを持つようにしてpopやpushはそのスタックを使用するように修正する. ;; make-registerがstackを持つ (define (make-register name) (let ((contents '*unassaigned*) (stack (make-stack))) ;;(make-stack) (define (dispatch message…

SICP 問題 5.11-b

;;; stackに退避するときにレジスタを指定しておき,そのレジスタにresotre出来るように修正する. (define (make-restore inst machine stack pc) (let ((reg (get-register machine (stack-inst-reg-name inst)))) (lambda () (let ((val (pop stack))) ;;…

SICP 問題 5.11-a

図5.12のfibonacci計算から1命令除去する. ;;; ex5.06で変更したこれを使う. (controller (assign continue (label fib-done)) fib-loop (test (op <) (reg n) (const 2)) (branch (label immediate-answer)) (save continue) (assign continue (label aft…

SICP 問題 5.10

新しく構文を追加する. 簡単にincrementとdecrementで. (define (make-execution-procedure inst labels machine pc flag stack ops) (cond ((eq? (car inst) 'assign) (make-assign inst machine labels ops pc)) ((eq? (car inst) 'test) (make-test ins…

SICP 問題 5.09

;; 演算はレジスタと定数にだけ使えるという条件を強要する. (define (make-operation-exp exp machine labels operations) (let ((op (lookup-prim (operation-exp-op exp) operations)) (aprocs (map (lambda (e) (if (label-exp? e) (error "Operation c…

SICP 問題 5.08

start (goto (label here)) here (assign a (const 3)) (goto (label there)) here (assign a (const 4)) (goto (label there)) there この時thereに達した時のaの値は何かという問題. (define (extract-labels text receive) (if (null? text) (receive '(…

SICP 問題 5.07

;; シミュレータを使い問題5.04で設計した計算機をテストせよ ;; 再帰的べき乗 (define factorial-recur-machine (make-machine '(b n val continue) (list (list '* *) (list '- -) (list '= =)) '((assign continue (label expt-done)) expt-loop (test (o…

SICP 問題 5.06

Fibonacci計算機の余分なsaveとrestoreを取り除く afterfib-n-1 (restore n) (restore continue) ;ここでcontinueをrestoreしているのに (assign n (op -) (reg n) (const 2)) (save continue) ;ここでそのままcontinueをsaveして (assign continue (label a…