5.4 카인드

 

이 글은 인사이트 출판사의 제안으로 작성 중인 책 『프로그래밍 언어 속 타입』 원고의 일부입니다.

 

---

가든 비닐봉지, 가든 종이 상자

처르지: 고민이 있는 표정인걸?
큐리 박사: 잘도 알았네. 넌 항상 눈치가 빠르구나.
처르지: 우리가 하루 이틀 본 사이도 아닌데 이쯤이야 뭐. 그래서 뭔데?
큐리 박사: 최근에 과일 가게에서 포장 서비스를 시작했거든. 과일을 사면 비닐봉지나 종이 상자에 담아서 줘. 근데 매번 손님이 과일을 사갈 때마다 어디에 포장할지 물어 봐야 하는 게 꽤나 귀찮더라고. 한두 번이면 몰라도, 하루 종일 그러려니 좀 힘들달까?
처르지: 장사를 하려면 그 정도는 당연히 감내해야 하는 거 아니야? 뭐 대단한 거도 아니고.
큐리 박사: 그렇긴 하지만, 그래도 귀찮은걸.
처르지: 그러면 이렇게 하는 게 어때? 손님이 처음 과일을 주문할 때부터 어디에 포장할지 말하도록 안내문을 써 붙이는 거야. 그러면 네가 매번 물어 볼 필요는 없지 않겠어?
큐리 박사: 정말 좋은 생각이야. 당장 그렇게 해야겠어.

잠시 후

큐리 박사: 이 정도면 되겠지?

 

주문 방법: □ □ 주세요.
□에 들어갈 말: 사과, 복숭아, 바나나, 오렌지, 키위, 딸기, 가 든 비닐봉지, 가 든 종이 상자

 

처르지: 음, 그런가? 뭔가 부족해 보이는 거 같기도 하고.
큐리 박사: 그래? 아, 손님 왔다. 금방 돌아올게.
손님 1: 안녕하세요. 사과가 든 비닐봉지 주세요.
큐리 박사: 네. 바로 드리겠습니다.

 

 

손님 1: 감사합니다. 안녕히 계세요.
큐리 박사: 야호, 성공이야. 이제 매번 어디에 포장할지 물어 볼 일이 없겠어.
처르지: 그러게. 잘 된 거 같네.
큐리 박사: 앗, 또 손님이다.
손님 2: 흠, 사과 사과 주세요.
큐리 박사: 네? 뭐라고요?
손님 2: 사과 사과 주세요.
큐리 박사: 그게 뭔 소리죠?
손님 2: 저는 여기에 적힌 주문 방법대로 한 건데요? 얼른 과일 주세요.
큐리 박사: 이상한 소리 하지 말고 과일 안 살 거면 얼른 나가세요.
손님 2: 허, 참. 장사 그따위로 하지 마쇼.
큐리 박사: 이상한 사람이네.
처르지: 저 사람이 잘못한 건 없지 않았어?
큐리 박사: 뭐라고? 아, 또 손님이네. 좀 있다 다시 이야기하자.
손님 3: 음, 가 든 비닐봉지가 든 종이 상자 주세요.
큐리 박사: 가든 비닐봉지, 가든 종이 상자? Garden? 에잇, 도통 뭐라는지 알아들을 수가 없구만. 이상한 소리 그만하고 얼른 가세요.
손님 3: 내가 여길 다시 오나 봐라.
큐리 박사: 이상한 사람이 연달아 왔잖아! 오늘 운수가 사납네.
처르지: 음, 내가 보기엔 네 주문 방법 설명이 좀 잘못된 거 같아. 과일 이름이랑 포장 방법을 좀 구분할 방법이 필요하지 않을까?

 

---

이번 절의 주제인 카인드kind는 사실 매개변수에 의한 다형성을 설명한 3장에서 다뤘어야 하는 개념이다. 하지만 타입클래스가 있어야 카인드의 유용성이 잘 드러나기 때문에 어쩔 수 없이 이번 장으로 미루게 되었다. 우선 카인드가 어떤 개념인지 예시와 함께 알아보자. 그 뒤에 카인드를 타입클래스와 함께 사용하는 방법까지 보겠다.

 

4장에서 본 배열 리스트와 연결 리스트를 다시 사용할 것이다. 오버로딩을 통해 각 종류의 리스트마다 함수가 두 개씩 정의되어 있다.

Int length<T>(ArrayList<T> lst) { ... }
Int length<T>(LinkedList<T> lst) { ... }

void add<T>(ArrayList<T> lst, T elem) { ... }
void add<T>(LinkedList<T> lst, T elem) { ... }

length는 리스트의 길이를 구하는 함수고, add는 리스트의 맨 끝에 새로운 원소를 추가하는 함수다. 각 함수는 리스트를 구성하는 원소의 타입과 상관없이 잘 작동하므로 모두 제네릭 함수로 정의했다.

