Generics of a Higher Kind

1. Introduction

일차 매개변수적 다형성과 고차 타입 생성자 다형성

• 일차 매개변수적 다형성은 정적 타입 프로그래밍 언어의 표준 요소임
• 일차 매개변수적 다형성은 제네릭(generic)이라고 부름
• 제네릭의 한 가지 응용 분야는 콜렉션(collection)
  • 예) List[A] 타입은 주어진 요소 A 타입의 리스트를 표현, A는 자유롭게 선택됨
• 일차 매개변수적 다형성은 List와 같은 타입 생성자를 도출하며 타입을 추상화 함
• 그러나 결과로 나온 타입 생성자는 그들 자신을 추상화할 수 없음
  • 예) List와 같은 타입 생성자를 다른 타입 생성자의 타입 인자로 전달할 수 없음
• 이런 제한은 자연스러운 추상를 정형화하는데 방해가 되며 불필요한 중복 코드로 이어짐

고차 타입 생성자 다형성와 카인드

• 고차 타입 생성자 다형성을 통해 더 많은 제네럴티를 확보할 수 있음
• 이 논문에서는 Scala 프로그래밍 언어의 타입 생성자 다형성의 설계와 구현에 대해 살펴봄
• Scala 2.5 버전부터 고차 타입 제네릭을 이용할 수 있음
• 고차 타입 제네릭에서는 타입과 타입 생성자를 특정 지우기 위해 개발한 카인드 시스템을 사용함
• 카인드는 ‘어떤 타입 혹은 타입 생성자가 추상화에서 허용될 수 있는 인스턴스’ 인지를 표현함
• 즉, 카인드의 타입에 대한 역할은 타입이 변수에 대해 하는 역할임
• 카인드는 타입이나 타입 생성자의 3가지를 캡쳐함: 쉐이프, 하위/상위 바운드, 변성

추상 타입 멤버를 지닌 타입 vs 타입 생성자

• 가상 타입이나 가상 클래스를 지닌 언어는 추상 타입 멤버를 통해 타입 생성자 다형성을 코드화할 수 있음, Scala가 이런 부류의 언어에 속함
• 예) Scala에서는 타입 매개변수화된 클래스 대신 추상 타입 멤버를 지닌 클래스로 List를 정의할 수 있음

abstract class List { type Elem }

• List의 구체적인 구현은 List { type Elem - String } 처럼 타입 재정의를 통해 모델링할 수 있음
• 결정적인 것은 이렇게 코드화된 List가 타입 생성자가 아닌 타입이라는 점. 따라서, List를 일차 다형성의 타입 인자나 추상 타입 인스턴스로 전달할 수 있음
• 타입 생성자 다형성과 비교하면, 이런 코드화는 3가지 단점이 있음
  • 첫째, 다소 장황하게 느껴짐
  • 둘째, 요소 타입을 나타내는 명명된 멤버의 정의가 필요한데, 이는 클래스 상속 계층에서 이름 충돌의 위험을 유발할 수 있음
  • 셋째, 이런 코드화는 이후 구체적인 변수로 인스턴스화될 수 없는 어떤 무의미한 타입의 추상화를 정의하도록 허용함
• 반대로 타입 생성자 다형성은 카인드 안정성를 지님, 잘 카인드된 타입의 적용하면 무의미한 타입을 만들지 않음
• 이는 객체지향 프로그래밍의 타입 생성자 다형성 포함을 찬성하는 논증의 3가지 이유임

2. Reducing Code Duplication with Type Constructor Polymorphism

코드 중복

• 다음은 Scala의 Iterable[T] 트레이트의 구현체로 혼합 구성(mixin composition)을 지원하는 추상 클래스임

trait Iterable[T] {
	def filter(p: T => Boolean): Iterable[T]
	def remove(p: T => Boolean): Iterable[T] = filter (x => !p(x))
}

trait List[T] extends Iterable[T] {
	def filter(p: T => Boolean): List[T]
	override def remove(p: T => Boolean): List[T] = filter (x => !p(x))
}

