RosettaLens LogoRosettaLens

Rust 공유 참조의 해적 기반 논리

ko생성일: 2025. 9. 16.갱신일: 2025. 10. 26.

스코프드 제네릭을 실험적으로 구현하는 과정에서, 가변 참조에서 공유 참조로의 기계적 변환과 그에 깔린 선형 논리(특히 ⅋와 ? 연결자)의 역할을 탐구한다. 해적질(허용되지 않은 복제) 개념으로 공유 참조를 재해석하고, Rc/Arc의 ‘지분’, 얕은 스냅샷의 한계, 참조 위 트레이트, 패킹된 타입, 그리고 Rust에 해적질을 도입할 때의 잠재적 장단점을 논의한다.

원문: http://ais523.me.uk/blog/logic-of-shared-references.html

URL: http://ais523.me.uk/blog/logic-of-shared-references.html

Title: Rust 공유 참조의 해적 기반 논리

Tags: rustprogrammingmemorymathematics | 작성자: Alex Smith, 2025-09-14

Contents

Introduction

이전 스코프드 제네릭에 관한 블로그 글에서, 기존 기법으로는 제대로 풀 수 없는 Rust 언어의 문제를 짚었고, 새 언어 기능이 필요하다는 결론을 내렸다. 그래서 스코프드 제네릭을 Rust에 정식 제안할 생각이었다. 이 글은 그 기능 자체가 주제라기보다는, 일반적으로 새 기능의 세부를 가다듬는 과정, 그리고 그 과정에서 알게 된 흥미로운 발견을 주로 다룬다.

새 기능의 디테일을 제대로 잡는 데 신경을 쓰는 이유는, 기능이 채택될 가능성도 높이고, 채택된 뒤 실제로 쓸모 있을 가능성도 높이기 위해서다. Rust 언어 설계 팀도 비슷한 상황에 자주 놓이는데, 세부를 잘 정리하기 위해 “실험적 기능 게이트” 프로세스를 사용한다. 이 과정은 기능을 실험적으로 구현해 보고 아이디어의 타당성과 세부를 검증하게 해준다. 나는 숙련된 Rust 기여자가 아니라서, 그 과정을 직접 쓸 수는 없다. 그렇다고 비슷한 시도를 스스로 해보지 말라는 법은 없다. 공식 컴파일러 저장소가 아니어도 구현을 시도하며 배울 수 있는 것들이 분명히 있다!

그래서 이미 스코프드 제네릭 구현 실험에 착수했다. 아직 완성되진 않았지만, 스코프드 제네릭뿐 아니라 Rust 전반에 관해서도 여러가지를 가르쳐 주었다. 그리고 그 중 하나는 너무도 근본적이고 놀라워서, 하던 일을 멈추고 이 글을 먼저 쓰게 만들었다.

그 통찰은 대부분의 Rust 프로그래머에게 익숙한 현상에 관한 것이다. “Rust 표준 라이브러리의 함수/메서드/타입 상당수는 두 번 써야 한다. 하나는 공유 참조로, 다른 하나는 가변 참조로.” 그리고 이 통찰은 두 부분으로 나뉜다:

  1. 두 번 써야 하는 함수/타입/메서드의 경우, 가변 참조 버전에서 공유 참조 버전을 기계적으로 도출하는 번역이 존재한다.
  2. 그 번역에는 잘 정립된 수학적 구조가 있다. 바로 선형 논리(linear logic)의 타입 이론을 따른다(선형 논리는 1987년에 고안된 수학적 도구로, 이후 프로그래밍 언어의 타입 시스템을 설명하는 데 자주 쓰여 왔다). 다만 여기서의 선형 논리 사용은 일반적이지 않다. 대부분의 PL 타입 이론은 선형 논리의 일부 조각(fragment)만 채택하는데, 우리가 다루는 번역은 흔히 쓰이는 조각 밖에 있다.

이 글의 주된 목표는 a) Rust의 관련 부분, b) 프로그래밍 언어 관점에서의 선형 논리의 거의 전부에 가까운 관련 부분, c) 둘의 연결 고리를 설명하는 것이다. 이 통찰들이 Rust를 더 쉽게 추론하게 해주고, 어쩌면 Rust가 고생하는 공유/가변 이중 구현을 줄이는 데도 도움이 되길 바란다.

그리고 그 과정에서, Copy하면 안 되는 것들을 잔뜩 복사하게 될지도 모른다.

Starting the experiment

먼저 지난 글을 안 읽은 분을 위해 내가 무엇을 하려는지 간단히 요약한다. Rust의 “상수 제네릭(const generic)”은 컴파일 타임 상수 숫자 등으로 타입을 매개변수화하는 기법이다. 예컨대 Rust의 “배열”(슬라이스/벡터와 구분되는)은 길이가 컴파일 타임에 알려져 있고, [i32; 4]와 [i32; 8]은 상수 제네릭이 달라서 서로 다른 타입이다. 스코프드 제네릭은 컴파일 타임 상수가 아닌 값(숫자가 아닐 수도)을 가지고 비슷한 일을 하게 해준다. 다만 조건이 있다. a) 타입 매개변수는 변수에 저장되어야 하고, b) 그 변수를 스코프에서 벗어나게 하거나 값을 바꾸기 전에, 해당 변수를 매개변수로 쓰는 모든 값은 버려야 한다. 즉, 그 타입의 관점에서 보면 매개변수는 “사실상 상수”다(값이 바뀌기 전에 그 값을 담은 값들이 이미 사라지니까). 상수 제네릭은 값의 동등성을 컴파일 타임에 비교하는 반면, 스코프드 제네릭은 “같은 변수에 저장되었는가”로 동일성을 본다.

새 언어 기능을 실험한다는 장점은, 완성된 구현을 즉시 내놓을 필요가 없다는 것이다. 실험에서는 a) 문법이 썩 좋지 않아도 되고, b) 모든 경우에 동작하지 않아도 되지만, 실제로 유용한 충분한 사례들에서 돌아가기만 하면 된다. 게다가 나는 Rust 컴파일러를 직접 빌드해 본 적이 없고, 내 컴퓨터는 그럴 메모리/디스크가 부족할 것 같다. 그래서 컴파일러를 바꾸기보다 라이브러리로 실험하기로 했다. 기능의 모든 면을 구현하진 못하겠고 문법도 나빠지겠지만, 더 쉽고 빠르게 결과를 얻을 수 있다.

이 방식은 또 하나의 어려운 문제를 피해갈 수 있게 해준다. 스코프드 제네릭은 지역 변수에 대한 타입 시스템 수준의 참조(reference)다. 즉 완성형은 지역 변수와 동일한 스코프 동작을 지원해야 한다(재귀 호출마다 새 스코프드 제네릭을 만든다). 실험으로는 더 단순한 구현을 택했다(현 Rust에서는 완전판이 불가능할 수도 있으니). 프로그램의 각 사용 지점마다, 해당 지역 변수의 참조를 그 지점 전용 전역 변수에 저장하고(실행 중에), 스코프드 제네릭을 그 전역 변수 참조를 하드코딩한 Rust 타입으로 표현한다. 이건 재진입 불가(re-entrant가 아님)다. 즉 멀티스레드나 재귀 코드에서는 제대로 동작하지 않으니 최종 언어 기능 구현으로는 부적절하다. 하지만 실험에는 충분하다. 스레드 하나, 재귀 없음인 프로그램 중에도 이 기능이 유용할 사례는 많고, 평가용으로 쓸 수 있다.

스코프드 제네릭을 Rust 타입으로 나타내면, 타입 체크는 Rust의 기존 타입 체커에 맡길 수 있다(이미 타입 매개변수의 동일성은 잘 판단한다). 즉 실험에서 작성할 코드가 아주 많이 줄어든다. 그래도 필요한 건 있다. 스코프드 제네릭을 쓰는 타입의 값이, 제네릭 값보다 오래 살 수 없다는 규칙을 구현해야 하고, 매개변수 값을 접근하는 방법도 만들어야 한다(단, 수명 내에서만). 둘 다 같은 수명에 묶인다. 즉 “수명을 가지며, 그 수명 동안 특정 전역 변수의 값을 접근하게 해주는 것” 같은 타입이 필요하다. 이런 값 하나를 나는 “Thing A”라고 부르겠다.

Thing A 하나면 스코프드 제네릭을 거의 구현할 수 있다. a) 그 제네릭을 가진 타입에 Thing A를 내장하고, b) 그 타입을 “어느 Thing A를 쓰는지”로 파라미터화하면 된다(각 Thing A는 다른 전역 변수에 묶이니까). 못 하는 건 두 가지다. a) 재진입적으로 쓰이는 코드에서 올바른 초기화, b) 기존 값에 기대지 않는 Default 같은 트레이트 구현. 그래도 기능 평가와 배움에는 충분하다.

그렇다면 Thing A는 정확히 무엇인가? 수명이 있고, 그 수명 동안 어떤 곳에 저장된 값을 접근하게 해주며, 아마 Copy여야 한다(그래야 다른 Copy 것들 안에 내장 가능). 참조 대상이 Sync가 아니면 Send가 될 수 없다. 여기까지만 보면 Rust의 공유 참조와 아주 비슷하다. 하지만 크기가 0이어야 한다(스코프드 제네릭의 목표 중 하나가, 많은 객체가 같은 것을 참조하되 객체마다 메모리를 추가로 쓰지 않는 것). Rust의 공유 참조는 포인터로 표현되므로 0바이트가 아니다. 즉 Thing A는 “주소를 저장하지 않고, 주소를 하드코딩한” 수동 구현 공유 참조다.

여기까지는 순조로웠다. 이 생각에 이르자, 나는 공유 참조를 수동으로 구현하기 시작했다. 사실상 Rust의 기존 공유 참조를 재현하되, 주소만 하드코딩하는 식이다. 그리고 전역 변수에 값을 저장하는 코드도(재진입 불가를 체크하는 안전한 방식으로) 구현했다. 바로 그때 배움이 시작됐다.

Lots and lots of references

이 글의 핵심은 “공유 참조의 수동 구현”에 있다. 하지만 먼저 전역 변수에 저장하는 코드를 보며 문제를 이해하는 편이 쉽다. 스코프드 제네릭의 스코프에 들어가면, 그 값에 무언가를 대입해야 한다. 하지만 우리는 Rust를 쓰고 있으므로, 전역 변수에 “그냥” 대입할 수 없다. 빈번히 불안전해지기 때문이다. 대신 전역 변수를 셀(cell) 타입으로 감싸야 한다. 즉 가변 참조 없이도 쓰기를 허용하는 타입으로 감수하고, 그 타입의 규칙을 통해 안전성을 증명해야 한다. (초기의 Rust는 unsafe 블록에서 전역 변수에 직접 쓰는 것을 허용했고, 지금도 하위 호환성 때문에 가능하지만, 요즘은 UnsafeCell 사용이 선호된다. 같은 연산을 지원하면서 언어 나머지와 일관된 API를 제공한다.)

