Parse, don't validate

[sorawee]

There are common wisdoms in type-driven development like make illegal states unrepresentable and parse, don't validate. Langium's validation phase is the opposite of these approaches: validation doesn't allow us to decorate the AST with verified data and types that guarantee their correctness. I know there's a caching mechanism that I could use, but that really seems like a hack. Is there any other mechanisms that I missed?

[msujew]

Hey @sorawee,

Langium is mainly designed as a toolkit to build language servers and surrounding tools from one code base. Language servers typically don't follow model- or type-driven development practices as they have a different set of requirements. They cannot simply outright reject invalid input, as that would make it impossible to provide meaningful, semantically correct results on not-quite correct data. I.e. programs that are in the process of being written.

I know there's a caching mechanism that I could use, but that really seems like a hack.

The caching mechanism is designed with caching data for AST nodes in mind. More specifically, we usually use it to cache scoping and type system information for specific documents. Note that attaching data to an AST node directly (you can always attach more properties to an AST node in JS) is usually not a good idea, as the AST node is not recreated upon changes to the workspace. E.g. if you have a dependency from file A to file B, changing file B will not lead to file A getting re-parsed. However, our caching will catch that (assuming it is correctly configured), and invalidate the cache for file A as well, as changes to file B might invalidate computed data on file A.

[sorawee]

Thanks for the reply!

Indeed, components of language servers like autocompletion, autoformatter, codelens, and even validation itself, are invoked during the process of program writing, so I totally agree that we can't outright reject invalid input.

However, my question was about what the validation phase could produce for later phases in the pipeline. IIUC, validation is the last step before we enter the traditional language toolchain pipeline (compilation, evaluation, symbolic execution, etc.), so it won't affect the components of language servers mentioned above. And I think it's very helpful to get more correctness guarantee on this "traditional language toolchain pipeline", since this is the core functionality of the language, where correctness matters much more.

[msujew]

Right. What we usually do when building interpreters and compilers with Langium is similar to what we already do in our langium-cli: Run the documents through the document builder and assert that there are no validation errors. Only then continue with the next step.

Can you elaborate a bit more on the correctness guarantee? What would you expect there?

[aabounegm]

A simple example I could think of is to have the ref property of Reference<> nodes be non-optional after the linking and validation phases pass successfully.
However, I personally think this is a bigger issue in stricter-typed languages (such as Haskell, which is what the articles linked above use) since in TypeScript you can simply use !. I understand that this is a particular example and @sorawee is talking about a principle in general (which I agree with, generally speaking), but I cannot come up with another concrete example off the top of my head.

[aabounegm]

Or maybe a simple example for correctness guarantee would be a C-like language that requires a main function. In the parser, it is more convenient to parse all function the same (so it's not a parsing error to not have a main function), and the AST looks something like this:

interface Program extends AstNode {
  functions: FunctionDeclaration[];
}

whereas a structure that guarantees correctness after running the validators would look more close to this:

interface Program extends AstNode {
  mainFunction: FunctionDeclaration;
  otherFunctions: FunctionDeclaration[];
}

Similarly to the example above, it is easy to overcome this wherever needed (like functions.find(fn => fn.name == 'main') and filter for the others, for example), it is not very convenient and has less readability (in terms of communicating expectations of the data) compared to a transformed AST.

However, while I generally agree with the principles (making illegal states unrepresentable and parsing instead of validating), I believe that they would add a lot of unnecessary complexity to Langium, increasing friction for new users, especially ones not familiar with Functional Programming principles.