17장: Prelude와 deriving

새 파일

• src/derive.rs

변경된 파일

• src/primitives.rs
• src/desugar.rs
• src/ast.rs
• src/core_lint.rs
• src/eval.rs
• src/lexer.rs
• src/lib.rs
• src/main.rs
• src/rename.rs

동기

map, foldr, maybe를 매번 직접 작성하지 않고도 꺼내 쓸 수 있을 때, 언어는 비로소 언어답게 느껴지기 시작합니다. 이제 우리에게는 Fun의 표준 라이브러리를 Fun으로 작성할 수 있을 만큼의 Fun이 갖춰졌습니다. 좋은 이정표입니다!

또한 반복적인 부분은 컴파일러가 작성하도록 가르칠 것입니다. 데이터 타입이 주어지면 deriving은 동등성, 순서, 표시를 위한 평범한 인스턴스를 생성합니다. 생성된 코드는 우리가 손으로 작성한 코드와 똑같은 검사기를 거칩니다. 인터프리터 안에 이 코드를 구해 줄 비밀 동등성 연산이 기다리고 있는 것은 아닙니다.

이 장에서는 인터프리터로 실행되는 언어를 하나로 완성합니다. 백엔드로 넘어가기 전에 잠시 시간을 내어 이 언어를 가지고 놀아 보십시오. 작은 라이브러리 함수는 컴파일러 예제로도 훌륭합니다. 그 타입과 정의만으로도 단 몇 줄 안에 전체 이야기를 들려주는 경우가 많습니다.

현재의 언어

데이터 타입은 deriving Eq를 요청하거나, Eq, Ord, Show 중에서 고른 비어 있지 않은 괄호 목록을 요청할 수 있습니다. 이 예제는 레코드 필드를 선언과 다른 순서로 생성합니다:

data P a = P {x :: a, y :: Int} deriving (Eq, Ord, Show)

main = print (Just (P {y=2,x=Left 1} :: P (Either Int Bool)))

파생된 동등성은 먼저 생성자를 비교하고 그다음 필드를 비교합니다. 순서 비교는 생성자 선언 순서를 따르고, 그다음으로 사전식 필드 순서를 따릅니다. 파생된 Show는 생성 순서와 관계없이 레코드 필드를 선언 순서대로 출력하며, 필요한 곳에서는 중첩된 생성자 적용을 괄호로 감쌉니다. 리스트는 쉼표로 구분된 대괄호 표기를 사용합니다. [Char]는 여전히 문자열이 아니라 리스트입니다. 함수에는 파생된 비교 인스턴스나 표시 인스턴스가 없습니다.

완성된 Prelude는 리스트 폴드와 순회, 유한 생성, 문자열 분할과 결합, 수치 변환, 문자 연산, 모나드 제어를 제공합니다. [a..b]는 양 끝을 포함하는 Int 범위입니다. iterateN은 길이가 제한된 수열을 만듭니다. 생성자 필드가 엄격하기 때문에 무한 리스트는 사용할 수 없습니다. 여기서는 foldl'과 foldl이 똑같이 엄격하게 동작합니다.

리스트를 이어 붙일 때는 ++를, 문자열을 이어 붙일 때는 <>를 사용하십시오. 수치 리터럴은 여전히 고정된 타입을 가지므로 sum과 product는 Int 리스트에 대해 동작합니다. 이 함수들의 시작값은 정수 리터럴이며, Fun의 Num 클래스에는 리터럴을 임의의 수치 타입으로 바꾸는 연산이 없습니다.

작은 함수들을 조합하기

이제 한숨에 읽을 수 있을 만큼 간결한 코드를 작성할 수 있습니다.

total = sum . map (\x -> x * x) . filter even

main = print (total [1..10])

이 프로그램은 220을 출력합니다. 합성은 오른쪽에서 왼쪽으로 읽으십시오. 짝수만 남기고, 각각을 제곱한 다음, 모두 더합니다. 각 함수는 익숙한 일 하나만 하고, (.)는 한 함수의 결과를 다음 함수의 입력으로 연결합니다. 루프 인덱스에 이름을 붙이거나 리스트를 어떻게 따라가며 진행할지 설명할 필요가 없습니다.

계산을 표현하는 아름다운 방식입니다. 그렇다고 해서 할 일이 사라진 것은 아닙니다. Fun은 엄격한 언어이며, 이 프로그램은 중간 리스트를 만듭니다. 나중에 최적화를 통해 이 리스트들을 없앨 수도 있지만, 유용한 분리는 이미 여기에 있습니다. 프로그램을 더 빠르게 만들 방법을 고르기 전에 프로그램이 무엇을 의미하는지 먼저 이해할 수 있습니다.

