(wat-aro)

無職から有職者にランクアップしました

SICP 問題 5.34

反復的階乗手続きをコンパイルし,再帰版との本質的な違いを示せ. 反復的階乗手続きの内容を説明する. (compile '(define (factorial n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1…

SICP 問題 5.33

以下の2つの翻訳結果を比較してその相違を説明する. (compile '(define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n))) 'val 'next) (compile '(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))))) 'val 'next) 一つ目を出力して…

SICP 問題 5.32

a: 演算子が記号である場合の組み合わせの式を別のクラスと認識し,そういう式を最適化する. operatorがvariableであればenvをsaveしない. ev-application (save continue) (assign unev (op operands) (reg exp)) (assign exp (op operator) (reg exp)) (…

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…

SICP 問題 5.05

階乗とFibonacci計算機を机上シミュレート. ;; 再帰的な階乗計算を机上シミュレートする. (controller (assign continue (label fact-done)) fact-loop (test (op =) (reg n) (const 1)) (branch (label base-case)) ;; nと continue を退避し再帰呼び出し…

SICP 問題 5.04

;; a 再帰的べき乗 (define (expt b n) (if (= n 0) 1 (* b (expt b (- n 1))))) (controller (assign continue (label expt-done)) expt-loop (test (op =) (reg n) (const 0)) (branch (label base-case)) (save continue) (save n) (assign n (op -) (reg…

SICP 問題 5.03

1章でやったNewton法で求めるsqrt手続き. これをデータパス図で描き,レジスタ計算機言語で定義する. (define (sqrt n) (sqrt-iter 1.0 x)) (define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) (define (i…

SICP 問題 5.02

5.01の反復的な階乗計算機をレジスト計算機言語使って記述する. (controller factorial (assign n (op read)) (assign product (const 1)) (assign counter (const 1)) test-b (test (op >) (reg counter) (reg n)) (branch (label factorial-done)) (assig…

SICP 問題 5.01

SICP 問題 4.77

簡略化して. (and (not A) B C)を(and B C (not A))に並び替えてからqevalしていく. 入れ子になっていた場合もqevalでまたcojoinに送られるので対処出来る. ただ問題文通りだと,必要な変数を満たす表明が現れたらすぐにnotを実行しなければいけないが,…

SICP 問題 4.76

本文中のandはひとつ目の質問を満たす表明に対して次の質問を満たす表明をデータベースから探してくる. それを2つの質問をそれぞれ満たすストリームをまず作り, 矛盾がないようにそれらを組み合わせるconjoin特殊形式を実装する. (define (conjoin conju…

SICP 問題 4.75

指定した質問を満足する項目がデータベースに一つしかないときに成功する特殊形式uniqueの実装. ;; streamの個数を調べる. (define (stream-length s) (let iter ((stream s) (count 0)) (if (stream-null? stream) count (iter (stream-cdr stream) (+ co…

SICP 問題 4.74

;; negate, lisp-value, singleton-streamはflatten-streamを変更して直列にしても問題ないのではという問題 ;; 元のflatten-stream (define (flatten-stream stream) (if (stream-null? stream) the-empty-stream (interleave-delayed (stream-car stream) …

SICP 問題 4.73

flatten-streamが明示的にdelayを使うのはなぜか. flatten-streamはストリームのストリームを引数にとる. 4.71と同じく引数のストリームの中に無限ストリームがあると評価が終わらずになにも印字されないため.

SICP 問題 4.72

stream-appendだと最初のストリームが無限ストリームだった場合に次のストリームが評価されなくなる. なのでinterleaveにして交互に先頭の要素を評価することで,どちらかもしくは両方が無限ストリームの時に対応できるようにする.

SICP 問題 4.71

;; 本文中のsimple-query (define (simple-query query-pattern frame-stream) (stream-flatmap (lambda (frame) (stream-append-delayed (find-assertions query-pattern frame) (delay (apply-rules query-pattern frame)))) frame-stream)) ;; 本文中のdi…

SICP 4.4.4 質問システムの実装

なかなか処理の流れがわからなかったのでコメントを多めにつけてみた. ;; 駆動ループ (define input-prompt ";;; Query input:") (define output-prompt ";;; Query result:") (define (prompt-for-input string) (newline) (newline) (display string) (ne…

継続を使ってフィボナッチ数列を求める

call/ccの使い方はよくわかってないので自分で継続を渡します. (define (fib n) (fib/cc n (lambda (a b) (+ a b)))) (define (fib/cc n func) (cond ((= n 0) (func 0 0)) ((= n 1) (func 0 1)) (else (func (fib/cc (- n 1) func) (fib/cc (- n 2) func))…

SICP 4.4.4 extend-if-consistentのエラー

4.4.4の論理型プログラミングの実装を評価すると以下のエラーが出ます. gosh> *** ERROR: Compile Error: cannot find "var" in ("/usr/local/Cellar/gauche/0.9.4/share/gauche-0.9/site/lib" "/usr/local/Cellar/gauche/0.9.4/share/gauche-0.9/0.9.4/lib…

SICP 問題 4.70

本文中のadd-assertion!とadd-rules!のletの目的は何か. 問題文のadd-assertion!ではダメな理由を述べよ. ;; 本文中のadd-assertion! (define (add-assertion! assertion) (store-assertion-in-index assertion) (let ((old-assertions THE-ASSERTIONS)) (…

SICP 問題 4.69

((great great grandson) adam Irad)のような質問ができるようにする. (rule (greatson-end ?x) (append-to-form ?u (grandson) ?x)) (rule ((grandson) ?x) (grandson ?x)) (rule ((great . ?rel) ?x ?y) (and (greatson-end ?rel) (son-of ?x ?z) (?rel ?z…