SICPを読む上でよく見るメモ

ゼミのたびに「あの単語の意味ってなんだったっけ?」って事案が多発するので定義をまとめた記事を作ります。

適用順序評価と正規順序評価
  • 正規順序評価(normal-order evaluation)

  完全に展開してから簡約する。

  • 適用順序評価(applicative-order evaluation)

  引数を評価してから展開する。

続きを読む

SICPゼミ第50回

練習問題4.22

(define (analyze-let exp)
  (analyze (let->combination exp)))

(define (let->combination exp)
  (let ((defs (let-defs exp)))
    ((make-lambda (let-variable-from-defs defs) (let-body exp))
     (let-defbody-from-defs defs))))
(define (let-defs exp)
  (cadr exp))
(define (let-body exp)
  (caddr exp))
(define (let-variable-from-defs defs)
  (if (null? defs)
      '()
      (cons (caar defs) (let-variable-from-defs (cdr defs)))))
(define (let-defbody-from-defs defs)
  (if (null? defs)
      '()
      (cons (cdar defs) (let-variable-from-defs (cdr defs)))))

SICPゼミ第49回

練習問題4.21

a

 ((lambda (n)
      ((lambda (fib) (fib fib n))
       (lambda (ft k)
         (if (< k 2) 1
             (+ (ft ft (- k 2)) (ft ft (- k 1)))))))
   5)

by tube

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))))))

SICPゼミ第46回

練習問題4.18

(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 '*hoge*) (dy '*hoge*))
    (let ((a (integral (delay dy) y0 dt))
          (b (stream-map f y)))
      (set! y a)
      (set! dy b))
    y))

(define (solve__ f y0 dt)
  (let ((y '*hoge*) (dy '*hoge*))
    (set! y (integral (delay dy) y0 dt))
    (set! dy (stream-map f y))
    y))

実行結果

> (stream-ref (solve (lambda (y) y) 1 0.001) 1000)
2.716923932235896
> (stream-ref (solve_ (lambda (y) y) 1 0.001) 1000)
. . car: contract violation
  expected: pair?
  given: '*hoge*
> (stream-ref (solve__ (lambda (y) y) 1 0.001) 1000)
2.716923932235896

書き換えるとエラーが出る。 solve_のほうでは、(b (stream-map f y)) が評価されるときに y には '*hoge* が入っているのでエラーが出る。 solve__ のほうでは、(set! y (integral (delay dy) y0 dt)) が評価されるときに dy には '*hogeが入っているが、遅延評価なので問題なく動く。

by tube

練習問題4.19

Ben式は割といろんな言語である気がする.Eva式は逐次定義絶対殺すマンなので割と異常だと思う.ところがGoshはこの方針で実装されているのでたいへん気持ち悪い.とりあえず結論としては「ここで出てくるようなプログラムを書くのを止めろ」に尽きる.by現実

SICPゼミ第45回

練習問題4.16

(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? (car vals) '*unassigned*)
                 (error "Unassigned Variable")
                 (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 procedure-body)
  (if (null? procedure-body)
      null
      (let ((exp (car procedure-body)))
        (if (definition? exp)
            (let ((var (definition-variable exp)))
              ((make-lambda var
                            (begin (set! var (definition-value exp))
                                   (scan-out-defines (cdr procedure-body))))
               '*unassigned*))
            (cons exp (scan-out-defines (cdr procedure-body)))))))

c. どっちでも問題はないが,make-procedureのほうが効率がいい.make-procedureに入れると,evalの一回だけscan-outするが,procedure-bodyに入れるとapplyするたびにscan-outすることになる.

練習問題4.17

f:id:sicp-zemi:20170426162851j:plain f:id:sicp-zemi:20170426162905j:plain