5장: 평가

새 파일

• src/cek.rs
• src/cbn.rs

변경된 파일

• src/eval.rs
• src/types.rs
• src/ast.rs
• src/lexer.rs
• src/lib.rs
• src/main.rs
• src/names.rs
• src/normal.rs

동기

재귀 평가기는 평가를 설명하기에 아주 좋은 방법입니다. Rust 호출 하나하나가 프로그램의 한 조각을 더 따라갑니다. 안타깝게도 호출 하나하나가 Rust 스택을 한 조각씩 더 쓸 수도 있습니다. 우리의 작은 언어는 우리가 전혀 의도하지 않은 한계를 물려받은 셈입니다. 스택을 키우면 시간을 벌 수는 있지만, 문제는 여전히 남아 있습니다.

우리는 평가기가 다음에 해야 할 일을 명시적으로 적어 두는 방식으로 이 문제를 해결할 것입니다. 그 정보를 Rust 호출 프레임에 맡겨 두는 대신 자료 구조에 저장하고, 평가기 전체를 하나의 루프로 구동할 것입니다. 이것이 추상 기계의 바탕에 깔린 아이디어입니다.

우리가 사용할 기계는 CEK라고 부릅니다. C는 무엇을 평가하고 있는지 알려 주고, E는 현재 변수 바인딩을 기록하며, K는 다음에 올 일을 기록합니다 (Felleisen and Friedman 1986). 이름이 아이디어보다 더 위압적으로 들릴 뿐입니다. 우리는 평가기가 암묵적으로 하던 장부 정리를 우리가 들여다볼 수 있는 무언가로 바꾸고 있습니다.

현재의 언어

재귀 바인딩은 우변보다 앞에 자신의 타입을 적습니다. 그 우변은 구문상 람다여야 합니다. let rec x : Int = x in x 같은 값은 E0120으로 거부됩니다.

let rec sum : Int -> Int -> Int =
  \(acc : Int) -> \(n : Int) ->
    if n == 0 then acc else sum (acc + n) (n - 1)
in sum 0 100

자기 자신의 이름은 함수 내부와 그 함수를 감싸는 let 본문 안에서 사용할 수 있습니다. 그 타입 표기는 추론된 우변 타입과 대조하여 검사됩니다. fix 역시 명시적인 항 형태이며, 적용보다 더 강하게 결합합니다:

fix (\(self : Int -> Int) -> \(n : Int) ->
  if n == 0 then 1 else n * self (n - 1)) 6

두 예제 모두 타입이 올바르지만, 꼬리 재귀인 것은 합계뿐입니다. 곱셈은 재귀적인 팩토리얼 호출이 반환될 때마다 그 결과를 기다려야 합니다.

이론

함수의 고정점은 펼침 등식(unfolding equation)을 만족합니다. fix f는 f (fix f)처럼 동작합니다. 그 타입 규칙은 인자로 받는 함수가 입력 타입과 같은 타입을 반환하도록 요구합니다 (Pierce 2002).

$$\frac{\Gamma ⊢f:\tau \to \tau }{\Gamma ⊢\mathsf{fix}f:\tau }\text{(Fix)}$$

fix가 있으면 타입이 올바른 프로그램도 영원히 실행될 수 있습니다. fix (\(x : Int) -> x)를 실행해 보고, 연료(fuel)를 얼마나 주든 이 프로그램이 모두 소진하는 것을 확인해 보십시오. 타입 검사기가 우리를 저버린 것은 아닙니다. 타입 검사기는 이 재귀 프로그램이 종료한다고 약속한 적이 없습니다. 재귀 let도 같은 고정점 개념을 사용하지만, 어떻게 초기화할지 알 수 있도록 우변에 함수가 와야 합니다. Fun은 이 제약을 유지할 것입니다.

값에 의한 호출(call-by-value)은 함수 본문에 들어가기 전에 함수와 인자를 먼저 평가합니다. 이름에 의한 호출(call-by-name)은 평가하지 않은 인자를 그것이 쓰일 때마다 치환하며, 람다에 이르면 멈춥니다. 필요에 의한 호출(call-by-need)은 여기에 더해 인자의 결과를 공유하므로, 보류된 계산과 메모된 결과가 필요합니다. 비교를 위한 우리의 작은 인터프리터는 메모이제이션 없이 이름에 의한 호출을 구현합니다. 그 치환 코드를 보면 공유가 없다는 점이 명시적으로 드러납니다. 3장의 완전한 정규 순서(normal-order) 축약기는 이 약한(weak) 이름에 의한 호출 평가기와 달리 람다 본문 안으로도 들어갑니다.

