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

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

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

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

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

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

続きを読む

第51回

ご無沙汰しております

練習問題4.23

  • Alyssaの解析器
(define (analyze-sequence exps)
  (define (execute-sequence procs env)
    (cond (( null? (cdr procs ))
           ((car procs) env))
          (else
            ((car procs) env)
            (execute-sequence (cdr procs) env ))))
  (let (( procs (map analyze exps )))
    (if (null? procs)
        (error "Empty sequence: ANALYZE"))
    (lambda (env)
      (execute-sequence procs env ))))
  • 本文中の解析器
(define (analyze-sequence exps)
  (define (sequentially proc1 proc2)
    (lambda (env) (proc1 env) (proc2 env )))
  (define (loop first-proc rest-procs)
    (if (null? rest-procs)
        first-proc
        (loop (sequentially first-proc (car rest-procs ))
              (cdr rest-procs ))))
  (let (( procs (map analyze exps )))
    (if (null? procs) (error "Empty sequence: ANALYZE"))
    (loop (car procs) (cdr procs ))))

Alyssaの解析器では字句解析を(map analyze exps)で行っていて、構文解析expecute-sequenceで行っているが、analyze-sequenceで返ってくるのはlambda式なので、lambdaが実行されるまで構文解析が行われない。
それに対して本文中の解析器はanalyze-sequenceの段階で構文解析まで行っている。

練習問題4.24

お気持ち

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現実