A Calculus of Inheritance

この論文は、レコード、定義、継承という 3 つの原始概念に基づき、継承を集合の和としてモデル化することで多重継承の線形化問題を構造的に解消し、$\lambda$ 計算よりも表現力に優れた宣言的プログラミングの基礎となる「継承計算」を提唱しています。

要約

継承の計算論：プログラミングの「レゴブロック」革命

この論文は、**「継承計算論（Inheritance-calculus）」**という新しいプログラミングの考え方を提案するものです。

一言で言うと、「関数（計算）」という概念を捨てて、「記録（データ）」と「継承（重ね合わせ）」だけで、どんな複雑な計算もできてしまうという驚くべき発見です。

これを理解するために、いくつかの身近な例えを使って説明しましょう。

---

1. 従来の考え方：「レシピ（関数）」の世界

これまでのプログラミング（関数型プログラミング）では、計算は**「レシピ」**のように考えられていました。

• 関数（λ）： 「材料（引数）を渡せば、料理（結果）を作る」という指示書。
• 適用： 材料をレシピに渡して、料理を作る。

これは非常に強力ですが、少し複雑で、指示書自体を「データ」として扱うのが難しい側面がありました。

2. 新しい考え方：「レゴブロック」の世界

この論文が提案する「継承計算論」では、世界は**「レゴブロック」**でできています。

• 記録（Record）： 穴が開いたブロック。
• 定義（Definition）： ブロックに「ネジ」や「突起」をつけること。
• 継承（Inheritance）： ブロックを「重ねて」くっつけること。

魔法の「重ね合わせ」

ここで重要なのが、この「重ね合わせ」のルールです。

• 順序は関係ない（可換）： A を B に乗せても、B を A に乗せても、同じ完成品になります。
• 重複は消える（冪等）： 同じブロックを 100 回重ねても、1 回重ねたのと同じです。
• グループ化も自由（結合）： (A+B)+C も A+(B+C) も同じです。

つまり、**「継承」は単なる「セットの和（足し算）」**なのです。
これにより、従来のプログラミングで頭を悩ませてきた「多重継承の順序問題（どっちのルールを優先するか？）」というバグが、最初から存在しなくなります。

---

3. なぜこれがすごいのか？

① 「計算」が「データ」になる

このシステムでは、「関数」は「レゴブロックの組み合わせ」に過ぎません。

• 関数を作る ＝ 入力用の穴と出力用の穴があるブロックを作る。
• 関数を呼ぶ ＝ 入力用の穴に別のブロックを「継承（重ね）」て、結果を出力用の穴から取り出す。

驚くべきことに、この「レゴブロック」だけで、チューリング完全（どんな計算も可能）な世界が作れてしまいます。つまり、「関数」という特殊な道具はもう不要で、「データを重ねる」だけで万能な計算機が作れるのです。

② 「遅延評価」と「無限」の解決

従来の計算では、無限に続く計算（ループ）は「止まらない（発散する）」とみなされます。
しかし、この「継承計算論」では、「観察者」がどこまで見たいかを決めるという考え方（遅延評価）を使います。

• 「無限のリスト」があっても、あなたが「最初の 3 つだけ見たい」と言えば、システムは最初の 3 つだけ計算して返します。
• さらに、このシステムでは、従来の計算では「無限ループで止まってしまう」プログラムが、「固定点（安定した状態）」として収束して答えを出せるという不思議な現象が起きることが証明されています。

③ 「拡張問題」の解決

プログラミングでよくある「新しい機能を追加したいけど、既存のコードを書き換えたくない」という悩み（Expression Problem）が、このシステムでは**「構造上、不可能」**になります。

• 既存のブロックに新しい突起（機能）を「重ねる」だけで、新しい機能が追加されます。
• 既存のブロックを壊したり、書き換えたりする必要はありません。
• しかも、誰かが作ったブロック A と、別の人作ったブロック B を重ねても、衝突せずに自然に融合します。

---

4. 具体的な例：足し算と論理

論文では、このシステムで「自然数の足し算」や「論理演算」を実装しています。

