TypePal: Maintainable typecheckers for your DSLs

Writing typecheckers is hard because a myriad of constraints must be checked. That leads to entangled and difficult-to-maintain typechecker code. TypePal is a new approach to improve upon this situation. We use it in many projects at Swat.engineering, including the typechecker of the open-source Bird DSL.

Typechecking is necessary and cost-effective

Typechecking is omnipresent but not always very visible. It ranges from a friendly notice from your IDE that a certain import in your program is unused to a harsh error that a function is called in the wrong way. In an IDE, an illegal use of the + operator is flagged by the typechecker and that usually looks like this:

Typechecking helps to spot problems early on and is cost-effective. It increases the productivity of software engineers, improves the reliability and security of your code, and helps to avoid technical debt.

Why is typechecking hard?

A typechecker has to answer dozens, hundreds or even thousands of questions like:

• How to handle declarations of names, in particular, their scope and uses?
• How to distinguish the roles names can play, e.g. names of functions, data types, labels, constants or variables?
• How to handle imports and multiple namespaces?
• How to handle global or local type inference?
• How to handle overloading?
• How to give precise error messages (and avoid spurious messages)?
• How to extract information that is useful for later compiler stages or the IDE, for example, code generation, use-def information or name completion?
• Are the types in assignment statements compatible?
• Is this function called with the right number of parameters, and do these have the expected type?
• Are the operands of this operator (say a + operator) as expected, and what is the type of the result?

For a general-purpose language, the list will be long and stable. For a (new) DSL, the list will be smaller but in flux.

Typechecking is complex. Writing individual checks may be hard, and the staging and flow of information needed for each check is delicate. So, it is easy to mess up a manually written typechecker. This is particularly true during DSL development.

TypePal to the rescue

TypePal is a Rascal library that leverages the best of both worlds from formal, rule-based typecheckers and manually written ones:

• TypePal reduces complexity by attaching constraints to each syntax rule of the language to be checked. The full power of Rascal is available for writing the constraints and for how these are attached to syntax rules.
• TypePal solves the staging of information by using a constraint solver that schedules constraints based on available information.
• TypePal provides a flexible and extensible built-in notion of Scope Graphs that can be used to model declarations, semantic links between modules, and the like.

TypePal uses two stages called Collector and Solver as shown in the diagram above. The Collector:

• Gathers facts from the parsed source code;
• Collects defines and uses of names;
• Creates calculators that describe how the type of more complex language constructs can be calculated based on their parts. Example: what is the type of a + expression?
• Creates requirements that are well-described. For instance, the condition of an if then statement should be of type Boolean.

The Solver uses the collected facts as a starting point and iteratively processes calculators and requirements as soon as their prerequisite information is available. The result is a so-called TModel that contains the type of parts of the source code, all definitions, use-def information, semantic links between modules, and possible messages (using Rascal’s Message data type).

The following code snippet checks the addition operator in a very simple programming language. Essentially, we require that the type of the left-hand side, respectively, the right-hand side of the expression, is equal to the integer type. If not, we give a tailored error message. This example is similar but not identical to the screenshot shown above.

void collect((Expression) `<Expression lhs> + <Expression rhs>`, Collector c){
   c.requireEqual(lhs, intType(),
      error(lhs, "Left argument of `+` should be `int`, found %t", lhs));
   c.requireEqual(rhs, intType(),
      error(rhs, "Right argument of `+` should be `int`, found %t", rhs));
   c.fact(current, intType());
   collect(lhs, rhs, c);
}

Key takeaways

1. TypePal has been used in dozens of open-source and commercial projects. The Rascal typechecker uses TypePal and is provided as part of the Rascal VS Code plugin.
2. A TModel can be used to provide information to the IDE (outline, hover help, document links, refactoring, suggestions for fixes), a compiler, or other tools.
3. At Swat.engineering, TypePal is our tool of choice to effectively create high-quality and well-maintainable typecheckers and compilers while working on old and new DSLs.

Further reading

• TypePal Documentation
• The ScopeGraphs used in TypePal are inspired by Uwe Kastens & William Waite, Name analysis for modern languages: a general solution, Software Practice & Experience, Wiley, 2017

Get in touch

Interested in writing a typechecker for your DSL? Designing a validator for some data format? We’re happy to discuss these and similar problems and help you to leverage TypePal.