14장: 타입 클래스

새 파일

src/classes.rs

src/evidence.rs

src/elaborate/dictionaries.rs

src/primitives.rs

변경된 파일

src/typecheck.rs

src/elaborate.rs

src/types.rs

src/ast.rs

src/core.rs

src/core_lint.rs

src/core_type.rs

src/data.rs

src/desugar.rs

src/eval.rs

src/fixity.rs

src/kinds.rs

src/lexer.rs

src/lib.rs

src/main.rs

src/parse.rs

src/rename.rs

src/renamed.rs

src/syn.rs

동기

두 리스트는 어떻게 비교할까요? 리스트의 원소들을 비교하므로, 그 원소들을 비교하는 방법을 알아야 합니다. 모든 리스트 비교에 동등성 함수를 넘겨줄 수도 있습니다. 그렇게 해도 동작하지만, 머지않아 똑같은 몇 가지 연산을 이리저리 넘겨주는 데 많은 시간을 쓰게 될 것입니다.

타입 클래스를 사용하면 그런 배관 작업을 컴파일러에게 맡길 수 있습니다. 우리는 클래스에 연산을 기술하고, 인스턴스에서 그 구현을 제공합니다. 컴파일러는 각 호출에 어떤 구현이 필요한지 알아내어 그 구현을 넘겨줍니다.

멋진 점은 정체를 알 수 없는 새로운 런타임 기능이 필요하지 않다는 것입니다. 클래스는 함수들의 레코드가 되며, 이 레코드를 흔히 딕셔너리라고 부릅니다. 그 인자들을 명시적으로 드러내고 나면, 기존의 Core 인터프리터로 결과를 실행할 수 있습니다. 이 장에서는 그 변환 과정을 처음부터 끝까지 따라가 보겠습니다.

현재의 언어

클래스를 하나 정의하고 정수에 대한 인스턴스를 만들어 봅시다.

class Value a where
  value :: a -> Int

instance Value Int where
  value x = x + 1

main = value 41

클래스 매개변수는 고차 카인드를 가질 수 있습니다. unwrap :: f a -> a라는 메서드가 있으면 클래스 매개변수 f의 카인드는 * -> *가 됩니다. 나머지 변수 a는 독립적으로 다형적입니다. 클래스는 슈퍼클래스와 기본 메서드 본문을 가질 수 있습니다. 인스턴스 메서드에는 일반적인 등식, 가드, 지역 where 바인딩을 쓸 수 있습니다.

이제 Prelude는 Eq, Ord, Show, Num, Fractional, Semigroup, Monoid를 정의합니다. 산술 연산과 비교 연산은 메서드로 해석됩니다. 리터럴은 여전히 단형적입니다. 1의 타입은 Int이고, 1.0의 타입은 Double입니다. 따라서 1 + 2.0은 실패합니다. toDouble 1 + 2.0은 성공합니다. 기본 타입 지정(defaulting)은 없습니다.

same :: Ord a => a -> a -> Bool
same x y = x == y

main = same [1,2] [1,2]

Ord가 Eq 슈퍼클래스를 제공하므로 시그니처만으로 충분한 증거가 주어집니다. 인스턴스가 없으면 E0210을 보고합니다. 형식이 잘못되었거나 겹치는 인스턴스, 그리고 누락된 메서드는 E0211을 보고합니다. 결과 타입에 나타나지 않는 변수를 가진 제약은 E0230을 보고합니다. 예를 들어 show Nothing은 원소의 Show 인스턴스를 고를 수 없습니다. 명시적인 Maybe Int 표기를 붙이면 그 모호성이 해소됩니다.

Double은 부동소수점 산술, 비교, 변환, 수학 함수를 추가합니다. 프리미티브 이름은 내장된 Prelude 안에서만 쓰이도록 비공개로 유지됩니다. 소스 언어에는 여전히 IO가 없으므로 run은 main의 값을 출력합니다. 이 장에서 ++는 여전히 문자열을 이어 붙입니다. 리스트에 대한 ++는 완전한 Prelude 장에서 다룹니다. <>는 이미 문자열과 리스트를 모두 지원합니다.

이론

타입 Eq a => a -> a -> Bool은 누군가 a에 대한 동등성을 제공하면 a 타입의 두 값을 비교할 수 있다는 뜻입니다. => 앞부분을 문맥(context)이라고 합니다. 이 타입을 가진 함수를 사용하면 추론 과정에서 그 동등성 연산에 대한 요청이 만들어집니다. 우리는 이것을 요구(wanted) 제약이라고 부릅니다.

