A Calculus of Inheritance

이 논문은 레코드, 정의, 상속이라는 세 가지 원리를 기반으로 상속을 집합 합집합으로 모델링하여 다중 상속의 선형화 문제를 구조적으로 해결하고, $\lambda$- calculus 보다 더 높은 표현력을 갖는 선언적 프로그래밍의 기초가 되는 '상속 연산 (inheritance-calculus)'을 제시합니다.

핵심

이 논문은 **"상속 연산 (Inheritance Calculus)"**이라는 새로운 컴퓨터 과학의 기초 이론을 제안합니다. 쉽게 말해, **"복잡한 소프트웨어를 만드는 방식을 단순한 '레고 블록'처럼 바꾸자"**는 아이디어입니다.

기존의 프로그래밍 언어 (함수형) 가 **$\lambda$-계산 (Lambda Calculus)**이라는 수학적 기초 위에 세워졌다면, 이 논문은 선언형 프로그래밍 (설정 파일, 구성 관리 등) 을 위해 **'상속 연산'**이라는 새로운 기초를 제시합니다.

이 복잡한 내용을 일상적인 비유로 풀어보겠습니다.

---

1. 핵심 아이디어: 레고 블록의 '합치기' (Deep Merge)

기존의 프로그래밍 세계에서는 두 가지 큰 흐름이 있었습니다.

• 함수형 (Functional): "이 일을 하려면 이 함수를 호출해라." (명령어 중심)
• 선언형 (Declarative): "이런 상태가 되면 이렇게 해라." (설정 중심)

이 논문은 **"선언형 프로그래밍도 함수형처럼 수학적으로 완벽하게 설명할 수 있다"**고 주장합니다. 하지만 그 방식은 다릅니다.

비유: 레고 성 쌓기

• 기존 방식 (함수형): 레고 블록을 조립할 때, "A 블록 위에 B 블록을 올려라"라고 명령합니다. 하지만 A 와 B 가 겹치는 부분이 있으면, 누가 위에 올라갈지 정하기 위해 복잡한 규칙 (선형화, 우선순위) 이 필요합니다.
• 이 논문의 방식 (상속 연산): 레고 블록을 그냥 **"한 덩어리로 합친다"**고 상상해 보세요.
  • A 블록과 B 블록을 합치면, 겹치는 부분은 자연스럽게 하나로 융합됩니다.
  • 순서 상관없음: A+B 와 B+A 는 똑같은 결과입니다. (교환법칙)
  • 중복 제거: 같은 블록을 두 번 합쳐도 하나만 남습니다. (멱등성)
  • 결합법칙: (A+B)+C 는 A+(B+C) 와 같습니다.

이 논문은 **"상속 (Inheritance)"**을 단순한 **'집합의 합집합 (Set Union)'**으로 정의합니다. 즉, 두 개의 설정 파일을 합칠 때 충돌이 나면 "어느 게 우선?"이라고 고민할 필요가 없이, 두 가지 정보가 모두 살아남아 자연스럽게 합쳐진다는 것입니다.

2. 왜 이것이 혁신적인가? (3 가지 기적)

이 방식은 기존 프로그래밍에서 해결하기 어려웠던 세 가지 문제를 자연스럽게 해결합니다.

① "누가 먼저야?" 문제 해결 (다중 상속의 악몽)

• 상황: A 라는 클래스와 B 라는 클래스를 동시에 상속받으려는데, 둘 다 같은 기능을 가지고 있다면?
• 기존 (Java, Scala 등): "A 가 우선이야", "B 가 우선이야"라고 정해야 합니다. 이 규칙이 복잡해지면 프로그램이 엉망이 됩니다.
• 이 논문: "둘 다 가져!"라고 합니다. 두 정보가 합쳐져서 더 풍부한 기능을 만들어냅니다. 마치 두 개의 레고 성을 붙였을 때, 두 성의 특징이 모두 살아있는 거대한 성이 되는 것과 같습니다.

② "자기 자신"을 찾는 문제 (Self-Reference)

• 상황: "나 (Self)"를 참조할 때, 내가 여러 개의 부모를 가졌다면 누구를 가리키는 걸까요?
• 기존: "하나만 고르라"고 해서, 다른 경로를 버립니다.
• 이 논문: "모든 경로를 따라가라"고 합니다. 내가 여러 갈래의 길에서 온 것이라면, 그 모든 길에서 온 정보를 모두 모아서 '나'를 정의합니다. 이는 마치 여러 가지 배경을 가진 사람이 그 모든 배경을 모두 자신의 정체성으로 받아들여 더 강해지는 것과 같습니다.

