SICP 孤読書会 - 2.2 階層データ構造と閉包性 (2.2.1 〜 2.2.4)

SICP

この節では、

  • 合成データの閉包性(closure property)の重要さ

について話す。

要素が"対"であるような"対"を作る能力は、リスト構造にとって重要。 この能力を cons の閉包性という。

閉包は階層的(hierarchical)構造を作ることができる。


2.2.1 並びの表現

対を使って並び(sequence)を表現することができる。

例えば、1, 2, 3,4 の並びは

(cons 1
      (cons 2
            (cons 3
                  (cons 4 nil))))

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

nil は 並びの終端を表す。
gauche には nil がないので空リスト '() で終端を表します。

入れ子の cons で作られた対の並びをリスト(list)という。
リストは list という基本手続きで作成することができる。

(list 1 2 3 4)

は上記の cons で作成した 1, 2, 3, 4 の並びと等価。


問題 2.17 〜 2.23

SICP/ch2/2-17.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-18.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-19.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-20.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-21.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-22.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-23.scm at master · snufkon/SICP · GitHub

に解答を追加。


2.2.2 階層構造

リストによる並びの表現は、その要素がまた並びであるような表現に一般化できる。

例えば

(cons (list 1 2) (list 3 4))

要素自身が並びであるような並びは、木(tree)としてみることができる。

再帰は、木構造を扱う自然な道具である。


問題 2.24 〜 2.32

SICP/ch2/2-24.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-24.png at master · snufkon/SICP · GitHub
SICP/ch2/2-25.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-26.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-27.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-28.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-29.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-30.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-31.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-32.scm at master · snufkon/SICP · GitHub

に解答を追加。


2.2.3 公認インタフェースとしての並び

引数として木をとり、奇数である葉の二乗の和を計算する手続きを考える

(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
        ((not (pair? tree))
         (if (odd? tree) (square tree) 0))
        (else (+ (sum-odd-squares (car tree))
                 (sum-odd-squares (cdr tree))))))

この手続きは内部で

  • 木の葉を数え上げる
  • フィルタを通し、奇数のものを選ぶ
  • 選ばれたものをそれぞれ二乗する
  • 0 の初期値に結果を + を使いアキュムレートする

を行なっている。

しかしながら、実装としては数え上げを手続き全体に撒き散らし、 写像、フィルタ、アキュムレータを使って混ぜあわせている。

信号処理のように

enumerate --> filter --> map --> accumulate

の構造が明白になるようにプログラムを構成できれば、 出来上がったプログラムの明晰性が増大する。

信号処理構造を構成する鍵は、プロセスのある段から次へ流れる「信号」 に集中することである。

並びの演算

プログラムを並びの演算として表すことは、部品化されたプログラム設計を可能とする。
リストとして実装した並びは、処理部品を組み合わせるのを可能にするための公認インタフェースとして役立つ。


問題 2.33 〜 2.43

SICP/ch2/2-33.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-34.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-35.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-36.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-37.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-38.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-39.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-40.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-41.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-42.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-43.scm at master · snufkon/SICP · GitHub

に解答を追加。


2.2.4 例: 図形言語

図形言語を例に、データ抽象と閉包の能力を示す。


問題 2.44 〜 2.52

SICP/ch2/2-44.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-45.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-46.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-47.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-48.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-49.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-50.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-51.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-52.scm at master · snufkon/SICP · GitHub

に解答を追加。

図形の描画には、以下を利用させてもらいました。

図形言語 描画スクリプト – SICP（計算機プログラムの構造と解釈）その59 : Serendip - Webデザイン・プログラミング
図形言語 描画スクリプト（with Canvas and JavaScript） :: SICP（計算機プログラムの構造と解釈）- Serendip


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

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

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