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

(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だけに…

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

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

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…

まずは素直に問題文に出てくる通りに書いてみる． (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章 Exercise 難易度リスト ( 4.1 ～ 4.79 ) | きのこる庭 (define (xor x y) (or (and x (not y)) (and (not x) y)))…

多住居手続きを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)…

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

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

これを手で解けとな．．． B≠5 C≠1 F≠1 F≠5 C C≠5 |F-C| ≠ 1 答えは5通り． 計算機プログラムの構造と解釈 第2版作者: ハロルドエイブルソン,ジュリーサスマン,ジェラルド・ジェイサスマン,Harold Abelson,Julie Sussman,Gerald Jay Sussman,和田英一出版社/…

(define (a-pythagorean-triple-between low high) (let ((i (an-integer-between low high)) (hsq (* high high))) (let ((j (an-integer-between i high))) (let ((ksq (+ (* i i) (* j j)))) (require (>= hsq ksq)) (let ((k (sqrt ksq))) (require (int…

(define (a-pythagorean-triple-between low high) (let ((i (an-integer-between low high))) (let ((j (an-integer-between i high))) (let ((k (an-integer-between j high))) (require (= (+ (* i i) (* j j)) (* k k))) (list i j k))))) ;; an-integer…

二つの与えられた限界の間の整数を返す手続き (define (an-integer-between low high) (require (<= low high)) (amb low (an-integer-between (+ low 1) high))) 計算機プログラムの構造と解釈 第2版作者: ハロルドエイブルソン,ジュリーサスマン,ジェラル…

遅延対とリストを正当に印字できるようにする． consへのタグづけがどうしてもうまくいかなくてここを参考にしました． SICP Exercise 4.34 | Weiqun Zhang's Blog 前回からの変更箇所のみ (define (eval exp env) (cond ((self-evaluating? exp) exp) ((var…

遅延リストの実装に合わせて，quoteを遅延リストに対応させる． (car '(a b c))で正しくaが表示できるようにする． make-lambdaの(make-quote (car obj))のところ，始め(car obj)だけにしていたら， 数字ではうまくいくのに'(a b c)だとunbound variable: a…

遅延度の高い遅延リストではcar部も遅延されているので未定義の変数を使って構成するできる． ;;; M-Eval input: (define my-stream (cons x y)) ;;; M-Eval value: ok ;;; M-Eval input: my-stream ;;; M-Eval value: (compound-procedure (m) ((m x y)) <procedure-env>) </procedure-env>…

手続きは引数を全て評価してoperatorに渡す． 特殊形式は引数を全て評価するとは限らない． ここではdefineについて見てみる． defineは第１引数は評価せず，第２引数を評価した値を第１引数に束縛する． (define x (+ 1 2)) (+ 1 2) 3 (define x 3) x 3 次…

(define (f a (b lazy) c (d lazy-memo)) ...) といった形で部分的に遅延評価やメモ化する遅延評価を実装する． 元となるのは4.30までで作っていた遅延評価器． まず変更した部分を書く． ;; メモ化する評価器 (define (force-it obj) (cond ((thunk? obj) (…

並びの中の式は最後まで評価されないのではないかというCy D. Fectの心配に答える． a ;; 元のeval-sequence (define (eval-sequence exps env) (cond ((last-exp? exps) (eval (first-exp exps) env)) (else (eval (first-exp exps) env) (eval-sequence (r…

前回のSICP問題4.29で遅延評価する評価器でメモ化しない場合に，する場合と比べてはるかに遅くなるプログラムの例としてフィボナッチを書きました． ただ，あまりに差が大きくてなぜそうなるのかがわからなかったので考えてみました． 評価器は最後に載せて…

メモ化しないとはるかに遅くなるプログラムの例として 再帰でフィボナッチ数列の第n項を求める手続きを定義する． (define (fib n) (let iter ((a 0) (b 1) (count n)) (if (= count 0) a (iter b (+ a b) (- count 1))))) ;; メモ化するforce-it (define (f…

引数に手続きをとる手続きを考える． (define (foo bar) (bar 'a)) 引数はすべてthunkなので(bar 'a)でbarをevalしても手続きとならない． applyでoperatorをactual-valueを使わないと手続きを引数に取る場合に困る．

遅延評価 ;;; M-Eval input: (define count 0) ;;; M-Eval value: ok ;;; M-Eval input: (define (id x) (set! count (+ count 1)) x) ;;; M-Eval value: ok ;;; M-Eval input: (define w (id (id 10))) ;;; M-Eval value: ok ;;; M-Eval input: count ;;; M…

unlessを特殊形式で定義する． (define (analyze exp) (cond ((self-evaluating? exp) (analyze-self-evaluating exp)) ((quoted? exp) (analyze-quoted exp)) ((variable? exp) (analyze-variable exp)) ((assignment? exp) (analyze-assignment exp)) ((de…

;; 作用的順序のschemeで本文中のunlessを使用してfactorialを定義した時， ``(factorial 5)``を評価しようとすると何が起きるか. (define (unless condition usual-value exceptional-value) (if condition exceptional-value usual-value)) (define (facto…

driver-loopにtimeマクロをしかけて計測する． (define (driver-loop) (prompt-for-input input-prompt) (let ((input (read))) (let ((output (time (eval input the-global-environment)))) (announce-output output-prompt) (user-print output))) (drive…

本文中のanalyze-sequenceと問題文のanalyze-sequenceの比較． リーダーマクロを使って実行する． 本文のanalyze-sequence (define (analyze-sequence exps) (define (sequentially proc1 proc2) #?=(lambda (env) (proc1 env) (proc2 env))) (define (loop …

letを使えるようにする． (define (analyze exp) (cond ((self-evaluating? exp) (analyze-self-evaluating exp)) ((quoted? exp) (analyze-quoted exp)) ((variable? exp) (analyze-variable exp)) ((assignment? exp) (analyze-assignment exp)) ((definit…

;; a 以下の式が階乗を計算すること確かめた後，フィボナッチ数を計算する手続きを作る． ((lambda (n) ((lambda (fact) (fact fact n)) (lambda (ft k) (if (= k 1) 1 (* k (ft ft(- k 1))))))) 10) gosh> ((lambda (n) ((lambda (fact) (fact fact n)) (la…