Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

타입 및 라이프타임 매개변수의 변성

변성에 대한 더 일반적인 배경 지식은 배경 부록을 참고하십시오.

타입 검사 과정에서는 타입 및 라이프타임 매개변수의 변성을 추론해야 합니다. 이 알고리즘은 PLDI’11에 발표된 Altidor 외 저자의 논문 “Taming the Wildcards: Combining Definition- and Use-Site Variance”(와일드카드 길들이기: 정의 지점 변성과 사용 지점 변성의 결합)의 4절에서 가져온 것이며, 이하에서는 이 논문을 ’해당 논문’이라고 부릅니다.

이 추론은 코드 내에서 타입이 사용되는 방식을 고려하지 않도록 명시적으로 설계되었습니다. 타입 X에 정의된 타입 매개변수의 변성을 결정할 때는 타입 X의 정의와 그 타입이 참조하는 모든 타입의 정의만을 고려합니다.

변성은 구조체와 열거형 같은 데이터 타입에 있는 타입 매개변수에 대해서만 추론합니다. 이러한 경우에는 변성이 무엇을 의미하는지 비교적 간단하게 설명할 수 있습니다. 타입 매개변수 또는 라이프타임 매개변수의 변성은 A와 B(각각 'a와 'b)의 관계에 따라 T<A>가 T<B>(각각 T<'a>와 T<'b>)의 서브타입인지를 정의합니다.

트레이트, 함수, impl에 있는 타입 매개변수에 대해서는 변성을 추론하지 않습니다. 트레이트 매개변수의 변성은 실제로 의미가 있을 수 있지만(예전에는 이를 계산하기도 했습니다), 그 의미가 상당히 미묘하고 실제로는 그다지 유용하지 않아서 제거했습니다. 자세한 내용은 부록을 참고하십시오. 반면 함수/impl 매개변수의 변성은 의미가 없습니다. 이러한 매개변수는 인스턴스화된 후 잊히기 때문입니다. 즉, 타입이나 컴파일된 부산물에 남지 않습니다.

표기법

이 장 전체에서 논문의 표기법을 사용합니다.

  • +는 공변성입니다.
  • -는 반공변성입니다.
  • *는 쌍변성입니다.
  • o는 불변성입니다.

알고리즘

기본 아이디어는 매우 간단합니다. 정의된 타입들을 순회하면서, 타입 매개변수 X가 사용될 때마다 X의 변성이 해당 사용 위치의 변성에 대해 유효해야 한다는 제약 조건을 누적합니다. 그런 다음 모든 제약 조건이 충족될 때까지 X의 변성을 반복적으로 정제합니다. 해는 항상 존재합니다. 극단적인 경우 모든 타입 매개변수를 불변으로 선언하면 모든 제약 조건이 충족되기 때문입니다.

간단한 예로 다음을 살펴보십시오.

enum Option<A> { Some(A), None }
enum OptionalFn<B> { Some(|B|), None }
enum OptionalMap<C> { Some(|C| -> C), None }

여기서는 다음과 같은 제약 조건을 생성합니다.

1. V(A) <= +
2. V(B) <= -
3. V(C) <= +
4. V(C) <= -

이 제약 조건들은 (1) A의 변성이 최대 공변이어야 하고, (2) B의 변성이 최대 반공변이어야 하며, (3, 4) C의 변성이 최대 공변이면서 반공변이어야 함을 나타냅니다. 이 모든 결과는 다음과 같이 정의된 변성 격자에 기반합니다.

   *      Top (bivariant)
-     +
   o      Bottom (invariant)

이 격자에 따르면 V(A)=+, V(B)=-, V(C)=o라는 해가 최적의 해입니다. 모든 변수를 불변으로 선언하기만 하는 단순한 해가 항상 존재한다는 점에 유의하십시오.

