🔢 mathematics

Bidirectional Interpolation for the Lambda-Calculus -- Revisiting and Formalising Craig-Čubrić Interpolation

이 논문은 양방향 타입 체킹 원리를 기반으로 크라그-추브리치 보간 정리에 대한 새로운 증명을 제시하고, 이를 Rocq 에서 형식화합니다.

원저자: Meven Lennon Bertrand, Alexis Saurin

게시일 2026-03-04

📖 4 분 읽기🧠 심층 분석

원저자: Meven Lennon Bertrand, Alexis Saurin

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

이 논문은 **"논리학과 프로그래밍의 비밀스러운 다리"**를 찾는 여정에 대한 이야기입니다.

제목이 좀 어렵게 들리지만, 핵심은 아주 간단합니다. **"A 라는 사실에서 B 라는 결론이 나왔다면, A 와 B 가 공통으로 가진 '중간 다리'를 찾아낼 수 있다"**는 것입니다. 이 다리를 **인터폴란트 (Interpolant)**라고 부릅니다.

이 논문은 이 '다리'를 찾을 때, 단순히 논리식만 보는 게 아니라 그 논리를 증명하는 과정 (코드나 수학적 증명) 자체를 보존하면서 다리를 만드는 새로운 방법을 제시하고, 이를 컴퓨터가 직접 검증할 수 있도록 정리했습니다.

이 복잡한 내용을 일상적인 비유로 풀어서 설명해 드릴게요.

1. 배경: "왜 중간 다리가 필요할까?"

상상해 보세요.

A(출발지): "나는 사과를 가지고 있다."
B(도착지): "나는 과일을 먹는다."

논리적으로 A 에서 B 로 가는 길은 명확합니다. 하지만 만약 이 두 문장 사이에 완전히 새로운 단어가 섞여 있다면 어떨까요? 예를 들어, "나는 사과를 가지고 있다"에서 "사과"라는 단어를 빼고 "과일"이라는 단어로 바로 연결하는 건 불가능하죠.

**크레이그 보간법 (Craig Interpolation)**은 이 두 문장 사이를 이어주는 **공통된 언어 (여기서는 '과일'이라는 개념)**로 이루어진 중간 문장을 찾아내는 규칙입니다.

중간 다리 (I): "나는 과일을 가지고 있다."
A(사과) → I(과일) → B(과일 먹기)

이게 왜 중요할까요? 컴퓨터 과학에서는 복잡한 시스템의 한 부분이 다른 부분과 어떻게 연결되는지, 혹은 어떤 데이터가 어떻게 변형되는지 분석할 때 이 '중간 다리'를 찾아내면 시스템을 모듈화하거나 버그를 찾는 데 큰 도움이 됩니다.

2. 문제: "예전에는 다리가 너무 복잡하고 추했다"

과거의 연구자들은 이 다리를 찾을 때, 증명 과정 (A 에서 B 로 가는 구체적인 단계) 을 무시하고 결과물만 뽑아냈습니다. 마치 지도에서 출발지와 도착지만 찍고, 그 사이에 어떤 길이 있는지 대충 그리는 것과 비슷합니다.

하지만 이 논문 (레논 - 베르랑과 사우린) 은 **"아니, 그건 안 돼! 우리가 A 에서 B 로 가는 구체적인 발걸음 (증명 과정) 을 그대로 유지하면서 다리를 만들어야 해!"**라고 주장합니다.

증명 관련 (Proof-relevant): A 에서 I 로 가는 발걸음과, I 에서 B 로 가는 발걸음을 이어붙이면, 원래 A 에서 B 로 가던 발걸음과 완벽하게 일치해야 합니다.

이전 연구자 (Čubrić) 가 이걸 성공적으로 증명했지만, 그 방법이 너무 복잡하고 지저분했습니다. 마치 미로에서 헤매다가 우연히 길을 찾은 것처럼, "이건 저건 비슷하니까 생략하자"라고 넘긴 부분들이 실제로는 완전히 달랐기 때문입니다.

3. 해결책: "양방향 타이핑 (Bidirectional Typing) 이라는 나침반"

저자들은 이 복잡한 미로를 해결하기 위해 **'양방향 타이핑'**이라는 새로운 나침반을 사용했습니다.

비유:
- 기존 방식: "이 길이 맞나? 일단 가보자. (추측)" -> 틀리면 다시 돌아오기.
- 양방향 타이핑: "이 길은 이런 목적으로만 쓰인다 (입력) / 이 길은 이런 결과를 내야 한다 (출력)"를 미리 정해놓고 길을 찾습니다.

이 논문은 **"정상적인 상태 (Normal Form)"**에 있는 코드나 증명들을 이 나침반으로 분류하면, 다리를 찾는 과정이 훨씬 깔끔하고 직관적임을 발견했습니다. 마치 레고 블록을 조립할 때, 어떤 블록이 '입력'용이고 '출력'용인지 미리 구별해 두면 조립이 훨씬 쉬워지는 것과 같습니다.