이론

트리의 동등성을 손으로 작성한다고 상상해 보십시오. 빈 트리끼리는 같습니다. 두 노드는 대응하는 필드가 서로 같을 때 같습니다. 서로 다른 생성자는 같지 않습니다. 데이터 타입 선언만으로도 이 절들을 작성하기에 충분한 정보를 알 수 있으므로, 컴파일러가 이 절들을 작성하게 합시다.

그것이 바로 파생(deriving)입니다. 우리는 평범한 인스턴스를 생성한 다음, 손으로 작성한 인스턴스를 검사할 때와 똑같이 그것을 검사합니다. Haskell Report는 이 구조적 동작을 명세합니다 (Simon Marlow 2010). 우리는 이것을 Fun의 레코드, 원시 문자열, 그리고 더 작은 Show 인터페이스에 맞게 조정합니다.

필드에서 쓰이는 매개변수는 보통 그에 대응하는 인스턴스 제약을 만듭니다. 팬텀 매개변수는 그렇지 않습니다. data Token a = Token Int의 경우, a 타입의 값을 전혀 검사하지 않으므로 동등성 비교에 Eq a 사전이 필요하지 않습니다. 어떤 매개변수가 필드에 나타나는지 판단하기 전에 타입 동의어를 먼저 전개해야 합니다. 그런 다음 일반 인스턴스 솔버가 생성된 컨텍스트가 모든 필드 연산에 실제로 충분한지 검사합니다 (Jones 1999). 도출(deriving)이 이러한 검사를 피해 가는 수단은 아닙니다.

생성자를 출력하는 데에는 작지만 중요한 까다로운 점이 하나 있습니다. Just (Left 3)에는 괄호가 필요하지만, Left 3 단독으로는 필요하지 않습니다. a -> String 타입의 함수는 자신의 결과가 어디에서 쓰일지 알 수 없습니다. 따라서 그 주변의 우선순위도 함께 넘겨주어야 합니다.

Fun의 Show 사전에는 이를 위한 내부 메서드 _showsPrec이 있습니다. 직접 작성한 인스턴스는 기본 구현을 물려받고, 파생 인스턴스는 이를 구조적으로 구현합니다. 최상위 show는 우선순위 0에서 시작합니다. 위치 기반 생성자 인자는 11을 사용하는데, 이는 중첩된 생성자 적용이 스스로 괄호를 치도록 요구합니다. 레코드 필드는 레이블이 붙은 중괄호 안에서 일반 show를 사용합니다.

엄격성은 익숙한 라이브러리 정의를 하나 더 바꿉니다. 일반적인 최상위 정의 undefined = error "undefined"는 쓰이지 않더라도 시작 시점에 실패합니다. 그 대신, 가려지지 않은 Prelude의 undefined 참조는 유닛을 받는 보조 함수를 적용하는 식의 범위 한정 약어입니다. 이렇게 하면 썽크나 지연 바인딩을 도입하지 않고도 사용 지점에서 실패하는 동작을 유지할 수 있습니다. 5장에서 다룬 평가 전략의 구분은 여전히 핵심적입니다(Pierce 2002).

구현

derive::derive는 클래스 수집과 어휘적 이름 변경 직전에 실행됩니다. 생성된 항은 데이터 타입의 소스 스팬을 그대로 유지하므로, 거부된 필드 연산이 있으면 그 선언을 가리킬 수 있습니다. 이 패스는 사용된 매개변수를 수집할 때 별칭을 전개하고, 세 가지 생성기 중 하나를 선택한 뒤, 일반 인스턴스 선언을 덧붙입니다:

#![allow(unused)]
fn main() {
use crate::{
    ast::*,
    diagnostics::{Diagnostic, ErrorCode},
    session::{Session, Stop},
    source::Span,
};
use std::collections::BTreeSet;
struct Builder {
    span: Span,
}
impl Builder {
    fn expr(&self, kind: Kind) -> Expr {
        Expr {
            kind,
            span: self.span,
        }
    }
    fn var(&self, name: &str) -> Expr {
        self.expr(Kind::Var(name.into()))
    }
    fn string(&self, text: &str) -> Expr {
        self.expr(Kind::String(text.into()))
    }
    fn call(&self, name: &str, args: Vec<Expr>) -> Expr {
        args.into_iter().fold(self.var(name), |f, x| {
            self.expr(Kind::App(Box::new(f), Box::new(x)))
        })
    }
    fn pat(&self, name: &str) -> Pat {
        Pat {
            kind: PatKind::Var(name.into()),
            span: self.span,
        }
    }
    fn constructor(&self, c: &ConstructorDecl, prefix: &str) -> Pat {
        Pat {
            kind: PatKind::Con(
                c.name.clone(),
                (0..c.fields.len())
                    .map(|i| self.pat(&format!("{prefix}{i}")))
                    .collect(),
            ),
            span: self.span,
        }
    }
    fn row(&self, patterns: Vec<Pat>, expr: Expr) -> Row {
        Row {
            patterns,
            body: RowBody::Plain(Box::new(expr)),
            locals: vec![],
            span: self.span,
        }
    }
    fn binding(&self, name: &str, rows: Vec<Row>) -> Binding {
        Binding {
            name: name.into(),
            rhs: self.expr(Kind::Equations(rows)),
            nonrecursive: vec![],
            span: self.span,
        }
    }
    fn append(&self, pieces: Vec<Expr>) -> Expr {
        pieces
            .into_iter()
            .reduce(|a, b| self.call("<>", vec![a, b]))
            .unwrap_or_else(|| self.string(""))
    }
    fn eq(&self, d: &DataDecl) -> Binding {
        let mut rows = vec![];
        for (i, a) in d.constructors.iter().enumerate() {
            for (j, b) in d.constructors.iter().enumerate() {
                let mut rhs =
                    self.var(if i == j { "True" } else { "False" });
                if i == j {
                    for k in (0..a.fields.len()).rev() {
                        let test = self.call(
                            "==",
                            vec![
                                self.var(&format!("x{k}")),
                                self.var(&format!("y{k}")),
                            ],
                        );
                        rhs = self.expr(Kind::If(
                            Box::new(test),
                            Box::new(rhs),
                            Box::new(self.var("False")),
                        ));
                    }
                }
                rows.push(self.row(
                    vec![
                        self.constructor(a, "x"),
                        self.constructor(b, "y"),
                    ],
                    rhs,
                ));
            }
        }
        self.binding("==", rows)
    }
    fn ord(&self, d: &DataDecl) -> Binding {
        let mut rows = vec![];
        for (i, a) in d.constructors.iter().enumerate() {
            for (j, b) in d.constructors.iter().enumerate() {
                let mut rhs = self.var(if i < j {
                    "LT"
                } else if i > j {
                    "GT"
                } else {
                    "EQ"
                });
                if i == j {
                    for k in (0..a.fields.len()).rev() {
                        let comparison = self.call(
                            "compare",
                            vec![
                                self.var(&format!("x{k}")),
                                self.var(&format!("y{k}")),
                            ],
                        );
                        let equal = Pat {
                            kind: PatKind::Con("EQ".into(), vec![]),
                            span: self.span,
                        };
                        rhs = self.expr(Kind::Case(
                            Box::new(comparison),
                            vec![
                                self.row(vec![equal], rhs),
                                self.row(
                                    vec![self.pat("order")],
                                    self.var("order"),
                                ),
                            ],
                        ));
                    }
                }
                rows.push(self.row(
                    vec![
                        self.constructor(a, "x"),
                        self.constructor(b, "y"),
                    ],
                    rhs,
                ));
            }
        }
        self.binding("compare", rows)
    }
    fn show(&self, d: &DataDecl) -> Vec<Binding> {
        let mut rows = vec![];
        for c in &d.constructors {
            let mut pieces = vec![self.string(&c.name)];
            if let Some(labels) = &c.labels {
                pieces.push(self.string(" {"));
                for (i, label) in labels.iter().enumerate() {
                    pieces.push(self.string(&format!(
                        "{}{label} = ",
                        if i == 0 { "" } else { ", " }
                    )));
                    pieces.push(
                        self.call("show", vec![self.var(&format!("x{i}"))]),
                    );
                }
                pieces.push(self.string("}"));
            } else {
                for i in 0..c.fields.len() {
                    pieces.push(self.string(" "));
                    pieces.push(self.call(
                        "_showsPrec",
                        vec![
                            self.expr(Kind::Int(11)),
                            self.var(&format!("x{i}")),
                        ],
                    ));
                }
            }
            let mut rhs = self.append(pieces);
            if !c.fields.is_empty() {
                let test = self.call(
                    ">",
                    vec![self.var("p"), self.expr(Kind::Int(10))],
                );
                rhs = self.call("_showParen", vec![test, rhs]);
            }
            rows.push(
                self.row(
                    vec![self.pat("p"), self.constructor(c, "x")],
                    rhs,
                ),
            );
        }
        let show = self.binding(
            "show",
            vec![self.row(
                vec![self.pat("value")],
                self.call(
                    "_showsPrec",
                    vec![self.expr(Kind::Int(0)), self.var("value")],
                ),
            )],
        );
        vec![show, self.binding("_showsPrec", rows)]
    }
}
fn variables(ty: &TypeSyntax, out: &mut BTreeSet<String>) {
    match ty {
        TypeSyntax::Name(n) => {
            out.insert(n.clone());
        }
        TypeSyntax::App(a, b) | TypeSyntax::Arrow(a, b) => {
            variables(a, out);
            variables(b, out);
        }
        TypeSyntax::Qualified(_, t) => variables(t, out),
    }
}
/// Generate only Eq, Ord and Show. Generated terms retain the declaration span.
pub fn derive(
    sess: &mut Session,
    program: &mut Program,
) -> Result<(), Stop> {
    for d in &program.data {
        if d.deriving.is_empty() {
            continue;
        }
        let build = Builder { span: d.span };
        let mut used = BTreeSet::new();
        for c in &d.constructors {
            for ty in &c.fields {
                let expanded =
                    crate::kinds::expand(ty, &program.aliases, d.span)
                        .map_err(|e| {
                            sess.emit(e);
                            Stop
                        })?;
                variables(&expanded, &mut used);
            }
        }
        for class in &d.deriving {
            let methods = match class.as_str() {
                "Eq" => vec![build.eq(d)],
                "Ord" => vec![build.ord(d)],
                "Show" => build.show(d),
                _ => {
                    sess.emit(Diagnostic::error(
                        ErrorCode::Instance,
                        "only Eq, Ord and Show can be derived",
                        d.span,
                    ));
                    return Err(Stop);
                }
            };
            let context = d
                .parameters
                .iter()
                .filter(|p| used.contains(*p))
                .map(|p| PredicateSyntax {
                    class: class.clone(),
                    variable: p.clone(),
                })
                .collect();
            let head = d.parameters.iter().fold(
                TypeSyntax::Name(d.name.clone()),
                |a, p| {
                    TypeSyntax::App(
                        Box::new(a),
                        Box::new(TypeSyntax::Name(p.clone())),
                    )
                },
            );
            program.instances.push(InstanceDecl {
                class: class.clone(),
                head,
                context,
                methods,
                span: d.span,
            });
        }
    }
    Ok(())
}
}