어떤 요청은 Int에 대한 인스턴스처럼 바로 답을 얻습니다. 나머지는 타입 변수에 관한 요청으로 남습니다. 바인딩을 일반화할 때 이런 요청은 그 바인딩의 스킴에 포함될 수 있으며, 그러면 호출자가 답을 제공합니다. 반면 바깥 변수가 관련된 제약은 둘러싼 스코프에 속합니다. Jones는 이러한 연산을 실행 가능한 형태로 설명합니다 (Jones 1999).

인스턴스를 찾는 것은 일의 절반에 불과합니다. 런타임에 전달할 무언가도 필요합니다. 그것이 제약에 대한 증거(evidence)입니다. Ord a 사전에는 이미 Eq a 슈퍼클래스 사전이 들어 있습니다. Eq a가 주어지면 리스트 인스턴스는 Eq [a]에 대한 사전을 만들 수 있습니다. 이 단계들을 따라가면 사전 변수, 필드 선택, 인스턴스 적용으로 이루어진 평범한 식이 만들어집니다. 런타임에 수행할 탐색은 남지 않습니다.

시그니처는 경직된(rigid) 스콜렘으로 검사하며, 시그니처의 문맥은 주어진(given) 제약으로 취급합니다. 시그니처가 있는 바인딩은 자신의 본문 안에서 다형적으로 사용될 수 있습니다. Haskell Report(Simon Marlow 2010)를 따라, 타입 추론 의존성에서는 시그니처가 있는 바인딩으로 향하는 간선을 생략합니다. 재귀 함수에는 여전히 공유된 재귀 환경이 필요하므로 런타임 의존성에서는 그 간선을 유지합니다. 이 둘은 같은 소스 의존성 그래프를 서로 다르게 사용하는 것입니다.

일반화는 여전히 제한 없이 이루어집니다. comparison = (==) 같은 제약이 있는 값은 사전을 인자로 받는 함수로 정교화됩니다. 그 본문은 사전이 제공될 때 평가되므로 소스 수준의 공유가 사라집니다. Fun은 사전 전달에서 비롯된 이 결과를 받아들입니다. 순수성 덕분에 이것은 건전합니다.

구현

classes.rs는 슈퍼클래스 탐색, 인스턴스 매칭, 함의를 구현합니다. 주 추론기는 계속해서 레벨 기반의 가변 메타변수를 사용합니다. 인스턴스 헤드를 매칭하는 데 쓰는 작은 불변 맵은 그 조회 안에서만 쓰입니다. 이것은 치환 기반의 또 다른 타입 검사기가 아닙니다.

#![allow(unused)]
fn main() {
pub enum Evidence {
    Given(usize, Vec<usize>),
    Instance(usize, Vec<Type>, Vec<Evidence>),
}
}

주어진 제약(given)은 어휘적 사전 환경 안에서의 자기 위치와 슈퍼클래스 필드를 거쳐 가는 경로를 저장합니다. 인스턴스 증명은 선택된 인스턴스, 그 타입 인자, 그리고 그 전제 조건들의 증명을 저장합니다.

#![allow(unused)]
fn main() {
pub fn resolve(
    &self,
    goal: &Predicate,
    givens: &[Predicate],
    span: Span,
) -> Result<Evidence, Diagnostic> {
    for (i, given) in givens.iter().enumerate() {
        if given.ty == goal.ty
            && let Some(path) =
                self.super_path(&given.class, &goal.class)
        {
            return Ok(Evidence::Given(i, path));
        }
    }
    let (i, args, context) =
        self.by_instance(goal).ok_or_else(|| {
            error(
                ErrorCode::NoInstance,
                format!("no instance for {} {}", goal.class, goal.ty),
                span,
            )
        })?;
    let proofs = context
        .iter()
        .map(|p| self.resolve(p, givens, span))
        .collect::<Result<Vec<_>, _>>()?;
    Ok(Evidence::Instance(i, args, proofs))
}
}

클래스 검증은 슈퍼클래스 순환, 메서드 소속, 메서드의 추가 제약, 명목 인스턴스 헤드 안의 서로 다른 변수, 중첩, 슈퍼클래스 가용성을 검사합니다. 카인드 추론은 제약되지 않은 클래스 카인드에 기본값을 정하기 전에 슈퍼클래스 의존성부터 처리합니다. 인스턴스 문맥은 헤드의 변수만 언급할 수 있습니다. 따라서 풀이는 구조적으로 더 작은 타입으로 내려갑니다.

