9장: 리네이머

새 파일

• src/rename.rs
• src/scc.rs
• src/renamed.rs

변경된 파일

• src/names.rs
• src/typecheck.rs
• src/ast.rs
• src/core.rs
• src/elaborate.rs
• src/eval.rs
• src/fixity.rs
• src/lib.rs
• src/main.rs
• src/parse.rs
• src/types.rs

동기

두 변수가 모두 x라는 이름을 가지면서도 전혀 다른 것을 의미할 수 있습니다. 작은 식에서는 이를 따라가기가 그리 어렵지 않습니다. 하지만 컴파일러가 식을 이리저리 옮기기 시작하면 사정이 덜 편해집니다. 우리는 각 출현이 어느 바인딩을 가리키는지 한 번만 정한 뒤, 그 답을 컴파일러의 나머지 부분 전체에 그대로 전달하고자 합니다.

이것이 리네이머의 첫 번째 일입니다. 두 번째 일은 보조 함수를 그것을 사용하는 함수보다 먼저 작성해야 하는 부담에서 우리를 해방하는 것입니다. 어떤 함수들은 서로를 호출하기까지 하므로, 모든 보조 함수를 앞에 두는 순서는 애초에 존재할 수 없습니다. 우리는 의존성 그래프에서 그러한 그룹을 찾아내고, 타입 검사기에 그룹 전체를 한꺼번에 넘겨줄 것입니다.

현재의 언어

최상위 선언과 지역 선언은 자신이 속한 블록 안에서 뒤에 나오는 선언을 참조할 수 있습니다. 다음 두 함수는 같은 재귀 컴포넌트에 속합니다:

even n = if n == 0 then True else odd (n - 1)

odd n = if n == 0 then False else even (n - 1)

main = even 100

각 바인딩 블록은 하나의 렉시컬 스코프입니다. 지역 정의는 철자가 같은 전역 정의를 가립니다. 같은 블록 안에 정의가 두 개 있으면 E0102 오류입니다. 재귀 컴포넌트의 모든 멤버는 우변이 함수여야 합니다. 따라서 a = b; b = a는 두 값 중 어느 것도 사용되지 않더라도 E0120으로 거부됩니다.

결합성 선언도 스코프 검사를 받습니다. 최상위 결합성 선언에는 파일 안에 대응하는 정의가 있어야 합니다(E0130). 바인딩되지 않은 변수는 E0101을 보고하며, 편집 거리가 2 이하이면 스코프 안에 있는 철자를 제안합니다.

이론

바인딩 식별자는 인턴된 철자와 새로 발급한 정수로 이루어집니다. 철자는 진단 메시지에 쓰입니다. 고유한 정수는 가려진 바인더들을 서로 구별합니다. 추론과 Core는 이 식별자를 사용하므로, 둘 다 렉시컬 조회를 반복할 필요가 없습니다. 이것은 3장에서 살펴본 바인딩 구분에 대응하는 컴파일러 쪽 장치입니다 (Pierce 2002).

각 함수에서 같은 블록 안에서 그 함수가 사용하는 각 바인딩으로 화살표를 그립니다. even이 odd를 호출하고 odd가 even을 호출한다면, 어느 쪽에서 출발하든 화살표를 따라 다른 쪽을 거쳐 다시 돌아올 수 있습니다. 이 둘은 한 묶음입니다. 강하게 연결된 컴포넌트(strongly connected component)는 이러한 상호 도달 가능성을 갖는 극대 그룹입니다.

이제 각 그룹을 하나의 노드로 취급합시다. 그 결과로 얻는 그래프에는 사이클이 없으므로, 의존 대상을 먼저 처리할 수 있습니다. 그것이 바로 우리 타입 검사기에 필요한 순서입니다. 재귀 그룹 밖에 있는 보조 함수는 호출자가 사용하기 전에 타입을 일반화할 수 있습니다 (Simon Marlow 2010).

재귀 컴포넌트 안에서는 바인더마다 임시 단형 타입을 하나씩 할당하고, 그것들을 기준으로 모든 본문을 추론하십시오. 그 임시 타입들을 추론 결과와 단일화하십시오. 그런 다음에야 컴포넌트를 일반화하십시오. 컴포넌트 밖에서는 각 출현이 결과 타입 스킴을 독립적으로 인스턴스화할 수 있습니다. 여기서도 시그니처는 추론된 타입을 검사합니다. 시그니처가 이끄는 다형 재귀는 14장에서 다룰 일로 남아 있습니다.

구현

이름 해석

표면 트리는 리네이밍 단계까지 지역 선언 블록 전체를 그대로 유지합니다. 리네이머는 우변을 하나라도 방문하기 전에 그 블록의 식별자를 모두 할당합니다. 각 람다는 자신의 매개변수를 담은 더 작은 스코프를 도입합니다. 조회는 가장 안쪽 스코프부터 바깥쪽으로 스코프를 탐색합니다.

