プロセスの抽象化　― シーケンスへの作用

SICP

『計算機プログラムにおける構造と解釈』の「2.2.3 公認インターフェースとしての並び」(p.65)が非常に面白かった。

ある計算プロセスを手続きとして設計する時、その一連のプロセスは大抵、複数の異なる要素(計算過程)を内包している。それらを最小の要素まで分解し、明確で単純な目的をもつ独立した部品とし、それらをある意図を持って組み合わせることによりプロセスを構成しようという話（これは単なる構造化ではなく、オブジェクトのcompositionに近い発想だ）。


これを説明する例として、「木構造で数値を保持するリストを引数に取り、その中の奇数である葉の二乗の和を返す」関数の設計を改善していく話が出てくる。当初は「木構造を頭から走査」し、要素が「末端」かつ「奇数」であればその「二乗」を再帰的に「加算していく」という愚直な方法で実装する。

■愚直な実装(p.65)

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


しかし、このプロセスは実は「シーケンス(並び)に関する作用群」として、以下の4つの要素に部品化することができる。このような要素を抽出する(プロセスを抽象化する)ことができるかどうかがプログラマにとって決定的に重要な力であることを痛感する日々。

enumeration与えられたリソースからシーケンスを生成する［木構造から葉の配列を生成する］
filterリストから特定の要素を抽出した結果を得る［奇数を抽出したリストを得る］
map与えられたシーケンスのある作用に対する写像を得る［全要素を二乗したリストを得る］
accumulation与えられたシーケンスの要素を何らかの規約に基づいて集約する［全要素の和を得る］


さて、これらの部品を構成することによって、最初に引用した手続きを下のように実装することができる（各部品の内部実装は省く）。

■interfaceのcompositionによる実装(p.67)

(define (sum-odd-squares tree)
  (accumulate +
              0
              (map square
                   (filter odd?
                           (enumerate-tree tree)))))

まず、この実装は最初のものに比べて可読性が圧倒的に高い。部品の名称からは各々の目的が明確に伝わってきて、全体として何を行いたいのかが一目で伝わってくる。

次に、部品化を行ったことによって、異なるプロセスへの再利用が可能となる。本書の例では「整数nより小さいか等しいkに対して、偶数のFibonacci数のリストを作る手続き」という、最初の例題とは一見似ても似つかないプロセスが、「シーケンスの取得、シーケンスへの作用、それら要素の集約」として抽象化（同一視）可能であることが指摘される。すると、必要な部品を置き換えることによってこのプロセスが実装できる。

■部品を再利用した例(p.76)

(define (even-fibs n)
  (accumulate cons
              nil
              (filter even?
                      (map fib
                           (enumerate-interval 0 n)))))

いや、美しい。