Fun은 중간 언어들을 거치는 동안 평가 순서와 할당을 더 쉽게 따라갈 수 있도록 값에 의한 호출을 택합니다. 생성자 역시 엄격(strict)할 것입니다. 람다는 여전히 값이므로, 언어는 어떤 동작을 아직 수행하지 않은 채로 표현할 수 있습니다. 15장에서는 이 성질을 IO에 활용합니다. 지연 평가를 도입하려면 또 다른 런타임 표현과, 효과와 공간 사용에 대한 또 다른 설명이 필요한데, 이는 이 책이 택한 컴파일러의 범위를 넘어섭니다.

구현

파서는 재귀 바인딩 제약을 검사하고, 허용된 바인딩을 다음 생성자를 통해 하위 표현으로 변환합니다:

#![allow(unused)]
fn main() {
/// Lower function-only recursive bindings to a fixed point with an annotated self parameter.
pub fn recursive(
    name: String,
    ty: Type,
    rhs: Expr,
    body: Expr,
    start: usize,
    end: usize,
) -> Result<Expr, Diagnostic> {
    if !matches!(rhs.kind, Kind::Lam(..)) {
        return Err(Diagnostic::new(
            "E0120",
            "recursive binding must be a function",
            rhs.span,
        ));
    }
    let self_function =
        Expr::new(Kind::Lam(name.clone(), ty, Box::new(rhs)), start, end);
    let fixed = Expr::new(Kind::Fix(Box::new(self_function)), start, end);
    Ok(Expr::new(
        Kind::Let(name, Box::new(fixed), Box::new(body)),
        start,
        end,
    ))
}
}

Value::Recursive는 고정점을 구성하는 데 쓰이는 함수를 저장합니다. 그 재귀 변수를 읽으면 저장된 함수를 해당 재귀 참조에 적용합니다. 재귀 함수의 경우 이는 원래 환경에서 클로저를 다시 만들어 냅니다. 이 방식은 Rust 소유권 순환을 만들지 않습니다. fix에 진입하면 그것을 정의하는 함수를 즉시 평가하므로, 그 초기화 과정에서 발생하는 오류는 여전히 엄격하게 드러납니다. 이것은 명시적 재귀를 보여 주기 위한 교육용 구현이며, 범용 지연 바인딩 메커니즘이 아닙니다.

cek.rs는 제어를 컨티뉴에이션 프레임과 분리합니다. 프레임 변형들은 트리 평가기라면 재귀 호출을 기다려야 했을 지점들입니다.

#![allow(unused)]
fn main() {
/// The remaining work after the current expression returns a value.
enum Frame {
    Argument(Rc<Expr>, Rc<Env>),
    Apply(Value),
    Let(String, Rc<Expr>, Rc<Env>),
    If(Rc<Expr>, Rc<Expr>, Rc<Env>),
    Neg,
    Left(Op, Rc<Expr>, Rc<Env>),
    Right(Op, i64),
    Fix,
}

/// Control alternates between evaluating an expression and returning a value.
enum Control {
    Expr(Rc<Expr>, Rc<Env>),
    Value(Value),
    Apply(Value, Value),
}

/// Statistics make tail-space behavior testable without relying on timing.
pub struct ResultValue {
    pub value: Value,
    pub steps: usize,
    pub max_continuations: usize,
}
}

적용은 먼저 함수를 평가하는 동안 Argument 프레임을 푸시합니다. 그다음 인자를 평가하는 동안 그 프레임은 Apply 프레임이 됩니다. 두 값이 모두 준비되면, 기계는 클로저의 캡처된 환경을 매개변수로 확장한 환경에서 본문에 진입합니다. 이때 적용 프레임들은 이미 팝된 상태입니다:

#![allow(unused)]
fn main() {
Control::Apply(
    Value::Closure(name, body, captured),
    argument,
) => {
    let mut env = (*captured).clone();
    env.push((name, argument));
    Control::Expr(body, Rc::new(env))
}
Control::Apply(_, _) => {
    return Err("expected a function".into());
}
}

합계 함수를 다시 봅시다. 이 함수의 재귀 호출은 이미 답을 만들어 내므로, 호출자를 위해 기억해 둘 것이 없습니다. 팩토리얼에는 아직 끝내야 할 곱셈이 남아 있습니다. 그 보류된 작업에는 프레임이 필요합니다.