표준 라이브러리에 이 목적에 적합해 보이는 셀 타입은 세 가지뿐이다:

  • Mutex. 의미론은 괜찮다. 하지만 효율적으로 쓰려면 런타임에 빌린 비전역 값인 MutexGuard에 0바이트 참조를 만들어야 한다. 내가 아는 한 이를 해결하는 유일한 방법은 스코프드 제네릭인데, 아쉽게도 자기 자신을 구현하는 데 쓸 순 없다. 비효율적 해법으로는 매 접근마다 Mutex를 잠그는 방법이 있지만, 실험이라 해도 과도한 오버헤드다. (또한 #[no_std]에서도 동작해야 하는 타입 시스템 기능 특성상, 최종 구현에서는 뮤텍스를 쓰기 어렵다. 그래도 실험 단계에서는 괜찮을 수 있다.)

  • AtomicPtr. 수명 정보를 기억하지 못하는 점이 어색하다. 수명을 수동으로 추적해야 해서 실수하기 쉽다. 그래도 Sized 객체의 참조를 저장한다면 거의 맞아떨어진다. 참조 자체를 저장하는 건 괜찮다(한 단계 간접화일 뿐). 하지만 Sized 제약은 불필요해 보인다. 실험은 제약이 꼭 필요한지 알아보는 과정이니, 최종 구현에서 피할 수 있음을 보지 못했다면 가급적 제약을 두지 말아야 한다.

(이 글을 쓰다 보니, 간접 참조를 한 단계 더 두면 Sized 제약을 없앨 수도 있겠다는 생각이 스쳤다. 하지만 불필요한 두 단계 간접화를 쓰고 싶진 않다.)

  • UnsafeCell. 무엇이든 저장할 수 있다(우리 목적에 완벽하다). 대신 재진입적으로는 안전하지 못하다. 우리는 애초에 재진입적으로 쓰지 않을 계획이라 완벽히 맞는다. 안전성을 위해, 코드가 재진입적으로 쓰이지 않음을 “검사”해야 하는데, 이건 간단하다. UnsafeCell이 현재 사용 중인지 알기 위한 AtomicBool 하나면 충분하고, 성공 시 이를 기억해 둘 MutexGuard-유사(0바이트 가능) 객체를 같이 두면 된다.

여기서는 UnsafeCell이 최선이다. 동시 접근이 없음을 보장하는 안전한 추상화로 감싸고, 첫 용도에 쓰는 중에 두 번째 용도로 쓰려 하면 패닉 나게 만들면 된다. 이렇게 나온 추상화는 의미론이 RefCell과 거의 동일하지만, Sync라는 점이 다르다. 이름은 뻔히 SyncRefCell이겠다. (표준 라이브러리에 이 추상화를 제공하지 않는 이유는, 멀티스레드 코드에서 경쟁이 생길 때마다 패닉이 나서 사실상 쓸모가 없기 때문일 것이다. 멀티스레드 코드에 거의 쓸 수 없다면 Sync로 만드는 의미가 없다. 하지만 전역 변수는 Sync여야 하므로, 난 이 추상화가 필요했다.)

이제 SyncRefCell 내부에 대한 0바이트 공유 참조를 수동으로 구현하려면 무엇이 필요할지 보자(이때부터 필요한 다양한 “참조 비슷한 타입”의 개수를 세겠다). 먼저, 0바이트 객체에서 셀의 “바깥” 주소를 얻는 방법이 필요하다(1). 이는 전역 변수에 대한 참조를 Deref로 돌려주는 0바이트 타입이면 된다. 다음으로, 바깥에서 셀의 “안”으로 들어갈 방법이 필요하다(2). 셀 내부에 접근하게 해주는 동시에 “내가 그 셀을 소유함”을 기억하는 0바이트 구조체가 필요하다(소유 참조는 읽기/쓰기가 가능해야 하고, 다른 참조는 패닉을 일으켜야 하니, 둘을 구분해서 기억할 타입이 필요하다). 이건 표준 라이브러리의 MutexGuard나 cell::RefMut와 비슷하고 구현은 그리 어렵지 않다. 0바이트의 바깥 참조를 내장하고, 평범한 PhantomData 수명 마커를 더하면 된다. 다만 이 타입은 소멸자(destructor)가 필요하다(참조가 더 이상 없을 때 잠금을 해제해야 하므로). 따라서 복사 가능하면 안 되고(그럼 소멸자가 두 번 돈다), 내부에 대한 가변 참조로만 쓸 수 있다. 그러니 MutexGuard와 같은 것을 “나눠 가진” 조각을 나타내는 또 다른 타입이 필요하다(3). 타입 2에 대한 공유 참조와 동일한 의미론이되, a) 0바이트이고 b) Deref에 한 단계 더의 간접이 생기지 않아야 한다.

다음 문제는 UnsafeCell 안에 어떤 타입을 넣을지다. 참조를 담고 싶다. 이때 참조의 타입은 “대부분” 알고 있지만, 수명은 모른다(스코프드 제네릭을 만드는 코드가 루프에서 돌면 매번 다른 객체를 가리킬 수 있고, 수명이 서로 소거되므로 참조 수명이 달라진다). 지난 글을 쓸 땐 이 지점 때문에 전역 변수 기법이 비현실적이라고 생각했지만, 해결책이 있다. 참조 자체와 참조 대상의 수명을 제외하면 같은 참조 타입끼리는 크기와 정렬이 같다. 그러니 초기화되지 않은 적절한 크기/정렬의 메모리 블록을 만들고, 이를 변환(transmute)해 다양한 타입으로 해석하면 된다. (사실 그 메모리 블록을 다른 데서 안 쓴다는 걸 안다면, 안전한 코드에서도 변환할 수 있다. 한 타입의 미초기화 인스턴스는, 같은 크기/정렬의 다른 타입의 미초기화 인스턴스로 해석해도 안전하기 때문이다.) 따라서 MaybeUninit 안에 포인터 크기만큼의 메모리가 필요하다. 이를 특정 타입의 MaybeUninit처럼 해석하는 “변환된 참조”를 만들어야 한다(4). 그런 다음 초기화됨을 추적해야 한다(안전하게 역참조하려면). 그래서 초기화 상태를 기록하는 MutexGuard-유사 참조가 더 필요하다(5). 원래의 0바이트 참조들을 만들려면, 각 참조는 이 가드 유사 참조를 내장해야 하므로, 가변 역참조는 못 하지만 복사 가능한 버전이 필요하다(6). 그런데 이를 구현하다 보면, 타입 6이 타입 4를 내장해야 한다는 사실을 발견한다. 하지만 타입 4는 배타적 접근에 의존해 변환의 안전성을 보장하므로 복사할 수 없다. 그래서 쓰기 기능 없이 복사 가능한 변형이 또 필요하다(7). (타입 7은 같은 변환으로만 접근됨을 알기에, 안전하게 변환할 수 있다.)

이 모든 걸 갖추고 나면, 타입 6을 내장하고 두 번 역참조해 실제 객체에 닿는 0바이트 참조 하나만 더 만들면 된다(8). 이것이 바로 스코프드 제네릭 구현을 가능케 하는 Thing A다. 가변판도 만들 수 있었겠지만, 더 이상 참조 구현을 쓰고 싶지 않아 만들지 않았다.

그리고 이쯤에서 좋은 프로그래머라면 생각을 시작해야 한다. 같은 코드 조각을 작은 변형만 달리한 채 8번이나 썼다. 이때 떠올라야 할 생각은 다음과 같다(덜 유익한 것부터 더 유익한 것 순서로):

  • 에디터로 자동화할 수 있나?
  • 매크로로 자동화할 수 있나?
  • 라이브러리로 처리할 수 있나?
  • 설계를 바꿔서 이 작업 자체가 필요 없게 할 수 있나?
  • 사용하는 언어를 개선해서 이 작업 자체가 필요 없게 할 수 있나?

