Chapter 8: Layout and the Extended Parser

New files

src/layout.rs

src/fixity.rs

src/format.rs

Changed files

src/parse.rs

src/typecheck.rs

src/ast.rs

src/elaborate.rs

src/lexer.rs

src/lib.rs

src/main.rs

src/types.rs

Motivation

The braces were useful while we were getting started. By now they’re mostly making us type punctuation for structure we can already see in the indentation. Let’s make Fun a little nicer to write.

We’ll add layout, local helpers with where, type signatures, and user-defined operators. Much of this can happen before evaluation. Indentation becomes punctuation, sections become lambdas, and operator chains acquire their grouping once we know the declared fixities. It’s a satisfying compiler trick. We can make the source language more expressive while keeping its evaluator small.

The Language, Now

Braces and semicolons become optional when indentation supplies their boundaries. A where block belongs to its equation. The equation’s parameters remain visible inside it. Several local declarations may share a let block.

addTwo x = x + y
  where
    y = 2

main = let result = addTwo 40 in result

Signatures can appear before or after their binding within the same block. Type variables are implicitly quantified. A signature may specialize an inferred type, but it cannot make the implementation more polymorphic than it is.

id :: a -> a
id x = x

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

Operators may be defined in prefix or infix form. Their fixities apply throughout the file, even before the fixity declaration. An undeclared operator associates to the left at precedence 9. Named functions become operators inside backticks.

infixr 5 %%

a %% b = a * 10 + b

main = 1 %% 2 %% 3

This program prints 33 because it means 1 %% (2 %% 3). Sections supply one argument: (40 +) and (+ 2) are functions. (- 2) instead means negation. Unary minus has precedence 6, so -2 * 3 + 4 means (-(2 * 3)) + 4. Write parentheses around negation used after an operator of precedence 6 or greater.

Theory

Layout is easier to understand once we stop treating whitespace as mysterious. We’re going to translate indentation into the braces and semicolons our parser already knows. The Haskell Report describes this translation (Simon Marlow 2010). Let’s do it by hand before looking at the adapter.

See the Invisible Delimiters

Think of indentation as a shorthand for punctuation. The first declaration in a block sets its left margin. Another declaration at that margin begins a new item. Moving back to an enclosing margin finishes the block.

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

main = let n = 7 in scale n

Before parsing, layout makes the omitted punctuation explicit. Here every brace and semicolon was inserted by the layout pass:

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

The file gets an outer pair of braces. doubled establishes the where block’s indentation, and result at the same column gets a separator before it. main is farther left, so layout closes the where block and separates the next top-level declaration. The same-line in closes the let block even though there was no dedent. The final brace closes the file at end of input. Writing the braces yourself produces the same grouping.

The later pattern and IO chapters use the same mechanism after of and do:

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

Its explicit form is:

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

The dedent before the last action closes only the of block. That action is still inside do. These constructs arrive later, but the rule for translating their indentation is already the same. Use --dump=layout to see the actual tokens, including the spans that distinguish inserted punctuation from source characters.

Fixity resolution compares adjacent operators before constructing applications. A greater precedence binds first. Equal precedences require compatible associativities. Two left-associative operators reduce from the left, and two right-associative operators from the right. Non-associative operators and mixed associativities at the same precedence require parentheses (Simon Marlow 2010).

A signature makes a promise. If we write a -> a, we mean the function works for any a its caller chooses. The checker mustn’t make that promise true by quietly choosing a = Int.

We enforce this by replacing the signature’s quantified variables with rigid identities, called skolems. Inference variables can be solved, but a skolem stands for an arbitrary type and must stay arbitrary. We instantiate the inferred scheme with fresh flexible variables and try to unify it with the rigid signature. We also check that no skolem escapes into the surrounding scope. Together these checks tell us whether the inferred type supports the promise [Damas & Milner (1982); Pierce (2002)].

Implementation

Layout and trivia

The logos lexer emits comment tokens with their original text. TriviaLexer records them in a side table and exposes only semantic tokens. LayoutLexer then performs indentation insertion. The adapter groups explicit braces and parentheses, recursively handling layout inside them, so a parenthesized let still gets its own block.

#![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)
        }
    }
}
}

The library does not expose a let/in closure operation. The adapter tracks which virtual frames have already closed at in, suppressing their later separators and closing braces. It also handles empty blocks and redundant virtual separators beside explicit semicolons. Tokens keep their original byte offsets. Inserted punctuation has zero-width spans.

of and do participate in lexical layout tests now. Their language constructs still wait for Chapters 11 and 15, respectively. The compiler does not accept those expressions prematurely.

Operator chains

The grammar retains a first operand followed by operator/operand pairs. Parentheses remain explicit until the resolver has established their boundary. A stack resolves these chains. A distinguished unary entry gives negation its precedence.

#![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())
}
}

Sections become lambdas with generated names that source identifiers cannot spell. The current primitive operators remain direct arithmetic nodes when unshadowed. User operators become ordinary curried applications. Core therefore needs no new expression forms.

Checking signatures

Declarations are collected before signatures are attached to bindings. The checker first infers and generalizes a binding, then tests its signature in a trial store. A successful check specializes the live scheme used by subsequent occurrences. Recursive calls remain monomorphic during inference. Signature-guided polymorphic recursion arrives with the later signature checker.

#![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))
}
}

Formatting

The formatter uses marginalia’s document algebra and attached comment map. Its canonical output uses explicit blocks and keeps source parentheses. Comments move to separate leading lines at token boundaries, preserving their text and order. This avoids inserting punctuation inside a line comment.

#![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()))
}
}

The tests compare parsed trees after removing spans, rather than merely comparing results of evaluation. Every syntactically valid corpus program must round-trip, and formatting the output again must produce exactly the same bytes. Dedicated cases retain nested block comments and comments beside where.

Running It

$ 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

The three dumps make a useful little tour. --dump=layout reveals the inserted punctuation, --dump=parse shows operator chains before grouping, and --dump=fixity shows the chosen grouping. Try changing only the indentation or a fixity declaration and watch which stage first changes.

Exercises

Introductory. predict the grouping of three operators with distinct fixities, then compare the fixity dump with your answer.
Intermediate. Explain why (1 + 2 *) is rejected and repair it with parentheses.
Intermediate. Add a formatter test with nested comments between an operator and its operand. Check both tree equality and comment retention.
Advanced. Construct a local signature whose skolem would escape through a captured lambda parameter. Trace the trial-store check that rejects it.
Advanced. Compare the restricted in rule with the Report’s general parse-error(t) rule. Identify syntax for which the latter would do more work.

Write You a Haskell