#![allow(unused)]
fn main() {
pub fn rename(
    sess: &mut Session,
    program: ast::Program,
) -> Result<Program, Stop> {
    let program = crate::fixity::resolve(sess, program)?;
    for fixity in &program.fixities {
        for op in &fixity.operators {
            if !program.bindings.iter().any(|b| b.name == *op) {
                sess.emit(Diagnostic::error(
                    ErrorCode::OrphanFixity,
                    format!("fixity without a definition: {op}"),
                    fixity.span,
                ));
            }
        }
    }
    let mut primitives = Vec::new();
    let mut prelude = BTreeMap::new();
    if !sess.options.no_prelude {
        for op in [
            Op::Div,
            Op::Mod,
            Op::Add,
            Op::Sub,
            Op::Mul,
            Op::Append,
            Op::Eq,
            Op::Lt,
            Op::Le,
        ] {
            let id = sess.fresh_id(op.text());
            prelude.insert(op.text().into(), id.clone());
            primitives.push((op, id));
        }
    }
    let mut renamer = Renamer {
        sess,
        scopes: vec![prelude],
    };
    let groups = renamer.bindings(program.bindings);
    let main = renamer.lookup("main", program.span);
    renamer.sess.finish(Program {
        groups,
        primitives,
        main,
        span: program.span,
    })
}
}

리네이밍된 트리는 별도의 IR입니다. 그 출현(occurrence)에는 Id가 들어 있으며, 이것은 Name과 그 진단용 표기를 함께 보관합니다. 덤프는 이름을 x#12처럼 표시합니다. 이처럼 약간 반복되는 텍스트 덕분에 소스 세션이 사라진 뒤에도 덤프를 읽을 수 있습니다. 비교에는 여전히 할당된 식별자가 포함됩니다.

오류는 순회하는 동안 누적됩니다. 해석되지 않은 출현에는 새로운 자리 표시자가 주어지므로, 다른 본문들도 계속해서 스코프 오류를 검사할 수 있습니다. 드라이버는 자리 표시자가 평가 단계에 도달하기 전에, 리네이밍 패스 직후 멈춥니다.

의존성 컴포넌트

Tarjan의 탐색은 각 정점에 인덱스를 부여하고, 탐색 스택에서 아직 활성 상태인 것 중 도달 가능한 가장 낮은 인덱스를 기록합니다. 두 인덱스가 일치하면 그 정점은 완전한 컴포넌트의 루트이며, 이 컴포넌트는 한꺼번에 꺼낼 수 있습니다.

#![allow(unused)]
fn main() {
fn visit(&mut self, v: usize) {
    self.index[v] = Some(self.next);
    self.low[v] = self.next;
    self.next += 1;
    self.stack.push(v);
    self.active[v] = true;
    for &w in &self.edges[v] {
        if self.index[w].is_none() {
            self.visit(w);
            self.low[v] = self.low[v].min(self.low[w]);
        } else if self.active[w] {
            self.low[v] = self.low[v].min(self.index[w].unwrap());
        }
    }
    if self.low[v] == self.index[v].unwrap() {
        let mut group = Vec::new();
        loop {
            let w = self.stack.pop().unwrap();
            self.active[w] = false;
            group.push(w);
            if w == v {
                break;
            }
        }
        group.sort_unstable();
        self.result.push(group);
    }
}
}

우리의 간선은 의존 대상 쪽을 가리키므로, 완성된 컴포넌트는 추론에 필요한 순서대로 도착합니다. 우리는 덤프를 재현 가능하게 유지하기 위해 소스 인덱스를 고정된 순서로 방문합니다. 바인딩 하나만 담은 그룹은 그 바인딩이 자기 자신을 참조할 때에만 재귀적입니다. Tarjan의 부기(bookkeeping)를 검증하기 위해, 테스트는 상호 도달 가능성을 검사하는, 훨씬 느리지만 직접적인 방법으로도 컴포넌트를 찾습니다.

그룹 단위 추론

재귀 컴포넌트를 추론하는 동안 환경에는 모든 임시 타입이 들어 있습니다. 일반화는 모든 본문이 제약을 제공할 때까지 기다립니다. 시그니처는 추론된 스킴과 대조하여 검사되며, 내보낼 스킴이 확정되기 전에 특수화가 공유 컴포넌트 전체로 전파됩니다.