③ "변경 불가능"과 "무한한 확장"

• 상황: 설정 파일을 한 번 만들면 수정하기 어렵거나, 새로운 기능을 추가하려면 기존 코드를 다 뜯어고쳐야 합니다 (Expression Problem).
• 이 논문: 설정 파일은 **고정된 상태가 아니라, 관찰자가 볼 때마다 조금씩 더 깊게 드러나는 '살아있는 나무'**입니다.
  • 새로운 기능을 추가하려면 기존 파일을 건드리지 않고, 새로운 파일을 만들어 "이 파일과 합쳐줘"라고 하면 됩니다.
  • 비유: 기존에 만든 레고 성을 부수지 않고, 옆에 새로운 레고 블록을 붙여 성을 더 크게 키우는 것과 같습니다.

3. 실생활 예시: NixOS 와 설정 파일

이 이론은 이미 NixOS라는 운영체제 설정 시스템에서 작동하고 있습니다.

• NixOS: 수만 개의 소프트웨어 패키지를 설정할 때, 서로 다른 파일들이 충돌하지 않고 자연스럽게 합쳐집니다.
• 이 논문의 설명: NixOS 가 왜 그렇게 강력하고 유연한지, 그 뒤에 숨겨진 수학적 원리가 바로 이 **'상속 연산'**이었다는 것을 증명했습니다.

4. 더 놀라운 점: 함수가 필요 없다?

이론적으로 **함수 (Function)**가 없어도 모든 계산을 할 수 있습니다.

• 기존: "함수 A 에 인자 B 를 넣어라" (Application)
• 이 논문: "함수 A 라는 레고 블록에 인자 B 라는 레고 블록을 합쳐라" (Inheritance)
• 결과: 함수 호출이라는 복잡한 개념이, 단순히 레고 블록을 합치는 것으로 대체됩니다. 함수는 사실 '상속'의 한 형태일 뿐입니다.

5. 결론: "모든 것이 연결된다"

이 논문은 **"상속 (Inheritance)"**이라는 개념을 단순한 객체 지향 프로그래밍의 기능을 넘어, **컴퓨터 과학의 새로운 기초 (Lambda Calculus 의 대안)**로 끌어올렸습니다.

• 핵심 메시지: 복잡한 소프트웨어를 만들 때, "누가 우선인가?"를 고민하지 말고, "모두 합쳐보자"는 태도를 취하면 됩니다.
• 일상적 비유:
  • 기존 프로그래밍은 전쟁처럼 "누가 이기나?"를 정하는 규칙이 필요했습니다.
  • 이 논문의 프로그래밍은 합창처럼 "모든 목소리가 섞여 더 아름다운 소리를 만든다"는 원리입니다.

이 방식은 설정 파일, 데이터베이스, 심지어 인공지능 모델의 구성까지도 더 유연하고 확장 가능하게 만들 수 있는 새로운 패러다임을 제시합니다.

기술 요약

이 논문은 Bo Yang (Figure AI Inc.) 이 저술한 **"A Calculus of Inheritance (상속의 미적분)"**으로, 선언적 프로그래밍 (Declarative Programming) 과 구성 언어 (Configuration Languages) 를 위한 새로운 계산 모델인 **상속 미적분 (Inheritance-calculus)**을 제안합니다.

논문은 함수형 프로그래밍의 기초인 $\lambda$-calculus 와 대조적으로, 객체, 메서드, 속성 등을 통합한 단일 추상화인 **레코드 (Record)**와 **상속 (Inheritance)**을 기반으로 한 새로운 이론적 틀을 제시하며, 이를 통해 표현력 (Expressiveness) 과 확장성 (Extensibility) 의 문제를 해결합니다.

다음은 논문의 상세 기술 요약입니다.

---

1. 문제 정의 (Problem Statement)