(하면 안 되는 것: AI 코딩 도우미에게 맡기는 것. 일반적으로도, 같은 작업을 다시 해야 할 때 쓸 신뢰할 수 있는 지침이 남지 않으므로 유지보수성이 떨어진다. 또한 반복/동일 부분을 매번 펼쳐 쓰게 되어 가독성과 편집 가능성이 떨어지고, 공통 부분을 한데 모으는 대신 곳곳에 복제하게 된다. 특히 이 사례는 일부 미묘한 수명 관련 unsafe 코드가 들어 있어, 틀리면 테스트로 드러내기 어려운 불안전성이 생긴다. 수명 과다의 모든 경우에 대해 각각 별도의 ````compile_fail` 테스트를 써야 할 텐데, 그 경우의 수 나열법조차 모르겠다.)

일반적으로 목록 뒤쪽의 선택지가 앞쪽보다 낫다. a) 컴파일러가 코드의 정합성을 검증해 줄 수 있는 범위를 넓히고, b) 향후 유지보수 노력을 줄이며, c) 미래의 다른(남이 작성한) 코드에도 도움이 될 수 있기 때문이다.

하지만 그 어떤 선택을 하든 먼저 패턴을 알아야 한다. 수동으로 참조를 여러 번 구현하고 나니, 패턴이 또렷해졌다. 같은 패턴이 a) DerefMut 구현으로부터 Deref 구현을 쓰거나, b) 가변 참조로부터 공유 참조를 구현할 때에도 적용되었다. 기본 아이디어는 “모든 가변 참조를 대응하는 공유 참조로 바꾸고, 소멸자/부작용을 가진 생성자(및 메서드)를 제거하며, 메서드 호출은 가변판에서 공유판으로 바꾸고(예: assume_init_mut → assume_init_ref), 대응하는 가변 참조의 공유 대여로부터 공유 참조를 얻는 방법을 추가한다(모든 필드를 재귀적으로 가변→공유 변환하고, 그 결과를 복사해서 공유 참조의 필드로 만든다)”였다.

이건 언어 기능이 하나 빠진 게 아닐까 싶어졌다. 즉 많은 메서드를, 가변 참조를 받는 대신 공유 참조를 주면 공유 참조를 돌려주는 식으로 호출할 수 있어야 할 것 같다. 하지만 그대로 구현하면 거의 확실히 불안전하다. 미묘한 방식으로라도. (예를 들어, UnsafeCell은 &mut UnsafeCell을 통해 읽을 땐 안전하지만, 해당 &UnsafeCell을 통해 읽으려면 추가 안전 체크가 필요하다. 전자는 배타적 참조라 그 시점에 다른 쓰기가 없음을 보장하지만, &UnsafeCell은 셀 내부에서는 &의 보장이 통하지 않기에 누가 쓰고 있는지 보장하지 못한다.)

여기서 포기해도 탓할 순 없지만(아니, 이미 더 먼저 포기했어도), 나는 이런 탐구를 계속하는 타입이다. 언제 가변→공유 대체가 안전한지 알고 싶었다. 이를 알기 위해선, 무슨 타입 이론이 이를 설명하는지 찾아야 했다.

"You can't have two mutable references to the same object"

또 다른 실험을 해보자. 이번엔 사고 실험이다. Rust가 가변 참조 구현을 공유 참조 구현으로 일반 변환하는 기능을 지원한다고 하자. 그러면 Rust의 실제 가변 참조인 &'a mut T에도 적용될 것이다. 즉 공유 참조가 언어에 “원래부터” 존재할 필요 없이, 가변 참조와 자동 변환만 있으면 된다는 뜻이다. 그렇다면 공유 참조가 전혀 없는 Rust도 somehow 성립할 수 있다. 무언가를 하는 가장 좋은 방법 중 하나는, 불가능을 증명하려 하다가 증명이 깨지는 지점을 찾는 것이다. 그 틈이 바로 해법이다.

가장 분명한 불가능은 이거다. 같은 객체에 두 개의 공유 참조를 만들어 동시에 쓰는 건 가능해야 한다. 그렇지 않으면 대부분의 Rust 프로그램을 쓸 수 없다. 하지만 Rust의 가장 근본적인 규칙 중 하나는 “같은 객체에 대한 두 개의 가변 참조는 가질 수 없다”이다. Rust의 aliasing 규칙은 아직 완전히 확정되진 않았지만, 이 규칙만큼은 핵심이고 예외가 없을 것 같다.

그래도 해볼 수밖에. 예전에 어떤 카드 게임을 보는데, 한 플레이어가 그 순간 정말 유용할 카드 두 장을 가지고 있었다. 하지만 규칙이 그 카드는 한 턴에 한 번만 낼 수 있다고 했다. 다른 관전자가 비꼬듯 말했다. 두 장을 못 내는 건, 충분히 열심히 시도하지 않아서라고. 그 말이 머리에 박혀 있다. 지금도 somehow 관련 있어 보인다.

Rust에서는 가변 참조를 복사할 수 “없다”(재대여(reborrow)는 가능하지만, 두 복사본을 동시에 쓰는 것을 막는다). 하지만 아마 내가 충분히 열심히 시도하지 않은 걸지도 모른다. 직접 해보자:

fn main() {
    let mut a = 5i32;
    let b = &mut a;
    
    // SAFETY:
    // It is better to remain silent and be thought a fool,
    // than to speak and remove all doubt.
    let c = unsafe {
        core::ptr::read(&raw const b)
    };
    
    println!("{}", *b);
    println!("{}", *c);
}

희망적이다. Rust가 참조를 복사하지 않겠다면, 참조가 놓인 메모리 비트를 그냥 읽어와서 새 참조를 만들면 어떨까? 불행히도, 이 코드는 참조를 복사하라고 분명히 적혀 있고 컴파일도 되지만, 실제로 복사하진 않는다.

이유는 메모리-불안전 언어(C, C++, unsafe Rust 등)를 써본 사람에게 익숙할 것이다. 이 프로그램은 정의되지 않은 동작(UB)을 가진다. 메모리-불안전 언어에는, 프로그램이 의미를 가지려면 따라야 할 여러 규칙이 있다. UB가 있는 프로그램은 의미가 없고 아무거나 할 수 있다. 문제의 코드를 건너뛰는 것도 포함된다(실제로 자주 발생한다). 따라서 이 코드는 참조를 복사한다고 말할 수 없다. Rust 컴파일러가 원래 프로그램과 닮은 기계어를 낼 필요가 없고, 결과 코드에 복사가 없을 수 있기 때문이다. (수십 년 전부터의 표준 비유가 있다. UB의 구현으로 코에서 악마가 나오는 것을 허용한다는 것이다. 그래서 나는 이 프로그램을 내 컴퓨터에서 테스트하지 않고 Rust playground에서 돌렸다. 만약 악마가 소환된다면, 먼 데이터센터가 더 잘 가둘 수 있길 바라면서.)

그래도 한 번 실패했다고 포기한다면, 충분히 열심히 시도하지 않은 것이다. 좀 더 세게 가보자:

fn main() {
    let mut a = 5i32;
    let b = &mut a;
    
    // SAFETY: ???
    let mut c = &mut 0;  // placeholder, immediately overwritten
    unsafe {
        core::ptr::copy(&raw const b, &raw mut c, 1);
    };
    
    println!("{}", *b);
    println!("{}", *c);
}

겉보기엔 이전과 거의 같다. 가변 참조의 비트를 복사해 새 가변 참조를 만든 대신, 기존 가변 참조를 덮어썼다. 그런데 이를 Miri(UB를 잡아내는 Rust 인터프리터)로 돌려 보면, 놀랍게도 문제 없이 실행되고 UB도 보고되지 않는다.

이 영역은 Rust에서 가장 미묘한 부분 중 하나다. 나도 최근 비슷한 상황을 버그로 제보했다가, 의도된 동작임을 알게 됐다(나만 그런 실수를 한 게 아니었다). 지금은 무슨 일이 일어나는지 이해한 것 같다. C에서의 비유로 시작하겠다.

환경 변수 PATH의 값을 출력하는 C 코드를 써보자:

puts(getenv("PATH"));

이 코드가 스레드 안전한가?

생각보다 미묘하다. glibc 매뉴얼에 좋은 설명이 있다 ("env" 섹션). 핵심은 이렇다. C의 getenv는 대개 전역 변수 environ의 내부를 가리키는 포인터를 돌려준다. 이 포인터는 다른 스레드가 environ을 바꾸지 않는 한에서만 유효하다. 바뀌면, 우리가 쓰는 도중에 반환값이 덮어써질 수 있고, 그 결과 버퍼 오버리드나 해제된 메모리 접근 같은 UB로 이어질 수 있다. 그럼에도 getenv는 보통 안전으로 간주된다. 이유는 environ을 바꾸는 setenv가, 동시에 다른 스레드가 getenv를 호출하지 않음을 증명하지 못하면 불안전하기 때문이다. 즉 같이 쓰면 불안전한 둘(getenv와 setenv) 중 하나는 안전, 다른 하나는 불안전으로 취급한다. (이 미묘함 때문에 Rust 역사에서 드물게 표준 라이브러리 함수의 안전성이 변경된 사례가 있다. std::env::set_var가 과거엔 안전이었지만, 병렬로 돌아가는 C의 getenv를 깨뜨릴 수 있어 unsafe로 바뀌었다(비록 Rust 쪽에서는 병렬 실행을 막더라도).)

여기서 알 수 있는 사실. UB의 원인은 두 가지다. 하나는 컴파일러/런타임/OS/CPU가 “불가능”하다고 가정하는 일을 직접 하는 것. 이 경우 최적화가 전제한 가정이 무너지며 임의의 고장이 난다. 다른 하나는, 다른 코드가 가정해도 되는 불가능을 깨는 것. 멀티스레드 프로그램에서 setenv를 호출하면, 병렬로 getenv를 안전하다 가정하는 다른 코드 때문에 UB가 날 수 있다. 반대로 setenv를 호출하면서, 동시에 getenv가 호출되지 않음을 보장할 수 있다면 UB가 아니고 프로그램은 정상 동작한다. 즉 “써선 안 되는 코드”에는 두 가지 그레이드가 있다. 1) 직접 UB를 일으키는 것(즉시 의미를 잃는다). 2) 다른 코드가 가정하는 불변을 깨뜨리는 것(그 가정에 의존한 코드가 같이 돌 때만 불안전하다).

그럼 위 Rust 예시는 어떨까? 일반적으로 Rust 코드는 “동시에 쓸 수 있는 두 가변 참조는 서로 alias하지 않는다”를 가정할 수 있다. 예컨대 ptr::read는 반환값이 호출자가 쓰는 어떤 가변 참조와도 alias하지 않는다고 가정한다(사실 일반적으로 Rust 함수들이 그렇게 가정한다).

Rust 코드는 “동시에 쓸 수 있는 두 가변 참조는 alias하지 않는다”고 가정할 수 있다… 하지만 컴파일러는 그렇지 않다.

좋은 데모가 있다. 이 두 함수를 릴리스 모드로 컴파일해 보자:

pub fn f1(a: &mut i32, b: &mut i32) {
    *a = 1;
    *b = 2;
    *a += 2;
}

pub fn f2(a: &mut &mut i32, b: &mut &mut i32) {
    **a = 1;
    **b = 2;
    **a += 2;
}

현재 Rust에서 f1의 기계어는 이렇게 동작한다. *b에 2를 저장하고, *a에 3을 저장한다. 인자로 들어온 가변 참조끼리는 alias하지 않는다는 가정이 가능하기 때문이다(컴파일러가 해도 되는 가정).

반면 f2의 기계어는 이렇게 동작한다. **a의 주소를 계산해 1을 쓰고, **b에 2를 쓰고, 계산해 둔 **a에 2를 더한다.

f1에서는 컴파일러가 a와 b가 서로 alias하지 않는다는 사실을 이용했다. 함수 인자의 가변 참조끼리는 alias하지 않는다는 가정은 컴파일러가 해도 되는 가정이며, 이를 어기면 즉시 UB다.

f2에서는 컴파일러가 *a와 *b가 alias하지 않는다는 사실을 이용하지 않았다. 현재 초안의 aliasing 규칙에 따르면, 이건 Rust의 실제 규칙이 아니기 때문이다. alias된 가변 참조로 해선 안 되는 것은 많지만, 이건 그중 아니다(호출자가 준 메모리에 참조를 써서 돌려주는 것도 마찬가지다. 이 차이가 위의 ptr::copy 예와 ptr::read 예를 의미 있게 갈라놓는다). 심지어(만약 b에 mut를 붙인다면) 위 ptr::copy 예에 f2(&mut b, &mut c) 호출을 추가해도, 릴리스 모드와 Miri 모두에서 출력은 4와 4가 된다.

물론 이런 코드를 사고 실험 말고 다른 목적으로 쓰는 건 추천하지 않는다. 규칙이 a) 매우 미묘하고 이해하기 어렵고, b) 런타임에서 임의로 악화되는 고장을 유발하며, c) 변경될 수 있고, 변경이 과거 잘 돌아가던 코드를 깨뜨릴 수 있어서다. Rust 개발자들이 이 글의 코드를 깨도 안전하다고(=기존 unsafe 코드를 많이 깨뜨리지 않는다고) 판단한다면, 내 글이 구식이 되는 건 아쉽겠지만, 새로운 최적화 기회와 이해하기 쉬운 규칙은 반길 것이다.

하지만 사고 실험의 세계에서, 어떤 이유로든 공유 참조 없이 Rust를 구현했다면, 모든 Rust 프로그래머는 이런 코드를 쓰고 있었을 것이다. 그리고 개발자들은 기존 코드를 다 깨뜨리지 않도록 신경 썼을 것이다.

그 결과는 두 가지 중 하나다. 첫째, 이런 세계의 Rust는 C보다 더 위험해서 아무도 쓰지 않는다. Rust의 존재 이유가 사라진다. 둘째, 더 흥미로운 시나리오로, 누군가 이런 것을 안전하게 만드는 프레임워크를 만들어낸다.

A Rust with piracy instead of sharing

이 가상의 Rust에서 프로그래머가 갖는 것은: a) 가변 참조(현 실제 Rust에도 있다), b) 복제하면 안 되는 것을 복사하는 방법(공유 참조가 없으니 매우 널리 쓰일 것이고, 문법은 더 좋아졌을 것이다), c) 최소한 타입에서, “불법 복제된 객체”와 “불법 복제되지 않은 객체”를 구분하는 표기(일부 연산은 후자에만 허용되므로, 안전성 증명을 위해 구분이 필요)이다.

c)는 또다시 새 언어 기능을 만들 상황이다. 비록 이번엔 평행 세계의 가상 언어를 위한 사고 실험이지만. 문법에 좋은 아이디어가 떠오르지 않는다. 그래서 실험에 배운 또 다른 교훈을 쓰겠다. 좋은 문법이 없다면, 임시 이름이 굳어버리지 않도록 일부러 아주 나쁜 문법을 택하라. (Rust 실험 API에 Yeet나 BikeshedIntrinsicFrom 같은 이름이 붙었던 이유가 이것이다. 다만 Yeet는 충분히 나쁘지 않았던지, 유지하자는 사람도 있었다.)

그래서 내 새 표기는, 실험용으로, 접두사 ?로 “불법 복제된” 타입을 표시하는 것이다. 예를 들어 불법 복제된 &'a mut T는 ?&'a mut T다. 그리고 접두사 ?는 복제 불가한 것을 복사하는 연산자로도 쓰겠다:

fn main() {
    let mut a = 5i32;
    let b = &mut a;
    let c = ?b;

    println!("{}", *b);
    println!("{}", *c);
}

나는 이 ? 연산을 “해적질(pirating)”이라 부른다. 규칙상 Copy하면 안 되는 것을 복사하기 때문이다. let c = ?b; 이후에는 b와 c 모두 사실상 ?&mut i32다. 원본과 복사본이 서로의 복사본이므로, 서로의 존재를 고려해야 한다.

해적질을 일반적으로 생각해 보자(가변 참조에만 한정하지 말고). 공유 참조를 만드는 것에 “반쯤” 해당한다. 예를 들어 해적화된 값은 Copy다(이미 한 번 불법 복제됐으니, 다시 복제한다고 더 나빠질 건 없다). 대부분의 경우 원본 값을 읽을 수 있고, 인자로 넘겨도 원본은 소비되지 않는다. 반면 크기는 원본과 같다(참조처럼 포인터 크기가 아니다). 주소는 알 수 없다. Cell 안에 쓰기도 못 한다(공유 참조는 가능). 이 차이들은, 해적화된 값이 원본의 사본이지 참조가 아니라는 사실에서 온다.

이쯤 되면 의심이 든다(적어도 나는 그랬다). 가변 참조를 해적질하면, 결과는 공유 참조가 되지 않나? 값을 직접 해적질하면 주소는 사라지고 크기는 보존되지만, 가변 참조를 해적질하면 주소는 복사되고, 참조 크기의 무언가가 된다. 남은 요구 조건은, ?&'a mut T로 할 수 있는 일이 실제 Rust의 &'a T로 할 수 있는 일과 같다는 것을 확인하는 것뿐이다. 대체로 비슷해 보인다(예: 다른 스레드에 복제되어 있을 수 있으니 쓰기 금지. 단일 스레드면 쓸 수는 있지만 가변 참조를 만들 수는 없음 등).

이건 흥미롭다. 원래 찾던 가변→공유 변환의 모델을 제시하기 때문이다. 특히 타입 변환에서 무엇을 해야 하는지 명확히 한다. 타입을 해적화하면, 필드를 전부 해적화하는 것과 같고, 그건(특수한 PhantomData를 제외하면) Copy가 아닌 필드만 해적화하는 것과 동일하다(이미 Copy인 필드를 복사하는 건 불법이 아니다). 이제 실제로 쓴 참조 구현과 대조해 볼 수 있다. 결과는… 거의 일치한다. 차이가 나는 곳은, 어떤 공유 참조는 수명이 있는데 대응하는 가변 참조는 없다는 점이다.

생각해 보면 이유가 있다. 가변 참조에 소멸자가 있는 경우다. 그걸 해적질하면, 소멸자가 안전하게 돌 수 없다. 해적화된 복사가 기대하는 “잠김 상태”를 소멸자가 풀어버릴 수 있으니까. 이를 안전하게 만드는 유일한 방법은, 소멸자가 돌기 전에 해적화된 복사본을 전부 제거하는 것이다. Rust에서 어떤 동작 전에 객체가 사라졌음을 보장하는 가장 좋은 방법은 수명을 주는 것이다. ? 연산자에 이 동작을 넣는 것은 쉽다. 타입에 적용할 때 수명을 붙인다. 대략 ?'a &'a mut T 같은 모양으로. 수명이 끝나면, 복사들이 더 이상 존재하지 않으므로, 원래의 “해적화되지 않은” 상태로 돌아간다. (값 수준에서도, 동작은 공유 참조와 동일하다.) 이 변경을 ?에 더하니, 참조들이 완전히 혹은 “다른 구현이지만 같은 결과를 주는” 수준에서 일치했다.

즉 수많은 참조를 구현하는 실험은 두 면에서 결실을 줬다. a) 구현은 스코프드 제네릭에 대한 통찰을 준다. b) 구현은 가변 버전으로부터 공유 참조 코드를 생성하는 법을 보여준다. 타입 변환은 거의 확실히 이 방법이 맞다. 그렇다면 함수와 메서드의 변환은? 예제와 “감각”은 있지만, 정합성을 증명하는 이론이 있으면 좋겠다.

여기서 박사과정에서 구조적 제약 타입 시스템을 공부하지 않았다면 어떻게 했을지는 모르겠다. 다행히 나는 배경지식이 맞아서, 몇 시간을 들여 기존 수학 이론이 있는지 찾아봤다. 먼저 기억을 뒤지고, 하스켈 문서에서 모양이 맞거나 이름이 관련 있어 보이는 타입을 찾고, 온라인 친구에게 물었다. (하스켈은 이런 걸 찾기에 좋다. 기이한 타입 시스템 관련 물건은 누군가 먼저 하스켈에 구현했을 가능성이 크다.) 결과는 러버덕과 이야기한 것과 비슷했다. 답변은 주로 반례를 제시해주었지만 내 생각을 정리하는 데 도움이 되어, 결국 스스로 제대로 된 방향으로 생각하게 되었고, 매우 흥미로운 것을 발견했다.

Linear logic

<ais523> 사실, 이건 선형 논리에 어딘가 연산이 있을 거야. 그런 류의 연산이 많거든

— 수학의 가지를 잘못 붙잡았음을 깨달은 나

조금 물러서서, 프로그래밍 언어의 타입 시스템을 생각해 보자. 수십 년 전에 관찰된 사실이 있다. 프로그래밍 언어의 타입 시스템은 논리학의 공리 체계와 같은 규칙을 따른다는 것이다(보통 “커리–하워드 대응”으로 알려져 있다). 간단한 예. 논리에서 A가 B를, B가 C를 함의하면, A는 C를 함의한다. 프로그래밍에서도 A를 받아 B를 내는 함수, B를 받아 C를 내는 함수가 있으면, A를 받아 C를 내는 합성 함수를 만들 수 있다. 일반적으로 프로그래밍의 타입은 논리의 술어와, 프로그램은 증명과 비슷한 규칙을 따른다. 그게 우연인지 아닌지는 내겐 분명치 않다. 하지만 규칙이 같으므로, 한 분야의 결과를 다른 분야에 재해석하여 배울 수 있다(그게 “이유”가 있든 없든 유효하다).

철학에는 다양한 논리 모델이 있고, 규칙이 조금씩 다르다. 대부분은 프로그래밍 언어 타입 시스템의 틀로서도 의미가 있다. 규칙의 차이는 다른 성격의 언어를 낳는다.

다수의 논리가 공통으로 갖는 점 하나. 전제 목록을 가지고 무엇인가를 증명할 때, 전제는 여러 번 써도 되고, 안 써도 되고, 임의 순서로 써도 된다. 예컨대 P, Q, R이 모두 참이라는 전제를 주면, (P와 Q)와 (Q와 R)을 증명할 수 있다. Q를 두 번 써야 하지만, 현실의 참을 반영하려는 논리에서는 허용된다. 하지만 이런 규칙 중 일부를 제거한 논리를 상상할 수 있다(“구조적 제약(substructural)” 논리). 예컨대 전제를 한 번 이상 쓰지 못하게 하면(“약선형(affine)” 논리), 전제의 참이 “소비”되어 다른 것의 증명에 쓸 수 없게 된다.

약선형 논리는 진리/거짓을 모델링하기에는 부적절하다(그렇다. 현실에서 참인 문장은 증명했다고 해서 참이 없어지지 않는다). 하지만 자원으로 무언가를 제조하는 등의 다른 것을 모델링하는 규칙으로는 매우 쓸모 있다. 고전 논리의 “P가 Q를 함의한다”는 문구는, 약선형 논리에서는 “P를 써서 Q를 만들 수 있다”로 해석할 수 있다. 타입 시스템으로 보면 흥미로운 효과가 나온다. 그 문구는 “P에서 Q로 가는 함수의 타입”이 되는데, 호출 후에 P는 더는 쓸 수 없다(다른 함수의 인자로 다시 쓸 수 없다). 가능한 이유 중 하나는 “P를 함수로 이동(move)시켰다”여서, 호출자에게 남지 않는 것이다. 현재, 기본이 그런 함수인 널리 쓰이는 언어는 하나뿐인데, 바로 이 글의 주제인 Rust다. Rust는 일반적으로 약선형 타입 시스템으로 여겨진다. 인자를 함수로 move시키고, 호출자에겐 남지 않는다는 관점에서.

하지만 약선형 타입 시스템은 다른 관점도 있다. 나는 Rust가 만들어질 무렵 박사과정에 있었고, 나 또한 약선형 타입 시스템을 썼다(덕분에 Rust 이해에 앞서갔다고도 볼 수 있겠다). 내 경우, 언어(SCI, "Syntactic Control of Interference", 간섭의 구문적 제어)를 하드웨어로 바로 컴파일하는 구현이었고, 그래서 병렬 실행이 매우 싸게 가능했다. 하지만 그만큼 병렬 코드의 스레드 안전성 문제가 따른다. SCI는 이를 피하고자 했다. SCI의 해법은 약선형 타입 시스템이었다. 스레드를 새로 만드는 것은 그 스레드에서 쓰는 자원(곱셈기 같은 하드웨어 자원, 특정 메모리 셀 같은 데이터 자원)을 “소비”한다고 보아, 다른 스레드에서 재사용을 막았다. 반면 두 코드 블록이 순차 실행이면 자원을 공유할 수 있었다.

이 둘의 차이는 “연결자(connective)”라는 것으로 구현했다. 고전 논리의 연결자는 “그리고”, “또는”, “부정” 등이다. 구조적 제약 논리에서는 연결자가 더 많다. 각자는 고전 연결자와 비슷하지만 자원 공유 방식에 더 구체적이다. SCI에는 “병렬로 실행”과 “순차로 실행”에 서로 다른 타입이 있었다. 병렬 실행에서는 스레드 사이에 자원을 공유할 수 없었다. 반면 순차 실행에서는 공유할 수 있었고, 인자 타입을 다른 연결자로 결합해 표현했다. 둘 다 “명령과 명령”을 받지만, 병렬은 “자원 공유 금지” 버전의 “그리고”를, 순차는 그 안전 제약이 없는 “그리고”를 쓴다. 결과적으로 고전 논리에서는 둘 다 “그리고”로 번역되지만, 언어에서는 서로 다른 연결자로 흉내냈다.

“선형 논리(linear logic)”는 구조적 제약 논리의 일종으로, 약선형과 마찬가지로 전제를 두 번 쓰지 못하게 하며, 연결자가 꽤 많기로 유명하다. 타입 이론에서 쓸 때는, 보통 원하는 연결자만 골라 쓰고 나머지는 버리는 도구로 쓰인다. 일부는 꽤 생소해서, 이 글을 쓰기 전 주까지 나는 써본 적도, 의미도 잘 몰랐다. 그래서 타입 이론으로 보자면, 그 자체로 유용한 이론이라기보다는 타입 이론을 만들기 위한 틀에 가깝다.

하지만 알고 보니 Rust는 이미 상당 부분을 쓰고 있었고, 해적질 연산자를 모델링하려면 더 많은 부분이 필요했다. 그래서 이 글에서는 여섯 “주요” 연결자를(“덧셈적(additives), 곱셈적(multiplicatives), 지수(exponentials)”) 설명하고, Rust와 어떻게 대응되는지 살펴보겠다.

Understanding the more commonly-used linear logic connectives

가장 이해하기 쉬운 것부터 시작하겠다. 먼저 ⊗. 두 것을 ⊗로 결합하면 둘 다 얻고, 둘 다 쓸 수 있다. Rust에서는 여러 필드를 가진 struct나 튜플이다. 모든 필드를 move할 수 있다. 예컨대 선형 논리는 Rust 타입 (i32, u32)를 i32⊗u32로 모델링한다. i32 필드와 u32 필드를 가진 struct도 타입 이론 관점에서는 차이가 없으니 같은 식으로 모델링한다. T⊗U는 만들 때 T 그리고 U를 만들어야 하고, 소비자는 T 그리고 U를 소비한다. 간단하다.

Rust의 임의 데이터 구조 도구 둘은 struct와 enum이다. 선형 논리에도 enum에 해당하는 연결자가 있다. ⊕는 Rust의 enum, 언어 불문으로는 "태그된 합(tagged union)", 수학에서는 “서로소 합(disjoint union)”이다. 두 타입 중 하나일 수 있고, 어느 쪽인지 기록한다. 예컨대 Result<T, U>는 T⊕U로 모델링된다. T⊕U를 만들려면 T 또는 U 하나만 만들면 된다. 소비자는 생산자가 만든 것 T 또는 U를 소비하면 된다. 다만 소비자는 두 경우 사이에 자원을 공유할 수 있다. 예컨대 T를 처리할 때든 U를 처리할 때든 같은 메모리에 접근해야 한다면, 먼저 T인지 U인지 확인한 뒤 그에 맞게 메모리를 사용하면 되니 안전하다.

다음으로 쉬운 건 &다. 하나의 객체가 두 타입 중 하나로 볼 수 있음을 나타낸다. Rust에서는 트레이트 구현이 이런 상황을 만든다. Vec는 Vec이지만, 동시에 impl Debug이고 impl IntoIterator이고, 다른 트레이트도 많이 구현한다. 선형 논리는 이를 &로 나타낸다. T&U는 T로도 U로도 볼 수 있는 하나의 값이다. 따라서 T&U를 만들려면 T 그리고 U인 것을 만들 수 있어야 하고, 소비할 때는 T 또는 U로만 소비할 수 있다. (&는 ⊕와 달리 소비자가 선택한다. ⊕에서는 생산자가 선택한다.)

이 시점에서 선형 논리는 프로그램에서 “시간의 흐름”을 어떻게 모델링하는지 융통성이 있음을 적어둘 가치가 있다. 흔한 방식 하나는 프로그램에서 그 순간 사용 가능한 타입을 나타낸다고 생각하는 것이다. SCI에서는 순차 실행 연산자의 인자가 command&command였다. 선형 논리는 둘 중 하나만 써야 한다고 한다. 하지만 (적어도 SCI에서의) 올바른 해석은 “한 번에 하나만” 쓸 수 있다는 뜻이다. 나중에 다른 하나를 실행하는 건 문제없다. 어느 순간에도 프로그램 상태가 잘못되지 않으면 되기 때문이다. 선형 논리를 Rust에 “한 번에” 관점으로 모델링하면 가변 대여를 모델링하게 된다(가변 대여를 돌려받으면 나중에 다른 용도로 쓸 수 있으니, T&U는 먼저 T로 빌렸다가 나중에 U로 빌릴 수 있다). “영원히” 관점으로 보면 move를 모델링한다. 아마 둘을 동시에 모델링하는 수학적 요령이 있을 것 같은데, 나는 모른다.

이 섹션의 마지막 연결자는 !다. 단일 타입에 적용되는 지수(exponential)다. 선형 논리에서 !T는 1 &T& (T⊗T) & (T⊗T⊗T) & …, 즉 임의 개수의 T를 의미한다(여기서 1은 빈 튜플, Rust의 ()다). T를 무한히 공급하는 것으로 볼 수 있다. Rust 관점에서는 임의 T에 적용할 연산으로는 말이 안 된다. 하지만 우리 목표는 선형 논리로 Rust를 모델링하는 것이지, Rust로 선형 논리를 모델링하는 것이 아니다. Rust에서 !의 명확한 용도 하나는 Copy 타입을 모델링하는 것이다. 예컨대 i32는 !NonCopyI32로 나타낼 수 있다. Rust에서 i32가 있으면 더 복제할 수 있고, 선형 논리에서는 !NonCopyI32를 !NonCopyI32⊗!NonCopyI32로 바꾸면 된다.

Copy 타입을 비-Copy 타입의 !로 번역하면 Rust에 대해 가르쳐 주는 바가 있다. 약선형 논리는 복사할 방법 없이 값을 여러 번 쓰게 하지 않는다. 선형 논리는 그에 더해, 버릴 방법 없이 값을 적어도 한 번은 쓰게 한다. Rust는 보통 약선형으로 묘사된다. mem::forget로 무엇이든 버릴 수 있기 때문이다. 하지만 이 묘사는 오해를 부를 수 있다. 약선형에서는 값을 무시하면 곧바로 부작용 없이 사라진다. Rust에서는 버리려면 드롭하거나, 누수시키거나, mem::forget/ManuallyDrop 같은 연산으로 “잊어야” 한다. 잊기는 명시적이어야 하고, 누수는 타입 시스템 관점에서 객체가 존재는 하지만 더 이상 접근하지 않는 것이다. 드롭은 암묵적으로 일어나지만, 사용자 정의 코드를 실행할 수 있으므로(즉, 타입 시스템 관점에선 drop/drop_in_place 호출이 명시적으로 적힌 것과 같아야 한다) 특별히 취급해야 한다. 그래서 나는 Rust의 타입 시스템을 “선형이되, 의도적으로 드롭/잊는 다양한 옵션이 있다”로 보는 게 정확하다고 생각한다.

흥미로운 점은, 선형 타입 시스템에서 ! 타입은, 명시적으로 없애는 함수를 호출하지 않아도 버릴 수 있다고 정의된다는 것이다. 대부분의 타입에서는, 타입 시스템이 값이 메모리를 떠날 때 드롭되도록 보장한다(명시적으로 잊지 않는 한). ! 타입에서는 그러지 않는다. 드롭 없이 사라져도 된다. 이는 Rust가(그리고 실제로) 가져야 하는 규칙을 암시한다. Copy 타입은 소멸자를 가질 수 없다. 내가 해적질의 타입 이론을 보고 싶었던 이유 중 하나가 이런 통찰 때문이다. 타입 이론이 타입을 제대로 모델링한다면, 논리를 따라가다 보면 언어에서 가능한 것과 불가능한 것을 가르쳐 준다. 실제로 그런지 대조해 볼 수 있다. 아니라면, 타입을 잘못 모델링했거나, 언어에 안전성 구멍이 있거나, 기능이 빠진 것이다.

아무튼 이 글에서 다룰 여섯 연결자 중 넷을 봤다. (함수 타입을 나타내는 연결자를 제외하면) 내가 실전에서 본 건 이게 전부다. 남은 건 ⅋와 ?이고, ?는 ⅋로 쉽게 정의된다.

하지만 ⅋를 이해하는 건 악몽에 가깝다. 선형 타입 이론에서(그 드문 경우에 실제로 필요할 때) 가장 복잡한 부분이다. 선형 논리는 내부적으로 대칭이 매우 강하고, ⅋는 패턴의 빈칸을 채운다. 다만 처음엔 채울 수 없을 것 같은 빈칸이다. 어떤 연결자는 만들기는 쉬우나 소비자는 덜 유용하다. 어떤 연결자는 반대다. 지수형이 아닌 넷을 소비하기 쉬운 것→만들기 쉬운 것 순서로 늘어놓으면 이렇다.

  • T⊗U: 두 객체 T 그리고 U를 만들어야 한다. 소비자는 T 그리고 U를 소비한다.
  • T&U: T이자 U인 한 객체를 만들어야 한다. 소비자는 그 한 객체를 T 또는 U로만 소비한다.
  • T⊕U: T 또는 U인 한 객체를 만들면 된다. 소비자는 그 한 객체를 T 또는 U로 소비한다. 어느 쪽인지는 생산자가 정한다.
  • T⅋U: T 또는 U를 만들면 되는데, 그게 어쩐지 두 객체처럼 행동해야 한다. 소비자는 T 그리고 U를 모두 소비해야 한다.

앞의 셋과 달리, ⅋는 불가능하고 말이 안 되는 것처럼 보인다. 생산자는 겉보기에 불가능한 일을 하는데, 그런데도 ⊕보다 더 쉽다. 소비자는 두 객체를 얻는데, 그게 하나만 받는 것보다 더 어려워 보인다(만들기에는 덜 유용해진다).

이제 ⅋가 실제로 하는 일을 직관적으로 이해한 것 같다. 하지만 이렇게 낯선 것은 설명이 길어질 수밖에 없다. 독자에게 그 직관이 전달되는지 보려면, 한 섹션을 온전히 써야겠다.

Understanding linear logic's ⅋ and ?

“달걀 하나를 사고 싶은데요,” 앨리스가 조심스레 말했다. “얼마죠?”

“하나는 5펜스와 4분의 1펜스, 둘은 2펜스요,” 양이 대답했다.

“그럼 하나보다 둘이 더 싸요?” 앨리스가 놀라며 지갑을 꺼냈다.

“단, 둘을 사면 둘 다 드셔야 해요,” 양이 말했다.

— 루이스 캐럴, 『거울 나라의 앨리스』

⅋가 실제로 등장할 수 있는 상황으로 시작하자. 자연스럽게 생길 법하진 않지만, 무슨 일이 일어나는지 이해하기에는 충분하길 바란다.

경험 많은 자바스크립트 프로그래머를 찾아 Rust는 모르는 상태라고 하자. 그에게 웹 요청 라이브러리(Rust용)의 인터페이스를 설계하게 한다(고수준 라이브러리. URL을 지정하면, 웹 페이지의 본문을 주거나, 에러 코드를 준다). 여기엔 두 문제가 있다. a) 요청과 응답 사이의 지연을 어찌 다룰 것인가. b) 반환값이 문자열일 수도, 정수일 수도 있음을 어찌 다룰 것인가.

a)에 관해, Rust 프로그래머는 async를 쓰거나 그냥 블록할 수 있다. 하지만 자바스크립트의 저수준 원시 도구는 콜백이다. 오늘날 JS에서는 Promises로 싸여 있겠지만, Rust를 모르는 사람은 간단한 것부터 시도할 것이다. 그러니 콜백을 쓰는 API를 고안할 가능성이 높다. b)에 관해, 정답은 태그된 합(enum, Rust 프로그래머라면 Result)이다. 하지만 Rust를 모르면 그 기능을 몰라서 직접 구현하려 들 수 있다.

그럼 enum을 인자로 받는 콜백을 enum 없이 어떻게 구현할까? (선형 논리 노트를 들춰 보니, T⊕U를 소비하려면 T-소비 함수 & U-소비 함수가 쓰인다고 한다) 올바른 접근은, 각 variant마다 메서드 하나를 가진 트레이트를 정의하는 것이다. 어떤 메서드가 호출되었는지로 variant를 알 수 있게.

trait HttpCallback {
    fn success(self, response_body: &str);
    fn failure(self, http_status: i32);
}

// version 1
fn http_request(url: &str, callback: impl HttpCallback);

하지만 Rust에 익숙하지 않다면 트레이트 대신, 함수 인자를 받는 문법을 찾아보고 콜백 두 개를 struct나 튜플로 묶거나, 그냥 메서드 인자로 콜백 두 개를 받게 할 수 있다.

rust
// version 2
fn http_request(url: &str,
                success_callback: impl FnOnce(&str),
                failure_callback: impl FnOnce(i32));

버전 1에서 http_request는 콜백에 사실상 &str⊕i32를 제공한다. 예상 그대로다. 하지만 버전 2에서는 &str⅋i32를 제공한다.

먼저 콜백을 만드는 쪽에서 무엇이 잘못되는지 보자. ⅋ 타입은 ⊕ 타입보다 소비자에게 덜 유용하다. 여기서는 콜백을 빌림 검사기에 걸칠 때 드러난다. 버전 1에서는 성공/실패 콜백 메서드가 모두 self의 같은 필드를 쓰려 해도 문제가 없다. 어느 메서드가 호출되든 self 전체가 move되므로, 메서드는 self 전부에 온전한 접근 권한을 가진다. 하지만 버전 2에서는 성공/실패 콜백이 동시에 존재하는 실제 객체다. 서로 충돌하는 빌림을 담을 수 없다. 예컨대 둘 다 어떤 컨트롤러 객체에 쓰고 싶다면, 둘 다 그 컨트롤러에 대한 가변 참조를 가질 수 없다.

빌림 검사기가 괜히 엄격한 걸까? Rust 초보는 그렇게 생각할 수 있지만, 숙련자는 “컴파일러가 지키려는 타당한 가설이 어딘가 있다”는 걸 알아차릴 것이다. 이 경우엔 쉽게 보인다. 버전 2의 http_request에는 “콜백 중 하나만 호출한다”는 명세가 없다. 악의적 구현은 성공 콜백을 호출할 수도, 실패를 호출할 수도, 성공 그리고 실패를 호출할 수도, 그 순서를 바꿀 수도 있다. 콜백 인자 타입이 &str과 i32보다 더 복잡했다면, 성공 콜백을 실패 콜백의 인자로 넘기거나 그 반대로 하여, 한 콜백을 다른 콜백 안에서 실행하게 속일 수도 있다. 둘 중 어느 하나라도 Send였다면, 서로 다른 스레드에서 동시에 실행할 수도 있다.

즉 T⅋U란 이런 것이다. T일 수도, U일 수도, 혹은 T 그리고 U일 수도 있는데, 둘은 임의의 방식으로 함께 처리되어도 안전해야 한다. 임의의 순서로, 병렬로, 섞어서 등. 소비자는 어느 쪽인지를 알 수 없다(⊕에서는 알 수 있고, &에서는 선택 할 수 있다). 생산자가 실제로는 하나만 만들었더라도, 둘 다 주어질 경우를 대비해 T와 U에 각각 자원을 따로 배정해야 한다. 어떤 면에서(선형 논리는 사실 이것을 정확히 정의한다!), ⅋는 ⊗의 반대다. T⊗U도 T로 처리할 수 있고, U로 처리할 수 있고, T 후 U, U 후 T, 동시에 처리할 수 있다. 하지만 ⊗에서는 _소비자_가 방식을 고른다. ⅋에서는 _생산자_가 강제한다.

⅋는 별로 쓸모 있어 보이지 않는다. 나도 Rust에서 간단하고 유용한 대응물을 찾지 못했다. 하지만 더 흥미로운 것을 위한 빌딩 블록이 될 수 있다. 두 타입이 같을 때 연결자가 어떻게 동작하는지 생각해 보자.

  • T⊗T는 T 두 개다. 둘 다 소비할 수 있으니, 단일 T의 두 배 자원을 제공한다.
  • T&T는 단일 T와 동등하다(둘 중 어느 쪽으로 소비하든 같다).
  • T⊕T는 사실상 T+불리언이다(왼쪽 T였는지 오른쪽 T였는지 알 수 있으니).
  • T⅋T는 T와 비슷하지만, 다른 T와 병렬로 처리해도 안전해야 한다(설령 실제로는 그렇지 않더라도). 따라서 그 처리에 사용할 자원의 두 번째 사본이 필요하다.

자, T⅋T가 a) 어떻게 만들어지는지, b) 만들어지더라도 어떻게 쓸모 있는지 떠올리기 어렵다. 그럼 더 나아가 보자. T⅋T⅋T는? T⅋T⅋T⅋T는? 극한을 생각하자. 임의 개수의 T를 ⅋로 엮은 타입. 이것은 T ⊕ T⅋T ⊕ T⅋T⅋T ⊕ …이고, 선형 논리는 이걸 ?T라고 부른다. 이 글의 여섯 번째이자 마지막 연결자 ?다.

?T가 무엇인지 생각해 보자. 겉으로는 T와 비슷하지만, 소비자는 처리에 큰 제약을 받는다. 원래 생산자가 ? 타입을 주었을 때, 그것을 처리할 때는 처리 전에/후에/도중에, 같은 소비자(동일한 소비자여야 한다. 임의 개수의 T를 처리해야 하는데 소비자 종류는 유한하니, 어떤 소비자는 자기 자신의 여러 복사본을 처리하게 된다)가 임의 횟수로 처리해도 안전해야 한다. 어떤 것도 가변 빌림에 의존할 수 없다. 두 번만 반복돼도 빌림 검사기를 통과하지 못한다. 또한 “내가 메모리에 유일하게 접근한다”는 주장을 가변 참조로 할 수 없다. 무엇이든 쓰려고 하면 alias되어 있을지도 모른다.

소비가 끝나면, 생산하는 결과도 또한 ? 타입이다. 이유는 원래 ? 타입을 만든 생산자가, 몇 번 처리하고 어떤 결과가 중요해지는지를 선택하기 때문이다. ? 타입을 처리해 값을 반환하더라도, 결과의 구조를 알 수 없다. 결과 값의 여러 복사본 중 몇 개가 유효한지, 어떤 순서로 실행되었는지 알 수 없다. 최선은 결과 타입의 ?를 만드는 것뿐이다.

?T를 들고 있으면서 쓰기(write)하는 것이 완전히 불가능한 것은 아니다. 다만 안전성을 빌림 검사기에 기대진 못한다. 다른 형태의 증명이 필요하다. 예컨대 “이건 Send가 아니므로 단일 스레드에서만 접근된다”거나, “동시 수정으로부터 보호하는 락이 있다” 같은 것. 이 규칙은 공유 참조에도 똑같이 적용된다(Cell과 Mutex가 각각 이 제한을 회피하는 타입이다). 이 정도면 의심스러울 것이다.

What linear logic teaches us about pirating

이제 대발견으로 이어진다. Rust에는(내가 아는 한) ⅋로 모델링되는 건 없지만, ?로 모델링되는 건 있는 듯하다. 특히 선형 논리의 ?T는 해적화된 타입 ?T와 매우 비슷하게 행동한다. 생각해 보면 이치에 맞는다. 타입을 해적질한다는 건 “존재하면 안 되는 복사본이 추가로 있을 수 있다”는 말이다. ?는 “복사본이 추가로 있을 수 있고, 그 복사본들이 조작되고 있더라도 안전한 방식으로만 값을 다룰 수 있다”는 뜻이다.

이 이론을 검증하려면, ?가 할 수 있어야 하는 일을 보고 Rust에서도 같은 일을 할 수 있는지 확인하면 된다. ?의 주요 규칙은, ! 타입 자원만 사용하는 방식으로 T를 다룰 수 있다면, ?T도 다룰 수 있다는 것이다(결과도 ?가 된다). Rust로 옮기면, “Copy인 클로저는 인자를 해적화한 버전으로 받아 결과의 해적화 버전을 만들 수 있다”가 된다.

불행히도 이건 명백히 틀린 것처럼 보인다. Rust에는 |x: &mut i32| *x = 10 같은 아주 단순한 클로저가 있고, 이는 Copy이며 ()를 반환한다(()는 Copy이므로 해적화 가능). 하지만 인자를 해적질해 가변 참조 대신 공유 참조를 만들면 불안전해진다.

불일치는 대입 연산자 =가 하는 일에서 온다. 쓰기가 안전하다는 사실을 확인하기 위해, 쓰는 대상의 가변 참조의 유일성을 근거로 삼는다. 해적화된 가변 참조(즉 공유 참조)를 받으면, 유일성의 근거는 다른 곳에서 와야 한다. 하지만 그러한 증거는(당연히) Copy일 수 없다. 두 클로저에 각각 유일한 접근이 있음을 증명하게 되어 버리기 때문이다. 따라서 올바른 결론은 “Copy인 클로저는, 유일성에 근거하지 않는 한, 인자의 해적화 버전을 받아 결과의 해적화 버전을 만들 수 있다”이다(혹은, 유일성에 근거하고 싶다면, Copy임에도 불구하고 어딘가에서 해적화되지 않은 유일성 증거를 얻어야 한다). 이 논변은 “유일성에 근거하는가”가 타입 시스템 수준의 개념이어야 한다는 느낌을 준다. 논리가 이를 드러내고 영향을 미치기 때문이다.

타입 시스템 수준의 개념이라면, 타입 시스템에서 찾아야 한다. 실제로 본 적이 두 군데 있다. 하나는 지난 블로그 글이다. 스코프드 제네릭으로 Cell을 안전한 Rust에서 구현했다. Cell 접근 권한을 나타내는 스코프드 제네릭을 사용했다. Cell 내부를 조작하는 동안에는 권한이 없어서, 이미 내부 참조를 들고 있는 동안 새 참조를 만들 수 없다. 이는 유일성에 근거하는 한 형태지만, 타입 시스템에 구체 객체로 나타나는 것(이를 “셀 권한(cell permission)”이라 부르겠다).

어떤 면에서 Rust의 기존 Cell도 비슷하게 동작한다. 스레드 로컬 변수에 셀 권한을 저장하고, Cell의 각 메서드는 그 권한을 받아서 본문에서 쓰고, 메서드가 끝나기 전 권한을 되돌린다고 생각할 수 있다. (이게 Cell 내부에서 참조를 빌려올 수 없는 이유다. 참조를 들고 있는 동안 권한을 스레드 로컬에 돌려줄 수 없다.) 권한이 스레드 로컬이므로, Cell은 그 안의 타입이 Send라면 Send일 수 있지만, Sync일 수는 없다. (실제로 그 트레이트 구현을 가진다.)

그럼에도 현재의 Cell은 이론이 암시하는 힘만큼 강하지 않다. 스코프드 제네릭 없이도, 타입 시스템에 셀 권한을 표현해, 다른 방식으로 접근 가능함을 증명할 수 없는 셀에 접근할 수 있어야 한다. 이는 Rust에 기능이 빠졌음을 시사한다. 표준 라이브러리에서는 못 찾았지만, crates.io에서는 둘을 찾았다. ghost-cell은 아이디어의 정당성을 형식 논리로 뒷받침하며 구현했고, qcell은 네 가지 구현을 제공한다. 각 구현은 셀 권한을 생성할 때 사용하는 유일성 근거가 다르다. 즉 이런 기능은 언어에 들어갈 법하다.

유일성 근거에 관한 또 다른 흥미로운 관찰. 보통 이런 근거는 쓰기를 정당화하는 데 쓰인다. 하지만 그 근거 자체를 해적질하면, 더 이상 쓰기를 안전하게 만들 수 없다. 자기 자신과 해적 복사본이 충돌할 수 있기 때문이다. 하지만 해적화된 증거도 “충돌하는 쓰기가 없다”는 사실은 증명한다(해적화로 쓰기는 금지되지만, 다른 것에 쓰기 권한을 주지도 않는다). 따라서 읽기를 안전하게 만든다. 이는 공유 참조가 읽기를 안전하게 만드는 이유에 일종의 수학적 정당화를 준다. 굳이 필요하지는 않았겠지만, 그렇게 깔끔한 정당화를 보게 되니 놀랍고 우아했다.

안타깝게도 “! 자원만 쓰는 T→U 사상은 ?T→?U로 lifting된다” 규칙에서 더 많은 결론을 끌어내진 못했다. Rust에서 이 규칙은 “해적화된 객체의 모든 복사본을 동시에 갱신한다”처럼 작동하고 싶어 하지만, 실제로 복사본이 어디 있는지 추적하지 않으니 구현 불가능하다.

?-관련 다른 규칙이 하나 더 있다. ??T는 ?T와 같다. 선형 논리에서는 다소 자명하지만, Rust에서는 흥미롭다. 해적질이 참조보다 더 투명해지는 효과를 준다. Rust에서 T, &T, &&T는 서로 다른 트레이트 구현을 가질 수 있다. 반면 ?T와 ??T가 같다는 사실은, 일반적 제네릭 트레이트에서 U와 ?U를 구분하기 어렵게 만든다(U가 ?T일 수도 있어서).

이는 몇몇 트레이트 구현을 이상하게 만든다. 논리적으로는 객체의 해적 복사본이 그 트레이트의 해적 복사본을 구현하길 원한다. 가장 눈에 띄는 예가 DerefMut를 해적질하면 Deref가 되는 것이다. 하지만 이 방향성은 Clone을 두 방향으로 찢어 놓는다. 하나는 Copy와 일관되어, ?T를 복사해서 다른 ?T를 만든다. 다른 하나는 ?T를 복제해 T를 만들고 싶어 한다(그리고 ??T도 T로 복제하고 싶어 한다. ?T가 아니라). 놀랍게도 Rust 라이브러리 팀은 두 번째 트레이트( ?T를 T로 복제하는) 도입 제안을 이미 수락했다. 이름은 CloneFromCopy. 현재 Rust에는 해적질 연산자조차 없는데 말이다! (이 트레이트는 이번 글을 쓰기 전에는 몰랐고, 전혀 다른 일을 하다 우연히 알게 됐다.) 자세한 내용은 이 GitHub 이슈의 코멘트에 있다. CloneFromCopy 아이디어는, Cell에서 안전하게 clone하는 방법을 만들다 발견되었다.

이상함에도, 공유/가변 참조 대신 해적질과 가변 참조를 기반으로 한 Rust(여기서 &T는 ?&mut T의 설탕 문법)도 충분히 성립 가능해 보인다. 나는 해적질 Rust로 사고해 볼 수 있고, 논리(선형 논리)와 언어 동작 모두에서 일관되게 보인다. 참조 비슷한 것이 셋(가변 참조, 공유 참조, 해적화된 복사)으로 늘어 문법 설계가 어려울 수 있지만, 풀 수 있는 문제일 것이다. 대부분의 면에서 현재 Rust보다 우월해 보인다. 공유하려고 굳이 참조를 만들 필요가 없다(많은 타입에서 참조는 그저 불필요한 한 단계 간접만 더한다). 거의 모든 메서드를 공유/가변 두 벌로 작성할 필요도 줄어든다. 또한 현재 Rust의 상위 집합이기도 하다. 공유 참조를 구현할 수 있으니, 현재 Rust의 모든 기능을 얻으면서 해적질도 얹는다.

또 하나의 데이터 포인트. 나는 한동안 실용적 프로그래밍 언어를 직접 만들까 고민해 왔다. 그 과정에서 메모리 모델을 어떤 식으로 할지(원하는 프로그램을 떠올리고 어떤 원시 기능이 필요한지로) 생각했다. 거의 백지에서 시작했는데, 인자 전달의 세 “주된” 방식이 Rust의 것(T, &T, &mut T)과 꽤 가깝게 귀결되었다. 다만 &T가 조금 달랐고, 지금 와서 생각해보니 내가 구상한 것은 &T가 아니라 ?T였다. (계획은 스코프드 제네릭의 동치도 포함하고 있었다. 문법은 매우 달랐지만, 의미론은 같았다.)

아쉽게도 지금 시점에서 Rust를 “해적질 기반”으로 전환하기엔 너무 늦었다. 현재 Rust에서는 맞지만 해적질을 도입하면 틀리는 가정을 둔 unsafe 코드가 많을 것이다. 표준 API 상당수를 공유 참조 대신 해적 복사 기반으로 재설계해야 할 것이다. 아주 핵심 트레이트 몇 개는 작동이 미묘하게 달라질 것이다. 기존 튜토리얼도 모두 구시대가 된다. 변화의 여파가 너무 넓다.

그럼에도, Rust 전체를 이렇게 크게 바꾸기엔 늦었더라도, 이 사고 실험에서 배운 교훈을 현재 Rust에 부분적으로 반영할 여지는 있다.

What pirating teaches us about Rust

Shares of reference-counted references

현재 Rust에서 빠진 기능을 찾는 가장 분명한 자리 하나는 기존 참조 타입을 해적질해 보는 것이다. 이 글도 실제로 그렇게 해서, 가변 참조에서 시작해 해적질로 공유 참조를 재구성했다. 그렇다면 다른 참조를 해적질하면 또 흥미로운 게 나오지 않을까?

실제로 곧바로 빠진 기능이 하나 보인다. ?'a Rc<T>나 ?'a Arc<T>를 생각해 보자. 의미론은 간단하다. 기존의 어떤 Rc/Arc(참조 카운트 객체에 대한 여러 참조 중 하나)에서 만들어지며, 그 특정 참조가 수명 'a 동안 드롭되지 않음을 단언한다. 그 수명 동안에는 참조 카운트를 실제로 변경하지 않고 자유롭게 복제할 수 있다(복제가 더 싸진다).

&'a Rc<T>/&'a Arc<T> 대비 장점은 간접화 한 단계를 줄여 코드가 단순해진다는 것(특히 생성된 바이너리에서). &'a T 대비 장점은, 기저의 Rc/Arc를 'a를 넘는 수명으로도 복제할 수 있다는 것. Rc/Arc 대비 장점은 참조 카운트 갱신을 줄인다는 것이다. 참조 카운트 갱신은 매우 느릴 수 있다(Arc는 원자적 읽기-수정-쓰기 연산을 쓰는데, 이는 보통 CPU가 가진 가장 느린 명령 중 일부다). Rc도 오버플로를 방지해야 하므로, 증가/감소를 최적화로 지우기 어렵다.

?Rc<T>와 ?Arc<T>는 표준 라이브러리에는 없지만, crates.io에서 둘을 찾았다. rc-borrow는 직접 구현이지만 거의 쓰이지 않는다. triomph는 자신의 Arc 구현에 대해 동등한 것을 제공한다. 내 추측엔, 이 기능은 필요한 경우 확실히 개선을 주지만, 의존성을 추가할 만큼 “그 정도까지”는 아니다(의존성은 자체 비용이 크니, 비슷한 이득이 없으면 추가하고 싶지 않다).

Why shallow snapshots don't work

해적질이 또 유용해 보이는 다른 방향은 값의 “스냅샷”을 만드는 것이다. 원본이 바뀐 뒤에도 안전하게 쓰기 위해, 얕은 복사본을 떠두면 좋을 것 같아 보인다. 하지만 내가 수많은 참조 타입을 해적질하다 배운 교훈 하나는, 이런 얕은 복사는 공유 참조와 같은 안전 규칙을 가진다는 것이다. 수명이 있고, 그 수명이 끝나기 전에는 원본을 바꿀 수 없다. 이 경우 정말 필요한 건 clone(타입의 Clone이 깊은 복사라면 깊게)이지, 얕은 복사가 아니다. 그렇지 않으면 원본이 수정되거나 드롭될 때, 원본이 소유한 무언가가 드롭되어 복사본 안에 댕글링 참조가 생길 수 있다. (이 문단을 쓰다 바로 이 문제로 CloneFromCopy가 불안전함을 깨달았고, 그 결과 설계가 수정되었다. 해적질에서 Rust에 대한 교훈을 얻고자 했지만, 이렇게 즉각 실무적으로 관련 있을 줄은 몰랐다!)

Trait implementations on references

Clone 대 CloneFromCopy 이야기는, 참조와 트레이트의 상호작용 전반에 대해 생각하게 했다. 일반적으로 Rust는, 참조가 가리키는 값이 구현한 트레이트를 자신의 트레이트로도 구현하고 싶어 한다(그리고 ??T가 ?T와 같다는 사실은 이런 기대를 뒷받침한다). 다만 공유 참조에서는 “읽기 전용” 버전의 트레이트를 얻게 된다(공유 참조는 가변 참조의 해적화이므로, 객체를 해적질하면 그 트레이트들의 읽기 전용 버전을 얻게 된다). 특히 참조와 피참조체가 동일 트레이트를 다르게 구현해야 하는 경우는 드물다.

눈에 띄는 예외 둘이 있다. Clone과 Debug다. 둘 다 추상화의 다른 레벨에서 의미가 있다. Rc<T>를 복제할 수도, 그 안의 T를 복제할 수도 있다. 디버깅도 참조 자체를 디버깅할 수도, 가리키는 값을 디버깅할 수도 있다. 흥미로운 점은 둘의 경우가 다르다는 것이다. 보통 clone에서는 참조를 clone하는 편이 옳다. 대체로 더 싸거나, 가리키는 객체를 clone하는 것과 동등하기 때문이다(다만 내부 가변 객체의 깊은 복사가 필요하다면, 참조가 아니라 객체 자체를 clone해야 한다). 디버깅에서는 보통 참조 자체가 아니라 피참조체를 보고 싶다.

Rust는 기본적으로 참조의 트레이트 구현을 우선한다. 그래서 <Rc as Clone>::clone()은 올바르게 동작한다. 하지만 이 “자연스러운” 규칙대로면 Debug는 잘못된 동작을 준다. 그래서 참조 타입은 보통 내부 값의 Debug를 그대로 위임하도록 구현한다. 이러면 참조 자체를 디버깅할 수 없다(사용자 정의 참조 타입을 쓸 때 성가시다). 때때로 일관성이 흔들리기도 한다. 내가 만든 참조 중 하나는 “MaybeUninit가 초기화되었음을 증명하는 값 + 그 내부 값에 대한 참조”쯤이었다. 내부 MaybeUninit 참조를 감싼다. 내부 값이 Debug라면, Rust의 규칙상 외부 참조의 Debug는 내부 값의 Debug로 위임해야 한다. 하지만 그러려면 내부 참조의 Debug를 수동으로 덮어써야 한다. 내부 참조는 가리키는 메모리가 초기화되었는지 모른다. 반대로 내부 값이 Debug가 아니면, 내부 참조를 Debug하고 싶다. 하지만 그러면 일관성이 깨진다. 이런 경험은 적어도 Debug(아마 Clone도)가 잘못 정의된 것 같다는 생각을 준다. 구체적으로, 참조의 Debug는 참조 자체를 디버깅하고, {:?} 포맷 지정자가 최대한 Deref를 적용한 뒤 그 결과에 Debug를 호출하는 편이 낫지 않나 싶다. Debug를 직접 호출하는 별도 포맷 지정자를 두고.

Packed types

해적질 관점으로 유용하게 생각해 볼 수 있는 또 하나는 패킹(packed) 혹은 비트 패킹된 타입이다. Rust의 대부분 타입은 정렬이 1보다 크다. 즉 그 타입을 가리키는 포인터의 하위 비트는 항상 0이어서, 모든 비트를 쓰지 않는다. 예컨대 최근 내가 작성한 프로그램에서 나온 것과 비슷한 enum을 생각하자:

enum Tree<'a> {
    Leaf(&'a u64),
    Branch(&'a [Tree; 2])
}

현재 Rust는 이를 포인터 두 개 분량의 메모리로 저장한다. 예컨대 64비트 시스템에서, 참조 저장에 64비트를 쓰고(그중 3비트는 항상 0), 잎/가지 구분에 또 64비트를 쓴다(Tree의 크기는 64비트의 배수여야 하므로 줄여도 이득 없다). 명백히 더 효율적인 방법은 이를 반으로 줄이는 것이다. 예컨대 Leaf 참조의 최하위 비트를 뒤집어 Branch와 구분한다. 이는 필드의 알려진 비트에 추가 데이터를 집어넣는 “비트 패킹” 타입이다.

패킹/비트 패킹 타입의 문제는, 이를 안전하게 쓰기 매우 어렵다는 것이다. 참조는 “올바른 타입의 값을 담은 메모리를 가리켜야 한다”. 하지만 예컨대 Leaf의 필드에 대한 참조를 만들려 하면, 가리키는 메모리에는 &'a u64가 아니라 “최하위 비트를 뒤집은 &'a u64”가 들어 있다(메모리 표상이 달라 타입이 다르다). Rust의 현재 해법은 “패킹 타입에서 무언가를 하려면 값의 move나 copy를 먼저 해야 한다”이다. 위 Tree에서는 &'a u64가 Copy이므로, 패킹 타입에서 꺼내 복사하면 된다.

그렇다면 필드가 Copy가 아닌 패킹 타입은? 현재 Rust에서는 거의 쓸 수 없다(내용물로 무언가를 하려면 완전히 구조 분해해야 한다). 왜냐면 필드를 복사할 수 없기 때문이다. 하지만 복사 대신, 필드를 해적질하면 어떨까? 이는 복사나 참조 형성보다 힘이 조금 덜하다(예: 내부 가변성으로 수정할 수는 없다). 그래도 안전하게 할 수 있는 일이 많다(그리고 해적질 이론은 그 범위를 명확히 해 준다). Rust에 해적질이 언어 기능으로 없다면, 컴파일러는 패킹 필드를 직접 쓰도록 도와줄 수 없다. 그래도 unsafe 코드에서 같은 일을 해볼 수는 있다. 이론을 써서 그 코드의 건전성을 빠르게 가늠할 수 있다. 이 논변은 또한, Rust에 해적질 연산을 도입하는 것이 API 전반에서 광범위하게 쓰이지 않더라도 유익할 수 있음을 시사한다. 패킹 필드에 “참조”를 형성하는 용도로만 써도 유용할 것이다.

The case for pirating in Rust

보통 글은 결론으로 맺는다. 하지만 이번에는 “아이디어를 떠올리고 실험했고, 그 결과 많은 것을 배웠고, 더 많은 아이디어로 이어졌지만, 그 아이디어가 좋은지 아직 판단이 서지 않는다”가 더 가깝다. 스코프드 제네릭처럼, 연구가 결론으로 이어지는 경우에는, 남을 설득할 논지를 세울 수 있고, 좋은 자기완결 글이 나온다. 하지만 때로는 결론 대신 더 많은 질문으로 끝난다. 이런 결과도 나름대로 유익하다.

그래서 결론 대신, 논쟁의 한쪽을 변호하며 끝내려 한다. Rust에 해적질을 추가하는 것이 실제로 괜찮은 아이디어일지도 모른다는 근거들을 제시한다. 기존 언어에 추가하는 것이 좋은지는 아직 모르겠다. 처음부터 Rust를 다시 만든다면 나는 해적질을 넣었을 것 같지만, 기존 언어 변경은 트레이드오프가 훨씬 크다. 단점은 명백하다. 하지만 장점들(그리고 단점에 대한 반박)은 훨씬 흥미롭고 예상보다 많았다. 독자가 스스로 판단할 수 있도록 적겠다.

핵심 관찰 하나. 해적화된 값과 원본 값에 대한 공유 참조의 유일한 관찰 가능한 차이는, 공유 참조는 주소를 보존한다는 것이다. (해적화된 값을 메모리에 저장한 뒤 그 포인터를 참조로 재해석하면, “주소가 틀린 공유 참조”로 바꿀 수 있다. Rust의 코드 생성 백엔드가 이미 값이 충분히 클 때는 함수 인자 전달을 위해 자동으로 그런 일을 한다. 따라서 큰 해적화된 값을 인자로 전달하는 것과, 그 값에 대한 공유 참조를 전달하는 것은, 생성된 코드 관점에서 매우 비슷하다.) 즉 해적질 연산은 “공유 참조이되, 주소에 의존하는 일을 하지 말라” 연산으로 볼 수 있다(주요하게 막히는 것은 포인터로 변환하기와 내부 가변으로 쓰기 등이다).

Rust 타입 시스템은 이미 “참조 대상 타입에 내부 가변성이 있는가”를 추적한다. 어려운 부분은 “공유 참조가 포인터로 바뀌는가”를 알아내는 것이다. 언어에 기능을 추가할 때의 또 다른 교훈을 쓸 때다. 기능이 근본적이고 중요하다면, 이미 컴파일러 어딘가에 그 기능의 개별 사용이나 특수 사례를 발견할 수 있다(예: 스코프드 제네릭이 올바른 설계라는 확신을 준 이유 중 하나는, 라이프타임이 그 특수 사례였기 때문이다. 즉 Rust가 이미 필요로 하는 것을 일반화한 것). 여기서는 “공유 참조가 포인터로 변환되는가”를 컴파일러가 검사하고, 그 여부에 따라 다르게 행동하는 경우를 찾자.

당연하게도 그런 경우는 있다. 가장 중요한 것은 컴파일러 백엔드에 있다. Rust의 백엔드인 LLVM은, 작은 값에 대한 공유 참조를 받고 주소를 쓰지 않는 함수를 찾아, 값을 직접 받는 함수로 바꾼다. 즉 참조화를 해적질로 최적화한다. 거의 모든 비자명한 Rust 프로그램이 성능 손실을 피하려면 이 최적화가 필요하다. 표준 라이브러리의 많은 메서드가, 주소가 아니라 공유를 위해 &T를 받기 때문이다. 즉 Rust는 “해적질 추론” 같은 것을 구현한다. 언어 자체에 해적질이 없기 때문에, 소스의 직해석은 다른 시스템 언어에 비해 느리고, 최적화를 통해 다시 해적질로 되돌려 성능을 회복한다.

이로 인해 본질적으로 필요치 않은 복잡성이 많이 생긴다. 간단한 코드를(값으로 전달) 복잡한 코드로(공유 참조로 전달) 강제한 뒤, 다시 간단한 것으로 최적화하는 것은 보통 안티패턴으로 여겨진다. 여기서는 현재 Rust가 “전달 방식(값/주소)”과 “공유 규칙(공유/배타)”을 뒤섞었기 때문이다. 복잡성은 실용적 단점도 낳는다. 추론이 빗나가면(예: 최적화기 버그 때문에), 프로그램이 훨씬 느려질 수 있다. 이런 버그는 꽤 흔할 것이다. 최근 버그 하나를 찾는 데 오래 걸리지 않았다. 코멘트에서도 “값이 작은데 참조로 캡처해서 후속 최적화를 막는다”는 문제가 논의된다. 복잡성은 컴파일러도 느리게 만들 것이다. 없애야 할 참조가 너무 많고, 제거 과정이 꽤 시간을 잡아먹을 테니.

“참조가 포인터로 쓰이는가”를 아는 건 최적화 말고도 유용하다. 이종 언어와 섞이는 프로그램은, 보통 이런 보안 완화를 이점으로 얻는다. “Rust에서 버퍼를 만들고 C에 포인터를 넘겼더니, C가 오버플로했다” 같은 시나리오다. 따라서 Rust 버퍼의 포인터가 C로 빠져나갈 수 있다면, 컴파일된 Rust 코드는, 그 버퍼 바로 뒤 메모리가 덮어써졌는지 중요한 일 전에 검사하면 보안이 좋아진다. 하지만 검사 과다는 성능을 해친다. 그래서 제안이 있었다. 공유 참조가 포인터로 변환되는 버퍼에 대해서만 검사를 넣자는 것이다. 즉 여기서도 “참조가 참조로서 쓰이는가, 해적질 시뮬레이션을 위해 쓰이는가”에 따라 컴파일러가 다르게 행동하길 원한다.

매 컴파일 때 정적 분석으로 이런 정보를 알아내는 건 본질적으로 느리다. 프로그램에 이 정보가 들어 있다면 분석을 생략할 수 있다. 그러니 이상적으로는 타입 시스템이 처리해야 할 것 같다. 실제로, 대부분의 Rust 크레이트는 공유 참조를 포인터로 바꿀 필요가 없다. (저수준 unsafe 코드도 대개 포인터를 저장해 두었다가 참조로 바꿔 쓰지, 그 반대로 하진 않는다.) 따라서, 예컨대 다음과 같은 크레이트 속성을 상상할 수 있다. “이 크레이트는 공유-참조→포인터 변환을 하지 않는다.” (필요하다면 포인터로 바꿀 수 있는 공유 참조의 별도 타입이 있으면 좋다. 급하면 & &mut 같은 것을 써도 된다.) 크레이트 그래프 전체가 이 속성을 세팅한다면, Rust 컴파일러는 타입 시스템에서 그 정보를 즉시 얻을 수 있다. 느리고 오류 가능성이 있는 정적 분석을 할 필요가 없다(설정을 안 한 크레이트가 있다면, 옛 방식으로 되돌아가면 된다). 어쩌면 미래의 에디션에서 기본값이 되게 할 수도 있다.

이 변경은 꽤 작아 보인다. 하지만 일단 적용되면, Rust에는 해적질이 생긴다. 내부 가변성이 없는 T에 대해, &T는 해적질의 의미론을 갖게 된다(컴파일러는 최적 효율에 따라 값 전달, 주소 전달, 주소-오브-복사 전달 중 자유로이 택할 수 있다). “완벽한” 구현은 아니다. 예컨대 &T와 &&T는 여전히 다른 타입이고, 실제 포인터 역참조가 아닌 곳에서도 가끔 *가 필요할 수 있다. 하지만 현재 Rust와 일관된다는 큰 장점이 있다. 기존 튜토리얼이 그대로 동작하고, 프로그래머가 새로 배울 필요도 거의 없다.

“패킹 필드에도 참조를 만들 수 있다” 같은 이득을 얻을 방법도 있을지 모른다(복사본을 만든 다음 그 복사본을 전달하거나, 그 포인터를 전달). 다만 이는 아마 어려울 것이다. 누군가 과거의 “주소를 담는 공유 참조” 정의에 의존한 옛 크레이트에 의존성을 추가하면, 갑자기 멈출 수 있어서다.

요약하면, 해적질을 Rust 자체에 도입하는 세계는 충분히 가능성 있어 보인다. “모든 것을 해적질로 작성”하는 세계보다 얻는 것은 작지만, 잃는 것도 작다(많은 프로그래머는 변화를 알아차리지 못할 수도 있다). 실험적으로 구현해 보고, 컴파일 시간에 어떤 영향이 있는지 보는 것도 재미있겠다!

그리고 설령 해적질을 Rust에 넣을 가치가 없다는 결론이 나와도, 우리는 많은 것을 배웠다. 커스텀 참조 작성에 대한 힌트, 트레이트 시스템에 대한 생각, Rc/Arc의 지분 공유 제안, 버그 하나 잡음, 그리고 이전엔 쓸모 없어 보였던 선형 논리 일부를 활용한 공유 참조의 수학적 모델. 즐거웠다. 이제 스코프드 제네릭 구현 실험으로 돌아가도 되겠다!