이제 length와 add를 사용해서 배열 리스트를 다루는 다음과 같은 함수를 정의할 수 있다.

void addUntil<T>(ArrayList<T> lst, T v, Int len) {
    while (length<T>(lst) < len) {
        add<T>(lst, v);
    }
}

addUntil은 리스트, 그 리스트에 추가할 값, 도달하고 싶은 리스트의 길이를 인자로 받는다. 그 뒤 리스트의 현재 길이를 확인해 가며 목표 길이에 도달할 때까지 반복해서 리스트에 값을 추가한다. 사실 이 함수가 사용하는 기능은 리스트의 길이를 재는 것과 리스트에 원소를 추가하는 것뿐이다. 이 둘은 배열 리스트가 아닌 다른 리스트도 모두 제공하는 기능이다. 가령 다음과 같이 연결 리스트를 가지고 같은 일을 하는 함수도 정의할 수 있다.

void addUntil<T>(LinkedList<T> lst, T v, Int len) {
    while (length<T>(lst) < len) {
        add<T>(lst, v);
    }
}

이렇게 함수 두 개를 각각 정의해도 잘 작동하기는 하지만 썩 만족스럽지 않다. 두 함수의 몸통이 완전히 똑같다. 게다가 배열 리스트와 연결 리스트 이외의 다른 방식의 리스트를 더 만든다면 몸통이 같은 addUntil을 또 만들어야 할 테다. 이는 우리가 원하는 일이 아니다.

그러니 지금까지 했던 것처럼 매개변수에 의한 다형성을 활용해야 한다. 함수를 한 번만 정의해도 모든 종류의 리스트를 처리할 수 있도록 코드를 고쳐 보자.

void addUntil<L, T>(L<T> lst, T v, Int len) {
    while (length<T>(lst) < len) {
        add<T>(lst, v);
    }
}

이제 addUntil은 두 개의 타입 인자를 받는 제네릭 함수다. 첫 타입 인자는 리스트의 종류를 나타내고, 둘째 타입 인자는 리스트를 구성하는 원소의 타입을 나타낸다. 즉, 정수를 담고 있는 배열 리스트에 원소를 추가하고 싶다면 addUntil<ArrayList, Int>(...)라고 쓰면 되고, 문자열을 담고 있는 연결 리스트에 원소를 추가하고 싶다면 addUntil<LinkedList, String>(...)이라고 쓰면 된다.

하지만 곰곰이 생각해 보면 위 코드가 조금 이상하다는 것을 깨닫게 된다. addUntil을 말도 안 되는 방식으로 사용할 수 있다. addUntil<Int, String>(...)이나 addUntil<LinkedList, ArrayList>(...) 같은 코드가 그 예시다. addUntil<Int, String>은 첫 번째 인자로 Int<String> 타입의 값을 받고, addUntil<LinkedList, ArrayList>는 첫 번째 인자로 LinkedList<ArrayList> 타입의 값을 받는다. 둘 다 전혀 말이 되지 않는다. Int는 제네릭 타입이 아니다. 그러니 Int<String> 타입이라는 것은 존재하지 않는다. 또, ArrayList는 제네릭 타입이다. 사용할 때 타입 인자를 받아야 한다. LinkedList<ArrayList<Int>>는 정수로 이루어진 배열 리스트들을 담고 있는 연결 리스트를 나타내는 올바른 타입이지만, LinkedList<ArrayList> 같은 타입은 없다.

무엇이 잘못된 것일까? 문제는 타입이라고 다 같은 타입이 아니라는 점이다. 타입에도 여러 종류가 있다. 한 종류는 지금까지 우리가 흔히 사용하던 타입들을 포함한다. Int나 String 같이 타입 인자를 받을 필요 없이 매개변수 타입이나 결과 타입으로 사용할 수 있는 타입들이다. 여기서 어떤 타입을 “매개변수 타입이나 결과 타입으로 사용할 수 있다”는 말은 그 타입에 속하는 값이 존재한다는 것이다. 어떤 타입 A가 함수의 매개변수 타입이라는 말은 그 함수가 인자로 A 타입의 값을 받는다는 뜻이다. 또, A가 함수의 결과 타입이라는 말은 그 함수가 A 타입의 값을 반환한다는 뜻이다. 만약 어떤 타입에 속하는 값이 없다면 그 타입을 매개변수 타입이나 결과 타입으로 사용하는 의미가 없다. 그러니 “매개변수 타입이나 결과 타입으로 사용될 수 있다”는 말을 “그 타입에 속하는 값이 존재한다”는 뜻으로 이해해도 무리가 없다. 이를 바탕으로 다시 말하면, 첫 종류는 그 타입의 값들이 존재하는 타입들이다.