4. 성과: "컴퓨터가 직접 검증한 완벽한 지도"

저자들은 이 새로운 방법을 **Rocq(로크)**라는 컴퓨터 증명 보조 도구를 이용해 코드로 작성했습니다.

첫 번째 성과: 수학적 증명을 컴퓨터가 100% 검증할 수 있도록 정리했습니다. (인간의 실수를 없앰)
두 번째 성과: 기존에 복잡했던 증명 과정을 훨씬 간결하고 아름다운 논리로 재구성했습니다.
세 번째 성과: '교환 변환 (Commuting Conversions)'이라는 복잡한 규칙을 포함해도 이 방법이 작동함을 증명했습니다. (이는 레고 블록을 조립할 때, 블록 순서를 바꿔도 최종 모양이 같다는 것을 보장하는 것과 같습니다.)

5. 결론: 왜 이 논문이 중요한가?

이 논문은 단순히 "다리를 찾았다"는 것을 넘어, "다리를 찾는 과정 자체가 원래의 논리와 완벽하게 일치하도록" 만드는 방법을 제시했습니다.

일상적인 비유:
이전에는 A 에서 B 로 가는 길에서 "중간 지점"만 대충 표시해 주었습니다. 하지만 이 논문은 **"A 에서 출발해서 중간 지점을 거쳐 B 에 도착하는 전체 여정 (버스 노선도) 을 그대로 보여주면서, 그 중간 지점이 A 와 B 의 공통 언어로만 이루어져 있음을 증명"**했습니다.

이 연구는 향후 소프트웨어의 안전성을 검증하거나, 복잡한 AI 모델의 의사결정 과정을 해석할 때, "어떤 공통된 원리만 공유하면 시스템이 안전하게 작동한다"는 것을 수학적으로 엄밀하게 증명하는 데 큰 기여를 할 것입니다.

한 줄 요약:

"복잡한 논리 증명 과정에서, 출발지와 도착지를 잇는 '공통된 다리'를 찾을 때, 원래의 여정 (증명 과정) 을 잃어버리지 않고도 깔끔하게 찾을 수 있는 새로운 지도를 그렸고, 컴퓨터가 그 지도의 정확성을 모두 확인해 주었습니다."

이 논문은 이중 방향 타이핑 (Bidirectional Typing) 원리를 기반으로 합 (Sum) 과 공집합 타입을 포함한 단순 타입 람다 계산식 (STLC+) 에 대한 크레이그 보간 정리 (Craig Interpolation Theorem) 를 재검토하고 공식화한 연구입니다. 저자들은 Čubrić 의 기존 증명 (Proof-relevant interpolation) 을 개선하고, 이를 Rocq 증명 보조도구 (Rocq proof assistant) 를 사용하여 형식화했습니다.

주요 내용은 다음과 같습니다.

1. 연구 배경 및 문제 제기

크레이그 보간 정리: 논리적 함의 $A \vdash B$ 가 성립할 때, $A$ 와 $B$ 의 공통 개념만을 사용하여 구성된 중간 논리식 $I$ 가 존재하여 $A \vdash I$ 와 $I \vdash B$ 가 성립한다는 정리입니다.
증명 관련성 (Proof-relevance): 기존 보간 정리는 논리식 자체에 초점을 맞췄지만, 최근에는 증명 (또는 람다 항) 의 구조를 보존하는 '증명 관련' 버전이 강조되고 있습니다. Čubrić 은 STLC+ 에서 $x:A \vdash t:B$ 인 경우, $A$ 와 $B$ 의 공통 원자 타입으로 구성된 타입 $C$ 와 항 $u, v$ 를 찾아 $t$ 가 $(\lambda y. v) u$ 로 환원되도록 하는 증명을 제시했습니다.
기존 증명의 한계: Čubrić 의 원래 증명은 항의 크기에 대한 귀납법을 사용했으나, 증명이 복잡하고 일부 경우 (Subcase 6.3.2) 가 논리적으로 명확하지 않았습니다. 또한, 합 (Sum) 타입이 포함된 경우 $\beta$ -정규형만으로는 '부분식 속성 (subformula property)'을 보장할 수 없어, 교환 변환 (commuting conversions) 을 통한 정규화가 필요했습니다.

2. 방법론

저자들은 기존의 복잡한 귀납법을 대체하기 위해 이중 방향 타이핑 (Bidirectional Typing) 과 정규형 (Normal Forms) 의 관계를 재정의하여 새로운 증명 전략을 수립했습니다.

