FAQ: 왜 mutable은 immutable의 서브타입이 아니며, 그 반대도 성립하지 않을까요?

본문

불변성(immutability)을 처음 배운 순간 모든 것이 달라졌다는 Denis Defreyne의 인용으로 시작하는 이 글은, 여러 프로그래밍 언어에서 반복적으로 제기되는 질문을 다룹니다. 어떤 자료구조에 immutable과 mutable 변형이 함께 있다면, 왜 둘 중 하나를 다른 하나의 서브타입(subtype) 또는 슈퍼타입(supertype)으로 만들지 않을까요? 글의 결론은 이를 구현하는 것 자체가 불가능해서가 아니라, 그렇게 하면 정적 타입 시스템(static type system)이 보장해야 하는 타입 안전성의 일부를 잃게 된다는 것입니다.

서브타입은 모든 문맥에서 대체 가능해야 합니다

서브타입의 기준은 Liskov 치환 원칙(Liskov Substitution Principle)입니다. 타입 S가 타입 T의 서브타입이라는 말은, S 타입의 값을 T 타입의 값이 요구되는 모든 문맥에서 사용할 수 있다는 뜻입니다. 여기서 핵심은 “대부분의 경우”가 아니라 “모든 경우”입니다. 객체지향 설계에서 권장되는 패턴 정도로 이 원칙을 이해할 수도 있지만, 형식적인 타입 이론에서 진짜 서브타입이 되려면 타입 검사기가 이 전면적인 대체 가능성을 증명할 수 있어야 합니다.

이를 가장 단순한 복합 자료구조인 pair로 설명합니다. immutable pair에는 새 pair를 만드는 cons, 첫 번째 값을 읽는 car, 두 번째 값을 읽는 cdr만 있다고 가정합니다. mutable pair에는 여기에 더해 첫 번째 값을 바꾸는 set-car!와 두 번째 값을 바꾸는 set-cdr!가 추가됩니다. immutable pair를 mutable pair가 필요한 곳에 넘길 수 없는 이유는 직관적입니다. 호출자는 set-car!나 set-cdr!를 호출할 수 있다고 가정하지만 immutable pair에는 그런 연산이 정의되어 있지 않으므로 타입 오류가 발생합니다.

메서드 집합만 보면 놓치는 불변성의 계약

더 어려운 질문은 반대 방향입니다. mutable pair도 값을 읽는 연산을 제공하므로, 겉으로 보이는 메서드 집합만 보면 immutable pair가 필요한 곳에 넣을 수 있을 것처럼 보입니다. 그러나 서브타입 관계는 타입이 제공하는 연산 목록만이 아니라, 그 연산에 따라오는 암묵적인 계약(implicit contract)까지 포함합니다.

immutable pair에서 car나 cdr를 호출하면, 같은 pair에 대해 이후에도 결과가 항상 같을 것이라고 의존할 수 있습니다. 이 보장은 pair의 내용으로 해시값(hash value)을 계산하고, 그 값을 다른 자료구조에 저장한 뒤 나중에 같은 pair의 해시값을 다시 계산해도 변하지 않을 것이라고 기대하게 합니다. 반대로 mutable pair는 호출 사이에 set-car!나 set-cdr!가 실행될 수 있으므로 내용과 해시값이 바뀔 수 있습니다. 따라서 mutable pair를 immutable pair가 요구되는 문맥에 허용하면, immutable pair가 제공해야 하는 안정성 계약을 깨뜨리게 됩니다. 글은 이러한 불변성이 hash consing의 전제이기도 하다고 설명합니다.

따라서 두 pair는 단순히 한쪽에 변경 연산 몇 개가 더 있는 관계가 아니라, 서로 다른 계약을 가진 완전히 별개의 타입이어야 합니다. 예시에서는 immutable pair에 icons, icar, icdr를 사용하고 mutable pair에는 mcons, mcar, mcdr, set-mcar!, set-mcdr!를 사용합니다. i가 mutable pair이거나 m이 immutable pair인 경우는 타입 오류가 됩니다. 어느 한쪽을 다른 쪽의 서브타입으로 선언하면 한 방향에서는 연산 누락을, 다른 방향에서는 불변성 계약 위반을 피할 수 없습니다.

