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

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

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

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

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

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

続きを読む

SICPゼミ第53回

練習問題4.27

外側の id については application なので評価がされており (引数の (id 10) については評価されずに残っている)、すなわち w の定義時点で count は一度だけインクリメントされていることになる。 答えは 1, 10, 2 となる。

SICPゼミ第52回

練習問題4.25

(define (factorial n)
  (unless (= n 1)
    (* n (factorial (- n 1)))
    1))

適用順序言語では先に unless の引数がすべて評価される、すなわち (factorial 0) の評価が先に行われてしまうため、無限ループに陥って停止しない。 正規順序言語では引数が遅延評価されるため停止する。

練習問題 4.26

派生手続きにするのは,いい感じにif文に変形してやればいい.引数の順番変えるだけだし楽.

構文として定義してしまうと,手続きではないのでmapとかと組み合わせて使いたいときに困る.

SICPゼミ第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))))))