7장: Fun의 설계

새 파일

• src/session.rs
• src/core.rs
• src/typecheck.rs
• src/elaborate.rs
• src/diagnostics/codes.rs
• src/diagnostics/mod.rs
• src/parse.rs
• src/source.rs

변경된 파일

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

동기

우리는 파서를 만들었고, 함수가 어떻게 실행되는지 살펴보았으며, 컴파일러에게 타입을 추론하도록 가르쳤습니다. 이제 이 조각들을 하나로 모을 수 있습니다. 이 장부터 우리는 최종적으로 네이티브 코드로 컴파일할 언어인 Fun을 만들어 나갈 것입니다. 각 장은 실행 가능한 스냅숏을 유지하므로, 어떤 아이디어가 어디서 시작되었는지 보고 싶을 때 언제든 더 단순한 버전으로 돌아갈 수 있습니다.

여기서 하는 작업 중 일부는 흥미로운 부분을 즐겁게 만들 수 있도록 해 주는 평범한 엔지니어링입니다. 타입 검사기가 실수를 발견하면, 그 실수가 소스의 어디에 있는지 가리킬 수 있어야 합니다. 한 패스가 실패하면, 다음 패스는 그 패스가 끝내지 못한 출력을 이해하려 들어서는 안 됩니다. 우리는 이름, 소스 위치, 오류에 공통의 거처를 마련해 준 다음, 패스들을 연결하여 계속 확장해 나갈 수 있는 컴파일러를 만들 것입니다.

현재의 언어

프로그램은 선언을 담은 명시적인 중괄호 블록입니다. 선언은 세미콜론으로 구분합니다. 끝에 붙는 세미콜론은 생략해도 됩니다. 각 선언은 자기 자신과 앞선 선언을 참조할 수 있습니다. 전방 참조와 상호 재귀는 9장에서 다룹니다.

{
  twice f x = f (f x);
  sum n = if n == 0 then 0 else n + sum (n - 1);
  main = twice (\x -> x + 1) (sum 10);
}

지역 let도 중괄호를 사용하며, 이 스냅숏에서는 바인딩을 하나만 둡니다. 재귀 바인딩에는 rec 키워드가 필요하지 않습니다. 자기 참조가 있으면 재귀로 식별하며, 이때 우변은 람다여야 합니다. let { x = x; } in x는 E0120으로 거부됩니다.

Char는 유니코드 스칼라 값을 담고, String은 원시 UTF-8 문자열입니다. 문자열은 단형 ++ 연산자로 연결합니다. 정수는 16진수 표기법과 밑줄을 허용합니다. 줄 주석과 중첩 블록 주석을 모두 지원합니다.

{ {- outer {- nested -} -} main = "Hello, " ++ "λ\n"; }

run은 여전히 main의 값을 출력하며, 문자열은 따옴표와 이스케이프를 포함해 출력합니다. 아직 IO를 실행하지는 않습니다. 정수 div와 mod는 내림(floor) 의미론을 따르는 커리된 내장 함수입니다. div 7 (-3)은 -3이고, mod 7 (-3)은 -2입니다. 이에 따라 예전 계산기의 버림 나눗셈 픽스처도 바뀝니다.

이론

소스 프로그램과 실행 가능한 중간 언어는 서로 다른 목적을 가집니다. 소스 트리는 철자, 구문, 소스 스팬을 보존합니다. Core는 평가에 필요한 연산만 남깁니다. 하나를 다른 하나로 정교화(elaboration)하면 언어의 편의 기능이 명시적으로 드러납니다. 나중에 우리는 Core에 타입을 추가하여 별도의 검사기가 각 변환을 검증할 수 있게 합니다 (Pierce 2002).

엄격성은 여전히 의미론상의 요구 사항입니다. 함수는 인자보다 먼저 평가되고, 연산자의 피연산자는 왼쪽에서 오른쪽으로 평가되며, 조건식은 하나의 분기만 선택합니다. 최상위 값은 main의 최종 값이 선택되기 전에 한 번씩 초기화되며, 이 스냅숏에서는 선언 순서를 따릅니다. 사용되지 않는 초기화식이라도 실패하면 프로그램이 멈춥니다. 최상위 함수 본문은 적용될 때까지 평가되지 않습니다.

