카테고리 보관물: Software

Software

현대 컴파일러에서 제네릭은 어떻게 구현됩니까? 0을 호출

여기서 의미하는 바는 일부 템플릿 T add(T a, T b) ...에서 생성 된 코드로 어떻게 이동합니까? 나는 이것을 달성 할 수있는 몇 가지 방법을 생각했다. 우리는 일반 함수를 AST에 저장 Function_Node한 다음 그것을 사용할 때마다 원래 함수 노드에 자체 유형의 사본으로 저장된 모든 유형의 사본을 원래 함수 노드에 저장 T한다. 사용 중입니다. 예를 들어 add<int>(5, 6)대한 일반적인 기능의 사본을 저장합니다 add및 모든 종류의 대체 T 사본에 와 int.

따라서 다음과 같이 보일 것입니다.

struct Function_Node {
    std::string name; // etc.
    Type return_type;
    std::vector<std::pair<Type, std::string>> arguments;
    std::vector<Function_Node> copies;
};

그런 다음 이들에 대한 코드를 생성 할 수 Function_Node있으며 사본 목록 을 방문하면 모든 사본 copies.size() > 0을 호출 visitFunction합니다.

visitFunction(Function_Node& node) {
    if (node.copies.size() > 0) {
        for (auto& node : nodes.copies) {
            visitFunction(node);
        }
        // it's a generic function so we don't want
        // to emit code for this.
        return;
    }
}

이것이 잘 작동합니까? 최신 컴파일러는이 문제에 어떻게 접근합니까? 아마도이 작업을 수행하는 또 다른 방법은 사본을 AST에 주입하여 모든 의미 단계를 거치도록 할 수 있다고 생각합니다. 예를 들어 Rust의 MIR 또는 Swifts SIL과 같은 즉각적인 형태로 생성 할 수 있다고 생각했습니다.

내 코드는 Java로 작성되었으며 여기 예제는 C ++입니다. 예제에 대한 설명은 조금 덜 장황하지만 원칙은 기본적으로 동일합니다. 질문 상자에 손으로 작성 되었기 때문에 약간의 오류가있을 수 있습니다.

이 문제에 접근하는 가장 좋은 방법과 마찬가지로 최신 컴파일러를 의미합니다. 그리고 제네릭을 말할 때 유형 삭제를 사용하는 Java 제네릭과 같은 의미는 아닙니다.

답변

현대 컴파일러에서 제네릭은 어떻게 구현됩니까?

최신 컴파일러의 작동 방식을 알고 싶다면 최신 컴파일러의 소스 코드를 읽으십시오. C # 및 Visual Basic 컴파일러를 구현하는 Roslyn 프로젝트부터 시작하겠습니다.

특히 형식 기호를 구현하는 C # 컴파일러의 코드에주의를 기울입니다.

https://github.com/dotnet/roslyn/tree/master/src/Compilers/CSharp/Portable/Symbols

또한 변환 규칙에 대한 코드를보고 싶을 수도 있습니다. 제네릭 형식의 대수적 조작과 관련된 내용이 많이 있습니다.

https://github.com/dotnet/roslyn/tree/master/src/Compilers/CSharp/Portable/Binder/Semantics/Conversions

나는 후자를 읽기 쉽도록 노력했다.

이것을 달성하는 몇 가지 방법을 생각했습니다. 일반 함수를 AST에 Function_Node로 저장 한 다음 사용할 때마다 원래 함수 노드에 모든 유형 T로 대체 된 자체 사본을 저장합니다. 사용되고 있습니다.

제네릭이 아닌 템플릿 을 설명하고 있습니다. C # 및 Visual Basic은 형식 시스템에 실제 제네릭이 있습니다.

간단히, 그들은 이렇게 작동합니다.

  • 컴파일 타임에 형식적으로 형식을 구성하는 규칙을 설정하는 것으로 시작합니다. 예를 들면 다음과 같습니다. intis a type, type parameter Tis a type, any typeX 에 대해 배열 유형 X[]도 유형 입니다.

  • 제네릭 규칙에는 대체가 포함됩니다. 예를 들어 class C with one type parameter유형이 아닙니다. 유형을 만들기위한 패턴입니다. class C with one type parameter called T, under substitution with int for T 이다 일종.

  • 형식 간 관계를 설명하는 규칙 (할당시 호환성, 식 형식 결정 방법 등)은 컴파일러에서 설계 및 구현됩니다.

  • 메타 데이터 시스템에서 일반 유형을 지원하는 바이트 코드 언어가 설계되고 구현됩니다.

  • 런타임시 JIT 컴파일러는 바이트 코드를 기계 코드로 변환합니다. 일반 전문화가 주어지면 적절한 기계 코드를 구성해야합니다.

예를 들어 C #에서는 말할 때

class C<T> { public void X(T t) { Console.WriteLine(t); } }
...
var c = new C<int>();
c.X(123);

그런 다음 컴파일러는에서 C<int>인수 int가 유효한 대체인지 확인하고 T그에 따라 메타 데이터 및 바이트 코드를 생성합니다. 런타임시 지터는 a C<int>가 처음으로 생성되고 있음을 감지 하고 적절한 머신 코드를 동적으로 생성합니다.

답변

