Internals · Parsing

Parsing

Each line is read against the grammar's productions to see what it is; parsing is how those lines are assembled. A whole program is not a flat list of lines: indentation nests each line under the one above it, so the source is really a tree. Parsing walks that structure once, top to bottom, building the Code.Language.Program.Tree — and as it goes it carries state, so it can check and resolve on the way to the canonical Structure form.

Walking with state

The walk carries a single piece of state that is updated as we enter and leave each block. The keyword that opens a block decides how the state changes. The aim is to do everything in this one pass — no block should need to be visited twice.

We assume two primitives are already in hand: given a line we can ask for its keyword, and given a line we can step through the lines nested beneath it. With those, the walk is small: read a line's keyword, use it to update the state, then descend into that line's children and repeat.

walk(line, state):
    keyword := keywordOf(line)
    state.enter(keyword, line)        # validate in context, record, push a scope
    for child in childrenOf(line):
        walk(child, state)
    state.leave(keyword, line)        # resolve, bubble results up, pop the scope

One recursive walk over the indentation tree. Each line is seen exactly once.

What the state holds

The state is the running picture of everything known so far at the current point in the walk:

the stack of enclosing scopes — the module, type or function we are currently inside;
every name declared so far and the type bound to it, so later lines can be checked against it;
which keywords are legal in the current block, so a keyword used in the wrong place is caught immediately;
the generic type variables currently in play and whatever each has been resolved to.

Entering a block pushes a scope and records what the keyword introduces; leaving it resolves anything that was still open, bubbles up what the parent needs (such as a function's inferred return type), and pops the scope again.

Checking as we go

Because the full state is available at every line, most errors surface exactly where they occur, with the surrounding scope on hand to explain them: a keyword that is not allowed in this block, a name used before it is declared, a value whose type does not match where it is being used. The single pass works as long as everything a line refers to is already in scope by the time we reach that line — declarations come before their use, so no forward look-ahead is needed.

Inferring generics

Types are tracked the whole way down: as each name is bound, its type is recorded in the current scope, and expressions are checked against the types already known. Function calls are the interesting case — there is currently no way to write type arguments explicitly on a call, so they have to be worked out on the spot. When the walk reaches a call, the types of the arguments (which we have been tracking) are matched against the function's declared parameter types; wherever a parameter is generic, that match pins the type variable. Once pinned, those variables give the call's result type, which then flows into whatever the call is bound to — all within the same single pass.