Subscribed unsubscribe Subscribe Subscribe

SE Can't Code

A Tokyo based Software Engineer. Not System Engineer :(

SICP2章, 公認インターフェース.

演算は手続きのリストとして表現することが出来る。要は信号処理のフィルタのように数珠繋ぎで演算が表現可能になるのだが、この時各リストの中の各種部品に類似性を見つけてあげると、それを"公認インターフェース"として柔軟かつ強力な設計が実現する。下記の例は2つの手続きを表現するプログラムである。

  1. 引数としてリストを取り、奇数である葉の二乗の和を計算する
  2. 引数として数値を取り、偶数のフィボナッチ数列のリストを作る

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

(sum-odd-squares '(1 (2 3) (4 5)))
; 35

(define (even-fibs n)
  (define (next k)
    (if (> k n)
        '()
        (let ((f (fib k)))
          (if (even? f)
              (cons f (next (+ 1 k)))
              (next (+ 1 k))))))
  (next 0))

(even-fibs 20)
; (0 2 8 34 144 610 2584)


この2つのプログラムには類似性を見ることができる。並びは違えど、それぞれのプロセスは[enumerate, filter, map, accumulate]の4つの共通部品によって構成されているのがわかる。
f:id:fixxman:20161202013624p:plain

sum-odd-squares

  • 木の葉を数え上げる[enumerate]
  • 奇数でフィルタ[filter]
  • 選ばれた要素を二乗[map]
  • 要素を0初期値で加算[accumulate]

even-fibs

  • 整数を0からnまで数え上げる[enumerate]
  • それぞれの要素でFibonacci数を計算[map]
  • 偶数でフィルタ[filter]
  • 要素を空リスト初期値でcons[accumulate]


この[enumerate, filter, map, accumulate]ような独立的な部品(公認インターフェース)を組み合わせ、プログラムを並びの演算として表現することで様々な実装を実現する。このケースの公認インターフェースだと下記のように実装ができる。

(define (accumulate op initial items)
  (if (null? items)
      initial
      (op (car items)
          (accumulate op initial (cdr items)))))

(define (map proc items)
  (if (null? items)
    nil
    (cons (proc (car items)
          (map proc (cdr items)))))

(define (filter predicate items)
  (cond ((null? items) nul)
        ((predicate (car items))
         (cons (car items)
               (filter predicate (cdr items))))
        (else (filter predicate (cdr items)))))


このように表現すると下記のように柔軟に公認インターフェースを様々な用途で利用可能になる。

(accumulate + 0 (list 1 2 3 4 5))
-> 15

(accumulate * 1 (list 1 2 3 4 5))
-> 120

(map square (list 1 2 3 4 5))
-> 1 4 9 16 25

(filter odd? (list 1 2 3 4 5))
-> (1 3 5)


これをリストとして組み合わせて、順序を入れ替えると表現できることが無数に広がる。
始めて実装する時は共通部分を見出すことが難しいため、公認インターフェースを作り出すことは難しい気がする。ただ、実装が進んでいくにつれて、他に作り出された演算との類似性が見えてくるため、公認インターフェースを作り出すための抽象化がし易くなるんじゃないか。リファクタリングをする必要が出てくるのだが、処理というものを信号処理のようなリストというでデータ構造に落とし込むことで、実装の各ステージが明確になり、独立性を高めることができるようになる。

Remove all ads