공통 연산은 서브타입 대신 ad hoc polymorphism으로 표현합니다

“내 함수에서는 pair를 변경하지 않으며 불변성 계약도 신경 쓰지 않는다”는 반론도 가능합니다. 하지만 두 pair가 서브타입 계층을 이루지 않으면, 두 타입에 같은 연산을 제공하는 별도의 방법이 필요합니다. 글은 이를 ad hoc polymorphism으로 설명합니다. 정적 타입 언어에서는 Wadler와 Blott가 도입한 type class가 이런 다형성을 형식적으로 다루는 수단입니다.

mutable pair와 immutable pair는 서로 다른 타입이지만, 둘 다 car와 cdr이라는 연산을 제공하는 공통 pair type class에 속할 수 있습니다. mutable pair에서 이 연산은 mcar와 mcdr를 사용하고, immutable pair에서는 icar와 icdr를 사용하도록 구현할 수 있습니다. 중요한 점은 pair type class가 불변성에 대해 아무것도 약속하지 않는다는 것입니다. 따라서 type class만 요구하는 함수는 두 종류의 pair 모두를 받을 수 있지만, 그 함수 안에서 mutable pair의 변경 연산을 사용해서는 안 됩니다. 반대로 함수가 결과의 안정성을 필요로 한다면 immutable pair를 요구한다고 명시해야 합니다.

이 방식은 함수의 입력 계약을 필요한 수준으로 명시하게 합니다. 함수가 mutable pair 또는 immutable pair 어느 쪽이든 받으면 되는지, 반드시 mutable pair여야 하는지, 반드시 immutable pair여야 하는지를 각각 표현할 수 있습니다. 한 방향의 서브타입 관계만 사용하면 immutable pair를 허용하는 선언에 mutable pair가 암묵적으로 포함되는 문제가 생기거나, 반대로 mutable pair를 허용하는 선언에 immutable pair가 잘못 포함될 수 있습니다. 두 타입을 일관되게 서로 배제하려면 서브타입의 대체 가능성 원칙을 위반해야 합니다.

정적 언어와 동적 언어의 표현 방식

정적 타입 언어에서는 type class와 비슷한 기능이 interface, trait, role 등의 이름으로 제공되기도 합니다. 다만 실제 언어의 타입 시스템이 이러한 계약을 얼마나 엄격하게 검사하는지는 서로 다릅니다. 공통 인터페이스를 통해 읽기 연산을 공유하더라도, 타입 검사기가 해당 인터페이스에 불변성이 포함되어 있지 않다는 점과 변경 연산을 사용할 수 없다는 점을 어느 수준까지 보장하는지는 구현에 달려 있습니다.

동적 객체지향 언어에서는 보통 duck typing으로 같은 문제를 다룹니다. 서로 다른 타입에 같은 이름의 메서드를 정의하고, 런타임 타입 디스패치(runtime type dispatch)가 실제 구현을 선택하도록 합니다. 필요하다면 함수 호출 전에 변경 연산이 존재하는지, 또는 반대로 변경 연산이 존재하지 않는지를 검사할 수도 있습니다. 하지만 특히 “변경 연산이 없어야 한다”는 부재(absence) 검사는 실무에서 드문 편입니다. 글은 이런 이유로 동적 언어의 ad hoc polymorphism이 데이터 타입의 흐름을 추론하기 어렵게 만들고 문제를 초래하기 쉽다고 설명합니다.

Lobsters 반응

• @isuffix — 이 차이는 Rust의 interior mutability와 비슷합니다. &Cell<T>와 &mut Cell<T>는 후자만 &mut를 사용하지만 둘 다 내부의 T를 변경할 수 있습니다. 그래서 &와 &mut에 선호되는 이름은 immutable reference와 mutable reference가 아니라 shared reference와 exclusive reference입니다. interior mutability 때문에 Rust는 thread-safety를 보장하기 위한 추가 요구사항이 필요합니다. Sync와 Send trait는 공유 메모리 접근을 Mutex<T>나 atomic처럼 thread-safe한 타입으로 제한합니다.
• @rs86 — Haskell에서 mutability를 monad로 모델링하면, 이는 단지 “a”와 “m a”가 subtyping relation에 있지 않다는 뜻입니다.

원문: Crumbles blog / 번역·요약: Trawling