【Common Lispと数学】
圏論的設計を考える
（パイプ指向とラムダ計算）

by
  • 手続き型やオブジェクト指向は「状態をどう管理するか」という問いを抱えており、状態があるとバグの再現が難しくなります。関数型設計とUNIXパイプはその問いを手放し、状態を持たない変換をつなぐ発想に切り替えました。
  • 圏論的設計では「どの順序で合成するか」という管理をパイプラインという値に閉じ込めます。操作をラムダとして先に組み立てておき、いつでもどんなデータにも適用できる構造として保持します。
  • さらに進んだ自由モナド的設計では、IOを含む操作の記述もデータとして表現し、「何をするか」と「どう実行するか」を完全に分離します。同じプログラム記述に本番・テスト・ロギング用のインタープリタを差し替えて使えます。
  • この設計の変遷は「状態の管理」「合成順序の管理」「IO実行の管理」を順に値として閉じ込める流れで、圏論はその各段階で「合成できるものには何でも同じパターンが使える」という見方を与えます。

関連記事

1. 圏論（category theory）とは？

「圏論（category theory）」は、1945年に数学者 Samuel Eilenberg と Saunders Mac Lane が代数的位相幾何の研究から生み出した理論1です。

出発点は「異なる数学の分野に、同じ形の対応が繰り返し現れる」という観察2で、中心にある問いはシンプルです。
「ものそのものより、ものの間の変換に注目したら、何が見えるか？」

1.1. 問題を考える有効な視点

プログラミングでは、「圏論」は複雑な問題を解くのに役立ちます。
問題の構造を「部品」に分解し、それを「つなぐ」というときに、その考えるための語彙と判断記述を示してくれるからです。

  • この処理は合成可能な形になっているか（入出力の型を揃える）
  • この合成はどの順序で区切っても同じ結果になるか（並列処理にできるか）
  • この変換は構造を保っているか（同じパターンを別の文脈で使い回せるか）

つまり、「圏論」は、「分解してつなぐことが成立する条件を問う考え方」です。

1.2. 「圏」の3要素

数学的には、「圏（category）」は3つの要素で構成されます。

  • 対象（object）は、型やデータの種類に相当するもの、
  • 射（morphism）は、対象から対象への変換、つまり関数に相当するもの、
  • 合成（composition）は、射をつなぐ操作3、つまりプログラムも合成の一つです。

圏論が「射」として扱うのは、普通の関数だけではなく、失敗するかもしれない処理、非同期処理、状態を変える処理なども含まれます。
「合成できる」という条件を満たせば、「射」になります。

プログラミングでは、この「射が合成できるか」という問いを持つことが役に立ちます。
というのも、データ操作を合成しやすく整えておけば、テストしやすく、部品を差し替えやすく、AIに修正を指示しやすくなるからです。

圏論と親和性の高いプログラミング言語としては、型クラスで Functor・Monad などを直接表現できる Haskell や、圏論の命題を証明として記述できる Coq があります。
ただ、Common Lisp でも、型システムによる保証はありませんが、合成・持ち上げ・IO の分離という圏論的な設計意図は活かせます。

2. データベースの処理問題

同じ問題を4つの設計スタイルで解きながら、「どこで読むか」「内部でどう持つか」「どこで出力するか」という差を見ていきます。

入力：
1行目 ユーザー数 N（整数）
2〜N+1行目 名前と年齢をスペース区切りで1行ずつ
出力：
18歳以上の名前をカンマとスペースで区切って1行

入力例：        出力例：
4               Alice, Carol
Alice 30
Bob 15
Carol 22
Dave 17

2.1. どのように変わるのか？

