다형성

0. 들어가며

보통 다형성은 상속과 오버라이딩으로 이해된다. Animal 변수에 Dog 객체를 넣고, Speak()를 호출하면 실제로는 Dog.Speak()가 실행된다는 그 예제다.

using System;

public abstract class Animal
{
    public abstract void Speak();
}

public sealed class Dog : Animal
{
    public override void Speak()
    {
        Console.WriteLine("Woof");
    }
}

public sealed class Cat : Animal
{
    public override void Speak()
    {
        Console.WriteLine("Meow");
    }
}

public static class Program
{
    public static void Main()
    {
        Animal animal = new Dog();

        animal.Speak(); // Woof
    }
}

(최근에는 interface 구현이 일반적이나 알기 쉽게
옛날버전으로 구현했다)

여기서 변수 animal의 정적 타입은 Animal이지만, 실제 객체는 Dog다. 그래서 animal.Speak()를 호출하면 Dog.Speak()가 실행된다. 상위 타입으로 말하고, 실제 동작은 하위 타입이 결정한다.

입문용으로는 나쁘지 않고, 실제로 꽤 많은 부분을 이해시켜주어서 객체지향의 기본기를 다지는 데는 훌륭한 출발점이다.

하지만 이 예제 하나로 다형성의 전모를 설명하려면, 이내 한계에 부딪힌다. 상속 기반 다형성은 계층 구조가 얕고, 동작이 명확할 때는 강력하지만, 그 구조가 깊어질수록 오히려 코드의 유연성을 해치는 경우가 많다. 사실 대부분의 다형성 구현에는 비판할 지점이 있다. 그럼에도 상속 기반 다형성이 유독 많이 비판되는 이유는, 역설적으로 그것이 너무 성공적이었기 때문이기도 하다.

더군다나 이 예제는 "이름은 같지만 다른 동작"이라는 겉모습만 보여줄 뿐, 다형성이 왜 필요한지, 그리고 어떤 문제를 해결하기 위해 존재하는지는 충분히 설명하지 못한다.

다형성의 영어 표은 Polymorphism다. poly는 여러(many), morph는 형태(form)다. 생물학에서는 같은 종 안에서 성별, 유전형, 환경 조건에 따라 서로 다른 형태가 나타나는 현상을 가리킬 때 이 말을 쓴다. 나비의 날개 무늬처럼 여러 morph가 공존하는 예를 떠올리면 된다. (애벌레가 성충이 되는 변태(metamorphosis)와는 다르다.)

이 비유를 프로그래밍으로 옮기면, 은유는 자연의 것이 아니라 기계의 것이 된다.
겉으로는 같은 이름, 같은 함수, 같은 인터페이스처럼 보이지만, 그 뒤에서는 두 가지 일이 벌어진다. 어떤 경우에는 타입이 달라도 같은 구조의 코드가 쓰이고, 어떤 경우에는 타입에 따라 다른 구현이 선택된다.

호출자에게는 하나의 이름이지만, 컴파일러와 런타임은 그 뒤에서 다른 함수, 다른 테이블, 다른 코드 생성 방식, 다른 메모리 표현을 다룰 수 있다.

이 문서는 다형성을 "하나의 이름이 여러 타입과 어떻게 관계 맺는가"라는 질문으로 바라본다.
상속과 오버라이딩은 그중 한 장면일 뿐이다. 제네릭, 오버로딩, coercion, type class, trait object, multiple dispatch까지 포함하면 많이 복잡해진다. 우선 원전의 정의부터 시작해서 순서대로 따라갈 생각이다.

Strachey의 두 축

Strachey는 이 복잡성을 두 개의 축으로 먼저 정리했다.

Cardelli-Wegner의 확장

Cardelli-Wegner는 그 구분을 다시 넓혀 parametric, inclusion/subtyping, overloading, coercion을 한 표 안에 넣었다.

Wadler-Blott의 전환

Wadler와 Blott는 다른 방향을 건드렸는데,ad hoc polymorphism을 버리는 대신, 타입 시스템 안에서 규율화하는 방법을 제안한다.

type class는 "아무 타입이나 알아서 처리한다"는 방식은 아니다.
대신 Eq, Ord, Show 같은 계약을 세우고,
컴파일러는 그 계약을 만족하는 구현 증거(dictionary)를 찾아 암묵 인자로 전달한다.

이후 언어들이 계약을 표현하는 방식

• Haskell: type class

• Rust: trait

• Swift: protocol

• Scala: given/using , type class pattern

• C#: interface + generic constraint

• TypeScript: structural constraint
  

우리는 흔히 '다형성을 위한 계약' 하면 하스켈의 타입 클래스를 떠올리지만, 실제 언어들의 계약 장치는 하스켈의 직계 자식이 아니다.

이는 생물학의 게화(Carcinization, 서로 다른 계통의 생물이 게의 형태로 진화하는 현상)처럼 완전히 다른 계통에서 출발해 비슷한 형태로 수렴된 결과다.
각 계통의 원전(原典)을 따라가 보면, 왜 C#을 하스켈 식으로 보면 어색한지, 왜 타입스크립트가 독자적인 길을 걸었는지가 선명해진다.

각 언어의 실제 구현을 들여다보면 OOP 인터페이스, ML 모듈 시스템, 구조적 타이핑, 암시적 파라미터라는 서로 다른 계보가 섞여 있다.
C#의 제네릭 제약은 nominal type과 OOP 인터페이스 계보에 가깝다. where T : IFoo처럼 특정 이름의 계약을 구현했음을 요구할 수도 있고, class, struct, new(), unmanaged처럼 타입의 표현 방식이나 생성 가능성에 대한 제약을 걸 수도 있다.

TypeScript의 구조적 제약은 덕 타이핑의 감각을 정적 타입 검사로 가져온 것에 가깝다. 런타임에 “될 것 같으면 호출한다”가 아니라, 컴파일 타임에 필요한 구조가 있는지를 검사한다.언어마다 제각기 다른 방식으로 다형성을 구현하지만, 결국 이들은 동일한 압력을 받아 하나의 목표를 향해 수렴된다. "아무 타입이나 받겠다"는 선언은 너무나 위험하기에, 시스템은 특정 능력이나 구조를 만족하는 타입만 받도록 엄격한 제약을 걸어야 한다.

정적 타입 언어는 그 조건을 타입 표면에 드러내려 하고, 동적 언어는 프로토콜, 덕 타이핑, 런타임 검증으로 그 자리를 메운다. 결국 다형성은 자유라기보다 계약에 가깝다. 그 계약은 정적 타입, 테스트, 런타임 검증 중 어딘가에 반드시 존재해야 한다. 만약 그 어디에도 없다면, 그것은 다형성이 아니라 런타임 도박에 불과하다.

1. Strachey 1967: ad hoc vs parametric