빌더들은 기존의 표면 표현식 타입과 패턴 타입을 구성합니다. 동등성은 생성자 쌍마다 절을 하나씩 생성합니다. 서로 다른 생성자는 False를 반환합니다. 일치하는 생성자는 필드를 왼쪽에서 오른쪽으로 비교하며, 처음으로 같지 않은 쌍에서 멈춥니다:

#![allow(unused)]
fn main() {
fn eq(&self, d: &DataDecl) -> Binding {
    let mut rows = vec![];
    for (i, a) in d.constructors.iter().enumerate() {
        for (j, b) in d.constructors.iter().enumerate() {
            let mut rhs =
                self.var(if i == j { "True" } else { "False" });
            if i == j {
                for k in (0..a.fields.len()).rev() {
                    let test = self.call(
                        "==",
                        vec![
                            self.var(&format!("x{k}")),
                            self.var(&format!("y{k}")),
                        ],
                    );
                    rhs = self.expr(Kind::If(
                        Box::new(test),
                        Box::new(rhs),
                        Box::new(self.var("False")),
                    ));
                }
            }
            rows.push(self.row(
                vec![
                    self.constructor(a, "x"),
                    self.constructor(b, "y"),
                ],
                rhs,
            ));
        }
    }
    self.binding("==", rows)
}
}

순서 비교도 같은 생성자 쌍 구조를 따릅니다. 생성자가 일치하는 쌍에서는 각 필드를 비교하며, 결과가 EQ일 때만 다음 필드로 넘어갑니다. 반면 Show는 생성자 이름, 필드 레이블, 구두점, 그리고 재귀적인 _showsPrec 호출로 문자열 표현식을 만듭니다. 이 식들은 일반적인 이름 변경, 추론, 사전 정교화, 매치 컴파일, Core 린트를 거칩니다. 지원하지 않는 클래스를 요청하면 E0211을 보고합니다. 필요한 동등성 증거 없이 Ord를 요청하는 경우에도 기존 인스턴스 검사를 통해 실패합니다.