이중 방향 타이핑과 정규형의 연결:
- 논리학의 '부분식 속성'은 증명에서 새로운 공식을 '발명'하지 않고 기존 정보만 흐름을 따르는 특성을 의미합니다. 이는 타입 이론에서 이중 방향 타이핑 (추론과 검사) 의 정보 흐름 특성과 일치합니다.
- 저자들은 STLC+ 의 정규형 (Normal forms) 과 중립형 (Neutral forms) 을 이중 방향 타이핑 규칙으로 명시적으로 정의했습니다. 이는 기존 Prawitz 의 정규형 특징을 현대적인 귀납적 구조로 재해석한 것입니다.
교환 변환 (Commuting Conversions) 의 도입:
- 합 (Sum) 타입과 공집합 타입 ( $\bot$ ) 이 포함된 경우, 단순한 $\beta$ -환원만으로는 부분식 속성을 가진 정규형을 얻기 어렵습니다. 따라서 저자들은 교환 변환 (예: if 문이나 raise 문이 다른 연산자 위로 이동하는 규칙) 을 추가하여 정규화를 수행했습니다. 이는 biCCC (bi-cartesian closed categories) 의 등식 이론에 대한 유일한 대표자를 보장하지는 않지만, 보간 증명에 필요한 부분식 속성을 확보합니다.
논리적 관계 (Logical Relations) 를 통한 정규화 증명:
- 모든 잘 타입된 항이 정규형으로 환원됨을 증명하기 위해, Abel 과 Sattler 의 작업을 참고하여 논리적 관계 기법을 사용했습니다. 특히 양의 타입 (positive types) 에서의 중립형 처리를 위해 'Covering' 개념을 도입하여 정규화 정리를 증명했습니다.

3. 주요 기여 (Contributions)

새로운 증명 및 형식화: Čubrić 의 증명 관련 보간 정리를 이중 방향 타이핑을 기반으로 한 더 직관적이고 구조화된 귀납법으로 재증명했습니다. 이 증명은 Rocq 에서 완전히 형식화되었습니다.
STLC+ 의 메타이론 정립: 교환 변환을 포함하는 STLC+ 에 대한 정규화 (Normalization) 정리를 최초로 형식화했습니다. 이는 기존에 형식화되지 않았던 중요한 메타이론적 결과입니다.
정규형과 이중 방향 타이핑의 관계 규명: 합 타입이 있는 경우에도 이중 방향 타이핑이 부분식 속성을 가진 정규형과 자연스럽게 대응됨을 보였습니다. (기존에는 합 타입에서 이중 방향 타이핑이 깨진다는 오해가 있었으나, 이는 두 가지 다른 정규형 개념의 혼동에서 비롯된 것임을 지적했습니다.)
자동화 도구 활용 및 한계 분석: Rocq 에서 AutoSubst2 및 Sulfur 플러그인 등을 사용하여 치환 (substitution) 계산과 타입 체킹을 자동화하는 과정에서 얻은 경험과 한계 (속도, 불완전성 등) 를 상세히 논의했습니다.

4. 주요 결과

정리 22 (상수 없는 보간): 주어진 $x:A \vdash t:B$ 에 대해, $A$ 와 $B$ 의 공통 어휘로 구성된 타입 $M$ 과 항 $l, r$ 이 존재하여 $t \equiv r[l..]$ 가 성립함을 증명했습니다.
정리 25 (상수 포함 보간): 언어에 상수 (constants) 와 방정식이 포함된 경우에도 보간 정리가 성립함을 보였습니다.
형식화 성과: 약 4,000 줄의 코드 (AutoSubst 생성 코드 포함) 로 증명과 정규화 정리를 성공적으로 형식화했으며, 컴파일 시간이 약 30 초로 매우 효율적이었습니다.

5. 의의 및 향후 과제

의의:
- 이 논문은 증명 관련 보간 정리를 람다 계산식 (Natural Deduction 스타일) 에서 명확하게 정립하고 형식화한 최초의 사례 중 하나입니다.
- 이중 방향 타이핑이 단순한 타입 체킹 알고리즘을 넘어, 논리적 구조 (부분식 속성) 를 이해하고 증명을 구성하는 강력한 도구임을 보여주었습니다.
- 복잡한 교환 변환을 포함한 정규화 정리를 형식화함으로써, 합 타입이 있는 람다 계산식의 이론적 기반을 강화했습니다.
향후 과제:
- 비정규항 (Non-normal terms) 에 대한 보간: 현재 증명은 정규형에 국한되어 있습니다. 교차 (Cut) 가 포함된 항에 대해 보간 정리를 확장하는 것이 중요한 과제입니다.
- 균일 보간 (Uniform Interpolation): 특정 증명에 의존하지 않고, 주어진 타입에 대해 일관된 보간자를 생성하는 '균일' 버전의 증명 관련 보간 정리를 연구할 계획입니다.
- 의존 타입 (Dependent Types) 으로 확장: 의존 타입 이론으로의 확장을 모색하고 있으나, 의존 타입에서의 교환 변환 문제 (Convoy pattern 등) 를 해결해야 하는 어려움이 있습니다.

요약하자면, 이 논문은 이중 방향 타이핑이라는 현대적인 타입 이론 도구를 활용하여 고전적인 크레이그 보간 정리를 증명 관련 (Proof-relevant) 관점에서 재해석하고, 이를 Rocq를 통해 엄밀하게 형식화한 중요한 연구입니다.