Christopher Strachey의 Fundamental Concepts in Programming Languages는 1967년 코펜하겐 여름학교 강의에서 나온 텍스트다. 이 글은 L-value/R-value, referential transparency, ad hoc polymorphism, parametric polymorphism 같은 표현을 널리 남긴 원전으로 자주 언급된다.¹²

Strachey가 다형성을 꺼내는 맥락은 정확히 지금에서야 유추할 수 없지만, 현대 시대에 사는 우리가 유추할때 아마 이럴 것이다.

'타입을 동적으로 취급한다고 해서 다형적 연산자의 문제가 사라지지 않는다고 본다. 결국 어느 버전의 연산자를 고를지, 필요한 형변환을 어디에 끼워 넣을지 결정해야 하기 때문'이다.¹
그가 판정했던 구분은 꽤 오래 시간 지속됐다.

ad hoc polymorphism:
  타입마다 다른 구현을 고른다.

parametric polymorphism:
   타입의 구체 구조를 모르고도 균일하게 동작한다.

예를 들어 +는 타입에 따라 구현이 다르다.

int + int, float + float, string + string은 같은 기호를 쓴다. 하지만 내부 구현은 타입마다 달라진다.
이쪽이 ad hoc polymorphism이다.

개인 메모:여기서도 한국어권 프로그래머의 불리함이 드러난다. 우리는 ad hoc을 “애드혹”으로, parametric을 “매개변수적”으로 외우지만, 임시 다형성이나 매개변수 다형성이나 우리에게 익숙치 않다. 영어권 학습자는 용어의 뉘앙스에서 출발하지만, 우리는 번역어라는 껍데기에서 출발한다. 그리고 대개 이런 번역은 한자어로 번역되기도해서 학습 비용도 비싸다.

한국인이 프로그래밍을 제대로 알기엔 그 속살이 너무 두꺼운 껍질 속에 쌓여있기때문일 것이다.

반면 identity는 타입이 무엇이든 같은 구조로 동작한다.

id :: a -> a
id x = x

a가 Int든 String이든 List<T>든 상관없다. 함수가 하는 일은 변하지 않는다. 받은 것을 그대로 돌려준다.
이쪽은 parametric polymorphism이다.

Strachey식 구분이 묘하게 오래가는 이유는 단순하다.
질문이 아직도 유효하기 때문이다.

• 같은 이름인데 타입마다 다른 구현을 고르는가?

• 아니면 타입을 모르더라도 같은 구조로 동작하는가?
  

사실상 현대 언어의 큰 갈림길이 어느정도 보인다.

우리의 목적은 프로그래밍 언어에서 타입(type)의 개념을 이해하고, 타입 이론의 최근 연구를 반영한 타입이 지정된(typed) 다형적(polymorphic) 프로그래밍 언어의 모델을 제시하며, 최근 연구가 실용적인 프로그래밍 언어 설계에 갖는 연관성을 살펴보는 것입니다.

2. Cardelli-Wegner 1985: 분류표가 정리된다

Luca Cardelli와 Peter Wegner의 1985년 논문 On Understanding Types, Data Abstraction, and Polymorphism은 다형성 분류를 더 체계화한 대표 원전이다.³

자주 인용되는 분류는 대략 이런 모양이다.

(On Understanding Types, Data Abstraction, and Polymorphism의 Figure 1)

Polymorphism
├─ Universal polymorphism
│  ├─ Parametric polymorphism
│  └─ Inclusion polymorphism
└─ Ad hoc polymorphism
   ├─ Overloading
   └─ Coercion

여기서 OOP 독자가 가장 익숙하게 보는 것은 inclusion polymorphism이다. 오늘날 말하는 subtype polymorphism에 가깝다.

IShape shape = new Circle();
shape.Draw();

shape의 정적 타입은 IShape다. 실제 호출되는 구현은 Circle.Draw()다. 호출자는 상위 타입으로 말하고, 런타임 객체가 구현을 고른다.

초보자는 보통 여기서 다형성을 처음 만난다. 그러다 보니 "다형성 = 상속 + override"로 외우고 끝나기 쉽다. 나도 처음엔 그랬고, 대부분 그렇다.
교재도 그렇게 생겼다.

개인 메모:한국 교재는 아예 이런 걸 설명하지 않지만, 나는 대체 왜 한국어라는 저주받은 언어에 종속되어 지적인 세계로 향할 수 없는가.

Cardelli-Wegner 관점에서는 그건 한 칸에 불과하다.

• List<T>의 T는 parametric polymorphism

• 1 + 2와 1.0 + 2.0의 +는 overloading

• int가 double로 자동 변환되는 것은 coercion

• Dog를 Animal로 다루는 것은 inclusion/subtype polymorphism
  

Cardelli-Wegner는 ad hoc polymorphism을 universal polymorphism과 구분되는, 더 비균일하고 구현 의존적인 형태로 분류한다. overloading과 coercion은 겉으로는 하나의 연산이 여러 타입에 적용되는 것처럼 보이지만, 구현 관점에서는 서로 다른 함수 선택이나 타입 변환으로 풀리는 경우가 많기 때문이다.³

이쯤에서 다형성을 하나의 기능처럼 말하기가 어려워진다. 하나의 코드, 이름, 연산, 추상 경계가 여러 타입과 관계 맺는 방식들의 묶음에 더 가깝다.

3. Wadler-Blott 1989: ad hoc을 덜 ad hoc하게

Philip Wadler와 Stephen Blott의 1989년 논문 How to Make Ad-Hoc Polymorphism Less Ad Hoc은 Haskell type class의 원전이다.⁴⁵

제목이 거의 논문 요약이다.
오버로딩은 편하지만 제멋대로 흐르기 쉽다.

== 라는 연산은 여러 타입에서 쓸 수 있어야 한다.
그런데 모든 타입에서 쓸 수 있지는 않다.
또 타입마다 구현은 달라야 한다.

Strachey식으로 보면 이것은 ad hoc polymorphism이다. 타입마다 구현이 다르기 때문이다.

Wadler-Blott의 아이디어는 이 ad hoc성을 없애는 게 아니라, 타입 시스템 안으로 끌고 들어오는 것이다.

(How to Make Ad-Hoc Polymorphism Less Ad Hoc Figure 3)

class Eq a where
  (==) :: a -> a -> Bool

instance Eq Int where
  (==) = primIntEq

instance Eq Bool where
  (==) True True = True
  (==) False False = True
  (==) _ _ = False

이제 ==는 아무 타입에나 열려 있는 기호가 아니라, Eq a라는 증거가 있는 타입에서만 쓸 수 있는 연산이 된다.

member :: Eq a => a -> [a] -> Bool

이 타입은 "a가 Eq 인스턴스를 가진 타입이라면, a 값 하나와 a 리스트를 받아 Bool을 돌려준다"로 읽으면 된다.

type class는 오버로딩을 하되, 어떤 타입이 그 연산을 지원하는지 타입 시스템이 추적하게 만든다.
논문 제목도 잘 붙었다. ad hoc polymorphism을 없애지 않고, less ad hoc하게 만든다.