라이브러리는 prelude.fun에 있으며, 사용자 프로그램 앞에 내장됩니다. 라이브러리의 비공개 헬퍼 참조는 그 스코프 안에서 해석되므로, 사용자 바인딩이 Prelude 함수의 구현을 몰래 바꿀 수 없습니다. 닫힌 범위(inclusive range)는 값을 증가시키기 전에 상한을 검사합니다. 가장 큰 63비트 정수에서 끝나는 범위는 랩어라운드되지 않고 종료되어야 합니다.

문자 분류와 단순 대소문자 변환은 unicode.fun에 체크인된 유니코드 17.0.0 테이블을 사용합니다. tools/unicode.py는 업스트림 출처와 그 다이제스트를 기록하며, 데이터 라이선스도 함께 보존합니다. 생성된 테이블은 평범하고 간결한 Fun 문자열입니다. 따라서 일반 범주(General Category) 술어와 단순 대소문자 매핑은 새로운 프리미티브를 대거 추가하는 대신 언어 자체를 통해 실행됩니다. isDigit은 의도적으로 ASCII 십진 숫자를 인식합니다. 유니코드에서 숫자로 분류된 문자라고 해서 모두 이를 만족하는 것은 아닙니다.

라이브러리는 컴파일러가 어디서 불필요한 일을 하고 있는지도 알려 줍니다. 리스트를 순회할 때 매 단계마다 꼬리 전체를 복사해서는 안 됩니다. 우리는 불변 생성자 필드 벡터를 Rc로 공유하며, Core 린트는 환경 전체를 복사하는 대신 스코프를 벗어날 때 지역 바인딩을 제거합니다. 이는 Fun 프로그램뿐 아니라 우리 Rust 표현의 비용도 살펴봐야 한다는 점을 일깨워 주는 유용한 사례입니다.

실행해 보기

$ cd crates/ch17_prelude
$ cargo run -q -- run tests/programs/prelude/derive-show-record.fun --lint
Just (P {x = Left 1, y = 2})
$ cargo run -q -- dump --pass=types tests/programs/prelude/derive-show-record.fun
main : IO ()

출력은 선언 순서대로 나열된 레코드 필드와 Just 아래에 놓인 레코드 생성자를 감싸는 괄호를 모두 보여 줍니다. --pass=core는 생성된 인스턴스 사전을 보여 줍니다. --pass=match는 그 사전들의 컴파일된 구조 검사를 보여 줍니다. 별도의 derive-show-tree와 derive-show-literals 픽스처는 중첩된 적용과 이스케이프 처리를 다룹니다.

라이브러리의 경계 사례는 좋은 실험 거리가 됩니다. 가장 큰 Int에서의 단일 원소 범위, fold에 전달된 빈 리스트, 팬텀 매개변수가 있는 파생 인스턴스를 시험해 보십시오. 여기서는 작은 예제들이 실제로 중요한 역할을 합니다. 경계 사례 하나가 길고 평범한 입력보다 라이브러리 정의를 더 명확하게 설명해 줄 수 있습니다.

연습 문제

1. 준비 운동. 생성자가 두 개인 트리에 대해 Eq, Ord, Show를 파생하고, 그 결과를 직접 작성한 인스턴스와 비교하십시오.
2. 중급. 사용하지 않는 데이터 타입 매개변수를 추가하고, 그 매개변수의 사전이 파생 인스턴스 문맥에 나타나는지 살펴보십시오.
3. 중급. Just (Left (Just 3))을 표시하는 동안 전달되는 우선순위를 추적하십시오.
4. 중급. 최대 Int에서의 단일 원소 범위를 테스트하고, 상한 검사와 증가의 순서가 왜 중요한지 설명하십시오.
5. 심화. Fun 프로그램은 바꾸지 말고, 불변 필드 벡터 공유를 도입하기 전과 후에 유니코드 조회에서 일어나는 생성자 꼬리 복사를 측정해 보십시오.

더 읽을거리

• 표준 파생 인스턴스와 Prelude (Simon Marlow 2010).
• 인스턴스 문맥과 함의 (Jones 1999).
• Haskell Report의 클래스와 파생 인스턴스 (Simon Marlow 2010).
• 연산적 의미론과 평가 전략 (Pierce 2002).