• Iterable은 추상 메소드 filter와 편의 메소드 remove를 포함
• 하위 클래스는 filter를 구현해야 현재 콜렉션의 술부 p를 만족하는 요소를 지닌 콜렉션를 생성할 수 있음
• remove는 filter에 의해 구현되는데, 단순히 술부를 반전한 것임
• 리스트를 필터링할 경우, 리스트를 반환케 될 것을 기대할 수 있음
• 따라서, List는 자신의 결과 타입을 공변하게 재정의하기 위해 filter를 오버라이딩해야 함 (세부 구현은 생략)
• 일관성을 위해 remove는 같은 결과 타입을 지녀야 하는데, 마찬가지로 오버라이딩 하는 거외에는 방법이 없음.
• 메소드 모두가 List에서 반복되므로 코드 중복은 명확함

타입 생성자를 통한 해법

• 해법은 filter와 remove의 결과 컨테이너를 나타내는 타입 생성자로 추상화하는 것임

trait iterable[T, Container[X]] {
	def filter(p: T => Boolean): Container[T]
	def remove(p: T => Boolean): Container[T] = filter (x => !p(x))
}

trait List[T] extends Iterable[T, List]

• 개선된 Iterable은 두 개의 타입 매개변수를 취함: [T, Container[X]]
• 첫 번째 T는 자신의 요소 타입을 나타내고, 두 번째 Container는 filter와 remove 메소드의 결과 타입을 결정하는 타입 생성자임
• Container는 타입 매개변수 하나를 취함

2.1 Type constructors and kinds

• 타입 생성자와 적당한 타입을 구별하기 위해 카인드(kind, 함수형 프로그래밍에서 차용한 용어)를 사용함

• 카인드는 변수에 대한 타입처럼 타입에 대한 것임, 이는 3가지 레벨로 언어를 구성함

• 객체는 타입으로 분류되고, 타입은 카인드로 분류됨

• 타입과 달리, 카인드는 순수하게 구조적임: 타입에 기대되는 타입의 매개변수의 종류를 반영함

• 적합한 타입들은 모두 타입 매개변수의 수가 같으므로 동일한 카인드 *로 분류됨

• 타입 생성자를 분류하기 위해, 카인드 생성자 From → To를 사용함

• From은 기대되는 타입 인자의 카인드이며 To는 인자에 타입 생성자를 적용할 때의 결과 타입의 카인드임

• 예) class List[T]는 적합한 타입을 도출하는 적합한 타입에 대해 적용하며 * → *로 분류되는 List 타입 생성자로 이루어 짐

• 카인드 레벨의 초기 모델은 다음과 같은 문법으로 기술됨

K ::= * | K  → K

• 타입 생성자 다형성없이 언어 타입의 정형성(well-formedness)을 정의하는 규칙은 타입에 할당하는 카인드 규칙과 일치함
• 이 규칙을 타입이 변수와 표현식에 타입 체킹을 하는 것처럼 카인드 체킹으로 일반화하여 확장시킴
• 클래스나 언바운드 타입 매개변수 혹은 추상 타입 멤버는 하나의 K’ 카인드의 타입 매개변수가 있을 경우 , K’ → * 인 카인드를 받음
• 바운드 타입 매개변수나 추상 멤버는 K’ → K인 카인드를 할당받음, 이 때 K는 바운드 타입과 일치함

타입 커링

• 다중 타입 매개변수를 다루기 위해 이 스킴을 일반화하는데 커링을 사용함
• T[T’] 타입을 적용하면 T가 K’ → K인 카인드를 가지며 T'가 K’ 카인드로 분류될 때, K인 카인드를 지님
• 타입 생성자 다형성으로 인한 Scala 확장의 문법적인 영향은 마이너함
• 클래스와 타입 알리어스만 형식적인 타입 매개변수를 선언할 수 있었으나 타입 매개변수와 추상 멤버 타입을 포함하기 위해 확장됨
• 다음은 추상 타입 생성자 멤버를 사용한 선택적인 형태임

trait Iterable[T] {
	type Container[X]
	