고정점 반복(fixed-point iteration)이 왜 필요한지 궁금하실 수 있습니다. 그 이유는 사용 위치의 변성(variance) 자체가 다른 타입 매개변수의 변성에 대한 함수일 수 있기 때문입니다. 가장 일반적인 형태로 보면, 제약 조건은 다음과 같은 형태를 띱니다:

V(X) <= Term
Term := + | - | * | o | V(X) | Term x Term

여기서 V(X) 표기는 타입/영역 매개변수 X가 그것을 정의하는 클래스에 대해 갖는 변성을 나타냅니다. Term x Term은 논문에서 정의된 “변성 변환(variance transform)“을 나타냅니다:

타입 표현식 E에서 타입 변수 X의 변성이 V2이고 클래스 C의 대응하는 타입 매개변수의 정의 위치 변성이 V1이라면, 타입 표현식 C<E>에서 X의 변성은 V3 = V1.xform(V2)입니다.

제약

where 절이 있는 구조체나 열거형이 있다고 합시다:

struct Foo<T: Bar> { ... }

Bar에 대한 T의 변성이 Foo에 대한 T의 변성에 영향을 주는지 궁금하실 수 있습니다. 저는 그렇지 않다고 주장합니다. 그 이유는 다음과 같습니다. T가 Bar에 대해서는 불변(invariant)이지만 Foo에 대해서는 공변(covariant)이라고 가정해 봅시다. 그리고 X <: Y일 때 Foo<Y>로 업캐스트되는 Foo<X>가 있다고 합시다. 그런데 X : Bar는 성립하지만 Y : Bar는 성립하지 않습니다. 이 경우 업캐스트는 허용되지 않습니다. 하지만 그 이유는 변성 검사에 실패해서가 아니라 대상 타입 Foo<Y> 자체가 적격하지 않기 때문입니다. 기본적으로 변성을 고려하기 전에 관련된 모든 타입이 적격성을 갖춘다고 가정할 수 있습니다.

의존성 그래프 관리

변성은 크레이트 전체에 걸친 추론이므로, 주의하지 않으면 의존성 그래프가 상당히 복잡하게 뒤엉킬 수 있습니다. 이를 해결하기 위해 다음 두 개의 쿼리로 리팩터링합니다:

  • crate_variances는 현재 크레이트의 모든 항목에 대한 변성을 계산합니다.
  • variances_of는 개별 항목의 변성에 접근합니다. 이 쿼리는 crate_variances를 요청한 다음 관련 데이터를 추출하는 방식으로 동작합니다.

variances_of만 읽도록 제한하면, 코드는 해당 항목의 추론에만 의존하게 됩니다.

결국 이 구성은 레드-그린 알고리즘에 의존합니다. 특히 모든 변성 쿼리는 (crate_variances를 통해) 사실상 크레이트 전체의 모든 타입 정의에 의존하지만, 대부분의 변경은 변성 추론의 실제 결과를 바꾸지 않으므로 variances_of 쿼리는 재평가된 후 결국 그린으로 간주됩니다.

부록: 트레이트의 변성

앞서 언급했듯이, 예전에는 트레이트에 변성을 허용했습니다. 이 변성은 메서드 시그니처에 트레이트 타입 매개변수가 나타나는 방식을 기반으로 계산되었으며, 트레이트 객체에서 vtable의 호환성(그리고 트레이트 바운드에서의 “가상” vtable 또는 딕셔너리의 호환성)을 표현하는 데 사용되었습니다. 한 가지 복잡한 점은 연관 타입의 변성이 덜 명확하다는 것이었습니다. 연관 타입은 프로젝션되어 무수히 다양한 용도로 쓰일 수 있으므로, X<A>::Bar가 변하는 것을 언제 허용해도 안전한지(또는 그것이 정확히 무엇을 의미하는지조차) 분명하지 않습니다. 게다가 (아래에서 다루듯이) 연관 타입이 있는 트레이트의 입력은 전부 불변이어야 했기 때문에 적용 범위가 제한되었습니다. 마지막으로, 모든 트레이트 타입 매개변수가 변성을 갖도록 보장하는 데 필요했던 어노테이션(MarkerTrait, PhantomFn)은 혼란스럽고 번거로웠던 데 비해 얻는 이점은 거의 없었습니다.

