読者です 読者をやめる 読者になる 読者になる

SICP 孤読書会 - 2.3 記号データ (2.3.1 〜 2.3.4)

この節では、データとして任意の記号に対して作業する能力を採用し、言語の表現力を拡大する。


2.3.1 クォート

記号を操作するために、データオブジェクトをクォートする(quote)能力が必要である。

リスト (a b) を作りたい場合、(list a b) で作ることはできない。
(list a b) は a と b をそれぞれ評価し、値のリストを作成してしまう。

(define a 1)
(define b 2)
(list a b) => (1 2)

リストや記号を評価される式としてではなく、データオブジェクトとして扱うことを示すのにクォートを使用する。

(list 'a 'b) => (a b)

(list 'a b) => (a 2)

リストの印字表現を使い、合成オブジェクトを作成するのにクォートを使うことができる

(car '(a b c)) => a

(cdr '(a b c)) => (b c)


問題 2.53 〜 2.55

SICP/ch2/2-53.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-54.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-55.scm at master · snufkon/SICP · GitHub

に解答を追加。


2.3.2 例: 記号微分

記号操作、データ抽象の実例として記号微分を実行する手続きの設計を考える。

記号微分を実行する手続きは

代数式(2ax + b)と変数(x)を引数としてとり、代数式を変数で微分した結果(2a)を返す

手続きとして実装する。

抽象データによる微分プログラム

対象の問題を簡単にするため、2つの引数を持った加算と乗算の演算だけからなる式を扱うこととする。
これらの式は以下の簡約規則を使うことで実行できる

\(\frac{dc}{dx} = 0\)     c は定数か x と異なる変数

\(\frac{dx}{dx} = 1\)

\(\frac{d(u + v)}{dx} = \frac{du}{dx} + \frac{dv}{dx}\)

\(\frac{d(uv)}{dx} = u(\frac{dv}{dx}) + v(\frac{du}{dx})\)


次の選択子、構成子、述語を実装した手続きは既にあると仮定すると

(variable? e)   e は変数か?
(same-variable? v1 v2)   v1 と v2 は同じ変数か?

(sum? e)   e は和か?
(addend e)   e の加数
(augend e)   e の被加数
(make-sum a1 a2)   a1 と a2 の和を構成

(product? e)   e は積か?
(multiplier e)     e の乗数
(multiplicand e)   e の被乗数
(make-product m1 m2)   m1 と m2 の積を構成

記号微分を実行する手続き(deriv)は以下にように記述できる

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        (else
         (error "unknown expression type -- DERIV" exp))))

この deriv は抽象データを使って表されている。
そのため、正当な選択肢と構成子を設計しさえすれば、

代数式の表現をどう選ぶか?

に無関係に微分を行うことができる。

代数式の表現

上記したように代数式の表現は自由に決めることができる。

例えば、通常の代数記法に合わせて ax + b を

(a * x + b)

と表現することができる。

ここでは、Lisp と同様、前置記法で代数式を表現することを考える。 ax + b は

(+ (* a x) b)

と表現することになる。

前置記法での代数式表現に合わせ、 deriv で使われている選択子、構成子、述語のデータ表現は以下のようになる

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (make-sum a1 a2) (list '+ a1 a2))

(define (make-product m1 m2) (list '* m1 m2))

(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))

(define (addend s) (cadr s))

(define (augend s) (caddr s))

(define (product? x)
  (and (pair? x) (eq? (car x) '*)))

(define (multiplier p) (cadr p))

(define (multiplicand p) (caddr p))

deriv 手続きの使用例

(deriv '(+ x 3) 'x)               ; (+ 1 0)

(deriv '(* x y) 'x)               ; (+ (* x 0) (* 1 y))

(deriv '(* (* x y) (+ x 3)) 'x)   ; (+ (* (* x y) (+ 1 0))
                                  ; (* (+ (* x 0) (* 1 y))
                                  ; (+  x 3)))


問題 2.56 〜 2.58

SICP/ch2/2-56.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-57.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-58-a.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-58-b.scm at master · snufkon/SICP · GitHub

に解答を追加。


2.3.2 例: 集合の表現

集合に使われる演算を規定することで「集合」を定義する。

  • 演算
    • element-of-set? : 与えられた要素が集合の構成要素であるか?を判定する述語
    • adjoin-set : 引数としてオブジェクトと集合をとり、元の集合にそのオブジェクトを追加した集合を返す
    • union-set : 2つの集合の和集合
    • intersection-set : 2つの集合の積集合

データ抽象的に、これらの演算を実装する表現は自由に選択することができる。

  • 集合の表現
    • 順序づけられないリストとしての集合
    • 順序づけられたリストとしての集合
    • 二進木としての集合

表現の選択は、そのデータを使用するプログラムの効率に大きく影響する。


問題 2.59 〜2.66

SICP/ch2/2-59.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-60.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-61.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-62.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-63.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-64.png at master · snufkon/SICP · GitHub
SICP/ch2/2-64.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-65.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-66.scm at master · snufkon/SICP · GitHub

に解答を追加。


2.3.3 例: Huffman 符号化木

集合と木を操作するリスト構造、データ抽象の使い方を Huffman 符号化木を例として練習する。


問題 2.67 〜 問題2.72

SICP/ch2/2-67.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-68.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-69.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-70.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-71.png at master · snufkon/SICP · GitHub
SICP/ch2/2-71.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-72.txt at master · snufkon/SICP · GitHub


SICP 孤読書会のメインページはこちら

計算機プログラムの構造と解釈

計算機プログラムの構造と解釈