• 数値は木（ツリー）： 数字「3」は、木のような構造で表現されます。
• 足し算は「木の結合」： 「2」と「3」を足すとき、システムはそれぞれの木を「重ね合わせ」ます。
• 驚きの結果： 単一の数字の足し算だけでなく、「集合」の足し算も自動的にできてしまいます。
  • {1, 2} + {3, 4} を計算すると、自動的に {4, 5, 6} という「すべての組み合わせ」が返ってきます。
  • これは、「論理プログラミング（データベース検索のようなもの）」の仕組みが、普通の足し算の中に自然に現れていることを意味します。

---

5. まとめ：なぜこれが重要なのか？

この論文は、「プログラミングの基礎」を再定義しようとしています。

• 従来の世界： 「計算（関数）」が主役で、「データ」は従者。
• 新しい世界： 「データ（記録）」と「重ね合わせ（継承）」が主役で、「計算」はそれらの結果として自然に生まれる。

これは、「設定ファイル（JSON や YAML）」をただのデータとして扱うのではなく、それ自体が「計算プログラム」になるような世界です。
NixOS（Linux のディストリビューション）のような複雑なシステム設定や、大規模なソフトウェア構成管理において、この「重ね合わせ」の考え方はすでに使われていますが、この論文は**「なぜそれがこんなに強力なのか」を数学的に証明し、その背後にある美しい原理を解き明かしました。**

「関数」を捨てて「継承」だけで世界を構築する。
それは、レゴブロックをただ重ねるだけで、複雑な城や宇宙船が自動的に組み上がってしまうような、魔法のような世界です。

技術概要

論文「A Calculus of Inheritance」の技術的サマリー

本論文は、Bo Yang 氏によって提案された**「継承計算（Inheritance-calculus）」**という、宣言的プログラミングのための新しい計算モデルを提示するものです。関数型プログラミングの基礎が $\lambda$ 計算（抽象化、適用、変数の 3 つのプリミティブ）であるのと同様に、宣言的プログラミングの基礎として、レコード、定義、継承の 3 つのプリミティブのみからなる計算体系を構築しました。

以下に、問題意識、手法、主要な貢献、結果、そしてその意義について詳細にまとめます。

---

1. 背景と問題意識 (Problem)

現代のソフトウェア工学において、NixOS モジュール、Jsonnet、CUE、Dhall などの構成言語や宣言的言語は、構造化データの継承やマージを通じて広く利用されています。特に NixOS のモジュールシステムは、再帰的な属性セットのマージと不動点意味論を用いて非常に高い表現力を持っていますが、その背後にある計算理論は未解明でした。

従来の計算モデルには以下の課題がありました：

• チューリング完全性、不変性、関数の不在の同時満たし:
  • ターニングマシンや RAM 機械は可変状態を必要とする。
  • $\lambda$ 計算は第一級関数を必要とする。
  • 宣言的言語は「値の不変性」と「第一級関数の不在」を特徴とするが、これらを満たしつつチューリング完全な計算モデルは存在しないと考えられていた（表の空欄）。
• 多重継承の線形化問題: オブジェクト指向やミックスインベースのシステムでは、多重継承時のメソッド解決順序（線形化）が複雑で、競合や非決定性を引き起こす。
• 表現問題（Expression Problem）: 既存のデータ型や操作を、既存のコードを変更せずに拡張することが困難である。

2. 手法とアプローチ (Methodology)

著者は、NixOS モジュールシステムの実践からインスピレーションを得て、これを最小のプリミティブに還元するアプローチを取りました。

• 3 つのプリミティブ:
  1. レコード（Record）: {} で囲まれた要素の集合。順序や重複は意味を持たない（集合論的）。
  2. 定義（Definition）: label ↦→ expression によるプロパティの定義。
  3. 継承（Inheritance）: 参照によるスコープ階層のナビゲーションとプロパティの投影。
     • 名前付き形式（Foo.this.field）とインデックス付き形式（↑n.field、de Bruijn 索引）の 2 種類。
