SICP 4.1.6

4.16

a

(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? '*unassigned* (car vars))
              (error "Unassigned variable --" var))
              (car vals))
            (else (scan (cdr vars) (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

b

方針が思いつかなかったのでカンニング

(define (scan-out-defines body)
  (define (make-variable-clauses body)
    (if (definition? (car body))
        (cons (list (definition-variable (car body))
                    ''*unassigned*)
              (make-variable-clauses (cdr body)))
        '()))
  (define (definition->assignment-body body)
    (if (definition? (car body))
        (cons (make-assignment (definition-variable (car body))
                               (definition-value (car body)))
              (definition->assignment-body (cdr body)))
        body))
  (if (definition? (car body))
      (list (apply-in-underlying-scheme
             make-let
             (cons (make-variable-clauses body)
                   (definition->assignment-body body))))
      body))

c

実行回数が少なくなるので、make-procedure に組み込むべき。

組み込みは 引数の body にあらかじめ scan-out-defines を適用してやればok

(define (make-procedure parameters body env)
  (list 'procedure parameters (scan-out-defines body) env))

4.17

ギブ

4.18

(define (solve f y0 dt)
  (define y (integral (delay dy) y0 dt))
  (define dy (stream-map f y))
  y)

本文中の掃き出し方だと

(define solve
  (lambda (f y0 dt)
     (let (( y '*unassigned*)
           (dy '*unassigned*))
          (set! y (integral (delay dy) y0 dt))
          (set! dy (stream-map f y))
          y)))

問題文の掃き出し方だと

(define solve
  (lambda (f y0 dt)
    (let ((y '*unassigned*)
          (dy '*unassigned*))
         (let ((a (integral (delay dy) y0 dt))
               (b (stream-map f y)))
              (set! y a)
              (set! dy b))
         y)))

本文中の掃き出し方は問題なし。

問題文の掃き出し方の場合、

(b (stream-map f y)))

この時点で anassigned の y が評価されてしまうので動かない.

4.19

議論対象の処理

(let ((a 1))
  (define (f x)
    (define b (+ a x))
    (define a 5)
    (+ a b))
  (f 10))

Benの主張

a -> 1
x-> 10
b -> + a x -> 11
a -> 5
(f 10) -> + a b -> 16

Alyysaの主張

(define b (+ a x))

の時点で、a が未定義のためエラーになる

Evaの主張

a -> 1
x -> 10
a -> 5, b -> + a x -> 15
(f 10) -> + a b -> 20

Schemeでは Alyysa の主張とおなじ結果になった。 ただ、define を数学的な「定義」と見なすなら、Evaの言う同時というのが自然な気もする。

Evaの主張に合わせて変更するとしたら、すべての define に delay を挿入すれば良い? (define の時点で評価させないようにするため)

参考 URL  http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3A%E5%86%85%E9%83%A8define%E3%81%AE%E8%A9%95%E4%BE%A1%E9%A0%86

2.20

(letrec
  ((var1 exp1) (var2 expr2) ...)
  body)

(lambda <vars>
  (let ((var1 *unassigned*) (var2 *unassigned) ... )
    (set! var1 exp1)
    (set! var2 exp2)
    ...
    body))

と変換される。

よって

a

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
  ;; ...
  ((letrec? exp) (eval (letrec->let exp) env))
  ;; ...
  ))
(define (letrec? exp) (tagged-list? exp 'letrec))
(define (letrec-inits exp) (cadr exp))
(define (letrec-body exp) (cddr exp))
(define (letrec->let exp)
  (let ((vars (map car (let-inits exp)))
        (exps (map cdr (let-inits exp)))
        (body (let-body exp)))
       (cons 'let
         (cons (map (lambda(x) (list x ''*unassigned*)) vars)
               (append (map (lambda (x y) (cons 'set! (cons x y))) vars exps)
                       body)))))

b

let で 評価される環境には定義された関数自身が存在しないので、再帰的な定義が出来ない。

4.21

a

((lambda (n)
   ((lambda (fact)
      (fact fact n))
    (lambda (ft k)
      (if (= k 1)
          1
          (* k (ft ft (- k 1)))))))
 10)

ややこしいので (lambda (fact) (fact fact n)) を a (lambda (ft k) (if ... )) を b とすると

((lambda (n) (a b)) 10)
=> ((lambda (n) (b b n)) 10)
=> (b b 10)
=> (* 10 (b b 9))
=> (* 10 (* 9 (b b 8)))
...

フィボナッチ

((lambda (n)
   ((lambda (fib)
      (fib fib n))
    (lambda (ft k)
      (cond ((= k 0) 0)
            ((= k 1) 1)
            (else (+ (ft ft (- k 1)) (ft ft (- k 2))))))))
 5)

b

(define (f x)
  ((lambda (even? odd?)
     (even? even? odd? x))
   (lambda (ev? od? n)
     (if (= n 0) true (od? ev? od? (- n 1))))
   (lambda (ev? od? n)
     (if (= n 0) false (ev? ev? od? (- n 1))))))