社内SICP勉強会(第1回)

SICP

社内SICP勉強会が始まる。随時メモを公開していこうと思う。環境はMac + Gauche + Emacs。

範囲

始めから問題1.5(P12)まで

内容

  • 値と記号を対応付ける(名前とオブジェクトの対を記憶しておく)ことを環境(environment、より正確には大域環境(grobal environment))という
  • 組み合わせ評価の基本は以下の通り
    • 組み合わせの部分式を評価する
    • 最左部分式の値である手続き(演算子)を、残りの部分式の値である引数(被演算子)に作用させる
  • 一般的評価規則は以下の通り
    • 数字列の値は、その表す数値とする。
    • 基本演算子の値は、対応する演算を実行する機会命令の列とする。
    • それ以外の名前は、その環境で名前と対応付けられたオブジェクトとする。
    • この評価規則は定義(define hogeg fuga)には当てはまらない
      • 一般評価規則に当てはまらない例外を特殊形式という
  • 合成手続き
    • (define ( ) )
  • 手続き作用の置き換えモデル
    • 正規順序の評価(normal-order evaluation)
      • 全てを展開してから演算子を作用させる
    • 作用的順序の評価(applicative-order evaluation)
      • 引数を評価してから演算子を作用させる
    • 正規順序と作用的順序の評価が同じ結果にならないこともある。
  • 条件式と述語
    • 特殊形式のif
      • (if )

問題

問題1.1
gosh> 10
10
gosh> (+ 5 3 4)
12
gosh> (- 9 1)
8
gosh> (/ 6 2)
3
gosh> (+ (* 2 4) (- 4 6))
6
gosh> (define a 3)
a
gosh> (define b (+ a 1))
b
gosh> (+ a b (* a b))
19
gosh> (= a b)
#f
gosh> (if (and (> b a) (< b (* a b)))
       b
       a)
4
gosh> (cond [(= a 4) 6]
         [(= b 4) (+ 6 7 a)]
         [else 25])
16
gosh> (+ 2 (if (> b a) b a))
6
gosh> (* (cond [(> a b) a]
            [(< a b) b]
            [else -1])
      (+ a 1))
16
問題1.2
(/ (+ 5
      4
      (- 2
      (- 3
         (+ 6
            (/ 4 5)))))
   (* 3
      (- 6 2)
      (- 2 7)))
問題1.3

愚直に実装した場合

(define (sum-of-squares x y)
  (+ (* x x) (* y y)))

(define (square-of-larger-two-numbers x y z)
  (if (> x y)
      (if (> y z)
       (sum-of-squares x y)
       (sum-of-squares x z))
      (if (> x z)
       (sum-of-squares x y)
       (sum-of-squares y z))))

Schemeっぽく書きたかったので考えてみた

(define (square-of-larger-two-numbers x y z)
  (cond [(> x z) (square-of-larger-two-numbers z y x)]
     [(> y z) (square-of-larger-two-numbers x z y)]
     [else (sum-of-squares y z)]))
問題1.4

b > 0 が成り立っていれば演算子+を返し、b < 0であれば演算子-を返す。

問題1.5
  • 作用的順序の場合
    • (test 0 (p))で始めに(p)を展開しようとするが、(define (p) (p))であるため、永遠に(p) -> (p)という処理が続きプログラムが終了しない
  • 正規順序の場合
    • (test 0 (p))は始めに(if (= 0 0) 0 (p))と展開され、特殊形式ifの評価が#tとなるため0が返されてプログラムは終了する

所感

大学院の時に１章は終わらせた経験があるし、最初なのでそこまで問題ない。