제네릭 (또는 파라 메트릭 다형성)의 대부분의 구현은 유형 삭제를 사용합니다. 이렇게하면 일반 코드를 컴파일하는 문제가 크게 단순화되지만 박스 형식에만 적용됩니다. 각 인수는 사실상 불투명 포인터이므로 인수에 대한 작업을 수행하려면 VTable 또는 이와 유사한 디스패치 메커니즘이 필요합니다. 자바에서 :

<T extends Addable> T add(T a, T b) { … }

컴파일하고 형식을 확인하고 다음과 같은 방식으로 호출 할 수 있습니다.

Addable add(Addable a, Addable b) { … }

제외시켰다 제네릭이 전화 사이트에서 훨씬 더 많은 정보 유형 검사를 제공하고 있다고. 이 추가 정보는 특히 제네릭 형식이 유추 될 때 형식 변수 로 처리 할 수 ​​있습니다 . 타입 검사 동안, 각각의 제네릭 타입은 변수로 대체 될 수 있습니다 $T1.

$T1 add($T1 a, $T1 b)

그런 다음 구체적인 변수로 대체 될 수있을 때까지 유형 변수가 더 많은 사실로 업데이트됩니다. 타입 검사 알고리즘은 이러한 타입 변수가 아직 완전한 타입으로 해석되지 않더라도 수용 할 수있는 방식으로 작성되어야합니다. Java 자체에서는 보통 함수 호출 유형을 알기 전에 인수 유형을 알기 때문에 일반적으로 쉽게 수행 할 수 있습니다. 주목할만한 예외는 함수 인수와 같은 람다 식이며 이러한 유형 변수를 사용해야합니다.

훨씬 나중에 최적화 프로그램 은 특정 인수 집합에 대해 특수 코드를 생성 할 수 있으며 , 이는 사실상 일종의 인라인이됩니다.

일반 함수가 형식에 대한 작업을 수행하지 않고 다른 함수에만 전달하는 경우 일반 형식 인수에 대한 VTable을 피할 수 있습니다. 예를 들어 Haskell 함수 call :: (a -> b) -> a -> b; call f x = f x는 x인수 를 상자에 넣을 필요가 없습니다 . 그러나 크기를 모른 채 값을 통과 할 수있는 호출 규칙이 필요하므로 기본적으로 포인터로 제한됩니다.

C ++은 이런 점에서 대부분의 언어와는 매우 다릅니다. 템플릿 클래스 또는 함수 (여기서는 템플릿 함수에 대해서만 설명하겠습니다) 자체로는 호출 할 수 없습니다. 대신 템플릿은 실제 함수를 반환하는 컴파일 타임 메타 함수로 이해해야합니다. 잠시 동안 템플릿 인수 유추를 무시하면 일반적인 접근 방식은 다음 단계로 요약됩니다.

  1. 제공된 템플리트 인수에 템플리트를 적용하십시오. 예는 전화 template<class T> T add(T a, T b) { … }로하는 것은 add<int>(1, 2)우리에게 실제 기능을 줄 것이다 int __add__T_int(int a, int b)(이름 엉망으로 접근 방식을 사용 또는 무엇이든).

  2. 해당 함수에 대한 코드가 현재 컴파일 단위에서 이미 생성 된 경우 계속하십시오. 그렇지 않으면 함수 int __add__T_int(int a, int b) { … }가 소스 코드에 작성된 것처럼 코드를 생성하십시오 . 여기에는 모든 템플리트 인수가 해당 값으로 대체됩니다. 아마도 AST → AST 변환 일 것입니다. 그런 다음 생성 된 AST에서 유형 검사를 수행하십시오.

  3. 소스 코드처럼 호출을 컴파일하십시오 __add__T_int(1, 2).

C ++ 템플릿은 여기에서는 설명하고 싶지 않은 과부하 해결 메커니즘과 복잡한 상호 작용을합니다. 또한이 코드 생성을 통해 템플릿 방식을 가상으로 만들 수 없습니다. 유형 삭제 기반 접근 방식에는 이러한 실질적인 제한이 없습니다.

이것이 컴파일러 및 / 또는 언어에 어떤 의미가 있습니까? 제공하려는 제네릭의 종류에 대해 신중하게 생각해야합니다. 박스형 유형을 지원하는 경우 유형 유추가없는 유형 삭제가 가장 간단한 방법입니다. 템플릿 전문화는 상당히 단순 해 보이지만 일반적으로 템플릿이 정의 사이트가 아닌 호출 사이트에서 인스턴스화되므로 이름 변경 및 여러 컴파일 단위의 경우 상당한 출력 복제가 필요합니다.

당신이 보여준 접근법은 본질적으로 C ++와 같은 템플릿 접근법입니다. 그러나 특수 / 인스턴스화 된 템플릿을 기본 템플릿의 “버전”으로 저장합니다. 이것은 오해의 소지가 있습니다. 그것들은 개념적으로 동일하지 않으며 함수의 다른 인스턴스화는 완전히 다른 유형을 가질 수 있습니다. 함수 오버로드를 허용하면 장기적으로 복잡해집니다. 대신, 이름을 공유하는 가능한 모든 기능과 템플릿을 포함하는 과부하 세트에 대한 개념이 필요합니다. 오버로드 해결을 제외하고는 서로 다른 인스턴스화 된 템플릿이 완전히 분리 된 것으로 간주 할 수 있습니다.

답변