다형성과 제네릭

다형성은 단일 코드가 여러 유형에 걸쳐 균일하게 작동하도록 하며, 매개변수 다형성(제네릭), 임시 다형성(오버로딩 및 타입 클래스), 서브타입 다형성이 주요 형태입니다.

Definition

다형성은 단일 함수, 타입 또는 연산이 하나 이상의 타입 값에 적용될 수 있는 속성입니다. 매개변수 다형성은 타입 매개변수(제네릭)를 통해 균일하게 작동하는 반면, 임시 다형성은 타입별 구현으로 디스패치됩니다.

Scope

이 주제는 다형성의 주요 유형인 제네릭과 System F로 구현되는 매개변수 다형성, 오버로딩 및 타입 클래스를 통한 임시 다형성, 그리고 포함(서브타입) 다형성을 다룹니다. 또한 매개변수성(parametricity)과 그것이 제공하는 강력한 추론 원리, 그리고 제네릭 추상화가 어떻게 컴파일되고 제약되는지에 대해 설명합니다.

Core questions

• 제네릭은 타입 안전성을 희생하지 않고 어떻게 재사용을 제공하는가?
• 매개변수성(parametricity)이란 무엇이며, 그것이 어떤 보장을 제공하는가?
• 타입 클래스는 임시 오버로딩을 어떻게 체계화하는가?
• 제네릭 정의는 어떻게 컴파일되며, 타입 매개변수를 제약할 수 있는 제약 조건은 무엇인가?

Key theories

매개변수성(추상화 정리)

Reynolds의 추상화 정리는 매개변수 다형성 함수가 타입에 걸쳐 균일하게 동작함을 보여주는데, 이는 구체적인 타입 인스턴스화와 무관하게 가능한 동작을 제약하는 속성입니다.

자유 정리(Theorems for free)

Wadler는 매개변수 다형성 함수의 타입만으로도 그 동작에 대한 자유 정리를 함축한다는 것을 보여주었는데, 이는 매개변수성의 직접적이고 실용적인 결과입니다.

원칙적인 오버로딩을 위한 타입 클래스

Wadler와 Blott는 타입 클래스를 도입하여 임시 다형성에 일관된 타입 이론적 기반을 제공했으며, 여기서 오버로드된 연산은 메서드 구현의 암묵적인 딕셔너리를 전달함으로써 해결됩니다.

Clinical relevance

제네릭과 다형성은 현대 언어 전반에 걸쳐 재사용 가능한 라이브러리 설계 및 컬렉션 프레임워크의 핵심입니다. 타입 클래스와 그 유사체(트레이트, 개념, 프로토콜)는 원칙적이고 타입 안전한 오버로딩을 제공하며, 매개변수성은 정확성 추론 및 컴파일러 최적화를 지원합니다.

History

매개변수 다형성을 포착하는 System F는 1970년대 초 Girard와 Reynolds에 의해 독립적으로 발견되었습니다. ML은 추론을 통한 다형성을 실용화했습니다. Cardelli와 Wegner의 1985년 조사는 다형성의 형태를 분류했으며, Reynolds는 1983년에 매개변수성을 형식화했고, Wadler와 Blott의 1989년 타입 클래스는 Haskell의 오버로딩을 형성하고 다른 곳의 트레이트 및 개념에 영향을 미쳤습니다.

Debates

타입 소거(Erasure) 대 재구현된(reified) 제네릭

언어 구현자들은 제네릭을 컴파일할 때 단순하지만 런타임 타입 정보를 잃는 타입 소거 방식과, 복잡성과 코드 크기 증가를 대가로 런타임에 타입 매개변수를 재구현하여 인트로스펙션(introspection)을 가능하게 하는 방식 사이에서 논쟁합니다.

Key figures

• John Reynolds
• Jean-Yves Girard
• Philip Wadler
• Luca Cardelli
• Robin Milner

Seminal works

• reynolds1983
• wadler1989free
• wadler1989
• cardelli1985

Frequently asked questions

매개변수 다형성과 임시 다형성의 차이점은 무엇인가요?

매개변수 다형성은 모든 타입 인수에 대해 하나의 균일한 구현을 적용하는 반면(제네릭과 같이), 임시 다형성은 오버로딩이나 타입 클래스와 같이 타입별 구현을 선택합니다.

매개변수성(parametricity)은 우리에게 무엇을 제공하나요?

매개변수성은 제네릭 함수가 모든 타입 인스턴스를 균일하게 처리한다는 것을 보장하며, 이는 타입 시그니처만으로도 그 동작에 대한 '자유 정리'를 도출할 수 있게 합니다.