4. FP에서 다형성과 변형 처리는 어떻게 보이는가

OOP만 보고 다형성을 배웠다면 FP 쪽으로 눈을 돌릴 필요가 있다.

Strachey의 parametric polymorphism과 Wadler-Blott의 type class는 오히려 함수형 프로그래밍 쪽에서 더 선명하게 보인다.

OOP에서 초보자가 흔히 보는 다형성은 이런 모양이다.

IShape shape = new Circle();
shape.Draw();

중심에는 receiver object가 있다. shape라는 객체에 Draw 메시지를 보내고, 실제 구현은 런타임 객체가 결정한다.

반면 FP의 감각은 다르다.

map :: (a -> b) -> [a] -> [b]

map은 a와 b가 무엇인지 모른다. 그래도 리스트 구조를 따라가며 함수를 적용할 뿐이므로, 원소 타입이 무엇이든 같은 구조로 동작한다.

length :: [a] -> Int

length도 리스트 안의 원소 타입을 모른다. 애초에 알아야 할 필요가 없기 때문에 length [1,2,3]도 되고, length ["a","b"]도 된다. 이쪽이 parametric polymorphism의 감각이다.

이 흐름은 OOP의 "객체가 자기 메서드를 override한다"는 그림과는 꽤 다르게 이해해야한다.

OOP subtype polymorphism:
  같은 메시지를 보내고, receiver의 실제 타입이 구현을 고른다.

FP parametric polymorphism:
  타입을 모른 채로도 성립하는 구조만 사용한다.

FP에는 ad hoc polymorphism도 있다. Haskell type class가 대표적이다.

sort :: Ord a => [a] -> [a]

sort는 아무 타입의 리스트나 정렬하지 않는다. Ord a라는 계약이 있는 타입만 받는다.
중요한 핵심은 "a가 무엇이든 된다"가 아니라 "a가 순서를 비교할 수 있으면 된다"다.

이 점에서 type class는 OOP interface와 비슷한 냄새가 난다.
하지만 중심은 다르게 이해해야만 한다.

OOP interface:
  객체가 메서드를 가진다.
  obj.compareTo(other)

FP type class:
  타입에 대한 연산 dictionary/evidence가 있다.
  compare(dict, x, y)

또 하나 FP에서 중요한 변형 처리 방식은 ADT와 pattern matching이다.

data Shape
  = Circle Double
  | Rectangle Double Double

area :: Shape -> Double
area shape =
  case shape of
    Circle r -> pi * r * r
    Rectangle w h -> w * h

여기서는 shape.Draw()를 호출하지 않는다. 대신 값의 형태를 열어보고 경우를 나눈다.

이 차이 때문에 FP와 OOP는 확장 방향도 다르게 느껴진다.

OOP:
  새 타입 추가가 쉽다.
  기존 operation은 interface method로 묶인다.
  새 operation을 추가하려면 여러 class를 수정해야 할 수 있다.

FP ADT:
  새 operation 추가가 쉽다.
  pattern matching 함수 하나를 추가하면 된다.
  새 variant를 추가하면 기존 pattern matching들을 고쳐야 한다.

이 문제가 Wadler가 말한 expression problem으로 이어진다.⁶

여기서 map 같은 예제는 조금 조심해서 봐야 한다. map :: (a -> b) -> [a] -> [b]는 함수를 인자로 받으니 higher-order function이고, 동시에 a와 b가 무엇인지 고정하지 않으니 parametric polymorphic function이다.
실제 FP 코드에서는 이런 식으로 둘이 자주 겹친다.
설명하려고 나눠놓은 칸인데 실전 코드에서는 한 함수 안으로 같이 들어오는 것이다.

정리하면 FP 쪽에서는 다형성과 변형 처리가 이런 모습으로 나타난다.

1. parametric polymorphism
   타입을 모르고도 같은 구조로 동작한다.
   예: map, length, id

2. ad hoc polymorphism / type class
   특정 능력을 가진 타입에서만 같은 이름의 연산을 쓴다.
   예: Eq, Ord, Show

3. higher-order function
   고전적 의미의 polymorphism이라기보다,
   함수를 인자로 받아 행동 선택을 값으로 넘긴다.
   예: map, filter, fold

4. ADT + pattern matching
   고전적 의미의 polymorphism이라기보다,
   값의 여러 형태를 합 타입으로 표현하고 case로 분기한다.
   예: Maybe, Either, Shape

OOP는 주로 객체와 메시지 디스패치로 다형성을 체감한다. FP는 타입 파라미터, 타입 클래스, 함수 인자, 합 타입 쪽에서 체감한다.

여기서 어느 쪽이 더 "진짜 다형성"인지 따지는 일은 시간이 많을때만 하는게 좋다.
higher-order function과 ADT + pattern matching은 고전적 의미의 polymorphism에서 조금 비켜 있지만, FP가 변형과 행동 선택을 처리할 때 자주 꺼내는 도구다.
결국 우리가 지켜보아야할 것은 확장 방향과 비용 구조이다.

5. 다형성 구현의 핵심 질문

다형성을 문법 이름으로만 보면 금방 헷갈린다. interface, generic, trait, type class가 전부 다형성 근처에 있지만, 실제 비용은 서로 다른 곳에서 발생한다.
구현을 볼 때는 먼저 4가지 질문으로 구성해보자.

1. 어떤 구현을 호출할지 언제 결정하는가?
   컴파일 타임인가, 런타임인가?

2. 타입 정보는 런타임에 남는가?
   지워지는가, metadata로 남는가, 코드가 복제되는가?

3. 같은 코드 하나를 공유하는가?
   타입별 specialized code를 만드는가?

4. 비용은 어디로 가는가?
   런타임 dispatch 비용인가, 컴파일 시간/바이너리 크기 비용인가?

이 질문을 건너뛰면 "제네릭은 빠르다", "interface는 느리다", "type class는 OOP랑 같다" 같은 말만 남는다.
사실 대부분 이정도만 알아도 충분한데, 명확하게는 다르다. 이런게 제일 힘들다. 어중간하게 알아도 동작은 하지만, 정확하지는 않은 것들.
어떤 경우에는 맞고 어떤 경우에는 틀리는데, 그 차이가 바로 결정 시점과 타입 정보, 코드 공유 방식에서 갈린다.

6. subtype polymorphism: vtable, message lookup, interface dispatch

OOP식 다형성을 구현할 때 가장 익숙한 방식은 런타임 디스패치다.호출자는 상위 타입만 보고 호출하지만, 실제로 어떤 구현으로 갈지는 실행 시점의 객체 표현과 디스패치 메커니즘에 의해 결정된다.
쉽게 표현하면 대략 이렇다.

Base reference
  └─ 실제 객체의 vtable / method table을 따라감
       └─ 실제 구현 메서드 호출

물론 실제 구현은 언어와 VM에 따라 vtable, method table, interface table, selector lookup, inline cache 등으로 달라지지만, 이건 컴파일러 뜯어보기 같은 걸 하는 애들이나 하는것이다.