• 선언적 프로그래밍의 이론적 공백: 현대 소프트웨어 공학에서 NixOS, Jsonnet, CUE, Dhall 등 다양한 구성 및 선언적 언어가 널리 사용되고 있습니다. 특히 NixOS 모듈 시스템은 재귀적 속성 집합 병합과 고정점 (fixpoint) 의미론을 통해 매우 높은 표현력을 보여줍니다. 그러나 이러한 메커니즘이 왜如此 강력한지 설명하는 **계산 이론 (Computational Theory)**은 존재하지 않았습니다.
• 기존 계산 모델의 한계:
  • Turing Machine / RAM: 가변 상태 (Mutable state) 가 필요하여 불변성 (Immutability) 을 위반합니다.
  • $\lambda$-calculus: 1 등 함수 (First-class functions) 가 필수적이므로, 함수가 없는 순수 선언적 언어에는 적용하기 어렵습니다.
  • 표준 객체 지향 (OOP) 및 Mixin: 다중 상속 시 선형화 (Linearization) 문제 (예: C3 알고리즘 필요), 충돌 해결의 복잡성, 그리고 "Expression Problem(표현 문제)"을 해결하기 어렵다는 한계가 있습니다.
• 핵심 질문: 가변 상태도 없고, 1 등 함수도 없으며, 불변성 (Immutable) 을 유지하면서 튜링 완전 (Turing Complete) 한 계산 모델은 존재할 수 있는가?

2. 방법론 (Methodology)

저자는 NixOS 모듈 시스템의 동작 원리를 분석하여 이를 세 가지 기본 원시 연산으로 축소하고, 이를 **상속 미적분 (Inheritance-calculus)**으로 정립했습니다.

2.1 세 가지 원시 연산 (Primitives)

$\lambda$-calculus 가 (추상화, 적용, 변수) 를 사용하는 것처럼, 상속 미적분은 다음 세 가지를 기반으로 합니다:

1. Record (레코드): {} 형태의 중괄호로 둘러싸인 요소들의 집합.
2. Definition (정의): ℓ ↦→ e 형태로 속성을 정의.
3. Inheritance (상속): ℓup.this.ℓdown... 또는 ↑n.ℓdown... 형태로 다른 레코드의 속성을 참조하고 병합.

2.2 핵심 메커니즘: 심층 병합 (Deep Merge)

• 상속 = 집합 합집합 (Set Union): 상속은 단순한 덮어쓰기가 아니라, 중첩된 구조까지 재귀적으로 병합하는 **심층 병합 (Deep Merge)**으로 정의됩니다.
• 대칭성: 상속은 교환법칙 (Commutative), 멱등성 (Idempotent), **결합법칙 (Associative)**을 만족합니다. 이로 인해 다중 상속 시 순서나 충돌 해결을 위한 복잡한 선형화 알고리즘이 불필요해집니다.
• 의미론 (Semantics): 계산은 관찰자 (Observer) 가 트리 내의 경로를 질의 (Query) 함으로써 수행됩니다. 6 개의 상호 재귀적인 1 차 함수 (First-order functions) 로 정의되며, 이는 **고정점 (Least Fixed Point, lfp)**으로 계산됩니다.

2.3 $\lambda$-calculus 와의 관계

• 임베딩: $\lambda$-calculus 를 상속 미적분으로 매핑하는 변환 (Translation) 을 제시했습니다. $\lambda$-추상화는 '인수 (argument)'와 '결과 (result)' 슬롯을 가진 레코드로, 함수 적용은 해당 레코드를 상속받는 것으로 변환됩니다.
• Böhm Tree 대응: 변환된 프로그램의 수렴 (Convergence) 은 원래 $\lambda$-항의 Böhm Tree 와 정확히 대응됩니다.

3. 주요 기여 (Key Contributions)

1. 상속 미적분 (Inheritance-calculus) 제안: 선언적 프로그래밍을 위한 최소 계산 모델을 제시했습니다. 클래스, 메서드, 객체, 속성을 단일 'Mixin' 추상화로 통합합니다.
2. Expression Problem (표현 문제) 의 해결:
   • 기존 시스템 (Scala, NixOS 등) 은 새로운 데이터 타입과 연산을 동시에 추가할 때 (확장성) 한계가 있었습니다.
   • 상속 미적분은 심층 병합을 통해 기존 파일을 수정하지 않고도 새로운 연산과 데이터 타입을 독립적인 파일로 추가하여 자동으로 통합할 수 있습니다.
   • 이는 **비확장성 (Nonextensibility) 에 대한 면역 (Immunity)**을 제공합니다.
