당신이 거대하고 혼란스러운 영화 촬영장의 감독이라고 상상해 보십시오. 배우들(코드)은 장면을 연기해야 하지만, 영화가 촬영되는 동안 대본도 함께 쓰이고 있습니다. 때로는 내일 촬영할 장면(미래의 코드)을 써야 할 때도 있고, 때로는 지금 배우가 들고 있는 소품(현재의 코드)을 집어 들어 그 미래의 장면에 넣어야 할 때도 있습니다. 이것이 바로 **다단계 프로그래밍(Multi-Stage Programming, MSP)**의 세계입니다. 이는 컴퓨터 과학자들이 다른 프로그램을 생성하는 프로그램을 작성할 수 있게 함으로써 믿을 수 없을 정도로 효율적이고 유연한 소프트웨어를 만드는 방법입니다.

하지만 이 과정은 까다롭습니다. 과거에는 이 "미래의 장면"이 "현재의 소품"과 어떻게 상호작나할지에 대한 규칙이 다소 경직되어 있었습니다. 한 세트의 규칙은 "미래의 장면은 완전히 독립적이어야 하며, 현재의 어떤 것도 건드려서는 안 된다"라고 말했습니다. 또 다른 규칙은 "미래의 장면은 오직 바로 다음 순간만을 볼 수 있다"라고 말했습니다. 그러나 실제 세계의 프로그래밍은 훨씬 더 복합적인 것을 필요로 합니다. 예를 들어, 특정 시점의 특정 변수를 과거의 특정 순간으로부터 직접 가져와 사용할 수 있는 미래의 장면이 필요할 수도 있습니다. 기존의 규칙들은 이러한 "교차 단계 지속성(cross-stage persistence)"이 어떻게 작동하는지 설명하려 할 때 시스템의 논리를 깨뜨리지 않고는 불가능했습니다.

이 논문은 이를 해결하기 위해 **유계 모달 논리(Bounded Modal Logic, BML)**라는 새로운 논리 규칙을 도입합니다. BML을 우리 영화 촬영장의 매우 정밀한 지도이자 새로운 규칙 책이라고 생각하십시오. BML은 단순히 "미래"나 "현재"라고 말하는 대신, 세트장의 모든 위치에 고유한 이름표("분류기")를 부여합니다. 감독이 미래의 장면을 작성할 때, 이제 "이 장면은 특정하게 명명된 위치로부터의 소품을 사용하는 것이 허용된다"라고 명시적으로 말할 수 있으며, 동시에 시간 순서를 준수할 수 있습니다. 저자들은 이 새로운 시스템이 수학적으로 건전하며(모순이 발생하지 않음), 완전하다(모든 유효한 시나리오를 설명할 수 있음)는 것을 증명합니다. 또한 이 새로운 시스템이 기존의 더 단순한 규칙 책들을 완벽하게 모방하면서도, 기존의 규칙들이 손댈 수 없었던 복잡하고 무질서한 사례들을 처리할 수 있음을 보여줍니다. 요컨대, 그들은 코드가 정확히 필요한 것을 얻기 위해 시간과 공간을 가로질러 안전하게 도달할 수 있는 논리적 토대를 마침내 구축했습니다.

문제: "시간 여행" 코드의 딜레마

이것이 왜 중요한지 이해하기 위해, 코드가 보통 어떻게 구축되는지 살펴봅시다. 당신이 집을 짓는 프로그램을 작성하고 있다고 가정해 봅시다. 당신은 벽에 대한 지침을 작성하는 "청사진 생성기"를 가질 수 있습니다. 표준 프로그래밍에서 일단 청사진이 작성되면, 그것은 정적인 종이 조각에 불과합니다. 하지만 다단계 프로그래밍에서 청사진 생성기는 그 자체로 실행되는 프로그램이며, 나중에 실행될 새로운 코드를 생성할 수 있습니다.

과거에는 이를 처리하는 두 가지 주요 방식이 있었습니다:

1. "닫힌 상자" 접근법 (S4 논리): 당신이 집의 청사진을 완전히 밀봉된 상태로 작성한다고 상상해 보십시오. 그것은 현재 작업실에 있는 어떤 도구나 재료도 사용할 수 없습니다. 스스로 자급자족해야 합니다. 이는 안전성 측면에서는 훌륭하지만, 제한적입니다. "지금 내가 들고 있는 망치를 사용하라"고 말할 수 없기 때문입니다.
2. "다음 단계" 접근법 (LTL 논리): 당신은 타임라인의 바로 다음 단계만을 볼 수 있습니다. "다음 장면에서 망치를 사용하라"고 말할 수는 있지만, 세 단계 전의 장면으로 거슬러 올라갈 수는 없습니다.