C++의 virtual, Java/C#의 virtual/interface dispatch, Rust의 dyn Trait이 이 계열에 들어간다.
문법은 다르지만 핵심은 결이 같다는 것이다. 일단 핵심은 호출 지점에서 바로 함수 주소가 고정되지 않고, 객체 표현이나 trait object가 제공하는 디스패치 정보를 통해 간접 호출한다.

Simula와 virtual procedure

Simula 67은 class, subclass, virtual procedure 같은 OOP 핵심 장치를 일찍 제공했다.⁷⁸ Simula의 virtual procedure는 서브클래스에서 재정의될 수 있고, 베이스 쪽 호출이 실제 하위 구현으로 연결된다. BETA의 virtual class 논의는 이 계보가 이후에 어떻게 확장됐는지 볼 때 같이 참고할 만하다.⁹¹⁰

여기서 OOP식 다형성의 기본 구조가 나온다.

상위 타입으로 말한다: 호출자는 구체적인 대상을 몰라도, 약속된 인터페이스(계약)만 믿고 메시지를 던진다.

하위 타입이 결정한다: 메시지를 받은 객체는 자신의 태생(구체 클래스)에 맞춰 고유한 방식으로 응답한다.

런타임이 지배한다: 이 모든 결합은 코드를 짤 때가 아니라, 코드가 실제로 실행되는 순간(Runtime)에 극적으로 맺어진다.

Smalltalk와 message sending

Smalltalk는 "메서드 호출"보다 "메시지 전송"이라는 사고를 전면에 세웠다. 객체는 메시지를 받고, 자기 클래스와 상속 체계에서 해당 selector를 찾는다.¹¹
따라서, Smalltalk식으로 보면 다형성은 별난 기능이라기보다 객체간에 통신할때 자연스럽게 따라오는 결과에 가깝다고 이해할 수 있다.

shape draw

shape가 원인지 사각형인지 호출자는 모른다. 그냥 draw 메시지를 보낸다. 받을 수 있으면 처리하고, 못 받으면 doesNotUnderstand: 쪽으로 간다. 이 발상은 현대의 동적 디스패치, duck typing, protocol/interface 기반 호출과 같은 문제 공간에 걸쳐 있다.

Smalltalk, Java interface, Rust trait object를 한 덩어리로 놓으면 곤란하다. 그래도 "호출자는 추상적인 요청을 보내고, 실제 구현 선택은 뒤로 미룬다"는 감각은 이어진다.

vtable의 비용

vtable/interface dispatch의 직접 비용은 보통 세 군데에서 난다.

• 간접 호출

• 인라이닝 어려움

• 분기 예측 실패 가능성

간접 호출이 비싼 이유는 무엇인가? 단순히 "포인터를 한 번 더 읽는다"에서 끝나지 않는다.
CPU 파이프라인 관점에서는 호출 타겟 주소를 컴파일 타임에 고정하기 어렵고, 런타임에 vtable이나 method table을 따라가야 한다. 분기 예측기가 타겟을 잘 맞히면 비용은 작다. 반면 여러 구현이 계속 섞이는 polymorphic call site에서는 예측 실패 확률이 올라가고, 예측이 틀리면 CPU는 이미 가져온 명령을 버린 뒤 파이프라인을 다시 채워야 한다. 흔히 말하는 pipeline flush 비용이다.

"virtual call은 항상 느리다"로 외우면 또 틀린다. 단일 구현만 반복되는 monomorphic call site는 JIT이나 PGO가 devirtualization과 inlining으로 지워버리기도 한다. 반면 실제 타입이 계속 바뀌는 megamorphic call site는 예측과 인라이닝 양쪽에서 불리하다. 결국 비용은 문법 하나가 아니라 호출 패턴에서 나온다.

여기에 참조 기반 객체 컬렉션, 힙 할당, 포인터 추적이 결합되면 캐시 locality까지 흔들릴 수 있다. 이 경우 비용의 원인은 vtable 그 자체보다 객체 배치와 메모리 레이아웃에 더 가깝다. 가상 호출 하나만 보고 성능을 단정하면, 보통 엉뚱한 곳에 화를 내게 된다.

대신 얻는 것도 분명히 있다.

• 런타임 교체 가능성

• 플러그인 구조

• 이질적 객체 컬렉션

• ABI boundary 뒤 구현 은닉
  

실무에서는 "다형성이 느린가?"보다 "이 위치에서 런타임 디스패치가 필요한가, 그리고 이 호출 지점이 hot path인가?"를 묻는 것이 맞다.
다형성이 너무 많은 걸 내포하기때문에 질문을 할땐 그 안에 있는 부분을 떼서 질문해야하는 것이다.

7. DOP/Data-Oriented Design에서 다형성은 어떻게 보이는가

Data-Oriented Programming 또는 Data-Oriented Design 관점으로 오면 질문이 조금 바뀌는데, DOP를 Strachey나 Cardelli-Wegner식 다형성 분류표 안에 넣으면 이상한 지점이 있다.(애초에 DOP에서는 이런 질문도 잘 안하기도 한다)
이쪽은 subtype polymorphism의 hot path 비용에 대한 반응이기도 하지만, 더 넓게는 프로그램을 객체 관계보다 데이터 배치와 접근 패턴 중심으로 다시 보는 실행 모델에 가깝다.

OOP 예제에서는 보통 이렇게들 쓴다.

foreach (IShape shape in shapes)
{
    shape.Draw();
}

호출자는 IShape만 알고, 실제 구현은 Circle, Rectangle, Line 같은 런타임 타입이 결정한다. OOP 교과서에서는 예쁘게 보이고, 또한 실제로 설계 관점에서는 유용한 그림이기도 하다.

그런데 DOP로 생각하는 사람은 이 코드를 보자마자 다른 장면을 먼저 떠올린다.

객체마다 실제 타입이 다를 수 있다.
매번 indirect dispatch가 발생할 수 있다.
객체가 힙에 흩어져 있을 수 있다.
hot field와 cold field가 섞일 수 있다.
CPU는 같은 연산을 연속적으로 보기 어렵다.
SIMD/vectorization 기회가 줄어들 수 있다.

DOP는 다형성을 반드시 객체의 virtual method로 표현하지 않는다. 데이터를 종류별로 나누거나, tag를 두거나, 같은 연산을 수행할 데이터끼리 모아 batch 처리한다. "누가 행동을 소유하는가"보다 "같은 모양의 데이터를 얼마나 연속적으로 처리할 수 있는가"가 더 중요해지는 순간이 있다.

예를들면 이런 것이다.

circles:
  centerX[]
  centerY[]
  radius[]

rectangles:
  x[]
  y[]
  width[]
  height[]

그러면 렌더링도 객체가 스스로 Draw()를 호출하는 방식에서 벗어난다. system/pass가 같은 종류의 데이터를 한 번에 처리한다.

drawCircles(circles)
drawRectangles(rectangles)

