8장: 레이아웃과 확장된 파서

새 파일

• src/layout.rs
• src/fixity.rs
• src/format.rs

변경된 파일

• src/parse.rs
• src/typecheck.rs
• src/ast.rs
• src/elaborate.rs
• src/lexer.rs
• src/lib.rs
• src/main.rs
• src/types.rs

동기

중괄호는 우리가 처음 시작할 때는 유용했습니다. 이제 와서는 대부분 들여쓰기만 봐도 이미 알 수 있는 구조를 위해 구두점을 일일이 타입해 넣게 만들 뿐입니다. Fun을 조금 더 작성하기 편한 언어로 만들어 봅시다.

우리는 레이아웃, where를 사용한 지역 보조 함수, 타입 시그니처, 사용자 정의 연산자를 추가할 것입니다. 이 작업의 상당 부분은 평가 이전에 이루어질 수 있습니다. 들여쓰기는 구두점이 되고, 섹션은 람다가 되며, 연산자 연쇄는 선언된 결합성을 알게 되는 시점에 묶음이 정해집니다. 이것은 만족스러운 컴파일러 기법입니다. 우리는 평가기를 작게 유지하면서도 소스 언어를 더 표현력 있게 만들 수 있습니다.

현재의 언어

들여쓰기가 경계를 제공하는 경우 중괄호와 세미콜론은 선택 사항이 됩니다. where 블록은 해당 등식에 속합니다. 등식의 매개변수는 그 블록 안에서도 계속 보입니다. 여러 지역 선언이 하나의 let 블록을 공유할 수 있습니다.

addTwo x = x + y
  where
    y = 2

main = let result = addTwo 40 in result

시그니처는 같은 블록 안에서 해당 바인딩의 앞이나 뒤에 올 수 있습니다. 타입 변수는 암묵적으로 한정됩니다. 시그니처는 추론된 타입을 특수화할 수는 있지만, 구현을 실제보다 더 다형적으로 만들 수는 없습니다.

id :: a -> a
id x = x

main = let { n :: Int; n = id 42; } in n

연산자는 전위 형식이나 중위 형식으로 정의할 수 있습니다. 연산자의 결합성은 결합성 선언보다 앞선 위치에서도 파일 전체에 적용됩니다. 선언되지 않은 연산자는 우선순위 9에서 왼쪽으로 결합합니다. 이름 있는 함수는 백틱 안에 넣으면 연산자가 됩니다.

infixr 5 %%

a %% b = a * 10 + b

main = 1 %% 2 %% 3

이 프로그램은 1 %% (2 %% 3)을 의미하므로 33을 출력합니다. 섹션은 인자 하나를 채워 줍니다. (40 +)와 (+ 2)는 함수입니다. 반면 (- 2)는 부정(negation)을 의미합니다. 단항 마이너스는 우선순위가 6이므로 -2 * 3 + 4는 (-(2 * 3)) + 4를 의미합니다. 우선순위가 6 이상인 연산자 뒤에 부정을 쓸 때는 괄호로 감싸십시오.

이론

공백을 신비로운 것으로 여기지 않게 되면 레이아웃은 이해하기가 더 쉬워집니다. 우리는 들여쓰기를 우리 파서가 이미 알고 있는 중괄호와 세미콜론으로 변환할 것입니다. Haskell Report가 이 변환을 설명합니다 (Simon Marlow 2010). 어댑터를 살펴보기 전에 직접 손으로 해 봅시다.

보이지 않는 구분자 보기

들여쓰기를 구두점의 약식 표기라고 생각하십시오. 블록의 첫 번째 선언이 그 블록의 왼쪽 여백을 정합니다. 그 여백에서 시작하는 또 다른 선언은 새 항목을 시작합니다. 바깥쪽 여백으로 되돌아가면 블록이 끝납니다.

scale x = result
  where
    doubled = x + x
    result = doubled * 3

main = let n = 7 in scale n

파싱하기 전에 레이아웃은 생략된 구두점을 명시적으로 드러냅니다. 여기서 모든 중괄호와 세미콜론은 레이아웃 패스가 삽입한 것입니다.

{ scale x = result
    where { doubled = x + x
          ; result = doubled * 3
          }
; main = let { n = 7 } in scale n
}