역사적 참고 자료로서, 변성과 트레이트 매칭을 어떻게 해석할 수 있는지 보여 주는 글을 일부 남겨 두겠습니다.

변성과 객체 타입

구조체와 열거형의 경우와 마찬가지로, 두 객체 타입 &Trait<A>와 &Trait<B> 사이의 서브타이핑 관계는 A와 B의 관계를 바탕으로 결정할 수 있습니다. 객체 타입에서는 Self 타입 매개변수를 무시한다는 점에 유의하십시오. 이 매개변수는 알 수 없으며, 동적 디스패치의 특성상 항상 적절한 Self 타입을 기대하는 함수를 호출하게 됩니다. 그러나 다른 타입 매개변수는 주의해서 다뤄야 합니다. 그렇지 않으면 어떤 타입을 기대하는 함수를 다른 타입의 값으로 호출하게 될 수 있습니다.

무슨 뜻인지 알아보기 위해 다음과 같은 트레이트를 생각해 봅시다.

#![allow(unused)]
fn main() {
trait ConvertTo<A> {
    fn convertTo(&self) -> A;
}
}

직관적으로, 하나의 객체 O=&ConvertTo<Object>와 또 다른 객체 S=&ConvertTo<String>가 있다면, String <: Object이므로 S <: O입니다(Java와 유사한 “string”(문자열) 타입과 “object”(객체) 타입을 가정합니다. 이는 서브타이핑을 설명할 때 제가 즐겨 드는 예시입니다). 실제 알고리즘은 (명시적) 타입 매개변수들을 각각의 변성을 고려하여 쌍별로 비교하는 것입니다. 여기서 타입 매개변수 A는 공변이므로(반환 위치에만 나타나므로) String <: Object를 요구하게 됩니다.

하지만 (암묵적) Self 타입 매개변수의 바인딩은 고려하지 않았다는 점을 눈치채셨을 것입니다. 사실 이 값은 알 수 없으므로, 고려하지 않는 편이 맞습니다. 이 매개변수를 무시할 수 있는 이유는 바로 호출이 일어나기 전까지는 그 값을 알 필요가 없기 때문이며, 호출 시점에는 (말씀하신 대로) 가상 디스패치의 동적 특성 덕분에, 메서드를 호출한 특정 객체에서 Self가 어떤 값에 바인딩되어 있든 실행되는 코드가 올바르게 동작합니다. 따라서 Self는 A와 다릅니다. 호출자는 메서드 convertTo()의 반환 타입을 알기 위해 A를 알아야 하기 때문입니다. (덧붙여, Self가 수신자 위치 이외의 곳에 나타나는 메서드는 객체를 통해 호출할 수 없도록 하는 규칙이 있습니다.)

트레이트 변성과 vtable 해석

그러나 트레이트는 객체에만 사용되는 것이 아닙니다. 주어진 impl이 주어진 트레이트 바운드를 만족하는지 판단할 때에도 사용됩니다. 상황을 설정하기 위해, 다음과 같은 함수가 있다고 가정해 봅시다.

fn convertAll<A,T:ConvertTo<A>>(v: &[T]) { ... }

이제 Object에 대한 ConvertTo 구현이 있다고 가정해 봅시다.

impl ConvertTo<i32> for Object { ... }

그리고 문자열 배열에 대해 convertAll을 호출하려고 합니다. 또한 어떤 이유에서인지 타입 매개변수 T의 값으로 String을 명시적으로 지정한다고 가정해 봅시다.

let mut vector = vec!["string", ...];
convertAll::<i32, String>(vector);