현재의 타입 시스템은 여전히 힌들리–밀너이며, 6장의 레벨 기반 검사기를 사용합니다 [Damas & Milner (1982); Kiselyov (2013)]. 재귀 바인딩 제약은 값이 자기 자신의 초기화가 끝나기 전에 생성되는 일을 막습니다. 대신 재귀 함수는 진입할 때 자기 자신의 클로저를 참조합니다. 여기서 일반적인 이름 스코프는 여전히 철자 기반 맵을 사용합니다. 고유한 바인딩 식별자는 9장에서 실제로 쓰이기 시작합니다.

구현

소스와 세션 상태

source.rs는 각 파일에 고유한 식별자를 부여하고 줄 시작 위치 테이블을 저장합니다. 스팬은 렉서와 마찬가지로 반열린 바이트 범위이며, 화면에 표시되는 열 번호는 유니코드 스칼라 값 단위로 셉니다. 파일 식별자가 있으므로 서로 다른 파일에서 오프셋이 같아도 혼동되지 않습니다.

#![allow(unused)]
fn main() {
/// Index of a source file in a session's source map.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct FileId(pub u32);

/// Half-open byte offsets within one source file.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Span {
    pub file: FileId,
    pub start: u32,
    pub end: u32,
}

impl Span {
    pub fn new(file: FileId, start: usize, end: usize) -> Self {
        Self {
            file,
            start: start.try_into().expect("source exceeds 4 GiB"),
            end: end.try_into().expect("source exceeds 4 GiB"),
        }
    }
    pub fn range(self) -> Range<usize> {
        self.start as usize..self.end as usize
    }
    pub fn through(self, other: Self) -> Self {
        assert_eq!(self.file, other.file);
        Self {
            end: other.end,
            ..self
        }
    }
}

/// Original text and line starts; columns count Unicode scalar values.
pub struct SourceFile {
    pub name: String,
    pub text: String,
    lines: Vec<usize>,
}

#[derive(Default)]
/// Owns every source used by this compilation, including future Prelude input.
pub struct SourceMap {
    pub files: Vec<SourceFile>,
}

impl SourceMap {
    pub fn add(&mut self, name: impl Into<String>, text: String) -> FileId {
        assert!(u32::try_from(text.len()).is_ok(), "source exceeds 4 GiB");
        let mut lines = vec![0];
        lines.extend(text.match_indices('\n').map(|(i, _)| i + 1));
        let id = FileId(
            self.files.len().try_into().expect("too many source files"),
        );
        self.files.push(SourceFile {
            name: name.into(),
            text,
            lines,
        });
        id
    }
    pub fn get(&self, file: FileId) -> &SourceFile {
        &self.files[file.0 as usize]
    }
    pub fn line_col(&self, span: Span) -> (usize, usize) {
        let file = self.get(span.file);
        let offset = span.start as usize;
        let line = file.lines.partition_point(|start| *start <= offset) - 1;
        (
            line + 1,
            file.text[file.lines[line]..offset].chars().count() + 1,
        )
    }
}
}

names.rs는 직접 작성한 인터너와 새 이름 공급기를 제공합니다. 철자가 같으면 하나의 Symbol을 공유합니다. 공급기를 거듭 호출하면 매번 서로 다른 Name 식별자가 만들어집니다. 이 정의들은 렉시컬 스코프를 서둘러 바꾸지 않으면서, 이후에 만들 리네이머가 사용할 인터페이스를 마련합니다.

세션은 이 기능들과 함께 옵션과 진단 싱크를 소유합니다:

#![allow(unused)]
fn main() {
#[derive(Default)]
/// No pass needs a global interner, source map, or diagnostic sink.
pub struct Session {
    pub sources: SourceMap,
    pub interner: Interner,
    pub supply: Supply,
    pub options: Options,
    pub diagnostics: Vec<Diagnostic>,
}

impl Session {
    pub fn emit(&mut self, diagnostic: Diagnostic) {
        self.diagnostics.push(diagnostic);
    }
    pub fn finish<T>(&self, value: T) -> Result<T, Stop> {
        if self
            .diagnostics
            .iter()
            .any(|d| d.severity == Severity::Error)
        {
            Err(Stop)
        } else {
            Ok(value)
        }
    }
}
}

각 패스는 &mut Session을 받아 Result<Output, Stop>을 반환합니다. Stop은 진단의 사본을 따로 들고 있지 않습니다. 드라이버는 누적된 구조화된 오류를 출력하고 다음 패스를 호출하기 전에 종료합니다. 렉싱과 중복 정의 검사는 오류를 모아 둡니다. 추론은 타입 오류 때문에 의미 있는 결과를 낼 수 없는 지점에서 멈춥니다.

diagnostics/codes.rs는 오류와 경고를 위한 안정적인 레지스트리로, 앞으로 추가될 기능을 위해 예약해 둔 코드도 담고 있습니다. 진단은 심각도, 메시지, 소스 레이블, 노트를 가집니다. 이를 출력하는 것은 Ariadne입니다. stderr의 처음 두 줄은 여전히 코퍼스 실행기가 사용하는 안정적인 코드와 주 소스 위치입니다.

표면 검사와 Core

lexer.rs는 logos를 사용하며, 중첩 주석과 리터럴 이스케이프를 위한 콜백도 포함합니다. 렉서의 예약어 테이블과 연산자 테이블은 cargo xtask syntax를 통해 HTML 및 PDF용 구문 정의도 생성합니다. 책 빌드는 이 출력물이 어긋나지 않았는지 검사합니다.

parser.lalrpop은 스팬이 붙은 표현식과 최상위 바인딩을 만듭니다. 등식의 매개변수는 중첩된 람다가 되며, 중복된 매개변수는 거부됩니다. 검사기는 선언을 소스 순서대로 처리합니다. 자기 자신에 의존하는 바인딩의 경우, 검사기는 람다를 검사하는 동안 임시 단형 타입을 도입하고, 결과를 단일화한 다음, 앞 장에서처럼 일반화합니다.

elaborate.rs는 검사를 마친 트리를 별도의 Core 표현으로 낮춥니다:

#![allow(unused)]
fn main() {
#[derive(Clone, Debug, PartialEq, Eq)]
/// Immediate source values; strings are primitive UTF-8 values, not character lists.
pub enum Lit {
    Int(i64),
    Bool(bool),
    Char(char),
    String(String),
}

#[derive(Clone, Debug)]
/// The initial lambda Core; types, data constructors, and compiled cases arrive later.
pub enum Expr {
    Var(String),
    Lit(Lit),
    Lam(String, Box<Expr>),
    App(Box<Expr>, Box<Expr>),
    Let(Bind, Box<Expr>),
    If(Box<Expr>, Box<Expr>, Box<Expr>),
    Prim(Op, Vec<Expr>, Span),
}

#[derive(Clone, Debug)]
/// A recursive binding is guaranteed to have a lambda right-hand side.
pub struct Bind {
    pub name: String,
    pub rhs: Box<Expr>,
    pub recursive: bool,
}

#[derive(Clone, Debug)]
/// Globals retain source order in this chapter; SCC ordering arrives in Chapter 9.
pub struct Program {
    pub bindings: Vec<Bind>,
    pub main: String,
}
}

연산자는 포화된 프리미티브 호출이 됩니다. 부정은 0에서 빼는 연산이 됩니다. 초기 내장 환경은 div와 mod에 대한 커리된 래퍼를 제공합니다. --no-prelude는 격리된 테스트를 위해 이 래퍼들을 제거합니다. 소스 Prelude는 데이터 타입과 함께 도입됩니다. prim_으로 시작하는 소스 이름은 앞으로 도입될 그 Prelude 경로 밖에서는 E0111로 거부됩니다.