이 경우 subtype polymorphism의 역할 일부가 객체 디스패치에서 데이터 분류와 처리 패스로 이동한다. 다형성이 사라진다기보는 다형성이 발현하는 위치가 바뀐다라고 이해하는 것이 옳은 이해이다.

OOP:
  객체가 자기 행동을 고른다.
  shape.Draw()

DOP:
  데이터가 분류되고,
  시스템이 같은 형태의 데이터를 batch로 처리한다.
  drawCircles(circleData)
  drawRectangles(rectangleData)

DOP가 subtype polymorphism을 경계하는 이유를 "객체 추상화가 나쁘다" 같은 이유로들 설명하는데, 더 직접적인 이유는 hot path에서 런타임 디스패치, 포인터 추적, cache miss, vectorization 방해가 한꺼번에 나타날 수 있기 때문이다.
게임 루프나 렌더링, 물리, 대량 시뮬레이션에서는 이런 비용이 생각보다 금방 체감할 수 있다.

DOP로 간다고 변형이 없어지지는 않는다. 원, 사각형, 선, 파티클, 충돌체가 전부 같은 모양일 수는 없듯 말이다. 이 문제는 SOLID/LSP 논의에서 자주 나오는 “모든 변형을 상속 계층으로 밀어 넣으면 모델이 깨질 수 있다”는 문제와도 닿아 있다.

tagged union / enum
type id + switch
종류별 dense array
function pointer table
command buffer
ECS의 component query

tagged union은 가능한 변형의 집합이 비교적 닫혀 있을 때 좋다.
새 연산을 추가하기는 쉽지만, 새 variant를 추가하면 switch 지점을 갱신해야 한다. 반대로 subtype polymorphism은 새 하위 타입을 추가하기 쉽지만, hot path에서 객체 단위 디스패치와 분산된 데이터 배치 비용을 감수하기 쉬운 것이다.

이 방식들도 당연히 비용이 있으며, 그 대표적 예시는 switch가 커지면 분기 비용과 코드 복잡성이 생기고, 종류별 배열은 데이터 이동과 관리 비용을 만든다. 그러나 hot loop에서는 같은 종류의 데이터를 모아 처리할 수 있으므로 cache locality와 SIMD 기회가 좋아진다.

단, type id + switch가 항상 virtual dispatch보다 빠르게 굴러가지는 않는다. 타입이 섞인 배열을 매번 switch로 분기하면 결국 큰 분기 테이블을 도는 셈이다. DOP에서 중요한 건 virtual을 switch로 바꿨다는 사실이 아니라, 가능하면 같은 tag/type의 데이터를 모아 처리해서 branch와 cache miss를 줄였느냐다.

FP의 ADT + pattern matching과 DOP의 tagged data는 겹치는 부분이 있지만 관심사가 다르다.

FP ADT:
  값의 가능한 형태를 타입으로 닫아두고,
  pattern matching으로 경우를 나눈다.

DOP:
  데이터를 메모리 배치와 처리 패스 중심으로 재구성하고,
  hot loop에서 cache/SIMD/batch 처리 비용을 줄인다.

이 차이를 놓고 보면 FP 섹션은 표현 모델에 가깝고, DOP 섹션은 메모리/실행 모델에 가깝다. 같은 tag를 보더라도 한쪽은 타입과 케이스 분석을 먼저 보고, 다른 한쪽은 배열 배치와 처리 패스를 먼저 본다.

짧게 묶으면 다음 정도로 요약할 수 있다.

OOP는 다형성을 객체의 행동 선택으로 보고,
FP는 타입 파라미터/타입 클래스/합 타입으로 보고,
DOP는 데이터 배치, 접근 패턴, batch 처리 비용까지 같이 본다.

8. overloading/coercion: 이름은 같지만 컴파일러가 골라준다

Cardelli-Wegner가 ad hoc polymorphism 밑에 둔 두 축은 overloading과 coercion이다.

Overloading

void Print(int x) { ... }
void Print(string x) { ... }

컴파일러는 인자 타입을 보고 어떤 Print를 부를지 고른다. 같은 이름을 쓰지만 실제 함수는 다르고, 대개 이 결정은 컴파일 타임에 끝난다. 현장에서는 이것을 다형성이라고 부르기보다 "오버로딩"이라고 따로 부르는 경우가 많다.

Coercion

double x = 1; // int -> double

타입이 정확히 맞지 않아도 컴파일러가 변환을 끼워 넣는다. 이 경우 호출자는 1을 넘겼지만, 실제 계산은 double 쪽 규칙으로 넘어갈 수 있다.

현대 개발자는 보통 coercion을 "다형성"이라고 부르지 않는다. 하지만 Cardelli-Wegner 분류에서는 ad hoc polymorphism의 한 형태로 들어간다.

개인메모:이게 좀 재밌는 지점이, 내가 발견한 것인데. 현장 용어와 타입 이론 용어는 종종 어긋난다.
보통 프로그래밍 커뮤니티에서 polymorphism 하면 interface/override를 떠올리고, 타입 이론에서는 overload와 coercion까지 같이 포함한다.
둘 다 틀린 건 아닌데, 같은 단어를 들고 다른 걸 떠올리니까 대화가 자주 길을 잃는다. 그래서 프로그래밍 커뮤니티의 싸움 시작 방식도 다형적으로 여러 개다.

9. parametric polymorphism: 같은 구조를 여러 타입에 적용한다

parametric polymorphism은 T, a, α 같은 타입 파라미터를 받는다. 겉으로는 단순해 보이지만, 이 방식의 강점은 "타입을 모른다"는 제약에서 나온다.

function identity<T>(x: T): T {
  return x;
}

T가 무엇인지 몰라도 동작해야 한다는 점 때문에, constraint가 없는 parametric polymorphism은 오히려 강한 제약을 만든다.

아무 constraint도 없는 순수한 parametric polymorphism에서는,
T 값을 새로 만들 수도 없고,
T의 필드를 읽을 수도 없고,
T의 구체 메서드를 호출할 수도 없다.

할 수 있는 일은 보통:
  받은 값을 저장한다.
  그대로 돌려준다.
  컨테이너에 넣는다.
  다른 함수에 넘긴다.

generic constraint가 붙으면 다르게 봐야한다.
타입을 완전히 모르는 게 아니라, 특정 능력을 가진 타입이라고 말할 수 있기 때문이다.

// C#: 생성 가능하다는 능력을 명시
T Make<T>() where T : new() => new T();

// Rust: Default 능력을 명시
fn make<T: Default>() -> T {
    T::default()
}

// TypeScript: name 필드가 있다는 구조를 명시
function readName<T extends { name: string }>(x: T): string {
  return x.name;
}

"T에 대해 아무것도 모른다"는 말은 unconstrained일 때의 이야기다. 능력을 명시하면 그 능력 안에서는 생성, 필드 접근, 메서드 호출이 가능하다.