또 다른 종류는 우리가 제네릭 타입이라고 부르는 타입들을 가리킨다. ArrayList나 LinkedList 같이 타입 인자를 필요로 하는 타입들이다. 이런 타입들을 매개변수 타입이나 결과 타입으로 사용하는 것은 이치에 맞지 않는다. ArrayList 타입의 값이나 LinkedList 타입의 값이란 것은 없기 때문이다. ArrayList<Int>나 LinkedList<String> 타입의 값은 있을지언정 ArrayList나 LinkedList 타입의 값은 없다. 즉, 두 번째 종류는 그 타입의 값들이 존재하지 않는 타입들을 포함한다. 또한, 이런 타입들이 타입 인자를 받으면 첫 번째 종류의 타입을 만들어 낸다. ArrayList가 Int를 받아 ArrayList<Int>라는 타입을 만들고, LinkedList가 String을 받아 LinkedList<String>이라는 타입을 만드는 게 그 예시다.

이런 타입의 분류를 설명하기 위해 도입된 개념이 카인드다. 카인드는 곧 타입의 타입인 셈이다. 첫 번째 종류의 타입은 *라는 카인드에 속한다. “Int의 카인드는 *이다”나 “String의 카인드는 *이다”와 같이 말할 수 있다. 두 번째 종류의 타입은 * => *라는 카인드에 속한다. 함수 타입을 떠올리면 * => *라는 카인드를 쉽게 이해할 수 있다. Int => String 타입은 Int 타입의 값을 인자로 받아 String 타입의 값을 반환하는 함수를 나타냈다. 마찬가지로, * => * 카인드는 * 카인드의 타입을 타입 인자로 받아 * 카인드의 타입을 만드는 타입을 나타낸다. ArrayList와 LinkedList가 여기에 속한다. 그러니 “ArrayList의 카인드는 * => *이다”나 “LinkedList의 카인드는 * => *이다”라고 말할 수 있다.

카인드는 이 두 개뿐일까? 그렇지 않다. Map과 같이 두 개의 타입 인자를 받는 타입은 (*, *) => * 카인드에 속한다. 또, 더 복잡한 카인드를 만들 수도 있다. 다음 코드를 보자.

class IntContainer<(* => *) L> {
   L<Int> integers;
}

IntContainer는 L이라는 이름의 타입 매개변수를 가지고 있는 제네릭 클래스다. 그런데 그 타입 매개변수에 * => *라는 카인드 표시가 붙어 있다. 이 카인드 표시는 IntContainer가 타입 인자로 받을 수 있는 타입이 * => * 카인드의 타입뿐이라는 뜻이다. 어떤 함수의 매개변수 x에 Int라는 타입 표시가 붙어 (Int x)라고 되어 있으면 그 함수가 Int 타입의 값만을 인자로 받을 수 있는 것과 마찬가지다. 즉, IntContainer<ArrayList>나 IntContainer<LinkedList>는 가능해도, IntContainer<String>이나 IntContainer<Map>은 불가능하다. 이는 아주 합리적이다. IntContainer 객체의 필드 integers의 타입이 ArrayList<Int>나 LinkedList<Int>인 것은 말이 되어도, String<Int>나 Map<Int>인 것은 말이 안 되니 말이다. 이렇게 만든 IntContainer라는 타입의 카인드는 무엇일까? IntContainer는 * => * 카인드의 타입을 타입 인자로 받아 * 카인드의 타입을 만든다. 그러니 IntContainer의 카인드는 (* => *) => *이다. 같은 방식을 반복하면 ((* => *) => *) => * 같이 더욱 복잡한 카인드도 끝없이 만들 수 있다. 그러니 카인드의 수는 무수히 많다. 하지만 일반적으로 코드를 작성할 때 *, * => *, (* => *) => * 수준을 넘어가는 카인드를 볼 일은 거의 없다.

 

 

이제 카인드 표시를 사용해 addUntil을 다시 작성해 보자.

void addUntil<(* => *) L, * T>(L<T> lst, T v, Int len) {
    while (length<T>(lst) < len) {
        add<T>(lst, v);
    }
}

이제 타입 매개변수 L 앞에는 * => *라는 카인드 표시가 붙고, T 앞에는 *라는 카인드 표시가 붙는다. 따라서 addUntil의 첫 타입 인자는 * => * 카인드에 속해야 하고, 둘째 타입 인자는 * 카인드에 속해야 한다. 그러니 addUntil<ArrayList, Int>(...)와 addUntil<LinkedList, String>(...)은 타입 검사를 통과하고, addUntil<Int, String>(...)과 addUntil<LinkedList, ArrayList>(...)는 타입 검사를 통과하지 못한다. 우리가 원하는 코드는 타입 검사를 통과하고, 말이 되지 않는 이상한 코드는 타입 검사기가 올바르게 거부하는 것이다.

