(wat-aro)

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

SICP

プログラミング初心者がSICP(計算機プログラムの構造と解釈)を読んでみた

読む前の状態と動機 読み始めた時点でプログラミング歴約1年 もうひとつのscheme入門でプログラミングに入門するも,高階関数で挫折. Ruby本二冊,Rails Tutorialを二周. 他読み始めたけど途中で飽きた本が何冊か. 仕事(非IT)が忙しく,プログラミング…

SICP 問題 5.50

4.1節の超循環評価器を5.5で作った翻訳系でコンパイルする. 問題5.50 – SICP(計算機プログラムの構造と解釈)その302 : Serendip - Webデザイン・プログラミング http://himoiku.cocolog-nifty.com/blog/2008/07/sicp550_f385.html ここを参考にしました.…

SICP 問題 5.49

compileとassembleを機械計算として持ち,REPLを行うレジスタ計算機を設計する. はじめ,assembleを命令列の上でやる方法がわからずに,compile-and-assembleという手続きを作り, それを機械演算として登録してRCEPLを実装したが, 問題5.49 – SICP(計算…

SICP 問題 5.48

ECEVALのrepl上でコンパイル出来るようにする. これで動くかなって思ったら動いた. ただトレースした命令列を見ると, apply-dispatchからprimitive-procedureにジャンプせずに先頭に戻っている. なぜそうなるのかわからない. ;; 環境を拡張してprimitiv…

SICP 問題 5.47

コンパイルした手続きから積極制御評価器で定義した手続きを使えるようにする. (define (compile-procedure-call target linkage) (let ((primitive-branch (make-label 'primitive-branch)) (compiled-branch (make-label 'compiled-branch)) (compound-br…

SICP 問題 5.46

5.45と同様に今度はフィボナッチ数列の計算でそれぞれ比べる. gosh> (define fib ;;一回目以外は省略 (make-machine (list (list '< <) (list '- -) (list '+ +)) '(controller (assign continue (label fib-done)) fib-loop (test (op <) (reg n) (const 2…

SICP 問題 5.45

コンパイルした階乗計算,積極制御評価器の階乗計算,特殊目的計算機のプッシュ数,最大スタック深さを調べて比較する. まずはコンパイルしたものから gosh> (compile-and-go '(define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n)))) (total-pu…

SICP 問題 5.44

基本手続きの名前を含む式の正しいコードを翻訳するため,翻訳時環境を調べるようにする. (cond ((self-evaluating? exp) (compile-self-evaluating exp target linkage)) ((variable? exp) (compile-variable exp target linkage ct-env)) ((quoted? exp) …

SICP 問題 5.43

内部定義を吐き出してコンパイルする. まず4.16で作ったscan-out-definesがこれ. (define (scan-out-defines body) (define (split-defines proc-body defines non-defines) (cond ((null? proc-body) (cons (reverse defines) (reverse non-defines))) ((…

SICP 問題 5.42

compile-variableとcompile-assignmentを文面アドレスを使った検索に対応 (define (compile-variable exp target linkage ct-env) (let ((address (find-variable exp ct-env))) (end-with-linkage linkage (if (eq? address 'not-found) (make-instruction-…

SICP 問題 5.41

翻訳時環境に対する変数の文面アドレスを返す手続きfind-variableの実装 (define (find-variable var ct-env) (define (env-loop frame-address env) (define (scan variable-address frame) (cond ((null? frame) (env-loop (+ frame-address 1) (enclosing…

SICP 問題 5.40

翻訳時環境を維持し,compile-lambda-bodyで拡張するように変更する. (define (compile-lambda-body exp proc-entry ct-env) ;; ct-envを追加 (let ((formals (lambda-parameters exp))) (append-instruction-sequences (make-instruction-sequence '(env p…

SICP 問題 5.39

文面アドレスと実行時環境とり値を検索するlexical-address-lookupと 値を変更するlexical-address-set!を実装する. ;;; 文面アドレスを使って変数の値を探す (define (lexical-address-lookup lex-add r-env) (let ((frame (frame-values (list-ref r-env …

SICP 問題 5.38d

+と*について任意個の被演算子の式が使えるように拡張する. ここに書いた手続きを変更もしくは追加する. 3つ以上の引数の時はarg1に畳み込んで計算していく. (define (compile-open-code exp target linkage ct-env) (cond ((= (length exp) 3) (compile…

SICP 問題 5.38c

元のcompileによる出力と5.38abでcompile-open-codeを追加したコンパイラの出力を比べる. 命令列が約半分になっている. compile-open-codeを追加したコンパイラの出力 ((env) (val) ((assign val (op make-compiled-procedure) (label entry1) (reg env)) …

SICP 問題 5.38ab

+ - * = はopen-codeとして (reg val (op +) (reg arg1) (reg arg2)) の形で処理できるようにする. (define (open-code? exp) (memq (car exp) '(= * - +))) (define (compile exp target linkage) (cond ((self-evaluating? exp) (compile-self-evaluating…

SICP 5.5.5 翻訳系

schemeの式をレジスタマシンのシミュレータの命令列に翻訳するコード. 理解するためにコメントを出来るだけつけた (load "./eval.scm") ;;; make-branchのための手続き (define label-counter 0) (define (new-label-number) (set! label-counter (+ 1 labe…

SICP 問題 5.37

preservingを修正して常にsaveとrestoreをさせ,修正前と後を比較する. 修正前 (define (preserving regs seq1 seq2) (if (null? regs) (append-instruction-sequences seq1 seq2) (let ((first-reg (car regs))) ;first-regが (if (and (needs-register? s…

SICP 問題 5.36

本文の被演算子の適用順はoperandをreverseしてから連結していくので右から左になっている. これを左から右に変更する. ;;; 最初のreverseをなくす (define (construct-arglist operand-codes) (if (null? operand-codes) (make-instruction-sequence '() …

SICP 問題 5.35

本文の図5.18 の翻訳出力の例から翻訳前の式を導く. 答え (compile '(define (f x) (+ x (g (+ x 2)))) 'val 'next) 実行結果(整形済み) ((env) (val) ((assign val (op make-compiled-procedure) (label entry12) (reg env)) (goto (label after-lambda1…

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…