11장: 데이터 타입과 패턴 매칭

새 파일

• src/data.rs
• src/syn.rs
• src/desugar.rs

변경된 파일

• src/typecheck.rs
• src/core.rs
• src/elaborate.rs
• src/ast.rs
• src/core_lint.rs
• src/core_type.rs
• src/eval.rs
• src/fixity.rs
• src/layout.rs
• src/lexer.rs
• src/lib.rs
• src/main.rs
• src/parse.rs
• src/rename.rs
• src/renamed.rs
• src/session.rs
• src/types.rs

동기

정수와 함수만으로도 우리는 꽤 멀리 왔지만, 이제 제대로 된 자료 구조를 만들 때입니다. 이진 트리는 비어 있을 수도 있고, 값 하나와 하위 트리 두 개를 담을 수도 있습니다. 조회는 실패할 수도 있고 결과를 돌려줄 수도 있습니다. 대수적 데이터 타입을 쓰면 “여기에는 아무것도 없음”을 뜻하는 특별한 값을 따로 만들어 내지 않고도 이런 것들을 직접 표현할 수 있습니다.

패턴 매칭은 그 값들을 분해하는 똑같이 직접적인 방법을 제공합니다. 데이터의 모양이 곧 프로그램의 모양이 됩니다. 이것은 함수형 프로그래밍의 아름다운 부분 중 하나이며, 우리는 지금부터 이것을 끊임없이 사용할 것입니다.

우리는 먼저 패턴을 소스 순서대로 시도하는 방식으로 매칭을 구현하겠습니다. 이렇게 하면 매칭이 무엇을 의미하는지 명확하게 설명할 수 있습니다. 16장에서는 같은 매칭을 네이티브 코드에 적합한 결정 트리로 바꾸겠습니다.

현재의 언어

선언은 명목적(nominal) 타입과 그 생성자를 도입합니다. 생성자 인자는 엄격(strict)하게 평가되며, 생성자는 커리된 함수로 주고받을 수 있습니다.

data Tree a = Empty | Node (Tree a) a (Tree a)

size Empty = 0
size (Node left _ right) = 1 + size left + size right

main = size (Node Empty 42 Empty)

size를 데이터 타입과 나란히 놓고 읽어 보십시오. Empty는 0을 더합니다. Node는 1에 두 자식의 크기를 더한 값을 더합니다. 정의가 데이터를 거의 그대로 따라갑니다. 아름다운 일이며, 훨씬 더 흥미로운 트리로도 확장됩니다.

트리를 뒤집는 것도 똑같이 직접적으로 할 수 있습니다.

data Tree a = Empty | Node (Tree a) a (Tree a)

mirror Empty = Empty
mirror (Node left x right) = Node (mirror right) x (mirror left)

main = mirror (Node Empty 1 (Node Empty 2 Empty))

mirror가 x를 전혀 들여다보지 않는다는 점에 주목하십시오. 그 타입은 Tree a -> Tree a이므로, 어떤 원소 타입의 트리에도 동작합니다. 재귀는 값은 그대로 둔 채 모양만 바꿉니다.

등식에는 중첩된 생성자 패턴, 리터럴, 와일드카드, as-패턴이 올 수 있습니다. 리스트, 쌍, 세 쌍, 유닛에는 전용 구문이 있습니다. 가드는 Bool 타입이어야 합니다. 모든 가드가 실패하면 매칭은 다음 등식으로 이어집니다.

select all@(x : xs) | x < 0 = xs
select all = all

main = select [-1,2,3]

where 블록은 모든 가드를 포함한 등식 전체에 속합니다. case 대안에도 가드와 where 블록을 둘 수 있습니다. 패턴 람다와 엄격한 비재귀 패턴 바인딩도 동작합니다: let (x,y) = (20,22) in x + y. 여기서 타입은 여전히 1차(first-order)입니다. 데이터 타입 매개변수는 카인드 *를 가지므로, Tree Int는 유효하지만 f Int처럼 매개변수를 적용하는 것은 13장에서 다룹니다.