3. 1 차 의미론 (First-order Semantics) 과 고정점 수렴:
   • $\lambda$-calculus 의 고차 의미론 (Higher-order semantics) 대신, 경로와 경로 집합에 대한 1 차 집합 논리로 의미론을 정의했습니다.
   • 발산 (Divergence) 의 해결: $\lambda$-calculus 에서 무한 루프로 발산하는 재귀 프로그램 (예: let x = x in x) 이라도, 상속 미적분의 고정점 계산 (lfp(T_P)) 을 통해 정의되지 않은 값으로 수렴할 수 있음을 보였습니다.
4. 관계적 의미론 (Relational Semantics) 의 출현:
   • 단순한 산술 연산이나 불리언 논리를 구현할 때, 상속의 집합적 성질 (Set-valued resolution) 로 인해 자동으로 **관계 대수 (Relational Algebra)**나 Datalog의 동작 (예: 카르테시안 곱, 조인) 이 구현됩니다.
   • 하나의 코드가 단일 값 연산과 집합 값 연산 모두에 대해 동일한 의미론을 가집니다.
5. 함수 색상 맹목 (Function Color Blindness):
   • 동기/비동기 실행 환경 (Async/Sync) 을 구분하는 "함수 색상" 문제가 상속을 통한 의존성 주입으로 해결됩니다. 비즈니스 로직은 추상 슬롯만 정의하고, 실행 시점에 구체적인 구현을 상속받아 채우므로 동일한 코드가 여러 런타임에서 실행 가능합니다.

4. 결과 및 실험 (Results)

• MIXINv2 구현: 논문의 이론을 바탕으로 Python 으로 구현된 MIXINv2를 공개했습니다.
• Case Study (Nat Arithmetic):
  • 자연수 (Nat), 덧셈 (Plus), 등호 (Equal) 를 별도의 파일로 정의하고 상속하여 조합했습니다.
  • 1 + 2와 3 + 4를 동시에 처리하는 테스트에서, 단일 값 연산이 자동으로 **카르테시안 곱 (Cartesian Product)**인 {4, 5, 6}을 생성하여 논리 프로그래밍의 관계적 의미론을 증명했습니다.
  • 기존 파일을 수정하지 않고 새로운 연산 (Equal) 과 데이터 타입 (Boolean) 을 추가하여 Expression Problem 을 성공적으로 해결했습니다.
• 다중 경로 자기 참조 (Multi-path Self-reference):
  • Scala 나 NixOS 모듈 시스템에서는 다중 상속 경로가 겹칠 때 "충돌"로 간주하여 에러를 발생시킵니다.
  • 반면, 상속 미적분은 this 가 여러 경로를 통해 해결될 수 있으며, 모든 경로의 속성이 집합 합집합으로 병합되므로 충돌 없이 자연스럽게 작동합니다.

5. 의의 및 결론 (Significance)

• 표현력의 비대칭성: 상속 미적분은 $\lambda$-calculus 를 포함하지만, $\lambda$-calculus 는 상속 미적분의 핵심 기능 (열린 확장성, 다중 경로 상속) 을 매크로로 표현할 수 없습니다. 따라서 **Felleisen 의 기준에 따라 상속 미적분이 $\lambda$-calculus 보다 엄격하게 더 표현력 (Strictly More Expressive)**이 있습니다.
• 새로운 프로그래밍 패러다임:
  • "함수는 상속의 문법적 당근 (Syntactic Sugar)"이라는 관점을 제시합니다.
  • 구성 언어 (Configuration Language) 가 단순한 데이터 처리를 넘어, 튜링 완전한 계산 모델로서 운영체제, 클라우드 인프라, 복잡한 애플리케이션을 구성할 수 있는 이론적 기반을 마련했습니다.
• 실용적 적용: NixOS 생태계의 성공 사례를 이론적으로 설명하고, 이를 확장하여 더 넓은 범위의 선언적 프로그래밍 언어 설계에 지침을 제공합니다.

요약하자면, 이 논문은 "상속"을 단순한 코드 재사용 기법이 아닌, 집합론적 심층 병합을 기반으로 한 강력한 계산 원리로 재정의함으로써, 불변성과 함수 부재 하에서도 튜링 완전성을 유지하고 표현 문제와 확장성 문제를 근본적으로 해결하는 새로운 프로그래밍 패러다임을 제시합니다.