状態入出力の扱い合成の見え方変換の扱い
手続き型明示的に変わるロジックと混在ループの中に埋まる処理ステップ
OOPスロットに隠蔽オブジェクト生成と結合メソッド呼び出しの連鎖型に紐付いた操作
関数型なしread-users / format t で分離ネストまたはパイプ第一級の値
UNIXパイプなしstdin / stdout が共通型| で一直線小さなコマンドの連鎖
圏論的なしread-input / write-outputパイプラインとして組み立て組み立て可能な部品
自由モナド的なしインタープリタが注入プログラムをデータとして構築記述と実行の完全分離

3. 状態を更新していく考え方

3.1. a. 手続き型の解

もっともシンプルに考えると、読み込み・判定・蓄積・出力をすべて1つのループに書けばよいことになります。

(defun solve/proc ()
  (let* ((n      (parse-integer (read-line)))
         (result '()))
    (dotimes (_ n)
      (let* ((line  (read-line))
             (space (position #\Space line))
             (name  (subseq line 0 space))
             (age   (parse-integer (subseq line (1+ space)))))
        (when (>= age 18)
          (push name result))))
    (format t "~{~a~^, ~}~%" (nreverse result))))

(solve/proc)Code language: Lisp (lisp)

result という変数は、 push のたびに変わります。
また、繰り返し処理の中に、読み込みと判定と蓄積が混在しているため、動作を読むには、処理の途中でどんな状態にあるかを追う必要があります。
とくに、バグを再現するには、その時点の result の内容と、何行目まで読んだかを両方再現しなければいけません。

3.2. b. オブジェクト指向の解

オブジェクト指向では、データとその処理を「オブジェクト」としてまとめ、クラスとメソッドで責務を分けます4。

(defclass user ()
  ((name :initarg :name :reader user-name)
   (age  :initarg :age  :reader user-age)))

(defgeneric adult-p (entity))
(defmethod adult-p ((u user))
  (>= (user-age u) 18))

;;; 読み込みとオブジェクト生成が結合している
(defun read-user ()
  (let* ((line  (read-line))
         (space (position #\Space line)))
    (make-instance 'user
      :name (subseq line 0 space)
      :age  (parse-integer (subseq line (1+ space))))))

(defun solve/oop ()
  (let* ((n     (parse-integer (read-line)))
         (users (loop repeat n collect (read-user))))
    (format t "~{~a~^, ~}~%"
            (mapcar #'user-name
                    (remove-if-not #'adult-p users)))))

(solve/oop)Code language: Lisp (lisp)

adult-p や user-name は責務として分離できました。
ただし、 read-user が読み込みとオブジェクト生成を一体化しているため、テストするには標準入力を用意しなければいけません。
「フィルタしてから名前を取ってからフォーマットする」という合成の構造も、solve/oop の中に埋まったままです。

3.3. バグになる状態を探す大変さ

a と b は、見た目が違っても同じ問いを抱えています。
「状態をどう管理するか」です。

手続き型では result という変数が push のたびに変わります。
オブジェクト指向ではスロットに隠蔽されましたが、状態そのものは残ります。
つまり、solve/oop が正しく動くかどうかは、user オブジェクトが「正しい状態にある」ことが前提です。

この「状態」があると、バグの再現が難しくなります。
ある時点の状態を再現しないと、問題が起きた条件を再現できないからです。
同じ関数でも、呼ばれる順序によって結果が変わります。

4. 状態を持たない「関数」を組み合わせる

そこで、「時間の中で変化ずる状態をどう整理するか」から「状態なしでどう処理をつなぐか」への発想の転換が生まれます。

状態を管理するのではなく、状態を持たない関数を合成して、データを一方向に流す、という設計です。

純粋な「関数」は、「同じ入力には必ず同じ出力を返す」という性質を持ちます。
これを参照透明性（referential transparency）と言います。

計算機工学で生まれた「つなぐ」という発想を、圏論は、形式化する理論です。

4.1. c. 関数型の解

変換を小さい関数に分けて、直接合成する設計を考えます5。

;;; 純粋な関数（IO なし）
(defun parse-user (line)
  (let* ((space (position #\Space line))
         (name  (subseq line 0 space))
         (age   (parse-integer (subseq line (1+ space)))))
    (list :name name :age age)))

(defun adult-p (user)
  (>= (getf user :age) 18))

(defun user-name (user)
  (getf user :name))

;;; IO（端に寄せる）
(defun read-users ()
  (let ((n (parse-integer (read-line))))
    (loop repeat n collect (parse-user (read-line)))))

(defun solve/fp ()
  (format t "~{~a~^, ~}~%"
          (mapcar #'user-name
                  (remove-if-not #'adult-p (read-users)))))

(solve/fp)Code language: Lisp (lisp)

たとえば、parse-user は IO を持たない純粋な関数です。
文字列を渡せばテストできます。

;; テストが簡単
(parse-user "Alice 30")  ;; => (:NAME "Alice" :AGE 30)
(adult-p '(:name "Bob" :age 15))  ;; => NILCode language: Lisp (lisp)

ただし、solve/fp の処理の流れはまだ見えにくいです。
というのも、関数が入れ子構造（ネスト）になっているので、内側から外側へと読む形になっているからです。

4.2. c’. パイプ指向とUNIX哲学

小さな処理を組み合わせる、という発想は、1970年代のUNIXでも同じ結論に到達していました6。
それが「パイプ（pipe）」です。

awk 'NR==1{next} $2>=18{print $1}' | paste -sd ', ' -Code language: Bash (bash)

Douglas McIlroyの設計哲学は、2点に集約されます。
「一つのことをうまくやる小さなプログラムを作れ」と「出力が別のプログラムの入力になることを前提にせよ」です7。

これは、工学的な設計原則で関数型プログラミングの理論とは独立して生まれたが、重要なのは、大きなデータ構造（オブジェクト、データベース）を共有するのではなく、「テキストストリーム」という最小限の共通インターフェースを使い回したことです。

圏論の言葉を使えば、テキストストリームは対象（object）で、各コマンドは射（morphism）です。

awk は、名前と年齢の詳細を知りません。
paste は、年齢の意味を知りません。
それでも合成できる。

射の出力型と入力型が合えば合成できる、という性質をUNIXは実践しています。
関数型プログラミングでは、これを「関数合成」として形式化し、圏論がさらに「合成できるもの一般」として抽象化します。
つまり、ここに数学と計算機工学の落ち合うポイントがあるわけです。

5. 順序の管理から構造の保持へ

関数型には、まだ一つ問いが残っています。
それは、「関数の合成順序をどう管理するか」です。

手続き型では状態の管理がやっかいでした。
関数型はその問いを手放しましたが、代わりに「どの関数をどの順序で合成するか」という管理が必要になります。

solve/fp の中のネストを見ると、処理の順序が内から外に読む形で埋まっています。
関数の数が増えるほど、その順序の見通しは悪くなります。

圏論的には、この問いを構造として取り出します。
「どう合成するか」をラムダとして先に値に落としておき、適用は後回しにします。

;; c: 呼ぶたびに「フィルタ→名前→フォーマット」という手順が走る
(defun solve/fp () ...)

;; d: 「フィルタ→名前」という構造を値として持つ
(defparameter *adult-name-pipeline* (pipe *filter-adults* *extract-names*))
;; 適用はいつでも、どんなデータに対しても
(funcall *adult-name-pipeline* data)Code language: Lisp (lisp)

パイプラインが値として存在するということは、「どう組み立てるか」と「いつ実行するか」が切り離されています。

もとの対象 A から求める答え C へ至る変換では、「どの道を通ってもよい」のです。
圏論で言えば、可換図式が成り立つなら A から C へ行く経路が複数あっても、結果は同じになります。

5.1. d. 圏論的な解

圏論的な設計では、関数を合成する順序管理を「パイプラインという値」に閉じ込めることで、使う側は組み立て済みの構造を渡すだけにします8。

;;; 合成の道具
(defun pipe (&rest fns)
  (lambda (x)
    (reduce (lambda (v f) (funcall f v)) fns :initial-value x)))

(defun map-with (f)
  (lambda (xs) (mapcar f xs)))

(defun filter-by (pred)
  (lambda (xs) (remove-if-not pred xs)))

;;; 純粋な変換部品（IO なし）
(defparameter *filter-adults*
  (filter-by (lambda (u) (>= (getf u :age) 18))))

(defparameter *extract-names*
  (map-with (lambda (u) (getf u :name))))

;;; パイプライン（IO を含まない変換の構造）
(defparameter *adult-name-pipeline*
  (pipe *filter-adults* *extract-names*))

;;; IO は端に寄せる
(defun parse-user (line)
  (let* ((space (position #\Space line))
         (name  (subseq line 0 space))
         (age   (parse-integer (subseq line (1+ space)))))
    (list :name name :age age)))

(defun read-input ()
  (let ((n (parse-integer (read-line))))
    (loop repeat n collect (parse-user (read-line)))))

(defun write-output (names)
  (format t "~{~a~^, ~}~%" names))

;;; 実行（IO → 変換 → IO）
(defun solve/categorical ()
  (write-output (funcall *adult-name-pipeline* 
                         (read-input))))

(solve/categorical)Code language: Lisp (lisp)

*adult-name-pipeline* は IO を一切持ちません。
read-input と write-output が外側にあり、中央の変換は純粋なデータの流れです。

5.2. pipe は合成関数そのもの

高校数学で合成関数 f(g(x)) を習います9。
(pipe f g h) は、それを左から右の順に書いたものです。

数学での書き方：  h(g(f(x)))     （内側から外側へ読む）
pipe での書き方： (pipe f g h)   （左から右へ読む）

圏論の「射の合成」は、この「つなげられる」という性質を出発点にしています。

5.3. pipe は結合法則を満たす

pipe でつないだ関数は、どこで区切っても最終結果が変わりません。

;; どちらも同じ変換になる
(pipe (pipe *filter-adults* *extract-names*) another-step)
(pipe *filter-adults* (pipe *extract-names* another-step))Code language: Lisp (lisp)

これはモノイドの結合法則 (a + b) + c = a + (b + c) と同じ構造10です。
さらに、何もしない恒等関数 (lambda (x) x) が単位元に対応します。

(pipe *filter-adults* (lambda (x) x))  ; *filter-adults* と同じ
(pipe (lambda (x) x) *filter-adults*)  ; *filter-adults* と同じCode language: Lisp (lisp)

圏論が「合成できるもの」に注目するのは、結合法則と単位元の存在が、どこで区切っても全体の構造を保証するからです。

5.4. 「持ち上げる」とは何か

map-with が行っていることを図で見ると、こうなります。

単体への変換：  User  ──────────────►  Name
               Alice                  "Alice"

                          ↕  map-with が持ち上げる

リストへの変換：[User] ─────────────►  [Name]
               [Alice, Bob, Carol]     ["Alice", "Bob", "Carol"]Code language: CSS (css)

一人への変換と、リスト全体への変換が、同じ形で平行しています。
これが Functor（関手）の直感11です。
「中身を変換する関数を、箱ごと変換する関数に育てる」と読んでいいでしょう。

6. IOもデータにできる

6.1. e. 自由モナド的設計

さらに、一歩進んでIO を含む操作の記述ごとデータにしてしまう設計も考えられます。

read-input と write-output を「どう実行するか」をインタープリタとして後から差し込みます。

;;; 操作の記述（実行ではない。ただのデータ）
(defun adult-p (u) (>= (getf u :age) 18))

(defparameter *adult-name-program*
  '((:read-input)
    (:filter  adult-p)   ; 何でフィルタするか
    (:extract :name)     ; 何を取り出すか
    (:write-output)))    ; どこへ出すか（まだ決まっていない）

;;; インタープリタ1：本番（stdin / stdout）
(defun run/production (program)
  (reduce (lambda (data op)
            (ecase (first op)
              (:read-input   (read-input))
              (:filter       (remove-if-not (symbol-function (second op)) data))
              (:extract      (mapcar (lambda (x) (getf x (second op))) data))
              (:write-output (write-output data) data)))
          program
          :initial-value nil))

;;; インタープリタ2：テスト（IO なし）
(defun make-test-runner (test-data)
  (lambda (program)
    (let (output)
      (reduce (lambda (data op)
                (ecase (first op)
                  (:read-input   test-data)
                  (:filter       (remove-if-not (symbol-function (second op)) data))
                  (:extract      (mapcar (lambda (x) (getf x (second op))) data))
                  (:write-output (setf output data) data)))
              program
              :initial-value nil)
      output)))

;;; インタープリタ3：ロギング付き本番
(defun run/logging (program)
  (reduce (lambda (data op)
            (let ((result
                    (ecase (first op)
                      (:read-input   (read-input))
                      (:filter       (remove-if-not (symbol-function (second op)) data))
                      (:extract      (mapcar (lambda (x) (getf x (second op))) data))
                      (:write-output (write-output data) data))))
              (format *error-output* "[LOG] ~a => ~a~%" (first op) result)
              result))
          program
          :initial-value nil))Code language: Lisp (lisp)

*adult-name-program* はただのリストです。
:read-input が標準入力を意味するのか、テストデータを意味するのかは、インタープリタが決めます。

;;; 本番（stdin から読んで stdout へ）
(run/production *adult-name-program*)

;;; テスト（IO なし。同じプログラムをそのまま渡す）
(funcall (make-test-runner
           '((:name "Eve" :age 25)
             (:name "Frank" :age 16)
             (:name "Grace" :age 19)))
         *adult-name-program*)
;; => ("Eve" "Grace")

;;; ロギング付き本番（同じプログラムをそのまま渡す）
(run/logging *adult-name-program*)Code language: Lisp (lisp)

ここでの違いは、 :read-input と :write-output はプログラムの記述の一部で、「実際に何をするか」はインタープリタが注入していることです。

たとえば、Tauri や Electron などのGUIプログラムを作るなら、「ファイルを読む」「設定を保存する」「通知を出す」という記述はプログラムとして書いておき、本番では Tauri のコマンドを呼ぶインタープリタ、テストではメモリ上で動かすインタープリタを差し込む、という設計がそのまま対応します。

つまり、「IO の意味まで値に閉じ込めた」段階の設計も可能なのです。

6.2. 圏論的設計の核心

*adult-name-pipeline* は IO を含まない純粋な変換構造です。
read-input や write-output を変えることなく、パイプラインだけ差し替えられます。
また、IO を挟まずにテストデータを直接渡せます。

;; テストは IO なしで完結する
(let ((test-data '((:name "Eve" :age 25)
                   (:name "Frank" :age 16)
                   (:name "Grace" :age 19))))
  (funcall *adult-name-pipeline* test-data))
;; => ("Eve" "Grace")Code language: Lisp (lisp)

段階を追加するときも、既存の部品は変えません。

;; 名前に件数を付けて出力するパイプラインに拡張する
(defparameter *adult-name-with-count*
  (pipe *filter-adults*
        *extract-names*
        (lambda (names)
          (cons (format nil "~d件" (length names)) names))))

(write-output (funcall *adult-name-with-count* (read-input)))
;; => 2件, Alice, CarolCode language: Lisp (lisp)

map-with が Functor 的なのは、「単体への変換をリスト全体への変換に持ち上げる」からです12。
(lambda (u) (getf u :name)) は一人のユーザーへの変換で、map-with がそれをリスト全体への変換に変えます。
圏論はこの「持ち上げ」という操作を形式化しています。

変換を組み立てる順序が、読む順序と一致しています。
各変換は独立してテストでき、差し替えられます。
AIに「フィルタ条件を変えてください」と指示するとき、*filter-adults* だけ指せばよくなります。

  1. 元論文は “General Theory of Natural Equivalences”（1945）として Transactions of the American Mathematical Society に掲載されました。圏（category）、関手（functor）、自然変換（natural transformation）の概念がこの論文で初めて体系的に導入されています。 – General Theory of Natural Equivalences – nLab
  2. 具体的には代数的位相幾何（algebraic topology）における、位相空間に代数的構造（群など）を対応させる操作が繰り返し現れることがきっかけでした。Eilenbergらは1942年の “Group Extensions and Homology” の時点でこの発想を使っており、1945年論文はその抽象化です。 – Category Theory – Stanford Encyclopedia of Philosophy
  3. 型をプログラムの命題、プログラムをその証明と対応させる「Curry-Howard対応」をさらに圏論に拡張したものが「Curry-Howard-Lambek対応」です。型＝圏の対象、プログラム＝射、という対応はこの理論的背景に基づいています。 – Curry-Howard-Lambek correspondence – John D. Cook
  4. CLOSはCommon Lisp Object Systemの略で、1980年代後半にANSI標準化の一環として設計されました。多重ディスパッチと多重継承を持ち、クラス定義とメソッド定義が分離しているという点でC++やJavaのOOPシステムとは設計思想が大きく異なります。 – CLOS – Common Lisp Cookbook
  5. 関数を第一級オブジェクトとして扱う（他のデータと同様に渡したり返したりできる）という性質は、Alonzo Churchが1930年代に開発したラムダ計算を理論的な基盤としています。Common Lisp、Scheme、Haskell、OCamlなどの関数型言語はこの系譜に連なります。 – Lambda Calculus: The Bedrock of Functional Programming – Medium
  6. UNIXパイプを最初に提案したのはBell LabsのDouglas McIlroyで、1964年に「プログラムをホースのようにつなげるべき」というメモを書き残しています。実際にパイプがUNIXに実装されたのは1973年で、Ken Thompsonが一晩でpipe()システムコールとシェル統合を実装しました。 – Pipeline (Unix) – Wikipedia
  7. McIlroyはUNIX哲学として「プログラムは一つのことをうまくやれ。出力が別のプログラムへの入力になることを前提にせよ」と1978年のBell System Technical Journalに記しています。 – Unix Philosophy – Klara Systems
  8. 関数を第一級の値として扱い、変換を組み合わせて大きな処理を構成するこのスタイルは、関数型プログラミングの実践と圏論の設計思想が最も近づく点です。HaskellのFunctor・Applicative・Monadといった型クラスも同じ発想を型システムレベルで保証しています。 – Functor (functional programming) – Wikipedia
  9. 関数合成はラムダ計算の核心的な操作です。圏論の「射の合成」はこの概念を一般化したもので、対象と射さえ定義されれば、関数以外のもの（型変換、データ変換ルール、パーサーなど）も合成の対象として扱えます。 – Stanford Encyclopedia of Philosophy – Category Theory
  10. モノイドとは、結合的な二項演算と単位元を持つ代数的構造のことです。整数の加算（単位元は0）、文字列の連結（単位元は空文字列）、リストの連結（単位元は空リスト）、そして関数合成（単位元は恒等関数）はすべてモノイドです。 – Monoid – Wikipedia
  11. HaskellではFunctorは型クラスとして定義されており、fmap :: (a -> b) -> f a -> f b というシグネチャを持ちます。Functorは「構造を壊さずに中身を変換できる型」を表し、リスト・Maybe・IO・Promiseなど広範な型がこれに相当します。 – Functor – HaskellWiki
  12. Functorが満たすべき法則は2つあります。恒等関数をfmapしても構造が変わらないこと（identity law）と、2つのfmapの連続が合成したfmapと等しいこと（composition law）です。map-with はこれらを自然に満たします。 – Haskell/The Functor class – Wikibooks