초기 Prelude는 다음의 실제 Fun 소스에서 임베드됩니다:

data Bool = False | True

data Ordering = LT | EQ | GT

data Maybe a = Nothing | Just a

data Either a b = Left a | Right b

data [] a = [] | (:) a [a]

data () = ()

data (,) a b = (,) a b

data (,,) a b c = (,,) a b c

이론

데이터 타입 선언은 각 생성자에 대한 다형적 타입 스킴을 제공합니다. 예를 들어 Node는 a에 대해 정량화된 Tree a -> a -> Tree a -> Tree a 타입을 가집니다. 다형 함수의 각 출현과 마찬가지로, 각 출현은 그 스킴을 새로운 메타변수로 인스턴스화합니다 [Marlow (2010); Pierce (2002)].

필드 타입이 인스턴스화된 생성자에 대해, 패턴 판단은 하위 패턴이 도입하는 바인딩을 반환합니다:

$$\frac{K:{\tau }_1\to {\tau }_2\to T\Gamma ⊢p_1:{\tau }_1\Rightarrow {\Delta }_1\Gamma ⊢p_2:{\tau }_2\Rightarrow {\Delta }_2}{\Gamma ⊢K{p}_1{p}_2:T\Rightarrow {\Delta }_1,{\Delta }_2}\text{(Constructor pattern)}$$

결합된 패턴 환경은 한 이름을 두 번 바인딩해서는 안 됩니다. 각 행은 같은 검사 대상(scrutinee) 타입들에 대해 검사되며, 성공한 모든 우변은 같은 결과 타입을 가져야 합니다. 가드는 추가로 Bool과 단일화됩니다.

Fun은 값을 구성하기 전에 필드를 평가합니다. 매치가 실패하면 런타임 오류가 발생합니다. 지연 패턴이나 보류된 생성자 필드는 없습니다. 완전성 경고와 중복 경고에는 별도의 분석이 필요합니다. 이 경고들은 매치 컴파일과 함께 도입됩니다(Maranget 2007).

구현

필드를 검사하기 전에 이름 선언하기

data.rs는 먼저 모든 타입 헤드를 할당한 다음 생성자 필드를 변환합니다. 이 덕분에 상호 재귀적인 데이터 타입이 가능합니다. 불변 테이블은 각 타입의 항수, 각 생성자의 스킴, 그리고 선언 순서에 따른 태그를 저장합니다. 중복된 이름, 바인딩되지 않은 필드 변수, 잘못된 타입 항수는 식 추론이 시작되기 전에 진단됩니다.

리네이머는 표현식과 패턴 안의 생성자 이름을 일반 변수와 별도로 해석합니다. 패턴 변수는 행마다 새로운 식별자를 받습니다. 그런 다음 가드와 우변을 모두 방문하는 동안 리네이머의 스코프에는 그 변수들과 해당 행의 지역 선언이 들어 있습니다.

구문을 Syn으로 낮추기

desugar.rs는 리네이밍과 추론 사이에 명시적인 패스를 도입합니다. 리스트와 튜플은 생성자 적용이 됩니다. if는 True와 False에 대한 두 행짜리 매치가 됩니다. 중위 &&와 ||는 먼저 조건식이 됩니다. 퍼스트 클래스(first-class) 값으로서 이 연산자들은 평범한 에타 확장 함수이며, 그 인자는 값에 의한 호출 적용으로 평가됩니다.

변수 패턴만 포함하는 단일 등식은 일반 람다와 let을 사용할 수 있습니다. 그 밖의 등식은 각 인자에 대한 람다와 그 뒤에 오는 매치가 됩니다:

#![allow(unused)]
fn main() {
let params: Vec<_> = (0..rows[0].patterns.len())
    .map(|_| self.sess.fresh_id("$match"))
    .collect();
let scruts = params
    .iter()
    .map(|id| self.node(Kind::Var(id.clone()), span))
    .collect();
let mut body = self.node(Kind::Match(scruts, rows), span);
for id in params.into_iter().rev() {
    body = self.node(Kind::Lam(id, Box::new(body)), span);
}
body
}