근데 사실 제네릭 함수를 정의할 때 대부분의 타입 매개변수에는 *가 카인드 표시로 붙는다. * 이외의 * => * 같은 카인드에 속하는 타입을 타입 인자로 받는 addUntil 같은 함수는 상당히 드물다. 그래서 매번 *를 붙이는 번거로움을 해결하고자 대부분의 언어에서는 *를 생략할 수 있도록 한다. 카인드 표시를 안 붙이면 그냥 * 카인드라고 간주하는 것이다. 이에 따라 코드를 다음처럼 다시 적을 수 있다.

void addUntil<(* => *) L, T>(L<T> lst, T v, Int len) {
    while (length<T>(lst) < len) {
        add<T>(lst, v);
    }
}

이제 코드가 완벽해졌을까? 아쉽게도 그렇지 않다. * => * 카인드에 속하는 모든 타입이 length와 add 함수를 가지고 있지는 않다. 예를 들어 읽기만 가능한 ReadOnlyList 타입을 위한 add 함수는 정의할 수 없다. 그러니 타입 검사기의 입장에서는 L<T> 타입의 값인 lst를 length와 add의 인자로 사용할 수 있다는 보장이 없다. L 타입을 위한 length와 add 함수가 반드시 정의되어 있다는 사실을 타입 검사기에게 알려 줘야 한다. 그 방법은 물론 타입클래스다.

다음 코드는 ListLike이라는 타입클래스를 정의한다.

typeclass ListLike<(* => *) L> {
    Int length<T>(L<T> lst);
    void add<T>(L<T> lst, T elem);
}

이 코드가 의미하는 바는 “* => * 카인드의 타입 L이 ListLike 타입클래스에 속하려면 length와 add 함수가 정의되어야 한다”는 것이다. 타입클래스 인스턴스를 정의하는 과정은 전과 비슷하다. 다음과 같이 ArrayList와 LinkedList를 각각 ListLike에 속하도록 만들 수 있다.

instance ListLike<ArrayList> {
    Int length<T>(ArrayList<T> lst) { ... }
    void add<T>(ArrayList<T> lst, T elem) { ... }
}
instance ListLike<LinkedList> {
    Int length<T>(LinkedList<T> lst) { ... }
    void add<T>(LinkedList<T> lst, T elem) { ... }
}

마지막으로 addUntil을 고치면 끝이다.

void addUntil<(* => *) L, T>(L<T> lst, T v, Int len) requires ListLike<L> {
    while (length<T>(lst) < len) {
        add<T>(lst, v);
    }
}

이제 addUntil의 첫 타입 인자는 카인드가 * => *이면서 ListLike 타입클래스에 속해야 한다. 그런 타입으로는 ArrayList와 LinkedList가 있다. 따라서 addUntil<ArrayList, Int>(...)와 addUntil<LinkedList, String>(...)는 계속해서 타입 검사를 통과한다. 한편 ReadOnlyList의 경우 카인드는 * => *가 맞을지언정 ListLike 타입클래스에 속하지 않기에 addUntil<ReadOnlyList, String>(...)은 타입 검사를 통과하지 못한다.

 

---

스칼라

class ArrayList[T]
class LinkedList[T]

trait ListLike[L[_]] {
  def length[T](lst: L[T]): Int
  def add[T](lst: L[T], elem: T): Unit
}

given ListLike[ArrayList] with
  def length[T](lst: ArrayList[T]): Int = ...
  def add[T](lst: ArrayList[T], elem: T) = ...
given ListLike[LinkedList] with
  def length[T](lst: LinkedList[T]): Int = ...
  def add[T](lst: LinkedList[T], elem: T) = ...

def addUntil[L[_]: ListLike, T](lst: L[T], v: T, len: Int) =
  while summon.length[T](lst) < len do
    summon.add[T](lst, v)

T의 카인드가 * -> *라는 조건을 T[_]라 쓴다. 비슷하게, T의 카인드가 (*, *) -> *라는 조건은 T[_, _]라 쓰고, T의 카인드가 (* -> *) -> *라는 조건은 T[_[_]]라 쓴다.

하스켈

data ArrayList a = ...
data LinkedList a = ...

class ListLike (l :: * -> *) where
  len :: l a -> Int
  add :: l a -> a -> ()

instance ListLike ArrayList where
  len lst = ...
  add lst elem = ...
instance ListLike LinkedList where
  len lst = ...
  add lst elem = ...

addUntil :: ListLike l => l a -> a -> Int -> ()
addUntil lst v l =
  len lst
  ...
  add lst v

타입 추론에 더해 카인드 추론도 지원하기 때문에 class ListLike (l :: * -> *) 대신 class ListLike l이라고만 써도 된다.