読者です 読者をやめる 読者になる 読者になる

(wat-aro)

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

SICP

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…

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…

SICP 問題 4.68

(define (my-reverse lst) (let iter ((lst lst) (result '())) (if (null? lst) result (iter (cdr lst) (cons (car lst) result))))) (rule (append-to-form () ?y ?y)) (rule (append-to-form (?u . ?v) ?y (?u . ?z)) (append-to-form ?v ?y ?z)) (rever…

SICP 問題 4.67

フレームに質問の履歴をつけていく. 入力ストリームと出力ストリームの間で同じ質問(4.64でいう(outranked-by ?staff-person Boss)のような)があれば ループしていると判断して処理を中止するようにする.

SICP 問題 4.66

重複したものをアキュムレートしてしまうのでこのままでは使えないことがわかった. 重複を削除するように変更すればよい.

SICP 問題 4.65

(rule (wheel ?person) (and (supervisor ?middle-manager ?person) (supervisor ?x ?middle-manager))) wheelはまず?personにデータベースの先頭から人を束縛して,and以下を満たすかを試していく. なので Ben -> Oliver -> X alyssa -> Ben -> Oliver Fec…

SICP 問題 4.64

(rule (outranked-by ?staff-person ?boss) (or (supervisor ?staff-person ?boss) (and (outranked-by ?middle-manager ?boss) (supervisor ?staff-person ?middle-manager)))) (outranked-by (Bitdiddle Ben) ?who) まずoutranked-byの?staff-personにBitd…

SICP 問題 4.63

SはGの孫であるという規則の形式化 (rule (?son son-of ?dad) (or (son ?dad ?son) (and (wife ?dad ?mam) (son ?mam ?son)))) (rule (?grandson grandson-of ?granddad) (and (?parent son-of ?grandson) (?grandson son-of ?parent)))

SICP 問題 4.62

;; last-pairに該当するルールを作る (rule (last-pair (?x) (?x))) (rule (last-pair? (?x . ?y) ?z) (last-pair? ?y ?z)) ;; 質問 (last-pair (3) (?x)) ;; ひとつ目の質問にマッチして ;; ?x=3となるので (last-pair (3) (3)) ;; と出力されるはず. ;; …

SICP 問題 4.61

;; 先頭の2つの隣接関係 (rule (?x next-to ?y in (?x ?y . ?u))) ;; リストのcdrの隣接関係 ;; (1 2 3 4 5)だとvが1,zが(2 3 4 5).2行目で,zに対してもnext-toをやると読める. (rule (?x next-to ?y in (?v . ?z)) (?x next-to ?y in ?z)) ;; 質問 (?x …

SICP 問題 4.60

最初の質問をすると近くに住む人の対になるので2つずつ表示される. (lives-near ?person-1 ?person2) ;; 例 (lives-near (Hacker Alyssa P) (Fect Cy D)) (lives-near (Fect Cy D) (Hacker Alyssa P)) これを防ぐために各人にIDを割り振る. ;; 例 (id (Bi…

SICP 問題 4.59

(meeting accounting (Monday 9am)) (meeting administration (Monday 10am)) (meeting computer (Wednesday 3pm)) (meeting administration (Friday 1pm)) (meeting whole-company (Wednesday 4pm)) ;; a 金曜の朝に今日ある会議をすべて質問する (meeting …

SICP 問題 4.58

ある人が,自分の勤める部署に勤める監督者がいない場合,その人をbig shotであるとする規則を定義する (rule (big-shot ?person) (and (job ?person (?division . rest)) (supervisor ?person ?boss) (job ?boss (?boss-division . rest2)) (not (same ?div…

SICP 問題 4.57

;; jiroの仕事をtaroができるかどうか (rule (replacible ?person1 ?person2) (and (or (and (job ?person2 ?job2) (job ?person1 ?job2)) ;person2とperosn1の仕事が同じ (and (job ?person1 ?job1) (can-do-job ?job1 ?job2))) ;person1はperson2の仕事job…

SICP 問題 4.56

;; 合成質問を形成する ;; a Ben Bitdiddleが監督している人すべての名前とその住所 (and (supervisor ?x (Bitdiddle Ben)) (address ?x ?y)) ;; b Ben Bitdiddleより給料が少ない人と,Ben Bitdiddleの給料 (and (salary (Bitdiddle Ben) ?Ben-amount) (sal…

SICP 問題 4.55

データベースへの単純質問を示せ ;; a Ben Bitiddleに監督されているすべての人々 (supervisor ?x (Bitdiddle Ben)) ;; b 経理部門のすべての人々の名前と担当 (job ?x (accounting . ?type)) ;; c Slumervilleに住む人すべての名前と住所 (address ?x (Slum…

SICP 問題 4.54

requireを特殊形式で実装する. (define (require? exp) (tagged-list? exp 'require)) (define (require-predicate exp) (cadr exp)) (define (analyze exp) (cond ((self-evaluating? exp) (analyze-self-evaluating exp)) ((quoted? exp) (analyze-quoted…

SICP 問題 4.53

permanent-set!でpairsに成功する組み合わせを束縛するが, (amb)で必ず失敗するので全ての成功する組み合わせをpairsに束縛する. 失敗継続が呼ばれ,if-failの第二引数のpairsが評価される. この時permanent-set!で束縛されているのでバックトラックで戻…

SICP 問題 4.52

利用者が失敗を捉えることができるif-failを実装する. (define (analyze exp) (cond ((self-evaluating? exp) (analyze-self-evaluating exp)) ((quoted? exp) (analyze-quoted exp)) ((variable? exp) (analyze-variable exp)) ((assignment? exp) (analyz…

SICP 問題 4.51

バックトラックで戻らないpermanent-set!の実装 ;; permanent-set! (define (analyze-permanent-assignment exp) (let ((var (assignment-variable exp)) (vproc (analyze (assignment-value exp)))) (lambda (env succeed fail) (vproc env (lambda (val fa…

SICP 問題 4.50

ランダムな順に探すrambを実装する. (use srfi-27) (define (random-car lst) (list-ref lst (random-integer (length lst)))) (define (rember item lst) (cond ((null? lst) '()) ((eq? (car lst) item) (cdr lst)) (else (cons (car lst) (rember item (…

SICP 4.3 amb評価器

(define true #t) (define false #f) ;; eval (define (ambeval exp env succeed fail) ((analyze exp) env succeed fail)) (define (analyze exp) (cond ((self-evaluating? exp) (analyze-self-evaluating exp)) ((quoted? exp) (analyze-quoted exp)) ((v…

SICP 問題 4.49

自然言語の構文解析用プログラムを少し改造するだけで文章の生成ができる. (define (an-element-of items) (require (not (null? items))) (amb (car items) (amb (cdr items)))) (define (parse-word word-list) (list (car word-list) (an-element-of (cd…

SICP 問題 4.48

adjectiveのみ追加する. ;; 冠詞の解析をparse-article-phraseにしてそこでmaybe-extendに進めばadjectiveも解析されるようにする. (define (parse-simple-noun-phrase) (list 'simple-noun-phrase (parse-article-phrase) (parse-word nouns))) (define (…

SICP 問題 4.47

(define (parse-verb-phrase) (amb (parse-word verbs) (list 'verb-phrase (parse-verb-phrase) (parse-prepositional-phrase)))) (parse '(the student with the cat sleeps in the class))これを例に考える. verbが問題なのでsleeps in the classだけに…

SICP 問題 4.46

構文解析器が右から左に非演算子を評価する時 perse-noun-phrase中の (amb noun-phrase (maybe-extend (list 'noun-phrase noun-phrase (parse-prepositional-phrase)))) で,maybe-extendが先に評価されてしまう. すると,実際に名詞が先にきた場合はmaybe…

SICP 問題 4.45

The professor lectures to the student in the class with the cat. これの5通りの構文解析結果を示す. まずはprofessor に in the class とwith the cat が掛かっている場合. 次はprofessorにwith the cat , student にin the classがかかっている場合…

SICP 問題 4.44

eight-queenをamb評価器を用いて解く. ただし,まだamb評価器は実装していないのでコードだけ. (define (eight-queen) (define (cross? a b) (= (/ (/ (car a) (car b)) (abs (- (cdr a) (cdr b)))) 1)) (let ((chess (iota 8 1))) (let ((one (cons 1 (am…

SICP 問題 4.43

まずは素直に問題文に出てくる通りに書いてみる. (define (kansas-state-enginner) (let ((moore (cons (amb 'mary 'gabrielle 'lorna 'rosalind 'melissa) (amb 'mary 'gabrielle 'lorna 'rosalind 'melissa))) (downing (cons (amb 'mary 'gabrielle 'lor…

SICP 問題 4.42

どちらかが正しいってどうやればいいのか思いつけず, ここを見たらヒントがあったのでその通り排他的論理和を作って解きました. SICP 第4章 Exercise 難易度リスト ( 4.1 ~ 4.79 ) | きのこる庭 (define (xor x y) (or (and x (not y)) (and (not x) y)))…

SICP 問題 4.41

多住居手続きをschemeで実装. (use util.combinations) (use srfi-1) (define (multiple-dwelling) (filter (lambda (x) (let ((baker (first x)) (cooper (second x)) (fletcher (third x)) (miller (fourth x)) (smith (fifth x))) (and (not (= baker 5)…

SICP 問題 4.40

人の階への割り当ての組みは,相異なるという要求の前では55通りある. 要求の後では5!通りになる. ambで生成してすぐにテストすることで効率的な手続き (define (multiple-dwelling) (let ((baker (amb 1 2 3 4 5))) (require (not (= baker 5))) (let ((c…

SICP 問題 4.39

制限の順番は解には影響しないが,その時間には影響する. 失敗が多い制限ほど先にテストするほうが実行速度は速くなる. ;; 本来のmultiple-dwelling (define (multiple-dwelling) (let ((baker (amb 1 2 3 4 5)) (cooper (amb 1 2 3 4 5)) (fletcher (amb …