엄격한 패턴 바인딩은 바인딩된 값들을 중첩된 쌍으로 표현한 하나의 검사된 묶음을 사용하고, 그 뒤에 프로젝션이 이어집니다. 우변은 한 번만 평가됩니다. 새로 바인딩되는 이름들은 그 우변을 리네이밍하는 동안 가려지므로, 같은 철자의 바깥쪽 바인딩에 여전히 접근할 수 있습니다. 사용되지 않는 최상위 패턴 바인딩도 여전히 실행되며 실패할 수 있습니다.

생성자 패턴 추론하기

검사기는 생성자 스킴을 인스턴스화하고, 필드 화살표를 결과 타입과 분리한 뒤, 그 결과를 검사 대상과 단일화합니다. 그런 다음 각 하위 패턴을 대응하는 인스턴스화된 필드에 대해 검사합니다:

#![allow(unused)]
fn main() {
PatKind::Con(id, patterns) => {
    let info = self.data.con(id).clone();
    if patterns.len() != info.fields.len() {
        return Err(Diagnostic::error(
            ErrorCode::Mismatch,
            format!(
                "{} expects {} pattern fields",
                id.name,
                info.fields.len()
            ),
            pattern.span,
        ));
    }
    let mut ty = self.instantiate(&info.scheme);
    let mut fields = Vec::new();
    for _ in patterns {
        let Type::Arrow(a, b) = ty else {
            unreachable!("constructor arity")
        };
        fields.push(*a);
        ty = *b;
    }
    self.unify(expected, &ty, &site)?;
    for (pattern, ty) in patterns.iter().zip(fields) {
        self.pattern(env, pattern, &ty)?;
    }
}
}

패턴 변수는 단형적으로 행 환경에 들어갑니다. 지역 바인딩은 일반적인 let 다형성을 유지합니다. 검사기는 System F 정교화에 이미 필요한 인스턴스화 메타데이터와 함께 식과 패턴 바인더의 타입을 기록합니다.

Core와 린트 확장하기

정교화는 생성자 값을 에타 확장하여, 본문이 포화된 Con 노드인 람다로 만듭니다. 엄격한 let은 매치 검사 대상을 한 번씩, 소스 순서대로 평가합니다. Core는 결정 트리 컴파일러가 도입될 때까지 중첩 패턴을 유지합니다.

#![allow(unused)]
fn main() {
/// Nested patterns remain until the decision-tree compiler in Chapter 16.
#[derive(Clone, Debug)]
pub enum Pat {
    Var(Id),
    Wild,
    As(Id, Box<Pat>),
    Con(crate::data::ConId, Vec<Pat>),
    Lit(Lit),
}

/// A guarded row falls through when all its Boolean tests fail.
#[derive(Clone, Debug)]
pub enum RowBody {
    Plain(Box<Expr>),
    Guarded(Vec<(Expr, Expr)>),
}

/// Row-local declarations run after patterns match and are shared by the guards.
#[derive(Clone, Debug)]
pub struct Row {
    pub pats: Vec<Pat>,
    pub locals: Vec<BindGroup>,
    pub body: RowBody,
    pub span: Span,
}

/// Scrutinees name strict preceding lets; the match records its result type and failure site.
#[derive(Clone, Debug)]
pub struct Match {
    pub scruts: Vec<Id>,
    pub rows: Vec<Row>,
    pub result: Type,
    pub span: Span,
}
}

린트는 생성자 타입 인자, 필드 개수, 필드 타입을 독립적으로 검사합니다. 생성자 패턴의 경우 린트는 검사 대상의 타입 인자로 선언을 인스턴스화한 다음 각 바인더를 검사합니다. 가드는 불리언이어야 하며, 모든 행은 선언된 매치 결과를 내야 합니다. 형식이 잘못된 Core 테스트는 표면 추론기에 입력 검증을 요청하지 않고도, 마치 연습 문제를 풀듯 이러한 검사들을 직접 시험합니다.

행 실행하기