이 제약이 오히려 도움이 되는 지점이 존재하는데, 타입이 무엇이든 같은 방식으로 동작해야 하므로, 코드가 몰래 타입별 특수 행동을 하기 어렵다. 제약이 많아서 답답해 보이지만, 그 답답함이 추상화를 지켜준다. 한국에서 불경기에 공무원직을 선호하는 이유와 같이 제약이 많지만 철밥통이라는 뜻이다.

Girard-Reynolds의 polymorphic lambda calculus, 흔히 System F라고 불리는 계열은 이런 parametric polymorphism을 형식적으로 다루는 중요한 이론적 기반이다.¹²¹³ System F는 Girard가 1972년에 논리 쪽에서, Reynolds가 1974년에 프로그래밍 언어 쪽에서 독립적으로 발견한 것으로 자주 설명된다.¹³

"parametricity"라는 말로 대표되는 더 강한 관점까지 보려면 Reynolds의 1983년 Types, Abstraction and Parametric Polymorphism을 함께 볼 수 있다.¹⁴
여기서 중요한 직관은 타입 파라미터가 단순히 "여러 타입에서 쓸 수 있다"는 문법 장치가 아니라, 구현이 타입의 구체 구조를 볼 수 없게 만들어 추상화 정리를 강제한다는 점인데, 나중에 Wadler가 "Theorems for free!"로 대중화한 free theorem 감각도 이 계열에서 나온다.

10. parametric polymorphism 구현: erasure, monomorphization, reification

같은 List<T>를 구현해도 언어마다 선택이 다르다. 겉으로는 전부 "제네릭"처럼 보이지만, 컴파일러와 런타임이 실제로 하는 일은 꽤 다르다. 여기서 Java, Rust/C++, .NET이 갈라진다.

10.1 Type erasure: Java

Java generics는 type erasure로 구현된다. Oracle 문서에 따르면 컴파일러는 타입 파라미터를 bound나 Object로 대체하고, 필요한 cast와 bridge method를 넣는다.¹⁵¹⁶

대략 이런 느낌.

List<String> names;

컴파일 후 실행 시점의 객체 표현은 대체로 타입 인자가 없는 List 객체처럼 취급된다.
erasure라고 해도 generic 정보의 흔적이 class file에서 전부 사라지지는 않는다. generic signature metadata는 남을 수 있고, reflection으로 선언 정보를 일부 볼 수 있다.
하지만 JVM 실행 시점의 객체 표현은 List<String>과 List<Integer>를 별개의 reified runtime type으로 다루지 않는다. "다 지워진다"도 과하고, "런타임에 완전히 살아 있다"도 과하다.

장점:

• 기존 JVM/바이트코드와 호환성이 좋다.

• 타입별 클래스가 새로 생기지 않는다.

• 타입 인자별 별도 런타임 표현이나 코드 생성을 피할 수 있다.
  

단점:

• T.class 같은 것이 자연스럽지 않다.

• primitive specialization 문제가 생긴다.

• 런타임에 List<String>과 List<Integer>를 완전히 구분하기 어렵다.

• bridge method, wildcard, capture 같은 복잡성이 생긴다.
  

Java generics는 타입 체크를 컴파일 타임에 최대한 하고, 런타임 표현은 과거와 호환되게 유지하는 쪽을 택했다. 오래된 JVM 생태계와의 호환성을 생각하면 이해되는 선택이지만, 그 대신 primitive specialization이나 런타임 타입 구분에서 대가를 치뤄야만 한다.

10.2 Monomorphization: C++ templates, Rust generics

반대로 monomorphization은 타입별로 코드를 찍어내는 방식이다. 타입 정보를 지우는 대신, 구체 타입마다 기계가 좋아하는 모양으로 코드를 만든다.

Rust compiler dev guide는 Rust가 generic type을 monomorphize한다고 설명한다. 필요한 concrete type마다 generic function/code의 별도 copy를 만든다는 뜻이다.¹⁷

fn id<T>(x: T) -> T { x }

id::<i32>(1);
id::<String>("a".to_string());

컴파일러는 내부적으로 i32용, String용 코드를 따로 만들 수 있다. 그러면 런타임에는 타입을 다시 물어볼 필요가 줄고, optimizer도 더 공격적으로 움직일 수 있다.

장점:

• 런타임 타입 체크나 간접 호출 없이 최적화하기 좋다.

• 인라이닝과 specialization이 잘 된다.

• zero-cost abstraction에 가깝게 만들 수 있다.

단점:

• 컴파일 시간이 늘 수 있다.

• 바이너리 크기가 커질 수 있다.

• generic code가 많으면 컴파일러가 고생한다. 그리고 그 고생은 대개 노트북 팬 소리로 표현된다.

이 바이너리 크기 증가는 code bloat라고 부른다. 타입별로 코드를 찍어내면 런타임은 빨라질 수 있지만, 같은 구조의 기계어가 여러 번 생길 수 있다. 특히 템플릿이나 제네릭이 깊게 중첩되고 여러 crate/library 경계를 넘으면 컴파일 시간과 binary size가 눈에 띄게 커진다.

현대 컴파일러도 가만히 당하지는 않는다. LLVM 기반 toolchain은 Link-Time Optimization(LTO), identical code folding, dead code elimination 같은 최적화로 중복 인스턴스를 줄일 수 있다. monomorphization의 대가는 실제로 존재하지만, 최종 바이너리에서 항상 소스 수준 인스턴스 수만큼 정직하게 폭증한다고 보면 잘못된 지점이 있다.

C++ templates도 같은 큰 계열이다. C++ template은 타입 파라미터뿐 아니라 값 파라미터와 template template parameter까지 받을 수 있지만, 여기서 중요한 대목은 컴파일 타임에 구체 인자별 instantiation을 만든다는 점이다.¹⁸

10.3 Reified generics: .NET CLR

.NET/C# generics는 Java식 erasure와 다르다. Microsoft 문서는 C# generics가 runtime type information을 유지하고 type erasure가 없다고 설명한다.¹⁹

CLR generic type/method는 metadata에 타입 파라미터 정보를 가진다. 런타임도 generics를 직접 알고 있다.²⁰

.NET이 모든 타입 인자 조합에 대해 C++/Rust처럼 무조건 별도 네이티브 코드를 찍어내지는 않는다. 값 타입 인자에 대해서는 타입별 native code specialization이 일어나고, 참조 타입 인자에 대해서는 object reference 기반 코드를 공유할 수 있다. 이런 이유로 .NET generics는 "reified metadata + runtime/JIT support + 일부 code sharing"으로 보는 편이 정확할 것이다.

장점:

• 런타임에 generic 타입 정보를 다루기 쉽다.

• List<int> 같은 value type generic이 boxing 없이 효율적으로 다뤄질 수 있다.

• reflection, metadata, JIT specialization과 잘 맞는다.

단점:

• 런타임과 VM 설계가 복잡해진다.

• 플랫폼이 generics를 직접 지원해야 한다.