	def filter(p: T => Boolean): Container[T]
}

2.2 Improving Iterable

• 타입 생성자 다형성은 설계 제약사항을 표현하는 데 필수적인 역할을 함

• Iterable의 map, filter, flatMap의 시그너쳐과 구현에 대해 논의함

  • map은 요소를 그 함수에 의해 지정된 요소로 변환함
  • filter는 술부인 함수를 해석해서 이를 만족하는 요소만 유지함
  • flatMap은 주어진 함수를 적용, 원본 콜렉션의 모든 요소에 대해 요소의 콜렉션을 만들고, 이런 콜렉션 내의 요소들을 수집해서 한 콜렉션으로 만듦 (참고)

• 다음은 콜렉션의 반복을 캡슐화한 잘 알려진 Iterator 추상과 쌍으로 고려되는 Builder 추상임

trait Builder[Container[X], T] {
	def +=(el: T): Unit
	def finalise(): Container[T]
}

trait Iterator[T] {
	def next() : T
	def hasNext: Boolean
	
	def foreach(op: T => Unit): Unit = while(hasNext) op(next())
}

• Builder는 빌드하는 콜렉션을 나타내는 타입 생성자를 추상화함

• += 메소드는 콜렉션에 나타나야 하는 순서로 요소를 공급하는데 사용됨

• 콜렉션 자체는 finalize에 반환됨

• 예) Builder[List, Int]는 ListBuffer[Int]로 생각할 수 있고, 이들 모두 List[Int]를 만드는데 사용될 수 있음

• 다음은 mapTo/fiilterTo/flatMapTo가 어떻게 좀 더 유연하게 구현될 수 있는지 나타냄

trait Buildable[Context[X]] {
	def build[T]: Builder[Container, T]
}

trait Iterable[T] {
	type Container[X] <: Iterable[X]
	
	def elements: Iterator[T]
	
	def mapTo[U, C[X]](f: T => U)(b: Buildable[C]): C[U] = {
		val buff = b.build[T]
		val elems = elements
		
		while(elems.hasNext) {
			val el = elems.next
			if(p(el)) buff += el
		}
		
		buff.finalise()
	}
	
	def filterTo[C[X]](p: T => Boolean)(b: Buildable[C]): C[T] = {
		val buff = b.build[T]
		val elems = elements
		
		while(elems.hasNext) {
			val el = elems.next
			if(p(el)) buff += el
		}
		
		buff.finalize()
	}
	
	def flatMapTo[U, C[X]] (f: T => Iterable[U])(b: Buildable[C]): C[U] = {
		val buff = b.build[U]
		val elems = elements
		
		while(elems.hasNext) {
			f(elems.next).elements.foreach{ el => buff += el }
		}
		
		buff.finalize()
	}
	
	def map[U](f: T => U)(b: Buildable[Container]): Container[U] = 
		mapTo[U, Container](f)(b)
		
	def filter(p: T => Boolean)(b: Buildable[Container]):Container[T] = 
		filterTo[Container](p)(b)
		
	def flatMap[U](f: T => Container[U])(b: Buildable[Container]): Container[U] = 
		flatMapTo[U, Container](f)(b)

• 만들어진 콜렉션과 원본 콜렉션을 디커플링하는 것으로 제네릭화 함 - 이들은 같을 필요가 없음
• 콜렉션을 반복하는 것과 콜렉션을 만드는 것은 서로 직교함 (의역: 연관성이 없음)
• 즉, 콜렉션의 요소를 반복하기 위해 콜렉션을 빌드할 수 있어야 할 필요는 없음
• mapTo와 같은 좀 더 복잡한 연산의 경우, Buildable[C]의 인스턴스가 필요함
• 따라서, 콜렉션 C를 빌드하는 Iterable의 메소드는 Buildable[C] 타입의 추가 매개변수를 취함
• 섹션 3에서 Scala의 직교적인(orthogonal) 특징이 이 매개변수의 실제 인자를 공급하는데 있어 콜러(caller)를 어떻게 해방시키는지 살펴볼 것임

용어