일반화 시점에 필드 제약은 여전히 클래스 제약보다 먼저 실행됩니다. zonking 이후 evidence.rs는 어휘적 given을 사용할 수 있는 동안 변수 출현 위치에 클래스 증명을 기록합니다. 정교화(elaboration)는 이렇게 검사된 증명을 소비합니다.

#![allow(unused)]
fn main() {
pub struct EvVar {
    pub node: u32,
    pub index: usize,
}
}

elaborate/dictionaries.rs는 클래스마다 명목적 Core 사전 타입을 하나씩 선언합니다. 그 필드에는 슈퍼클래스 사전이 먼저 오고 그 뒤에 메서드가 옵니다. 메서드 지역 한정자는 필드 타입 안에서 System F 다형성이 됩니다. 이것이 소스 언어에 rank-N 시그니처를 추가하는 것은 아닙니다. 각 인스턴스는 자신의 타입 변수와 문맥 사전에 대해 추상화된 전역 값이 됩니다. 메서드 선택자는 사전 생성자에 대한 평범한 매치입니다.

#![allow(unused)]
fn main() {
pub(super) fn dictionary_type(&self, class: &str, ty: Type) -> Type {
    let c = &self.constructors[self.dicts[class]];
    instantiate(&c.result, &c.parameters, &[ty])
}
}

기본 구현에는 이름 붙은 전역이 주어지며, 누락된 각 구현은 해당 인스턴스에 맞게 특수화된 기본 본문의 복사본으로부터 검사됩니다. 이렇게 하면 엄격한 사전 생성이 재귀적인 값의 매듭을 묶지 않게 됩니다. 사전이 도입한 의존성은 평가 전에 정렬됩니다. 함수가 아닌 값의 재귀적 초기화는 거부됩니다. 평가기는 값을 평가하기 전에 함수 클로저를 설치하며, 제약이 없는 각 최상위 값은 여전히 한 번만 평가됩니다.

primitives.rs는 고정된 원시 연산 시그니처와 구현을 제공합니다. 정수 연산은 63비트 래핑을 유지합니다. 부동소수점 표시는 지정된 위치 표기 범위, 부호 있는 지수, 명시적인 특수 값과 함께 최단 왕복(round-trip) 자릿수를 사용합니다. 테스트는 음의 0, 경계 크기, 유니코드 문자열, 실패한 변환을 다룹니다. 공유 런타임 장에서는 사소하지 않은 연산들을 fun-rt로 옮길 것입니다.

실행해 보기

$ cd crates/ch14_classes
$ cargo run -q -- run tests/programs/classes/minimal.fun --lint
42
$ cargo run -q -- dump --pass=types tests/programs/classes/principal-type.fun
main : Num a => a -> a -> a
$ cargo run -q -- check tests/programs/classes/mixed-literals.fun
E0201

실패하는 명령은 레이블이 붙은 진단도 함께 출력합니다. --dump=core는 $D 사전 타입, $f 인스턴스 전역, 명시적인 사전 적용을 드러냅니다. 작은 사전 스냅숏들은 예제를 읽기 쉽게 하려고 Prelude를 끕니다. 일반 빌드는 사용자 스코프보다 먼저 내장된 Prelude를 컴파일합니다. Prelude 이름을 가려도 Prelude 자체의 참조는 바뀌지 않습니다.

식 타입 표기는 감싸는 괄호 없이도 동작합니다. 다만 주의해야 할 곳이 한 군데 있습니다. case 가드 안에서는 타입 표기를 괄호로 감싸서, 그 타입 화살표가 대안의 본문으로 이어지는 화살표와 혼동되지 않게 하십시오.

연습 문제

준비 운동. [Maybe Int]에 대한 동등성 비교의 사전 인자를 살펴보십시오.
중급. 슈퍼클래스에 비해 문맥이 불충분한 인스턴스를 작성한 다음, 빠진 증명을 찾아내십시오.
중급. show Nothing은 모호하지만 show (Nothing :: Maybe Int)는 그렇지 않은 이유를 설명하십시오.
고급. 다형 재귀 픽스처의 타입 추론 의존성 컴포넌트와 런타임 의존성 컴포넌트를 비교하십시오.
심화. 슈퍼클래스 사전의 Core 타입을 손상시키고, 표면 추론을 거치지 않는 린트 회귀 테스트를 추가하십시오.

더 읽을거리

Typing Haskell in Haskell (Jones 1999).
생성자 클래스와 고차 카인드 매개변수 (Jones 1993).
언어 레퍼런스의 클래스와 인스턴스 (Simon Marlow 2010).
Haskell Report의 바인딩 그룹과 인스턴스 제약 사항(Simon Marlow 2010).

Keyboard shortcuts

Write You a Haskell 한국어판