이 차이 때문에 Java와 C# 둘 다 "제네릭"이라고 말해도 구현 감각은 다른 지점이 있다. 그래서 Java를 할 줄 알면 C#도 할 줄 안다. 라는 소리에 코웃음 치는 것이다. 소스 코드 표면이 비슷하다고 런타임 선택까지 같지는 않듯이.

11. type class 구현: dictionary passing

Haskell type class는 보통 dictionary passing으로 설명된다. 처음 들으면 뭔가 거창해 보이지만, 감각은 비교적 단순하긴하다.
제약 조건을 만족한다는 증거를 함수에 같이 넘긴다고 보면 간단하다.

class Eq a where
  (==) :: a -> a -> Bool

컴파일러는 Eq a를 "a 타입에 대한 == 구현이 담긴 dictionary"처럼 볼 수 있다.

member :: Eq a => a -> [a] -> Bool

이 함수는 내부적으로 대략 이런 모양으로 번역된다고 생각할 수 있다.

member :: EqDictionary a -> a -> [a] -> Bool

type class constraint는 숨겨진 인자로 넘어가는 구현 증거가 된다. Oleg Kiselyov의 설명처럼 type class constraint의 double arrow =>를 일반 함수 화살표 ->로 번역하면, constraint satisfaction의 evidence가 dictionary argument로 지나간다고 볼 수 있다.²¹

물론 이것은 의미를 설명하기 위한 번역 모델이다. 실제 컴파일러는 specialization과 inlining으로 dictionary 전달 비용을 제거하거나 줄일 수 있다. 따라서 dictionary passing을 "항상 런타임에 dictionary 포인터를 따라가는 비용"으로만 이해하면 좁다. 설명 모델과 최종 기계어를 섞으면 또 이상해진다.

이 방식은 OOP interface dispatch와 비슷해 보이지만, 중심이 다르다.

OOP:

객체 안에 데이터와 메서드 구현이 붙어 있다.
obj.method()

Type class:

데이터와 구현 dictionary가 분리될 수 있다.
method(dict, value)

Haskell type class를 “OOP의 interface와 똑같다”고 말할 수도 있다. 물론 완전히 동일한 것은 아니지만 말이다.

유사점은 분명한데, 둘 다 어떤 타입이 특정 연산 집합을 제공한다는 계약을 표현한다.

하지만 OOP interface가 대체로 receiver 중심의 메시지 디스패치 모델이라면, Haskell type class는 타입에 대한 instance, 즉 evidence/dictionary를 컴파일러가 선택하고 전달하는 모델에 가깝다.

공통점:

• 어떤 타입이 어떤 연산을 지원한다는 계약을 표현한다.

• 같은 함수 이름을 여러 타입에서 쓸 수 있다.

차이:

• OOP는 보통 receiver object 중심이다.

• type class는 타입에 대한 외부 evidence/dictionary 중심이다.

• type class 계열은 데이터 정의와 연산 구현을 분리할 수 있기 때문에, 일부 경우에는 OOP receiver 중심 모델보다 나중에 연산 계약을 붙이는 확장이 자연스럽다.
  

물론 이것도 무제한으로 열려 있지는 않다. Haskell의 orphan instance는 충돌 위험 때문에 조심해야 하고, Rust는 coherence/orphan rule로 trait impl 위치를 제한한다. "나중에 붙일 수 있다"는 말은 "아무 데서나 마음대로 붙여도 된다"와 다르다. 타입 시스템도 결국 동네 질서가 있어야 한다.

12. Rust trait: type class와 interface 사이

Rust trait은 흥미로운 중간 지점에 있다. type class처럼 제약으로도 쓰이고, interface처럼 trait object로도 쓰이는데,

trait Draw {
    fn draw(&self);
}

Rust는 두 방식을 모두 제공할 수 있다.

Static dispatch

fn render<T: Draw>(x: T) {
    x.draw();
}

이건 보통 monomorphization으로 구체 타입별 코드가 만들어진다. 컴파일러가 타입을 알고 있으니 인라이닝과 최적화가 쉬워진다.

Dynamic dispatch

fn render(x: &dyn Draw) {
    x.draw();
}

이건 trait object를 통해 런타임 dynamic dispatch를 사용한다. Rust Book은 trait object 사용 시 컴파일러가 모든 concrete type을 알 수 없으므로 runtime에 pointer를 이용해 호출할 method를 찾고, 이 lookup에는 runtime cost가 있다고 설명한다.²²

또 하나 주의할 점이 있다. 모든 trait이 dyn Trait이 되지는 않는다. 예전에는 주로 object safety라고 불렀고, 현재 Rust 문서에서는 dyn compatibility라는 이름을 쓴다. 이름은 바뀌었지만 조건은 같다. trait object로 만들 수 있으려면 런타임 vtable로 호출 가능한 형태여야 한다.

Rust는 개발자에게 이 선택을 노골적으로 선택하게 한다.

성능/인라이닝/정적 검증이 중요하다:
  generic T: Trait

이질적 타입을 한 컬렉션에 담거나 런타임 교체가 필요하다:
  dyn Trait

현실적으로 말하자면 나는 이걸 과하다고 생각한다.
다형성이 하나가 아니라는 사실을 문법이 강제로 보여주는데, 이게 러스트가 런닝커브가 높다고 하는 것이다. impl Trait과 dyn Trait을 구분하지 않고 "trait 쓰면 다형성"이라고 뭉개면 Rust라는 언어를 모른다고 할 수 있다.

개인메모:Rust를 하기 위해서 제반 지식이 이렇게 많이 필요하고, 이게 어떤 선택인지 대부분 모르기때문에 Rust는 7할의 개발자가 실수하게 설계되있다. 왜냐하면 이 다형성에 대한 제대로 된 이해를 우리는 실질적으로 탐구하지 않으면 모르고 설명도 하지 않는다.

그럼 결국 어떻게 되냐? 그냥 소수 엘리트들이 만든 코드를 따라치고 그게 옵션이 아니라, 고정된 설정이 될 뿐이다.
대부분 프로그래밍이 그런식이더라도 러스트는 특히 심하다. 개인적으로 우상숭배형 언어라고 표현하는 편이다.

거기에 더해서impl Trait도 위치에 따라 느낌이 다르다. 인자 위치의 fn f(x: impl Draw)는 익명 generic bound처럼 읽히고, 반환 위치의 fn f() -> impl Draw는 구체 타입을 숨기는 opaque return type으로 동작한다. 둘 다 dyn Trait처럼 런타임 vtable을 타는 선택과는 결이 다르다.

13. structural typing과 row polymorphism

TypeScript의 T extends { name: string } 같은 코드는 Haskell type class나 Rust trait bound와는 다른 방향으로 움직인다. TypeScript 쪽에서는 "이 타입의 이름이 무엇인가"보다 "필요한 구조를 갖고 있는가"가 핵심이다. 사실 실제로 타입 단 하나보다 구조 단위로 보는게 프로그램 설계에 편하기때문에 지극히 실용적이다.
공식 문서도 TypeScript의 type compatibility가 structural subtyping에 기반한다고 설명한다.²³