파일 전체에는 바깥쪽 중괄호 한 쌍이 붙습니다. doubled가 where 블록의 들여쓰기를 정하고, 같은 열에 있는 result 앞에는 구분자가 붙습니다. main은 더 왼쪽에 있으므로 레이아웃은 where 블록을 닫고 다음 최상위 선언을 구분합니다. 같은 줄의 in은 내어쓰기가 없었는데도 let 블록을 닫습니다. 마지막 중괄호는 입력이 끝나는 지점에서 파일을 닫습니다. 중괄호를 직접 써도 같은 묶음이 만들어집니다.

이후의 패턴 장과 IO 장에서는 of와 do 뒤에 같은 메커니즘을 사용합니다.

main = do
  case flag of
    True -> putStrLn "yes"
    False -> putStrLn "no"
  putStrLn "done"

이를 명시적으로 쓰면 다음과 같습니다.

{ main = do
    { case flag of
        { True -> putStrLn "yes"
        ; False -> putStrLn "no"
        }
    ; putStrLn "done"
    }
}

마지막 동작 앞의 내어쓰기는 of 블록만 닫습니다. 그 동작은 여전히 do 안에 있습니다. 이 구문들은 나중에 등장하지만, 그 들여쓰기를 변환하는 규칙은 이미 같습니다. 삽입된 구두점과 소스 문자를 구별하는 스팬을 포함하여 실제 토큰을 보려면 --dump=layout을 사용하십시오.

결합성 해석(fixity resolution)은 적용을 구성하기 전에 인접한 연산자들을 비교합니다. 우선순위가 더 높은 연산자가 먼저 결합합니다. 우선순위가 같으면 결합 방향이 서로 호환되어야 합니다. 좌결합 연산자 두 개는 왼쪽부터, 우결합 연산자 두 개는 오른쪽부터 축약됩니다. 비결합 연산자나, 같은 우선순위에서 결합 방향이 섞인 연산자에는 괄호가 필요합니다 (Simon Marlow 2010).

시그니처는 약속을 합니다. a -> a라고 쓰면, 그 함수가 호출자가 고르는 어떤 a에 대해서도 동작한다는 뜻입니다. 검사기가 몰래 a = Int를 골라서 그 약속을 참으로 만들어서는 안 됩니다.

우리는 시그니처의 양화된 변수를 스콜렘(skolem)이라 불리는 경직된 식별자로 바꿔서 이를 강제합니다. 추론 변수는 풀 수 있지만, 스콜렘은 임의의 타입을 나타내며 계속 임의의 타입으로 남아야 합니다. 추론된 스킴을 새로운 유연한(flexible) 변수들로 인스턴스화하고, 이를 경직된 시그니처와 단일화해 봅니다. 또한 어떤 스콜렘도 바깥 스코프로 탈출하지 않는지 검사합니다. 이 검사들을 함께 거치면 추론된 타입이 그 약속을 뒷받침하는지 알 수 있습니다 [Damas & Milner (1982); Pierce (2002)].

구현

레이아웃과 트리비아

logos 렉서는 주석 토큰을 원래 텍스트와 함께 내보냅니다. TriviaLexer는 이를 별도 테이블에 기록하고 의미 있는 토큰만 노출합니다. 그런 다음 LayoutLexer가 들여쓰기 삽입을 수행합니다. 어댑터는 명시적인 중괄호와 괄호를 묶고 그 안의 레이아웃을 재귀적으로 처리하므로, 괄호로 감싼 let도 자신만의 블록을 얻습니다.

#![allow(unused)]
fn main() {
pub fn layout(
    sess: &mut Session,
    file: FileId,
) -> Result<Vec<Spanned>, Stop> {
    let tokens = lexer::lex(sess, file)?;
    let source = &sess.sources.get(file).text;
    let eager = !matches!(tokens.first(), Some((_, Token::Open, _)));
    // offsides measures byte columns with fixed-width tabs. Give it a shadow
    // source whose byte positions are visual columns, then restore original spans.
    let (shadow, forward, backward) = visual_source(source);
    let tokens = tokens
        .into_iter()
        .map(|(lo, t, hi)| (forward[lo], t, forward[hi]))
        .collect::<Vec<_>>();
    match region(&shadow, &tokens, eager)
        .map(|tokens| {
            tokens
                .into_iter()
                .map(|(lo, t, hi)| (backward[lo], t, backward[hi]))
                .collect()
        })
        .map_err(|(lo, hi, message)| (backward[lo], backward[hi], message))
    {
        Ok(tokens) => Ok(tokens),
        Err((lo, hi, message)) => {
            sess.emit(Diagnostic::error(
                ErrorCode::Parse,
                message,
                Span::new(file, lo, hi),
            ));
            Err(Stop)
        }
    }
}
}