인터프리터는 생성자 필드를 왼쪽에서 오른쪽으로 평가합니다. 이미 평가된 값에 대한 매칭은 생성자와 리터럴을 재귀적으로 검사하며, 변수와 as-패턴으로 행 전용 환경을 확장합니다:

#![allow(unused)]
fn main() {
fn matches_pattern(p: &core::Pat, v: &Value, env: &mut Env) -> bool {
    match p {
        core::Pat::Wild => true,
        core::Pat::Var(id) => {
            env.push((id.clone(), v.clone()));
            true
        }
        core::Pat::As(id, p) => {
            env.push((id.clone(), v.clone()));
            matches_pattern(p, v, env)
        }
        core::Pat::Lit(l) => matches!(v,Value::Lit(actual) if l==actual),
        core::Pat::Con(id, ps) => match v {
            Value::Con(actual, vs)
                if id == actual && ps.len() == vs.len() =>
            {
                ps.iter().zip(vs).all(|(p, v)| matches_pattern(p, v, env))
            }
            _ => false,
        },
    }
}
}

패턴이 실패하면 그 환경을 버리고 다음 행을 시도합니다. 패턴이 성공하면 그 where 그룹을 한 번 평가한 다음, 가드를 순서대로 검사합니다. 모든 가드가 실패하면 실행은 다음 행으로 넘어갑니다. 행을 모두 소진하면 fun: pattern match failure at FILE:LINE:COL을 보고하고 상태 코드 1로 종료합니다.

값 프린터는 생성자 우선순위를 사용하므로 중첩된 적용은 Just (Left 3)처럼 출력됩니다. 리스트와 튜플은 표면 표기법을 사용합니다. 문자 리스트는 ['a','b']로 출력되고, 기본 문자열은 큰따옴표를 유지합니다.

실행해 보기

$ cd crates/ch11_data
$ cargo run -q -- run tests/programs/data/tree.fun --lint
(True,False)
$ cargo run -q -- dump --pass=syn tests/programs/data/bool-data.fun
nonrec { not#9 = (lambda $match#11 (match $match#11 [ (True) -> False ] [ (False) -> True ])); }
nonrec { main#10 = (app (app (,) (app not#9 True)) (app not#9 False)); }
$ cargo test --test data

가드 폴스루는 실험해 볼 가치가 있습니다. 첫 번째 패턴은 매치되지만 그 가드는 실패하게 만든 다음, 다음 등식이 실행되는지 확인하십시오. 사용되지 않으면서 실패하는 최상위 패턴 바인딩도 시도해 보십시오. 엄격한 평가에서는 “사용되지 않는다“고 해서 매치가 사라지지 않습니다. 이러한 예제들은 평범하게 성공하는 트리 순회에서는 놓칠 수 있는 부분을 연습 문제처럼 짚어 줍니다.

연습 문제

1. 입문. 이진 트리 미러 함수를 정의하고 비대칭 트리에서 테스트하십시오.
2. 중급. 필드가 너무 적은 생성자 패턴에서 발생하는 타입 오류와, 서로 다른 타입을 반환하는 두 등식에서 발생하는 타입 오류를 설명하십시오.
3. 중급. 뒤따르는 등식으로 폴스루하는 가드 두 개를 작성하십시오. 두 가드가 공유하는 계산을 where로 옮기고 Syn 덤프를 살펴보십시오.
4. 고급. 엄격한 패턴 바인딩(strict pattern binding)을 Haskell의 일반 패턴 바인딩과 비교하십시오. 종료 여부나 오류 동작이 달라지는 프로그램을 작성하십시오.
5. 심화. 필드 개수는 유지하면서 타입이 서로 다른 두 생성자 필드를 맞바꾸는 린트 테스트를 설계하십시오.

더 읽을거리

Haskell Report는 데이터 타입 선언, 패턴, 가드, 지역 스코프를 명세합니다(Simon Marlow 2010). Pierce는 데이터의 도입(introduction)과 제거(elimination) 사이의 연결을 전개합니다(Pierce 2002). Maranget의 논문들은 그 이후 단계인 경고 분석과 결정 트리 컴파일을 설명합니다[Maranget (2007); Maranget (2008)].