SICP
やっと5章です.もう少しで終わりなのです.ついに! 5.1,5.4,5.5はノートに書いた. 5.2 ;; exercise 5.2 (controller init (assign p (const 1)) (assign c (const 1)) test-c (test (op >) (reg c) (const n)) (branch (label init-done)) (assign t (op…
パスします. 4.76は少し取り組んでみて、以下のような感じになるのかぁという感じでですが、merge-frameの実装がいまいち浮かばず... (define (conjoin2 conjoins frame-stream) (if (empty-conjunction? conjoins) frame-stream (let ((join1 (qeval (first…
4章もあとちょっと ;; exercise 4.75 (define (uniquely-asserted operands frame-stream) (stream-flatmap (lambda (frame) (let ((result (qeval (uniquely-query operands) (singleton-stream frame)))) (cond ((stream-null? result) the-empty-stream) …
;; exercise 4.74 (define (simple-stream-flatmap proc stream) (simple-flatten (stream-map proc stream))) (define (simple-flatten stream) (stream-map stream-car (stream-filter pair? stream)))
4.72 disjoinと,stream-flatmapがストリームを差込にするのは,s1が無限ストリームになるとき,stream-map-delayedではおかしくなるため. 例は, 少し考えたけど思い浮かばず... 4.73 無限ループ
正直言ってここらへんの問題はつまらない... delay演算を陽に使用しない場合とする場合での違いが一番わかるのは,質問が無限ループになるとき. つまり,P.276のような場合に振る舞いがおかしくなる. "無限ループ"なのでもともと正しいものではない (asser…
他の評価器の実装を張っている人はちらほらいるけれど,質問システムは見た限りいないので,一応張っておこう. ちょっと長いけれど. (load "./stream.scm") (load "./evaluator.scm") (define true #t) (define false #f) (define user-initial-environmen…
4.67, 4.69はパスします。 exercise 4.64 ;; exercise 4.64 (assert! (rule (outranked-by2 ?staff-person ?boss) (or (supervisor ?staff-person ?boss) (and (outranked-by2 ?middle-manager ?boss) (supervisor ?staff-person ?middle-manager))))) (outr…
なんとかquery評価器を実装した. そのままの実装では動かないので,注意. 変更点は (define false #f) (define true #t)を追加 self-evaluating? に ((boolean? exp) #t) を追加 (define extend-in-underlying-scheme extend)を追加して,もともとのextend…
4.4論理型プログラミングに入った. いつもながら、実装は最後の節.しかし,最後の節はなかなか面倒そうので,本の進行通りに進めていく. 答えが確かめられないのが問題. ;; exercise4.55 ;; a (supervisor ?x (Bitdiddle Ben)) ;; b (job ?x (accounting…
ちょっと戻ってやってみた. 今回は条件を判定する軸が2つあるので,意外とやっかいだった. (define (who-is-Lorna-father) (define daughter car) (define yacht cdr) (let ((Barnacle (cons 'Melissa 'Gabrielle)) (Moore (cons 'Ann 'Lorna)) (Hall (con…
最後の問題は簡単だった. (amb)は何を表しているかというと, もちろん (fail)である.なので, requireは以下のようになる. 大切なのは, failではなく,(fail)として,そこで,失敗継続を実行すること. ;; exercise4.54 (define (require? exp) (tagged-li…
4.51 ;;;; exercise4.51 ;;parmanent-set! (define (permanent-assignment? exp) (tagged-list? exp 'permanent-set!)) (define (analyze-permanent-assignment exp) (let ((var (assignment-variable exp)) (vproc (analyze (assignment-value exp)))) (lam…
問題4.50 分岐を左から右ではなく,ランダムに探す他はambと同じである,新しい特殊形式rambを実装せよ ここで,そもそも分岐の候補はどこで作られているかが問題になる. いままでいまいち動きがわからなかったけど,少しわかったので,自分用にメモ.簡単の…
4.38はパス.めんどー. 4.39 影響しない(はず) 4.40 backerたちがそもそもすまないところは,始めからリストに入れない. ;exercise4.40 (define (multiple-dwelling) (let ((cooper (amb 2 3 4 5)) (miller (amb 1 2 3 4 5))) (require (not (= cooper mil…
非決定性計算に入る. 基本的には深さ優先探索を考えればいいみたい. 計算機プログラムの構造と解釈P.248より, 非決定性プログラムの長所は,探索の仕方の細部を隠すことができ,われわれのプログラムをより高い抽象レベルで表現できることである. 参考 h…
carも遅延されるので,定義されていないものが,carにあっても問題ない. (cons x (* x x)) こういうのが問題なく使える. 3章のcons-streamでは,carは評価されるので, (cons-stream 1 x) はできても, (cons-stream x 1) はエラーとなる.利用方法..無限…
これはおもしろい問題. しかし,問題の訳文がひどい.これは原書を読んだほうがわかりやすい.序文だけ載せる. Exercise 4.30. Cy D. Fect, a reformed C programmer, is worried that some side effects may never take place, because the lazy evaluato…
時間に差が出るのは,再帰(反復的プロセス)を使うとき. 前の計算結果を使えないため,もう一度先頭から計算する. メモ化の必要性を実感した演習問題 ;with memo ;;; L-Eval input: (square (id 10)) ;;; L-Eval value: 100 ;;; L-Eval input: count ;;; L-…
”演習問題”ではなく”問題”であることに気がついた. 最後まで”演習問題”で行くwさてさて,4.2に入りました.遅延評価です. ;exercise4.27 ;with Lazy ;;; L-Eval input: (define count 0) ;;; L-Eval value: ok ;;; L-Eval input: (define (id x) (set! cou…
今回は簡単だった. しかし,こんな考え方もあるのかーと思ってしまった. ;;a ((lambda (n) ((lambda (fact) (fact fact n)) (lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1))))))) 10) ((lambda (n) ((lambda (fibonacci) (fibonacci fibonacci n)) (la…
a 式の変換は以下のようにする. (letrec ((fact (lambda (n) (if (= n 1) 1 (* n (fact (- n 1))))))) (fact 10)) (let ((fact '*unassigned)) (set! fact (lambda (n) (if (= n 1) 1 (* n (fact (- n 1)))))) (fact 10)) これを実現するために, (define (…
Ben:逐次規則版 もともとの内部定義を掃き出さない評価器を使えばいい ;;; M-Eval input: (let ((a 1)) (define (f x) (define b (+ a x)) (define a 5) (+ a b)) (f 10)) ;;; M-Eval value: 16 Alyssa ;;; M-Eval input: (let ((a 1)) (define (f x) (defin…
変換前 (define (solve f y0 dt) (define y (integral (delay dy) y0 dt)) (define dy (stream-map f y)) y) 変換後 (define (solve f y0 dt) (let ((y '*unassigned*) (dt '*unassigned)) (let ((a (integral (delay dy) y0 dt)) (b (stream-map f y))) (se…
とりあえず張る. (define (hoge1 x) (define a 1) (+ x a)) 変換する場合 ;;; M-Eval input: #?="./evaluater.scm":348:(car body) #?- (define a 1) #?=body #?- ((let ((a '*unassigned)) (set! a 1) (+ x a))) ;;; M-Eval value: ok ;;; M-Eval input: #…
やっと4.1の終わりが見えてきた. analyze付きがなかなか実行できずはまった. 原因はscan-ouf-defines用にmake-procedureを変えていたのを忘れていて,そのままanalyze付きの評価器を実行しようとしたため.今日はもうお終い. 解答は [(let? exp) (analyze…
最近の演習問題は難しくてなえるw 全然進まない!今回も1時間以上掛かってしまった. なんとか読める範囲のプログラムにはなったかなぁ... 追記(20090626) バグがあったので修正した. definition?の位置がおかしかった. 評価器には入れないで,単純に式変形…
;;exercise4.13 ;;今見てる環境の変数のみを削除 ;;内部で使おうとして上の環境の変数も削除されては大変 (define (unbind! variable env) (let ((frame (first-frame env))) (define (scan-and-delete variables values) (cond [(null? variables) (error "…
;;exercise4.12 ;;解答確認 (define (env-loop variable env emptyproc hitproc err) (define (scan variables values) (cond [(null? variables) (emptyproc env)] [(eq? variable (car variables) (hitproc values))] [else (scan (cdr variables) (cdr va…
map, assoc, cut を使ってしまった.完全に反則だな. 時間があれば書き直す.でもassocは演習問題4.5の中で,もともと使っているぞ? と自分を慰める.しかもテストをしていないので,たぶん間違えがある. ;;exercise4.11 (define (make-frame variables v…