이것은 허용됩니까? 다르게 말하면, Object에 대한 impl을 타입 String에 적용할 수 있습니까? 답은 ’그렇다’이지만, 그 이유를 알려면 어떤 일이 일어나는지 풀어서 살펴봐야 합니다.

  • convertAll은 벡터의 항목 중 하나를 가리키는 포인터를 생성하며, 이 포인터의 타입은 &String입니다

  • 그런 다음 객체에 사용하도록 의도된 convertTo()의 impl을 호출합니다. 이 impl의 타입은 fn(self: &Object) -> i32입니다.

    &String <: &Object이므로 self에 &String 타입의 값을 제공해도 문제없습니다.

좋습니다. 직관적으로는 이것이 허용되기를 바라므로, 다시 변성으로 돌아가서 올바른 결과를 계산하고 있는지 확인해 봅시다. 먼저 “String,i32에 대한 impl이 기대되는 곳에서 Object,i32에 대한 impl을 사용할 수 있는가?“라는 질문을 어떻게 표현할지 알아내야 합니다.

타입 클래스의 딕셔너리 전달 방식 구현을 떠올려 보면 도움이 될 수 있습니다. 그 경우 convertAll()은 impl을 나타내는 암묵적 매개변수를 받습니다. 요컨대, 우리가 가지고 있는 impl의 타입은 다음과 같습니다.

V_O = ConvertTo<i32> for Object

그리고 함수 프로토타입이 기대하는 impl의 타입은 다음과 같습니다.

V_S = ConvertTo<i32> for String

여느 인자와 마찬가지로, 주어진 값의 타입(V_O)이 기대되는 타입(V_S)의 서브타입이면 이는 허용됩니다. 그렇다면 V_O <: V_S입니까? 답은 여러 매개변수의 변성에 따라 달라집니다. 이 경우 Self 매개변수는 반공변이고 A는 공변이므로, 다음을 의미합니다.

V_O <: V_S iff
    i32 <: i32
    String <: Object

이 조건들이 충족되므로 문제가 없습니다.

변성과 연관 타입

연관 타입을 가진 트레이트는, 적어도 프로젝션 표현식은, 모든 입력에 대해 불변이어야 합니다. 이것이 왜 타당한지 알아보기 위해, 트레이트 참조에 대한 서브타이핑이 무엇을 의미하는지 생각해 봅시다:

<T as Trait> <: <U as Trait>

이는 T as Trait임을 알면 U as Trait임도 안다는 뜻입니다. 또한 이를 딕셔너리 전달 방식으로 생각하면, <U as Trait>에 대한 딕셔너리가 기대되는 곳에서 <T as Trait>에 대한 딕셔너리를 안전하게 사용할 수 있다는 뜻입니다.

문제는 <T as Trait>에서 타입을 프로젝션해 낼 수 있을 때, T==U가 아닌 한 <U as Trait>에서 프로젝션된 타입과의 관계를 전혀 알 수 없다는 점입니다(자세한 내용은 #21726을 참고하십시오). Trait를 불변으로 만들면 이것이 성립함이 보장됩니다.

또 다른 관련 이유는, 연관 타입을 가진 트레이트를 불변으로 만들지 않으면 프로젝션이 더 이상 단일 결과를 갖는 함수가 아니게 된다는 점입니다. 다음을 생각해 봅시다:

trait Identity { type Out; fn foo(&self); }
impl<T> Identity for T { type Out = T; ... }

이제 <&'static () as Identity>::Out이 있다면, 이는 임의의 'a에 대해 &'a ()로 유효하게 도출될 수 있습니다:

<&'a () as Identity> <: <&'static () as Identity>
if &'static () < : &'a ()   -- Identity is contravariant in Self
if 'static : 'a             -- Subtyping rules for relations

반면 이 변경으로 <'static () as Identity>::Out은 항상 &'static ()가 됩니다(이후 별도로 'a ()로 업캐스트될 수는 있습니다). 이는 #21750을 해결하는 데 도움이 되었습니다.