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를 만족하는 요소를 지닌 콜렉션를 생성할 수 있음

  • removefilter에 의해 구현되는데, 단순히 술부를 반전한 것임

  • 리스트를 필터링할 경우, 리스트를 반환케 될 것을 기대할 수 있음

  • 따라서, List는 자신의 결과 타입을 공변하게 재정의하기 위해 filter를 오버라이딩해야 함 (세부 구현은 생략)

  • 일관성을 위해 remove는 같은 결과 타입을 지녀야 하는데, 마찬가지로 오버라이딩 하는 거외에는 방법이 없음.

  • 메소드 모두가 List에서 반복되므로 코드 중복은 명확함

타입 생성자를 통한 해법

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

    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는 자신의 요소 타입을 나타내고, 두 번째 Containerfilterremove 메소드의 결과 타입을 결정하는 타입 생성자임

  • 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)를 어떻게 해방시키는지 살펴볼 것임

용어

국문 영문
일차 매개변수적 다형성 First-order parametric Polymorphism
타입 생성자 Type Constructor
타입 생성자 다형성 Type Constructor Polymorphism
타입 매개변수화 클래스 Type Parametised Class
제네럴티 Generality
카인드 Kind
추상 타입 멤버 Abstract Type Member
카인드 안정성 Kind soundness