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

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

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

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

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

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

続きを読む

SICP ゼミ第55回

練習問題4.30

a .

(for-each (lambda (x) (newline) (display x))
  (list 57 321 88))

を呼ぶ。 問題になっているのは eval-sequence に食われる begin 節、すなわち

(define (for-each proc items)
  (if (null? items)
    'done
    (begin (proc (car items ))
           (for-each proc (cdr items )))))

から

(begin ((lambda (x) (newline) (display x)) 57)
        (for-each proc (list 321 88))))

のところである。 副作用がないという主張に基づくならば、このとき lambda 節が force されず、結局 list の最後のである88だけが評価されてしまうということになる。 しかし実際には、lambda 節の中にある演算子であるnewline と display が基本手続きであるため、これは force され正しい出力がなされる。

b . 結果としては

(define (p1 x)
  (set! x (cons x '(2)))
  x)

の出力は (1 . 2)

(define (p2 x)
  (define (p e)
    e
    x)
  (p (set! x (cons x '(2)))))

の出力は 1 である。

p1 については

(set! x (cons x '(2)))
x

のシーケンスが評価される。 まず一つ目の要素である set! が評価されるが、この時 set! が基本手続きであることからこれは force され、xに(1 . 2)が代入される。その後 (x) が評価されるので正しくペアが返ってくる。

しかし p2 については、まず (p (set! x (cons x '(2))))が評価されるが、p が基本手続きでないため、引数の set! 節が force されないまま thunk として残っている環境となる。 その後

e
x

のシーケンスが評価されるが、このとき、e には thunk しか入っていない。その後 x が評価されるときに e は呼ばれない。このため単純に x が呼ばれて 1 が返ってくる。

c . シーケンスの中身を順番に force していくだけなので問題ない。

d . 純粋に個人の好み。本文中の eval-sequence は、シーケンスであろうがなかろうが遅延評価なのだから必要になるまでシーケンスの要素を force するべきではないという考えに基づいたもの。Cy の eval-sequence は遅延評価であってもシーケンスは前から順に評価を値まで完了させるべきという考えに基づいたものである。 ぼくは Cy のほうが好きです。

by tube

練習問題4.31

最初に実装したevalと,evalを遅延評価ができるように改造したeval-delayと,メモ化もできるように改造したeval-delay-memoの3つを用意しておいて,引数の後ろにlazyが来ているか,lazy-memoが来ているか,何もひっついていないかでそれぞれ別々のevalを呼び出せば良い.実装は闇だからやらない.

速水奏さんと鷺沢文香さんを応援しています.

SICPゼミ第54回

練習問題4.28

演算子がevalの中で評価されない(遅延されてしまう)場合,すなわち複合手続きが引数として呼ばれた場合,演算子を評価しないままthunkがそのまま返ってきてしまう事がある.

例えば

(define (g x) (+ x 1))
(define (f g x) (g x))

とした場合に,(g 2) を呼ぶとするとこれは eval に渡るのは基本手続きのみであり,complex-application? 節が呼ばれない.そのため普通に eval が基本手続きとして値評価を行い,問題なく動く. 一方,(f g 2) を呼ぶとする.このとき actual-value でないとすると,引数である g が thunk のまま eval に渡されてしまい,エラーとなる.

練習問題4.29

メモ化してないと,引数が評価が必要な値のとき何回も評価が必要でつらい.引数をn回足すとかつらいし,フィボナッチとかやると破滅する.

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