이 라이브러리는 let/in 클로저 연산을 노출하지 않습니다. 어댑터는 어떤 가상 프레임이 in에서 이미 닫혔는지 추적하여, 그 프레임들의 이후 구분자와 닫는 중괄호를 억제합니다. 또한 빈 블록과, 명시적 세미콜론 옆의 불필요한 가상 구분자도 처리합니다. 토큰은 원래의 바이트 오프셋을 유지합니다. 삽입된 구두점은 너비가 0인 스팬을 가집니다.

이제 of와 do는 어휘 레이아웃 테스트에 참여합니다. 이들의 언어 구문은 여전히 각각 11장과 15장을 기다립니다. 컴파일러는 그 표현식들을 미리 받아들이지 않습니다.

연산자 연쇄

문법은 첫 번째 피연산자와 그 뒤에 이어지는 연산자/피연산자 쌍들을 유지합니다. 괄호는 해석기가 그 경계를 확정할 때까지 명시적으로 남아 있습니다. 스택이 이 체인들을 해석합니다. 따로 구별된 단항 항목이 부정(negation)에 우선순위를 부여합니다.

#![allow(unused)]
fn main() {
fn chain(
    &mut self,
    first: Expr,
    pairs: Vec<(String, Expr)>,
) -> Result<Expr, Diagnostic> {
    let mut values = Vec::new();
    let mut operators: Vec<Option<String>> = Vec::new();
    self.operand(first, &mut values, &mut operators)?;
    for (op, value) in pairs {
        let next = self.fix(&op);
        while let Some(previous) = operators.last() {
            let prior =
                previous.as_ref().map(|p| self.fix(p)).unwrap_or(Fix {
                    precedence: 6,
                    assoc: Assoc::Left,
                });
            if prior.precedence < next.precedence {
                break;
            }
            if prior.precedence == next.precedence && previous.is_some()
            {
                if prior.assoc != next.assoc
                    || prior.assoc == Assoc::None
                {
                    return Err(self.error(value.span,"operators with conflicting fixities need parentheses"));
                }
                if prior.assoc == Assoc::Right {
                    break;
                }
            }
            let prior = operators.pop().unwrap();
            self.reduce(&mut values, prior);
        }
        operators.push(Some(op));
        self.operand(value, &mut values, &mut operators)?;
    }
    while let Some(op) = operators.pop() {
        self.reduce(&mut values, op);
    }
    Ok(values.pop().unwrap())
}
}

섹션은 소스 식별자로는 쓸 수 없는 생성된 이름을 가진 람다가 됩니다. 현재의 기본 연산자는 가려지지 않았을 때 직접적인 산술 노드로 남습니다. 사용자 연산자는 평범한 커링된 적용이 됩니다. 따라서 Core에는 새로운 식 형태가 필요하지 않습니다.

시그니처 검사

선언은 시그니처가 바인딩에 붙기 전에 수집됩니다. 검사기는 먼저 바인딩을 추론하고 일반화한 다음, 시험용 저장소에서 그 시그니처를 검사합니다. 검사가 성공하면 이후 출현들이 사용하는 현재 스킴을 특수화합니다. 재귀 호출은 추론 중에 단형으로 남습니다. 시그니처가 이끄는 다형 재귀는 이후의 시그니처 검사기와 함께 도입됩니다.

#![allow(unused)]
fn main() {
fn check_signature(
    &mut self,
    inferred: &Scheme,
    declared: &Scheme,
    expr: &Expr,
) -> Result<Scheme, Diagnostic> {
    fn rigid(ty: &Type) -> Type {
        match ty {
            Type::Var(n) => Type::Skolem(*n),
            Type::Arrow(a, b) => Type::arrow(rigid(a), rigid(b)),
            t => t.clone(),
        }
    }
    fn has_skolem(ty: &Type) -> bool {
        match ty {
            Type::Skolem(_) => true,
            Type::Arrow(a, b) => has_skolem(a) || has_skolem(b),
            _ => false,
        }
    }
    let mut trial = self.clone();
    let actual = trial.instantiate(inferred);
    let expected = rigid(&declared.ty);
    let invalid = trial.unify(&actual, &expected, expr).is_err()
        || (0..self.metas.len()).any(|n| {
            self.metas[n].level <= self.level
                && has_skolem(&trial.zonk(&Type::Var(n as u32)))
        });
    if invalid {
        return Err(Diagnostic::error(
            ErrorCode::Signature,
            format!(
                "signature {} is not an instance of inferred type {}",
                declared.ty,
                inferred.ty.canonical()
            ),
            expr.span,
        ));
    }
    // Specialization can constrain variables captured from an outer scope.
    self.level += 1;
    let actual = self.instantiate(inferred);
    let expected = self.instantiate(declared);
    let result = self.unify(&actual, &expected, expr);
    self.level -= 1;
    result?;
    Ok(self.generalize(expected))
}
}