--lint는 현재 Core의 스코프, 프리미티브 포화, 재귀 람다 불변식을 검사합니다. 이것은 구조적 린트일 뿐, 타입 검사기가 아닙니다. 10장에서 이를 완전한 System F 검사로 대체할 것입니다. 골든 하네스는 매 실행마다 이를 활성화합니다.

참조 평가

eval.rs는 Core를 직접 해석합니다. 재귀 클로저는 순환하는 Rust 환경을 만들지 않고 자기 자신의 이름을 저장합니다. 적용은 그 클로저를 매개변수보다 먼저 캡처된 환경에 삽입합니다:

#![allow(unused)]
fn main() {
Expr::App(function, argument) => {
    let function = evaluate(function, env, fuel)?;
    let argument = evaluate(argument, env, fuel)?;
    if let Value::Closure {
        parameter,
        body,
        env,
        recursive,
    } = &function
    {
        let mut local = (**env).clone();
        if let Some(name) = recursive {
            local.push((name.clone(), function.clone()));
        }
        local.push((parameter.clone(), argument));
        evaluate(body, &local, fuel)
    } else {
        Err("internal error: non-function application".into())
    }
}
}

프로그램 실행기는 모든 최상위 바인딩을 순서대로 초기화하고 그 값들을 환경에 보관합니다. 정수는 산술 연산 후 63비트로 정규화되며, 나눗셈은 내림 몫과 그에 맞는 나머지를 계산하기 전에 0인지 검사합니다. 문자와 문자열 출력은 소스 리터럴과 같은 이스케이프 규칙을 공유합니다.

이 참조 평가기는 512 MiB 스레드 스택 위에서 동작하는 재귀적 트리 워커입니다. 실험을 위한 연료 제한은 있지만, 상수 스택 보장은 없습니다. 5장의 명시적 기계는 18장에서 ANF 오라클로 다시 등장합니다. Core의 참조 인터프리터를 직접적인 형태로 유지하면 앞으로 나올 정교화 패스들을 살펴보기가 더 쉬워집니다.

실행해 보기

$ cd crates/ch07_fun
$ cargo run -q -- run tests/programs/fun-top.fun
42
$ cargo run -q -- dump --pass=types tests/programs/fun-string.fun
main : String
$ cargo run -q -- dump --pass=core --no-prelude tests/programs/fun-char.fun
val main = 'λ'
$ cargo run -q -- repl
Fun: expressions, :type EXPR, :core EXPR, :quit.
fun> :type \x -> x
main : a -> a
fun> :quit

같은 작은 프로그램에 대해 tokens, parse, types, core 덤프를 시도해 보십시오. 각 덤프는 여정의 서로 다른 단계를 보여 줍니다. dump --pass=...나 공통 옵션인 --dump=...를 사용할 수 있습니다. 현재 REPL은 개별 표현식을 평가합니다. 영속적인 정의는 JIT와 함께 도입될 것입니다.

연습 문제

1. 쉬움. --dump=tokens를 사용해 중첩 주석과 연산자 -->를 비교해 보십시오.
2. 보통. 0으로 나누는, 사용되지 않는 최상위 초기화식을 추가해 보십시오. main이 왜 결코 값을 내지 못하는지 설명해 보십시오.
3. 보통. 지역 재귀 함수의 Core를 살펴보고, 자기 참조가 어디에서 바인딩되는지 설명해 보십시오.
4. 어려움. 소스 파싱은 통과하지만 잘못된 컴파일러 변환에서만 만들어질 수 있는, 유효하지 않은 Core 프로그램을 구성하십시오. 린트 테스트를 확장하여 이 프로그램을 거부하도록 하십시오.

더 읽을거리

Haskell Report는 Fun이 점진적으로 채택하는 어휘 및 스코프 규칙의 기준을 제공합니다 (Simon Marlow 2010). Pierce는 타입이 있는 중간 언어의 관점을 전개합니다 (Pierce 2002).