#![allow(unused)]
fn main() {
fn group(
    &mut self,
    env: &mut Vec<(Id, Scheme)>,
    group: &BindGroup,
) -> Result<(), Diagnostic> {
    self.level += 1;
    let size = env.len();
    let provisional: Vec<_> = group
        .binds
        .iter()
        .map(|b| (b.id.clone(), self.fresh()))
        .collect();
    if group.recursive {
        env.extend(
            provisional
                .iter()
                .map(|(id, ty)| (id.clone(), Scheme::mono(ty.clone()))),
        );
    }
    let inferred = group
        .binds
        .iter()
        .zip(&provisional)
        .map(|(b, (_, expected))| {
            let ty = self.infer(env, &b.rhs)?;
            if group.recursive {
                self.unify(expected, &ty, &b.rhs)?;
            }
            Ok(ty)
        })
        .collect::<Result<Vec<_>, Diagnostic>>();
    env.truncate(size);
    self.level -= 1;
    let inferred = inferred?;
    for (binding, ty) in group.binds.iter().zip(&inferred) {
        if let Some(annotation) = &binding.annotation {
            let scheme = self.generalize(ty.clone());
            self.check_signature(&scheme, annotation, &binding.rhs)?;
        }
    }
    self.level += 1;
    for (binding, ty) in group.binds.iter().zip(&inferred) {
        if let Some(annotation) = &binding.annotation {
            let declared = self.instantiate(annotation);
            self.unify(ty, &declared, &binding.rhs)?;
        }
    }
    self.level -= 1;
    for (binding, ty) in group.binds.iter().zip(inferred) {
        env.push((binding.id.clone(), self.generalize(ty)));
    }
    Ok(())
}
}

이 마지막 단계가 중요합니다. f와 g가 서로를 호출하고 f에 Int -> Int 시그니처가 있다면, 공유된 인자 타입은 g도 제약해야 합니다. g에 대해 제약 없는 다형 스킴을 내보내는 것은 건전하지 않습니다. 회귀 테스트는 그 뒤에 오는 g True 호출을 거부합니다.

재귀 클로저

인터프리터는 모든 재귀 그룹에 대해 불변 레시피, 즉 그 그룹의 람다 본문들과 바깥 환경을 저장합니다. 이러한 클로저 중 하나에 진입하면 함수 인자를 추가하기 전에 그룹의 바인딩을 재구성합니다. 어떤 클로저도 자기 자신을 가리키는 가변 포인터가 필요하지 않으며, 참조 카운팅 순환도 생기지 않습니다.

#![allow(unused)]
fn main() {
fn recursive_values(bindings: Rc<Vec<Bind>>, env: Rc<Env>) -> Env {
    let mut values = Vec::new();
    for binding in bindings.iter() {
        let Expr::Lam(parameter, body) = &*binding.rhs else {
            unreachable!("recursive lambda invariant")
        };
        let value = Value::Closure {
            parameter: parameter.clone(),
            body: Rc::new(*body.clone()),
            env: env.clone(),
            recursive: Some(bindings.clone()),
        };
        values.push((binding.name.clone(), value));
    }
    values
}
}

최상위 값 초기화식은 의존 순서에 따라 한 번 실행됩니다. 함수는 클로저입니다. 클로저를 생성해도 그 본문은 실행되지 않습니다. 이제 Core 린트는 스코프, 프리미티브 포화, 재귀 람다 제한뿐만 아니라 고유한 바인더 식별자도 검사합니다.

실행해 보기

$ cd crates/ch09_rename
$ cargo run -q -- run tests/programs/rename/mutual.fun
True
$ cargo run -q -- dump --pass=rename tests/programs/fun-forward.fun
nonrec { later#10 = 1; }
nonrec { main#9 = later#10; }
$ cargo xtask check-inherit 09
chapter 09: 101 inherited programs verified and chapter tests passed

작은 프로그램에서 보조 함수를 호출하는 함수 아래로 옮겨 보십시오. 이제는 잘 동작합니다. 그다음 두 함수가 서로를 호출하게 만들고 rename 덤프를 살펴보십시오. 재귀 그룹 하나가 보일 것이며, 이 그룹은 검사기에게 두 함수를 함께 추론하라고 알려 줍니다.

연습 문제

1. 입문. 중첩된 섀도잉 예제에서 x가 나타나는 각 위치에 그것이 참조하는 바인더를 표시하십시오. rename 덤프와 비교해 보십시오.
2. 중급. 재귀적이지 않은 보조 함수 하나가 딸린, 세 함수로 이루어진 재귀 그룹의 의존성 그래프를 그린 다음, 출력될 컴포넌트 순서를 예측하십시오.
3. 중급. 서로 무관한 철자 오류 이름 두 개가 들어 있는 진단 테스트를 추가하고, 이 패스가 두 오류를 모두 보고하는지 확인하십시오.
4. 고급. 불변 클로저 레시피에 속한 함수 중 하나가 다른 클로저를 반환하더라도 참조 카운팅 순환이 생기지 않는 이유를 설명하십시오.
5. 고급. 시그니처 기반 다형 재귀를 지원하려면 현재의 컴포넌트 구성 방식과 검사 전략 중 어디를 바꿔야 하는지 짚어 보십시오.

더 읽을거리

Haskell Report는 바인딩 그룹과 의존성 분석을 설명합니다 (Simon Marlow 2010). Pierce는 변수, 스코프, 바인딩에 관한 기초적인 내용을 다룹니다 (Pierce 2002).