서식화

포매터는 marginalia의 문서 대수와 부착된 주석 맵을 사용합니다. 포매터의 정규 출력은 명시적인 블록을 사용하고 소스의 괄호를 유지합니다. 주석은 토큰 경계에서 별도의 앞선 줄로 옮겨지며, 그 내용과 순서는 보존됩니다. 이렇게 하면 줄 주석 안에 구두점을 삽입하는 일을 피할 수 있습니다.

#![allow(unused)]
fn main() {
pub fn format(sess: &mut Session, file: FileId) -> Result<String, Stop> {
    let parsed = parse::parse(sess, file)?;
    crate::fixity::resolve(sess, parsed)?;
    let (semantic, trivia) = lexer::trivia(sess, file)?;
    let tokens = layout::layout(sess, file)?;
    let source = &sess.sources.get(file).text;
    let mut comments = attach(
        source,
        &trivia,
        semantic.iter().map(|(lo, _, hi)| span(*lo, *hi)),
        AttachOptions::default(),
    );
    // Tokens are smaller anchors than statements. Put their comments on
    // separate leading lines so a trailing line comment cannot swallow a
    // newly inserted separator or a following `where`.
    for (lo, _, hi) in &semantic {
        let entry = comments.entry(span(*lo, *hi));
        entry.leading.append(&mut entry.trailing);
    }
    let mut cursor = 0;
    let doc = document(source, &tokens, &mut cursor, false);
    let rendered = pretty::render(&doc, &comments, RenderOpts::default());
    Ok(format!("{}\n", rendered.trim_end()))
}
}

테스트는 단순히 평가 결과를 비교하는 대신, 스팬을 제거한 뒤 파싱된 트리를 비교합니다. 구문적으로 올바른 모든 코퍼스 프로그램은 왕복 변환되어야 하며, 출력을 다시 서식화하면 정확히 같은 바이트가 나와야 합니다. 전용 사례들은 중첩된 블록 주석과 where 옆의 주석을 유지하는지 확인합니다.

실행해 보기

$ cd crates/ch08_layout
$ cargo run -q -- run tests/programs/layout/right-fixity.fun
33
$ cargo run -q -- dump --pass=fixity tests/programs/layout/negation.fun
{
  main = -(2 * 3) + 4;
}
$ cargo run -q -- fmt example.fun
$ cargo run -q -- fmt example.fun --check

세 가지 덤프는 유용한 짧은 둘러보기가 됩니다. --dump=layout은 삽입된 구두점을 드러내고, --dump=parse는 묶기 전의 연산자 연쇄를 보여 주며, --dump=fixity는 선택된 묶음을 보여 줍니다. 들여쓰기나 결합성 선언 하나만 바꿔 보고 어느 단계가 가장 먼저 달라지는지 관찰해 보십시오.

연습 문제

1. 입문. 결합성이 서로 다른 세 연산자의 묶음을 예측한 다음, fixity 덤프를 여러분의 답과 비교해 보십시오.
2. 중급. (1 + 2 *)가 거부되는 이유를 설명하고 괄호로 고쳐 보십시오.
3. 중급. 연산자와 그 피연산자 사이에 중첩된 주석이 있는 포매터 테스트를 추가하십시오. 트리 동등성과 주석 보존을 모두 확인하십시오.
4. 고급. 스콜렘이 포획된 람다 매개변수를 통해 탈출하게 되는 지역 시그니처를 구성해 보십시오. 이를 거부하는 시험용 저장소 검사를 추적해 보십시오.
5. 고급. 제한된 in 규칙을 Report의 일반적인 parse-error(t) 규칙과 비교해 보십시오. 후자가 더 많은 일을 하게 되는 구문을 찾아보십시오.

더 읽을거리

Report는 레이아웃과 결합성 해석을 정확하게 규정합니다 (Simon Marlow 2010). Damas와 Milner는 시그니처 검사에 쓰이는 주요 타입(principal type) 성질을 정립합니다 (Damas and Milner 1982). Pierce는 다형 타입과 그 인스턴스 사이의 구별을 더 넓은 타입 이론의 틀에서 전개합니다 (Pierce 2002).