그러나 실제 프로그래밍의 세계는 더 복잡합니다. 때때로 당신은 나중에 실행될 코드(청로)를 작성하지만, 그것은 바로 지금의 스코프(scope)에서 정의된 변수를 사용해야 합니다. 이것을 **교차 단계 지속성(Cross-Stage Persistence, CSP)**이라고 부릅니다. 이것은 마치 미래의 자신에게 보내는 편지에 "내가 지금 들고 있는 열쇠를 사용하여 문을 열어라"라고 쓰는 것과 같습니다.

문제는 기존의 논리 체계들이 이를 처리할 수 없었다는 점입니다. 기존 체계들은 "스코프"(변수가 존재하는 곳)와 "단계"(코드가 실행되는 시점)를 별개의 것으로 취급했습니다. 만약 이 둘을 섞으려고 하면 논리가 깨지게 됩니다. 이 논문은 기존 시스템들이 3차원 물체를 2차원 그림만으로 설명하려고 하는 것과 같다고 주장합니다. 즉, 코드 의존성이 실제로 어떻게 작동하는지에 대한 깊이를 놓치고 있다는 것입니다.

해결책: 스코프에 이름 붙이기

저자 Yuito Murase와 Akinori Maniwa는 **유계 모달 논리(BML)**를 제안합니다. 핵심 아이디어는 간단하지만 강력합니다: 모든 스코프에 이름을 붙여라.

기존 시스템에서 코드는 단순히 "나는 미래에 있다"라고 말할 수 있습니다. BML에서 코드는 "나는 미래에 있지만, 구체적으로 *'주방'*이라는 이름의 스코프로부터 접근하는 것이 허용된다"라고 말합니다.

그들은 특수 기호인 □⪰𝛾를 도입하는데, 이를 "허가증"이라고 생각하면 됩니다.

• **□**는 "이것은 나중에 실행될 코드"임을 의미합니다.
• **⪰**는 "에 의해 유계됨" 또는 "에 의존함"을 의미합니다.
• 𝛾(감마)는 특정 스코프의 이름(예: "주방" 또는 "거실")입니다.

따라서 □⪰𝛾A는 다음과 같이 번역됩니다: "이것은 타입 A의 코드로서 나중에 실행되지만, 명시적으로 𝛾라는 이름의 스코프에 있는 변수를 사용하는 것이 허용된다."

이 작은 추가가 모든 것을 바꿉니다. 이것은 의존성을 명시적으로 만듭니다. 변수가 어디에서 왔는지 추측하는 대신, 타입 시스템(규칙 책)은 미래의 코드가 어떤 스코프를 만질 수 있는지 정확히 알게 됩니다.

작동 원리: 크립키 맵 (Kripke Map)

이것이 작동함을 증명하기 위해, 저자들은 **이관계 크립키 구조(Birelational Kripke Structure)**라는 수학적 구조를 사용합니다. 이것이 무섭게 들린다면, 다층 맵이라고 생각하십시오.

• 레이어 1 (스코프 중첩): 방들이 다른 방 안에 어떻게 포함되어 있는지를 보여줍니다. "주방"은 "집" 안에 있습니다. 이것은 가계도와 같습니다.
• 레이어 2 (단계 전이): 시간의 흐름을 보여줍니다. "현재"는 "나중"으로 이어집니다.

기존의 맵에서는 이 두 레이어가 분리되어 있었습니다. 당신은 시간 속에서 앞으로 나아갈 수는 있었지만, 자신이 어떤 "방"에 있는지 쉽게 파악할 수는 없었습니다. BML 맵에서는 이 레이어들이 연결되어 있습니다. "현재"에서 "나중"으로 이동할 때, 맵은 당신이 어떤 "방"(스코프)을 들여다볼 수 있는지 정확히 추적합니다.

저자들은 이 맵에 대해 두 가지 큰 사실을 증명합니다:

1. 건전성(Soundness): 만약 당신이 BML의 규칙을 따른다면, 코드가 존재하지 않는 변수를 사용하려고 시도하는 상황에 결코 빠지지 않을 것입니다. 즉, 안전합니다.
2. 완전성(Completeness): 만약 어떤 코드가 논리적으로 가능하다면(실제 세계에서 말이 된다면), BML은 그것을 설명할 수 있습니다. 맵에 "빈틈"은 없습니다.

"분류기"의 마법

이 논문은 **분류기(classifiers)**라고 불리는 것을 도입합니다. 이것들은 단지 스코프의 이름일 뿐입니다. 저자들은 또한 이러한 이름들에 대해 양화사(예: "모든")를 사용할 수 있음을 보여줍니다.

당신이 일반적인 사용 설명서를 작성하고 있다고 상상해 보십시오. 대신 "주방에 있는 망치를 사용하라"고 말하는 대신, "집 안에 있는 어떠한 방이라도 그 안에 있는 망치를 사용하라"고 말할 수 있습니다. BML에서 이것은 ∀𝛾1 :⪰𝛾2와 같이 나타납니다. 이는 "스코프 𝛾2 안에 있는 임의의 스코프 𝛾1에 대하여..."를 의미합니다.

이를 통해 프로그래머는 믿을 수 없을 정도로 유연한 코드를 작성할 수 있습니다. 당신은 코드를 생성하는 함수를 작성할 수 있고, 그 생성된 코드는 중첩 규칙을 준로하는 한, 그것이 최종적으로 어떤 특정 스코프에 처하게 되더라도 작동할 수 있습니다.

이것이 미래에 의미하는 바

이 논문은 단순히 새로운 아이디어를 제안하는 데 그치지 않고, 이를 둘러싼 완전한 시스템을 구축합니다. 그들은 다음을 만들었습니다:

• 자연 연역 시스템(Natural Deduction System): 이 논리에 대해 증명하기 위한 일련의 규칙들.
• 커리-하워드 계산법(Curry-Howard Calculus): 이러한 논리적 증명을 실제 컴퓨터 프로그램(람다 계산법)으로 변환하는 방법.
• 단계적 의미론(Staged Semantics): 코드가 실제로 어떻게 단계별로 실행되는지 시뮬레이션하여 오류가 발생하지 않도록 보장하는 방법.

그들은 자신들의 새로운 시스템이 기존의 S4 및 LTL 시스템이 할 수 있는 모든 것을 수행할 수 있을 뿐만 아니라, 까다로운 "교차 단계 지속성"까지 처리할 수 있음을 보여주었습니다. 이것은 자전거에서 비행할 수 있는 자동차로 업그레이드하는 것과 같습니다. 기존 시스템들도 여전히 유효하지만, 이제는 이 더 크고 강력한 시스템의 특수한 사례가 되었습니다.

저자들은 자신들이 단순히 이 방식이 작동한다고 "제안"한 것이 아니라, 수학적으로 **"증명"**했다는 점을 매우 신중하게 명시합니다. 그들은 시스템이 일관적이며(모순이 없고), 항상 실행을 완료하며(무한 루프에 빠지지 않음), 타입을 보존한다(코드가 안전하게 유지됨)는 것을 보여주었습니다.

요약

결국, 이 논문은 컴퓨터 과학의 오래된 수수께끼를 해결합니다: 어떻게 하면 미래의 코드가 과거를 안전하게 참조하도록 할 것인가?

모든 스코프에 이름을 붙이고 미래의 코드가 어떤 이름을 접촉할 수 있는지 명시적으로 기술함으로써, 저자들은 엄격하면서도 유연한 논리적 프레임워크를 만들었습니다. 이것은 마치 모든 배우에게 이름표를 주고, "다음 장면에서 '밥'이라는 이름의 배우와 대화할 수 있지만, '앨리스'와는 안 된다"라고 명시된 대본을 주는 것과 같습니다. 이는 혼란을 방지하고, 제작 과정을 안전하게 유지하며, 훨씬 더 복잡하고 흥eli로운 이야기를 들려줄 수 있게 합니다.

이 논문은 **유계 모달 논리(Bounded Modal Logic)**를 차세대 프로그래밍 언어의 견고한 토대로 확립하여, 우리가 코드가 코드를 작성하게 될 때, 그 코드가 시간적으로나 공간적으로 얼마나 멀리 이동하든 상관없이 모든 조각이 정확히 어디에 속해 있는지 알 수 있도록 보장합니다.