• 継承の定義: 継承を集合の和（Set Union）としてモデル化します。これにより、継承は可換、冪等、結合の性質を持ちます。
• 意味論（Semantics）:
  • 観測的意味論を採用。計算は、観測者がツリー内のパスをクエリすることで駆動されます。
  • 6 つの相互再帰的な第一階の方程式（properties, supers, overrides, bases, resolve, this）で定義されます。
  • 関数空間や高階構造を含まず、パスとパスの集合のみを扱う**第一階（First-order）**の記述です。
  • 意味論は**不動点（lfp）**として定義され、Kna ster-Tarski の定理により一意に定まります。
• MIXINv2: この計算論理を実装した Python 言語「MIXINv2」を開発し、ブール論理、自然数算術、Web アプリケーションなどの実装を通じて検証しました。

3. 主要な貢献 (Key Contributions)

1. 継承計算（Inheritance-calculus）の提案:
   宣言的プログラミングのための最小計算モデルを確立し、クラス、メソッド、オブジェクト、プロパティを単一の「ミックスイン（レコード）」抽象で統一しました。
2. 多重継承問題の構造的排除:
   継承が深さ優先の深マージ（Deep Merge）として定義されるため、線形化アルゴリズム（C3 など）が不要になります。競合する定義があっても、集合和として統合されるため、競合エラーが発生しません。
3. 第一階の意味論と $\lambda$ 計算への埋め込み:
   • $\lambda$ 計算を継承計算へ 5 つの局所的な規則でマクロ展開（翻訳）できることを示しました。
   • これにより、遅延 $\lambda$ 計算は継承計算の部分言語として表現可能となり、$\lambda$ 計算のボーム木（Böhm tree）等価性が、パスクエリに基づく第一階の意味論で記述可能であることを証明しました。
4. 表現の非対称性（Expressive Asymmetry）:
   継承計算は遅延 $\lambda$ 計算よりも厳密に表現力が高いことを示しました（Felleisen の基準）。$\lambda$ 計算では区別できない項を、継承計算のコンテキスト（オープン拡張による新しい観測プロジェクションの追加）で区別できるためです。
5. 表現問題への免疫と関係的意味論:
   • 既存のコードを変更せずに新しいデータ型や操作を追加できる「表現問題への免疫」を構造的に実現しました。
   • 通常の算術演算が、Church 符号化された値をトライ（Trie）構造として扱い、その操作が自動的にデカルト積（Cartesian product）となり、論理プログラミング（Datalog）の関係的意味論を自然に実現することを示しました。

4. 結果と知見 (Results)

• 実装の検証: MIXINv2 において、ブール論理、自然数算術、Web アプリケーションを実装し、すべてのテストを機械的に検証しました。
• 関数の色の盲目性（Function Color Blindness）: 同じ MIXINv2 コードが、同期実行と非同期実行（asyncio）の両方で変更なしに動作することを示しました。これは、継承による依存性注入が、関数の副作用（色）を抽象化するためです。
• 自己参照の解決: 自己参照（this）が単一のオブジェクトではなく、複数のパス（多重継承経路）に解決されることを実証しました。Scala や NixOS モジュールシステムでは「競合する基底型」エラーとなるようなパターンも、継承計算では集合和として自然に処理されます。
• 発散と収束: $\lambda$ 計算で発散する再帰プログラム（例：let x = x in x）が、継承計算の不動点評価（lfp）においては収束する（未定義として扱われる）場合があることを示しました。

5. 意義と将来展望 (Significance)

• 宣言的プログラミングの理論的基盤: 関数型プログラミングにおける $\lambda$ 計算に相当する、宣言的プログラミングの基礎理論を提供しました。
• 構成言語の進化: NixOS や Jsonnet などの既存の構成言語の背後にある直感的な「マージ」のメカニズムを、形式的かつ厳密な計算モデルとして定式化しました。
• 新しいプログラミングパラダイム: 「関数」を「継承」の糖構文として捉え直すことで、可変状態や第一級関数なしでチューリング完全な計算を実現し、拡張性と安全性を両立する新しい言語設計の指針となりました。
• 応用可能性: 設定管理、パッケージ管理、ドメイン固有言語（DSL）、そして論理プログラミングの実装など、多岐にわたる分野での応用が期待されます。

総じて、本論文は「継承」という概念を単なるオブジェクト指向の機能ではなく、計算そのものの基盤として再定義し、宣言的プログラミングの理論的成熟を大きく前進させた画期的な研究です。