function readName<T extends { name: string }>(x: T): string {
  return x.name;
}

이 코드는 Nameable이라는 명목 타입을 구현했는지 묻지 않는다. name: string이라는 모양이 있으면 받는다. 그래서 duck typing의 정적 버전처럼 보이는 구석이 있다. 다만 TypeScript는 JavaScript 생태계와 맞물려 돌아가야 해서 완전한 soundness보다 실용적 호환성을 많이 택한다. Haskell식 parametricity나 Rust식 trait bound와 같은 강도의 계약으로 보면 또 실수하게 된다.

row polymorphism은 여기서 한 발 더 이론 쪽으로 간다. record나 variant가 어떤 필드를 갖고 있고, 아직 열려 있는 나머지 row가 무엇인지 타입으로 다루는 방식이다. Wand의 1987년 record/object type inference 계열이 자주 언급되고, 이후 extensible records와 variants 쪽으로 이어진다.²⁴

TypeScript의 structural typing을 곧바로 row polymorphism이라고 부르기는 어렵지만, "이름보다 구조"라는 직관을 이해할 때 같이 놓고 보면 도움이 되는 지점이 많다.

14. multiple dispatch와 multimethods

OOP 초보자가 배우는 다형성은 보통 single dispatch다.

receiver 하나의 runtime type으로 method 선택

하지만 어떤 언어는 여러 인자의 runtime type을 보고 구현을 고른다.

collide(Ship, Asteroid)
collide(Laser, Shield)
collide(Player, Item)

이건 multiple dispatch 또는 multimethod 계열이다. Common Lisp Object System(CLOS), Dylan, Julia 등이 대표적으로 언급된다.

multiple dispatch는 "연산이 특정 객체 하나의 소유인가?"라는 OOP식 질문을 망가뜨린다.
특히 두 값의 조합 자체가 의미를 만드는 경우에는 receiver 하나를 고르는 일이 어색해지는 부분이 많다.

a.collide(b)라고 쓰면 구현이 a 쪽에 붙는다. 그런데 충돌은 a와 b 둘의 조합이다. 이 경우 multiple dispatch가 더 자연스럽다고 할 수 있다.

대신 method resolution은 복잡해진다. 우선순위, 모호성, 성능, 캐싱 문제가 생긴다.

multiple dispatch는 의미론적으로 여러 인자의 런타임 타입을 기준으로 method를 고른다. Julia 같은 구현은 여기에 JIT specialization과 method cache를 강하게 사용한다. 그러니 단순히 "매 호출마다 느린 런타임 lookup"으로 이해하면 맞긴한데, 잘못된 지점이 있다.

개인메모: 프로그래밍 언어에는 공짜 점심이 없고, 있는 것처럼 보이면 대개 컴파일러가 뒤에서 도시락을 싸고 있다.

15. 구현 방식별 요약

DOP-style handling은 고전적 다형성 분류라기보다, subtype polymorphism을 hot path에서 피하거나 재배치하는 실행 전략에 가깝다. type id, tagged data, dense array, ECS query, command buffer 같은 방식으로 변형을 표현한다.
표 안에 억지로 끼워 넣을 수는 있지만, 그러면 이론 분류와 실행 전략이 섞인다.

따로 적어두는 편이 덜 헷갈리더라.

16. 다형성을 설명할 때 조심할 점

나는 초보자에게는 주로 이렇게 설명하는 편이다.

다형성은 같은 요청을 보냈을 때,
실제 대상에 따라 다른 동작이 실행되는 능력이다.

이 설명은 입문용으로 쓸모가 있지만 OOP식 subtype polymorphism 쪽으로 무게가 쏠리는 지점이 있다. 근데 어차피 대부분 OOP선에서 끝난다.

하지만, 조금 더 개념을 나아가서 말하면 이렇게 된다.
(그리고 대부분 이 수준에서 정리된다)

다형성은 하나의 코드, 이름, 인터페이스, 연산이
여러 타입에 대해 의미 있게 적용될 수 있게 하는 언어 메커니즘이다.

그리고 프로그래밍 커뮤니티에서 논쟁이 붙을땐, 내가 잘 알고 있다는 것을 보여주기 위해서 반드시 다음 질문을 붙여야 한다.

이 다형성은:
  컴파일 타임에 결정되는가?
  런타임에 결정되는가?
  타입별 코드가 생성되는가?
  하나의 코드를 공유하는가?
  인터페이스 디스패치인가?
  타입 클래스/dictionary인가?
  단순 overload인가?

이 질문을 붙이지 않으면 다형성 논의는 금방 취향 싸움이 되고,
누군가는 interface를 말하고, 누군가는 generic을 말하고, 누군가는 Rust trait을 말하고, 누군가는 Haskell type class를 말한다.
결론은 대부분 서로가 맞다고 끝난다. 전부 다형성 근처의 이야기지만 비용과 계약 위치만 다를뿐이니까, 제대로 논쟁에서는 이기기 위해서는 정확해야한다.

결론

Strachey는 다형성을 ad hoc과 parametric으로 정리했고, Cardelli-Wegner는 parametric, inclusion, overloading, coercion을 큰 분류표 안에 배치했다. 그 뒤 Wadler-Blott는 ad hoc polymorphism을 type class라는 장치로 덜 임의적으로 만들었다.

여기까지가 개념의 지도라면, 그 뒤 언어 구현의 역사는 거의 같은 질문을 다른 방식으로 반복한 것에 가까울 것이다.

다형성을 어디까지 타입 시스템이 책임질 것인가?
어디부터 런타임 디스패치로 넘길 것인가?
코드를 복제할 것인가, 타입을 지울 것인가, metadata를 남길 것인가?
추상화 비용을 런타임에 낼 것인가, 컴파일 타임에 낼 것인가?

이 흐름을 따라가면 다형성을 하나의 기능으로 보기 어렵다. 언어가 "같은 코드로 여러 타입을 다루고 싶다"는 욕망을 처리하는 여러 방식의 묶음에 가깝다.

상속과 override는 그중 하나다. 중요한 축이지만 전체를 대신하지는 못한다. FP에서는 타입 파라미터와 type class가 더 선명하게 보이고, DOP에서는 다형성의 비용이 메모리 배치와 처리 패스의 문제로 다시 나타난다.

다형성을 설명할 때는 먼저 물어야하는 것들이 있다.
언제 결정되는가.
어떤 계약이 있는가.
타입 정보는 남는가.
비용은 어디로 가는가.
이 네 가지를 빼면, 남는 건 대개 "interface는 느리다" 같은 반쯤 맞는 격언뿐이다. 격언은 외우기 쉽고, 그래서 교조화 되기 쉽다.

같이 보기:

• 함수형 프로그래밍

• 컴포지션

• 프로그래밍 이디엄

• 대수적 데이터 타입

• 데이터 지향 프로그래밍