メモ化しないと、メモ化するよりはるかに遅く走ると思われるプログラムを示す問題。メモ化した場合としない場合の速度差が出るものと言えば、階乗かfibonacciかなぁ。 ということで問題4.24の時と同様にtimeマクロを組み込み、fibを定義して実行時間を見る …

また二週間ぶり。ｗevalはapplyに渡す前に演算子を評価するのに、演算子の値を強制するため、evalでなくactual-valueを使う。この強制の必要性を示す例をあげよ、という問題。パラメータで手続きを受け取る手続き f を考えてみる (define (f g) (g 10)) これ…

入力に対する応答内容を答える問題。 "← 応答"となっている部分が解答。 (define count 0) (define (id x) (set! count (+ count 1)) x) (define w (id (id 10))) ;;; L-Eval input: count ;;; L-Eval value: 1 ;; ← 応答 ;;; L-Eval input: w ;;; L-Eval va…

遅延評価を組み込んだ評価器のソース。 この節で使用する評価器は解析と評価を分離していない方を元に遅延評価を組み込む。 問題4.27のためメモ化したthunkの部分はコメントアウトしてある。 ;; 評価器実行用に超循環のapplyを定義する前に定義しておく (def…

unless の実装。unlessをifに変換するように実装する 追加する手続き (define (unless? exp) (tagged-list? exp 'unless)) (define (unless-predicate exp) (cadr exp)) (define (unless-consequent exp) (caddr exp)) (define (unless-alternative exp) (if…

手続きunlessの定義 (define (unless condition usual-value exceptional-value) (if condition exceptional-value usual-value)) 上記のunlessを使用して以下のようなfactorialを定義する (define (factorial n) (unless (= n 1) (* n (factorial (- n 1)))…

始めの超循環評価器とこの節での版の速度を比較する 以下の要領で time マクロを組み込みeval実行時間を計測する (define (driver-loop) (prompt-for-input input-prompt) (let ((input (read))) ;; time マクロを組み込む (let ((output (time (eval input …

一ヶ月ぶり。 二つの版の違いは既に本文および問題中に書かれている。 本文版の方は これらの実行手続きを組み合わせ、環境を引数としてとり、個々の実行手続きを環境を引数として順に呼び出す一個の実行手続きを作る という動作なのに対し、Alyssa版の方は …

式と環境をとるevalを分けた超循環評価器。 手続き analyze は式だけを取る。これは構文解析を実施し、解析された式を実行する 教科書の定義に加えてletを組み込む。 ;; 4.1.7 - 以降 ;; 評価器実行用に超循環のapplyを定義する前に定義しておく (define app…

再帰手続きをletrec(やdefineさえ)使わずに指定する。次の式は再帰的な階乗手続きを作用させ、10の階乗を計算する ((lambda (n) ((lambda (fact) (fact fact n)) (lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1))))))) 10) a. (式を評価することで)これが…

a. letrec式をlet式に変換し、導出された式として実装する (define (letrec? exp) (tagged-list? exp 'letrec)) (define (letrec-parameters exp) (cadr exp)) (define (letrec-body exp) (cddr exp)) (define (letrec->let exp) (let ((vars (map (lambda (…

式 (let ((a 1)) (define (f x) (define b (+ a x)) (define a 5) (+ a b)) (f 10)) を評価した時の望ましい結果について。MITのScheme実装についてだけど、脚注に答えが書いてあるような。 原理的にはEvaが正しいが、実装が困難な場合、正しくない答えを出…

3.5.4節のsolve手続き: (define (solve f y0 dt) (define y (integral (delay dy) y0 dt)) (define dy (stream-map f y)) y) を問題で示したように内部定義を掃き出した場合に動作するか?本文に示したように掃き出したら動作するか?を述べる。三章のストリー…

環境の図は省略。定義を逐次的に解釈する場合 (lambda <vars> (define u <e1>) (define v <e2>) <e3>) letを使い内部定義を掃き出した場合 (lambda <vars> (let ((u '*unassigned*) (v '*unassigned*)) (set! u <e1>) (set! v <e2>) <e3>)) これは更に (lambda <vars> ((lambda (u v) (set! u <e1>) (set! u <e2></e2></e1></vars></e3></e2></e1></vars></e3></e2></e1></vars>…

a. 値が*unassigned*ならエラーとするlookup-variable-value (define (lookup-variable-value var env) (define (env-loop env) (define (scan vars vals) (cond ((null? vars) (env-loop (enclosing-environment env))) ((eq? var (car vars)) (if (eq? (ca…

問題4.11でscan手続きを抽出しましたが、変数が見つからなかった時の戻り値をfalseにすると、環境を作成した時に束縛した変数falseが検索できないし、戻り値をnullにした場合は引数をcdrしていって再帰していくような手続きでは引数が見つからないという結果…

Turingの停止問題(Halting Theorem)です。 任意の手続きp が オブジェクトa で停止するかどうか判定する (halts? p a) がある。 オブジェクト a で停止する場合は真, 停止しない場合は偽を返す場合、これを使用して以下の手続きが定義できる。 (define (run-…

4.11 でやった各束縛が名前-値の対であるような束縛のリストで表現したフレームの定義のままだと、うまく評価器が動かなかったので、色々書き直しているうちに時間かかった。Eva Lu Ator の方法で実行した場合 (define (map f lst) (if (null? lst) '() (con…

束縛を除去するunbind!式の定義。 unbind!の実装は最初のフレームからだけ結合を除去する仕様とした。 これはdefineが最初のフレームに束縛を追加するのと対応づけるためである。 (define (unbind? exp) (tagged-list? exp 'unbind!)) (define (eval-unbind!…

set-variable-value!, define-variable!およびlookup-variable-valueから共通パターンを取り込んだ抽象の定義。 define-variable!と次の問題まで含めて考えて、手続きを渡せるようにしておく。 (define (scan var vars vals proc) (cond ((null? vars) #f) (…

各束縛が名前-値の対であるような束縛のリストで表現されたフレーム (define (make-frame variables values) (define (iter rest-variables rest-values) (if (null? rest-variables) '() (cons (cons (car rest-variables) (car rest-values)) (iter (cdr r…

データ抽象を使うと評価される言語の特定の構文と独立なeval手続きを書くことが出来る。これを示すため、evalとapplyを変えずに本節の手続きを修正し、schemeの新しい構文を設計し、実装せよ。という問題。 ためしに新しい構文として前置記法でなく後置記法…

2010/03/17 while?の定義の部分が間違ってたので修正do,for,while,untilといった反復構造を設計し、その使用例を示し、それを導出された式としてどう実装するのか示せということだが、Schemeのdo構文が分かりづらいのでwhileの実装を考えてみる (while <predicate> <body>) と</body></predicate>…

名前付きlet (let <var> <bindings> <body>) 名前付きletで定義したfib手続き (define (fib n) (let fib-iter ((a 1) (b 0) (count n)) (if (= count 0) b (fib-iter (+ a b) a (- count 1))))) これは以下と同じである (define (fib n) (define (fib-iter a b count) (if (= coun</body></bindings></var>…

2010/03/17 evalでlookup-variable-valueのトコが間違ってたので修正 2010/03/16 4.9のmake-named-letに合わせてmake-letを修正問題のlet*式の例 (let* ((x 3) (y (+ x 2)) (z (+ x y 5))) (* x z)) ; 39 これは以下のようなletに書き換えることが可能である…

2010/03/17 evalでlookup-variable-valueのトコが間違ってたので修正let式が (let ((<var1> <exp1>) ... (<varn> <expn>)) <body>) lambda式 ((lambda (<var1> ... <varn>) <body>) <exp1> ... <expn>) のsyntax sugarであることから、変換let->combinationを実装し、let式が使えるようevalに適当な節を追加する。 let関連</expn></exp1></body></varn></var1></body></expn></varn></exp1></var1>…

cond節のもう一つの構文(=>) が真の値に評価されると、が評価される。 その値は一引数の手続きでなければならない この手続きは次にの値に対して呼び出され、その結果がcond式の値として返る。 (例) (cond ((assoc 'b '((a 1) (b 2))) => cadr) (else #f)) …

2010/03/17 evalでlookup-variable-valueのトコが間違ってたので修正 and: 式を左から右へ評価する。ある式が偽に評価されたら偽を返す;残りの式は評価しない。全ての式が真に評価されたら、最後の式の値を返す。式が一つもなければ真を返す or: 式を左から…

2010/03/17 evalでlookup-variable-valueのトコが間違ってたので修正元のeval (define (eval exp env) (cond ((self-evaluating? exp) exp) ((variable? exp) (lookup-variable-value exp env)) ((quoted? exp) (text-of-quotation exp)) ((assignment? exp)…

2010/03/17 evalでlookup-variable-valueのトコが間違ってたので修正 a. cond節の順序で手続き作用の節(application?)が代入の節(assignment?)の前に現れるようにすると、いろいろな式が手続き作用として扱われてしまう。ヒントとしてあげられている(define …