이제 두 버전 모두 Rust의 호출 스택을 키우지 않습니다. 그중 꼬리 재귀 버전만이 우리의 명시적인 컨티뉴에이션 스택까지 커지지 않게 합니다. 우리는 짧은 실행과 백만 번 호출하는 실행의 최대 컨티뉴에이션 깊이를 비교하여 이를 확인합니다. 넉넉한 크기의 기계 한 대에서 실행이 끝났다는 사실만으로는 그만큼 많은 것을 알려 주지 못합니다.

전체 전이 루프는 식의 형태를 따라가며, 값이 반환될 때 프레임 하나를 팝합니다. max_continuations는 매 전이 전에 측정되며, 연료 카운터 덕분에 발산하는 예제도 안전하게 살펴볼 수 있습니다. 연료는 기계 전이 횟수를 세므로, 그 수치는 트리 평가기가 세는 식 방문 횟수와 다릅니다.

작은 이름에 의한 호출(call-by-name) 평가기는 적용과 let 경우에 환경 대신 치환을 사용합니다:

#![allow(unused)]
fn main() {
Kind::App(f, a) => {
    let function = evaluate(f, fuel)?;
    if let Kind::Lam(name, _, body) = function.kind {
        evaluate(&substitute(&body, &name, a), fuel)
    } else {
        Err("expected a function".into())
    }
}
Kind::Let(n, a, b) => evaluate(&substitute(b, n, a), fuel),
}

필요에 의한 호출(call-by-need) 변형이라면 이 치환을 공유 셀로 대체할 것이며, 그 셀은 처음 요구될 때 인자를 계산하고 저장합니다. 그 구현은 향후 과제로 남겨 둡니다. 여기서 실제 운영 경로는 여전히 엄격한 기계이며, 비교용 인터프리터는 명시적으로 선택해야 합니다.

실행해 보기

$ cd crates/ch05_eval
$ cargo run -q -- run tests/programs/sum-tail.fun
5050
$ cargo run -q -- run --engine=core tests/programs/factorial.fun
720
$ cargo run -q -- dump --pass=types tests/programs/fix-factorial.fun
Int
$ cargo run -q -- run --engine=cbn tests/programs/strict-argument.fun
1
$ cargo test -q a_million_tail_calls_use_bounded_continuations

기본 엔진은 cek입니다. core는 재귀 클로저 평가기를, cbn은 비교용 인터프리터를 선택하며, normal은 앞서 만든 완전 축약기를 그대로 사용합니다. --fuel=N은 실행 횟수에 상한을 둡니다. 트리 인터프리터에는 적당한 연료 예산을 사용하십시오. 그것들의 호스트 스택 의존성을 없애는 것은 CEK입니다. 두 엄격한 엔진은 답과 실패 모두에서 일치해야 합니다. 이름에 의한 호출 비교 구현은 사용되지 않는 인자가 실패할 경우 의도적으로 다르게 동작합니다. 구현을 읽기 전에 실행해 보고, 어떤 오류가 나올지, 혹은 오류가 나오기는 할지 예측해 보십시오.

연습 문제

1. 쉬움. 각 피연산자가 반환될 때마다 1 + 2 * 3의 컨티뉴에이션 프레임을 그려 보십시오.
2. 보통. 꼬리 합을 꼬리가 아닌 합으로 바꾸고 두 경우의 최대 컨티뉴에이션 깊이를 측정해 보십시오.
3. 보통. 클로저가 호출자의 환경이 아니라 정의된 곳의 환경을 캡처해야 하는 이유를 설명하십시오.
4. 어려움. 값에 의한 호출(call-by-value)은 한 번만 계산하는데 이름에 의한 호출(call-by-name)은 상당한 작업을 반복하게 되는 식을 제시하십시오. 공유(sharing)가 무엇을 바꾸는지 설명하십시오.

더 읽을거리

Felleisen과 Friedman은 추상 기계 관점의 설명을 전개합니다 (Felleisen and Friedman 1986). Pierce는 평가 전략, 타입 지정, 고정점 사이의 관계를 다룹니다 (Pierce 2002). Appel은 컴파일 과정에서 컨티뉴에이션을 명시적으로 만드는 관련 기법을 전개합니다(Appel 1992). 우리의 ANF 컴파일러는 나중에 이 연결 고리를 다시 다룹니다.